ejemplos - javascript for each

¿Por qué usar un bucle para iterar desde el inicio de la matriz hasta el final es más rápido que iterar tanto de principio a fin y de principio a fin?

Question

Dada una matriz que tiene .length 100 contiene elementos que tienen valores de 0 a 99 en los índices respectivos, donde el requisito es encontrar un elemento de matriz igual a n : 51 .

¿Por qué usar un bucle para iterar desde el inicio de la matriz hasta el final es más rápido que iterar tanto de principio a fin y de principio a fin?

const arr = Array.from({length: 100}, (_, i) => i);
const n = 51;
const len = arr.length;

console.time("iterate from start");
for (let i = 0; i < len; i++) {
  if (arr[i] === n) break;
}
console.timeEnd("iterate from start");

const arr = Array.from({length: 100}, (_, i) => i);
const n = 51;
const len = arr.length;

console.time("iterate from start and end");
for (let i = 0, k = len - 1; i < len && k >= 0; i++, k--) {
  if (arr[i] === n || arr[k] === n) break;
}
console.timeEnd("iterate from start and end");

jsperf https://jsperf.com/iterate-from-start-iterate-from-start-and-end/1

Answer 1

@Bergi tiene razón. Más operaciones es más tiempo. ¿Por qué? Más ciclos de reloj de la CPU. El tiempo es realmente una referencia a la cantidad de ciclos de reloj necesarios para ejecutar el código. Para llegar al meollo de la cuestión, debe consultar el código de nivel de la máquina (como el código de nivel de ensamblaje) para encontrar la evidencia real. Cada ciclo de reloj de la CPU (¿núcleo?) Puede ejecutar una instrucción, ¿entonces cuántas instrucciones está ejecutando?

No he contado los ciclos de reloj en mucho tiempo desde que programé las CPU de Motorola para aplicaciones integradas. Si su código tarda más tiempo, en realidad está generando un conjunto de instrucciones más grande de código de máquina, incluso si el bucle es más corto o se ejecuta una cantidad igual de veces.

Nunca olvide que su código realmente se está compilando en un conjunto de comandos que la CPU va a ejecutar (punteros de memoria, punteros de nivel de código de instrucción, interrupciones, etc.). Así es como funcionan las computadoras y es más fácil de entender a nivel de microcontrolador como un procesador ARM o Motorola, pero lo mismo ocurre con las máquinas sofisticadas en las que estamos trabajando hoy.

Su código simplemente no se ejecuta de la forma en que lo escribe (suena loco, ¿no?). Se ejecuta como se compila para ejecutarse como instrucciones a nivel de máquina (escribir un compilador no es divertido). La expresión matemática y la lógica se pueden compilar en un montón de código de nivel de máquina, y eso depende de cómo el compilador elija interpretarlo (¿está cambiando los bits, etc., recuerdan las matemáticas binarias?)

Referencia: https://software.intel.com/en-us/articles/introduction-to-x64-assembly

Su pregunta es difícil de responder, pero como @Bergi dijo, cuantas más operaciones duró, ¿por qué? Cuantos más ciclos de reloj se necesitan para ejecutar tu código. Dual core, quad core, threading, ensamblaje (lenguaje de máquina) es complejo. Pero ningún código se ejecuta como lo has escrito. C ++, C, Pascal, JavaScript, Java, a menos que esté escribiendo en el ensamblaje (incluso el que se compila en código de máquina) pero está más cerca del código de ejecución real.

Un maestro en CS y usted podrá contar los ciclos de reloj y ordenar los tiempos. Probablemente creará su propio lenguaje enmarcado en conjuntos de instrucciones de máquina.

La mayoría de la gente dice a quién le importa? La memoria es barata hoy y las CPU están gritando rápido y cada vez más rápido.

Pero hay algunas aplicaciones críticas en las que importa 10 ms, donde se necesita una interrupción inmediata, etc.

Comercio, NASA, una planta de energía nuclear, contratistas de defensa, algo de robótica, entiendes la idea. . .

Voto déjalo andar y sigo moviéndome.

Saludos, Wookie

Answer 2

Dado que el elemento que está buscando siempre está aproximadamente en el centro de la matriz, debe esperar que la versión que avanza tanto desde el principio como desde el final de la matriz demore aproximadamente el doble que la que comienza desde el principio.

Cada actualización de variable toma tiempo, cada comparación toma tiempo y usted está haciendo el doble de ellas. Como sabe que tomará una o dos iteraciones menos del bucle para terminar en esta versión, debería razonar que costará aproximadamente el doble de tiempo de CPU.

Esta estrategia sigue siendo una complejidad de tiempo O(n) ya que solo mira a cada elemento una vez, es específicamente peor cuando el elemento está cerca del centro de la lista. Si está cerca del final, este enfoque tendrá un mejor tiempo de ejecución esperado. Intenta buscar el artículo 90 en ambos, por ejemplo.

