-
Notifications
You must be signed in to change notification settings - Fork 1
/
Prac4_SkipList.cpp
83 lines (65 loc) · 8.58 KB
/
Prac4_SkipList.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
// Skip list structure are used to retrieve the data faster.
// Implement the structure up to third level. Show the effect
// of insert and delete operation
#include "SkipList.h"
#include "LinkedList.h"
#include <iostream>
#include <ctime>
int main(){
using namespace std;
SkipList data("Knuth", 4);
SkipList data2("NG", 1);
LinkedList line;
data.AddData("data.csv", 1);
data2.AddData("data.csv", 1);
line.AddData("data.csv", 1);
// data.insertNode(241,3472);
// data.insertNode(238,3038);
// data.insertNode(849,4886);
// data.insertNode(231,3404);
// data.insertNode(492,4891);
// data.insertNode(893,1531);
// data.insertNode(433,3703);
// data.insertNode(239,4056);
// data.insertNode(406,2890);
// data.insertNode(455,4604);
// data.insertNode(541,4113);
// data.insertNode(285,2508);
// data.insertNode(529,2689);
// data.insertNode(718,4044);
// data.insertNode(220,2134);
// data.insertNode(643,3733);
// data.Display();
// data.deleteNode(220);
// data.deleteNode(718);
// data.deleteNode(406);
// data.Display();
cout << "Starting Searching" << endl;
const int keys = 967;
int searchKeys[keys] = {969148,120038,410057,5126,424841,71015,130238,717597,671037,863907,715341,640319,98832,401088,227077,196772,760691,377700,48771,833879,183245,697840,541479,506587,378111,873222,295611,502146,392925,67745,855704,66953,415647,388060,205079,53286,515164,921606,69240,648956,169842,157771,161822,332534,533106,111400,507075,306405,683823,493724,555659,128261,111810,873125,767417,402177,981726,722361,580251,807309,109494,850976,583975,861383,204261,138053,587970,555763,4855,325464,686823,476253,10783,560292,122572,943709,394542,788019,76740,740956,568647,704588,24135,936924,223318,358914,982974,205870,998175,618816,704037,790308,509056,74664,610868,168260,510665,398651,889412,646960,956813,680965,984312,10432,570143,418921,536618,701451,647860,791807,503847,867978,109487,746670,531939,567429,118257,585661,858071,519117,435103,314525,626269,227054,927090,261308,698093,432171,19182,2223,759131,62422,790017,112941,341694,138351,832810,671743,138452,381217,473234,676092,547786,306442,817945,735894,837167,264548,127773,851233,510388,922731,905717,232080,956573,512611,593380,323347,346288,674880,300197,825580,238731,757124,523127,985860,4178,370323,273227,92155,917882,112481,885012,506188,95646,671177,190458,219041,973777,512750,672500,130637,836925,276544,578983,184773,702513,20944,249550,734150,697245,610050,294596,791832,500302,880919,608744,28177,805127,703891,728765,395093,818190,619973,477190,695790,519486,866969,960820,594813,879747,126119,820192,220506,654288,643491,741364,981090,257980,632093,512030,171906,613455,869109,125008,414929,150586,264762,181194,890599,297798,685273,471561,389926,111744,328802,987762,523099,495704,724169,766792,81417,785844,496204,25131,962268,818566,297524,162084,995661,952669,977246,750625,712224,709414,347508,221669,413279,170581,510081,913799,855283,452668,730046,32784,953851,675357,748137,584262,807337,44009,367456,578824,608563,469193,145527,968026,600109,943466,342090,962134,163131,205555,784705,328008,96190,377468,436579,425113,670156,244258,637471,537496,659319,503924,450914,839554,998846,395439,150101,664537,924599,201956,606841,192793,740625,517957,99923,93955,909515,516947,621363,272917,121422,467967,993842,237367,121968,456309,574573,40687,886818,960094,324423,680380,753078,362033,889521,30324,794456,789611,478503,45801,726188,431265,608485,522757,962371,992843,367172,212182,304992,323689,207994,237704,379104,699209,104988,520004,608461,476065,679747,169223,265307,694990,723330,89016,335877,432012,819980,947385,188696,938726,314902,521247,574419,208689,177792,602966,419084,869324,929081,916685,579775,808320,370994,79155,322577,813844,545604,684329,131293,567439,886258,654615,10005,386165,596303,69813,306626,438300,759989,961754,82656,976448,109300,49113,943703,514352,806122,223069,298904,403350,366757,750456,220144,969795,393965,598646,467510,442881,341497,5735,36564,150543,842604,364662,150267,265131,95051,271786,726609,684981,691204,609893,514538,423014,727934,838367,51034,879474,9129,678726,94254,487883,736106,448574,17090,971405,246829,173456,173520,680418,278326,583348,996386,284991,752242,586191,381100,42399,243639,741564,472510,38863,648089,551762,53367,134466,724859,110649,389993,475242,625400,48635,453119,55341,736360,868076,648305,53555,631406,232096,911244,754464,907424,178315,577423,764291,559638,818762,787480,885566,113242,338523,271356,426963,91784,767662,507724,932628,217098,925744,677007,464426,492646,309865,811568,804232,382017,885407,733534,746140,988808,605271,235958,284470,482258,880718,797240,28368,508595,370066,47102,137748,584655,533250,609377,452684,794979,446823,42770,888674,951903,969579,776915,706461,643886,873178,589047,74903,197915,237087,370251,587290,434052,414197,739737,437353,557230,301283,978983,438675,710817,633046,382205,283698,77631,871622,240477,869908,985954,802139,987443,697678,755436,586793,820649,557461,837265,777199,967665,909947,55474,623167,870958,351419,466645,328797,496486,737262,95052,842671,4548,740047,794245,227825,788336,884898,687171,688419,599386,686257,543669,109105,627673,363294,473037,587795,634246,381925,904471,815945,414486,608465,807652,257839,356069,562146,60029,160026,915919,344572,38721,804390,868925,252697,868376,197714,693444,610514,712024,981210,312335,827469,695426,382094,97747,652399,697917,588153,415444,84192,935305,795855,161427,910341,626726,198457,221588,652616,58251,601587,173726,657224,914454,500406,113863,150421,663880,518089,527520,981036,966072,971526,414023,335376,601119,81493,749855,605062,164391,634305,341819,163781,539451,863695,249018,941394,543059,122637,989738,140294,16081,843454,376375,67674,844824,74189,721303,638400,800602,748619,274351,484758,573226,884835,897332,749591,945430,229092,109377,122052,965823,113203,675983,783035,18991,236772,731635,949131,500610,503870,916893,270886,201889,840945,303122,111438,301466,816629,500974,98317,779635,306946,619437,161656,343953,907448,572464,306440,603831,37951,220093,106599,749016,740408,327170,305540,896961,866960,371087,196989,969066,760792,365595,465174,427591,939141,477373,724368,69839,465664,688831,332957,500779,523425,2731,763206,607370,371272,264367,948807,74425,756549,775375,832014,655059,388758,807625,695461,810881,909084,43481,829615,49752,159010,536860,7998,232494,268189,159689,583637,460455,825750,381569,848972,241809,219002,581312,326006,26227,298469,293659,772643,23175,413294,121677,364429,14599,241141,230491,287206,196358,103422,810960,699356,188961,163630,869694,923067,79758,674905,121992,553012,195358,590573,771645,806346,973419,697840,296949,495441,537871,741007,229746,699810,93194,110475,992872,414265,777251,781946,135632,644031,419902,658998,461258,417202,743653,307912,149359,952446,463771,897444,126391,378761,246678,473352,312464,109218,69345,854414,74023,257955,169439,520386,823480,880675,406007,684963,806248,372947,694834,33017,749623,851987,293765,9287,703218,981267,825032,545377,923764,111467,823026,391961,344151,497699,781460,515114,240292,343973,342387,277258,279473,560612,837717,138548,336735,374549,366406,29266,945135,10153,165574,245313,647659,575242,405742,542515,854358,783863,37616,43574,795763,433474,7302,561024,264058,430150,995600,711162,433467,269773,61213,105809,813432,968307,664603,720013,99636,804294,242955,488602,573730,251137,369629,212039,905349,750675,363365,753006,618902,936434,396145,498012,859253,232072,669194,881508,765161,474430,480116,889698,836276,54014,786436,75570,534815,743301,942321,676090,280284,27238,674478,542706,907595,329216,389677,568969,329943,251317,72120,737323,333956,113930,375697,209752,482331,626146,348822,460948,505035,250921,656390,718623,497472,236423,263934,575145,519072,248682,907323,850215,613448,32854};
clock_t result1 = 0;
for (int i = 0; i < keys; i++)
{
clock_t start_time1 = clock();
line.search(searchKeys[i]);
result1 += clock() - start_time1;
}
cout << "Average time for LinkedList: " << (float)result1/CLOCKS_PER_SEC << endl;
clock_t result2 = 0;
for (int i = 0; i < keys; i++)
{
clock_t start_time1 = clock();
data.Search(searchKeys[i]);
result2 += clock() - start_time1;
}
cout << "Average time for SkipList Knuth: " << (float)result2/CLOCKS_PER_SEC << endl;
clock_t result3 = 0;
for (int i = 0; i < keys; i++)
{
clock_t start_time1 = clock();
data2.Search(searchKeys[i]);
result3 += clock() - start_time1;
}
cout << "Average time for SkipList NG: " << (float)result3/CLOCKS_PER_SEC << endl;
return 0;
}