Chaîne de répétition - Javascript

Question

Quelle est la méthode la plus efficace ou la plus concise pour renvoyer une chaîne de caractères répétée un nombre arbitraire de fois ?

Ce qui suit est mon meilleur essai jusqu'à présent :

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

Answer 1

Note aux nouveaux lecteurs : Cette réponse est ancienne et n'est pas terriblement pratique - elle est juste "intelligente" parce qu'elle utilise des éléments de tableau pour réaliser des éléments de chaîne. des chaînes de caractères. Quand j'ai écrit "moins de processus", je voulais vraiment dire "moins de code" car, comme d'autres l'ont noté dans des réponses ultérieures, elle fonctionne comme un cochon. Ne l'utilisez donc pas si la vitesse est importante pour vous.

Je mettrais cette fonction directement sur l'objet String. Au lieu de créer un tableau, de le remplir et de le joindre à un caractère vide, il suffit de créer un tableau de la bonne longueur et de le joindre à la chaîne souhaitée. Même résultat, moins de processus !

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

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

Answer 2

J'ai testé les performances de toutes les approches proposées.

Voici la variante la plus rapide Je l'ai.

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

Ou comme autonome fonction :

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

Il est basé sur de wnrph algorithme. Il est très rapide. Et plus le count plus elle est rapide par rapport à la méthode traditionnelle new Array(count + 1).join(string) l'approche.

Je n'ai changé que deux choses :

1. remplacés pattern = this con pattern = this.valueOf() (efface une conversion de type évidente) ;
2. ajouté if (count < 1) chèque de prototypejs au sommet de la fonction afin d'exclure les actions inutiles dans ce cas.
3. l'optimisation appliquée à partir de Dennis répondre (accélération de 5 à 7 %)

UPD

Création d'un petit terrain de jeu pour tester les performances aquí pour ceux qui sont intéressés.

variable count ~ 0 .. 100 :

constante count = 1024 :

Utilisez-le et rendez-le encore plus rapide si vous le pouvez :)

Answer 3

Ce problème est un problème d'optimisation bien connu / "classique" pour JavaScript, dû au fait que les chaînes JavaScript sont "immuables" et que l'ajout par concaténation d'un seul caractère à une chaîne nécessite la création d'une nouvelle chaîne entière, y compris l'allocation de mémoire pour cette chaîne et la copie vers cette dernière.

Malheureusement, la réponse acceptée sur cette page est erronée, où "erronée" signifie un facteur de performance de 3x pour les chaînes simples d'un caractère, et de 8x-97x pour les chaînes courtes répétées plusieurs fois, jusqu'à 300x pour les phrases répétées, et infiniment erronée en prenant la limite des rapports de complexité des algorithmes comme suit n va à l'infini. Il y a également une autre réponse sur cette page qui est presque correcte (basée sur l'une des nombreuses générations et variations de la solution correcte circulant sur l'Internet au cours des 13 dernières années). Toutefois, cette solution "presque correcte" omet un point clé de l'algorithme correct, ce qui entraîne une dégradation de 50 % des performances.

Résultats des performances JS pour la réponse acceptée, l'autre réponse la plus performante (basée sur une version dégradée de l'algorithme original de cette réponse), et cette réponse utilisant mon algorithme créé il y a 13 ans.

~ En octobre 2000, j'ai publié un algorithme pour ce problème précis qui a été largement adapté, modifié, puis finalement mal compris et oublié. Pour remédier à ce problème, j'ai publié en août 2008 un article http://www.webreference.com/programming/javascript/jkm3/3.html expliquant l'algorithme et l'utilisant comme exemple d'optimisations JavaScript simples et générales. A ce jour, Référence web a supprimé mes coordonnées et même mon nom de cet article. Une fois de plus, l'algorithme a été largement adapté, modifié, puis mal compris et largement oublié.

Algorithme JavaScript original de répétition/multiplication de chaînes de caractères par Joseph Myers, vers l'an 2000, comme fonction de multiplication de texte dans Text.js ; publié en août 2008 http://www.webreference.com/programming/javascript/jkm3/3.html (Les a utilisé cette fonction comme exemple d'optimisation de JavaScript, ce qui explique le nom étrange de "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;
}

