Das heißt, wäre ich besser geeignet, irgendeine Art von Baum- oder Sprunglisten-Datenstruktur zu verwenden, wenn ich diese Funktion für einzelne Array-Einfügungen viel aufrufen muss?Javascript: Was ist die algorithmische Leistung von "Spleiß"?
Sie können überlegen, ob Sie stattdessen eine gerade Karte verwenden möchten; Alle JavaScript-Objekte (einschließlich Array Instanzen) sind Karten, und so eine Implementierung sollte (ich sage nicht, "tut") haben eine angemessene Leistung Hashalgorithmus.
Abgesehen davon wird die Leistung von splice wird variieren Los zwischen Implementierungen (z. B. Anbieter). Dies ist einer der Gründe, warum "nicht vorzeitig optimieren" für JavaScript-Anwendungen, die in Implementierungen mehrerer Anbieter (z. B. Web-Apps) ausgeführt werden, sogar noch besser geeignet ist als für die normale Programmierung. Halten Sie Ihren Code gut modularisiert und beheben Sie Leistungsprobleme, wenn und wenn sie auftreten.
Problem mit einer Karte ist, glaube ich nicht, dass ich in sortierter Reihenfolge darüber iterieren kann ... – Hamster
@Hamster: Sie können, aber nur durch das Finden aller Schlüssel, sortieren sie und dann durch diese Liste. Wenn Sie viel tun müssen, dann sind Sie wahrscheinlich besser mit einem 'Array' (was in JavaScript ist schließlich nur eine Karte mit einer definierten Reihenfolge und eine magische 'Länge'-Eigenschaft). –
@ T.J.Crowder Was ist, wenn ich häufig ein Element in einen bestimmten Index zwischen bereits vorhandenen Elementen einfügen muss (d. H. Sie beibehalten und die Indizes neu anordnen muss), und es gibt Tausende von Elementen? Ich weiß, dass ich es mit "splice" machen kann, aber ist ein 'Array' mit' splice' eine richtige Datenstruktur für solch eine Aufgabe? Wenn nicht, welche andere JS-Datenstruktur könnte dafür geeignet sein? – tonix
Hier ist eine gute Faustregel basierend auf Tests durchgeführt, in Chrome, Safari und Firefox: so schnell grob Hälfte einen einzelnen Wert in der Mitte eines Feldes Spleißen als Schiebe-/Wert auf ein Ende der Verschiebung Array. (Hinweis: Nur auf einem Array von Größe getestet 10.000.)
http://jsperf.com/splicing-a-single-value
, die ziemlich schnell ist. Es ist daher unwahrscheinlich, dass Sie so weit gehen müssen, eine weitere Datenstruktur zu implementieren, um mehr Leistung herauszuholen.
aktualisieren: Als E-Business in den Kommentaren unten weist darauf hin, führt der Test einen teueren Kopiervorgang zusammen mit jedem splice, push und shift, was bedeutet, dass sie den Unterschied in der Leistung untertreibt. Hier ist ein überarbeiteter Test, den das Array Kopieren vermeidet, so sollte es sein, viel genauer: http://jsperf.com/splicing-a-single-value/19
Eigentlich hängt es vollständig von der Länge des Arrays ab. Wenn Sie zu einem Array mit 100.000 Elementen wechseln, ist das Spleißen eines Werts in der Mitte um 95% langsamer als das Hinzufügen eines Werts am Ende, gemessen an Ihrem jsperf-Test. Das liegt daran, dass das Einfügen in der Mitte O (n) in der Größe des Arrays ist, während das Einfügen am Ende O (1) sein kann. – Geoff
-1 Dieser JSperf-Test ist durch das Kopieren eines Arrays verunreinigt, es misst hauptsächlich die Zeit, die benötigt wird, um ein ganz neues 10000-Item-Array zu erstellen. – aaaaaaaaaaaa
@eBusiness Bitte erläutern Sie Ihren Anspruch. Wo wird das Array in den Tests kopiert? –
Verschieben einzelner Wert
// \t tmp = arr[1][i];
// \t arr[1].splice(i, 1); \t // splice is slow in FF
// \t arr[1].splice(end0_1, 0, tmp);
\t tmp = arr[1][i];
\t ii = i;
\t while (ii<end0_1)
\t \t {
\t \t arr[1][ii] = arr[1][++ii];
cycles++;
\t \t }
\t arr[1][end0_1] = tmp;
Test-it! Das ist der beste Weg, diese Frage zu beantworten ... – Harmen
Was ist eine gute Möglichkeit, dies zu testen? – Hamster
Wenn JavaScript-Arrays wirklich Arrays sind, ist es O (n). – Gumbo