Gesucht: Sehr Schnell verketteten Listen in C

Ich versuche zu implementieren ist eine einfach verknüpfte Liste in C Eine gemeinsame Umsetzung, die Sie sehen, schwimmende rund um das internet ist so etwas wie

typedef struct {
  int head;
  Node *tail;
} Node;

mit Methoden wie

Node cons(int head, Node tail) {
  Node y;
  y.head = head;
  y.tail = malloc(sizeof(Node));
  *y.tail = tail;
}

Leistung ist sehr wichtig. Gibt es eine Möglichkeit zum implementieren Sie eine verkettete Liste in C, die wird schneller sein als dieses? Zum Beispiel, loszuwerden, die memory allocation (y.tail = malloc(sizeof(Node))) sollte eine signifikante Erhöhung der Geschwindigkeit.

  • Ich habe nie gesehen, dass ein Knoten deklariert mit einer int head. Vielleicht meinst du int payload? Gleiches gilt für eine Node *tail. Vielleicht meinst du Node *next? Auch mit Ihrer aktuellen definition von Knoten Nachteile(...), Sie haben einen Typenkonflikt von Node head zugeordnet int head. Nichts für ungut, aber es scheint zu sein, tiefere Probleme als die Leistung...
  • nicht-standard-inplementation ich denke... im Grunde Leiter=Daten-und tail=link! Hasse es, wenn manche Lehrer versuchen, übermäßig vereinfachen Dinge!
  • Ram Bhat - glaube nicht, können Sie die Schuld auf die Lehrer. Er sagte, er fand, dass "im Umlauf auf dem Internet'.
  • Einige wud sagen, das ist informelle Bildung 😀
  • Frage mich, wo Sie gefunden, dass floating around'. Your cons function doesn't even have a return statement. And since you are doing copy by value for Schwanz' zweimal, performance-Probleme woanders liegen, denke ich.
  • Dies macht Sinn in Bezug auf car und cdr.
  • Was sind die Anforderungen an den container? Ist es wirklich sein muss, eine verknüpfte Liste? Welche Operationen sind die häufigsten? Die Operationen Kosten die? Die Antwort ist: einen solchen container, der Ihren Anforderungen angepasst. Sie gar nicht schreiben, was Sie sind ... einfach nur genauer sein, zu sagen "ich brauche eine schnelle Link-Liste" ist nicht genug.
  • Wenn Sie auf der Suche für die link-Liste bietet, schneller traversal, schauen Sie auf skip-Listen.