Deux mois après la publication de cet article, cette même question a été postée sur Stack Overflow et est passée sous mon radar jusqu'à aujourd'hui, où apparemment l'algorithme original pour ce problème a une fois de plus été oublié. La meilleure solution disponible sur cette page de Stack Overflow est une version modifiée de ma solution, peut-être séparée par plusieurs générations. Malheureusement, les modifications ont ruiné l'optimalité de la solution. En fait, en changeant la structure de la boucle par rapport à ma solution originale, la solution modifiée effectue une étape supplémentaire complètement inutile de duplication exponentielle (joignant ainsi la plus grande chaîne de caractères utilisée dans la bonne réponse à elle-même une fois de plus et la jetant ensuite).

Ci-dessous se trouve une discussion sur certaines optimisations JavaScript liées à toutes les réponses à ce problème et pour le bénéfice de tous.

Technique : Éviter les références à des objets ou à des propriétés d'objets

Pour illustrer le fonctionnement de cette technique, nous utilisons une fonction JavaScript réelle qui crée des chaînes de caractères de la longueur souhaitée. Et comme nous le verrons, d'autres optimisations peuvent être ajoutées !

Une fonction comme celle utilisée ici permet de créer un remplissage pour aligner des colonnes de texte, pour formater de l'argent ou pour remplir des blocs de données jusqu'à la limite. Une fonction de génération de texte permet également une entrée de longueur variable pour tester toute autre fonction opérant sur du texte. Cette fonction est l'un des composants importants du module de traitement de texte JavaScript.

Au fur et à mesure que nous avancerons, nous aborderons deux autres des techniques d'optimisation les plus importantes tout en développant le code original en un algorithme optimisé pour la création de chaînes de caractères. Le résultat final est une fonction industrielle très performante que j'ai utilisée partout : alignement des prix et des totaux des articles dans les formulaires de commande JavaScript, formatage des données et formatage des messages électroniques ou textuels, et bien d'autres utilisations encore.

Code original pour la création de chaînes de caractères stringFill1()

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

La syntaxe est ici claire. Comme vous pouvez le voir, nous avons déjà utilisé des variables de fonctions locales, avant de passer à d'autres optimisations.

Sachez qu'il existe une référence innocente à une propriété d'objet s.length dans le code qui nuit à ses performances. Pire encore, l'utilisation de cette propriété d'objet réduit la simplicité du programme en supposant que le lecteur connaît les propriétés des objets de type chaîne JavaScript.

L'utilisation de cette propriété d'objet détruit la généralité du programme informatique. Le programme suppose que x doit être une chaîne de longueur un. Cela limite l'application de la méthode stringFill1() à tout sauf à la répétition de caractères uniques. Même les caractères simples ne peuvent pas être utilisés s'ils contiennent plusieurs octets comme l'entité HTML   .

Le pire problème causé par cette utilisation inutile d'une propriété d'objet est que la fonction crée une boucle infinie si elle est testée sur une chaîne d'entrée vide x . Pour vérifier la généralité, appliquez un programme à la plus petite quantité possible d'entrées. Un programme qui se plante lorsqu'on lui demande de dépasser la quantité de mémoire disponible a une excuse. Un programme comme celui-ci, qui se plante lorsqu'on lui demande de ne rien produire, est inacceptable. Parfois, un joli code est un code toxique.

La simplicité peut être un objectif ambigu de la programmation informatique, mais elle ne l'est généralement pas. Lorsqu'un programme manque d'un niveau raisonnable de généralité, il n'est pas valable de dire : "Le programme est assez bon pour ce qu'il est". Comme vous pouvez le constater, l'utilisation de la fonction string.length empêche ce programme de fonctionner dans un cadre général et, en fait, le programme incorrect est prêt à provoquer un plantage du navigateur ou du système.

Existe-t-il un moyen d'améliorer les performances de ce JavaScript et de remédier à ces deux graves problèmes ?

Bien sûr. Il suffit d'utiliser des nombres entiers.

Code optimisé pour la création de chaînes de caractères stringFill2()

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

Code temporel à comparer stringFill1() y stringFill2()

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

Le succès rencontré jusqu'à présent par l'initiative stringFill2()

stringFill1() met 47,297 microsecondes (millionièmes de seconde) pour remplir une chaîne de 100 octets, et stringFill2() met 27,68 microsecondes pour faire la même chose. Cela représente presque un doublement des performances en évitant une référence à une propriété d'objet.

Technique : Éviter d'ajouter des chaînes courtes à des chaînes longues

