Dado que array.find() itera sobre una matriz, si manejo (potencialmente) matrices grandes, siempre me aseguro de tener un objeto indexado así:
{ [id:string]: Item }si necesito buscar elementos por id en estas matrices.
Sin embargo, viviendo en una época de V8 (y optimizaciones de motor comparables para Safari y Firefox), me pregunto si tal vez bajo el capó, un simple array.find() ya está optimizado para ello. ¿O lo optimizará (creará un objeto indexado de este tipo) en tiempo de ejecución tan pronto como tenga que realizar esta operación una vez?
¿Es cierto que los navegadores modernos ya tienen algún tipo de optimización para algoritmos de tipo O(N) que podrían convertirse en O(1) con la implementación adecuada? ¿O estoy pensando demasiado en lo que estos navegadores realmente pueden/harán bajo el capó?
Desarrollador V8 aquí. La complejidad temporal de Array.prototype.find es O(n) (siendo n la longitud de la matriz), y es justo suponer que seguirá siendo así.
En términos generales, a menudo es imposible que los motores mejoren la clase de complejidad de una operación. En el caso de Array.prototype.find , la función de predicado que pase podría importarle con qué frecuencia se llama:
[1, 2, 3].find((value, index, object) => { console.log(`Checking ${value}...`); // Or any other side effect. return value === 42; });En tal caso, el motor no tiene más remedio que iterar sobre toda la matriz exactamente en el orden correcto, porque cualquier otra cosa rompería el comportamiento de su programa.
En teoría, dado que los motores JS pueden realizar optimizaciones dinámicas, podrían inspeccionar la función de predicado y, si no tiene efectos secundarios, podrían usarla para crear algún tipo de índice/caché. Aparte de la dificultad de construir un sistema de este tipo que funcione para predicados arbitrarios, esta técnica, incluso cuando funciona, solo aceleraría las búsquedas repetidas de la misma matriz con la misma función, a costa de perder tiempo y memoria si este mismo escenario exacto no volverá a ocurrir. Parece poco probable que un motor pueda hacer esta predicción con suficiente confianza para justificar invertir este tiempo y memoria.
Como regla general: cuando se opera con grandes conjuntos de datos, vale la pena elegir algoritmos y estructuras de datos eficientes. Por lo general, vale mucho más la pena que las microoptimizaciones que vemos tanto en las preguntas SO :-)
Un motor altamente optimizado/optimizador puede hacer que su código O(n) sea entre un 10 % y 10 veces más rápido que de otro modo. Al cambiar a una solución O(log n) u O(1) en su extremo, puede acelerarlo en órdenes de magnitud. Eso a menudo se logra haciendo algo que los motores no pueden hacer. Por ejemplo, puede mantener su matriz ordenada y luego usar la búsqueda binaria sobre ella; eso es algo que un motor no puede hacer por usted automáticamente porque obviamente no está permitido reordenar los contenidos de su matriz sin su aprobación. Y como @myf ya señala en un comentario: si desea acceder a las cosas mediante una clave única, entonces usar un Map probablemente funcionará mejor que usar un Array .
Dicho esto, las soluciones simples tienden a escalar mejor de lo que asumimos intuitivamente; la advertencia estándar contra las optimizaciones prematuras se aplica aquí como en cualquier otro lugar. La búsqueda lineal a través de matrices a menudo está bien, no necesita un mapa (hash) solo porque tiene más de tres elementos. En caso de duda, perfile su aplicación para averiguar dónde están los cuellos de botella de rendimiento.