STL list arschlahm?

[pest]

Hi,

ich programmiere gerade ein kleines Projekt und habe erst das Rad neu erfunden ;)

ein Teil des Codes macht im Prinzip Folgendes

-generiere Hash-Key (int)
-durchsuche alle Elemente die den selben Hash-Key besitzen
-lösche ein Element mit einem anderen Hash-Key
-füge den ersten Hash-Key an

nun habe ich die Elemente die den selben Key besitzen in einer Linked-List angeordnet, und wollte mal sehen wie fix das geht, wenn ich stattdessen STL list verwende

das heißt Durchsuchen per Iterator, Einfügen mittels push_front und Löschen mittels remove. Zu meinem Erstaunen ist der Code zwar extrem kurz, aber die Laufzeit hat sich verdoppelt! Woran liegt das? Ich verwende den letzten offiziellen GCC.


Laufzeit manuelle Single-Linked List: 3.13s, 3.13s, 3.11s

Laufzeit STL list: 5.91s, 6.01s, 5.92s


Gruss

[Trap]

std::list ist eine double linked list.

[pest]

ich weiß
sollte aber beim löschen (meiste zeit im programm) eher vorteile bringen als meine variante, da ist die löschprozedur ein grauss

[pest]

ich konnte die zeit beträchtlich verbessern, wenn ich beim durchsuchen der liste

aus

while (iterator!=list.end())



ende = list.end()
while (iterator!=ende)


mache.

mein algorithmus erlaubt es, statt ein bestimmtes element zu löschen, das letzte zu löschen
also statt remove, ein pop_back, das ist aber langsamer :|

[Trap]

Es gibt verschiedene mögliche Ursachen für den Unterschied:
-zusätzlicher Pointer pro Node
-intrusive vs. non-intrusive container
-doppelter Aufwand beim Hinzufügen und Löschen

Du hast beide Versionen mit eingeschalteten Optimierungen und ohne Debug-Zeugs compiliert?

Edit: Zum Suchen würde sich std::find aus <algorithm> anbieten anstatt es selbst zu schreiben.

[pest]

-intrusive vs. non-intrusive container


?


-doppelter Aufwand beim Hinzufügen und Löschen


ein pop_back() kann doch bei einer doppelt-verketten liste in konstanter zeit durchgeführt werden, mein code durchläuft die ganze liste! kann doch nicht sein, das dies schneller ist.

der zeitaufwand durch den doppelten pointer erklärt nicht die stark verlängerte laufzeit, da das programm nämlich was ganz anderes macht und dies nur ein kleiner programm-teil ist.
(einfügen kann man praktisch vernachlässigen)

aber wenn du es nicht glaubst, mach ich aus der linked-list eine double-linked, das wird schneller als meine jetzige variante



Du hast beide Versionen mit eingeschalteten Optimierungen und ohne Debug-Zeugs compiliert?


jep -O3 Release, habe die verbesserung von oben vorgenommen und ein anderes beispiel getestet

mein code: 4:07 [m:s]
stl list: 7:40 [m:s]

:freak:


Edit: Zum Suchen würde sich std::find aus <algorithm> anbieten anstatt es selbst zu schreiben.

nee ich muss die ganze liste durchlaufen, weil ich mit den elementen was mache

[Trap]

http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/intrusive_vs_nontrusive.html - könnte ja sein, dass du eine intrusive Liste benutzt, wäre für deinen Fall relativ naheliegend

Was sagt denn der Profiler dazu wo die zusätzliche Zeit hingeht?

[pest]

http://www.boost.org/doc/libs/1_35_0/doc/html/intrusive/intrusive_vs_nontrusive.html - könnte ja sein, dass du eine intrusive Liste benutzt, wäre für deinen Fall relativ naheliegend

Was sagt denn der Profiler dazu wo die zusätzliche Zeit hingeht?

das ist gar nicht so wichtig, aber ich danke dir für die tipps, der algorithmus an sich ist schon nicht optimal, ich wollte gern wissen ob stl list in dem fall etwas bringt
aber mehr zeit (profiler) werde ich da nicht investieren weil ich den schnelleren algorithmus nur dazu linken muss.

ich war etwas voreilig, hatte einen parameter übersehen so das löschen praktisch nicht stattgefunden hat (ka warum stl list dann zeit verplempert), jetzt ist pop_back auch schneller

stl list (remove): 44s
stl list (pop_back): 2s
meine double-linked-list: 45s

;( :wink: