Jaka jest najlepsza lub najbardziej zwięzła metoda zwracania ciągu powtórzonego dowolną liczbę razy?

Oto mój najlepszy do tej pory strzał:

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

Uwaga dla nowych czytelników: Ta odpowiedź jest stara i nie jest zbyt praktyczna - jest po prostu „sprytna”, ponieważ używa rzeczy Array do wykonania zadań String. Kiedy napisałem „mniej procesu”, zdecydowanie miałem na myśli „mniej kodu”, ponieważ, jak zauważyli inni w kolejnych odpowiedziach, działa jak świnia. Więc nie używaj go, jeśli liczy się prędkość.

Umieściłbym tę funkcję bezpośrednio w obiekcie String. Zamiast tworzyć tablicę, wypełniać ją i łączyć pustym znakiem, po prostu utwórz tablicę o odpowiedniej długości i połącz ją z pożądanym łańcuchem. Ten sam wynik, mniej procesów!

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

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

Testowałem wydajność wszystkich proponowanych podejść.

Oto najszybszy wariant , jaki mam.

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;
};

Lub jako samodzielna funkcja:

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;
}

Opiera się na algorytmie artistoex . To jest naprawdę szybkie. A im większy count, tym szybciej idzie w porównaniu z tradycyjnym new Array(count + 1).join(string)podejściem.

Zmieniłem tylko 2 rzeczy:

1. otrzymuje pattern = thissię z pattern = this.valueOf()(bezbarwnych oczywistym typu konwersji);
2. dodano if (count < 1)kontrolę od prototypejs na górze funkcji, aby wykluczyć niepotrzebne działania w tym przypadku.
3. zastosowana optymalizacja z odpowiedzi Dennisa (przyspieszenie 5-7%)

UPD

Stworzył małą wydajność testowania zabaw tutaj dla tych, którzy interesują.

zmienna count~ 0 .. 100:

stała count= 1024:

Skorzystaj z niego i jeszcze szybciej, jeśli możesz :)

Problem ten jest dobrze znanym / „klasycznym” problemem optymalizacji dla JavaScript, spowodowanym faktem, że ciągi JavaScript są „niezmienne”, a dodanie przez połączenie nawet jednego znaku z ciągu wymaga utworzenia, w tym alokacji pamięci i skopiowania do , cały nowy ciąg.

Niestety, przyjęta odpowiedź na tej stronie jest błędna, gdzie „zła” oznacza współczynnik wydajności 3x dla prostych ciągów jednoznakowych i 8x-97x dla krótkich ciągów powtarzanych więcej razy, do 300x dla powtarzania zdań i nieskończenie zły, gdy przyjmowanie granicy współczynników złożoności algorytmów ndo nieskończoności. Jest też inna odpowiedź na tej stronie, która jest prawie słuszna (oparta na jednej z wielu generacji i odmian prawidłowego rozwiązania krążących w Internecie w ciągu ostatnich 13 lat). Jednak w tym „prawie właściwym” rozwiązaniu brakuje kluczowego punktu prawidłowego algorytmu, powodując obniżenie wydajności o 50%.

Wyniki wydajności JS dla zaakceptowanej odpowiedzi, drugiej najbardziej wydajnej odpowiedzi (na podstawie zdegradowanej wersji oryginalnego algorytmu w tej odpowiedzi) i tej odpowiedzi przy użyciu mojego algorytmu utworzonego 13 lat temu

~ Październik 2000 Opublikowałem algorytm tego dokładnie problemu, który został szeroko dostosowany, zmodyfikowany, a następnie ostatecznie źle zrozumiany i zapomniany. Aby temu zaradzić, w sierpniu 2008 roku opublikowałem artykuł http://www.webreference.com/programming/javascript/jkm3/3.html wyjaśniający algorytm i wykorzystujący go jako przykład prostych ogólnych optymalizacji JavaScript. Do tej pory Web Reference wyczyściło moje dane kontaktowe, a nawet moje nazwisko z tego artykułu. I jeszcze raz algorytm został szeroko dostosowany, zmodyfikowany, a następnie źle zrozumiany i w dużej mierze zapomniany.

