Was ist die beste oder prägnanteste Methode, um eine Zeichenfolge zurückzugeben, die beliebig oft wiederholt wird?

Folgendes ist mein bisher bester Schuss:

function repeat(s, n){
    var a = [];
    while(a.length < n){
        a.push(s);
    }
    return a.join('');
}

Hinweis für neue Leser: Diese Antwort ist alt und nicht besonders praktisch - sie ist nur "clever", weil sie Array-Material verwendet, um String-Dinge zu erledigen. Als ich "weniger Prozess" schrieb, meinte ich definitiv "weniger Code", weil es, wie andere in den nachfolgenden Antworten bemerkt haben, wie ein Schwein funktioniert. Verwenden Sie es also nicht, wenn Ihnen die Geschwindigkeit wichtig ist.

Ich würde diese Funktion direkt auf das String-Objekt setzen. Anstatt ein Array zu erstellen, es zu füllen und mit einem leeren Zeichen zu verbinden, erstellen Sie einfach ein Array mit der richtigen Länge und verbinden Sie es mit der gewünschten Zeichenfolge. Gleiches Ergebnis, weniger Prozess!

String.prototype.repeat = function( num )
{
    return new Array( num + 1 ).join( this );
}

alert( "string to repeat\n".repeat( 4 ) );

Ich habe die Leistung aller vorgeschlagenen Ansätze getestet.

Hier ist die schnellste Variante, die ich habe.

String.prototype.repeat = function(count) {
    if (count < 1) return '';
    var result = '', pattern = this.valueOf();
    while (count > 1) {
        if (count & 1) result += pattern;
        count >>= 1, pattern += pattern;
    }
    return result + pattern;
};

Oder als eigenständige Funktion:

function repeat(pattern, count) {
    if (count < 1) return '';
    var result = '';
    while (count > 1) {
        if (count & 1) result += pattern;
        count >>= 1, pattern += pattern;
    }
    return result + pattern;
}

Es basiert auf dem Artistoex- Algorithmus. Es ist sehr schnell. Und je größer count, desto schneller geht es im Vergleich zum herkömmlichen new Array(count + 1).join(string)Ansatz.

Ich habe nur 2 Dinge geändert:

1. ersetzt pattern = thisdurch pattern = this.valueOf()(löscht eine offensichtliche Typkonvertierung);
2. if (count < 1)Überprüfung von prototypejs an der Spitze der Funktion hinzugefügt , um unnötige Aktionen in diesem Fall auszuschließen.
3. angewandte Optimierung von Dennis Antwort (5-7% Beschleunigung)

UPD

Erstellt ein wenig Performance-Testing Spielplatz hier für diejenigen , die interessiert sind .

Variable count~ 0 .. 100:

Konstante count= 1024:

Verwenden Sie es und machen Sie es noch schneller, wenn Sie können :)

Dieses Problem ist ein bekanntes / "klassisches" Optimierungsproblem für JavaScript, das durch die Tatsache verursacht wird, dass JavaScript-Zeichenfolgen "unveränderlich" sind und das Hinzufügen durch Verketten eines einzelnen Zeichens zu einer Zeichenfolge das Erstellen einschließlich der Speicherzuweisung für und das Kopieren in JavaScript erfordert , eine ganz neue Zeichenfolge.

Leider ist die akzeptierte Antwort auf dieser Seite falsch, wobei "falsch" einen Leistungsfaktor von 3x für einfache Zeichenfolgen mit einem Zeichen und 8x-97x für kurze Zeichenfolgen bedeutet, die mehrmals wiederholt werden, bis 300x für wiederholte Sätze und unendlich falsch, wenn Nehmen Sie die Grenze der Komplexitätsverhältnisse der Algorithmen nbis ins Unendliche. Außerdem gibt es auf dieser Seite eine andere Antwort, die fast richtig ist (basierend auf einer der vielen Generationen und Variationen der richtigen Lösung, die in den letzten 13 Jahren im Internet verbreitet wurde). Bei dieser "fast richtigen" Lösung fehlt jedoch ein wichtiger Punkt des richtigen Algorithmus, was zu einer Leistungsminderung von 50% führt.

JS-Leistungsergebnisse für die akzeptierte Antwort, die leistungsstärkste andere Antwort (basierend auf einer verschlechterten Version des ursprünglichen Algorithmus in dieser Antwort) und diese Antwort unter Verwendung meines vor 13 Jahren erstellten Algorithmus

~ Oktober 2000 Ich veröffentlichte einen Algorithmus für genau dieses Problem, der weitgehend angepasst, modifiziert, schließlich schlecht verstanden und vergessen wurde. Um dieses Problem zu beheben, veröffentlichte ich im August 2008 einen Artikel http://www.webreference.com/programming/javascript/jkm3/3.html , in dem der Algorithmus erläutert und als Beispiel für einfache JavaScript-Optimierungen für allgemeine Zwecke verwendet wurde. Inzwischen hat Web Reference meine Kontaktinformationen und sogar meinen Namen aus diesem Artikel entfernt. Und wieder einmal wurde der Algorithmus weitgehend angepasst, modifiziert, dann schlecht verstanden und weitgehend vergessen.

Ursprünglicher JavaScript-Algorithmus zur Wiederholung / Multiplikation von Zeichenfolgen von Joseph Myers, circa Y2K als Textmultiplikationsfunktion in Text.js; veröffentlicht im August 2008 in dieser Form von Web Reference: http://www.webreference.com/programming/javascript/jkm3/3.html (Der Artikel verwendete die Funktion als Beispiel für JavaScript-Optimierungen, die die einzige für die Seltsamen ist Name "stringFill3.")

/*
 * Usage: stringFill3("abc", 2) == "abcabc"
 */

function stringFill3(x, n) {
    var s = '';
    for (;;) {
        if (n & 1) s += x;
        n >>= 1;
        if (n) x += x;
        else break;
    }
    return s;
}

