Cro-Marmot's Blog

發表於 更新於 分類於 ， Disqus： 文章字數： 169 所需閱讀時間 ≈ 1 分鐘

Java 整理

core java

##《Java项目开发全程实录 第3版》个人整理

涉及知识一览

按层次

其它

按目录

  1. SQL Server 2000, PowerDesigner
  2. JavaDB
  3. Hibernate Oracle
  4. SQL Server 2005, Visio
  5. SQL Server 2000
  6. JavaDB, 短信猫 Java Mail
  7. Hibernate, Spring
  8. SQL Server 2005
  9. no Swing, jsp, javaBean, SQL Server 2000, Tomcat, Proxool
  10. Socket, thread

TODO

IoC

AOP

Spring

Swing

个人账目管理

發表於 更新於 分類於 ， Disqus： 文章字數： 1.3k 所需閱讀時間 ≈ 5 分鐘
C++手工优化

Minimum_maintenance.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

//template
#include<iostream>
#include<cstdlib>
#include<assert.h>
using namespace std;
struct max_select{
  int p;
  int d;
  double v;
  bool operator > (const max_select & other) const {
    return v > other.v;
  }
  bool operator < (const max_select & other) const {
    return v < other.v;
  }
  bool operator == (const max_select & other) const {
    return v == other.v;
  }
};

template <class T>
class Minimum_maintenance {
  private:
    T * _stack[2]; // 0 store Descending sequence, 1 store other's
    int _iter[2];    // store iter
    int * _order;    // for push and pop
    int * _fakedeepcopy ;
  public:
    Minimum_maintenance(){
      cout<<"NOT SUPPORT"<<endl;
      assert(0);
    }
    Minimum_maintenance(int s){
      if(s < 1)//protect
        s = 1;
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new T[s];
      _stack[1] = new T[s];
      _order = new int[s];
      _fakedeepcopy = new int [1] ;
      printf("new (%08x)\n",this);
      printf("    _stack[0] = (%08x)\n",_stack[0]);
      printf("    _stack[1] = (%08x)\n",_stack[1]);
      printf("    _order    = (%08x)\n",_order);
      _fakedeepcopy[0] = 0;
    }
    Minimum_maintenance(const Minimum_maintenance& copy){
      _stack[0]   = copy._stack[0];
      _stack[1]   = copy._stack[1];
      _iter [0]   = copy._iter [0];
      _iter [1]   = copy._iter [1];
      _order      = copy._order;
      _fakedeepcopy = copy._fakedeepcopy;
      _fakedeepcopy[0]++;
      printf("Fake deepcopy %08x => %08x\n",&copy,this);
    }
    ~Minimum_maintenance(){
      printf("free(%08x)\n",this);
      printf("    _fakedeepcopy = %d\n",_fakedeepcopy[0]);
      printf("    _stack[0]   = (%08x)\n",_stack[0]);
      printf("    _stack[1]   = (%08x)\n",_stack[1]);
      printf("    _order      = (%08x)\n",_order);
      if(!_fakedeepcopy[0]){
        delete [] _stack[0];
        delete [] _stack[1];
        delete [] _order;
      }else{
        _fakedeepcopy[0]--;
      }
      cout<<"free() finished"<<endl;
    }
    void push(const T & ms){
      int i;
      if(_iter[0] == 0 || _stack[0][_iter[0] - 1] > ms){
        i = 0;
      }else{
        i = 1;
      }
      _stack[i][_iter[i]] = ms;

      _order[_iter[0]+_iter[1]] = i;
      _iter[i] ++ ;
    }
    void pop(){
      if(_iter[0]+_iter[1]){
        _iter[_order[ _iter[0] + _iter[1] - 1 ]]--;
      }
    }
    bool top(T & ms){
      if(!(_iter[0]+_iter[1]))
        return false;
      int o = _order[ _iter[0] + _iter[1] - 1];
      ms = _stack[0][ _iter[0] - 1];
      return true;
    }
    bool const empty(){
      return _iter[0] == 0;
    }
};

int main(){
  int i;
  Minimum_maintenance<max_select> mm(20);
  for( i = 0; i < 20 ; i ++){
    double in = rand()*1.0;
    cout<<in<<endl<<"\t";
    max_select inms = {1,1,in};
    mm.push(inms);
    while(rand()%2){
      cout<< " POP ";
      mm.pop();
    }
    max_select ms;
    if(mm.top(ms))//mm.empty()
      cout<<ms.v<<endl;
    else
      cout<<"EMPTY()"<<endl;
  }
  return 0;
}

Minimum_maintenance.old1.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// just run
#include<iostream>
#include<cstdlib>
using namespace std;
class MinimumMaintenance {
  private:
    int * _stack[2]; // 0 store Descending sequence, 1 store other's
    int _iter[2];    // store iter
    int * _order;    // for push and pop
  public:
    MinimumMaintenance(int s){
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new int[3*s];
      _stack[1] = new int[3*s];
      _order = new int[s];
    }
    ~MinimumMaintenance(){
      delete [] _stack[0];
      delete [] _stack[1];
      delete [] _order;
    }
    void push(int p,int d,int v){
      int i;
      if(_iter[0] == 0 || _stack[0][3*(_iter[0] - 1)+2] > v){
        i = 0;
      }else{
        i = 1;
      }
      _stack[i][3*_iter[i]    ] = p;
      _stack[i][3*_iter[i] + 1] = d;
      _stack[i][3*_iter[i] + 2] = v;

      _order[_iter[0]+_iter[1]] = i;
      _iter[i] ++ ;
    }
    void pop(){
      if(_iter[0]+_iter[1]){
        _iter[_order[ _iter[0] + _iter[1] - 1 ]]--;
      }
    }
    bool top(int & p,int & d,int &v){
      if(!(_iter[0]+_iter[1]))
        return false;
      int o = _order[ _iter[0] + _iter[1] - 1];
      p = _stack[0][ 3 * _iter[0] - 3];
      d = _stack[0][ 3 * _iter[0] - 2];
      v = _stack[0][ 3 * _iter[0] - 1];
      return true;
    }
};
int main(){
  int i;
  MinimumMaintenance mm(20);
  for( i = 0; i < 20 ; i ++){
    int in = rand();
    cout<<in<<endl<<"\t";
    mm.push(1,1,in);
    while(rand()%2){
      cout<< " POP ";
      mm.pop();
    }
    int a,b,c;
    if(mm.top(a,b,c))
      cout<<c<<endl;
    else
      cout<<"EMPTY()"<<endl;
  }
  return 0;
}

Minimum_maintenance.old2.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
//struct
#include<iostream>
#include<cstdlib>
using namespace std;
struct max_select{
  int p;
  int d;
  double v;
};
class Minimum_maintenance {
  private:
    max_select * _stack[2]; // 0 store Descending sequence, 1 store other's
    int _iter[2];    // store iter
    int * _order;    // for push and pop
  public:
    Minimum_maintenance(int s){
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new max_select[s];
      _stack[1] = new max_select[s];
      _order = new int[s];
    }
    ~Minimum_maintenance(){
      delete [] _stack[0];
      delete [] _stack[1];
      delete [] _order;
    }
    void push(const max_select & ms){
      int i;
      if(_iter[0] == 0 || _stack[0][_iter[0] - 1].v > ms.v){
        i = 0;
      }else{
        i = 1;
      }
      _stack[i][_iter[i]] = ms;

      _order[_iter[0]+_iter[1]] = i;
      _iter[i] ++ ;
    }
    void pop(){
      if(_iter[0]+_iter[1]){
        _iter[_order[ _iter[0] + _iter[1] - 1 ]]--;
      }
    }
    bool top(max_select & ms){
      if(!(_iter[0]+_iter[1]))
        return false;
      int o = _order[ _iter[0] + _iter[1] - 1];
      ms = _stack[0][ _iter[0] - 1];
      return true;
    }
};
int main(){
  int i;
  Minimum_maintenance mm(20);
  for( i = 0; i < 20 ; i ++){
    double in = rand()*1.0;
    cout<<in<<endl<<"\t";
    max_select inms = {1,1,in};
    mm.push(inms);
    while(rand()%2){
      cout<< " POP ";
      mm.pop();
    }
    max_select ms;
    if(mm.top(ms))
      cout<<ms.v<<endl;
    else
      cout<<"EMPTY()"<<endl;
  }
  return 0;
}

Minimum_maintenance.old3.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
//operator
#include<iostream>
#include<cstdlib>
using namespace std;
struct max_select{
  int p;
  int d;
  double v;
  bool operator > (const max_select & other) const {
    return v > other.v;
  }
  bool operator < (const max_select & other) const {
    return v < other.v;
  }
  bool operator == (const max_select & other) const {
    return v == other.v;
  }
};
class Minimum_maintenance {
  private:
    max_select * _stack[2]; // 0 store Descending sequence, 1 store other's
    int _iter[2];    // store iter
    int * _order;    // for push and pop
  public:
    Minimum_maintenance(int s){
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new max_select[s];
      _stack[1] = new max_select[s];
      _order = new int[s];
    }
    ~Minimum_maintenance(){
      delete [] _stack[0];
      delete [] _stack[1];
      delete [] _order;
    }
    void push(const max_select & ms){
      int i;
      if(_iter[0] == 0 || _stack[0][_iter[0] - 1] > ms){
        i = 0;
      }else{
        i = 1;
      }
      _stack[i][_iter[i]] = ms;

      _order[_iter[0]+_iter[1]] = i;
      _iter[i] ++ ;
    }
    void pop(){
      if(_iter[0]+_iter[1]){
        _iter[_order[ _iter[0] + _iter[1] - 1 ]]--;
      }
    }
    bool top(max_select & ms){
      if(!(_iter[0]+_iter[1]))
        return false;
      int o = _order[ _iter[0] + _iter[1] - 1];
      ms = _stack[0][ _iter[0] - 1];
      return true;
    }
};
int main(){
  int i;
  Minimum_maintenance mm(20);
  for( i = 0; i < 20 ; i ++){
    double in = rand()*1.0;
    cout<<in<<endl<<"\t";
    max_select inms = {1,1,in};
    mm.push(inms);
    while(rand()%2){
      cout<< " POP ";
      mm.pop();
    }
    max_select ms;
    if(mm.top(ms))
      cout<<ms.v<<endl;
    else
      cout<<"EMPTY()"<<endl;
  } 
  return 0;
}

Minimum_maintenance.old4.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
//template
#include<iostream>
#include<cstdlib>
using namespace std;
struct max_select{
  int p;
  int d;
  double v;
  bool operator > (const max_select & other) const {
    return v > other.v;
  }
  bool operator < (const max_select & other) const {
    return v < other.v;
  }
  bool operator == (const max_select & other) const {
    return v == other.v;
  }
};

template <class T>
class Minimum_maintenance {
  private:
    T * _stack[2]; // 0 store Descending sequence, 1 store other's
    int _iter[2];    // store iter
    int * _order;    // for push and pop
  public:
    Minimum_maintenance(){
      // CHANGE?
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new T[1];
      _stack[1] = new T[1];
      _order = new int[1];
    }
    Minimum_maintenance(int s){
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new T[s];
      _stack[1] = new T[s];
      _order = new int[s];
    }
    ~Minimum_maintenance(){
      delete [] _stack[0];
      delete [] _stack[1];
      delete [] _order;
    }
    void resize(int s){
      delete [] _stack[0];
      delete [] _stack[1];
      delete [] _order;
      _iter[0] = 0;
      _iter[1] = 0;
      _stack[0] = new T[s];
      _stack[1] = new T[s];
      _order = new int[s];
    }
    void push(const T & ms){
      int i;
      if(_iter[0] == 0 || _stack[0][_iter[0] - 1] > ms){
        i = 0;
      }else{
        i = 1;
      }
      _stack[i][_iter[i]] = ms;

      _order[_iter[0]+_iter[1]] = i;
      _iter[i] ++ ;
    }
    void pop(){
      if(_iter[0]+_iter[1]){
        _iter[_order[ _iter[0] + _iter[1] - 1 ]]--;
      }
    }
    bool top(T & ms){
      if(!(_iter[0]+_iter[1]))
        return false;
      int o = _order[ _iter[0] + _iter[1] - 1];
      ms = _stack[0][ _iter[0] - 1];
      return true;
    }
    bool empty(){
      return _iter[0] == 0;
    }
};
int main(){
  int i;
  Minimum_maintenance<max_select> mm;
  mm.resize(20);
  for( i = 0; i < 20 ; i ++){
    double in = rand()*1.0;
    cout<<in<<endl<<"\t";
    max_select inms = {1,1,in};
    mm.push(inms);
    while(rand()%2){
      cout<< " POP ";
      mm.pop();
    }
    max_select ms;
    if(mm.top(ms))//mm.empty()
      cout<<ms.v<<endl;
    else
      cout<<"EMPTY()"<<endl;
  } 
  return 0;
}

發表於 更新於 分類於 Disqus： 文章字數： 1.5k 所需閱讀時間 ≈ 5 分鐘

permutation_traversal.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
//10 - 0.2s
#include<iostream>
using namespace std;

int pt_s;

void ptdemo(unsigned int pt_bits){
  if(pt_bits == (1<<pt_s) - 1)
    return ;
  unsigned int i;
  for(i = 0; i < pt_s ; ++i){
    if( pt_bits & (1<<i) )
      continue ; 
    //cout<<i<<endl;
    int debug = i;
    ptdemo(pt_bits | (1<<i));
  }
  return ;
}
int main(){
  pt_s = 10;
  int v = 0;
  ptdemo(v);
  return 0;
}

