Sorted List (fast)
-
@Tyrdal sagte in Sorted List (fast):
Sorry für Offtopic: Aber was für eine Länge haben den Punkte?
16Byte x,y jeweils Int64
@hustbaer sagte in Sorted List (fast):
@SoIntMan Vielleicht verstehe ich das ganze nicht richtig - aber was du schreibst klingt für mich nach:
- Speicher für das Array besorgen (
malloc, am Stack, ...) - Elemente einfügen (ohne sortieren)
qsortaufrufen- Drüberiterieren
Also ich sehe keine Notwendigkeit das Array während des Einfügens sortiert zu halten.
Da hast du natürlich recht, ich "dachte" es sei effektiver das on-fly zu machen.. und ich brauch das auch erst am ende.. richtig.
aber "qsort" wusste gar nich dass sowas die c standart anbietet, was steckt da dahinter? sw oder hw implemtiert?
- Speicher für das Array besorgen (
-
@SoIntMan sagte in Sorted List (fast):
@Tyrdal sagte in Sorted List (fast):
Sorry für Offtopic: Aber was für eine Länge haben den Punkte?
16Byte x,y jeweils Int64
Und wo hat der Punkt jetzt ne Länge? Ist das der Abstand von (0,0)?
-
@SoIntMan sagte in Sorted List (fast):
aber "qsort" wusste gar nich dass sowas die c standart anbietet, was steckt da dahinter? sw oder hw implemtiert?
Das ist eine Funktion aus der C library, also in Software.
-
@SoIntMan sagte in Sorted List (fast):
Da hast du natürlich recht, ich "dachte" es sei effektiver das on-fly zu machen.. und ich brauch das auch erst am ende.. richtig.
Es ist fast immer effizienter nur 1x zu sortieren wenn man nicht mehr braucht.
-
@Tyrdal sagte in Sorted List (fast):
Und wo hat der Punkt jetzt ne Länge? Ist das der Abstand von (0,0)?
sorry, Koordinaten und länge .. nach länge wird sortiert..
@DocShoe sagte in Sorted List (fast):
@SoIntMan sagte in Sorted List (fast):
aber "qsort" wusste gar nich dass sowas die c standart anbietet, was steckt da dahinter? sw oder hw implemtiert?
Das ist eine Funktion aus der C library, also in Software.
ja hab mal damit rumgespielt sieht gut aus
@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;)
-
@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;)