Innerhalb von zwei Monaten nach Veröffentlichung dieses Artikels wurde dieselbe Frage an Stack Overflow gesendet und flog bis jetzt unter meinem Radar, als anscheinend der ursprüngliche Algorithmus für dieses Problem erneut vergessen wurde. Die beste auf dieser Stapelüberlaufseite verfügbare Lösung ist eine modifizierte Version meiner Lösung, die möglicherweise durch mehrere Generationen getrennt ist. Leider haben die Modifikationen die Optimalität der Lösung ruiniert. In der Tat führt die modifizierte Lösung durch Ändern der Struktur der Schleife von meinem Original einen völlig unnötigen zusätzlichen Schritt des exponentiellen Duplizierens aus (wodurch die größte in der richtigen Antwort verwendete Zeichenfolge mit sich selbst verbunden wird und diese dann verworfen wird).

Im Folgenden werden einige JavaScript-Optimierungen erläutert, die sich auf alle Antworten auf dieses Problem und zum Nutzen aller beziehen.

Technik: Vermeiden Sie Verweise auf Objekte oder Objekteigenschaften

Um zu veranschaulichen, wie diese Technik funktioniert, verwenden wir eine reale JavaScript-Funktion, mit der Zeichenfolgen beliebiger Länge erstellt werden. Und wie wir sehen werden, können weitere Optimierungen hinzugefügt werden!

Eine Funktion wie die hier verwendete besteht darin, Auffüllungen zu erstellen, um Textspalten auszurichten, Geld zu formatieren oder Blockdaten bis zur Grenze zu füllen. Eine Texterzeugungsfunktion ermöglicht auch die Eingabe variabler Länge zum Testen aller anderen Funktionen, die mit Text arbeiten. Diese Funktion ist eine der wichtigen Komponenten des JavaScript-Textverarbeitungsmoduls.

Im weiteren Verlauf werden wir zwei weitere der wichtigsten Optimierungstechniken behandeln und gleichzeitig den ursprünglichen Code zu einem optimierten Algorithmus zum Erstellen von Zeichenfolgen entwickeln. Das Endergebnis ist eine industrietaugliche Hochleistungsfunktion, die ich überall verwendet habe - das Anpassen von Artikelpreisen und -summen in JavaScript-Bestellformularen, Datenformatierung und E-Mail- / Textnachrichtenformatierung und viele andere Verwendungszwecke.

Originalcode zum Erstellen von Zeichenfolgen stringFill1()

function stringFill1(x, n) { 
    var s = ''; 
    while (s.length < n) s += x; 
    return s; 
} 
/* Example of output: stringFill1('x', 3) == 'xxx' */ 

Die Syntax ist hier klar. Wie Sie sehen, haben wir bereits lokale Funktionsvariablen verwendet, bevor wir weitere Optimierungen vornehmen.

Beachten Sie, dass es einen unschuldigen Verweis auf eine Objekteigenschaft gibt s.length der Code enthält, der die Leistung beeinträchtigt. Noch schlimmer ist, dass die Verwendung dieser Objekteigenschaft die Einfachheit des Programms verringert, indem davon ausgegangen wird, dass der Leser die Eigenschaften von JavaScript-Zeichenfolgenobjekten kennt.

Die Verwendung dieser Objekteigenschaft zerstört die Allgemeinheit des Computerprogramms. Das Programm geht davon aus, dass xes sich um eine Zeichenfolge der Länge eins handeln muss. Dies beschränkt die Anwendung der stringFill1()Funktion auf alles außer der Wiederholung einzelner Zeichen. Selbst einzelne Zeichen können nicht verwendet werden, wenn sie mehrere Bytes enthalten, wie die HTML-Entität  .

Das schlimmste Problem, das durch diese unnötige Verwendung einer Objekteigenschaft verursacht wird, besteht darin, dass die Funktion eine Endlosschleife erstellt, wenn sie an einer leeren Eingabezeichenfolge getestet wird x . Wenden Sie zur Überprüfung der Allgemeinheit ein Programm auf die kleinstmögliche Eingabemenge an. Ein Programm, das abstürzt, wenn es aufgefordert wird, den verfügbaren Speicher zu überschreiten, hat eine Entschuldigung. Ein Programm wie dieses, das abstürzt, wenn man aufgefordert wird, nichts zu produzieren, ist inakzeptabel. Manchmal ist hübscher Code giftiger Code.

Einfachheit mag ein mehrdeutiges Ziel der Computerprogrammierung sein, ist es aber im Allgemeinen nicht. Wenn einem Programm ein angemessener Grad an Allgemeinheit fehlt, kann man nicht sagen: "Das Programm ist soweit gut genug." Wie Sie sehen können, string.lengthverhindert die Verwendung der Eigenschaft, dass dieses Programm in einer allgemeinen Einstellung funktioniert, und tatsächlich ist das falsche Programm bereit, einen Browser- oder Systemabsturz zu verursachen.

Gibt es eine Möglichkeit, die Leistung dieses JavaScript zu verbessern und diese beiden schwerwiegenden Probleme zu beheben?

Natürlich. Verwenden Sie einfach ganze Zahlen.

Optimierter Code zum Erstellen von Zeichenfolgen stringFill2()

function stringFill2(x, n) { 
    var s = ''; 
    while (n-- > 0) s += x; 
    return s; 
} 

Timing-Code zum Vergleichen stringFill1()undstringFill2()

function testFill(functionToBeTested, outputSize) { 
    var i = 0, t0 = new Date(); 
    do { 
        functionToBeTested('x', outputSize); 
        t = new Date() - t0; 
        i++; 
    } while (t < 2000); 
    return t/i/1000; 
} 
seconds1 = testFill(stringFill1, 100); 
seconds2 = testFill(stringFill2, 100); 

Der bisherige Erfolg von stringFill2()

stringFill1() Es dauert 47,297 Mikrosekunden (Millionstelsekunden), um eine 100-Byte-Zeichenfolge zu füllen, und stringFill2() 27,68 Mikrosekunden, um dasselbe zu tun. Das ist fast eine Verdoppelung der Leistung, wenn ein Verweis auf eine Objekteigenschaft vermieden wird.