Oryginalny algorytm JavaScript powtarzania / mnożenia napisany przez Josepha Myersa, około Y2K jako funkcja mnożenia tekstu w Text.js; opublikowany w sierpniu 2008 roku w tej formie przez Web Reference: http://www.webreference.com/programming/javascript/jkm3/3.html (W artykule wykorzystano tę funkcję jako przykład optymalizacji JavaScript, która jest jedyną dziwną nazwa „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;
}

W ciągu dwóch miesięcy po opublikowaniu tego artykułu to samo pytanie zostało wysłane do Stack Overflow i leciało pod moim radarem aż do chwili, kiedy najwyraźniej pierwotny algorytm tego problemu został ponownie zapomniany. Najlepszym rozwiązaniem dostępnym na tej stronie przepełnienia stosu jest zmodyfikowana wersja mojego rozwiązania, prawdopodobnie rozdzielona przez kilka pokoleń. Niestety modyfikacje zepsuły optymalność rozwiązania. W rzeczywistości, zmieniając strukturę pętli z mojego oryginału, zmodyfikowane rozwiązanie wykonuje całkowicie niepotrzebny dodatkowy krok wykładniczego powielania (łącząc w ten sposób największy ciąg użyty we właściwej odpowiedzi ze sobą dodatkowy czas, a następnie odrzucając go).

Poniżej omówiono niektóre optymalizacje JavaScript związane z wszystkimi odpowiedziami na ten problem i dla wszystkich.

Technika: Unikaj odwołań do obiektów lub właściwości obiektów

Aby zilustrować działanie tej techniki, używamy rzeczywistej funkcji JavaScript, która tworzy ciągi o dowolnej potrzebnej długości. I jak zobaczymy, można dodać więcej optymalizacji!

Funkcją taką jak tutaj użyta jest tworzenie wypełnienia w celu wyrównania kolumn tekstu, formatowania pieniędzy lub wypełniania danych bloku do granicy. Funkcja generowania tekstu umożliwia także wprowadzanie zmiennych długości w celu testowania dowolnej innej funkcji, która działa na tekście. Ta funkcja jest jednym z ważnych elementów modułu przetwarzania tekstu JavaScript.

W miarę postępów będziemy omawiać jeszcze dwie najważniejsze techniki optymalizacji, jednocześnie rozwijając oryginalny kod w zoptymalizowany algorytm do tworzenia łańcuchów. Ostateczny wynik to przemysłowa, wysokowydajna funkcja, z której korzystałem wszędzie - wyrównanie cen produktów i sum w formularzach zamówień JavaScript, formatowanie danych oraz formatowanie wiadomości e-mail / SMS i wiele innych zastosowań.

Oryginalny kod do tworzenia ciągów stringFill1()

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

Składnia jest tutaj jasna. Jak widać, użyliśmy już lokalnych zmiennych funkcji, zanim przejdziemy do dalszych optymalizacji.

Pamiętaj, że s.lengthw kodzie jest jedno niewinne odniesienie do właściwości obiektu, które ma negatywny wpływ na jego wydajność. Co gorsza, użycie tej właściwości obiektu zmniejsza prostotę programu, przyjmując założenie, że czytelnik wie o właściwościach ciągów znaków JavaScript.

Użycie tej właściwości obiektu niszczy ogólność programu komputerowego. Program zakłada, że xmusi to być ciąg długości jeden. Ogranicza to zastosowanie stringFill1()funkcji do czegokolwiek poza powtarzaniem pojedynczych znaków. Nawet pojedyncze znaki nie mogą być użyte, jeśli zawierają wiele bajtów, takich jak encja HTML  .

Najgorszym problemem spowodowanym tym niepotrzebnym użyciem właściwości obiektu jest to, że funkcja tworzy nieskończoną pętlę, jeśli jest testowana na pustym ciągu wejściowym x. Aby sprawdzić ogólność, zastosuj program do jak najmniejszej ilości danych wejściowych. Program, który ulega awarii, gdy zostanie wyświetlony monit o przekroczenie ilości dostępnej pamięci, ma usprawiedliwienie. Program taki jak ten, który ulega awarii, gdy zostanie poproszony o nic nie produkować, jest niedopuszczalny. Czasami ładny kod jest trującym kodem.

Prostota może być niejednoznacznym celem programowania komputerowego, ale generalnie tak nie jest. Gdy programowi brakuje jakiegokolwiek rozsądnego poziomu ogólności, nie można powiedzieć: „Program jest wystarczająco dobry, o ile to możliwe”. Jak widać, użycie tej string.lengthwłaściwości uniemożliwia temu programowi działanie w ustawieniach ogólnych, aw rzeczywistości niepoprawny program jest gotowy do spowodowania awarii przeglądarki lub systemu.