Answer 3

La respuesta es bastante obvia:

Más operaciones toman más tiempo.

Al juzgar la velocidad del código, observa cuántas operaciones realizará. Solo paso y cuéntalos. Cada instrucción tomará uno o más ciclos de CPU, y cuanto más tiempo haya, más tardará en ejecutarse. El hecho de que diferentes instrucciones tomen una cantidad diferente de ciclos no importa, si bien una búsqueda de matrices puede ser más costosa que la aritmética de enteros, ambas toman básicamente un tiempo constante y, si son demasiados, dominan el costo de nuestro algoritmo.

En su ejemplo, hay algunos tipos diferentes de operaciones que podría querer contar individualmente:

• comparaciones
• incrementos / decrementos
• búsqueda de matriz
• saltos condicionales

(Podríamos ser más granulares, como el conteo variable y las operaciones de almacenamiento, pero eso no importa, todo está en los registros de todos modos, y su número básicamente es lineal a los demás).

Ahora, ambos códigos se repiten unas 50 veces; el elemento en el que rompen el bucle se encuentra en el centro de la matriz. Ignorando algunos errores, esos son los conteos:

               |  forwards  | forwards and backwards
---------------+------------+------------------------
>=/===/<       |       100  |                   200
++/--          |        50  |                   100
a[b]           |        50  |                   100
&&/||/if/for   |       100  |                   200

Teniendo en cuenta esto, no es inesperado que hacer el doble de las obras lleve mucho más tiempo.

También responderé algunas preguntas de sus comentarios:

¿Se necesita tiempo adicional para la segunda búsqueda de objetos?

Sí, cada búsqueda individual cuenta. No es como si pudieran realizarse a la vez, u optimizarse en una sola búsqueda (imaginable si hubieran buscado el mismo índice).

¿Debería haber dos bucles separados para cada inicio y fin y para comenzar?

No importa por el número de operaciones, solo por su orden.

O, dicho de otra manera, ¿cuál es el enfoque más rápido para encontrar un elemento en una matriz?

No hay "más rápido" con respecto al pedido. Si no sabe dónde está el elemento (y están distribuidos uniformemente), debe probar cada índice. Cualquier orden, incluso aleatorias, funcionaría igual. Sin embargo, tenga en cuenta que su código es estrictamente peor, ya que mira cada índice dos veces cuando no se encuentra el elemento, no se detiene en el medio.

Pero aún así, hay algunos enfoques diferentes para microoptimizar tal bucle: verifique estos puntos de referencia .

• let es (aún?) más lento que var , vea ¿Por qué está usando `let` dentro de un bucle` for` tan lento en Chrome? y ¿Por qué es más lento que var en un bucle for en nodejs? . Este desgarre y desgarro (aproximadamente 50 veces) del alcance del cuerpo del bucle, de hecho, domina su tiempo de ejecución, es por eso que su código ineficiente no es completamente el doble de lento.
• la comparación con 0 es ligeramente más rápida que la comparación con la longitud, lo que hace que el bucle hacia atrás sea una ventaja. Consulte ¿Por qué es iterar a través de una matriz hacia atrás más rápido que hacia adelante , rendimiento de bucle de JavaScript? ¿Por qué es disminuir el iterador hacia 0 más rápido que incrementando y Son los bucles realmente más rápidos a la inversa?
• en general, consulte ¿Cuál es la forma más rápida de recorrer una matriz en JavaScript? : cambia de actualización del motor a actualización del motor. No hagas nada raro, escribe código idiomático, eso es lo que se optimizará mejor.

Answer 4

La respuesta seleccionada es excelente. Me gustaría agregar otro aspecto: intente findIndex() , es 2-3 veces más rápido que usar bucles:

const arr = Array.from({length: 900}, (_, i) => i);
const n = 51;
const len = arr.length;

console.time("iterate from start");
for (let i = 0; i < len; i++) {
  if (arr[i] === n) break;
}
console.timeEnd("iterate from start");

console.time("iterate using findIndex");
var i = arr.findIndex(function(v) {
  return v === n;
});
console.timeEnd("iterate using findIndex");

Answer 5

Las otras respuestas aquí cubren las razones principales, pero creo que una adición interesante podría ser mencionar el caché.

En general, el acceso secuencial a una matriz será más eficiente, particularmente con matrices grandes. Cuando la CPU lee una matriz de la memoria, también almacena las ubicaciones de memoria cercanas en la memoria caché. Esto significa que cuando recuperas el elemento n , el elemento n+1 probablemente también se carga en el caché. Ahora, la memoria caché es relativamente grande en estos días, por lo que su matriz de 100 int probablemente puede caber cómodamente en la memoria caché. Sin embargo, en una matriz de un tamaño mucho mayor, la lectura secuencial será más rápida que el cambio entre el principio y el final de la matriz.