Technik: Vermeiden Sie es, langen Saiten kurze Saiten hinzuzufügen

Unser bisheriges Ergebnis sah gut aus - in der Tat sehr gut. Die verbesserte FunktionstringFill2() ist aufgrund der Verwendung unserer ersten beiden Optimierungen viel schneller. Würden Sie es glauben, wenn ich Ihnen sagen würde, dass es verbessert werden kann, um ein Vielfaches schneller zu sein als jetzt?

Ja, wir können dieses Ziel erreichen. Im Moment müssen wir erklären, wie wir vermeiden, kurze Zeichenfolgen an lange Zeichenfolgen anzuhängen.

Das kurzfristige Verhalten scheint im Vergleich zu unserer ursprünglichen Funktion recht gut zu sein. Informatiker analysieren gerne das "asymptotische Verhalten" einer Funktion oder eines Computerprogrammalgorithmus, dh sie untersuchen ihr Langzeitverhalten, indem sie es mit größeren Eingaben testen. Manchmal wird man ohne weitere Tests nie darauf aufmerksam, wie ein Computerprogramm verbessert werden kann. Um zu sehen, was passieren wird, erstellen wir eine 200-Byte-Zeichenfolge.

Das Problem, das sich zeigt stringFill2()

Mit unserer Timing-Funktion stellen wir fest, dass die Zeit für eine 200-Byte-Zeichenfolge auf 62,54 Mikrosekunden ansteigt, verglichen mit 27,68 für eine 100-Byte-Zeichenfolge. Es scheint, dass die Zeit für doppelt so viel Arbeit verdoppelt werden sollte, aber stattdessen verdreifacht oder vervierfacht. Aus Programmiererfahrung erscheint dieses Ergebnis seltsam, da die Funktion eher etwas schneller sein sollte, da die Arbeit effizienter ausgeführt wird (200 Byte pro Funktionsaufruf statt 100 Byte pro Funktionsaufruf). Dieses Problem hat mit einer heimtückischen Eigenschaft von JavaScript-Zeichenfolgen zu tun: JavaScript-Zeichenfolgen sind "unveränderlich".

Unveränderlich bedeutet, dass Sie eine Zeichenfolge nach ihrer Erstellung nicht mehr ändern können. Durch Hinzufügen von jeweils einem Byte verbrauchen wir kein weiteres Byte mehr Aufwand. Wir erstellen tatsächlich die gesamte Zeichenfolge plus ein weiteres Byte neu.

Um einer 100-Byte-Zeichenfolge ein weiteres Byte hinzuzufügen, sind 101 Byte Arbeit erforderlich. Lassen Sie uns kurz die Berechnungskosten für die Erstellung einer NBytefolge analysieren . Die Kosten für das Hinzufügen des ersten Bytes betragen 1 Rechenaufwand. Die Kosten für das Hinzufügen des zweiten Bytes betragen nicht eine Einheit, sondern 2 Einheiten (Kopieren des ersten Bytes in ein neues Zeichenfolgenobjekt sowie Hinzufügen des zweiten Bytes). Das dritte Byte erfordert Kosten von 3 Einheiten usw.

C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2). Das Symbol O(N^2)wird als Big O von N im Quadrat ausgesprochen und bedeutet, dass der Rechenaufwand auf lange Sicht proportional zum Quadrat der Zeichenfolgenlänge ist. Das Erstellen von 100 Zeichen erfordert 10.000 Arbeitseinheiten, und das Erstellen von 200 Zeichen erfordert 40.000 Arbeitseinheiten.

Aus diesem Grund dauerte das Erstellen von 200 Zeichen mehr als doppelt so lange als von 100 Zeichen. Tatsächlich hätte es viermal so lange dauern sollen. Unsere Programmiererfahrung war insofern richtig, als die Arbeit für längere Saiten etwas effizienter ausgeführt wird und daher nur etwa dreimal so lange dauerte. Sobald der Overhead des Funktionsaufrufs vernachlässigbar wird, wie lange eine Zeichenfolge erstellt wird, dauert die Erstellung einer doppelt so langen Zeichenfolge viermal so lange.

(Historischer Hinweis: Diese Analyse gilt nicht unbedingt für Zeichenfolgen im Quellcode, z. B. html = 'abcd\n' + 'efgh\n' + ... + 'xyz.\n'da der JavaScript-Quellcode-Compiler die Zeichenfolgen zusammenfügen kann, bevor sie zu einem JavaScript-Zeichenfolgenobjekt verarbeitet werden. Vor wenigen Jahren wurde die KJS-Implementierung von JavaScript würde beim Laden langer Quellcode-Zeichenfolgen, die durch Pluszeichen verbunden sind, einfrieren oder abstürzen. Da die Rechenzeit knapp war, war O(N^2)es nicht schwierig, Webseiten zu erstellen, die den Konqueror-Webbrowser überlasteten, oder Safari, das den KJS-JavaScript-Engine-Kern verwendete Dieses Problem trat auf, als ich eine Markup-Sprache und einen JavaScript-Markup-Sprachparser entwickelte, und dann entdeckte ich, was das Problem verursachte, als ich mein Skript für JavaScript Includes schrieb.)

Diese schnelle Verschlechterung der Leistung ist eindeutig ein großes Problem. Wie können wir damit umgehen, da wir die Art und Weise, wie JavaScript Zeichenfolgen als unveränderliche Objekte behandelt, nicht ändern können? Die Lösung besteht darin, einen Algorithmus zu verwenden, der die Zeichenfolge so oft wie möglich neu erstellt.

Zur Verdeutlichung ist es unser Ziel, das Hinzufügen kurzer Zeichenfolgen zu langen Zeichenfolgen zu vermeiden, da zum Hinzufügen der kurzen Zeichenfolge auch die gesamte lange Zeichenfolge dupliziert werden muss.

So funktioniert der Algorithmus, um zu vermeiden, dass langen Zeichenfolgen kurze Zeichenfolgen hinzugefügt werden