Czy istnieje sposób na poprawę wydajności tego JavaScript oraz rozwiązanie tych dwóch poważnych problemów?

Oczywiście. Po prostu użyj liczb całkowitych.

Zoptymalizowany kod do tworzenia ciągów stringFill2()

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

Kod czasowy do porównania stringFill1()istringFill2()

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); 

Dotychczasowy sukces stringFill2()

stringFill1()zajmuje 47.297 mikrosekund (milionowych części sekundy), aby wypełnić łańcuch o długości 100 bajtów, i stringFill2()zajmuje 27,68 mikrosekund, aby zrobić to samo. To prawie dwukrotne zwiększenie wydajności dzięki uniknięciu odwołania do właściwości obiektu.

Technika: Unikaj dodawania krótkich łańcuchów do długich łańcuchów

Nasz poprzedni wynik wyglądał dobrze - w rzeczywistości bardzo dobry. Udoskonalona funkcja stringFill2()jest znacznie szybsza dzięki zastosowaniu naszych pierwszych dwóch optymalizacji. Czy uwierzyłbyś, gdybym ci powiedział, że można go poprawić wiele razy szybciej niż teraz?

Tak, możemy osiągnąć ten cel. W tej chwili musimy wyjaśnić, w jaki sposób unikamy dodawania krótkich łańcuchów do długich łańcuchów.

Krótkoterminowe zachowanie wydaje się być całkiem dobre w porównaniu z naszą pierwotną funkcją. Informatycy lubią analizować „asymptotyczne zachowanie” algorytmu funkcji lub programu komputerowego, co oznacza badanie jego długoterminowego zachowania poprzez testowanie go przy użyciu większych danych wejściowych. Czasami bez wykonywania dalszych testów nigdy nie zdajemy sobie sprawy, w jaki sposób można poprawić program komputerowy. Aby zobaczyć, co się stanie, utworzymy ciąg 200-bajtowy.

Problem, który się pojawia stringFill2()

Korzystając z naszej funkcji pomiaru czasu, okazuje się, że czas wzrasta do 62,54 mikrosekundy dla ciągu 200-bajtowego, w porównaniu do 27,68 dla ciągu 100-bajtowego. Wydaje się, że czas należy podwoić, aby wykonać dwukrotnie więcej pracy, ale zamiast tego jest on trzykrotnie lub czterokrotnie. Z doświadczenia w programowaniu wynik ten wydaje się dziwny, ponieważ jeśli już, funkcja powinna być nieco szybsza, ponieważ praca jest wykonywana bardziej wydajnie (200 bajtów na wywołanie funkcji zamiast 100 bajtów na wywołanie funkcji). Ten problem dotyczy podstępnej właściwości ciągów JavaScript: ciągi JavaScript są „niezmienne”.

Niezmienny oznacza, że ​​nie można zmienić łańcucha po jego utworzeniu. Dodając jeden bajt na raz, nie zużywamy jeszcze jednego bajtu wysiłku. W rzeczywistości odtwarzamy cały ciąg plus jeszcze jeden bajt.

W efekcie, aby dodać jeszcze jeden bajt do ciągu 100-bajtowego, potrzeba 101 bajtów pracy. Przeanalizujmy krótko koszt obliczeniowy tworzenia ciągu Nbajtów. Koszt dodania pierwszego bajtu to 1 jednostka wysiłku obliczeniowego. Koszt dodania drugiego bajtu to nie jedna jednostka, ale 2 jednostki (skopiowanie pierwszego bajtu do nowego obiektu ciągu, a także dodanie drugiego bajtu). Trzeci bajt wymaga kosztu 3 jednostek itp.

C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2). Symbol O(N^2)jest wymawiany jako Big O z N do kwadratu, a to oznacza, że ​​koszt obliczeniowy w długim okresie jest proporcjonalny do kwadratu długości łańcucha. Stworzenie 100 znaków wymaga 10 000 jednostek pracy, a stworzenie 200 znaków wymaga 40 000 jednostek pracy.

