0
$\begingroup$

I have got assignment to implement set class with linked list, so I first made it with unordered list and time needed to insert million integers is bit less than hour. Then I thought I can get it to work faster by making list ordered (since in average it should take less time to check is element already in set) but it went running for 1.5h after I stopped it.

In both algorithm there are 2 functions: 1. searches through linked list and returns pointer to predecessor of given element (null if element is not found). In first algorithm before searching for element, element itself is inserted at end of list and after search it is removed (this way there is no need to check if current element is last in search loop). If element is not found second function adds it on beginning of list.

In second algorithm search function does same except it stops after it finds element larger than searched element and returns it address.Then it is inserted in right place.

Integers are randomly generated using built in rand() function.

Update: I measured average time it takes to find element in both ordered and unordered list and results looks strange to me.

Average times in unordered list (left is number of elements in list, right is average time spent in search loop in microseconds).

10000 :29.4015
20000 :58.7789
30000 :88.0507
40000 :117.39
50000 :146.82
60000 :176.307
70000 :206.139
80000 :236.085
90000 :265.948
100000 :296.426
110000 :326.888
120000 :357.238

In ordered list

10000 :30.2287
20000 :87.0195
30000 :154.494
40000 :221.932
50000 :292.55
60000 :364.127
70000 :442.623
80000 :527.407
90000 :624.626
100000 :739.803
110000 :869.816
120000 :1008.33

Measured pieces of code:

Search in unordered list

while(k != current->k){
    old = current;
    current = current->next;
}

Search in ordered list

while(current->k < k){
    old = current;
    current = current->next;
}

In both cases there is guard at and of list, in first case equal to k, and in second larger than k.

$\endgroup$
  • $\begingroup$ Have you tried estimating the asymptotic running time in both methods? $\endgroup$ – Yuval Filmus Dec 25 '17 at 21:48
  • $\begingroup$ From your description it's hard to understand what you did. Can you perhaps clearly explain what you were trying to solve, and which two algorithms you were using? $\endgroup$ – Yuval Filmus Dec 25 '17 at 21:49
  • $\begingroup$ @YuvalFilmus In both algorithm there are 2 functions:1. searches through linked list and returns pointer to predecessor of given element(null if element is not found).In first algorithm before searching for element element itself inserted to end of list and after search it is removed(this way there is no need to check if current element is last in search loop).If element is not found second function adds it on beginning of list.In second algorithm search function does same except it stops after it finds element larger than searched element and returns it address.Then it is added in right place $\endgroup$ – joks Dec 25 '17 at 22:03
  • $\begingroup$ Please add this information to your post. $\endgroup$ – Yuval Filmus Dec 25 '17 at 22:20
  • $\begingroup$ Sorry but fixing your code is off-topic here and, in any case, it's impossible to know what you've done because you don't say with any precision. But I have to say, if your program is taking an hour to insert a million items to a list, that's really shockingly inefficient. I can't imagine it taking more than a few seconds. $\endgroup$ – David Richerby Dec 25 '17 at 23:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.