Hier ist eine gute Möglichkeit, die Häufigkeit zu verringern, mit der neue Zeichenfolgenobjekte erstellt werden. Verketten Sie längere Zeichenfolgenlängen miteinander, sodass der Ausgabe mehr als ein Byte gleichzeitig hinzugefügt wird.

Um beispielsweise eine Zeichenfolge mit einer Länge zu erstellen N = 9:

x = 'x'; 
s = ''; 
s += x; /* Now s = 'x' */ 
x += x; /* Now x = 'xx' */ 
x += x; /* Now x = 'xxxx' */ 
x += x; /* Now x = 'xxxxxxxx' */ 
s += x; /* Now s = 'xxxxxxxxx' as desired */

Dazu musste eine Zeichenfolge mit der Länge 1 erstellt, eine Zeichenfolge mit der Länge 2 erstellt, eine Zeichenfolge mit der Länge 4 erstellt, eine Zeichenfolge mit der Länge 8 erstellt und schließlich eine Zeichenfolge mit der Länge 9 erstellt werden. Wie viel Kosten haben wir gespart?

Alte Kosten C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45.

Neue Kosten C(9) = 1 + 2 + 4 + 8 + 9 = 24.

Beachten Sie, dass wir einer Zeichenfolge der Länge 0 eine Zeichenfolge der Länge 1 hinzufügen mussten, dann eine Zeichenfolge der Länge 1 einer Zeichenfolge der Länge 1, dann eine Zeichenfolge der Länge 2 einer Zeichenfolge der Länge 2 und dann eine Zeichenfolge der Länge 4 zu einer Zeichenfolge der Länge 4, dann eine Zeichenfolge der Länge 8 zu einer Zeichenfolge der Länge 1, um eine Zeichenfolge der Länge 9 zu erhalten. Was wir tun, kann so zusammengefasst werden, dass das Hinzufügen kurzer Zeichenfolgen zu langen Zeichenfolgen oder in anderen vermieden wird Wörter, die versuchen, Zeichenfolgen miteinander zu verketten, die gleich oder nahezu gleich lang sind.

Für die alten Rechenkosten haben wir eine Formel gefunden N(N+1)/2. Gibt es eine Formel für die neuen Kosten? Ja, aber es ist kompliziert. Das Wichtigste ist, dass dies der Fall ist. Wenn Sie O(N)also die Länge der Saite verdoppeln, verdoppelt sich der Arbeitsaufwand ungefähr, anstatt ihn zu vervierfachen.

Der Code, der diese neue Idee implementiert, ist fast so kompliziert wie die Formel für die Rechenkosten. Denken Sie beim Lesen daran, dass Sie >>= 1um 1 Byte nach rechts verschieben müssen. Wenn n = 10011es sich also um eine Binärzahl handelt, n >>= 1ergibt sich der Wert n = 1001.

Der andere Teil des Codes, den Sie möglicherweise nicht erkennen, ist der bitweise geschriebene Operator &. Der Ausdruck n & 1wertet true aus, wenn die letzte Binärziffer von n1 ist, und false, wenn die letzte Binärziffer von n0 ist.

Neue hocheffiziente stringFill3()Funktion

function stringFill3(x, n) { 
    var s = ''; 
    for (;;) { 
        if (n & 1) s += x; 
        n >>= 1; 
        if (n) x += x; 
        else break; 
    } 
    return s; 
} 

Für das ungeübte Auge sieht es hässlich aus, aber die Leistung ist nicht weniger als reizend.

Mal sehen, wie gut diese Funktion funktioniert. Nachdem Sie die Ergebnisse gesehen haben, werden Sie wahrscheinlich nie den Unterschied zwischen einem O(N^2)Algorithmus und einem O(N)Algorithmus vergessen .

stringFill1()Die Erstellung einer 200-Byte-Zeichenfolge dauert 88,7 Mikrosekunden (Millionstelsekunden), stringFill2()dauert 62,54 Sekunden und stringFill3()dauert nur 4,608 Sekunden. Was hat diesen Algorithmus so viel besser gemacht? Alle Funktionen nutzten die Verwendung lokaler Funktionsvariablen, aber die Nutzung der zweiten und dritten Optimierungstechniken führte zu einer zwanzigfachen Verbesserung der Leistung von stringFill3().

Tiefere Analyse

Was bringt diese besondere Funktion dazu, die Konkurrenz aus dem Wasser zu jagen?

Wie ich bereits erwähnt habe, ist der Grund dafür, dass diese beiden Funktionen stringFill1()und stringFill2()so langsam ausgeführt werden, dass JavaScript-Zeichenfolgen unveränderlich sind. Der Speicher kann nicht neu zugewiesen werden, damit jeweils ein weiteres Byte an die von JavaScript gespeicherten Zeichenfolgendaten angehängt werden kann. Jedes Mal, wenn ein weiteres Byte am Ende der Zeichenfolge hinzugefügt wird, wird die gesamte Zeichenfolge von Anfang bis Ende neu generiert.

Um die Leistung des Skripts zu verbessern, müssen Sie daher Zeichenfolgen mit längerer Länge vorberechnen, indem Sie zwei Zeichenfolgen vorab miteinander verketten und dann die gewünschte Zeichenfolgenlänge rekursiv aufbauen.

Um beispielsweise eine 16-Buchstaben-Byte-Zeichenfolge zu erstellen, wird zunächst eine Zwei-Byte-Zeichenfolge vorberechnet. Dann würde die Zwei-Byte-Zeichenfolge wiederverwendet, um eine Vier-Byte-Zeichenfolge vorab zu berechnen. Dann würde die Vier-Byte-Zeichenfolge wiederverwendet, um eine Acht-Byte-Zeichenfolge vorab zu berechnen. Schließlich würden zwei Acht-Byte-Zeichenfolgen wiederverwendet, um die gewünschte neue Zeichenfolge mit 16 Byte zu erstellen. Insgesamt mussten vier neue Zeichenfolgen erstellt werden, eine mit der Länge 2, eine mit der Länge 4, eine mit der Länge 8 und eine mit der Länge 16. Die Gesamtkosten betragen 2 + 4 + 8 + 16 = 30.