permutation_traversal.old1.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
//10 - 11.588 
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Permutation_traversal{
  protected:
    vector<int>left_index; // to boost vector?
    stack<pair<vector<int>::iterator,int>>visitstack; // to boost list?
    vector<int>::iterator iter;
    Permutation_traversal(const vector<int>&li,const stack<pair<vector<int>::iterator,int>>&vs)
    :left_index(li),visitstack(vs){
      iter = left_index.begin();
    }
  public:
    Permutation_traversal(int s){
      for(int i=0;i<s;i++){
        left_index.push_back(i);
      }
      iter = left_index.begin();
    }
    
    bool const empty(){
      return left_index.empty();
    }
    void next(){
      if(iter == left_index.end())
        return ;
      ++iter;
    }

    bool const valid(){
      return iter != left_index.end();
    }

    int getnum(){
      return visitstack.size();
    }

    int const getvalue(){
      return iter != left_index.end() ? *iter : -1;
    }
    void push(){
      if(iter == left_index.end())
        return ;
      visitstack.push(make_pair(iter,*iter));
      left_index.erase(iter);
    }
    void pop(){
      if(visitstack.empty())
        return ;
      pair<vector<int>::iterator,int> p = visitstack.top();
      left_index.insert(p.first,p.second);
      visitstack.pop();
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      return new Permutation_traversal(left_index,visitstack);
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    //for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    //cout<<pt.getvalue()<<endl;
    int debug = pt.getvalue();
    pt.push();
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
    pt.pop();
  }
  return ;
}
int main(){
  Permutation_traversal pt(10);
  ptdemo(pt);
  return 0;
}

permutation_traversal.old1.min.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
// ,min.cpp use less check
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Permutation_traversal{
  protected:
    vector<int>left_index; // to boost vector?
    stack<pair<vector<int>::iterator,int>>visitstack; // to boost list?
    vector<int>::iterator iter;
    Permutation_traversal(const vector<int>&li,const stack<pair<vector<int>::iterator,int>>&vs)
    :left_index(li),visitstack(vs){
      iter = left_index.begin();
    }
  public:
    Permutation_traversal(int s){
      for(int i=0;i<s;i++){
        left_index.push_back(i);
      }
      iter = left_index.begin();
    }
    
    bool const empty(){
      return left_index.empty();
    }
    void next(){
      ++iter;
    }

    bool const valid(){
      return iter != left_index.end();
    }

    int const getvalue(){
      return *iter;
    }
    void push(){
      visitstack.push(make_pair(iter,*iter));
      left_index.erase(iter);
    }
    void pop(){
      pair<vector<int>::iterator,int> p = visitstack.top();
      left_index.insert(p.first,p.second);
      visitstack.pop();
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      return new Permutation_traversal(left_index,visitstack);
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    cout<<pt.getvalue()<<endl;
    pt.push();
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
    pt.pop();
  }
  return ;
}
int main(){
  Permutation_traversal pt(5);
  ptdemo(pt);
  return 0;
}

permutation_traversal.old2.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
//10 4.469s
#include<iostream>
#include<vector>
using namespace std;

class Permutation_traversal{
  protected:
    vector<int>left_index; // to boost vector?
    vector<int>::iterator iter;
    Permutation_traversal(const vector<int>&li)
    :left_index(li){
      iter = left_index.begin();
    }
  public:
    Permutation_traversal(int s){
      for(int i=0;i<s;i++){
        left_index.push_back(i);
      }
      iter = left_index.begin();
    }
    
    bool const empty(){
      return left_index.empty();
    }
    void next(){
      if(iter == left_index.end())
        return ;
      ++iter;
    }

    bool const valid(){
      return iter != left_index.end();
    }


    int const getvalue(){
      return iter != left_index.end() ? *iter : -1;
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      if(iter == left_index.end())
        return NULL;
      vector<int>::iterator tmp_iter = iter;
      int tmp_val = *iter;
      left_index.erase(iter);
      Permutation_traversal * newpt = new Permutation_traversal(left_index);
      left_index.insert(tmp_iter,tmp_val);
      return newpt;
    }
    // debug [TODO]remove code below
    int getnum(){
      return 5-left_index.size();
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    //for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    //cout<<pt.getvalue()<<endl;
    int debug = pt.getvalue();
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
  }
  return ;
}
int main(){
  Permutation_traversal pt(10);
  ptdemo(pt);
  return 0;
}

permutation_traversal.old2.min.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Permutation_traversal{
  protected:
    vector<int>left_index; // to boost vector?
    vector<int>::iterator iter;
    Permutation_traversal(const vector<int>&li)
    :left_index(li){
      iter = left_index.begin();
    }
  public:
    Permutation_traversal(int s){
      for(int i=0;i<s;i++){
        left_index.push_back(i);
      }
      iter = left_index.begin();
    }
    
    bool const empty(){
      return left_index.empty();
    }
    void next(){
      ++iter;
    }

    bool const valid(){
      return iter != left_index.end();
    }


    int const getvalue(){
      return *iter;
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      vector<int>::iterator tmp_iter = iter;
      int tmp_val = *iter;
      left_index.erase(iter);
      Permutation_traversal * newpt = new Permutation_traversal(left_index);
      left_index.insert(tmp_iter,tmp_val);
      return newpt;
    }
    // debug [TODO]remove code below
    int getnum(){
      return 5-left_index.size();
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    cout<<pt.getvalue()<<endl;
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
  }
  return ;
}
int main(){
  Permutation_traversal pt(5);
  ptdemo(pt);
  return 0;
}

permutation_traversal.old3.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
//10 - 0.927s
#include<iostream>
using namespace std;

class Permutation_traversal{
  protected:
    int * left_index; // to boost vector?
    int size;
    int iter;
    Permutation_traversal(){
    }
  public:
    Permutation_traversal(int s)
    :size(s),iter(0){
      left_index = new int[s];
      for(int i=0;i<s;i++){
        left_index[i]=i;
      }
    }
    ~Permutation_traversal(){
      delete [] left_index;
    }
    bool const empty(){
      return size == 0;
    }
    void next(){
      if(iter == size)
        return ;
      ++iter;
    }

    bool const valid(){
      return iter != size;
    }

    int const getvalue(){
      return iter != size ? left_index[iter] : -1;
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      if(iter == size)
        return NULL;
      Permutation_traversal * newpt = new Permutation_traversal();
      newpt->left_index = new int[size-1];
      newpt->size = 0;
      newpt->iter = 0;
      for(int it = 0 ; it < size ; ++it){
        if(it == iter)
          continue;
        newpt->left_index[newpt->size++] = left_index[it];
      }
      return newpt;
    }
    // debug [TODO]remove code below
    int getnum(){
      return 5-size;
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    //for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    //cout<<pt.getvalue()<<endl;
    int debug = pt.getvalue();
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
  }
  return ;
}
int main(){
  Permutation_traversal pt(10);
  ptdemo(pt);
  return 0;
}

permutation_traversal.old3.min.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<iostream>
#include<vector>
#include<stack>
using namespace std;

class Permutation_traversal{
  protected:
    int * left_index; // to boost vector?
    int size;
    int iter;
    Permutation_traversal(){
    }
  public:
    Permutation_traversal(int s)
    :size(s),iter(0){
      left_index = new int[s];
      for(int i=0;i<s;i++){
        left_index[i]=i;
      }
    }
    ~Permutation_traversal(){
      delete [] left_index;
    }
    bool const empty(){
      return size == 0;
    }
    void next(){
      ++iter;
    }

    bool const valid(){
      return iter != size;
    }

    int const getvalue(){
      return left_index[iter];
    }

    Permutation_traversal * isolate(){// careful about memory overflow
      Permutation_traversal * newpt = new Permutation_traversal();
      newpt->left_index = new int[size-1];
      newpt->size = 0;
      newpt->iter = 0;
      for(int it = 0 ; it < size ; ++it){
        if(it == iter)
          continue;
        newpt->left_index[newpt->size++] = left_index[it];
      }
      return newpt;
    }
    // debug [TODO]remove code below
    int getnum(){
      return 5-size;
    }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    cout<<pt.getvalue()<<endl;
    Permutation_traversal * child_pt = pt.isolate();
    ptdemo(*child_pt);
    delete child_pt;
  }
  return ;
}
int main(){
  Permutation_traversal pt(5);
  ptdemo(pt);
  return 0;
}

permutation_traversal.old4.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
//10 - 0.581s
#include<iostream>
using namespace std;

class Permutation_traversal{
  private:
  class Child_Permutation_traversal{
    public:
      int * left_index; // to boost vector?
      int size;
      int iter;
      Child_Permutation_traversal(int s)
        :size(s),iter(0){
          left_index = new int[s];
        }
      ~Child_Permutation_traversal(){
        delete [] left_index;
      }
  };

  Child_Permutation_traversal ** cpt;
  int size;
  int depth;
  public:
  Permutation_traversal(int s)
  :size(s){
    cpt = new Child_Permutation_traversal * [s + 1];
    int i;
    for(i = 0; i <= s; i++){
      cpt[i] = new Child_Permutation_traversal(s-i);
    }
    for(i = 0; i < s; i++){
      cpt[0]->left_index[i]=i;
    }
    depth = 0;
  }
  ~Permutation_traversal(){
    for(int i=0;i<=size;i++){
      delete cpt[i];
    }
    delete [] cpt;
  }
  bool const empty(){
    return cpt[depth]->size == 0;
  }
  void next(){
    if(cpt[depth]->iter == cpt[depth]->size)
      return ;
    ++(cpt[depth]->iter);
  }
  
  bool const valid(){
    return cpt[depth]->iter != cpt[depth]->size;
  }
  
  int const getvalue(){
    return cpt[depth]->iter != cpt[depth]->size ? cpt[depth]->left_index[cpt[depth]->iter] : -1;
  }

  void select(){
    if(cpt[depth]->iter == cpt[depth]->size)
      return ;
    int newdepth = depth + 1;
    cpt[newdepth]->size = 0;
    cpt[newdepth]->iter = 0;
    for(int it = 0,itlimit=cpt[depth]->size ; it < itlimit ; ++it){
      if(it == cpt[depth]->iter)
        continue;
      cpt[newdepth]->left_index[cpt[newdepth]->size++] = cpt[depth]->left_index[it];
    }
    depth = newdepth;
  }

  void unselect(){
    if(depth > 0)
      --depth;
  }

  int getnum(){
    return 5-cpt[depth]->size;
  }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    //for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    //cout<<pt.getvalue()<<endl;
    int debug = pt.getvalue();
    pt.select();
    ptdemo(pt);
    pt.unselect();
  }
  return ;
}
int main(){
  Permutation_traversal pt(10);
  ptdemo(pt);
  return 0;
}

permutation_traversal.old4.min.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//10 - 0.472s
#include<iostream>
using namespace std;

class Permutation_traversal{
  private:
  class Child_Permutation_traversal{
    public:
      int * left_index; // to boost vector?
      int size;
      int iter;
      Child_Permutation_traversal(int s)
        :size(s),iter(0){
          left_index = new int[s];
        }
      ~Child_Permutation_traversal(){
        delete [] left_index;
      }
  };

  Child_Permutation_traversal ** cpt;
  int size;
  int depth;
  public:
  Permutation_traversal(int s)
  :size(s){
    cpt = new Child_Permutation_traversal * [s + 1];
    int i;
    for(i = 0; i <= s; i++){
      cpt[i] = new Child_Permutation_traversal(s-i);
    }
    for(i = 0; i < s; i++){
      cpt[0]->left_index[i]=i;
    }
    depth = 0;
  }
  ~Permutation_traversal(){
    for(int i=0;i<=size;i++){
      delete cpt[i];
    }
    delete [] cpt;
  }
  bool const empty(){
    return cpt[depth]->size == 0;
  }
  void next(){
    ++(cpt[depth]->iter);
  }
  
  bool const valid(){
    return cpt[depth]->iter != cpt[depth]->size;
  }
  
  int const getvalue(){
    return cpt[depth]->left_index[cpt[depth]->iter];
  }

  void select(){
    int newdepth = depth + 1;
    cpt[newdepth]->size = 0;
    cpt[newdepth]->iter = 0;
    for(int it = 0,itlimit=cpt[depth]->size ; it < itlimit ; ++it){
      if(it == cpt[depth]->iter)
        continue;
      cpt[newdepth]->left_index[cpt[newdepth]->size++] = cpt[depth]->left_index[it];
    }
    depth = newdepth;
  }

  void unselect(){
      --depth;
  }

  int getnum(){
    return 5-cpt[depth]->size;
  }
};

void ptdemo(Permutation_traversal & pt){
  if(pt.empty())
    return ;
  for(;pt.valid();pt.next()){
    //for(int i=0,limiti=pt.getnum();i<limiti;i++)cout<<" ";
    //cout<<pt.getvalue()<<endl;
    int debug = pt.getvalue();
    pt.select();
    ptdemo(pt);
    pt.unselect();
  }
  return ;
}
int main(){
  Permutation_traversal pt(10);
  ptdemo(pt);
  return 0;
}

發表於 更新於 分類於 ， Disqus： 文章字數： 1.9k 所需閱讀時間 ≈ 7 分鐘 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
# coding: utf-8

__version__ = '1.1.0'
__author__ = 'Zhu Jianqi (heloowird@gmail.com)'

'''
以关键词收集新浪微博
'''
import requests
import wx
import csv
import codecs
import sys
import urllib
import urllib2
import re
import json
import hashlib
import os
import time
import datetime
import random
from lxml import etree
import logging
import gzip
from StringIO import StringIO