Dlatego utworzenie ponad 200 znaków zajęło ponad dwa razy więcej czasu. W rzeczywistości powinno to zająć cztery razy dłużej. Nasze doświadczenie w programowaniu było prawidłowe, ponieważ praca jest wykonywana nieco bardziej wydajnie dla dłuższych ciągów, a zatem zajęło to tylko około trzy razy dłużej. Gdy narzut wywołania funkcji stanie się nieistotny, jeśli chodzi o długość tworzonego ciągu, utworzenie tego ciągu będzie czterokrotnie więcej czasu.

(Uwaga historyczna: Ta analiza niekoniecznie dotyczy łańcuchów w kodzie źródłowym, na przykład html = 'abcd\n' + 'efgh\n' + ... + 'xyz.\n', ponieważ kompilator kodu źródłowego JavaScript może łączyć łańcuchy razem przed przekształceniem ich w obiekt łańcucha JavaScript. Kilka lat temu implementacja KJS JavaScript zawiesza się lub ulega awarii podczas ładowania długich ciągów kodu źródłowego połączonych znakami plus. Ponieważ czas obliczeniowy O(N^2)nie był trudny, tworzenie stron internetowych, które przeciążały przeglądarkę Konqueror lub Safari, które korzystały z rdzenia silnika KJS JavaScript. natknąłem się na ten problem, gdy opracowywałem język znaczników i parser języka znaczników JavaScript, a następnie odkryłem, co było przyczyną problemu, gdy napisałem skrypt dla JavaScript Includes).

Oczywiście ta szybka degradacja wydajności jest ogromnym problemem. Jak sobie z tym poradzić, skoro nie możemy zmienić sposobu obsługi napisów przez JavaScript jako obiektów niezmiennych? Rozwiązaniem jest użycie algorytmu, który odtworzy ciąg tak mało, jak to możliwe.

Aby to wyjaśnić, naszym celem jest unikanie dodawania krótkich łańcuchów do długich łańcuchów, ponieważ aby dodać krótki łańcuch, cały długi łańcuch również musi zostać zduplikowany.

Jak działa algorytm, aby uniknąć dodawania krótkich łańcuchów do długich łańcuchów

Oto dobry sposób na zmniejszenie liczby razy, gdy tworzone są nowe obiekty łańcuchowe. Połącz dłuższe ciągi razem, aby do wyjścia dodawano więcej niż jeden bajt na raz.

Na przykład, aby utworzyć ciąg długości 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 */

Wykonanie tego wymagało utworzenia ciągu o długości 1, utworzenia ciągu o długości 2, utworzenia ciągu o długości 4, utworzenia ciągu o długości 8 i wreszcie utworzenia ciągu o długości 9. Ile zaoszczędziliśmy na kosztach?

Stary koszt C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45.

Nowy koszt C(9) = 1 + 2 + 4 + 8 + 9 = 24.

Zauważ, że musieliśmy dodać ciąg o długości 1 do ciągu o długości 0, następnie ciąg o długości 1 do ciągu o długości 1, a następnie ciąg o długości 2 do ciągu o długości 2, a następnie ciąg o długości 4 na ciąg o długości 4, następnie ciąg o długości 8 na ciąg o długości 1, w celu uzyskania ciągu o długości 9. To, co robimy, można streścić, unikając dodawania krótkich ciągów do długich ciągów lub w inny sposób słowa, próbując połączyć ze sobą ciągi o równej lub prawie równej długości.

Dla starego kosztu obliczeniowego znaleźliśmy wzór N(N+1)/2. Czy istnieje wzór na nowy koszt? Tak, ale to skomplikowane. Ważną rzeczą jest to, że tak jest O(N), dlatego podwojenie długości struny w przybliżeniu podwoi ilość pracy, zamiast ją czterokrotnie.

Kod implementujący ten nowy pomysł jest prawie tak skomplikowany, jak formuła kosztu obliczeniowego. Kiedy ją czytasz, pamiętaj, że >>= 1oznacza to przesunięcie w prawo o 1 bajt. Więc jeśli n = 10011jest liczbą binarną, to n >>= 1daje wartość n = 1001.

Inną częścią kodu, której możesz nie rozpoznać, jest zapis bitowy i operator &. Wyrażenie n & 1ocenia true, jeśli ostatnia cyfra binarna nto 1, i false, jeśli ostatnia cyfra binarna nwynosi 0.

Nowa wysoce wydajna stringFill3()funkcja

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

