Sorted List (fast)

hustbaer

d.h. mit next/prev zwischen elementen rumspringen ist cache unfreundlich!? wie genau meinst du das?

Bei einer Linked List liegen die Elemente im Allgemeinen nicht hintereinander im Speicher. Sondern jedes Element irgendwo. D.h. immer wenn du von einem Element zum anderen "springst", wird auf einen anderen Speicherbereich zugegriffen. Und die CPU kann das nicht wirklich vorhersehen. D.h. die Chancen sind dabei höher dass der Speicherbereich vom nächsten Element nicht im Cache liegt.

Was die schnellste Variante ist hängt davon ab wie die Datenstruktur verwendet wird. Also z.B. wie oft folgende Operationen ausgeführt werden:

Neues Element einfügen
Altes Element löschen
"Random" Lookup anhand des Keys
Über die Liste iterieren

Weiters kann es einen Unterschied machen wie die Reihenfolge dieser Operationen ist. Immer einzelne insert/remove und dazwischen immer Lesezugriffe ist was anderes als 50x remove gefolgt von 50x insert gefolgt von 50x Lesezugriffen.

Und wie schon geschrieben wurde kommt es auf die Anzahl der Elemente an. Wenn wir von 10 oder 20 Elementen reden, dann nimm einfach ein sortiertes Array. Bzw. ein sortiertes Array aus Zeigern auf die Elemente.

SoIntMan

@hustbaer sagte in Sorted List (fast):

Bei einer Linked List liegen die Elemente im Allgemeinen nicht hintereinander im Speicher. Sondern jedes Element irgendwo. D.h. immer wenn du von einem Element zum anderen "springst", wird auf einen anderen Speicherbereich zugegriffen. Und die CPU kann das nicht wirklich vorhersehen. D.h. die Chancen sind dabei höher dass der Speicherbereich vom nächsten Element nicht im Cache liegt.

achso, verstehe.. ja das macht Sinn;)

So generell wird die Liste max. 50-100 Elemente groß sein, wobei im schnitt so 10-20 Einträge verwendet werden.

Ich möchte die Liste in sortierter Form füllen "insert" also 10-20 mal. und dann (1x) durch iterieren. Aber beim "inserten" integriere ich ja schon im Prinzip durch um die passende Stelle zu finden.

Die Variante mit "memove" kommt nicht in Frage? wäre das ineffektiver. da würde ja der Speicher schon on einem stück vorliegen wegen Caching und so.

Schlangenmensch

@SoIntMan Schreib doch alle Varianten und mach ein Profiling. Und, ganz wichtig: Teile deinen Code und Ergebnisse hier Ich bin an solchen Sachen immer sehr interessiert, kann aber so schwer abschätzen, was für deinen Anwendungsfall das Schnellste ist. Aus dem Bauch heraus würde ich auf ein Array tippen.

*john 0

@SoIntMan sagte in Sorted List (fast):

So generell wird die Liste max. 50-100 Elemente groß sein, wobei im schnitt so 10-20 Einträge verwendet werden.

Eine Cache Line in den meisten aktuellen CPUs ist 64Bytes groß. D.h. bei jedem Memory Access werden immer 64 Bytes in den L1 Cache geholt. Schnell ist ein Algorithmus, wenn er die 64Bytes möglichst optimal nutzen kann und die Zahl der Cache Misses auf ein notwendiges Minimum reduziert.

Was für Daten sollen hier überhaupt verwaltet werden?
Wenn die Daten größer sind, dann ist es eher sinnvoll einen Vektor (meint in C selbst allozierter Speicher) von Zeiger anzulegen und nur die Zeiger zu kopieren. Sind die Daten kleiner sollte man sie lieber direkt in den Vektor ablegen und dann beim Sortieren die Daten kopieren.

SoIntMan

@Schlangenmensch sagte in Sorted List (fast):

@SoIntMan Schreib doch alle Varianten und mach ein Profiling. Und, ganz wichtig: Teile deinen Code und Ergebnisse hier Ich bin an solchen Sachen immer sehr interessiert, kann aber so schwer abschätzen, was für deinen Anwendungsfall das Schnellste ist. Aus dem Bauch heraus würde ich auf ein Array tippen.

ja ich muss bis Ende des Jahre das ding "fertig" machen, wenn ich noch Zeit habe, mach ich da was. Profillinge mache ich mit gTest und std::chrono zeitmessung in Loops. Vermutlich gibt es bessere Profiling Tools;) aber vorweg.. Mit der Linked-List Variante bei 10 Elemente einfügen und jeweils wieder löschen 10000mal das ganze ~1ms (habe nen I7 irgendwas rechner):)

@john-0 sagte in Sorted List (fast):

Eine Cache Line in den meisten aktuellen CPUs ist 64Bytes groß. D.h. bei jedem Memory Access werden immer 64 Bytes in den L1 Cache geholt. Schnell ist ein Algorithmus, wenn er die 64Bytes möglichst optimal nutzen kann und die Zahl der Cache Misses auf ein notwendiges Minimum reduziert.

AHHH.. deswegen der Look-Up, um möglich wenig bytes an nem Stück zu haben 64Bytes:)

@john-0 sagte in Sorted List (fast):

Was für Daten sollen hier überhaupt verwaltet werden?

das sind einfach nur "punkte" auf einem Strahl im 2 Dimensionalen eines raum geordnet nach ihre Länge:)

Tyrdal

@SoIntMan sagte in Sorted List (fast):

das sind einfach nur "punkte" auf einem Strahl im 2 Dimensionalen eines raum geordnet nach ihre Länge:)

Sorry für Offtopic: Aber was für eine Länge haben den Punkte?

hustbaer

@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)
qsort aufrufen
Drüberiterieren

Also ich sehe keine Notwendigkeit das Array während des Einfügens sortiert zu halten.

SoIntMan

@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)

qsort aufrufen

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?

Tyrdal

@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)?

DocShoe

@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.

hustbaer

@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.

SoIntMan

@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;)

hustbaer

@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.

Schlangenmensch

@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

Peter Viehweger

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!

nameName

@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.

hustbaer

Sind die Daten denn überhaupt vorsortiert?

Peter Viehweger

wenn sie von vornherein mit insertionsort eingepflegt werden, oder einmalig mit quicksort o.ä. sortiert wurden, schon.

nameName

@Peter-Viehweger

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.

Peter Viehweger

@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.