class CollectData():
    """数据收集类
        利用微博高级搜索功能，按关键字搜集一定时间范围内的微博。

        大体思路：构造URL，爬取网页，然后解析网页中的微博ID。后续利用微博API进行数据入库。本程序只负责收集微博的ID。

        登陆新浪微博，进入高级搜索，输入关键字”空气污染“，选择”实时“，时间为”2013-07-02-2:2013-07-09-2“，地区为”北京“，之后发送请求会发现地址栏变为如下：
        http://s.weibo.com/wb/%25E7%25A9%25BA%25E6%25B0%2594%25E6%25B1%25A1%25E6%259F%2593&xsort=time&region=custom:11:1000&timescope=custom:2013-07-02-2:2013-07-09-2&Refer=g

        是不是很长，其实很简单。
            固定地址部分：http://s.weibo.com/wb/
            关键字二次UTF-8编码：%25E7%25A9%25BA%25E6%25B0%2594%25E6%25B1%25A1%25E6%259F%2593
            排序为“实时”：xsort=time
            搜索地区：region=custom:11:1000
            搜索时间范围：timescope=custom:2013-07-02-2:2013-07-09-2
            可忽略项：Refer=g
            显示类似微博：nodup=1    注：这个选项可多收集微博，建议加上。默认不加此参数，省略了部分相似微博。
            某次请求的页数：page=1

        另外，高级搜索最多返回50页微博，那么时间间隔设置最小为宜。所以该类设置为搜集一定时间段内最多50页微博。
    """
    def __init__(self, keyword, startTime, savedir, interval='50', flag=True, begin_url_per = "http://s.weibo.com/weibo/"):
        self.begin_url_per = begin_url_per  #设置固定地址部分，默认为"http://s.weibo.com/weibo/"，或者"http://s.weibo.com/wb/"
        self.setKeyword(keyword)    #设置关键字
        self.setStartTimescope(startTime)   #设置搜索的开始时间
        # self.setRegion(region)  #设置搜索区域
        self.setSave_dir(savedir)   #设置结果的存储目录
        self.setInterval(interval)  #设置邻近网页请求之间的基础时间间隔（注意：过于频繁会被认为是机器人）
        self.setFlag(flag)  #设置
        self.logger = logging.getLogger('main.CollectData') #初始化日志

    ##设置关键字
    ##关键字需解码
    def setKeyword(self, keyword):
        #self.keyword = keyword.decode('GBK').encode("utf-8")
        self.keyword = keyword
        print 'twice encode:',self.getKeyWord()

    ##设置起始范围，间隔为1小时
    ##格式为：yyyy-mm-dd-HH
    def setStartTimescope(self, startTime):
        if not (startTime == '-'):
            self.timescope = startTime + ":" + startTime
        else:
            self.timescope = '-'

    # ##设置搜索地区
    # def setRegion(self, region):
    #     self.region = region

    ##设置结果的存储目录
    def setSave_dir(self, save_dir):
        self.save_dir = save_dir
        if not os.path.exists(self.save_dir):
            os.mkdir(self.save_dir)

    ##设置邻近网页请求之间的基础时间间隔
    def setInterval(self, interval):
        self.interval = int(interval)

    ##设置是否被认为机器人的标志。若为False，需要进入页面，手动输入验证码
    def setFlag(self, flag):
        self.flag = flag

    ##构建URL
    def getURL(self):
        return self.begin_url_per+self.getKeyWord()+"&typeall=1&suball=1"+"&timescope=custom:"+self.timescope+"&page="

    ##关键字需要进行两次urlencode
    def getKeyWord(self):
        once = urllib.urlencode({"kw":self.keyword})[3:]
        return urllib.urlencode({"kw":once})[3:]

    ##爬取一次请求中的所有网页，最多返回50页
    def download(self, url, maxTryNum=4):
        csvFile = open(self.save_dir + os.sep + "weibo_kanbing.csv", "ab")  #向结果文件中写微博ID
        csvFile.write(codecs.BOM_UTF8)
        content = csv.writer(csvFile, dialect='excel')
        headers = {'User-Agent': 'Mozilla/5.0 (Windows NT 6.1; WOW64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/56.0.2924.87 Safari/537.36'}
        cookie = {'SINAGLOBAL':'3726160468139.8677.1489128973894', 'un':'18621677460', 'wvr':'6', 'SWB':'usrmdinst_12', 'SCF':'At4nsWXnBTiLQgwnhEdGW1ipfDRoyBYdEIpm4KN7_ZN3C0BxRlQeyX0sHoQOK6bDqLR6HeBBiwo6wRFXfObIvnc.', 'SUB':'_2A251wx_bDeRxGeNP7FIR9yjFwzyIHXVWuXYTrDV8PUNbmtBeLRjVkW8ia3o1WnWjknWq3t_Uh0UkKzBqsg..', 'SUBP':'0033WrSXqPxfM725Ws9jqgMF55529P9D9Wh_ODAX.pd3QJ6U3yvqGKET5JpX5KMhUgL.Fo-pS057S0q41h52dJLoIEUBBEXLxKqL1hnL1KnLxK-LBKeLB-zLxK-L1K5L1K2LxK-L12qLBoet', 'SUHB':'0vJ4Ss25HO1Ohu', 'ALF':'1521001227', 'SSOLoginState':'1489465228', '_s_tentry':'login.sina.com.cn', 'Apache':'7301168373695.357.1489465207066', 'ULV':'1489465207130:8:8:5:7301168373695.357.1489465207066:1489412710557', 'UOR':',,login.sina.com.cn', 'WBStorage':'02e13baf68409715|undefined'}

        hasMore = True  #某次请求可能少于50页，设置标记，判断是否还有下一页
        isCaught = False    #某次请求被认为是机器人，设置标记，判断是否被抓住。抓住后，需要复制log中的文件，进入页面，输入验证码
        filter = set([])    #过滤重复的微博ID

        i = 1   #记录本次请求所返回的页数
        while hasMore and i < 51 and (not isCaught):    #最多返回50页，对每页进行解析，并写入结果文件
            source_url = url + str(i)   #构建某页的URL
            data = ''   #存储该页的网页数据
            goon = True #网络中断标记

            ##网络不好的情况，试着尝试请求三次
            for tryNum in range(maxTryNum):
                try:
                    # set header http://stackoverflow.com/questions/385262/how-do-i-send-a-custom-header-with-urllib2-in-a-http-request
                    # see this http://stackoverflow.com/questions/1653591/python-urllib2-response-header , so you can see 'gzip' in response header with urllib2.urlopen(URL).info()
                    # and this http://stackoverflow.com/questions/3947120/does-python-urllib2-automatically-uncompress-gzip-data-fetched-from-webpage teach you how to decode gzip
                    #
                    #r = requests.get(source_url, cookies=cookie, headers=headers, timeout=12)
                    send_headers = {
                            "Accept":"text/html,application/xhtml+xml,application/xml;q=0.9,image/webp,*/*;q=0.8",
                            "Accept-Encoding":"gzip, deflate, sdch",
                            "Accept-Language":"zh-CN,zh;q=0.8,en;q=0.6",
                            "Cache-Control":"no-cache",
                            "Connection":"keep-alive",
                            #"Cookie":"cookies here"
                            "Host":"s.weibo.com",
                            "Pragma":"no-cache",
                            "Referer":"http://s.weibo.com/",
                            "Upgrade-Insecure-Requests":"1",
                            "User-Agent":"Mozilla/5.0 (X11; Linux x86_64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/55.0.2883.87 Safari/537.36"
                            }
                    req = urllib2.Request(source_url , headers=send_headers)
                    r = urllib2.urlopen(req)
                    if r.info().get('Content-Encoding') == 'gzip':
                        buf = StringIO(r.read())
                        f = gzip.GzipFile(fileobj=buf)
                        html = f.read()
                    else:
                        html = r.read()
                    data = html
                    #print data
                    break
                except:
                    if tryNum < (maxTryNum-1):
                        time.sleep(10)
                    else:
                        print 'Internet Connect Error!'
                        self.logger.error('Internet Connect Error!')
                        self.logger.info('filePath: ' + self.save_dir)
                        self.logger.info('url: ' + source_url)
                        self.logger.info('fileNum: ' + str(fileNum))
                        self.logger.info('page: ' + str(i))
                        self.flag = False
                        goon = False
                        break
            if goon:
                lines = data.splitlines()
                isCaught = True
                for line in lines:
                    ## 判断是否有微博内容，出现这一行，则说明没有被认为是机器人
                    if line.startswith('<script>STK && STK.pageletM && STK.pageletM.view({"pid":"pl_weibo_direct"'):
                        isCaught = False
                        n = line.find('html":"')
                        if n > 0:
                            j = line[n + 7: -12].encode("utf-8").decode('unicode_escape').encode("utf-8").replace("\\", "").decode('utf-8')
                            ## 没有更多结果页面
                            if (j.find('<div class="search_noresult">') > 0):
                                hasMore = False
                            ## 有结果的页面
                            else:
                                page = etree.HTML(j)
                                comment_box = page.xpath("//div[@action-type=\"feed_list_item\"]")
                                for each_comment in comment_box:
                                    comment_time = each_comment.xpath(".//div[@class=\"feed_from W_textb\"]/a/@title")
                                    comment_text_list = each_comment.xpath(".//p[@class='comment_txt']")
                                    comment_text = []
                                    for eachtext in comment_text_list:
                                        comment_text = 'r'.join(eachtext.xpath(".//text()"))
                                        comment_text = comment_text.replace(' ','').replace('\n', '').replace('\r', ' ')
                                        comment_text = comment_text.encode('utf8')
                                        if (comment_text != 'None' and comment_text not in filter):
                                            filter.add(comment_text)
                                            content.writerow([comment_time[0], comment_text])
                                # weibo = page.xpath("//div[@class=\"feed_from W_textb\"])
                                # for weibo_time, weibo_content in weibo:
                                #     weibo_time = weibo_time.xpath("./[@class=\"feed_from W_textb\"]/a/@title")
                                #     concept = 'r'.join(weibo_content.xpath("./text()"))
                                #     concept = concept.replace(' ','').replace('\n','').replace('\r',' ')
                                #     concept = concept.encode('utf8')
                                #     if (concept != 'None' and concept not in filter):
                                #         filter.add(concept)
                                #         content.writerow([weibo_time, concept])

                                # dls_id = page.xpath("//div[@class=\"feed_from W_textb\"]/a/@title")
                                # for dl_id in dls_id:
                                #     # mid = str(dl_id.attrib.get('nick-name'))
                                #     dl_id = dl_id.encode('utf8')
                                #     if (dl_id != 'None' and dl_id not in mid_filter):
                                #         mid_filter.add(dl_id)
                                #         content.writerow([dl_id])
                                #
                                # dls_text = page.xpath("//p[@class='comment_txt']")
                                # for dl_text in dls_text:
                                #     concept = 'r'.join(dl_text.xpath("./text()"))
                                #     concept = concept.replace(' ','').replace('\n','').replace('\r',' ')
                                #     concept = concept.encode('utf8')
                                #     if (concept != 'None' and concept not in mid_filter):
                                #         mid_filter.add(concept)
                                #         content.writerow([concept])
                                        # content.writerow('\n')
                                    # if (concept != 'None' and concept not in mid_filter):
                                    #     mid_filter.add(concept)
                                    #     content.write(concept)
                                    #     content.write('\n')
                                    # print concept
                                    # print "----------------------"
                        break
                lines = None
                ## 处理被认为是机器人的情况
                if isCaught:
                    print 'Be Caught!'
                    self.logger.error('Be Caught Error!')
                    self.logger.info('filePath: ' + self.save_dir)
                    self.logger.info('url: ' + source_url)
                    self.logger.info('fileNum: ' + str(fileNum))
                    self.logger.info('page:' + str(i))
                    data = None
                    self.flag = False
                    break
                ## 没有更多结果，结束该次请求，跳到下一个请求
                if not hasMore:
                    print 'No More Results!'
                    if i == 1:
                        time.sleep(random.randint(55,75))
                    else:
                        time.sleep(15)
                    data = None
                    break
                i += 1
                ## 设置两个邻近URL请求之间的随机休眠时间，防止Be Caught。目前没有模拟登陆
                # sleeptime_one = random.randint(self.interval-30,self.interval-10)
                # sleeptime_two = random.randint(self.interval+10,self.interval+30)
                # if i%2 == 0:
                #     sleeptime = sleeptime_two
                # else:
                #     sleeptime = sleeptime_one
                # print 'sleeping ' + str(sleeptime) + ' seconds...'
                # time.sleep(sleeptime)
            else:
                break
        csvFile.close()
        csvFile = None

    ##改变搜索的时间范围，有利于获取最多的数据
    def getTimescope(self, perTimescope, hours):
        if not (perTimescope=='-'):
            times_list = perTimescope.split(':')
            start_datetime = datetime.datetime.fromtimestamp(time.mktime(time.strptime(times_list[-1],"%Y-%m-%d-%H")))
            start_new_datetime = start_datetime + datetime.timedelta(seconds = 3600)
            end_new_datetime = start_new_datetime + datetime.timedelta(seconds = 3600*(hours-1))
            start_str = start_new_datetime.strftime("%Y-%m-%d-%H")
            end_str = end_new_datetime.strftime("%Y-%m-%d-%H")
            return start_str + ":" + end_str
        else:
            return '-'

def main():
    logger = logging.getLogger('main')
    logFile = './collect.log'
    logger.setLevel(logging.DEBUG)
    filehandler = logging.FileHandler(logFile)
    formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s: %(message)s')
    filehandler.setFormatter(formatter)
    logger.addHandler(filehandler)

    while True:
        ## 接受键盘输入
        keyword = raw_input('Enter the keyword(type \'quit\' to exit ):')
        if keyword == 'quit':
            sys.exit()
        startTime = raw_input('Enter the start time(Format:YYYY-mm-dd-HH):')
        # region = raw_input('Enter the region([BJ]11:1000,[SH]31:1000,[GZ]44:1,[CD]51:1):')
        savedir = raw_input('Enter the save directory(Like C://data//):')
        interval = raw_input('Enter the time interval( >30 and deafult:50):')

        ##实例化收集类，收集指定关键字和起始时间的微博
        cd = CollectData(keyword, startTime, savedir, interval)
        while cd.flag:
            print cd.timescope
            logger.info(cd.timescope)
            url = cd.getURL()
            cd.download(url)
            cd.timescope = cd.getTimescope(cd.timescope,1)  #改变搜索的时间，到下一个小时
        else:
            cd = None
            print '-----------------------------------------------------'
            print '-----------------------------------------------------'
    else:
        logger.removeHandler(filehandler)
        logger = None
if __name__ == '__main__':
    main()

發表於 更新於 分類於 ， Disqus： 文章字數： 566 所需閱讀時間 ≈ 2 分鐘

四种指针

参考文

个人整理

四个智能指针: auto_ptr, shared_ptr, weak_ptr, unique_ptr 其中后三个是c++11支持，并且第一个已经被c++11弃用。

用于测试的结构体

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Test
{
public:
    Test(string s)
    {
        str = s;
       cout<<"Test creat\n";
    }
    ~Test()
    {
        cout<<"Test delete:"<<str<<endl;
    }
    string& getStr()
    {
        return str;
    }
    void setStr(string s)
    {
        str = s;
    }
    void print()
    {
        cout<<str<<endl;
    }
private:
    string str;
};