Dla niewprawnego oka wygląda to brzydko, ale jego wydajność jest niczym innym, jak uroczym.

Zobaczmy, jak dobrze działa ta funkcja. Po zobaczeniu wyników prawdopodobnie nigdy nie zapomnisz różnicy między O(N^2)algorytmem a O(N)algorytmem.

stringFill1()zajmuje 88,7 mikrosekund (milionowych części sekundy), aby utworzyć ciąg 200-bajtowy, stringFill2()zajmuje 62,54 i stringFill3()zajmuje tylko 4,608. Co sprawiło, że ten algorytm był o wiele lepszy? Wszystkie funkcje wykorzystały lokalne zmienne funkcyjne, ale skorzystanie z drugiej i trzeciej techniki optymalizacji dodało dwudziestokrotną poprawę wydajności stringFill3().

Głębsza analiza

Co sprawia, że ​​ta konkretna funkcja wysadza konkurencję z wody?

Jak już wspomniano, dlatego, że obie te funkcje, stringFill1()i stringFill2()uruchomić tak powoli, że ciągi są niezmienne JavaScript. Pamięci nie można ponownie przydzielić, aby umożliwić dołączenie jednego bajtu naraz do danych ciągów przechowywanych przez JavaScript. Za każdym razem, gdy na końcu łańcucha dodawany jest jeszcze jeden bajt, cały łańcuch jest generowany od początku do końca.

Tak więc, aby poprawić wydajność skryptu, należy wstępnie obliczyć łańcuchy o większej długości, łącząc dwa łańcuchy przed czasem, a następnie rekurencyjnie budując pożądaną długość łańcucha.

Na przykład, aby utworzyć 16-literowy ciąg bajtów, najpierw należy wstępnie obliczyć ciąg dwóch bajtów. Następnie dwubajtowy ciąg znaków zostałby ponownie wykorzystany do wstępnego obliczenia czterobajtowego ciągu. Następnie czterobajtowy ciąg znaków zostanie ponownie wykorzystany do wstępnego obliczenia ośmiobajtowego ciągu. Wreszcie dwa ośmiobajtowe ciągi znaków zostaną ponownie wykorzystane do utworzenia pożądanego nowego ciągu 16 bajtów. W sumie musiały zostać utworzone cztery nowe ciągi, jeden o długości 2, jeden o długości 4, jeden o długości 8 i jeden o długości 16. Całkowity koszt to 2 + 4 + 8 + 16 = 30.

Na dłuższą metę wydajność tę można obliczyć, dodając w odwrotnej kolejności i używając szeregu geometrycznego rozpoczynającego się od pierwszego członu a1 = N i mającego wspólny stosunek r = 1/2. Suma szeregu geometrycznego jest podana przez a_1 / (1-r) = 2N.

Jest to bardziej wydajne niż dodawanie jednego znaku w celu utworzenia nowego ciągu o długości 2, tworzenia nowego ciągu o długości 3, 4, 5 itd. Do 16. Poprzedni algorytm używał tego procesu dodawania pojedynczego bajtu naraz , a całkowity koszt wyniósłby n (n + 1) / 2 = 16 (17) / 2 = 8 (17) = 136.

Oczywiście 136 jest znacznie większą liczbą niż 30, więc poprzedni algorytm zajmuje dużo, dużo więcej czasu, aby zbudować ciąg.

Aby porównać te dwie metody, możesz zobaczyć, o ile szybciej algorytm rekurencyjny (zwany także „dziel i rządź”) ma ciąg długości 123.457. Na moim komputerze FreeBSD ten algorytm, zaimplementowany w stringFill3()funkcji, tworzy ciąg w 0,001058 sekund, podczas gdy oryginalna stringFill1()funkcja tworzy ciąg w 0,0808 sekund. Nowa funkcja jest 76 razy szybsza.

Różnica w wydajności rośnie wraz ze wzrostem długości łańcucha. W granicy, gdy tworzone są coraz większe ciągi, oryginalna funkcja zachowuje się mniej więcej tak jak C1(stałe) czasy N^2, a nowa funkcja zachowuje się jak C2(stała) razy N.

Na podstawie naszego eksperymentu możemy określić wartość C1bytu C1 = 0.0808 / (123457)2 = .00000000000530126997i wartość C2bytu C2 = 0.001058 / 123457 = .00000000856978543136. W ciągu 10 sekund nowa funkcja może utworzyć ciąg zawierający 1168 890 359 znaków. Aby utworzyć ten sam ciąg, stara funkcja potrzebowałaby 7 218 384 sekund.

