Ich verstehe, dass Ruby-Arrays dynamisch und dynamisch skaliert werden; Ich kann jedoch keine klaren Informationen darüber finden, ob es sich um true Arrays handelt. d.h. sie sind zusammenhängend im Speicher (genauer gesagt, die Referenzen, die sie halten, sind zusammenhängend im Speicher).
Meine Annahme wäre, dass die Vergrößerung eines Ruby-Arrays die Neuzuweisung des gesamten Arrays an einen größeren zusammenhängenden Speicherblock erfordert, falls erforderlich.
Ist das korrekt oder ist "Array" in diesem Fall eine falsche Bezeichnung?
Die Ruby Language Specification schreibt für Array objects (oder any -Objekt) keine bestimmte Speicherrepräsentation vor. Das wäre zu restriktiv für die Implementoren. Tatsächlich schreibt es nicht einmal vor, dass Objekte überhaupt im Speicher leben müssen , was Implementierungen wie MagLev möglich macht, bei denen der Objektspeicher eine auf dem Datenträger gespeicherte OO-Datenbank statt RAM ist.
Die Ruby Language Specification schreibt auch keine speziellen Leistungsmerkmale für Methoden der Klasse Array vor.
Allerdings haben Ruby-Programmierer von bestimmten Array -Methoden bestimmte Leistungsgarantien erwartet (und jede Implementierung, die diese Garantien nicht erfüllt, wird von der Community einfach ignoriert), z.
Array#[] hat eine Worst-Case-Schrittkomplexität von O (#of slices) Array#<< hat eine Worst-Case-Schrittkomplexität von O (n) und eine amortisierte Worst-Case-Schrittkomplexität von O (1) Grundsätzlich ist die typische Leistung garantiert, die Sie von einem dynamischen Array erwarten würden.
Dies bedeutet mehr oder weniger, dass die einzige Möglichkeit, diese Leistungsgarantien zu erfüllen, darin besteht, dass die Implementierung den zusammenhängenden Speicher und die exponentielle Größenänderung verwenden muss.
Nachdem Sie die Quelle und die article referenziert von Darek in den Kommentaren, kann ich bestätigen, dass Ruby-Arrays sind in der Tat echte Arrays und bestehen aus zusammenhängenden Speicherblöcken, wo das Element an einem gegebenen Index kann in O (1) Zeit zugegriffen werden.
Es scheint, dass Ruby Arrays zu viel zuordnet, um die Effizienz von push und ähnlichen Operationen zu verbessern; Wenn die Kapazität des Arrays jedoch überschritten wird, wird das Array automatisch um% größer vergrößert.
Dies ist eine ziemlich wichtige Unterscheidung, die anscheinend weitgehend vernachlässigt wird. Hoffentlich wird diese Information für andere nützlich sein, die nach ähnlicher Erleuchtung suchen.