auto_ptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int main()
{
    auto_ptr<Test> ptest(new Test("123"));
    ptest->setStr("hello 0");
    ptest->print();
    ptest.get()->print();
    ptest->getStr() += "world !";
    (*ptest).print();
    ptest.reset(new Test("567"));
    ptest->print();

    auto_ptr<Test> ptest(new Test("789"));
    auto_ptr<Test> ptest2(new Test("JQK"));
    ptest2 = ptest;
    ptest2->print();
    if(ptest.get() == NULL)cout<<"ptest = NULL\n";
    return 0;
}

输出

1
2
3
4
5
6
7
8
9
10
11
12
13
Test creat
hello 0
hello 0
hello 0world !
Test creat
Test delete:hello 0world !
567
Test creat
Test creat
Test delete:JQK
789
Test delete:789
Test delete:567

unique_ptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
unique_ptr<Test> fun()
{
    return unique_ptr<Test>(new Test("789"));
}
int main()
{
    unique_ptr<Test> ptest(new Test("123"));
    unique_ptr<Test> ptest2(new Test("456"));
    ptest->print();
    ptest2 = std::move(ptest);//不能直接ptest2 = ptest
    if(ptest == NULL)cout<<"ptest = NULL\n";
    Test* p = ptest2.release();
    p->print();
    ptest.reset(p);
    ptest->print();
    ptest2 = fun(); //这里可以用=，因为使用了移动构造函数
    ptest2->print();
    return 0;
}

输出

1
2
3
4
5
6
7
8
9
10
11
Test creat
Test creat
123
Test delete:456
ptest = NULL
123
123
Test creat
789
Test delete:789
Test delete:123

share_ptr

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int main()
{
    shared_ptr<Test> ptest(new Test("123"));
    shared_ptr<Test> ptest2(new Test("456"));
    cout<<ptest2->getStr()<<endl;
    cout<<ptest2.use_count()<<endl;
    ptest = ptest2;//"456"引用次数加1，“123”销毁
    ptest->print();
    cout<<ptest2.use_count()<<endl;//2
    cout<<ptest.use_count()<<endl;//2
    ptest.reset();
    ptest2.reset();//此时“456”销毁
    cout<<"done !\n";
    return 0;
}

输出

1
2
3
4
5
6
7
8
9
Test creat
Test creat
456
1
Test delete:123
456
2
2
Test delete:456

总结

auto_ptr

  • 手动释放资源 .reset()
  • 将指针置空,返回资源控制权 .release()
  • 用 .get()==NULL 判断是否为空

unique_ptr

  • 和auto_ptr相似
  • 不能使用两个智能指针赋值操作，应该使用std::move
  • 可以直接用if(ptest == NULL)来判断是否空指针

share_ptr

  • 使用计数机制来表明资源被几个指针共享,.use_count()来查看资源的所有者个数
  • 没有release

weak_ptr

  • weak_ptr是用来解决shared_ptr相互引用时的死锁问题,如果说两个shared_ptr相互引用,那么这两个指针的引用计数永远不可能下降为0,资源永远不会释放。它是对对象的一种弱引用，不会增加对象的引用计数，和shared_ptr之间可以相互转化，shared_ptr可以直接赋值给它，它可以通过调用lock函数来获得shared_ptr。

發表於 更新於 分類於 Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘

很久以前就有听说这个命题

但我始终也不能说出个所以然,最多的个人体验也就是root权限

知乎这种逐渐变为垃圾问答区的地方，显然是大量的0说服力的答案,慢慢变成百度知道了:-)

搜了一篇 当做英文休闲阅读了

original link

写在前面

  • windows的想法是好的,闭源比开源更难攻击
  • 事实上并没有得到预期的更好,由永无休止的补丁可证(?啊,Linux 没补丁的咯?)

这里的意思并没有反驳闭源的安全性比开源更好 同样的linux(闭) > linux(开) > windows(闭) > 同样的windows(开)

安全性:同样A,A(闭源) > A(开源)，但开源带来的可以让A变成A+ 那么安全性上,A+(开) 是可能 > A(闭)的

权限

windows

  • 日常运行 对于文件:高权限
  • 能够操作任何电脑上任何文件

Linux

  • 日常运行 对于文件:低权限
  • 只能操作当前用户有权限的文件

也就是说用户的文件等在Linux 还是有同样的风险?

这里原文没有说细,[对于不同用户,windows是可以操作他人的文件,而linux可一通过权限控制在一个用户内+共享?]

小总结:Linux 也不是绝对可靠

  • 更难发生系统级别的破坏
  • 更难发生用户层面广泛的破坏

社社社…社会工程学

好吧 说得有那么一点道理 (这里也有执行时需要权限属于上一部分的东西)

病毒呢 传播时 通常诱导用户添加/点击/安装

说是windos呢 例子:给个带exe附件的邮件并诱导你下载点击，然后 就完事了 (简言之 点3下就可以入侵)

但是linux呢 你下下来给它执行权限chmod么才行(简言之 要执行过程复杂繁琐+运行有系统级别破坏时需要系统权限)

个人看法

  • 不认可
  • 如果把两边用户交换一下,linux 也能提供点3下就执行程序的,并且目前的易用操作系统的流程已经很简洁了
  • 感觉这一点 大自和用户习惯,使用方式,社区安全,用的人少相联系

单种效应

…….这个名词 瞎翻译的,说的是 windows就一个,但linux 有各种分支,不同的邮件客户端,不同的架构,然后病毒的兼容性很难实现…..

仔细想一想 还是有那么些道理的 但我只想到作为server端，比如架构

外网—我们的linux1—我们的linux2—我们的linux3—我们的linux4(服务)—我们的linux5(数据)

那么要从外网进攻, 至少需要4个不同兼容性 而window就just do it again....
讲道理的话....真有做这么多层这样防护的吗,目前只了解到 有 外网-server1-服务-数据这样的

以及,本身作为非系统的server的话,在不同的linux之间的移植能力，也会比 攻击程序 的移植能力强。

感觉有那么一些道理,对我还不是太有说服力，感觉比第二点说服力强很多

用户多

个人看法

  • 不认可
  • 这只能说可能是 当下linux比当下window安全的一个原因
  • 并不想讨论当下 我更喜欢数学上的 如果有相同的用户量呢 如果linux 比windows用户更多呢,如果真的是因为用户少而更安全,那我认为是无数学上的优势的
  • 其它看法linux desktop 少，但linux server多啊 虽然数据并不多到那里去数据

开源

就是上面我自己碎碎念的

大量的人能看到代码的bug,并及时去维护。

有利有弊吧

总结

啊,唯一让我满意一点的就是权限的说明了…

这篇文章也没有深入到系统里,感觉还是很表面的东西,不过windows也不开源,不知道能不能找到逆向工程出来的系统级别的,和linux的系统级别的深入比较的文章。。。恩 我不打算自己研究 还是看文章好了，期望能找到

之后在一个长篇的知乎回答上得到了一点对于权限的补充说明”其繁殖速度必须超过其死亡(被消灭)的速度”

所以,我现在能想到一个没有杀软的linux的进攻(相对于windows点3下)即是 下载并运行(社会工程学:-))->写入用户的需要管理员权限的可执行文件/脚本文件?->用户执行了它->达到和windows点3下同样能达到的效果

發表於 更新於 分類於 Disqus： 文章字數： 1.1k 所需閱讀時間 ≈ 4 分鐘

mongodb 学习记录

本文依赖

nodejs

mongodb

angularjs

记录

工作总图

Detail

nodejs

事件驱动可扩展性，端到端

npm install

npm search

npm install -g

npm install -g npm-check

npm-check -u -g

模块封装

事件模型 阻塞I/O

发送接受P59

1
2
3
4
5
6
var events = require("events");
var emitter=events.EventEmitter();
emitter.emit(eventName,data);
.addListener(eventName,callback(data))
.on(eventName,callback(data))
.once(eventName,callback(data))

json/buffer/stream(网页流数据/压缩解压) -P90

文件系统 -P107

require(“fs”)

HTTP:

1
2
3
require("http")
require("url")
require("querystring")

HTTPS:P127-

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/*
openssl genrsa -out server.pem 2048
openssl req -new -key server.pem -out server.csr
openssl x509 -req -days 365 -in server.csr -signkey server.pem -out server.crt
*/
var https = require("https");                                                                                                                          
var fs = require("fs");
var options = {
  key: fs.readFileSync("./server.pem"),
  cert: fs.readFileSync("./server.crt")
};
https.createServer(options,function(req,res){
  res.writeHead(200);
  res.end("Hello Secure World\n");
}).listen(8128);

socket P132-

多处理器

process

child_process

cluster,worker实现多个”线程”监听一个port并可自动处理cluster_server.js /cluster_worker.js/cluster_client.js

1
2
3
process.stdin.on("data",function(data){;});
process.on("SIGINT",function(){;});
process.on("SIGBREAK",function(){;});

https://raw.githubusercontent.com/bwdbooks/nodejs-mongodb-angularjs-web-development/master/ch09/process_info.js

exec() / execFile()/spawn()

其它模块介绍,runnoob上也有https://nodejs.org/api/

os见os_info.js

util有format,log,debug,checktype,转对象为字串原型继承见util_inherit.js

dns有lookup不同level的resolve

Express(server)

npm install express

route,Error handle,易于集成,cookie,会话缓存

_http_https.js require('url')

1
2
3
app.get('/user/:userid',function(req.res){
	res.send("Get User: "+ req.param("userid"));
});

express_routes.js 路由demo/req.params/正则/Request对象/Response对象

express_json.js/express_send_file.js/res.download([path])/res.redirect()

模板引擎ejs+jade,express_templates.js and other files

中间件大法

app.use(path,bodyParser()).use(path,bodyParser()).use(path,bodyParser());

app.get(path,bodyParser(),function(req,res){});

  • static 内置 流式处理静态文件访问
  • express-logger
  • basic-auth-connect基本身份验证
  • cookie-parser读取设置cookie
  • cookie-session/会话支持
  • express-session,相当强大会话实现
  • body-parser req正文中的JSON解析为req.body
  • compression 对客户端大响应提供Gzip支持
  • csurf 跨站点请求 伪造保护

res.query. 用于查询把url转化为json

静态文件服务

app.use(pathurl,express.static(path_file_or_dir_local)[,config]);//maxAge hidden redirect index

auth_session.js 会话+验证

mongodb(NoSQL)

针对文档，高性能，高可用性，高可扩展性

安装

mongodb类型

基础教程

封顶集合(capped collection) 超过大小以旧的替代新的

索引？分片？复制？

生命周期？应用程序代码控制或者TTL

1
2
3
4
help <option>
use <database>
show <option> (such as dbs,collections,profile,log)
exit

用户管理身份验证-P196

数据库管理

1
2
3
4
5
6
7
8
9
db.copyDatabase(origin,destination)
db.dropDatabase()
db.createCollection("collectionname")
coll =db.getCollection("collectionname")
coll.drop()
coll.find({'key':'value'})
coll.insert({'key':'value'})
coll.remove({'key':'value'})
coll.update(where,set,other option) //inc set push sort等update运算符

mongo+nodejs

1
2
npm install mongo
npm install mongoose

见 db_connect_object.js

demo

db,Admin,Collection,Cursor对象

atomically:findAndModify()/findAndRemove()

upsert()/save()/remove()

mongo可以直接执行js :generate_data.js

count / limit

