Was ist die Laufzeit von Shift / Unshift in einem Ruby-Array?

Question

Was ist die Laufzeit von Shift / Unshift in einem Ruby-Array?

8

Weiß jemand, wie effizient Shift und Unshift in einem Ruby-Array sind?

Das Löschen am Anfang eines Arrays und das Verschieben jedes Elements im Speicher kann sehr ineffizient werden. Ich nehme an, dass Ruby dies anders macht.

Irgendwelche Infos zu den folgenden wären hilfreich:
- Algorithmische Laufzeitumgebung - Implementierung
- Allgemeine Effizienz - Wäre das Shift / Unshift akzeptabel für eine Queue (in etwas wie C ++ würde das nicht funktionieren)

Danke!

ruby big-o

djburdick 02.12.2011, 07:26

quelle

4 Antworten

0

Laut diesem Artikel scheint es, dass dies nicht der Fall ist wirklich verschieben, nur einen Zeiger inkrementieren und gibt das zurück. In Bezug auf Effizienz ist es also lächerlich effizient (O (1)). Der Artikel erwähnt jedoch ein mögliches Speicherleck, das in den neueren Releases vorhanden sein kann oder nicht.

Chris Eberle 02.12.2011 07:35
quelle

0

Ich fand, dass der einfachste und definitivste Weg, dies zu beantworten, darin bestand, es zu bewerten.
%Vor%
Auf meinem System, auf dem die Ruby-Version 2.0.0 ausgeführt wird, werden die Ergebnisse zurückgegeben:
%Vor%
Es scheint, dass push , pop , shift und unshift alle ungefähr die gleiche Zeit benötigen. Sie alle scheinen linear zu skalieren, wenn ich iterations ändere, was bedeutet, dass sie Operationen mit O(1) runtime sind. Ich würde sagen, dass dies als Warteschlange akzeptabel wäre.

Simon Baumgardt-Wellander 01.11.2017 19:50
quelle

Tags und Links ruby big-o

Django: Verwenden von Annotate, Count und Distinct in einem Queryset C # / C ++ in der gleichen Lösung - DllImport findet DLL nicht

score 3 · Answer 1

Sie können hier durchgehen und C Quelle sehen Code der Methode unshift (klicken Sie einfach auf den Beschreibungsblock). Es ist sehr klar: Erhöhen Sie die Speicherkapazität, wenn wir nicht schon genug haben, bewegen Sie den aktuellen Inhalt des Arrays vorwärts, kopieren Sie übergebene Argumente in den freien Speicherplatz am Anfang unseres Speicherblocks. Es ist also O(n) für unshift .

score 3 · Answer 2

In älteren Versionen von Ruby (vor ~ 2012) war unshift eine O (n) -Operation. Es wurde jedoch eine Optimierung in dieses Commit hinzugefügt, die das unshift amortisierte O (1) , was bedeutet, dass es durchschnittlich O (1) ist, aber eine einzelne Operation kann O (n) sein. Dies ist die gleiche Laufzeit wie shift .

Dieser CS Stack Exchange-Beitrag hat eine gute Erklärung dafür, wie das funktioniert und wie du am Ende eine O (1) amortisierte Laufzeit hast (es geht um C ++ vector::push_back , aber es funktioniert genauso).

score 0 · Answer 3

Laut diesem Artikel scheint es, dass dies nicht der Fall ist wirklich verschieben, nur einen Zeiger inkrementieren und gibt das zurück. In Bezug auf Effizienz ist es also lächerlich effizient (O (1)). Der Artikel erwähnt jedoch ein mögliches Speicherleck, das in den neueren Releases vorhanden sein kann oder nicht.

score 0 · Answer 4

Ich fand, dass der einfachste und definitivste Weg, dies zu beantworten, darin bestand, es zu bewerten.

%Vor%

Auf meinem System, auf dem die Ruby-Version 2.0.0 ausgeführt wird, werden die Ergebnisse zurückgegeben:

%Vor%

Es scheint, dass push , pop , shift und unshift alle ungefähr die gleiche Zeit benötigen. Sie alle scheinen linear zu skalieren, wenn ich iterations ändere, was bedeutet, dass sie Operationen mit O(1) runtime sind. Ich würde sagen, dass dies als Warteschlange akzeptabel wäre.