Langfristig kann diese Effizienz berechnet werden, indem in umgekehrter Reihenfolge addiert wird und eine geometrische Reihe verwendet wird, die mit einem ersten Term a1 = N beginnt und ein gemeinsames Verhältnis von r = 1/2 aufweist. Die Summe einer geometrischen Reihe ist gegeben durch a_1 / (1-r) = 2N.

Dies ist effizienter als das Hinzufügen eines Zeichens zum Erstellen einer neuen Zeichenfolge mit der Länge 2, das Erstellen einer neuen Zeichenfolge mit der Länge 3, 4, 5 usw. bis 16. Der vorherige Algorithmus verwendete diesen Prozess zum Hinzufügen eines einzelnen Bytes zu einem Zeitpunkt und die Gesamtkosten dafür wären n (n + 1) / 2 = 16 (17) / 2 = 8 (17) = 136.

Offensichtlich ist 136 eine viel größere Zahl als 30, und daher benötigt der vorherige Algorithmus viel, viel mehr Zeit, um eine Zeichenfolge aufzubauen.

Um die beiden Methoden zu vergleichen, können Sie sehen, wie viel schneller der rekursive Algorithmus (auch "Teilen und Erobern" genannt) auf einer Zeichenfolge mit der Länge 123.457 ist. Auf meinem FreeBSD-Computer erstellt dieser in der stringFill3()Funktion implementierte Algorithmus die Zeichenfolge in 0,001058 Sekunden, während die ursprüngliche stringFill1()Funktion die Zeichenfolge in 0,0808 Sekunden erstellt. Die neue Funktion ist 76-mal schneller.

Der Leistungsunterschied wächst, wenn die Länge der Zeichenfolge größer wird. In der Grenze, in der immer größere Zeichenfolgen erstellt werden, verhält sich die ursprüngliche Funktion ungefähr wie C1(konstante) Zeiten N^2, und die neue Funktion verhält sich wie C2(konstante) Zeiten N.

Von unserem Experiment können wir den Wert bestimmen C1zu sein C1 = 0.0808 / (123457)2 = .00000000000530126997, und den Wert C2zu sein C2 = 0.001058 / 123457 = .00000000856978543136. In 10 Sekunden könnte die neue Funktion eine Zeichenfolge mit 1.166.890.359 Zeichen erstellen. Um dieselbe Zeichenfolge zu erstellen, würde die alte Funktion 7.218.384 Sekunden Zeit benötigen.

Das sind fast drei Monate im Vergleich zu zehn Sekunden!

Ich antworte nur (einige Jahre zu spät), weil meine ursprüngliche Lösung für dieses Problem seit mehr als 10 Jahren im Internet schwebt und anscheinend von den wenigen, die sich daran erinnern, immer noch schlecht verstanden wird. Ich dachte, wenn ich hier einen Artikel darüber schreibe, würde ich helfen:

Leistungsoptimierungen für Hochgeschwindigkeits-JavaScript / Seite 3

Leider sind einige der anderen hier vorgestellten Lösungen immer noch einige, die drei Monate benötigen würden, um die gleiche Menge an Ausgabe zu erzeugen, die eine richtige Lösung in 10 Sekunden erzeugt.

Ich möchte mir die Zeit nehmen, einen Teil des Artikels hier als kanonische Antwort auf Stack Overflow zu reproduzieren.

Beachten Sie, dass der Algorithmus mit der besten Leistung hier eindeutig auf meinem Algorithmus basiert und wahrscheinlich von der Anpassung der 3. oder 4. Generation eines anderen geerbt wurde. Leider führten die Änderungen zu einer Verringerung der Leistung. Die Variation meiner hier vorgestellten Lösung verstand vielleicht meinen verwirrenden for (;;)Ausdruck nicht, der wie die Endlosschleife eines in C geschriebenen Servers aussieht und einfach so konzipiert wurde, dass eine sorgfältig positionierte break-Anweisung für die Schleifensteuerung möglich ist, die kompakteste Methode Vermeiden Sie es, die Zeichenfolge eine zusätzliche unnötige Zeit exponentiell zu replizieren.

Dieser ist ziemlich effizient

String.prototype.repeat = function(times){
    var result="";
    var pattern=this;
    while (times > 0) {
        if (times&1)
            result+=pattern;
        times>>=1;
        pattern+=pattern;
    }
    return result;
};

Gute Nachrichten! String.prototype.repeatist jetzt ein Teil von JavaScript .

"yo".repeat(2);
// returns: "yoyo"

Die Methode wird von allen gängigen Browsern außer Internet Explorer und Android Webview unterstützt. Eine aktuelle Liste finden Sie unter MDN: String.prototype.repeat> Browserkompatibilität .

MDN verfügt über eine Polyfüllung für Browser ohne Unterstützung.

String.prototype.repeat ist jetzt ES6-Standard.

'abc'.repeat(3); //abcabcabc

Erweiterung der Lösung von P. Bailey :

String.prototype.repeat = function(num) {
    return new Array(isNaN(num)? 1 : ++num).join(this);
    }

Auf diese Weise sollten Sie vor unerwarteten Argumenttypen geschützt sein:

var foo = 'bar';
alert(foo.repeat(3));              // Will work, "barbarbar"
alert(foo.repeat('3'));            // Same as above
alert(foo.repeat(true));           // Same as foo.repeat(1)

alert(foo.repeat(0));              // This and all the following return an empty
alert(foo.repeat(false));          // string while not causing an exception
alert(foo.repeat(null));
alert(foo.repeat(undefined));
alert(foo.repeat({}));             // Object
alert(foo.repeat(function () {})); // Function

EDIT: Dank an Jerone für seine elegante ++numIdee!

Verwenden Array(N+1).join("string_to_repeat")

/**  
@desc: repeat string  
@param: n - times  
@param: d - delimiter  
*/

String.prototype.repeat = function (n, d) {
    return --n ? this + (d || '') + this.repeat(n, d) : '' + this
};

So wiederholen Sie die Zeichenfolge mehrmals mit dem Delimeter.