Notre résultat précédent semblait bon - très bon, en fait. La fonction améliorée stringFill2() est beaucoup plus rapide grâce à l'utilisation de nos deux premières optimisations. Le croiriez-vous si je vous disais qu'il est possible de l'améliorer pour qu'il soit plusieurs fois plus rapide qu'il ne l'est actuellement ?

Oui, nous pouvons atteindre cet objectif. Pour l'instant, nous devons expliquer comment nous évitons d'ajouter des chaînes courtes à des chaînes longues.

Le comportement à court terme semble être assez bon, en comparaison avec notre fonction originale. Les informaticiens aiment analyser le "comportement asymptotique" d'une fonction ou d'un algorithme de programme informatique, ce qui signifie étudier son comportement à long terme en le testant avec des entrées plus importantes. Parfois, en l'absence de tests supplémentaires, on ne se rend jamais compte des possibilités d'amélioration d'un programme informatique. Pour voir ce qui se passe, nous allons créer une chaîne de 200 octets.

Le problème qui se pose avec stringFill2()

En utilisant notre fonction de synchronisation, nous constatons que le temps passe à 62,54 microsecondes pour une chaîne de 200 octets, contre 27,68 pour une chaîne de 100 octets. Il semble que le temps devrait être doublé pour effectuer deux fois plus de travail, mais au lieu de cela, il est triplé ou quadruplé. D'après notre expérience de la programmation, ce résultat semble étrange, car la fonction devrait être légèrement plus rapide puisque le travail est effectué plus efficacement (200 octets par appel de fonction au lieu de 100 octets par appel de fonction). Ce problème est lié à une propriété insidieuse des chaînes JavaScript : Les chaînes JavaScript sont "immuables".

Immuable signifie que vous ne pouvez pas modifier une chaîne une fois qu'elle a été créée. En ajoutant un octet à la fois, nous n'utilisons pas un octet supplémentaire d'effort. Nous recréons en fait la chaîne entière plus un octet supplémentaire.

En effet, pour ajouter un octet à une chaîne de 100 octets, il faut travailler sur 101 octets. Analysons brièvement le coût de calcul pour la création d'une chaîne de caractères de N des octets. Le coût de l'ajout du premier octet est de 1 unité de calcul. Le coût de l'ajout du deuxième octet n'est pas d'une unité mais de 2 unités (copie du premier octet dans un nouvel objet chaîne de caractères et ajout du deuxième octet). Le troisième octet nécessite un coût de 3 unités, etc.

C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2) . Le symbole O(N^2) se prononce Big O de N au carré, et signifie que le coût de calcul à long terme est proportionnel au carré de la longueur de la chaîne. Pour créer 100 caractères, il faut 10 000 unités de travail, et pour créer 200 caractères, il faut 40 000 unités de travail.

C'est pourquoi il a fallu plus de deux fois plus de temps pour créer 200 caractères que 100 caractères. En fait, cela aurait dû prendre quatre fois plus de temps. Notre expérience en matière de programmation s'est avérée correcte dans la mesure où le travail est effectué de manière légèrement plus efficace pour les chaînes de caractères plus longues, ce qui explique que l'opération n'ait pris que trois fois plus de temps. Une fois que le surcoût de l'appel à la fonction devient négligeable en fonction de la longueur de la chaîne que nous créons, il faudra en fait quatre fois plus de temps pour créer une chaîne deux fois plus longue.

(Note historique : cette analyse ne s'applique pas nécessairement aux chaînes de caractères du code source, telles que html = 'abcd\n' + 'efgh\n' + ... + 'xyz.\n' car le compilateur du code source JavaScript peut joindre les chaînes de caractères avant de les transformer en un objet chaîne de caractères JavaScript. Il y a encore quelques années, l'implémentation KJS de JavaScript se figeait ou se bloquait lors du chargement de longues chaînes de code source reliées par des signes plus. Comme le temps de calcul était de O(N^2) il n'était pas difficile de créer des pages Web qui surchargeaient le navigateur Konqueror ou Safari, qui utilisait le noyau du moteur JavaScript de KJS. J'ai rencontré ce problème pour la première fois lorsque je développais un langage de balisage et un parseur de langage de balisage JavaScript, puis j'ai découvert ce qui causait le problème lorsque j'ai écrit mon script pour JavaScript Includes).

Il est clair que cette dégradation rapide des performances constitue un énorme problème. Comment pouvons-nous y remédier, étant donné que nous ne pouvons pas modifier la façon dont JavaScript traite les chaînes de caractères en tant qu'objets immuables ? La solution consiste à utiliser un algorithme qui recrée la chaîne le moins de fois possible.