To prawie trzy miesiące w porównaniu do dziesięciu sekund!

Odpowiadam tylko (kilka lat z opóźnieniem), ponieważ moje oryginalne rozwiązanie tego problemu krąży w Internecie od ponad 10 lat i najwyraźniej wciąż jest słabo rozumiane przez niewielu, którzy go pamiętają. Pomyślałem, że pisząc tutaj o tym artykuł, pomogę:

Optymalizacje wydajności dla szybkiego JavaScript / strona 3

Niestety, niektóre z innych przedstawionych tutaj rozwiązań to nadal niektóre z tych, które zajęłyby trzy miesiące, aby uzyskać taką samą moc wyjściową, jaką tworzy właściwe rozwiązanie w 10 sekund.

Chcę poświęcić trochę czasu na odtworzenie tutaj tego artykułu jako kanonicznej odpowiedzi na temat przepełnienia stosu.

Zauważ, że najskuteczniejszy algorytm tutaj jest wyraźnie oparty na moim algorytmie i prawdopodobnie został odziedziczony z adaptacji trzeciej lub czwartej generacji innej osoby. Niestety modyfikacje spowodowały zmniejszenie jego wydajności. Przedstawiona tutaj odmiana mojego rozwiązania może nie rozumieć mojego mylącego for (;;)wyrażenia, które wygląda jak główna nieskończona pętla serwera napisanego w C i które zostało po prostu zaprojektowane, aby umożliwić dokładnie ustawione polecenie break do sterowania pętlą, najbardziej kompaktowy sposób unikaj wykładniczego powtarzania ciągu o jeden dodatkowy niepotrzebny czas.

Ten jest dość wydajny

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

Dobre wieści! String.prototype.repeatjest teraz częścią JavaScript .

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

Ta metoda jest obsługiwana przez wszystkie główne przeglądarki, z wyjątkiem Internet Explorera i Androida Webview. Aby uzyskać aktualną listę, zobacz MDN: String.prototype.repeat> Kompatybilność z przeglądarkami .

MDN ma polifill dla przeglądarek bez wsparcia.

String.prototype.repeat ma teraz standard ES6.

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

Rozszerzanie rozwiązania P.Baileya :

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

W ten sposób powinieneś być bezpieczny przed nieoczekiwanymi typami argumentów:

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

EDYCJA: Podziękowania dla jerone za jego elegancki ++numpomysł!

Posługiwać się 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
};

w ten sposób kilka razy powtarza się ciąg za pomocą ogranicznika.

Oto 5-7% poprawa w stosunku do zdesperowanych.

Rozwiń pętlę, zatrzymując się przy niej count > 1i wykonaj dodatkową result += pattnernkonkat po pętli. Pozwoli to uniknąć pętli, które nie były poprzednio nieużywane pattern += patternbez konieczności korzystania z drogiego sprawdzania zgodności. Ostateczny wynik wyglądałby następująco:

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;
};

Oto rozwidlone skrzypce rozwidlone dla wersji rozwijanej: http://jsfiddle.net/wsdfg/

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

Testy różnych metod:

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));
    }
}

Oto bezpieczna wersja JSLint

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

Dla wszystkich przeglądarek

Jest to tak zwięzłe, jak to możliwe:

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

Jeśli zależy Ci również na wydajności, jest to znacznie lepsze podejście:

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

Jeśli chcesz porównać wydajność obu opcji, zobacz ten Fiddle i ten Fiddle do testów porównawczych. Podczas moich własnych testów druga opcja była około 2 razy szybsza w Firefoksie i około 4 razy szybsza w Chrome!

Tylko dla współczesnych przeglądarek:

W nowoczesnych przeglądarkach możesz teraz to zrobić:

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

Ta opcja jest nie tylko krótsza niż obie inne opcje, ale jest nawet szybsza niż druga opcja.

Niestety nie działa w żadnej wersji Internet Explorera. Liczby w tabeli określają pierwszą wersję przeglądarki, która w pełni obsługuje tę metodę:

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

Możesz to przetestować w JSFiddle . Porównywany z hacky Array.joini mój jest, z grubsza, 10 (Chrome) do 100 (Safari) do 200 (Firefox) razy szybciej (w zależności od przeglądarki).