aggregate([{$match:{tasdf:X"}},{$group:{asdf:"agqwe",sdfo:{$sum:"agqwe"}}}]) //mapreduce? 聚合

mongoose结构化模式与验证

mongoose/schema/query/Document

mongoose_find.js/_create.js/_save/_update_one

***.validate(function(value){;})

中间件

pre/post

mongoDB高级

ensureIndex /MongoClient

分片集群等等 GridFS/GridStore

修复 备份

angularjs

数据绑定，可扩展性，整洁，可重用，整洁，支持，兼容性

MVC

node_server.jssimple demo

专有对象提供器animation,controller,filter,directive

服务提供器value,constant,factory,service,provider

注入21 injector.js

作用域+广播emit/broadcast/on->event的属性targetScope/currentScope/name/stopPropagation/preventDefault/defaultPrevented

ng-model,data-ng-model,x-ng:model,ng_model 都被规范化为ngModel

内置过滤器currency,filter:exp:compare,json,limitTo:limit,lowercase,uppercase,number[:fraction],orderBy:exp:reverse,date[:format]

DIY过滤器

1
2
3
4
angular.module(***).filter('fff',function(){return function(leftinput,argument){return result;}})
controller('aController',['$scope','fffFilter',function($scope,fffFilter){
	;//直接在html上用 或者 用作函数也行
}])

支持AngularJS模板功能的指令/表单 P411-419

24directive_custom.js/html

  • template允许你定义插入指令的元素的AngularJS模板
  • templateUrl同上但是是url
  • restrict允许你指定该指令 A属性名E元素名C类名
  • replace取代元素
  • transclude内部是否可以访问内部作用域以外的作用域
  • scope指定内部作用域，{}隔离 @funcname/@ 绑定到DOM = 双向绑定 & 局部绑定到指定scope
  • link指定 作用域 DOM元素 和其它能操作DOM属性的链接函数
  • controller
  • require所需要的其它指令

内置常用服务

animate(css),cacheFactory,compile,cookies,document,http,interval,locale,location,resource,rootElement,rootScope,route,sce,templateCache,timeout/interval,window.alert,

$http 请求delete/get/head/jsonp/post/put

26章完整登陆注册验证实例

社交媒体账户作为身份验证来源 npm install passport/passport-google/passport-facebook/passport-twitter 已验证后的序列化和反序列化 google_auth.js

27定义评论回复照片和页面模型 /mongoose model schema的应用 更复杂的控制实现 和 angularJS的service应用/

28购物车 mongoose model schema的应用

建议的代码文件结构方式,代码编码顺序[bg(node)/view(html[css])/fg(angularJS)]

29 选项卡 天气服务 可拖动组件 交互表格数据

發表於 更新於 分類於 ， Disqus： 文章字數： 271 所需閱讀時間 ≈ 1 分鐘

贡献

  • 提供了系统分类的RDF存储管理器实现
  • 容易检测到特定RDF存储管理器实现之间的差异
  • 通过多进程环境获取有关有效进程的属性。

Single(T,I,Q,S,J,C,D,F)

Table

  • vertical
  • property
  • horizontal

Indexx structure

  • 6-independent
  • GSPO-PGPS
  • matrix

Query type

  • SPARQL
  • original

String translation method

  • URI
  • literal
  • long
  • none

Join optimization method

  • RDBMS-based
  • column-strore-based
  • conventional ordering
  • pruning
  • none

Cache type

  • materialized-path-index
  • reified-statement
  • none

Dabase engine type

  • RDB
  • custom

inference Feature type

  • TBox 本体推断
  • ABox 断言推断
  • no

Multiple(D,Q,S,A)

Data distribution method

  • hash
  • data-source
  • none

Query process distribution method type

  • data-parallel
  • data-replication
  • none

Stream process

  • pipeline
  • none

sharing Architecture

  • memory
  • disk
  • nothing
name T I Q S J C D F D Q S A
3store v S U R R T n n n
4store v S U o R h p n
Virtuoso v G S Ulo R R TA n n n
RDF-3X v 6 S Ul o R n n n
Hexastore v 6 o Ul n n n n
Apache Jena p S Ulo R r R n n n
SW-store h Uo c m c n n n
BitMat v m S Ul p c p
AllegroGraph S c h p m
Haddop/HBase h c p m
wukong v ??? S Ul c+? ? R? ? dh? p p m

發表於 更新於 分類於 ， Disqus： 文章字數： 1.2k 所需閱讀時間 ≈ 4 分鐘

dgraph engine for web scale rdf data

ABSTRACT

现有的对于网络范围的RDF数据现有依然不是高效的,内部存储不用bitmap,other operations,

INTRODUCTION

挑战:可扩展性(急切)和普遍性,需要分布式,现有依然三元组,join巨大中间结果,过大的开销 通常指数级 ,现有不支持更有意义的查询 仅仅对SPARQL优化

作者的成就:分布式,处理billion even trillion triples ,不用 relational tables and bitmap matrices,build on top of a memory cloud,首先说 随机访问的情况下 用硬盘储存三元组不够优良 ,就算有好的索引也会因为额外的join操作,作为主要的查询中 耗时,in-memory graph exploration instead of join operations for SPARQL processing ,作为对比 之前的系统 孤立使用自己划分的三元组 没有用已有的 造成了很大的中间额外开销,介绍如何降低join 数量 如何降低中间过程的大小,并且就算没有足够好的划分 也有优秀的性能,我们允许大范围的图分析

  1. 新的基于图表的管理RDF数据 ,有对于RDf 高效基于图查询 和 图分析 的可能性
  2. 新的查询规范(相对于SPARQL)有效的提高性能 减少总监结果 和提高系统可扩展性
  3. 新的价值模型 新的基数估计基数 分布式查询生成的优化算法 ,这些成果提供 在web 范围 RDF数据上 出色的性能

Section 2 join操作 和 图探索 的区别. Section 3 Trinity.RDF 系统的架构. Section 4 how we model RDF data as native graphs. Section 5 describes SPARQL query processing techniques. Section 6 shows experimental results. We conclude in Section 8.

Join vs. Graph Exploration

RDF and SPARQL 的介绍 和 缺点(join 耗费高 中间无用结果大)

图探索 介绍方法 并说需要更高效的储存方式来适应这种方法 用native graph 会把原来的每次 读入O(log N)的时间复杂度降低为O(1) 需要搜索的顺序优化来

System Architecture

就是图储存,并且完全存在内存里 (因为是分布式的所以才可以储存这么多)

架构client,proxy,string server,trinity machine [看来陈榕老师就是按照这样的思路改的代码

Data Modeling

(node-id, in-adjacency-list, out-adjacency-listi)

讲图分割问题 对于自然图 用大度的点 连接点来决定放置未知 以及使用 in out间接id 可以有效减少发送数据交流量

但是对于邻点少的来说用另一种方法更好 同一个点的in和out放在同一个机器上的方法

还用了

  • 本地 谓词索引 sort all (predicate, node-id )
  • 全局的 谓词索引 (predicate, hsubject-list i , object-list i i)

提供基本图操作

  1. LoadNodes(predicate, direction): Return nodes that have an incoming or outgoing edge labeled as predicate. 使用全局谓词索引
  2. LoadNeighborsOnMachine(node, direction, machine i): For a given node, return its incoming or outgoing neighbors that reside on machine i. 返回的是上面的间接id
  3. SelectByPredicate(nid, predicate): From a given partial adjacency list specified by nid, return nodes that are labeled with the given predicate.
    Figure 4.
    LoadNodes(l2 , out) finds n2 on machine 1, and n3 on machine 2. LoadNeighborsOnMachine(n0 , in, 1) returns the partial adjacency list’s id in1 , and SelectByP redicate(in1 , l2 ) returns n2 .

Query Processing

先把 查询Q拆分为 q1 q2 q3…qn，然后让它们并行寻找 再最后再和并

单个q的匹配方式

For a triple pattern q, our goal is to find all its matches R(q). Let P de[notes] the predicate in q, V denote the variables in q, and B(V ) denote the binding of V . If V is a free variable (not bound), we also use B(V ) to denote all possible values V can take.

从 S 去找 O ,写作q→

从 O 去找 S ,写作q←

分为两个阶段

src

用LoadNodes(本机)找到基于 所有可能predicate 的所有可能的src

对于所有可能src 在所有机器LoadNeighborsOnMachine(有远端操作)找nid_i 把结果M再发给所有机器

tgt

对于收到的结果M 的每一个(src,nid)

找所有的可能的predicate

用 SelectByPredicate(本机) 交 所有可能的tgt 得到R

方案是 合并相邻 的操作来减少中间过程的损耗

然后讲优化 也就是顺序优化

注意到用了合并以后 前面j个操作 只要集合相同 那么结果与前面j个的内部顺序无关

我们使用 启发式算法

Heuristic 1. We expand a subgraph from its exploration point. We combine two subgraphs by connecting their exploration points.

Property 1. We expand a subgraph or combine two subgraphs through an edge. The two nodes on both ends of the edge are valid exploration points in the new graph.

Theorem 1. For a query graph G(V, E), the DP has time complexity O(n·|V |·|E|) where n is the number of connected subgraphs in G.

Theorem 2. Any acyclic query Q with query graph G is guaranteed to have an exploration plan.

Discussion. There are two cases we have not considered formally: i) G is cyclic, and ii) G contains a join on predicates.

發表於 更新於 分類於 ， Disqus： 文章字數： 16k 所需閱讀時間 ≈ 57 分鐘

ABSTRACT

这个论文写的是RDF-3X的引擎,一个基于SPARQL的实现，并超级高效,小心的设计出的追求RISC格式和流线型结构和的简洁的数据结构和操作。

  1. 储存和索引3元RDF的通用解决方案,且完全不用做物理设计的调整。
  2. 一个强力且简单的query处理器对最大可能性范围利用快速合并。
  3. 一个用基于整个连接路径的统计对照表的耗费模型来选择最优合并顺序的query优化程序

RDF-3X与先前最先进的系统相比，在几个大规模数据集上进行测量，这些数据集具有超过5000万个RDF三元组和基准查询，包括模式匹配和长连接路径 基础数据图。

INTRODUCTION

Motivation and Problem

RDF数据结构已经存在了十年,它被设计为对于语义Web的模式松弛或甚至无模式的信息的灵活表示。到商业化的今天的电子世界，RDF也没有得到太多的关注，但RDF建立了强大的动力。语义网络风格的本身和知识是基于数百万现实来自维基百科和其它在线已经创建并可获取的来源。E-science数据容器以导入/导出的格式支持RDF,并也可以筛数据选(基于query),更引人注目的,是在生命科学领域。最终,Web 2.0平台的在线社区将RDF视为非专有交换格式,并将其作为构建信息混搭的工具。

在RDF格式中，所有的数据元素都表示为(subject,predicate,object) 三元组,有的是(subject,property,value)三元组,例如

  • (id1, hasT itle, ”Sweeney T odd”),
  • (id1, producedInYear, ”2007”),
  • (id1, directedBy, ”T im Burton”),
  • (id1, hasCasting, id2),
  • (id2, RoleN ame, ”Sweeney T odd”), (id2, Actor, id11),
  • (id1, hasCasting, id3),
  • (id3, RoleN ame, ”M rs. Lovett”), (id3, Actor, id12),
  • (id11, hasN ame, ”Johnny Depp”),
  • (id12, hasN ame, ”Helena Bonham Carter”)

这样,注意到predicate和属性没有两样,并且这没有数据库模式,这种三元组的概念非常适合现在的随收随付(pay as you go),和实体关系模型相比,都有实体的属性和关系/谓语,所有的三元组放在一起可以看作一个巨大的层次结构图。

SPARQL查询语言是官方标准用来搜索RDF仓库。它支持三元组的conjunctions 和 disjunctions,在关系引擎中选择项目连接查询的对应项。比如我们可以得到Johnny Depp 的电影的title用 SPARQL查询语句:

1
2
3
Select ?title Where {
?m <hasTitle> ?title. ?m <hasCasting> ?c.
?c <Actor> ?a. ?a <hasName> "Johnny Depp" }

这里每一个点代表一个conjunction(join),整个查询也可以看做在RDF数据图中做图模式匹配,predicates 也可以是变量或者通配符,因此也允许未知模式的查询。

RDF驱动用于储存索引和查询已经有一些年了,尤其是the Jena frame-work by HP Labs 显著收到欢迎,and Oracle also provides RDF support for semantic data integration in life sciences and enterprises [11, 29]. However, with the exception of the VLDB 2007 paper by Abadi et al. [1], none of the prior implementations could demonstrate convincing efficiency, failing to scale up towards large datasets and high load. [1] achieves good performance by grouping triples with the same property name into property tables, mapping these onto a column store, and creating materialized views for frequent joins

管理大规模RDF数据需要很多技术挑战，包括储存布局,索引和查询过程。

  1. (没有固定结构与实际的数量大变化频繁的矛盾)缺少全局模式和谓词名称的多样性对物理数据库设计提出了主要问题。原则上，可以依靠自动调谐“向导”来实现频繁的连接路径;然而在实践中，数据的不断发展的结构和不一致动态的工作量将这个问题变成一个复杂的西斯弗斯任务。
  2. (join 查询多难预测 RDF为动态应用空间 需要适合的动态优化查询算法)通过RDF数据 - 三元组而不是整个记录或实体的细粒度建模 - 具有大量连接的查询将固有地形成工作负载的大部分，但连接属性比关系设置中的可预测性要差得多。这要求查询处理算法的特定选择，以及对复杂连接查询的仔细优化;但RDF是用于在数据空间上的即时应用程序，因此优化发生在查询运行时。
  3. (需要统计来 找到 优化方案 不同优化方案的适应度差别大)由于连接顺序和其他执行计划优化需要数据统计来进行选择性估计，因此RDF引擎面临的问题是，在没有模式的情况下，统计信息收集的合适粒度是显而易见的。例如，在工作负载的where子句中出现的所有属性的单维直方图 - 关系系统中的最先进的方法 - 不适用于RDF，因为它错过了长连接链或大连接星的影响多对多关系。
  4. (和XML样子像但是具体差别挺大)虽然RDF使用XML语法，而SPARQL涉及类似于XML路径表达式的搜索模式，但是RDF三元组形成图形而不是树的集合的事实是对更深入研究的XML设置的主要区别。

Contribution and Outline

本文为上述问题提供了一个全面，可扩展的解决以上问题的方案。 它提供了一个完整的系统，创造的RDF-3X（RDF Triple eXpress），从头设计和实现，专门用于管理和查询RDF数据。 RDF-3X遵循[24,39]中倡导的为特定应用领域设计和定制的数据管理系统可以通过两个数量级来超越通用主流系统的原理。 在这个论点的因素包括

  1. 数据结构和算法的裁剪，而不是支持更多各种各样的方法
  2. 更轻的软件脚印和开销，
  3. 简化的系统内部优化和更容易配置 和自适应变化的环境（例如，数据和工作量特性）。

RDF-3X遵循这种RISC风格的设计理念[10]，设计用于支持RDF的“精简指令集”.RDF-3X基于三个原则：

  1. 物理设计通过在单个“巨型三元组表”上创建适当的索引来独立于工作负载.RDF-3X不依赖于自动调整向导的成功（或限制），而是有效地消除了对物理设计调整的需要。它通过在构成RDF三元组的三个维度的所有6个排列上构建索引，并且附加地对所有三维二维和所有三个一维投影的计数聚合变体进行索引。每个索引都可以很好地压缩;所有索引的总存储空间小于主数据的大小。
  2. 查询处理器是RISC风格的，主要依赖于对排序后的索引列表的合并连接。这可以通过三元组表的“穷举”索引来实现。事实上，所有处理都是仅索引的，并且三元组表仅仅虚拟地存在。运算符树被构造以便在最大可能程度上保留后续连接的有趣顺序[17];只有当这不再可能时，RDF-3X才会切换到基于散列的连接处理。这种方法可以在代码级别进行高度优化，并且与传统查询处理器相比具有低得多的开销。同时，支持SPARQL的各种重复消除选项，查询中的分离模式以及SPARQL所需的所有其他功能也非常有用。
  3. 查询优化器主要关注执行计划生成时的连接顺序。它采用动态规划计划枚举，成本模型基于RDF特定的统计概要。这些统计包括数据图的路径中的频繁谓词序列的计数器;这样的路径是电位连接模式。与通用数据库系统中的查询优化器相比，RDF-3X优化器更简单，但在执行计划的选择性估计和决策方面更加准确。

这项工作的科学贡献是：

  1. 用于RDF索引和查询的新颖架构，消除对物理数据库设计的需要，
  2. 用于大规模连接查询在无结构的RDF三元组上的优化器，由新的对于RDF路径的选择性估计驱动，
  3. 基于具有三个大数据集的实际测量的综合性能评估，示出了先前最好的发动机[1]的大增益（对于一些查询，通常为5和高达20） 。 RDF-3X的源代码和实验数据可根据要求提供非商业用途。

BACKGROUND AND STATE OF THE ART

SPARQL

SPARQL查询[36]是构成RDF数据图的三元组上的模式匹配查询。 除了语法糖，一个基本的SPARQL查询具有形式

1
2
select ?variable1 ?variable2 ...
where { pattern1. pattern2. ... }

其中每个模式由subject，predicate，object组成其中的每一个都是变量或文字。 查询模型是和样例一样：查询指定已知的文字并将未知数保留为变量。 变量可以出现在多个模式中，由默认连接。 查询处理器需要查找满足给定模式的所有可能的变量绑定，并将来自projection子句的绑定返回到应用程序。 请注意，并非所有变量都必须绑定（例如，如果变量只出现在projection中，而不是在pattern中），这将返回NULL。

该模式匹配方法限制了关于可能的执行计划的查询引擎的自由度，如以下示例所示：

1
2
select ?a ?c
where { ?a label1 ?b. ?b label2 ?c }

用户对通过?b可以连接的所有?a和?c感兴趣。 ?b本身的值不是projection子句的一部分。 不幸的是，模式匹配语义要求仍然需要计算所有的?b的绑定。 可能有多种方式从?a到?c，导致输出重复。 由于这通常不是用户/应用程序的意图，SPARQL引入了两个查询修饰符：distinct关键字指定必须删除重复项，而reduced关键字指定重复项可以但不必删除。 reduced关键字的目标显然是通过允许优化来帮助RDF查询引擎，但是使用减少的选项，查询输出具有非确定性。

然而，即使是创建所有重复的默认模式允许一些优化。 查询处理器不能忽略由于它们对重复项的影响而被投影掉的变量，但是它不必创建显式绑定。 只要我们能保证产生正确数目的重复，绑定本身是不相关的。 我们稍后将通过计数重复项的数量而不是产生重复项本身来使用此观察。

大多数可公开访问的RDF系统将RDF三元组映射到关系表（例如，RDFSuite [2, 32], Sesame [8, 28], Jena [23, 46], the C-Store-based RDF engine of [1], and also Oracle’s RDF MATCH implementation [11]）。有两种极端的方式做到这一点：

  1. 所有三元组存储在一个单一的，巨大的三元组表与通用属性主题，谓词，对象。
  2. 三元组按其谓词名称分组，具有相同谓词名称的所有三元组存储在同一属性表中。可以使具有用于每个谓词名称的单独表的属性表的极端形式更加灵活，从而导致混合方法：
  3. 基于对于相同实体类的谓词或工作负载中的同现（co-occurrence），通过谓词名称对三元组进行聚类;

每个簇属性表包含少量相关谓词的值，并且对于具有不频繁谓词的三元组，可以另外存在“剩余”表。集群属性表具有类别特定的模式，其具有在相应的RDF谓词之后命名的属性，并且其宽度可以从单个谓词（属性）到相同实体类型的所有谓词。

早期的开源系统如Jena [23,46]和Sesame [8,28]使用集群属性表，但将物理设计留给了应用程序调优专家。这些系统都没有报告任何性能基准，大型数据在千兆字节范围内有超过1000万个三元组。 Oracle [29]在[11]中报告了非常好的性能结果，但是似乎在很大程度上依赖于良好的调整，除了基本的三元组表之外，通过正确选择物化连接视图（创建的主题 - 属性矩阵）。 [1]目前最快的RDF引擎使用最小宽度属性表（即二进制关系），但将它们映射到列存储系统。 [41]给出了不同存储布局的一个很好的分类，并提出了中型合成数据和合成工作负载的系统性能比较。与[1]针对“巨 - 三元组表”方法的论据相反，我们的RDF3X系统显示了如何成功地使用具有优异性能的三元组表。

性能最佳的系统，Oracle和C-Storebased的引擎擎，依赖于这些视图上的物化连接路径和索引。索引本身是分别由底层RDBMS和列存储支持的标准索引。本地YARS2系统[19]提出了在6个单独的B +树或散列索引中的三元组及其所有嵌入子三元组（对和单值）的详尽索引。这类似于我们的方法，但是YARS2忽略了在subject, predicate, object（作为主要，次要和第三级排序标准）的规范顺序之外的排序顺序中索引三元组。对于HPRD系统[6]提出了一个非常相似的方法，并在Sesame系统中作为选项（创造的“三重指数”）[28]。 YARS2和HPRD似乎主要适用于简单的查找操作，并且对连接的支持有限;他们缺乏DBMS风格的查询优化（例如，不考虑任何连接顺序优化，虽然[6]认识到这个问题）。 [5]提出使用后缀数组索引整个连接路径，但不讨论优化此物理设计的查询。 [42]介绍了一种基于明智选择的“中心节点”的新型路径索引;该指数，创造的GRIN，在小到中等数据和手指定的执行计划表现出良好的性能。在[12]中也讨论了模式无关的“宽和稀疏表”的物理设计，没有具体考虑RDF。所有这些用于RDF索引和物化视图的方法都会产生一些形式的物理设计问题，并且没有一个解决了这些物理设计特性所产生的查询优化问题。

对于查询优化，[11,29]和[1]利用与这些解决方案分层的SQL引擎一起提供的最先进的技术。 据我们所知，没有一个采用任何RDF本地优化。 [38]概述了代数重写的框架，但似乎性能增益的主要规则是推动选择低于连接; 没有考虑连接排序。 [20]具有类似的风格，同样忽视找到好的连接排序的关键问题。

最近，图上的SPARQL模式的选择性估计已经由[38]和[25]解决。方法[38]收集每个主题，每个谓词和每个对象（标签或值）的单独的频率统计;通过假设主语，谓词和对象分布在概率上是独立的来估计整个三元模式的频率。 [25]的方法通过在所选择的任意形状的图形模式的集合上建立统计来更加复杂。它将模式的选择转换为优化问题，并使用贪婪启发式。查询模式的基数估计识别统计存在的最大子模式，并且将它们与关于超级模式的统一性假设组合而没有统计。虽然[38]似乎太过于简单，不能产生准确的估计，方法[25]是基于一个复杂的优化问题，并依靠简单的启发式选择一组好的模式的总和结构。我们在RDF-3X中采用的方法捕获路径标签频率，从而超越[38]，但避免了计算的复杂性[25]。

STORAGE AND INDEXING

Triples Store and Dictionary

虽然大多数先前的，特别是最近的文献喜欢存储模式与属性表，我们决定采用概念上更简单的方法与单个，可能巨大的三元组表，我们自己的存储实现下面（相对于使用RDBMS ）。 这反映了我们的RISC风格和“无旋钮”设计理念。 我们克服了以前的批评，即通过创建“正确的”索引集合（见下文）和非常快速的合并连接处理（见第4节），三元组表会产生太多昂贵的自联接。

我们将所有三元组存储在（压缩的）聚类B +树中。三元组在B +树中按字典顺序排序，这允许将SPARQL模式转换为范围扫描。 在模式（literal1，literal2，?x）中，文字指定公共前缀，因此有效地进行范围扫描。 在对中等数量的叶页的单次扫描期间找到每个可能的?x的绑定。

因为三元组可以包含长字符串，所以我们采用使用字典+id映射替换所有字面量的方法（参见例如[11]）。这有两个好处：1）它压缩三元组存储，现在只包含id三元组，和2）它是查询处理器的一个伟大的简化，允许快速，简单，RISC式操作符（见第4.5节）。这些增益的小成本是两个附加的字典索引。在查询翻译期间，在查询中出现的文字被翻译成其字典id，这可以通过从字符串到id的标准B +树来完成。在处理查询之后，所得到的id必须被转换回文本作为应用/用户的输出。我们也可以在这个方向上使用B +树，但是我们实现了一个直接映射索引[14]。直接映射被调谐用于id查找并且导致更好的高速缓存命中率。请注意，这只是当查询产生很多结果时的问题。通常，先前的步骤（连接等）支配成本，但是对于具有许多结果字典查找的简单查询是不可忽略的。

id+字典的方式 提高效率

Compressed Indexes

在上面给出的索引范围扫描示例中，我们依赖于变量是后缀（即，对象或谓词和对象）的事实。 为了保证我们能够通过仅执行单个索引扫描来回答模式三元组的任何位置中的变量，我们在六个单独的维度中保持主语（S），谓词（P）和对象（O）的所有六个可能的排列 索引。 我们可以提供这种级别的冗余，因为我们压缩id三元组（下面讨论）。 在所有实验数据集上，所有索引的总大小小于原始数据。

由于六个索引中的每一个的排序规则顺序不同（SPO，SOP，OSP，OPS，PSO，POS），我们使用通用术语值1，值2，值3而不是主语，谓词， 不同列。 索引中的三元组通过（值1，值2，值3）（对于六个不同排列中的每一个）按字典顺序排序，并且直接存储在聚类B +树的叶页面中。

归类顺序使得相邻三元组非常相似：最邻近的三元组在值1和值2中具有相同的值，并且值3的增加趋向于非常小。 这个观察自然导致三元组的压缩方案。 代替存储完整的三元组，我们只存储三元组之间的变化。 这种压缩方案的灵感来自文本检索系统中的倒排列表[50]，但我们将其推广到id三元组而不是简单的id。 由于下面讨论的原因，我们只在单个叶子页面中应用压缩，而不是跨页面。

对于压缩方案本身，在压缩项目的解压缩或解释的空间节省和CPU消耗之间存在明显的权衡[45]。我们注意到，当压缩过于积极时，CPU时间开始成为一个问题，因此确定了一个字节级（而不是位级）压缩方案。我们计算每个值的增量，然后使用最小字节数来仅对增量编码。标题字节表示由以下值使用的字节数（图1）。每个值在0字节（不变）和4字节（delta需要完整的4字节）之间消耗，这意味着每个值有5个可能的大小。对于三个值，这些是5 * 5 * 5 = 125个不同大小的组合，其适合于报头字节的有效载荷。剩余间隙位用于指示小间隙：当仅值3改变，并且增量小于128时，其可以直接包括在报头字节的有效载荷中。这种小的delta是非常常见的，并且可以在我们的方案中由单个字节编码。

三元压缩伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
compress((v 1 , v 2 , v 3 ),(prev 1 , prev 2 , prev 3 ))
// writes (v 1 , v 2 , v 3 ) relative to (prev 1 , prev 2 , prev 3 )
if v 1 = prev 1 ∧ v 2 = prev 2
  if v 3 − prev 3 < 128
    write v 3 − prev 3
  else encode(0,0,v 3 − prev 3 − 128)
else if v 1 = prev 1
  encode(0,v 2 − prev 2 ,v 3 )
else
  encode(v 1 − prev 1 ,v 2 ,v 3 )
encode(δ 1 , δ 2 , δ 3 )
// writes the compressed tuple corresponding to the deltas
write 128+bytes(δ 1 )*25+bytes(δ 2 )*5+bytes(δ 3 )
write the non-zero tail bytes of δ 1
write the non-zero tail bytes of δ 2
write the non-zero tail bytes of δ 3

压缩的细节如上所示。算法计算前一个元组的增量。 如果它是小的，它被直接编码在标题字节中，否则它计算每个树值和调用编码的δi值。 编码用大小信息写头部字节，然后写入δi的非零尾部（即，它按字节写入i，但跳过前导零字节）。 这导致具有不同大小的压缩元组，但是在解压缩期间，可以容易地从报头字节重建大小。 由于所有操作都是逐字节的，解压缩仅涉及几个便宜的操作并且非常快。

我们测试了压缩率和解压时间（以秒为单位）的逐字节压缩与文献中提出的许多逐位压缩方案[33]。 Barton数据集（见第6节）的结果如图3所示。我们的逐字节方案压缩几乎与最佳逐位压缩方案一样好，同时提供更好的解压缩速度。在IR系统中倒置列表中流行的Gamma和Golomb压缩方法执行得更糟，因为在我们的设置中，每当三重前缀发生变化时，间隙就可能很大。

我们还在我们的压缩方案之上试验了更强大的LZ77压缩。有趣的是，我们的压缩方案使用LZ77比原始数据压缩更好，因为增量编码在三元组中表现出共同的模式。附加的LZ77压缩大约减少索引大小两倍，但显着增加CPU时间，这对于复杂查询将变得至关重要。因此，RDF-3X发动机不使用LZ77。

压缩索引的一个重要考虑是每个叶页是单独压缩的。压缩更大的数据块导致更好的压缩（特别是与LZ77压缩相结合），但是逐页压缩有几个优点。首先，它允许我们寻找（通过B +树遍历）任何叶子页面，并直接开始读取三元组。如果我们压缩更大的块，我们经常需要解压缩前面的页面。第二，压缩索引的行为就像一个正常的B +树（有一个特殊的叶编码）。因此，可以像标准B +树中那样容易地进行更新。这极大地简化了压缩索引与其余引擎的集成，并保持其RISC性质。特别是，我们可以采用先进的并发控制和恢复方法进行索引管理，而无需任何更改。

以上新的index 按字节压缩法索引方法 比既有所有的方案效率更优 大小更小(具体方法见上面伪代码)

Aggregated Indices

对于许多SPARQL模式，索引部分三元组而不是完全三元组就足够了，如以下SPARQL查询所示：

1
2
select ?a ?c
where { ?a ?b ?c }

它计算通过任何谓词连接的所有?a和?c，和?b的具体是什么无关的。

因此，我们另外构建聚合索引，每个索引只存储三元组的三个列中的两个。更确切地说，它们存储两个条目（例如，主体和对象）以及聚合计数，即，该对在三元组的全集中的对数的数量。这对于三个可能的三个对中的每一个以及在每个排序顺序（SP，PS，SO，OS，PO，OP）中进行，从而添加另外六个索引。

计数是必要的，因为SPARQL语义。在输出中不会出现?b的具体值，但是需要对重复正确的计数。注意，聚合索引比全三重索引小得多;由六个附加索引导致的总数据库大小的增加是可以忽略的。

代替（值1，值2，值3），聚合索引存储（值1，值2，计数），否则它们被组织在B +树中，就像全三重压缩索引。叶编码略有不同，因为现在大多数变化包括值2中的间隙和低计数值。伪码如图4所示。

最后，除了三元组中的这些索引之外，我们还构建了所有三个包含just（value 1，count）条目的单值索引（编码类似）。虽然仅使用一个变量的三元模式可能很少，但单值索引非常小，并且它们可用简化了查询翻译。

QUERY PROCESSING AND OPTIMIZATION

Translating SPARQL Queries

编译SPARQL查询的第一步是将其转换为适合稍后优化的演算表示。我们构造一个可以被解释为关系元组演算的查询图表示。从SPARQL派生域演算会更容易，但元组演算更容易优化。

虽然SPARQL允许许多语法快捷方式来简化查询制定，但每个（连接）查询都可以被解析并扩展为一组三重模式。三元组的每个组件是文字或变量。解析器已经执行字典查找，即文字被映射到id。与域微积分类似，SPARQL指定必须为数据中每个出现的纯文本三元组生成变量绑定。当查询由单个三元模式组成时，我们可以使用第3节中的索引结构，并使用单个范围扫描回答查询。当查询由多个三元模式组成时，我们必须连接各个模式的结果。因此，我们在查询图表示上采用连接排序算法，如下面进一步讨论的。

每个三元模式对应于查询图中的一个节点。在概念上，每个节点需要对整个数据库进行适当的变量绑定和由字面量所引起的选择的扫描。虽然每个扫描都可以实现为单个索引范围扫描，但优化程序可能会选择不同的策略（见下文）。查询图中的边缘反映变量出现次数。当且仅当它们具有共同的（查询）变量时，连接两个节点。

当查询的projection子句包含distinct选项时，我们添加一个聚合运算符，以消除结果中的重复项。最后，我们添加一个字典查找操作符，将生成的ids返回到字符串。

Optimizing Join Ordering

优化SPARQL执行计划的关键问题是连接排序。关于这个问题有大量文献，通常基于各种形式的动态规划（DP）或随机化（例如，[13,15,26,34]）的解决方案。然而，RDF和SPARQL的固有特性创建了具有特别要求的属性的联接查询，这些属性没有通过现有技术直接解决：

  1. PARQL查询往往包含星形子查询，用于组合同一实体的几个属性类属性。因此，必须使用可以创建浓密连接树（而不是专注于左深或右深树）的策略。
  2. 这些星形连接发生在长连接路径的各个节点，通常在路径的开始和结束。 SPARQL查询可以轻松导致三元组之间的10个或更多联接（例如，参见第6节中的我们的基准查询）。因此，精确优化需要非常快速的计划枚举和成本估计，或者需要求助于启发式近似。
  3. 我们希望利用我们的三重索引的特殊优势，鼓励大量使用合并连接（而不是哈希或嵌套循环连接），但这需要在生成连接计划时保持有趣的顺序非常小心。

他的第一个要求排除了不能生成所有可能的星形链组合的方法。第二个要求强烈建议快速自下而上的方法，而不是基于转换的自上而下的枚举。第三个要求排除了基于抽样的计划枚举（或随机化优化方法），因为这些不太可能为具有超过10个联接的查询生成所有顺序保留计划。事实上，我们期望最具竞争力的执行计划具有特定的形式：它们将尽可能长地使用保持顺序的合并连接，并且仅针对最后几个运算符切换到散列连接。

我们的解决方案是基于自下而上的DP框架[26]。它使用针对基本关系的扫描来生成其DP表，在我们的情况下是三重模式。播种是两步法。首先，优化器分析查询以检查在查询的其他部分中使用哪些变量绑定。如果一个变量未被使用，它可以通过使用聚合索引（参见第3.3节）被抛出。注意，该投影在概念上通过索引中的计数信息保留基数;我们在下面4.4小节中讨论这个问题。在第二步中，优化器决定使用哪些适用的索引。有两个因素影响索引选择。当三重模式中的文字形成索引键的前缀时，它们由范围扫描自动处理。否则，读取的元组太多，需要额外的选择。另一方面，不同的索引可以以适合稍后的后续合并连接的顺序产生三元组，这可能具有比读取太多元组更低的总成本。因此，优化器为所有索引生成计划，并使用计划修剪机制来决定是否早些时候可以丢弃其中的一些。

修剪主要基于估计的执行成本。也就是说，优化器为每个生成的计划调用成本模型，并修剪由廉价替代品支配的等价计划。这种修剪机制依赖于订单优化[35]来决定计划是否可以被另一个计划支配。由于优化器可以对所有三重排列使用索引，它可以按任意顺序生成元组，这使得合并连接非常有吸引力。因此，如果计划更昂贵，但产生可以在以后使用的有趣的顺序，则保留计划。注意，排序不仅通过索引扫描创建，而且还通过选择引起的功能依赖性创建，因此顺序优化组件是不重要的[35]。从种子开始，通过连接较小问题的最佳解决方案创建更大的计划。在此过程中，所有属性处理逻辑实现为对可用等价类的推理，而不是单个变量绑定。每个计划将为每个等价类产生至多一个绑定。这既简化了流水线断路器前面的隐式投影，并允许自适应传递连接条件的检测（即a = b ^ b = c⇒a = c）。

从种子开始，通过连接在查询图[26]中相邻的较小问题的最优解来创建更大的计划。 当查询包含由于FILTER谓词而产生的其他选择时，它们将尽快置于贪婪，因为它们通常价格不贵。 如果选择真的很昂贵，可以更好地将其集成到[9]中提出的DP运算符放置，但是我们没有进一步调查。 我们沿着这些线实现的DP方法非常快，并且能够为具有多达20个三元模式的连接查询计算精确的成本最优解。 我们测量了典型SPARQL场景的优化时间（以毫秒为单位），其中两个实体由星形子查询选择并通过连接模式链连接。 结果示于图5中。

Handling Disjunctive Queries

虽然连接查询更常用，但SPARQL还允许某些形式的析取。 UNION表达式返回由两个或多个模式组生成的绑定的并集。如果有任何结果，OPTIONAL表达式返回模式组的绑定，否则返回NULL值。在这种情况下，模式组是三重模式的集合，可能包含UNION和OPTIONAL表达式本身。

在优化期间，我们将UNION和OPTIONAL中的模式组视为嵌套子查询。也就是说，我们首先优化嵌套模式组（可能递归地），然后在外部查询的优化期间将它们视为具有特殊成本/基数的基本关系。对于UNION，我们添加模式组结果的并集，就像它是一个基本关系一样，对于OPTIONAL，我们使用外连接将结果添加为基本关系。

原则上，可以更积极地优化这些查询，但是最有趣的优化需要使用旁路计划[37]或其他非树结构的执行计划，这超出了本工作的范围。这些优化只会为复杂的查询付出代价;当分离元素很简单时，我们的嵌套优化方案产生最优解。

Preserving Result Cardinality

标准SPARQL语义要求产生正确数量的变量绑定，即使它们中有许多是重复的。 然而，从处理的角度来看，应该避免生产和保留重复的额外工作。

我们通过在查询处理期间跟踪每个元组的多重性来解决这个问题。 对非聚集索引的扫描总是产生1的多重性，而聚合索引将复制的数量报告为多重性。 连接运算符乘以多项式以获得每个输出元组的重复数。 注意，如果我们可以静态地推导出它在子计划中必须是1，我们可以可选地关闭多重跟踪。 当结果呈现给应用程序/用户时，输出运算符根据指定的查询语义（distinct，reduced或standard）解释多重性。

Implementation Issues

我们的运行时系统包括典型的代数运算符（merge-join，hash-join，filter，aggregation等）。与其他系统的一个显着区别是，我们的运行时系统是非常RISC风格的：大多数运算符只处理整数编码的id，消费和产生id元组流，比较id等。除了简化代码，这种减少的复杂性允许整洁的实现技巧。

例如，考虑使用B +树迭代器访问物理数据的索引扫描算子，将三元模式与数据进行比较。三元组中的每个条目都是必须生成或绑定到文字的id属性，如果它在前缀中会影响开始/停止条件，或者如果未绑定的条目先到达，则意味着选择。而不是在运行时检查这些不同的条件，我们可以在查询编译时处理它们。每个条目都是id属性或文字。在三元组中有三个条目，这意味着有八种可能的组合。使用具有索引扫描算子的八个不同实现的单个方法接口，我们可以大大减少系统代码中的条件分支的数量。除了速度更快，每个专业操作员都更简单，因为它现在只实现其设置所需的逻辑。注意，我们只需要专门化步骤逻辑，每个专业化的代码少于10行。

这种RISC风格的简化型系统和简单，快速的操作系统的组合导致非常好的CPU性能。在我们的第6部分的评估中，我们包括温热缓存时间来演示这些效果。我们意识到这些类型的代码调优问题通常不被重视，但对于现代硬件的高性能至关重要。

SELECTIVITY ESTIMATES

查询优化器在寻找最低成本执行计划时依赖其成本模型。 特别地，估计的基数（以及因此选择性）对计划生成具有巨大的影响。 虽然这是数据库系统中的标准问题，但RDF数据的无模式性质使统计数据生成复杂化。 我们提出两种统计。 第一个，专门的直方图，是通用的，可以处理任何种类的三重模式和联接。 它的缺点是它假定谓词之间的独立性，这通常在紧密耦合的三元模式中不成立。 因此，第二个统计量计算数据中的频繁连接路径，并为大型连接提供这些路径的更准确的预测。 在查询优化期间，我们使用连接路径基数（如果可用），否则假设独立性并使用直方图。

Selectivity Histograms

虽然三元组在概念上形成具有三个列的单个表，但是在各个列上的直方图不是非常有用，因为大多数查询模式接触三元组的至少两个属性。相反，我们利用我们的聚合索引，这完全适合于计算三种模式选择性：对于每个文字或字面对，我们可以得到匹配三元组的确切数量与一个索引查找。不幸的是，这不足以估计连接选择性。此外，我们希望将成本模型的所有辅助结构保留在主存储器中。因此，我们进一步聚合索引，使得每个索引适合单个数据库页面并包括有关连接选择性的信息。

就像聚合索引一样，我们构建六个不同的统计信息，一个用于三元组中条目的每个顺序。从聚合索引开始，我们将具有长度为2的相同前缀的所有三元组放置在一个桶中，然后合并最小的两个相邻桶，直到总直方图足够小。这近似于等深度直方图，但避免将桶边界置于具有相同前缀的三元组之间（预期相似）。

对于每个桶，然后计算图6所示的统计量。前三个值 - 三元组的数量，不同的2-前缀的数量和不同的1-前缀的数量 - 被用于估计单个三元模式的基数。注意，这仅仅给出扫描基数，即，所扫描的三元组的数量，其确定索引扫描的成本。当字面量不是索引前缀的一部分并且稍后通过选择测试时，真正的结果基数（其影响后续运算符）实际上可能会降低。在这种情况下，我们通过重新排序文字来导出结果基数（并获得准确的预测），使所有文字都在前缀中。

如果桶中的三元组根据指定的连接条件连接到数据库中的所有其他三元组，则下一个值是连接伙伴的数量（即结果基数）。由于有九种方法来组合来自两个三元组的属性，我们预先计算了九个基数。例如，条目o = s是有效的

|{b|b ∈ current bucket} 1 b.object=t.subject {t|t ∈ all triples}|

这些值在连接与桶完全匹配的模式时会提供完美的连接大小预测。通常情况不是这样，因此我们假定查询条件之间是独立的，并且乘以所涉及的谓词的选择性。 （这种独立性假设是用于可追踪性的最先进的查询优化器的标准）。

Frequent Paths

上面讨论的直方图具有相当的准确性，并且适用于所有种类的谓词。他们的主要弱点是他们假设谓词之间的独立性。两种相关谓词通常出现在SPARQL查询中。首先，三种模式的“星”，其中具有不同谓词的多个三元模式共享相同的主题。这些用于选择特定主题（即，基于相同实体的不同属性的实体）。第二，三元模式的“链”，其中第一模式的对象是下一模式的主题，同样具有给定的谓词。这些链对应于长连接路径（跨不同实体）。由于这两种情况是常见的，我们另外构建专用统计信息以具有用于这样的查询的更准确的估计量。

为此，我们预先计算数据图中的频繁路径，并为它们保留精确的连接统计信息。这里的频率指的是具有相同标签序列的路径。注意，我们对于链和星使用术语路径，在两种情况下结构是相似的。我们通过谓词p 1，…，p的序列来表征路径P. 。 。 ，在其遍历中看到。使用SPARQL语法，我们定义一个（链）路径P p 1 ,…,p n as
P p 1 ,…,p n := select r 1 r n+1 where { (r 1 p 1 r 2 ).(r 2 p 2 r 3 ). . . . (r n p n r n+1 )}

星形路径定义类似，p 1 , . . . , p n在这种情况下是不排序的。我们计算最频繁的路径，即具有最大基数的路径，并实现它们的结果基数和路径描述p 1，…。 。 。 ，p n。使用此信息，我们可以准确地预测查询中出现的频繁路径的连接基数。同样，我们希望将这些统计信息保存在主内存中，从而计算最常见的路径，以便它们仍然适合单个数据库页面。在我们的实验中，我们可以在一个16KB页面上存储大约1000个路径。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
FrequentPath(k)
// Computes the k most frequent paths
C 1 = {P p |p is a predicate in the database}
sort C 1 , keep the k most frequent
C = C 1 , i = 1
do
C i+1 = ∅
for each p 0 ∈ C i , p predicate in the database
if top k of C ∪ C i+1 ∪ {P p 0 p } includes all subpaths of p 0 p
C i+1 = C i+1 ∪ {P p 0 p }
if top k of C ∪ C i+1 ∪ {P pp 0 } includes all subpaths of pp 0
C i+1 = C i+1 ∪ {P pp 0 }
C = C ∪ C i+1 , sort C, keep the k most frequent
C i+1 = C i+1 ∩ C, i = i + 1
while C i 6 = ∅
return C

找到最常见的路径需要小心。虽然看起来这是一个标准的图表挖掘问题，但是该研究线中的普遍方法[16,44,49]，例如基于众所周知的Apriori频繁项目集挖掘算法，不是直接适用的。

与Apriori设置不同，我们的RDFpath意义上的常见路径不一定包含频繁的子路径。考虑具有两个星形链路群集的图，其中所有端节点分别通过谓词（边缘标记）p 1和p 2连接到它们各自的星形中心。现在考虑在两个星形中心之间具有谓词p 3的单个边。在这种情况下，路径P p 3将不频繁，而路径P p 1，p 3，p 2将是频繁的。因此，我们不能简单地使用Apriori算法。

我们的RDF设置中的另一个问题是周期，这可能导致看似无限长，无限频繁的路径。我们通过两种手段解决这个问题。首先，我们要求如果要保持频繁路径P，其所有子路径也必须保持。这对于查询优化目的是必需的，因为我们可能必须将长连接路径分解成较小的连接，并且它简化了频繁路径计算。第二，我们不是通过它们的结果基数而是通过它们的不同节点的数量对频繁路径进行排序。在树中，这两个是相同的，但是在循环的存在下，我们不对节点计数两次。

路径挖掘算法的伪代码如图7所示。它从长度为1的频繁路径开始，通过附加或前置谓词来放大它们。当新路径本身频繁并且其所有子路径仍然保持时，我们添加它。当没有新的路径可以添加时，我们停止。请注意，虽然伪代码显示了一个嵌套循环以方便表示，但我们实际上在实现中使用了一个join和一个group-by操作符。对于我们在实验中考虑的数据集，1000个最常见的路径可以在几分钟内确定。

Estimates for Composite Queries

为了估计整个复合查询的整体选择性，我们将直方图与频繁路径统计相结合。具有具有对象字面量的三元模式的中间节点的长连接链被分解为最大长度的子链，使得只有它们的末端节点具有带有文字的三元模式。例如，像

1
2
?x 1 a 1 v 1 . ?x 1 p 1 ?x 2 . ?x 2 p 2 ?x 3 . ?x 3 p 3 ?x 4 .
?x 4 a 4 v 4 . ?x 4 p 4 ?x 5 . ?x 5 p 5 ?x 6 . ?x 6 a 6 v 6

具有属性谓词a 1，a 4，a 6，v 1，v 4，v 6和关系谓词p 1至p 5的将被分解为p 1 -p 2 -p 3和p 4 -p 5和每个主题选择a 1 -v 1，a 4 -v 4和a 6 -v 6。我们使用频繁路径统计来估计两个连接子链的选择性以及用于选择的直方图。然后，在没有任何其他统计量的情况下，我们假设不同的估计量在概率上是独立的，导致具有每个子链和每个选择估计的乘积公式作为因子。如果不是像?x 6 a 6 v 6这样的简单属性值选择，我们具有星形图案诸如?x 6 a 6 u 6 . ?x 6 b 6 v 6 . ?x 6 c 6 w 6具有属性a 6 ,b 6 , c 6和对应的对象文字u 6，v 6，w 6，我们将首先使用星的频繁路径统计调用星形模式的估计器，然后将它们与产品形式中的其他估计值组合。

EVALUATION

General Setup

为了评估RDF-3X的性能，我们使用了具有不同特性的三个大数据集，并将查询运行时与其他方法（下面讨论）进行比较。所有实验在具有2Ghz Core 2 Duo处理器，2GBytes内存并运行64位Linux 2.6.24内核的Dell D620 PC上进行。对于冷缓存实验，我们使用/ proc / sys / vm / drop caches内核接口删除所有文件系统缓存，然后重新启动各个被测试的系统。我们重复了所有查询五次（包括删除缓存和系统重新启动），并获得最佳结果，以避免操作系统活动造成的工件。对于温暖的缓存，我们运行查询五次，而不删除缓存，再次采取最佳的运行时。
我们的主要比较是在[1]中提出的基于列存储的方法，已经被证明是高度优于所有其他基于DBMS的方法在该文件。我们实现了[1]中描述的方法，但使用MonetDB 5.2.0 [27]作为后端，而不是CStore，因为C-Store不再维护，不在我们的硬件/操作系统平台上运行。 C-Store网页http://db.csail.mit.edu/projects/cstore/建议使用MonetDB，而MonetDB工作正常。注意，我们的设置使用的硬件比[1]特别是硬盘是比在[1]中使用的非常快的RAID慢6倍，传输ca.顺序读取中为32 MB / s。考虑到这个因素6，MonetDB的性能数据与[1]中的C-Store数字相当。对于一个查询（Q6），MonetDB明显快于6（14s对10s），而另一个（Q7）明显更慢（61s对1.4s），但是MonetDB的整体性能比预期的要慢，因为硬盘较慢。

作为RDF-3X的第二个对手，我们使用PostgreSQL 8.3作为字符串字典和（主语，谓词，对象），（谓词，主语，对象）和（谓词，对象，主语）索引的三重存储。这模拟了Sesamestyle [8]存储系统。我们还尝试了当前版本的具有内置RDF支持的领先商业数据库系统，但是在其他系统的运行时间附近无法获得可接受的性能。当使用自己的RDF查询语言，尽管尝试几个自动调整选项，它执行速度比PostgreSQL三元组存储，即使对于简单的查询，并且无法在合理的时间执行更复杂的查询。因此，我们从演示中省略了它。
除了这些基于DBMS的对手之外，我们尝试了来自语义网络社区的几个可用作开源代码的系统。不幸的是，没有一个缩放到我们使用的数据集大小。我们首先尝试了惠普实验室语义网计划中出现的流行的Jena2系统[46]。我们使用Jena版本2.5.5与SDB 1.0包装程序和Apache Derby 10.3.2.1，但无法在24小时内导入我们的三个数据集。从文件增长来看，系统持续变慢，似乎没有在合理的时间内终止。我们还尝试了Yars2 [19,48]，但是再次无法在24小时内导入我们的任何数据集。最后，我们尝试了Sesame 2.0 [8,28]，它应该是最快的语义Web系统之一。 Sesame 2.0能够在13小时内导入Barton数据集，但后来需要ca.对于前两个查询中的每个查询为15分钟，并且由于更复杂的查询的过多的内存使用而崩溃。

请注意，MonetDB和RDF-3X都可以在不到半小时内导入数据集，并且可以按秒的顺序运行查询。 其他语义Web方法通常假定RDF数据适合主存储器，这不是这里的情况。 因此，下面的所有实验都只考虑RDF-3X，基于列存储的MonetDB顶层方法和基于PostgreSQL的三元组存储。 独立于数据库系统，下面讨论的每个数据集首先被带入因子分解形式：一个文件具有表示为整数三元组的RDF三元组和一个从整数到字面量的字典文件映射。 所有三个系统使用相同的文件作为输入，将它们加载到事实表和字典中。 第二阶段的加载时间和数据库大小如图8所示.MonetDB大小是加载后的初始大小。 运行基准后，大小为2.0 / 2.4 / 6.9 GB。 显然MonetDB根据需要构建一些索引结构。

Barton Dataset

对于第一个实验，我们使用Barton库数据集和在[1]中提出的查询作为基准。我们按照[1]中所述处理数据，使用Redland解析器将其转换为三元形式，然后将三元组导入我们的RDF-3X系统。在[1]中，作者修剪了数据，由于C-Store的限制（他们删除所有三元组包含超过127字节的字符串和一些三元组与大量的加入合作伙伴）。我们保留完整的数据，并将其直接导入所有三个系统。总体上，数据包括51,598,328个不同的三元组和19,344,638个不同的字符串。原始数据为RDF（XML）格式的4.1 GB，三重形式的7.7 GB，以及包含所有索引和字符串字典的RDF-3X存储库中的2.8 GB。
我们使用[1]的查询作为我们的实验，但是由于它们在SQL中给出，我们不得不在SPARQL for RDF-3X中重新组织它们。附录A显示所有查询。我们的测量结果如图9所示。我们还包括查询集的几何平均值，它通常用作基准（例如，TPC）中的工作负载平均值度量，并且比极端异常值比算术平均值更具弹性。
第一个观察是，RDF-3X对所有查询执行得比MonetDB好多了，MonetDB本身的性能比PostgreSQL好得多（如[1]中所述）。我们首先讨论RDF-3X与MonetDB的结果。在比较冷缓存时间和热缓存时间时，很明显，磁盘I / O对总体运行时间有很大的影响。 RDF-3X由于其高度压缩的索引结构而简单地读取较少的数据，因此在冷高速缓存的情况下优于MonetDB的典型因子为2至5，有时超过10。在暖缓存的情况下，差异通常较小但仍然很大（因子2，有时高得多）。一个有趣的数据点是查询Q4，其在构造的连接对方面相对昂贵，并且其中RDF-3X甚至在CPU主导的热缓存情况下表现非常好。此外，我们观察到除了I / O和CPU使用率之外的第三个关键方面是内存消耗。查询Q5有一个非常大的中间结果。 MonetDB显然在主存储器中实现这些中间结果的部分。因此，只有少数数据库页面可以进行缓冲，这极大地损害了热缓存行为。

PostgreSQL对此数据集有问题，因为此基准的查询的性质。 几乎所有查询都是聚合查询（通常通过谓词聚合），结果基数很大，这需要昂贵的字典查找。 对于其他更自然的RDF查询，PostgreSQL的性能更好，我们将在接下来的两个小节中看到。
为了了解Yars2风格的系统如何扩展，我们实验禁用所有聚合索引。 这使几何平均值增加到9.52秒（冷）和1.04秒（暖），这显着慢于RDF-3X。 这仍然比其他系统快得多，特别是由于我们的运行时系统和查询优化器。

Yago Dataset

Barton数据集是相对同质的，因为它描述了库数据。作为第二个数据集，我们因此使用Yago [40]，它包括从维基百科提取的事实（利用维基百科的信息框和类别系统），并与WordNet词库集成。 Yago数据集包含40,114,899个不同的三元组和33,951,636个不同的字符串，消耗3.1 GB作为（因式分解）三元组转储。 RDF-3X需要2.7 GB的所有索引和字符串字典。作为查询，我们考虑了三种不同的应用场景 - 面向实体，面向关系，以及具有未知谓词的查询 - 并导出八个基准查询，如附录A所示。这些查询比Barton查询更“自然”，因为它们是标准的SPARQL没有任何聚合和明确给定的谓词。另一方面，查询要大得多（需要更多的多对多连接），因此更难以优化和执行。
结果如图10所示。再次，RDF-3X显然胜过冷和暖缓存的其他两个系统，典型的因子为5到10.这里的PostgreSQL执行得比MonetDB好多了。这很可能是由于MonetDB中的连接顺序差。 warmcache运行时间几乎与冷缓存时间一样高，这表明MonetDB创建了大量的中间结果。
一般来说，这个数据集对于查询优化器来说更具挑战性，因为查询更复杂，选择性估计非常重要。在测试我们的系统时，我们注意到选择性误估可以很容易导致这个数据集减速10-100倍。 RDF-3X在运行时执行和优化器选择执行计划方面表现出极好的性能。

LibraryThing Dataset

作为第三个数据集，我们使用了LibraryThing书籍社交网络www.librarything.com的部分爬网。它包含9989个用户，5,973,703个不同的图书（由这些用户个人拥有）以及用户分配给这些图书的标记。总的来说，数据集由36,203,751个三元组和9,352,954个不同的字符串组成，其原始格式为1.8 GB，RDF-3X为1.6 GB。这个数据集的一个特殊性是具有异构链接结构。在我们的RDF表示中，每个标记都映射到一个谓词，将用户链接到她标记的图书。由于不同标签的数量非常大，数据集包含338,824个不同的谓词，而其他两个数据集分别仅包含285和93个不同的谓词。虽然其他映射到RDF可能是可能的，但我们使用这种非示意性方法作为所有竞争系统的压力测试。
此数据使得RDF-3X的压缩更加困难，并且对MonetDB造成严重的问题。 MonetDB无法处理338,824个表，在文件系统中创建数百万个文件，并一直交换。因此，我们为此数据集使用MonetDB的混合存储方案。我们分割了[1]中描述的1000个最常用的谓词，并将剩余的三元组（大约12％）放在一个大的三元组表中。我们再次构造了三种查询：面向书，面向用户，浏览书和用户链（参见附录A）。与Yago数据集相反，几百万三元组中出现的谓词很少，这降低了连接排序决策的影响。另一方面，数据本身是非常不均匀的，使得选择性更难以预测。

结果如图11所示。在某些情况下，RDF-3X表现很好，优于对手的典型因素为至少5和大于30。 MonetDB和PostgreSQL之间没有明确的赢家。总体MonetDB似乎表现更好，但它崩溃了两次。它拒绝执行查询B3（“太多变量”），可能是因为它包括三个模式与可变谓词（因此至少3000次扫描）。在查询C2中，由于缺少磁盘空间，它在15分钟后崩溃，因为它实现了一个20 GB的中间结果（这是整个数据库大小的10倍）。查询A3由于其高运行时间而突出。
它与相对非选择性的谓词（书籍作者等）执行许多连接，这是昂贵的。其他“困难”查询（B3，C1，C2）本身并不那么难，他们只是需要正确的执行计划选择。例如，B3会找到所有标记为英语，法语和德语的图书的用户。 PostgreSQL通过收集用户拥有的所有图书对来启动此查询，这是非常昂贵的。另一方面，RDF-3X的优化器选择一个计划，收集每个标签的用户与这些书，然后加入结果，这是更有效率。

CONCLUSION

本文提出了RDF-3X引擎，一个RISCstyle架构，用于对大型RDF三元组存储库执行SPARQL查询。正如我们的实验表明，RDF-3X的性能优于以前最好的系统。特别地，它解决了模式数据的挑战，并且与其对手不同，非常好地处理具有大量多样性的属性名称的数据。导致这些性能提高的RDF-3X的显着特征是：1）详尽但非常节省空间的三重索引，消除了对物理设计调整的需要，2）以非常快的合并连接为中心的简化的执行引擎，3）智能查询优化器，它选择成本最优的连接排序，并且甚至对于长连接路径（涉及10到20个连接）也可以有效地执行此操作; 4）基于提供给优化器成本模型的频繁路径的统计信息的选择性估计器。
我们未来的工作包括进一步改进查询优化器（例如，基于魔术集）以及支持超出当前SPARQL标准的RDF搜索功能。沿着后一行，一个方向是允许更强大的通配符模式的整个路径，在XPath后代轴的精神，但图形而不是树。已经提出了扩展SPARQL的建议[3]，但还没有实现。第二个方向是基于应用特定的评分模型提供查询结果的排名。这需要top-k查询处理，并对算法和查询优化提出具有挑战性的问题。最后，完整的SPARQL支持需要一些额外的信息，特别是打字信息。我们认为这可以包括在字典中，但确定最佳编码相对于运行时性能和压缩率需要更多的工作。

总结

现有的储存方式

  • RDF Triples
  • by predicates

RDF3X

  • B+ tree
  • string/literal -> id ,Dictionary
  • RISC style reduced complexity
  • 6-index && compressed index (chunk to leaf level compressed ?) && store changes between index because of the neighboring index are similar
  • aggregated index
0%