Pour clarifier, notre objectif est d'éviter d'ajouter des chaînes courtes à des chaînes longues, puisque pour ajouter la chaîne courte, il faut également dupliquer l'ensemble de la chaîne longue.

Comment l'algorithme fonctionne-t-il pour éviter d'ajouter des chaînes courtes à des chaînes longues ?

Voici un bon moyen de réduire le nombre de fois où de nouveaux objets de type chaîne de caractères sont créés. Concaténer des chaînes de caractères plus longues afin que plus d'un octet à la fois soit ajouté à la sortie.

Par exemple, pour obtenir une chaîne de longueur 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 */

Pour ce faire, il a fallu créer une chaîne de longueur 1, créer une chaîne de longueur 2, créer une chaîne de longueur 4, créer une chaîne de longueur 8 et, enfin, créer une chaîne de longueur 9. Combien de coûts avons-nous économisés ?

Ancien coût C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45 .

Nouveau coût C(9) = 1 + 2 + 4 + 8 + 9 = 24 .

Notez que nous avons dû ajouter une chaîne de longueur 1 à une chaîne de longueur 0, puis une chaîne de longueur 1 à une chaîne de longueur 1, puis une chaîne de longueur 2 à une chaîne de longueur 2, puis une chaîne de longueur 4 à une chaîne de longueur 4, puis une chaîne de longueur 8 à une chaîne de longueur 1, afin d'obtenir une chaîne de longueur 9. Ce que nous faisons peut se résumer à éviter d'ajouter des chaînes courtes à des chaînes longues, ou en d'autres termes, à essayer de concaténer des chaînes ensemble qui sont de longueur égale ou presque égale.

Pour l'ancien coût de calcul, nous avons trouvé une formule N(N+1)/2 . Existe-t-il une formule pour le nouveau coût ? Oui, mais elle est compliquée. L'important est qu'il soit O(N) Ainsi, en doublant la longueur de la corde, on double approximativement la quantité de travail au lieu de la quadrupler.

Le code qui met en œuvre cette nouvelle idée est presque aussi compliqué que la formule du coût de calcul. Lorsque vous le lirez, rappelez-vous que >>= 1 signifie qu'il faut décaler d'un octet vers la droite. Ainsi, si n = 10011 est un nombre binaire, alors n >>= 1 se traduit par la valeur n = 1001 .

L'autre partie du code que vous ne reconnaîtrez peut-être pas est l'opérateur bitwise et, qui s'écrit & . L'expression n & 1 évalue vrai si le dernier chiffre binaire de n est 1, et faux si le dernier chiffre binaire de n est de 0.

Nouveau système à haut rendement stringFill3() fonction

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

Il est laid pour l'œil non averti, mais ses performances ne sont rien moins que charmantes.

Voyons dans quelle mesure cette fonction est efficace. Après avoir vu les résultats, il est probable que vous n'oublierez jamais la différence entre un O(N^2) et un algorithme de O(N) algorithme.

stringFill1() prend 88,7 microsecondes (millionièmes de seconde) pour créer une chaîne de 200 octets, stringFill2() prend 62,54, et stringFill3() ne prend que 4,608. Qu'est-ce qui a rendu cet algorithme tellement meilleur ? Toutes les fonctions ont tiré parti de l'utilisation de variables de fonction locales, mais l'utilisation des deuxième et troisième techniques d'optimisation a permis de multiplier par vingt les performances de stringFill3() .

Une analyse plus approfondie

Qu'est-ce qui fait que cette fonction particulière fait exploser la concurrence ?

Comme je l'ai mentionné, la raison pour laquelle ces deux fonctions, stringFill1() y stringFill2() est que les chaînes JavaScript sont immuables. La mémoire ne peut pas être réaffectée pour permettre l'ajout d'un octet supplémentaire à la fois aux données de la chaîne stockée par JavaScript. Chaque fois qu'un octet supplémentaire est ajouté à la fin de la chaîne, la chaîne entière est régénérée du début à la fin.

Ainsi, pour améliorer les performances du script, il faut précalculer des chaînes plus longues en concaténant deux chaînes à l'avance, puis en construisant récursivement la longueur de chaîne souhaitée.