Kolejna funkcja powtarzania:

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

ES2015zrealizowano tę repeat()metodę!

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/ Ciąg / powtórz
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

Może to być najmniejszy cykliczny:

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

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

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

Prosta rekurencyjna konkatenacja

Chciałem tylko dać temu spokój i zrobiłem to:

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

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

Nie mogę powiedzieć, że zastanowiłem się nad tym i prawdopodobnie pokazuje :-)

To jest prawdopodobnie lepsze

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

"foo".ditto( 128 );

I to bardzo przypomina odpowiedź już opublikowaną - wiem o tym.

Ale po co w ogóle być rekurencyjnym?

A może trochę domyślne zachowanie?

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

"foo".ditto();

Ponieważ chociaż nierekurencyjna metoda poradzi sobie z dowolnie dużymi powtórzeniami bez przekraczania limitów stosów wywołań, jest znacznie wolniejsza.

Dlaczego zawracałem sobie głowę dodawaniem kolejnych metod, które nie są w połowie tak sprytne, jak te już opublikowane?

Częściowo dla własnej rozrywki, a częściowo w najprostszy sposób wiem, że istnieje wiele sposobów na skórowanie kota, a w zależności od sytuacji całkiem możliwe, że najwyraźniej najlepsza metoda nie jest idealna.

Stosunkowo szybka i wyrafinowana metoda może w pewnych okolicznościach skutecznie ulec awarii i spaleniu, podczas gdy wolniejsza, prostsza metoda może ostatecznie zakończyć pracę.

Niektóre metody mogą być trochę więcej niż wyczyny i jako takie są podatne na stałe z istnieniem, a inne metody mogą działać pięknie w każdych warunkach, ale są tak skonstruowane, że jeden po prostu nie ma pojęcia jak to działa.

„A co jeśli nie wiem, jak to działa ?!”

Poważnie?

JavaScript ma jedną z największych zalet; jest wysoce tolerancyjny na złe zachowanie i jest tak elastyczny, że pochyla się do tyłu, aby zwrócić wyniki, gdy mogłoby być lepsze dla wszystkich, gdyby pękło!

„Z wielką mocą wiąże się wielka odpowiedzialność” ;-)

Ale co ważniejsze i co ważniejsze, chociaż takie ogólne pytania prowadzą do niesamowitości w postaci sprytnych odpowiedzi, że jeśli nic więcej, poszerzają swoją wiedzę i horyzonty, w końcu zadanie, o które chodzi - praktyczny skrypt, który wykorzystuje wynikową metodę - może wymagać trochę mniej lub trochę sprytniej, niż sugeruje.

Te „idealne” algorytmy są fajne i wszystkie, ale „jeden rozmiar dla wszystkich” rzadko, jeśli w ogóle, będzie lepszy niż na zamówienie.

To kazanie zostało przedstawione dzięki uprzejmości i brakowi zainteresowania. Idź naprzód i koduj!

Po pierwsze, wydaje się, że pytania PO dotyczą zwięzłości - co rozumiem jako „proste i łatwe do odczytania”, podczas gdy większość odpowiedzi wydaje się dotyczyć wydajności - co oczywiście nie jest tym samym, i myślę, że chyba, że ​​zastosuje się jakieś bardzo specyficzne algorytmy do manipulowania dużymi danymi, nie powinny cię martwić, kiedy zaczniesz implementować podstawowe funkcje JavaScript do manipulacji danymi. Zwięzłość jest o wiele ważniejsza.

Po drugie, jak zauważył André Laszlo, String.repeat jest częścią ECMAScript 6 i jest już dostępny w kilku popularnych implementacjach - więc najbardziej zwięzłą implementacją String.repeatjest nie implementowanie go ;-)

Wreszcie, jeśli potrzebujesz obsługiwać hosty, które nie oferują implementacji ECMAScript 6, wypełnienie MDN wspomniane przez André Laszlo nie jest zwięzłe.

Bez zbędnych ceregieli - oto mój zwięzły wypełnienie:

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

Tak, to jest rekurencja. Lubię rekurencje - są proste, a jeśli wykonane poprawnie, łatwo je zrozumieć. Jeśli chodzi o wydajność, jeśli język go obsługuje, mogą być bardzo wydajne, jeśli zostaną poprawnie napisane.

