Mire esta pregunta loca... Tengo una matriz con 30.000 elementos, y tengo que ejecutar algo como esto sobre ella:
const bigArray = [ { createdAt: 1 }, { createdAt: 2 }, { createdAt: 3 }, // And so on... 30.000 ]; const found = bigArray.find(x => x.createdAt > 29950) Y la cosa aquí, es que sé que el 100% del tiempo, ese elemento estará en el índice 29.950 (aprox). Porque esa matriz ya está ordenada por createdAt (procedente del backend)
¿Cómo funciona .find ? ¿Itera a partir del primer elemento? ¿Hay alguna manera de decir "Sé que está más cerca el final... Cambia tu comportamiento"?
Por supuesto, existe la alternativa de hacer algo como:
bigArray.reverse() const prevIndex = bigArray.findIndex(x => x.createdAt <= 29950); const found = bigArray[prevIndex - 1]; bigArray.reverse()Pero no estoy seguro de si eso será realmente peor (debido al hecho de que allí también tendremos varias iteraciones innecesarias... supongo).
Quien me puede dar alguna pista sobre esto? No es que tenga un error aquí... Ni siquiera un problema de rendimiento (porque 30.000 no es mucho), pero parece que debería haber algo allí, y nunca escuché sobre eso en ~16 años trabajando en JavaScript.
¡Muchas gracias!
Según la documentación aquí , parece que find es O(n) complejidad de tiempo, donde n es la longitud de la matriz.
Dado que sus elementos están ordenados, puede intentar realizar una búsqueda binaria y reducir la complejidad del tiempo a O(log n) .
Este es el algoritmo iterativo básico de búsqueda binaria:
function binarySearchIterative (nums, target) { let res = -1; let left = 0; let right = nums.length; while (left <= right && res === -1) { const mid = Math.floor(left + (right - left)/2); if (nums[mid] === target) { res = mid; } else if (nums[mid] > target) { right--; } else { left++; } } return res; };No estoy al tanto de ninguna opción para Array.prototype.findIndex que comience desde el final... Sé con certeza que usar Array.prototype.reverse es muy costoso y podría crear su propio algoritmo como este si sabe que es probable que encuentre el resultado que necesita cerca del final:
const bigArray = [ { createdAt: 1 }, { createdAt: 2 }, { createdAt: 3 } ]; // Add the function to Array.prototype Array.prototype.findIndexFromEnd = function (cond) { for(let i = this.length - 1; i >= 0; i--) { if(cond(this[i])) return i; } return -1; } // Gives 1 as expected console.log(bigArray.findIndexFromEnd(x => x.createdAt == 2)); // Or use an external function if you don't want to edit the prototype function findIndexFromEnd(array, cond) { for(let i = array.length - 1; i >= 0; i--) { if(cond(array[i])) return i; } return -1; } // Gives 1 as expected console.log(findIndexFromEnd(bigArray, (x) => x.createdAt == 2));