Gjenta streng - Javascript
Hva er den beste eller mest konsise metoden for å returnere en streng gjentatt et vilkårlig antall ganger?
Følgende er mitt beste forsøk så langt:
function repeat(s, n){
var a = [];
while(a.length < n){
a.push(s);
}
return a.join('');
}
Svar #1
Merk til nye lesere: Dette svaret er gammelt og ikke særlig praktisk - det er bare "smekt" fordi det bruker Array-greier for å få gjort String-greier. Når jeg skrev "mindre prosess" mente jeg definitivt "mindre kode" fordi, som andre har påpekt i etterfølgende svar, så yter det som en gris. Så ikke bruk det hvis hastighet betyr noe for deg.
Jeg ville lagt denne funksjonen direkte på String-objektet. I stedet for å lage et array, fylle det og så slå det sammen med en tom tegn, bare lag et array av riktig lengde, og slå det sammen med ønsket streng. Samme resultat, mindre prosess!
String.prototype.repeat = function( num )
{
return new Array( num + 1 ).join( this );
}
alert( "string to repeat\n".repeat( 4 ) );
Svar #2
Jeg har testet ytelsen til alle de foreslåtte tilnærmingene.
Her er den raskeste varianten jeg har.
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;
};
Eller som en frittstående funksjon:
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;
}
Det er basert på wnrphs algoritme. Det er veldig raskt. Og jo større count, desto raskere går det sammenlignet med den tradisjonelle new Array(count + 1).join(string)-metoden.
Jeg har bare endret 2 ting:
- erstattet
pattern=thismedpattern=this.valueOf()(rydder opp i en åpenbar typekonvertering); - la til
if (count < 1)sjekk fra prototypejs øverst i funksjonen for å utelate unødvendige handlinger i det tilfellet. - påført optimalisering fra Dennis svar (5-7 % hastighetsøkning)
OPP
Lagde en liten ytelsestesting-lekeplass her for de som er interesserte.
variabel count ~ 0 .. 100:
konstant count=1024:
Bruk det og gjør det enda raskere hvis du kan :)
Svar #3
Dette problemet er et kjent/«klassisk» optimaliseringsproblem for JavaScript, forårsaket av at JavaScript-strenger er «immutable», og at tillegg ved sammenkobling av selv ett enkelt tegn til en streng krever opprettelse av, inkludert minnetildeling for og kopiering til, en helt ny streng.
Dessverre er det aksepterte svaret på denne siden feil, der "feil" betyr med en ytelsesfaktor på 3x for enkle én-tegns strenger, og 8x-97x for korte strenger gjentatt flere ganger, opptil 300x for gjentakende setninger, og uendelig galt når man tar grensen for forholdet mellom kompleksiteten til algoritmene når n går mot uendelig. I tillegg finnes det et annet svar på denne siden som er nesten riktig (basert på en av de mange generasjonene og variasjonene av den korrekte løsningen som har sirkulert på Internett de siste 13 årene). Denne "nesten riktige" løsningen mangler imidlertid et nøkkelpunkter ved den korrekte algoritmen, noe som forårsaker en ytelsesreduksjon på 50 %.
JS-ytelsesresultater for det aksepterte svaret, det best presterende andre svaret (basert på en forverret versjon av den opprinnelige algoritmen i dette svaret), og dette svaret ved bruk av min algoritme laget for 13 år siden
~ Oktober 2000 publiserte jeg en algoritme for dette eksakte problemet som ble bredt tilpasset, modifisert, og til slutt dårlig forstått og glemt. For å bøte på dette problemet publiserte jeg i august 2008 en artikkel http://www.webreference.com/programming/javascript/jkm3/3.html som forklarte algoritmen og brukte den som et eksempel på enkle generelle JavaScript-optimaliseringer. Nå har Web Reference fjernet mine kontaktopplysninger og til og med mitt navn fra denne artikkelen. Og igjen har algoritmen blitt bredt tilpasset, modifisert, deretter dårlig forstått og stort sett glemt.
Opprinnelig strengrepetisjon/-multiplikasjonsalgoritme i JavaScript av Joseph Myers, omtrent år 2000, som en tekstmultipliseringsfunksjon i Text.js; publisert august 2008 i denne formen av Web Reference: http://www.webreference.com/programming/javascript/jkm3/3.html (Artikkelen brukte funksjonen som et eksempel på JavaScript-optimaliseringer, noe som er det eneste for det merkelige navnet "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;
}
Innen to måneder etter publiseringen av den artikkelen, ble det samme spørsmålet lagt ut på Stack Overflow og gikk under radaren min frem til nå, da det tilsynelatende originale algoritmen for dette problemet nok en gang har blitt glemt. Den beste løsningen som er tilgjengelig på denne Stack Overflow-siden er en modifisert versjon av min løsning, muligens adskilt av flere generasjoner. Dessverre ødela modifikasjonene løsningens optimalitet. Faktisk, ved å endre strukturen på løkken fra min original, utfører den modifiserte løsningen et helt unødvendig ekstra steg med eksponentiell duplisering (og dermed kombinere den største strengen som brukes i det korrekte svaret med seg selv en ekstra gang og deretter forkaste den).
Nedenfor følger en diskusjon om noen JavaScript-optimaliseringer knyttet til alle svarene på dette problemet og til fordel for alle.
Teknikk: Unngå referanser til objekter eller objekt-egenskaper
For å illustrere hvordan denne teknikken fungerer, bruker vi en JavaScript-funksjon fra virkelig liv som lager strenger i hvilken som helst lengde som trengs. Og som vi skal se, kan flere optimaliseringer legges til!
En funksjon som den som brukes her, er å lage fyll for å justere tekstkolonner, for formatering av penger, eller for å fylle blokkdata opp til grensen. En tekstgenereringsfunksjon tillater også variabel lengde på input for å teste enhver annen funksjon som opererer på tekst. Denne funksjonen er en av de viktige komponentene i JavaScript-tekstbehandlingsmodulen.
Når vi går videre, vil vi dekke to til av de viktigste optimaliseringsteknikkene mens vi utvikler den originale koden til en optimalisert algoritme for å lage strenger. Det endelige resultatet er en industristyrke, høyytelsesfunksjon som jeg har brukt overalt - for å justere varepriser og totalsummer i JavaScript-bestillingsskjemaer, dataformatering og e-post-/tekstmeldingformatering og mange andre bruksområder.
Opprinnelig kode for å lage strenger stringFill1()
function stringFill1(x, n) {
var s = '';
while (s.length < n) s += x;
return s;
}
/* Example of output: stringFill1('x', 3) == 'xxx' */
Syntaksen her er klar. Som du kan se, har vi allerede brukt lokale funksjonsvariabler, før vi går videre til flere optimaliseringer.
Vær oppmerksom på at det finnes en uskyldig referanse til en objekt-egenskap s.length i koden som skader ytelsen. Enda verre, bruken av denne objektegenskapen reduserer enkelheten i programmet ved å anta at leseren kjenner til egenskapene til JavaScript-strengobjekter.
Bruken av denne objekt-egenskapen ødelegger generellheten til dataprogrammet. Programmet antar at x må være en streng med lengde én. Dette begrenser bruken av stringFill1()-funksjonen til alt annet enn repetisjon av enkelttegn. Selv enkelttegn kan ikke brukes hvis de inneholder flere byte, som HTML-entiteten .
Det verste problemet som oppstår på grunn av denne unødvendige bruken av en objekt-egenskap er at funksjonen skaper en uendelig løkke dersom den testes på en tom input-streng x. For å sjekke generell gyldighet, anvend et program på den minste mulige mengden input. Et program som krasjer når det blir bedt om å overskride mengden tilgjengelig minne har en unnskyldning. Et program som dette, som krasjer når det blir bedt om å produsere ingenting, er uakseptabelt. Noen ganger er pen kode giftig kode.
Enkelhet kan være et tvetydig mål i dataprogrammering, men generelt er det ikke det. Når et program mangler et rimelig nivå av generalitet, er det ikke gyldig å si: «Programmet er godt nok så langt det går.» Som du kan se, hindrer bruken av string.length-egenskapen at dette programmet fungerer i en generell setting, og faktisk er det feilaktige programmet klart til å forårsake en nettleser- eller systemkrasj.
Finnes det en måte å forbedre ytelsen til dette JavaScriptet på, samt ta hånd om disse to alvorlige problemene?
Selvfølgelig. Bruk bare heltall.
Optimalisert kode for å lage strenger stringFill2()
function stringFill2(x, n) {
var s = '';
while (n-- > 0) s += x;
return s;
}
Tidtakingskode for å sammenligne stringFill1() og 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);
Suksessen så langt med stringFill2()
stringFill1() tar 47,297 mikrosekunder (milliondels sekund) for å fylle en 100-byt streng, og stringFill2() tar 27,68 mikrosekunder for å gjøre det samme. Det er nesten en dobling i ytelse ved å unngå en referanse til en objekt-eiendom.
Teknikk: Unngå å legge til korte strenger til lange strenger
Vårt forrige resultat så bra ut—veldig bra, faktisk. Den forbedrede funksjonen stringFill2() er mye raskere takket være bruken av våre to første optimaliseringer. Ville du tro det hvis jeg sa at den kan forbedres til å bli mange ganger raskere enn den er nå?
Ja, vi kan oppnå det målet. Akkurat nå må vi forklare hvordan vi unngår å legge korte strenger til lange strenger.
Korttidsatferden ser ut til å være ganske god, sammenlignet med vår opprinnelige funksjon. Datavitere liker å analysere «asymptotisk atferd» av en funksjon eller dataprogramalgoritme, som betyr å studere dens langtidsholdbare atferd ved å teste den med større input. Noen ganger, uten å gjøre flere tester, blir man aldri klar over måter et dataprogram kan forbedres på. For å se hva som vil skje, skal vi lage en 200-byte streng.
Problemet som dukker opp med stringFill2()
Ved å bruke vår tidsfunksjon finner vi at tiden øker til 62,54 mikrosekunder for en 200-byte streng, sammenlignet med 27,68 for en 100-byte streng. Det virker som om tiden burde dobles for å gjøre dobbelt så mye arbeid, men i stedet tredobles eller firedobles den. Fra programmeringserfaring virker dette resultatet rart, fordi funksjonen om noe burde være litt raskere siden arbeidet blir gjort mer effektivt (200 byte per funksjonskall i stedet for 100 byte per funksjonskall). Dette problemet har å gjøre med en slu egenskap ved JavaScript-strenger: JavaScript-strenger er «immuterbare».
Immutable betyr at du ikke kan endre en streng når den er opprettet. Ved å legge til én byte om gangen, bruker vi ikke opp en byte ekstra innsats. Vi gjenskaper faktisk hele strengen pluss én byte til.
I praksis, for å legge til én byte til en 100-bytes streng, krever det 101 bytes med arbeid. La oss kort analysere beregningskostnaden for å lage en streng på N bytes. Kostnaden for å legge til den første byten er 1 enhet av beregningsinnsats. Kostnaden for å legge til den andre byten er ikke én enhet, men 2 enheter (kopiering av den første byten til et nytt strengobjekt samt å legge til den andre byten). Den tredje byten krever en kostnad på 3 enheter, osv.
C(N)=1 + 2 + 3 + ... + N=N(N+1)/2=O(N^2). Symbolet O(N^2) uttales Big O av N kvadrat, og det betyr at beregningskostnaden på lang sikt er proporsjonal med kvadratet av strengens lengde. Å lage 100 tegn krever 10.000 enheter arbeid, og å lage 200 tegn krever 40.000 enheter arbeid.
Dette er grunnen til at det tok mer enn dobbelt så lang tid å lage 200 tegn som 100 tegn. Faktisk burde det ha tatt fire ganger så lang tid. Vår programmeringserfaring var korrekt i at arbeidet blir gjort litt mer effektivt for lengre strenger, og derfor tok det bare omtrent tre ganger så lang tid. Når overheaden ved funksjonskallet blir ubetydelig for hvor lang streng vi lager, vil det faktisk ta fire ganger så lang tid å lage en streng dobbelt så lang.
(Historisk merknad: Denne analysen gjelder ikke nødvendigvis for strenger i kildekode, slik som html='abcd\n' + 'efgh\n' + ... + 'xyz.\n', siden JavaScript-kildekodekompilatoren kan slå sammen strengene før de gjøres om til et JavaScript-strengobjekt. For bare noen år siden ville KJS-implementeringen av JavaScript fryse eller krasje når den lastet lange strenger av kildekode koblet sammen med pluss-tegn. Siden beregningstiden var O(N^2), var det ikke vanskelig å lage nettsider som overbelastet Konqueror-nettleseren eller Safari, som brukte KJS JavaScript-motoren. Jeg støtte først på dette problemet da jeg utviklet et markeringsspråk og en JavaScript-markeringsspråkparser, og deretter oppdaget jeg hva som forårsaket problemet da jeg skrev mitt script for JavaScript Includes.)
Klart er denne raske nedgangen i ytelse et stort problem. Hvordan kan vi håndtere det, gitt at vi ikke kan endre JavaScripts måte å håndtere strenger som uforanderlige objekter på? Løsningen er å bruke en algoritme som gjenskaper strengen så få ganger som mulig.
For å klargjøre, vårt mål er å unngå å legge korte strenger til lange strenger, siden hele den lange strengen også må dupliseres for å kunne legge til den korte strengen.
Hvordan algoritmen fungerer for å unngå å legge til korte strenger til lange strenger
Her er en god måte å redusere antallet ganger nye strengobjekter opprettes på. Koble sammen lengre strenger slik at mer enn én byte om gangen legges til i outputen.
For eksempel, for å lage en streng med lengde 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 */
Å gjøre dette krevde å lage en streng på lengde 1, lage en streng på lengde 2, lage en streng på lengde 4, lage en streng på lengde 8, og til slutt lage en streng på lengde 9. Hvor mye kostnad har vi spart?
Gammel kostnad C(9)=1 + 2 + 3 + 4 + 5 + 6 + 7 + 9=45.
Ny kostnad C(9)=1 + 2 + 4 + 8 + 9=24.
Merk at vi måtte legge til en streng på 1 tegn til en streng på 0 tegn, deretter en streng på 1 tegn til en streng på 1 tegn, deretter en streng på 2 tegn til en streng på 2 tegn, deretter en streng på 4 tegn til en streng på 4 tegn, deretter en streng på 8 tegn til en streng på 1 tegn, for å oppnå en streng på 9 tegn. Det vi gjør kan oppsummeres som å unngå å legge korte strenger til lange strenger, eller med andre ord, å prøve å koble sammen strenger som er av lik eller nesten lik lengde.
For den gamle beregningskostnaden fant vi en formel N(N+1)/2. Finnes det en formel for den nye kostnaden? Ja, men den er komplisert. Det viktige er at den er O(N), og dermed vil en dobling av strengens lengde omtrent doble arbeidsmengden i stedet for å firedoble den.
Koden som implementerer denne nye ideen er nesten like komplisert som formelen for beregningskostnaden. Når du leser den, husk at >>= 1 betyr å skifte til høyre med 1 byte. Så hvis n=10011 er et binært tall, vil n >>= 1 resultere i verdien n=1001.
Den andre delen av koden du kanskje ikke gjenkjenner er bitvise og-operatoren, skrevet &. Uttrykket n & 1 evalueres til sant hvis den siste binære sifren av n er 1, og usant hvis den siste binære sifren av n er 0.
Ny svært effektiv stringFill3()-funksjon
function stringFill3(x, n) {
var s = '';
for (;;) {
if (n & 1) s += x;
n >>= 1;
if (n) x += x;
else break;
}
return s;
}
Det ser stygt ut for det utrente øyet, men ytelsen er intet mindre enn vakker.
La oss se hvor godt denne funksjonen fungerer. Etter å ha sett resultatene, er det sannsynlig at du aldri vil glemme forskjellen mellom en O(N^2) algoritme og en O(N) algoritme.
stringFill1() tar 88,7 mikrosekunder (milliondeler av et sekund) å lage en 200-bytters streng, stringFill2() tar 62,54, og stringFill3() tar bare 4,608. Hva gjorde denne algoritmen så mye bedre? Alle funksjonene utnyttet bruk av lokale funksjonsvariabler, men å dra nytte av den andre og tredje optimaliseringsteknikken ga en tjue ganger bedre ytelse for stringFill3().
Dypere analyse
Hva får denne spesielle funksjonen til å slå konkurrentene fullstendig?
Som jeg har nevnt, grunnen til at begge disse funksjonene, stringFill1() og stringFill2(), kjører så sakte er at JavaScript-strenger er uforanderlige. Minne kan ikke omfordeles for å tillate at ett byte om gangen legges til strengdataene lagret av JavaScript. Hver gang ett byte legges til på slutten av strengen, genereres hele strengen på nytt fra begynnelse til slutt.
Dermed, for å forbedre skriptets ytelse, må man forhåndsberegne lengre strenger ved å sammenkoble to strenger på forhånd, og deretter bygge opp ønsket strenglengde rekursivt.
For eksempel, for å lage en 16-bokstavers byte-streng, ville først en to-byte streng bli forhåndsberegnet. Deretter ville den to-byte strengen bli gjenbrukt for å forhåndsberegne en fire-byte streng. Deretter ville den fire-byte strengen bli gjenbrukt for å forhåndsberegne en åtte-byte streng. Til slutt ville to åtte-byte strenger bli gjenbrukt for å lage den ønskede nye strengen på 16 byte. Totalt måtte fire nye strenger opprettes, én med lengde 2, én med lengde 4, én med lengde 8 og én med lengde 16. Den totale kostnaden er 2 + 4 + 8 + 16=30.
På lang sikt kan denne effektiviteten beregnes ved å legge til i omvendt rekkefølge og bruke en geometrisk rekke som starter med første ledd a1=N og har en felles forhold r=1/2. Summen av en geometrisk rekke er gitt ved a_1/(1-r)=2N.
Dette er mer effektivt enn å legge til ett tegn for å lage en ny streng med lengde 2, lage en ny streng med lengde 3, 4, 5, og så videre, helt til 16. Den forrige algoritmen brukte den prosessen med å legge til en enkelt byte om gangen, og den totale kostnaden for dette ville være n (n + 1)/2=16 (17)/2=8 (17)=136.
Åpenbart er 136 et mye større tall enn 30, og derfor tar den forrige algoritmen mye, mye mer tid å bygge opp en streng.
For å sammenligne de to metodene kan du se hvor mye raskere den rekursive algoritmen (også kalt "del og hersk") er på en streng av lengde 123 457. På min FreeBSD-datamaskin skaper denne algoritmen, implementert i stringFill3()-funksjonen, strengen på 0,001058 sekunder, mens den originale stringFill1()-funksjonen skaper strengen på 0,0808 sekunder. Den nye funksjonen er 76 ganger raskere.
Forskjellen i ytelse øker ettersom lengden på strengen blir større. I grensen, når større og større strenger blir opprettet, oppfører den opprinnelige funksjonen seg omtrent som C1 (konstant) ganger N^2, og den nye funksjonen oppfører seg som C2 (konstant) ganger N.
Fra vårt eksperiment kan vi fastslå verdien av C1 til å være C1=0.0808/(123457)2=.00000000000530126997, og verdien av C2 til å være C2=0.001058/123457=.00000000856978543136. På 10 sekunder kunne den nye funksjonen lage en streng som inneholder 1.166.890.359 tegn. For å lage denne samme strengen, ville den gamle funksjonen trengt 7.218.384 sekunder.
Dette er nesten tre måneder sammenlignet med ti sekunder!
Jeg svarer bare (flere år for sent) fordi min opprinnelige løsning på dette problemet har sirkulert på Internett i mer enn 10 år, og tilsynelatende fortsatt er dårlig forstått av de få som husker det. Jeg tenkte at ved å skrive en artikkel om det her, ville jeg hjelpe:
Ytelsesoptimaliseringer for høyhastighets JavaScript/Side 3
Dessverre er noen av de andre løsningene som presenteres her fortsatt noen av dem som ville ta tre måneder å produsere samme mengde output som en skikkelig løsning skaper på 10 sekunder.
Jeg vil ta meg tid til å gjengi deler av artikkelen her som et kanonisk svar på Stack Overflow.
Merk at den best-presterende algoritmen her tydeligvis er basert på min algoritme og sannsynligvis ble arvet fra en annens 3. eller 4. generasjons tilpasning. Dessverre resulterte modifikasjonene i redusert ytelse. Variasjonen av min løsning som presenteres her forsto kanskje ikke mitt forvirrende for (;;)-uttrykk som ser ut som hovedløkka til en server skrevet i C, og som ganske enkelt var designet for å tillate en nøye plassert break-setning for løkkekontroll, den mest kompakte måten å unngå å eksponentielt replikere strengen én unødvendig gang ekstra.
Svar #4
Gode nyheter! String.prototype.repeat er nå en del av JavaScript.
"yo".repeat(2);
// returns: "yoyo"
Metoden støttes av alle store nettlesere, bortsett fra Internet Explorer. For en oppdatert liste, se MDN: String.prototype.repeat > Nettleserkompatibilitet.
MDN har en polyfill for nettlesere uten støtte.
Svar #5
Denne er ganske effektiv
String.prototype.repeat = function(times){
var result="";
var pattern=this;
while (times > 0) {
if (times&1)
result+=pattern;
times>>=1;
pattern+=pattern;
}
return result;
};
Svar #6
String.prototype.repeat er nå ES6-standard.
'abc'.repeat(3); //abcabcabc
Svar #7
Utvidelse av P.Baileys løsning:
String.prototype.repeat = function(num) {
return new Array(isNaN(num)? 1 : ++num).join(this);
}
På denne måten bør du være trygg mot uventede argumenttyper:
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
REDIGER: Kreditt til jerone for hans elegante ++num-idé!
Svar #8
Bruk Array(N+1).join("string_to_repeat")