Z moich testów wynika, że ​​ta metoda jest ~ 60% szybsza niż Array.joinpodejście. Chociaż oczywiście nie jest to implementacja rozproszona, jest znacznie prostsza niż obie.

Moja konfiguracja testowa to węzeł v0.10, używając „trybu ścisłego” (myślę, że umożliwia on pewien rodzaj TCO ), wzywając repeat(1000)milion znaków w ciągu 10 znaków.

Jeśli uważasz, że wszystkie te prototypowe definicje, tworzenie tablic i operacje łączenia są przesadzone, po prostu użyj kodu jednej linii tam, gdzie jest to potrzebne. Ciąg S powtarzający się N razy:

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

Użyj funkcji narzędzia Lodash dla Javascript, np. Powtarzania ciągów.

Lodash zapewnia niezłą wydajność i zgodność z ECMAScript.

Bardzo polecam go do tworzenia interfejsu użytkownika i działa również po stronie serwera.

Oto jak powtórzyć ciąg „yo” 2 razy za pomocą Lodash:

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

Rozwiązanie rekurencyjne wykorzystujące dzielenie i podbijanie

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); }
}

Przybyłem tu losowo i nigdy wcześniej nie miałem powodu, aby powtarzać znak w javascript.

Byłem pod wrażeniem sposobu, w jaki artistoex to zrobił, i rezultatów rozproszonych. Zauważyłem, że ostatni konkord struny był niepotrzebny, jak zauważył Dennis.

Zauważyłem jeszcze kilka rzeczy podczas zabawy z rozproszonym próbkowaniem.

Wyniki różniły się dość często, co sprzyjało ostatniemu biegowi, a podobne algorytmy często podważałyby pozycję. Jedną z rzeczy, które zmieniłem, było użycie generowanego przez JSLitmus licznika jako źródła dla połączeń; ponieważ liczba generowana była różnie dla różnych metod, wstawiłem indeks. To sprawiło, że rzecz była o wiele bardziej niezawodna. Następnie sprawdziłem, czy do funkcji zostały przekazane łańcuchy o różnych rozmiarach. Zapobiegło to niektórym odmianom, które widziałem, gdzie niektóre algorytmy radziły sobie lepiej na pojedynczych znakach lub mniejszych ciągach. Jednak wszystkie 3 najlepsze metody wypadły dobrze, niezależnie od wielkości łańcucha.

Zestaw testowy rozwidlony

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();

Następnie załączyłem poprawkę Dennisa i zdecydowałem, czy mogę znaleźć sposób, aby trochę więcej wypróbować.

Ponieważ JavaScript nie może tak naprawdę optymalizować rzeczy, najlepszym sposobem na poprawę wydajności jest ręczne unikanie rzeczy. Gdybym wyjął z pętli pierwsze 4 trywialne wyniki, mogłem uniknąć 2-4 ciągów znaków i zapisać końcowy sklep bezpośrednio do wyniku.

// 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;
}

Spowodowało to średnio 1-2% poprawę w stosunku do poprawki Dennisa. Jednak różne przebiegi i różne przeglądarki wykazują wystarczającą wariancję, aby ten dodatkowy kod prawdopodobnie nie był wart wysiłku w porównaniu z 2 poprzednimi algorytmami.

Wykres

Edycja: Zrobiłem to głównie pod chromem. Firefox i IE często faworyzują Dennisa o kilka%.

Prosta metoda:

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

Ludzie komplikują to w absurdalny sposób lub marnują wydajność. Tablice? Rekurencja? Chyba sobie żartujesz.

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

Edytować. Przeprowadziłem kilka prostych testów w celu porównania z wersją bitową opublikowaną przez artistoex / disfated i grupę innych osób. Ten ostatni był tylko nieznacznie szybszy, ale rzędy wielkości bardziej wydajne pod względem pamięci. W przypadku 1000000 powtórzeń słowa „bla” proces Node wzrósł do 46 megabajtów za pomocą prostego algorytmu konkatenacji (powyżej), ale tylko 5,5 megabajtów za pomocą algorytmu logarytmicznego. To drugie jest zdecydowanie właściwą drogą. Przesłanie go dla zachowania jasności:

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

Łączenie ciągów znaków na podstawie liczby.

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));

Mam nadzieję, że to pomaga!

Z ES8 możesz również użyć padStartlub padEnddo tego. na przykład.

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