Sorted List (fast)

SoIntMan

Hallo Leute,

ich möchte in C eine sortierte Liste implementieren. Dabei ist die "maximale" Größe also Anzahl vorher bekannt bzw. fix definiert. Sortiert wird nach einem Wert der eine Länge X repräsentiert.

Nun habe ich 2 Varianten:

Eine Array, beim Einfügen eines neuen Elements, fange ich vorne an , schau "ab" welchem Elemente die "Länge" Variable "kleines ist" dann kopiere ich alle nachfolgenden Elemente mit "memmove" nach hinten und für das neue ein.
Ein "Linked List", Ich habe eine Array dessen Elemente (typen einen prev, next pointer) die liste hat einen head/tail pointer. beim Einfügen nehme ich ein eine frei stelle meines array, und verlinke diese entsprechender der Reihenfolgen.. müsste klar sein.

nun frage ich mich ob es noch eine "schneller" variante gibt bzw. eine eleganterer;) Wäre eine Binary Tree was? kann ich diesen schon in seiner Größe fix machen? wäre dieser schneller?

Oder was hätte ich noch für ne Idee ?

Danke und grüße

wob

@SoIntMan Du kannst in Variante 1 auch mit binary search in der Mitte anfangen zu suchen. Das ist bei langen Arrays schneller.

Überhaupt: wenn du nach schneller fragst, hängt das von der Länge ab (!). Die meisten Listen dürften kurz sein. Da ist eine lineare Suche mit mehr Vergleichen sogar schneller als eine binäre Suche mit weniger Vergleichen (aber mehr Rumspringen im Speicher (Cache etc.)). Die verkettete Liste ist meist sehr Cache-unfreundlich und sollte daher im Regelfall vermieden werden. (Da ist sicher mehr als nur Cache, Prozessoren machen heutzutage ja noch ganz viel anderen Krams, der da mit reinspielt...)

DocShoe

Was genau ist denn deine Anforderung? Wenn die Länge fix ist ginge vielleicht ein hybrider Ansatz:

Du kennst die Anzahl der Elemente und die Größe eines Elements, damit kennst du die Gesamtgröße aller Elemente (wenn da so Sachen wie char* auf strings oÄ nicht vorkommen).
Du allokierst den gesamten Speicher am Stück und zusätzlich eine Lookup-Tabelle mit Zeigern auf die einzelnen Einträge. Am Besten machste das auch noch zusammenhängend, damit du wirklich nur einen Speicherblock hast. Die Lookup-Tabelle der Einträge initialisiertst du anfänglich alle mit NULL, um unbenutzte Einträge zu kennzeichnen.
Wenn du einen neuen Eintrag hinzufügst kopierst du ihn in den Datenbereich des Blocks und trägst die Adresse der Einfügeposition in die Lookup-Tabelle ein. Anschließend musst du nur noch die Zeiger in der Lookup-Tabelle umsortieren, die Daten liegen immer an fester Position.

SoIntMan

@wob sagte in Sorted List (fast):

Überhaupt: wenn du nach schneller fragst, hängt das von der Länge ab (!). Die meisten Listen dürften kurz sein. Da ist eine lineare Suche mit mehr Vergleichen sogar schneller als eine binäre Suche mit weniger Vergleichen (aber mehr Rumspringen im Speicher (Cache etc.)). Die verkettete Liste ist meist sehr Cache-unfreundlich und sollte daher im Regelfall vermieden werden. (Da ist sicher mehr als nur Cache, Prozessoren machen heutzutage ja noch ganz viel anderen Krams, der da mit reinspielt...)

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

@DocShoe sagte in Sorted List (fast):

Wenn du einen neuen Eintrag hinzufügst kopierst du ihn in den Datenbereich des Blocks und trägst die Adresse der Einfügeposition in die Lookup-Tabelle ein. Anschließend musst du nur noch die Zeiger in der Lookup-Tabelle umsortieren, die Daten liegen immer an fester Position.

aber genau das ist ja das Problem wie sortiere ich das effektiv, der Hashtable hat ja quasi die Pointer des Elemente in sortierter Reihenfolge richtig? wenn ich nun einen "inserter" muss ich alle Pointer recht vom Index rüber kopieren.. du meinst dass ich wenider daten im Speicher rüberschieben, als enn die Gesamtgröße der Elemente verschiebe?

hustbaer

@SoIntMan sagte in Sorted List (fast):

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.