Repetir cadena - Javascript [duplicado]
¿Cuál es el método mejor o más conciso para devolver una cadena repetida una cantidad arbitraria de veces?
La siguiente es mi mejor oportunidad hasta ahora:
function repeat(s, n){
var a = [];
while(a.length < n){
a.push(s);
}
return a.join('');
}
Nota para los nuevos lectores: esta respuesta es antigua y no muy práctica; es simplemente "inteligente" porque utiliza elementos de Array para realizar las tareas de String. Cuando escribí "menos proceso" definitivamente quise decir "menos código" porque, como otros han señalado en respuestas posteriores, funciona como un cerdo. Así que no lo uses si la velocidad te importa.
Pondría esta función directamente en el objeto String. En lugar de crear una matriz, llenarla y unirla con un carácter vacío, simplemente cree una matriz de la longitud adecuada y únala con la cadena deseada. ¡Mismo resultado, menos proceso!
String.prototype.repeat = function( num )
{
return new Array( num + 1 ).join( this );
}
alert( "string to repeat\n".repeat( 4 ) );
He probado el rendimiento de todos los enfoques propuestos.
Aquí está la variante más rápida que tengo.
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;
};
O como función independiente :
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;
}
Está basado en el algoritmo de wnrph . Es realmente rápido. Y cuanto más grande es count, más rápido va en comparación con el new Array(count + 1).join(string)enfoque tradicional.
Sólo he cambiado 2 cosas:
- reemplazado
pattern = thisconpattern = this.valueOf()(borra una conversión de tipo obvia); - Se agregó
if (count < 1)una verificación de prototipojs en la parte superior de la función para excluir acciones innecesarias en ese caso. - optimización aplicada de la respuesta de Dennis (5-7% de aceleración)
UPD
Creé aquí un pequeño patio de juegos para pruebas de rendimiento para aquellos interesados.
variables count~ 0 .. 100:
constante count= 1024:
Úsalo y hazlo aún más rápido si puedes :)
Este problema es un problema de optimización bien conocido/"clásico" para JavaScript, causado por el hecho de que las cadenas de JavaScript son "inmutables" y la adición mediante concatenación de incluso un solo carácter a una cadena requiere la creación, incluida la asignación de memoria y la copia. , una cadena completamente nueva.
Desafortunadamente, la respuesta aceptada en esta página es incorrecta, donde "incorrecto" significa un factor de rendimiento de 3x para cadenas simples de un carácter y de 8x-97x para cadenas cortas repetidas más veces, a 300x para oraciones repetidas e infinitamente incorrecto cuando tomando el límite de los ratios de complejidad de los algoritmos hasta nel infinito. Además, hay otra respuesta en esta página que es casi correcta (basada en una de las muchas generaciones y variaciones de la solución correcta que circulan por Internet en los últimos 13 años). Sin embargo, esta solución "casi correcta" pasa por alto un punto clave del algoritmo correcto, lo que provoca una degradación del rendimiento del 50 %.
Resultados de rendimiento de JS para la respuesta aceptada, la otra respuesta de mejor rendimiento (basada en una versión degradada del algoritmo original en esta respuesta) y esta respuesta usando mi algoritmo creado hace 13 años
~ Octubre de 2000 Publiqué un algoritmo para este problema exacto que fue ampliamente adaptado, modificado y finalmente mal comprendido y olvidado. Para remediar este problema, en agosto de 2008 publiqué un artículo http://www.webreference.com/programming/javascript/jkm3/3.html explicando el algoritmo y usándolo como ejemplo de optimizaciones simples de JavaScript de propósito general. Hasta ahora, Web Reference ha eliminado mi información de contacto e incluso mi nombre de este artículo. Y una vez más, el algoritmo ha sido ampliamente adaptado, modificado, luego mal comprendido y en gran medida olvidado.
Algoritmo JavaScript de repetición/multiplicación de cadenas original de Joseph Myers, alrededor del año 2000 como función de multiplicación de texto dentro de Text.js; publicado en agosto de 2008 en este formulario por Web Reference: http://www.webreference.com/programming/javascript/jkm3/3.html (El artículo utilizó la función como ejemplo de optimizaciones de JavaScript, que es la única para las extrañas nombre "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;
}
Dos meses después de la publicación de ese artículo, esta misma pregunta se publicó en Stack Overflow y pasó desapercibida hasta ahora, cuando aparentemente el algoritmo original para este problema ha sido olvidado una vez más. La mejor solución disponible en esta página de Stack Overflow es una versión modificada de mi solución, posiblemente separada por varias generaciones. Desafortunadamente, las modificaciones arruinaron la optimización de la solución. De hecho, al cambiar la estructura del bucle con respecto a mi original, la solución modificada realiza un paso adicional completamente innecesario de duplicación exponencial (uniendo así la cadena más grande utilizada en la respuesta adecuada consigo misma una vez más y luego descartándola).
A continuación sigue una discusión de algunas optimizaciones de JavaScript relacionadas con todas las respuestas a este problema y para el beneficio de todos.
Técnica: evitar referencias a objetos o propiedades de objetos.
Para ilustrar cómo funciona esta técnica, utilizamos una función de JavaScript de la vida real que crea cadenas de cualquier longitud que sea necesaria. Y como veremos, ¡se pueden agregar más optimizaciones!
Una función como la que se usa aquí es crear relleno para alinear columnas de texto, para formatear dinero o para llenar datos de bloques hasta el límite. Una función de generación de texto también permite la entrada de longitud variable para probar cualquier otra función que opere con texto. Esta función es uno de los componentes importantes del módulo de procesamiento de texto JavaScript.
A medida que avancemos, cubriremos dos de las técnicas de optimización más importantes mientras desarrollamos el código original en un algoritmo optimizado para crear cadenas. El resultado final es una función industrial de alto rendimiento que he usado en todas partes: alinear precios y totales de artículos en formularios de pedido de JavaScript, formatear datos y formatear correos electrónicos/mensajes de texto y muchos otros usos.
Código original para crear cadenas.stringFill1()
function stringFill1(x, n) {
var s = '';
while (s.length < n) s += x;
return s;
}
/* Example of output: stringFill1('x', 3) == 'xxx' */
La sintaxis aquí es clara. Como puede ver, ya hemos utilizado variables de funciones locales, antes de continuar con más optimizaciones.
Tenga en cuenta que hay una referencia inocente a una propiedad de objeto s.lengthen el código que perjudica su rendimiento. Peor aún, el uso de esta propiedad de objeto reduce la simplicidad del programa al suponer que el lector conoce las propiedades de los objetos de cadena de JavaScript.
El uso de esta propiedad del objeto destruye la generalidad del programa informático. El programa supone que xdebe ser una cadena de longitud uno. Esto limita la aplicación de la stringFill1()función a cualquier cosa excepto a la repetición de caracteres individuales. Ni siquiera se pueden utilizar caracteres individuales si contienen varios bytes, como la entidad HTML .
El peor problema causado por este uso innecesario de una propiedad de objeto es que la función crea un bucle infinito si se prueba en una cadena de entrada vacía x. Para comprobar la generalidad, aplique un programa a la menor cantidad posible de entrada. Un programa que falla cuando se le pide que exceda la cantidad de memoria disponible tiene una excusa. Un programa como este que falla cuando se le pide que no produzca nada es inaceptable. A veces, un código bonito es un código venenoso.
La simplicidad puede ser un objetivo ambiguo de la programación informática, pero en general no lo es. Cuando un programa carece de un nivel razonable de generalidad, no es válido decir: "El programa es suficientemente bueno hasta donde llega". Como puede ver, el uso de la string.lengthpropiedad impide que este programa funcione en una configuración general y, de hecho, el programa incorrecto está listo para provocar un bloqueo del navegador o del sistema.
¿Hay alguna manera de mejorar el rendimiento de este JavaScript y solucionar estos dos problemas graves?
Por supuesto. Solo usa números enteros.
Código optimizado para crear cadenas.stringFill2()
function stringFill2(x, n) {
var s = '';
while (n-- > 0) s += x;
return s;
}
Código de tiempo para comparar stringFill1()ystringFill2()
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);
El éxito hasta ahora destringFill2()
stringFill1()Se necesitan 47,297 microsegundos (millonésimas de segundo) para llenar una cadena de 100 bytes y stringFill2()se necesitan 27,68 microsegundos para hacer lo mismo. Eso es casi duplicar el rendimiento al evitar una referencia a una propiedad de objeto.
Técnica: evite agregar cadenas cortas a cadenas largas
Nuestro resultado anterior parecía bueno; de hecho, muy bueno. La función mejorada stringFill2()es mucho más rápida debido al uso de nuestras dos primeras optimizaciones. ¿Lo creerías si te dijera que se puede mejorar para que sea muchas veces más rápido de lo que es ahora?
Sí, podemos lograr ese objetivo. Ahora necesitamos explicar cómo evitamos agregar cadenas cortas a cadenas largas.
El comportamiento a corto plazo parece bastante bueno en comparación con nuestra función original. A los informáticos les gusta analizar el "comportamiento asintótico" de una función o algoritmo de programa de computadora, lo que significa estudiar su comportamiento a largo plazo probándolo con entradas más grandes. A veces, sin realizar más pruebas, uno nunca se da cuenta de las formas en que se podría mejorar un programa de computadora. Para ver qué sucede, crearemos una cadena de 200 bytes.
El problema que se presenta constringFill2()
Usando nuestra función de temporización, encontramos que el tiempo aumenta a 62,54 microsegundos para una cadena de 200 bytes, en comparación con 27,68 para una cadena de 100 bytes. Parece que el tiempo debería duplicarse para hacer el doble de trabajo, pero en cambio se triplica o cuadriplica. Desde la experiencia de programación, este resultado parece extraño, porque en todo caso, la función debería ser un poco más rápida ya que el trabajo se realiza de manera más eficiente (200 bytes por llamada de función en lugar de 100 bytes por llamada de función). Este problema tiene que ver con una propiedad insidiosa de las cadenas de JavaScript: las cadenas de JavaScript son "inmutables".
Inmutable significa que no se puede cambiar una cadena una vez creada. Al agregar un byte a la vez, no estamos gastando ni un byte más de esfuerzo. De hecho, estamos recreando la cadena completa más un byte más.
De hecho, para agregar un byte más a una cadena de 100 bytes, se necesitan 101 bytes de trabajo. Analicemos brevemente el costo computacional de crear una cadena de Nbytes. El costo de agregar el primer byte es 1 unidad de esfuerzo computacional. El costo de agregar el segundo byte no es una unidad sino 2 unidades (copiar el primer byte a un nuevo objeto de cadena y agregar el segundo byte). El tercer byte requiere un costo de 3 unidades, etc.
C(N) = 1 + 2 + 3 + ... + N = N(N+1)/2 = O(N^2). El símbolo O(N^2)se pronuncia Gran O de N al cuadrado y significa que el costo computacional a largo plazo es proporcional al cuadrado de la longitud de la cadena. Para crear 100 caracteres se necesitan 10.000 unidades de trabajo y para crear 200 caracteres se necesitan 40.000 unidades de trabajo.
Es por eso que tomó más del doble de tiempo crear 200 caracteres que 100 caracteres. De hecho, debería haber tardado cuatro veces más. Nuestra experiencia en programación fue correcta en el sentido de que el trabajo se realiza de manera ligeramente más eficiente para cadenas más largas y, por lo tanto, solo tomó aproximadamente tres veces más tiempo. Una vez que la sobrecarga de la llamada a la función se vuelve insignificante en cuanto a la longitud de una cadena que estamos creando, en realidad tomará cuatro veces más tiempo crear una cadena dos veces más larga.
(Nota histórica: este análisis no se aplica necesariamente a cadenas en el código fuente, como html = 'abcd\n' + 'efgh\n' + ... + 'xyz.\n', ya que el compilador del código fuente de JavaScript puede unir las cadenas antes de convertirlas en un objeto de cadena de JavaScript. Hace apenas unos años, la implementación KJS de JavaScript se congelaba o fallaba al cargar largas cadenas de código fuente unidas por signos más. Desde la época computacional, O(N^2)no era difícil crear páginas web que sobrecargaran el navegador web Konqueror o Safari, que usaba el núcleo del motor JavaScript KJS. Encontré este problema cuando estaba desarrollando un lenguaje de marcado y un analizador de lenguaje de marcado JavaScript, y luego descubrí la causa del problema cuando escribí mi script para JavaScript Incluye.)
Es evidente que esta rápida degradación del rendimiento es un gran problema. ¿Cómo podemos lidiar con esto, dado que no podemos cambiar la forma en que JavaScript maneja las cadenas como objetos inmutables? La solución es utilizar un algoritmo que recree la cadena el menor número de veces posible.
Para aclarar, nuestro objetivo es evitar agregar cadenas cortas a cadenas largas, ya que para agregar la cadena corta, también se debe duplicar toda la cadena larga.
Cómo funciona el algoritmo para evitar agregar cadenas cortas a cadenas largas
Esta es una buena manera de reducir la cantidad de veces que se crean nuevos objetos de cadena. Concatene longitudes más largas de cadena para que se agregue más de un byte a la vez a la salida.
Por ejemplo, para hacer una cadena de longitud 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 */
Hacer esto requirió crear una cadena de longitud 1, crear una cadena de longitud 2, crear una cadena de longitud 4, crear una cadena de longitud 8 y, finalmente, crear una cadena de longitud 9. ¿Cuánto costo hemos ahorrado?
Costo antiguo C(9) = 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 = 45.
Nuevo costo C(9) = 1 + 2 + 4 + 8 + 9 = 24.
Tenga en cuenta que tuvimos que agregar una cadena de longitud 1 a una cadena de longitud 0, luego una cadena de longitud 1 a una cadena de longitud 1, luego una cadena de longitud 2 a una cadena de longitud 2, luego una cadena de longitud 4 a una cadena de longitud 4, luego una cadena de longitud 8 a una cadena de longitud 1, para obtener una cadena de longitud 9. Lo que estamos haciendo se puede resumir en evitar agregar cadenas cortas a cadenas largas, o en otras palabras, tratando de concatenar cadenas que sean de igual o casi igual longitud.
Para el antiguo costo computacional encontramos una fórmula N(N+1)/2. ¿Existe una fórmula para el nuevo costo? Sí, pero es complicado. Lo importante es que lo es O(N), por lo que duplicar la longitud de la cuerda aproximadamente duplicará la cantidad de trabajo en lugar de cuadruplicarla.
El código que implementa esta nueva idea es casi tan complicado como la fórmula del coste computacional. Cuando lo leas, recuerda que eso >>= 1significa desplazarse 1 byte a la derecha. Entonces, si n = 10011es un número binario, el n >>= 1resultado es el valor n = 1001.
La otra parte del código que quizás no reconozca es el operador bit a bit y, escrito &. La expresión n & 1se evalúa como verdadera si el último dígito binario de nes 1 y falsa si el último dígito binario de nes 0.
stringFill3()Nueva función altamente eficiente
function stringFill3(x, n) {
var s = '';
for (;;) {
if (n & 1) s += x;
n >>= 1;
if (n) x += x;
else break;
}
return s;
}
Parece feo para el ojo inexperto, pero su rendimiento es nada menos que encantador.
Veamos qué tan bien funciona esta función. Después de ver los resultados, es probable que nunca olvides la diferencia entre un O(N^2)algoritmo y un O(N)algoritmo.
stringFill1()Se necesitan 88,7 microsegundos (millonésimas de segundo) para crear una cadena de 200 bytes, stringFill2()62,54 y stringFill3()sólo 4,608. ¿Qué hizo que este algoritmo fuera mucho mejor? Todas las funciones aprovecharon el uso de variables de funciones locales, pero aprovechar la segunda y tercera técnicas de optimización agregó una mejora veinte veces mayor al rendimiento de stringFill3().
Análisis más profundo
¿Qué hace que esta función en particular deje a la competencia fuera del agua?
Como mencioné, la razón por la que ambas funciones stringFill1()y stringFill2(), se ejecutan tan lentamente es que las cadenas de JavaScript son inmutables. La memoria no se puede reasignar para permitir que se agregue un byte más a la vez a los datos de cadena almacenados por JavaScript. Cada vez que se agrega un byte más al final de la cadena, la cadena completa se regenera de principio a fin.
Por lo tanto, para mejorar el rendimiento del script, se deben precalcular cadenas de mayor longitud concatenando dos cadenas con anticipación y luego acumulando recursivamente la longitud de cadena deseada.
Por ejemplo, para crear una cadena de bytes de 16 letras, primero se precalcularía una cadena de dos bytes. Luego, la cadena de dos bytes se reutilizaría para precalcular una cadena de cuatro bytes. Luego, la cadena de cuatro bytes se reutilizaría para precalcular una cadena de ocho bytes. Finalmente, se reutilizarían dos cadenas de ocho bytes para crear la nueva cadena deseada de 16 bytes. En total se tuvieron que crear cuatro nuevas cadenas, una de longitud 2, una de longitud 4, una de longitud 8 y una de longitud 16. El coste total es 2 + 4 + 8 + 16 = 30.
A largo plazo, esta eficiencia se puede calcular sumando en orden inverso y utilizando una serie geométrica que comienza con un primer término a1 = N y que tiene una relación común de r = 1/2. La suma de una serie geométrica viene dada por a_1 / (1-r) = 2N.
Esto es más eficiente que agregar un carácter para crear una nueva cadena de longitud 2, crear una nueva cadena de longitud 3, 4, 5, y así sucesivamente, hasta 16. El algoritmo anterior usaba ese proceso de agregar un solo byte a la vez. , y el costo total del mismo sería n (n + 1) / 2 = 16 (17) / 2 = 8 (17) = 136.
Obviamente, 136 es un número mucho mayor que 30, por lo que el algoritmo anterior requiere mucho, mucho más tiempo para construir una cadena.
Para comparar los dos métodos, puede ver cuánto más rápido es el algoritmo recursivo (también llamado "divide y vencerás") en una cadena de longitud 123,457. En mi computadora FreeBSD, este algoritmo, implementado en la stringFill3()función, crea la cadena en 0,001058 segundos, mientras que la stringFill1()función original crea la cadena en 0,0808 segundos. La nueva función es 76 veces más rápida.
La diferencia en el rendimiento crece a medida que aumenta la longitud de la cuerda. En el límite, a medida que se crean cadenas cada vez más grandes, la función original se comporta aproximadamente como C1tiempos (constantes) N^2y la nueva función se comporta como C2tiempos (constantes) N.
A partir de nuestro experimento podemos determinar el valor de C1to be C1 = 0.0808 / (123457)2 = .00000000000530126997y el valor de C2to be C2 = 0.001058 / 123457 = .00000000856978543136. En 10 segundos, la nueva función podría crear una cadena que contenga 1.166.890.359 caracteres. Para crear esta misma cadena, la función anterior necesitaría 7.218.384 segundos de tiempo.
¡Esto son casi tres meses en comparación con diez segundos!
Solo respondo (con varios años de retraso) porque mi solución original a este problema ha estado flotando en Internet durante más de 10 años y aparentemente todavía no la comprenden bien los pocos que la recuerdan. Pensé que escribiendo un artículo al respecto aquí ayudaría:
Optimizaciones de rendimiento para JavaScript de alta velocidad / Página 3
Desafortunadamente, algunas de las otras soluciones presentadas aquí siguen siendo algunas de las que tardarían tres meses en producir la misma cantidad de resultados que una solución adecuada genera en 10 segundos.
Quiero tomarme el tiempo para reproducir parte del artículo aquí como una respuesta canónica sobre Stack Overflow.
Tenga en cuenta que el algoritmo de mejor rendimiento aquí se basa claramente en mi algoritmo y probablemente se heredó de la adaptación de tercera o cuarta generación de otra persona. Desafortunadamente, las modificaciones resultaron en una reducción de su rendimiento. La variación de mi solución presentada aquí tal vez no entendió mi for (;;)expresión confusa que parece el bucle infinito principal de un servidor escrito en C, y que simplemente fue diseñada para permitir una declaración break cuidadosamente posicionada para el control del bucle, la forma más compacta de Evite replicar exponencialmente la cadena una vez más innecesaria.
