QTree/Main.cc at main · Swiftense/QTree · GitHub

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
#include "Main.hpp"

int main()
{
    #ifdef performance
        struct timeval start, end;
        long long elapsed;

        QTree* tree;
        std::map<long long, long long>* map;

        QTree* tree_clone;
        std::map<long long, long long>* map_clone;

        /* insert qtree */
        tree = qtr_create();

        printf("Running Performance tests on tree operations with 10 Million Nodes:\n");

        gettimeofday(&start, NULL);
        for(long long l = 0;l < 10000000; l++)
        {
            qtr_set(tree, l, (void*)l);
        }
        gettimeofday(&end, NULL);

        elapsed = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
        printf(" *QTree insert: %lld ms\n", elapsed/1000);

        /* insert Red Black Tree */
        map = new std::map<long long, long long>();

        gettimeofday(&start, NULL);
        for(long long l = 0;l < 10000000; l++)
        {
            map->insert(std::pair<long long, long long>(l,l));
        }
        gettimeofday(&end, NULL);

        elapsed = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
        printf(" *Red Black Tree insert: %lld ms\n", elapsed/1000);

        /* search qtree */
        gettimeofday(&start, NULL);
        for(long long l = 0;l < 10000000; l++)
        {
            qtr_get(tree, l);
        }
        gettimeofday(&end, NULL);

        elapsed = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
        printf(" *QTree search: %lld ms\n", elapsed/1000);

        /* search Red Black Tree */
        gettimeofday(&start, NULL);
        for(long long l = 0;l < 10000000; l++)
        {
            map->at(l);
        }
        gettimeofday(&end, NULL);

        elapsed = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
        printf(" *Red Black Tree search: %lld ms\n", elapsed/1000);

        /* clone qtree */
        gettimeofday(&start, NULL);
        tree_clone = qtr_clone(tree);
        gettimeofday(&end, NULL);

        elapsed = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
        printf(" *QTree clone: %lld ms\n", elapsed/1000);

        /* clone Red Black Tree */
        gettimeofday(&start, NULL);
        map_clone = new std::map<long long, long long>(*map);
        gettimeofday(&end, NULL);

        elapsed = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
        printf(" *Red Black Tree clone: %lld ms\n", elapsed/1000);

        /* delete qtree */
        gettimeofday(&start, NULL);
        for(long long l = 0;l < 10000000; l++)
        {
            qtr_delete(tree, l);
        }
        gettimeofday(&end, NULL);

        elapsed = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
        printf(" *QTree delete: %lld ms\n", elapsed/1000);

        /* remove qtree */
        gettimeofday(&start, NULL);
        for(long long l = 0;l < 10000000; l++)
        {
            qtr_remove(tree_clone, l);
        }
        gettimeofday(&end, NULL);

        elapsed = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
        printf(" *QTree remove: %lld ms\n", elapsed/1000);


        /* delete Red Black Tree */
        gettimeofday(&start, NULL);
        for(long long l = 0;l < 10000000; l++)
        {
            map->erase(l);
        }
        gettimeofday(&end, NULL);

        elapsed = (end.tv_sec - start.tv_sec) * 1000000 + (end.tv_usec - start.tv_usec);
        printf(" *Red Black Tree delete: %lld ms\n", elapsed/1000);
        printf("Done.\n");
        return 0;
    #elif defined(preview)
        QTree* tree = qtr_create();

        qtr_set(tree, 8, (void*)2);
        qtr_set(tree, 18, (void*)7);
        qtr_set(tree, 5, (void*)9);
        qtr_set(tree, 15, (void*)64);
        qtr_set(tree, 17, (void*)4);
        qtr_set(tree, 25, (void*)67);
        qtr_set(tree, 40, (void*)11);
        qtr_set(tree, 80, (void*)175);
        qtr_set(tree, 33, (void*)45);

        printf("Values:\n");
        printf(" -%lld\n", qtr_get(tree, 8));
        printf(" -%lld\n", qtr_get(tree, 18));
        printf(" -%lld\n", qtr_get(tree, 5));
        printf(" -%lld\n", qtr_get(tree, 15));
        printf(" -%lld\n", qtr_get(tree, 17));
        printf(" -%lld\n", qtr_get(tree, 25));
        printf(" -%lld\n", qtr_get(tree, 40));
        printf(" -%lld\n", qtr_get(tree, 80));
        printf(" -%lld\n", qtr_get(tree, 33));

        printf("Tree:\n");
        qtr_print(tree);

        /* remove would have the same effect, but wouldn't change the tree structure */
        qtr_delete(tree, 17);

        printf("Values after deleting node with key 17:\n");
        printf(" -%lld\n", qtr_get(tree, 8));
        printf(" -%lld\n", qtr_get(tree, 18));
        printf(" -%lld\n", qtr_get(tree, 5));
        printf(" -%lld\n", qtr_get(tree, 15));
        printf(" -%lld\n", qtr_get(tree, 17));
        printf(" -%lld\n", qtr_get(tree, 25));
        printf(" -%lld\n", qtr_get(tree, 40));
        printf(" -%lld\n", qtr_get(tree, 80));
        printf(" -%lld\n", qtr_get(tree, 33));
        printf("Tree after deleting node with key 17:\n");
        qtr_print(tree);
        return 0;
    #else
        printf("./qtree.sh preview - shows you the tree structure\n");
        printf("./qtree.sh performance - compares the Red Black Tree and the QTree Algorithm using tests\n");
        return 0;
    #endif
}