Ich habe versucht, über die verschiedenen Datenstrukturen zu lernen, die in populären Sprachen verwendet werden, wie Listen und Wörterbücher in Python, assoziative Arrays in PHP (im Wesentlichen Hash-Tabellen), Vektoren in C ++, usw.
Ich habe eine Menge Kollegen, die R religiös verwenden, und ich habe mich gefragt, wie Vektoren, Matrizen und Datenrahmen in R implementiert werden. Was sind ihre Stärken und Schwächen? Ich habe den Quellcode durchgesehen, aber ich konnte die Datenstrukturen nicht selbst finden. Wo befinden sich diese Definitionen im Quellcode?
Wie bereits erwähnt, schauen Sie sich auch das Handbuch "R internals" an als diesen Teil von "Writing R extensions" .
Ein bisschen spät, aber wollte einen Fehler mit einer der anderen Antworten aufzeigen und eine explizite Antwort geben. Sehen Sie sich das Handbuch für Internes an:
Lesen Sie den Anfang dieses Abschnitts und den Eintrag für 'INTSXP'. Es scheint, dass ganzzahlige Vektoren als ein Array von C int implementiert sind. Ähnlich für 'REALSXP' und 'CHARSXP'.
Die Implementierung als verknüpfte Listen wäre zu langsam gewesen.
Von R Internals, 1.1 SEXPs:
... die Grundbausteine von R-Objekten werden oft Knoten genannt ... Beide Typen von Knotenstrukturen haben als ihre ersten drei Felder einen 32-Bit-spxinfo-Header und dann drei Zeiger (zu den Attributen und dem vorherigen und nächsten Knoten in einer doppelt verknüpften Liste)
Daher sind Vektoren in R als doppelt verknüpfte Liste implementiert. Und es scheint sogar, dass es keine Datenstruktur gibt, die kleiner als eine verknüpfte Liste mit einem einzigen Knoten ist. Dies wird offensichtlich durch:
%Vor%Wie von anderen erwähnt: %code% hat %code% und %code% und %code% hat die Quelle für %code% . Zusätzlich enthält %code% die Quelle für %code% und %code% enthält die Quelle für %code% .
Während viele Dinge, die sich abspielten, über meinem Kopf lagen, scheint es offensichtlich, dass eine Matrix einfach eine doppelt verknüpfte Liste doppelt verknüpfter Listen ist. Ich glaube (obwohl ich nicht sicher bin), dass Zeilen- und Spaltennamen (wie die in einem Datenrahmen gespeicherten) in den 'Attributen' jeder Liste gespeichert sind.
Die Antwort auf die "Was die Stärken und Schwächen" der Implementierung der Datenstrukturen wäre, dass (aus meinem begrenzten Wissen) doppelt verknüpfte Listen eine Stärke darin haben, dass die dynamische Speicherzuweisung einfacher ist und keinen Overhead erfordert Kopieren und Neuzuweisen eines gesamten Arrays, und die Schwäche ist, dass (abhängig davon, wie viele Zeiger auf die Liste sind: Kopf, Schwanz, Mitte, Viertel usw.) der Zugriff auf einen zufälligen Wert %code% den Overhead des Iterierens in Anspruch nehmen kann mehrere Elemente vor dem gewünschten gefunden.
Stimmt das?
Ich habe versucht, über die verschiedenen Datenstrukturen zu lernen, die in populären Sprachen verwendet werden, wie Listen und Wörterbücher in Python, assoziative Arrays in PHP (im Wesentlichen Hash-Tabellen), Vektoren in C ++, usw.
Ich habe eine Menge Kollegen, die R religiös verwenden, und ich habe mich gefragt, wie Vektoren, Matrizen und Datenrahmen in R implementiert werden. Was sind ihre Stärken und Schwächen? Ich habe den Quellcode durchgesehen, aber ich konnte die Datenstrukturen nicht selbst finden. Wo befinden sich diese Definitionen im Quellcode?
Wie bereits erwähnt, schauen Sie sich auch das Handbuch "R internals" an als diesen Teil von "Writing R extensions" .
Von R Internals, 1.1 SEXPs:
... die Grundbausteine von R-Objekten werden oft Knoten genannt ... Beide Typen von Knotenstrukturen haben als ihre ersten drei Felder einen 32-Bit-spxinfo-Header und dann drei Zeiger (zu den Attributen und dem vorherigen und nächsten Knoten in einer doppelt verknüpften Liste)
Daher sind Vektoren in R als doppelt verknüpfte Liste implementiert. Und es scheint sogar, dass es keine Datenstruktur gibt, die kleiner als eine verknüpfte Liste mit einem einzigen Knoten ist. Dies wird offensichtlich durch:
%Vor% Wie von anderen erwähnt: builtin.c hat do_makevector und do_makelist und array.c hat die Quelle für do_matrix . Zusätzlich enthält array.c die Quelle für allocMatrix und memory.c enthält die Quelle für allocVector .
Während viele Dinge, die sich abspielten, über meinem Kopf lagen, scheint es offensichtlich, dass eine Matrix einfach eine doppelt verknüpfte Liste doppelt verknüpfter Listen ist. Ich glaube (obwohl ich nicht sicher bin), dass Zeilen- und Spaltennamen (wie die in einem Datenrahmen gespeicherten) in den 'Attributen' jeder Liste gespeichert sind.
Die Antwort auf die "Was die Stärken und Schwächen" der Implementierung der Datenstrukturen wäre, dass (aus meinem begrenzten Wissen) doppelt verknüpfte Listen eine Stärke darin haben, dass die dynamische Speicherzuweisung einfacher ist und keinen Overhead erfordert Kopieren und Neuzuweisen eines gesamten Arrays, und die Schwäche ist, dass (abhängig davon, wie viele Zeiger auf die Liste sind: Kopf, Schwanz, Mitte, Viertel usw.) der Zugriff auf einen zufälligen Wert v[99] den Overhead des Iterierens in Anspruch nehmen kann mehrere Elemente vor dem gewünschten gefunden.
Stimmt das?
Ein bisschen spät, aber wollte einen Fehler mit einer der anderen Antworten aufzeigen und eine explizite Antwort geben. Sehen Sie sich das Handbuch für Internes an:
Lesen Sie den Anfang dieses Abschnitts und den Eintrag für 'INTSXP'. Es scheint, dass ganzzahlige Vektoren als ein Array von C int implementiert sind. Ähnlich für 'REALSXP' und 'CHARSXP'.
Die Implementierung als verknüpfte Listen wäre zu langsam gewesen.
Tags und Links c r data-structures