Hier ist eine Verbesserung von 5-7% gegenüber der Antwort von disfated.

Rollen Sie die Schleife ab, indem Sie bei anhalten count > 1und result += pattnernnach der Schleife ein zusätzliches Concat durchführen. Dadurch wird vermieden, dass die Schleifen endgültig nicht verwendet werden, pattern += patternohne dass ein teurer If-Check erforderlich ist. Das Endergebnis würde so aussehen:

String.prototype.repeat = function(count) {
    if (count < 1) return '';
    var result = '', pattern = this.valueOf();
    while (count > 1) {
        if (count & 1) result += pattern;
        count >>= 1, pattern += pattern;
    }
    result += pattern;
    return result;
};

Und hier ist die Geige von disfated für die entrollte Version: http://jsfiddle.net/wsdfg/

function repeat(s, n) { var r=""; for (var a=0;a<n;a++) r+=s; return r;}

Tests der verschiedenen Methoden:

var repeatMethods = {
    control: function (n,s) {
        /* all of these lines are common to all methods */
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        return '';
    },
    divideAndConquer:   function (n, s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        with(Math) { return arguments.callee(floor(n/2), s)+arguments.callee(ceil(n/2), s); }
    },
    linearRecurse: function (n,s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        return s+arguments.callee(--n, s);
    },
    newArray: function (n, s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        return (new Array(isNaN(n) ? 1 : ++n)).join(s);
    },
    fillAndJoin: function (n, s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        var ret = [];
        for (var i=0; i<n; i++)
            ret.push(s);
        return ret.join('');
    },
    concat: function (n,s) {
        if (n==0) return '';
        if (n==1 || isNaN(n)) return s;
        var ret = '';
        for (var i=0; i<n; i++)
            ret+=s;
        return ret;
    },
    artistoex: function (n,s) {
        var result = '';
        while (n>0) {
            if (n&1) result+=s;
            n>>=1, s+=s;
        };
        return result;
    }
};
function testNum(len, dev) {
    with(Math) { return round(len+1+dev*(random()-0.5)); }
}
function testString(len, dev) {
    return (new Array(testNum(len, dev))).join(' ');
}
var testTime = 1000,
    tests = {
        biggie: { str: { len: 25, dev: 12 }, rep: {len: 200, dev: 50 } },
        smalls: { str: { len: 5, dev: 5}, rep: { len: 5, dev: 5 } }
    };
var testCount = 0;
var winnar = null;
var inflight = 0;
for (var methodName in repeatMethods) {
    var method = repeatMethods[methodName];
    for (var testName in tests) {
        testCount++;
        var test = tests[testName];
        var testId = methodName+':'+testName;
        var result = {
            id: testId,
            testParams: test
        }
        result.count=0;

        (function (result) {
            inflight++;
            setTimeout(function () {
                result.start = +new Date();
                while ((new Date() - result.start) < testTime) {
                    method(testNum(test.rep.len, test.rep.dev), testString(test.str.len, test.str.dev));
                    result.count++;
                }
                result.end = +new Date();
                result.rate = 1000*result.count/(result.end-result.start)
                console.log(result);
                if (winnar === null || winnar.rate < result.rate) winnar = result;
                inflight--;
                if (inflight==0) {
                    console.log('The winner: ');
                    console.log(winnar);
                }
            }, (100+testTime)*testCount);
        }(result));
    }
}

Hier ist die sichere JSLint-Version

String.prototype.repeat = function (num) {
  var a = [];
  a.length = num << 0 + 1;
  return a.join(this);
};

Für alle Browser

Dies ist ungefähr so ​​kurz wie es nur geht:

function repeat(s, n) { return new Array(n+1).join(s); }

Wenn Sie sich auch für die Leistung interessieren, ist dies ein viel besserer Ansatz:

function repeat(s, n) { var a=[],i=0;for(;i<n;)a[i++]=s;return a.join(''); }

Wenn Sie die Leistung beider Optionen vergleichen möchten, finden Sie in dieser Geige und in dieser Geige Benchmark-Tests. Während meiner eigenen Tests war die zweite Option in Firefox ungefähr 2-mal schneller und in Chrome ungefähr 4-mal schneller!

Nur für moderne Browser:

In modernen Browsern können Sie jetzt auch Folgendes tun:

function repeat(s,n) { return s.repeat(n) };

Diese Option ist nicht nur kürzer als beide anderen Optionen, sondern sogar schneller als die zweite Option.

Leider funktioniert es in keiner Version des Internet Explorers. Die Zahlen in der Tabelle geben die erste Browserversion an, die die Methode vollständig unterstützt:

function repeat(pattern, count) {
  for (var result = '';;) {
    if (count & 1) {
      result += pattern;
    }
    if (count >>= 1) {
      pattern += pattern;
    } else {
      return result;
    }
  }
}

Sie können es bei JSFiddle testen . Im Vergleich zu Hacky Array.joinund Mine ist es ungefähr 10 (Chrome) bis 100 (Safari) bis 200 (Firefox) mal schneller (je nach Browser).

Nur eine weitere Wiederholungsfunktion:

function repeat(s, n) {
  var str = '';
  for (var i = 0; i < n; i++) {
    str += s;
  }
  return str;
}

ES2015wurde diese repeat()Methode realisiert !

http://www.ecma-international.org/ecma-262/6.0/#sec-string.prototype.repeat
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/ Zeichenfolge / Wiederholung
http://www.w3schools.com/jsref/jsref_repeat.asp

/** 
 * str: String
 * count: Number
 */
const str = `hello repeat!\n`, count = 3;

let resultString = str.repeat(count);

console.log(`resultString = \n${resultString}`);
/*
resultString = 
hello repeat!
hello repeat!
hello repeat!
*/

({ toString: () => 'abc', repeat: String.prototype.repeat }).repeat(2);
// 'abcabc' (repeat() is a generic method)

// Examples

'abc'.repeat(0);    // ''
'abc'.repeat(1);    // 'abc'
'abc'.repeat(2);    // 'abcabc'
'abc'.repeat(3.5);  // 'abcabcabc' (count will be converted to integer)
// 'abc'.repeat(1/0);  // RangeError
// 'abc'.repeat(-1);   // RangeError

