最小值管理

發表於 更新於 分類於 ， 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;
}