Par exemple, pour créer une chaîne d'octets de 16 lettres, une chaîne de deux octets est d'abord précalculée. Ensuite, la chaîne de deux octets est réutilisée pour précalculer une chaîne de quatre octets. Ensuite, la chaîne de quatre octets serait réutilisée pour précalculer une chaîne de huit octets. Enfin, deux chaînes de huit octets sont réutilisées pour créer la nouvelle chaîne souhaitée de 16 octets. Au total, quatre nouvelles chaînes ont dû être créées, une de longueur 2, une de longueur 4, une de longueur 8 et une de longueur 16. Le coût total est de 2 + 4 + 8 + 16 = 30.

À long terme, cette efficacité peut être calculée en additionnant dans l'ordre inverse et en utilisant une série géométrique commençant par un premier terme a1 = N et ayant un rapport commun de r = 1/2. La somme d'une série géométrique est donnée par a_1 / (1-r) = 2N .

C'est plus efficace que d'ajouter un caractère pour créer une nouvelle chaîne de longueur 2, puis de créer une nouvelle chaîne de longueur 3, 4, 5, et ainsi de suite jusqu'à 16. L'algorithme précédent utilisait ce processus d'ajout d'un octet à la fois, et le coût total était de n (n + 1) / 2 = 16 (17) / 2 = 8 (17) = 136 .

Évidemment, 136 est un nombre beaucoup plus grand que 30, et l'algorithme précédent prend donc beaucoup, beaucoup plus de temps pour construire une chaîne de caractères.

Pour comparer les deux méthodes, vous pouvez voir combien l'algorithme récursif (également appelé "diviser pour régner") est plus rapide sur une chaîne de longueur 123 457. Sur mon ordinateur FreeBSD, cet algorithme, implémenté dans le programme stringFill3() crée la chaîne de caractères en 0,001058 seconde, alors que la fonction stringFill1() crée la chaîne de caractères en 0,0808 seconde. La nouvelle fonction est 76 fois plus rapide.

La différence de performance s'accroît à mesure que la longueur de la corde augmente. Dans la limite où des chaînes de plus en plus grandes sont créées, la fonction originale se comporte à peu près comme suit C1 temps (constants) N^2 et la nouvelle fonction se comporte comme C2 temps (constants) N .

Notre expérience nous permet de déterminer la valeur de C1 être C1 = 0.0808 / (123457)2 = .00000000000530126997 et la valeur de C2 être C2 = 0.001058 / 123457 = .00000000856978543136 . En 10 secondes, la nouvelle fonction peut créer une chaîne contenant 1 166 890 359 caractères. Pour créer cette même chaîne, l'ancienne fonction aurait eu besoin de 7 218 384 secondes.

C'est presque trois mois contre dix secondes !

Je ne réponds (avec plusieurs années de retard) que parce que ma solution originale à ce problème circule sur Internet depuis plus de 10 ans et qu'elle est apparemment encore mal comprise par les quelques personnes qui s'en souviennent. J'ai pensé qu'en écrivant un article à ce sujet ici, j'aiderais :

Optimisation des performances pour un JavaScript à haute vitesse / Page 3

Malheureusement, certaines des autres solutions présentées ici sont encore des solutions qui prendraient trois mois pour produire la même quantité de résultats qu'une solution appropriée crée en 10 secondes.

Je souhaite prendre le temps de reproduire une partie de l'article ici en tant que réponse canonique sur Stack Overflow.

Notez que l'algorithme le plus performant ici est clairement basé sur mon algorithme et a probablement été hérité de l'adaptation de 3e ou 4e génération de quelqu'un d'autre. Malheureusement, les modifications apportées ont eu pour effet de réduire ses performances. La variante de ma solution présentée ici n'a peut-être pas compris ma confusion. for (;;) qui ressemble à la boucle infinie principale d'un serveur écrit en C, et qui a simplement été conçue pour permettre une instruction break soigneusement positionnée pour le contrôle de la boucle, la manière la plus compacte d'éviter de répliquer exponentiellement la chaîne une fois de plus inutilement.

Answer 4

Bonne nouvelle ! String.prototype.repeat es fait désormais partie de JavaScript .

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

La méthode est prise en charge par tous les principaux navigateurs, à l'exception d'Internet Explorer. Pour une liste actualisée, voir MDN : String.prototype.repeat > Compatibilité avec les navigateurs .

MDN a un polyfill pour les navigateurs non compatibles.

Answer 5

Celui-ci est assez efficace

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