Dies kann die kleinste rekursive sein:

String.prototype.repeat = function(n,s) {
s = s || ""
if(n>0) {
   s += this
   s = this.repeat(--n,s)
}
return s}

Geige: http://jsfiddle.net/3Y9v2/

function repeat(s, n){
    return ((new Array(n+1)).join(s));
}
alert(repeat('R', 10));

Einfache rekursive Verkettung

Ich wollte es nur versuchen und habe folgendes gemacht:

function ditto( s, r, c ) {
    return c-- ? ditto( s, r += s, c ) : r;
}

ditto( "foo", "", 128 );

Ich kann nicht sagen, dass ich viel darüber nachgedacht habe, und es zeigt wahrscheinlich :-)

Das ist wohl besser

String.prototype.ditto = function( c ) {
    return --c ? this + this.ditto( c ) : this;
};

"foo".ditto( 128 );

Und es ähnelt einer bereits veröffentlichten Antwort - das weiß ich.

Aber warum überhaupt rekursiv sein?

Und wie wäre es auch mit einem kleinen Standardverhalten?

String.prototype.ditto = function() {
    var c = Number( arguments[ 0 ] ) || 2,
        r = this.valueOf();
    while ( --c ) {
        r += this;
    }
    return r;
}

"foo".ditto();

Denn obwohl die nicht rekursive Methode beliebig große Wiederholungen verarbeitet, ohne die Aufrufstapelbeschränkungen zu erreichen, ist sie viel langsamer.

Warum habe ich mir die Mühe gemacht, mehr Methoden hinzuzufügen, die nicht halb so clever sind ? wie die bereits veröffentlichten?

Teilweise zu meiner eigenen Unterhaltung, teils um auf einfachste Weise darauf hinzuweisen, dass es viele Möglichkeiten gibt, eine Katze zu häuten, und je nach Situation ist es durchaus möglich, dass die scheinbar beste Methode nicht ideal ist.

Eine relativ schnelle und ausgefeilte Methode kann unter bestimmten Umständen effektiv abstürzen und brennen, während eine langsamere, einfachere Methode die Arbeit erledigen kann - schließlich.

Einige Methoden können kaum mehr als Exploits sein und als solche dazu neigen, aus dem Leben gerissen zu werden, und andere Methoden können unter allen Bedingungen wunderbar funktionieren, sind aber so konstruiert, dass man einfach keine Ahnung hat, wie es funktioniert.

"Und wenn ich nicht weiß, wie es funktioniert?!"

Ernsthaft?

JavaScript leidet unter einer seiner größten Stärken. Es ist sehr tolerant gegenüber schlechtem Verhalten und so flexibel, dass es sich nach hinten beugt, um Ergebnisse zu erzielen, wenn es für alle besser gewesen wäre, wenn es geknackt hätte!

"Mit großer Kraft geht große Verantwortung einher " ;-)

Aber ernster und wichtiger, obwohl allgemeine Fragen wie diese zu Ehrfurcht in Form kluger Antworten führen, die nicht zuletzt das eigene Wissen und den eigenen Horizont erweitern , sondern letztendlich die anstehende Aufgabe - das praktische Skript, das die resultierende Methode verwendet - erfordert möglicherweise etwas weniger oder etwas klüger als vorgeschlagen.

Diese "perfekten" Algorithmen machen Spaß und alles, aber "one size fits all" wird selten, wenn überhaupt, besser sein als maßgeschneidert.

Diese Predigt wurde Ihnen mit freundlicher Genehmigung von Schlafmangel und vorübergehendem Interesse gebracht. Geh hinaus und codiere!

Erstens scheinen sich die Fragen des OP auf Prägnanz zu beziehen - was ich als "einfach und leicht zu lesen" verstehe, während sich die meisten Antworten auf Effizienz zu beziehen scheinen - was offensichtlich nicht dasselbe ist, und ich denke auch, dass es nicht so ist, wenn Sie einige sehr implementieren Bestimmte Algorithmen zur Manipulation großer Datenmengen sollten Sie nicht beunruhigen, wenn Sie grundlegende Javascript-Funktionen zur Datenmanipulation implementieren. Prägnanz ist viel wichtiger.

Zweitens ist String.repeat, wie André Laszlo bemerkte, Teil von ECMAScript 6 und bereits in mehreren gängigen Implementierungen verfügbar. Die prägnanteste Implementierung String.repeatbesteht also darin, es nicht zu implementieren ;-)

Wenn Sie Hosts unterstützen müssen, die die ECMAScript 6-Implementierung nicht anbieten, ist die von André Laszlo erwähnte Polyfüllung von MDN alles andere als prägnant.

Also, ohne weiteres - hier ist meine prägnante Polyfüllung:

String.prototype.repeat = String.prototype.repeat || function(n){
    return n<=1 ? this : this.concat(this.repeat(n-1));
}

Ja, das ist eine Rekursion. Ich mag Rekursionen - sie sind einfach und bei richtiger Ausführung leicht zu verstehen. In Bezug auf die Effizienz können sie, wenn die Sprache dies unterstützt, sehr effizient sein, wenn sie richtig geschrieben sind.

Nach meinen Tests ist diese Methode ~ 60% schneller als der Array.joinAnsatz. Obwohl die Implementierung von disfated offensichtlich nicht annähernd erreicht wird, ist sie viel einfacher als beide.

Mein Test-Setup ist Knoten v0.10, der den "Strict-Modus" verwendet (ich denke, er ermöglicht eine Art TCO ) und repeat(1000)eine 10- stellige Zeichenfolge millionenfach aufruft .

Wenn Sie der Meinung sind, dass all diese Prototypdefinitionen, Array-Erstellungen und Verknüpfungsvorgänge übertrieben sind, verwenden Sie einfach einen einzelnen Zeilencode, wo Sie ihn benötigen. String S wird N-mal wiederholt:

for (var i = 0, result = ''; i < N; i++) result += S;