InformationsquelleAutor Michael Dickens | 2010-06-19
  1. 18

    Ja, es ist... Das heißt, wie ein Speicher-pool. Ähnlich wie ein thread-pool. Im Grunde weisen Sie einen Bereich des Arbeitsspeichers zu Beginn des Programms vom Typ Knoten. Zeiger auf diesem Bereich gespeichert sind, in ein array. In Ihrem cons-Funktion alles, was Sie tun ist, erhalten die Zeiger aus dem array. Dies verbessert nicht die Allgemeine Geschwindigkeit, aber wenn Sie Häufig Speicherzuordnungen dadurch erhöhen Sie die Reaktionsfähigkeit des Programms auf Kosten von Speicherplatz für das array

    • +1. Sie wirklich werden müssen pre-Zuweisung des Speicherplatzes für die Knoten in pools. Die einzelnen Zuweisungen werden dich töten, wenn Sie viele von Ihnen.
    • Ja... aber für eine verknüpfte Liste wie die, die er gezeigt wird, es tut nicht viel zur Sache 😛 .
    • +1. Ja, dies sollte eine wirksame Lösung.
    InformationsquelleAutor Laz
  2. 11

    Sehr schnell Anhängen an eine verkettete Liste? Ein Seil (nicht nur strings, die mit kleinen Modifikationen) würde ermöglichen es Ihnen, batch-Speicher (Verbesserung der Performance), während Sie nicht bestrafen anfügen an das Ende der Liste.

    • Verlinkten Listen nicht gut durchführen. +1 für die Annahme, die einzige vernünftige Antwort hier -- verwenden Sie eine andere Daten-Struktur! (Am besten etwas wie std::deque oder std::vector!)
    • Ich verstehe nicht, warum dein Kommentar hat gestimmt, da die Frage speziell an C und Sie befürworten eine C++ - Lösung.
    • Sie implementieren können, so etwas wie einen Vektor in C
    • Seil ist im wesentlichen ein binärer Baum. Für einige Operationen ist es langsamer als eine Liste. Es kann auch mit mehr Speicher-Zuteilung, je nach Zugriffsmuster.
    • Was @Pete gesagt. Die Worte "so etwas" tun tatsächlich etwas bedeuten 🙂
    • Aber umsetzen "so etwas wie std::vector in C" ist nicht zu sagen nichts anderes als "verwenden Sie eine andere, bessere Daten-Struktur". Was ist die Implementierung von std::vector?

    InformationsquelleAutor Yann Ramin
  3. 5

    Welche operation muss schnell sein: einfügen, retrieval, alle ? Es ist immer ein trade-off. Hat Ihre Lösung muss skalierbar sein ? Verknüpfte Liste nicht.

    Sollten Sie wollen/müssen zu halten, um eine verknüpfte Liste, die Sie speichern könnte es in ein array von structs mit einem Feld gibt den index des nächsten Eintrag in der verknüpften Liste. Einfügemarke sehr schnell, ohne eine Zuweisung, der Nachteil, Sie haben, um zu wissen, die Anzahl der Elemente im Voraus - oder Neuverteilung der Tabelle, wenn es immer voll.

    Beziehen sich auf die "Verknüpfte Listen mit arrays von Knoten" Unterabschnitt die Wikipedia-Seite verlinkten Liste.

    InformationsquelleAutor philant
  4. 3

    Speicher Bedenken beiseite, einige Gedanken zu machen single-link-Listen schneller.

    Ich denke, es ist ein wenig Verwirrung in Ihrem code. An ihm ist sehr Kern eine verknüpfte Liste ist:

    typdef struct _node {
     ...
     struct _node *next;
} NODE;

    Meisten Implementierungen würden einen void * dort hängen die Nutzlast auf. Das ist nicht besonders wichtig für jetzt.

    Liste fügt verbinden muss den Zeiger. Für das einfache hinzufügen der Knoten (und ignorieren dabei, dass das hinzufügen der Nutzlast) gibt es 1-Zuordnung, wenn der Knoten wird auf den Kopf oder Schwanz einer Liste, und 2, wenn es geht, in die Mitte. Es gibt nicht viel, das getan werden kann, um zu bekommen, dass.

    Gelegentlich einfache Listen nur verwenden, Knoten-Strukturen, so Schwanz einfügen erfordert traversal. Dies ist teuer. Mit einer speziellen Kopf-Struktur mit der Kenntnis der ersten und letzten Knoten entfernt, die Kosten.

    Traversalen können schneller gemacht werden, durch die Umsetzung dieser als skip-Liste (http://en.wikipedia.org/wiki/Skip_list). Obwohl einige Sorgfalt muss getroffen werden, während der Knoten-insertion zu optimieren (und Sie bekommen mehr Zeiger-Zuweisungen während der insertion).

    InformationsquelleAutor Jon L
  5. 2

    Wenn man sich mit malloc Fragmentierung, könnten Sie verlangen, eine große, mehrere Anzahl der Größe der Knoten und halten der Inkrementierung eines Zeigers durch sizeof(Knoten) jedes mal, wenn Sie kopieren Knoten-Werte.

    • Das ist wahrscheinlich besser als die array-Lösungen anderer vorschlagen. Sie haben zu verfolgen, Ihren pool und wissen, Wann die Zuweisung von mehr, und wissen, wenn alle Zeiger zurückgegeben wurden.
    InformationsquelleAutor Jeff Meatball Yang
  6. 2

    Ich würde vorschlagen, Sie verwenden linux-kernel-Liste Implementierung:

    http://git.kernel.org/?p=linux/kernel/git/torvalds/linux-2.6.git;a=blob;f=include/linux/list.h

    (keine zusätzliche memory allocation)

    • Eine Menge von performance-Problemen für Zeiger Lokalität und die Speicherzuweisung. Wie diese Umsetzung nicht implementiert, diese Teile, ich glaube nicht, dass es nützlich ist Michael Dickens.
    • git.kernel.org/?p=linux/kernel/git/torvalds/... Es auch prefetch-der nächste Zeiger für die nächste iteration. Vertrauen Sie mir, diese Liste im kernel sind SEHR optimiert
    InformationsquelleAutor Nicolas Viennot
  7. 0

    Überprüfen Sie die Geschwindigkeit dieser einfach verkettete Liste Implementierung:

    http://web.archive.org/web/20071103112712/http://stsdas.stsci.edu/bps/linked_list.html

    InformationsquelleAutor curoo
  8. 0

    Wenn die nur Operationen, die Sie benötigen, schieben, knallen und Durchlaufen dann statt der verlinkten Liste könnte man Elemente in ein array. Pushing und popping-element ist nur zu ändern, eine Zahl (index der das erste oder das Letzte element). Vorder-und Rückseite des Arrays werden zyklisch verbunden, so dass Elemente kann frei geschoben, ohne ein problem, dass das array endet.

    InformationsquelleAutor adf88
Schreibe einen Kommentar