Sorted List (fast)
-
@SoIntMan sagte in Sorted List (fast):
@hustbaer sagte in Sorted List (fast):
s ist fast immer effizienter nur 1x zu sortieren wenn man nicht mehr braucht.
jepp, aber meine linked-list variante ist tatsächluch um factor 2x schneller;)
Klingt unwahrscheinlich. Zeig mal den Code für die beiden Varianten.
-
@SoIntMan sagte in Sorted List (fast):
jepp, aber meine linked-list variante ist tatsächluch um factor 2x schneller;)
Ich wäre vorsichtig mit so einfachen Performance Tests. Gerade bei so kleinen Beispielen ist der Compiler teilweise so schlau, dass er das schon zur Compilezeit ausrechnet und damit die Laufzeit wegoptimiert.
Es gibt Perfomance Test Frameworks, die dafür sorgen, dass das nicht passiert, zum Beispiel das hier: https://github.com/google/benchmark
-
ich würde einfach ein array int myarray[ARRAYLEN] nehmen und dieses dann mit insertionsort füllen, das ist dann O(n), liste wäre mir zu aufwendig zu programmieren, obwohl das auch ginge und O(n) wäre.
quicksort ist bei vorsortierten daten sehr ineffektiv!
-
@Peter-Viehweger sagte in Sorted List (fast):
quicksort ist bei vorsortierten daten sehr ineffektiv!
Na ja, das "sehr" stört mich... O(n) vs O(n log n) im best case ist ineffizienter, ja... aber sehr? Afaik wird dann (bei Millionen oder Milliarden Elementen) anderes zuerst zum bottle neck.
-
Sind die Daten denn überhaupt vorsortiert?
-
wenn sie von vornherein mit insertionsort eingepflegt werden, oder einmalig mit quicksort o.ä. sortiert wurden, schon.
-
Darum geht es nicht. n-mal Insertionsort aufzurufen, ist teurer als Quicksort.
Es geht darum, ob die Basisdatenmenge sortiert vorliegt oder nicht.
Ohne das zu wissen, kann keine adäquate Antwort gegeben werden.
-
@nameName ja gut, ich habe mich jetzt einfach an dem oben geschriebenen orientiert: da steht was von "beim einfügen eines neuen elements".
also wenn die werte erst nach und nach kommen, dann würde ich insertionsort nehmen; quicksort, wenn sie von beginn an alle da sind; und erst quicksort und dann insertionsort, wenn beides auftritt, also es sind werte vorhanden und später kommen neue dazu.
-
@SoIntMan sagte in Sorted List (fast):
jepp, aber meine linked-list variante ist tatsächluch um factor 2x schneller;)
Schau dir mal den folgenden Benchmark an:
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
PS: Ist zwar für C++, aber die Ergebnisse lassen sich für C übertragen.
-
@Schlangenmensch sagte in Sorted List (fast):
@SoIntMan sagte in Sorted List (fast):
jepp, aber meine linked-list variante ist tatsächluch um factor 2x schneller;)
Ich wäre vorsichtig mit so einfachen Performance Tests. Gerade bei so kleinen Beispielen ist der Compiler teilweise so schlau, dass er das schon zur Compilezeit ausrechnet und damit die Laufzeit wegoptimiert.
Es gibt Perfomance Test Frameworks, die dafür sorgen, dass das nicht passiert, zum Beispiel das hier: https://github.com/google/benchmarkdas is cool, das schau ich mir an.. wenn das benchmark das pendant zu google test ist.. perfekt
@Quiche-Lorraine sagte in Sorted List (fast):
@SoIntMan sagte in Sorted List (fast):
jepp, aber meine linked-list variante ist tatsächluch um factor 2x schneller;)
Schau dir mal den folgenden Benchmark an:
https://baptiste-wicht.com/posts/2012/12/cpp-benchmark-vector-list-deque.html
PS: Ist zwar für C++, aber die Ergebnisse lassen sich für C übertragen.
mach ich;)