Verwenden Sie die Funktionen des Lodash for Javascript-Dienstprogramms, z. B. das Wiederholen von Zeichenfolgen.

Lodash bietet eine gute Leistung und ECMAScript-Kompatibilität.

Ich empfehle es sehr für die UI-Entwicklung und es funktioniert auch serverseitig gut.

So wiederholen Sie die Zeichenfolge "yo" zweimal mit Lodash:

> _.repeat('yo', 2)
"yoyo"

Rekursive Lösung mit Teilen und Erobern:

function repeat(n, s) {
    if (n==0) return '';
    if (n==1 || isNaN(n)) return s;
    with(Math) { return repeat(floor(n/2), s)+repeat(ceil(n/2), s); }
}

Ich kam zufällig hierher und hatte noch nie einen Grund, ein Zeichen in Javascript zu wiederholen.

Ich war beeindruckt von der Vorgehensweise von artistoex und den Ergebnissen von disfated. Ich bemerkte, dass das letzte Saiten-Concat unnötig war, wie Dennis ebenfalls betonte.

Ich bemerkte noch ein paar Dinge, als ich mit dem zusammengestellten Sampling spielte.

Die Ergebnisse variierten ziemlich stark, was häufig den letzten Lauf begünstigte, und ähnliche Algorithmen kämpften oft um die Position. Eines der Dinge, die ich geändert habe, war, anstatt die von JSLitmus generierte Anzahl als Startwert für die Aufrufe zu verwenden. Da die Anzahl für die verschiedenen Methoden unterschiedlich generiert wurde, habe ich einen Index eingegeben. Dies machte die Sache viel zuverlässiger. Ich habe dann darauf geachtet, sicherzustellen, dass Zeichenfolgen unterschiedlicher Größe an die Funktionen übergeben werden. Dies verhinderte einige der Variationen, die ich sah, bei denen einige Algorithmen bei einzelnen Zeichen oder kleineren Zeichenfolgen besser abschnitten. Unabhängig von der Zeichenfolgengröße haben sich die drei besten Methoden jedoch alle bewährt.

Gabel Testset

http://jsfiddle.net/schmide/fCqp3/134/

// repeated string
var string = '0123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890123456789';
// count paremeter is changed on every test iteration, limit it's maximum value here
var maxCount = 200;

var n = 0;
$.each(tests, function (name) {
    var fn = tests[name];
    JSLitmus.test(++n + '. ' + name, function (count) {
        var index = 0;
        while (count--) {
            fn.call(string.slice(0, index % string.length), index % maxCount);
            index++;
        }
    });
    if (fn.call('>', 10).length !== 10) $('body').prepend('<h1>Error in "' + name + '"</h1>');
});

JSLitmus.runAll();

Ich schloss dann Dennis 'Fix ein und beschloss zu sehen, ob ich einen Weg finden könnte, ein bisschen mehr herauszufinden.

Da Javascript die Dinge nicht wirklich optimieren kann, besteht der beste Weg zur Verbesserung der Leistung darin, Dinge manuell zu vermeiden. Wenn ich die ersten 4 trivialen Ergebnisse aus der Schleife herausnehmen würde, könnte ich 2-4 String-Speicher vermeiden und den endgültigen Speicher direkt in das Ergebnis schreiben.

// final: growing pattern + prototypejs check (count < 1)
'final avoid': function (count) {
    if (!count) return '';
    if (count == 1) return this.valueOf();
    var pattern = this.valueOf();
    if (count == 2) return pattern + pattern;
    if (count == 3) return pattern + pattern + pattern;
    var result;
    if (count & 1) result = pattern;
    else result = '';
    count >>= 1;
    do {
        pattern += pattern;
        if (count & 1) result += pattern;
        count >>= 1;
    } while (count > 1);
    return result + pattern + pattern;
}

Dies führte zu einer durchschnittlichen Verbesserung von 1-2% gegenüber Dennis 'Fix. Unterschiedliche Läufe und unterschiedliche Browser würden jedoch eine hinreichend unterschiedliche Varianz aufweisen, sodass sich dieser zusätzliche Code gegenüber den beiden vorherigen Algorithmen wahrscheinlich nicht lohnt.

Ein Diagramm

Edit: Ich habe das meistens unter Chrom gemacht. Firefox und IE bevorzugen Dennis oft um ein paar Prozent.

Einfache Methode:

String.prototype.repeat = function(num) {
    num = parseInt(num);
    if (num < 0) return '';
    return new Array(num + 1).join(this);
}

Menschen überkomplizieren dies in einem lächerlichen Ausmaß oder verschwenden Leistung. Arrays? Rekursion? Du willst mich wohl veralbern.

function repeat (string, times) {
  var result = ''
  while (times-- > 0) result += string
  return result
}

Bearbeiten. Ich habe einige einfache Tests durchgeführt, um sie mit der bitweisen Version von artistoex / disfated und einigen anderen Leuten zu vergleichen. Letzteres war nur unwesentlich schneller, aber um Größenordnungen speichereffizienter. Bei 1000000 Wiederholungen des Wortes "bla" stieg der Knotenprozess mit dem einfachen Verkettungsalgorithmus (oben) auf 46 Megabyte, mit dem logarithmischen Algorithmus jedoch nur auf 5,5 Megabyte. Letzteres ist definitiv der richtige Weg. Aus Gründen der Klarheit erneut veröffentlichen:

function repeat (string, times) {
  var result = ''
  while (times > 0) {
    if (times & 1) result += string
    times >>= 1
    string += string
  }
  return result
}

Verketten von Zeichenfolgen basierend auf einer Zahl.

function concatStr(str, num) {
   var arr = [];

   //Construct an array
   for (var i = 0; i < num; i++)
      arr[i] = str;

   //Join all elements
   str = arr.join('');

   return str;
}

console.log(concatStr("abc", 3));

Ich hoffe, das hilft!

Mit ES8 können Sie auch padStartoder padEnddafür verwenden. z.B.

var str = 'cat';
var num = 23;
var size = str.length * num;
"".padStart(size, str) // outputs: 'catcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcatcat'