Tengo una matriz de vectores, myCoords , con coordenadas x e y , de tamaño superior a 50 000.
Estoy buscando encontrar el valor de índice del vector en myCoord que tiene la misma coordenada ( x , y ) que el vector, myVector . Tenga en cuenta que myVector siempre existe en myCoords .
La siguiente línea de código devuelve el valor de índice que estoy buscando. Me preguntaba si hay alguna forma más rápida de obtener el mismo resultado. Tengo que realizar esta búsqueda miles de veces y me di cuenta de que está ralentizando significativamente mi script.
myIndex = myCoords.findIndex(a => ax === myVector.x && ay === myVector.y);aquí está mi mejora obvia (usando deno, pero puedes usarlo en el sabor que quieras):
import { runBenchmarks, bench } from "https://deno.land/std/testing/bench.ts"; bench({ name: "Array.prototype.findIndex", runs: 10_000, func(b): void { const arr = Array(100_000) .fill(null) .map(() => ({ x: Math.random(), y: Math.random() } as const)); const lastItem = arr[arr.length - 1]; b.start(); arr.findIndex((item) => item.x === lastItem.x && item.y === lastItem.y); b.stop(); }, }); function findIndex( arrX: Float64Array, arrY: Float64Array, x: number, y: number ) { const length = arrX.length; for (let i = 0; i < length; i++) { if (arrX[i] === x && arrY[i] === y) { return i; } } return -1; } bench({ name: "typed array findIndex", runs: 10_000, func(b): void { const arrX = new Float64Array(100_000).map(Math.random); const arrY = new Float64Array(100_000).map(Math.random); const lastItemX = arrX[arrX.length - 1]; const lastItemY = arrY[arrY.length - 1]; b.start(); findIndex(arrX, arrY, lastItemX, lastItemY); b.stop(); }, }); await runBenchmarks();resultados:
running 2 benchmarks ... benchmark Array.prototype.findIndex ... 10000 runs avg: 1.1294ms benchmark typed array findIndex ... 10000 runs avg: 0.1306ms benchmark result: DONE. 2 measured; 0 filtered ¿Por qué tenemos tal mejora aquí? bueno, técnicamente podría pasar por debajo de O(n) usando, por ejemplo. búsqueda binaria (que tiene O(log n) ), pero si no quiere molestarse, simplemente optimice cómo se ejecuta su código utilizando estructuras de datos de mayor rendimiento,
primero: no use cierres, no son muy eficaces,
segundo: observe que he usado dos matrices escritas aquí: las coordenadas son números, así que trabajemos en números; sin embargo, no sé qué tipo de coordenadas tiene allí, por lo que puede optimizarlo un poco al reducir el tipo,
además, tal vez podría probar Object.is en lugar del operador === , pero no estoy seguro de si habría alguna ganancia