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
|
// benchmark with (insert insert delMin)^N (insert delMin delMin)^N
// just in time RNG
// version 3: use easier to handle binary heaps
// hold.C: generage inputs in the hold model
#include <limits.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#define DEBUGLEVEL 0
#include "util.h"
//#define KNH
#define H2
//#define H4
//#define HSLOW
#ifdef KNH
# include "knheap.C"
# define HTYPE KNHeap<int, int>
# define HINIT heap(INT_MAX, -INT_MAX)
#else
# ifdef H4
# include "heap4.h"
# define HTYPE Heap4<int, int>
# define HINIT heap(INT_MAX, -INT_MAX, n)
# else
# ifdef H2
# include "heap2.h"
# define HTYPE Heap2<int, int>
# define HINIT heap(INT_MAX, -INT_MAX, n)
# else
# ifdef HSLOW
# include "heap-CLR.h"
# define HTYPE Heap2<int, int>
# define HINIT heap(INT_MAX, -INT_MAX, n)
# endif
# endif
# endif
#endif
#define rand32() (ran32State = 1664525 * ran32State + 1013904223)
#define getRandom() ((rand32()), (int)(((unsigned int)ran32State) >> 4))
inline void onePass(HTYPE& heap, int n)
{ int j, newElem, k, v, old;
long long insertSum=0, deleteSum=0;
static int ran32State = 42 << 20;
Debug3(cout << heap.getSize());
Assert(heap.getSize() == 0);
// build heap
for (j = 0; j < n; j++) {
newElem = getRandom();
heap.insert(newElem, j);
Debug0(insertSum += newElem);
Debug3(cout << newElem << "in ");
}
// hold phase
old = 0;
for (j = 0; j < 2*n; j++) {
heap.deleteMin(&k, &v);
Debug0(deleteSum += k);
Assert0(k >= old);
Debug0(old = k);
Debug3(cout << k << "out ");
newElem = k + getRandom();
heap.insert(newElem, j);
Debug0(insertSum += newElem);
Debug3(cout << newElem << "in ");
}
Assert0(heap.getSize() == n);
// finish up
for (j = 0; j < n; j++) {
heap.deleteMin(&k, &v);
Debug0(deleteSum += k);
Debug3(cout << k << "out ");
}
Assert0(deleteSum == insertSum);
Assert(heap.getSize() == 0);
}
int main(int argc, char **argv)
{
Assert(argc > 1);
int n = atoi(argv[1]);
int i;
int ran32State = 42 << 20;
int repeat = 1;
double startTime, endTime;
if (argc > 2) repeat = atoi(argv[2]);
//#ifdef H2
//HTYPE *temp = new HTYPE(INT_MAX, -INT_MAX);
//HTYPE& heap =*temp;
//#else
HTYPE HINIT;
//#endif
// warmup
onePass(heap, n);
startTime = cpuTime();
for (i = 0; i < repeat; i++) {
onePass(heap, n);
}
endTime = cpuTime();
// output time per insert-delete-pair and this time over log n
double timePerPair = (endTime - startTime) / n / repeat / 3.0;
double timePerCompare = timePerPair / (log((double)n) / log(2.0));
cout << n << " " << timePerPair * 1e9 << " " << timePerCompare * 1e9 << endl;
}
|
