I have an array of vectors, myCoords, with x and y coordinates, of size larger than 50,000.
I am looking to find the index value of the vector in myCoord having the same coordinate (x, y) as vector, myVector. Note that myVector always exists in myCoords.
The following line of code returns the index value I am looking for. I was wondering if there is any faster way to obtain the same result. I have to perform this search thousand of time and realized it is significantly slowing down my script.
myIndex = myCoords.findIndex(a => a.x === myVector.x && a.y === myVector.y);
here is my no-brainer improvement (using deno, but you can use it in any flavor you like):
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();
results:
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
why do we have such improvement here?
well, technically you could go under O(n) by using eg. binary search (which has O(log n)), but if you don't want to bother just optimize how your code runs by using more performant data structures,
first - don't use closures they are not very performant,
second - notice I've used two typed array here: coordinates are numbers, so let's work on numbers - however I don't know what kind of coordinates you have there so you can optimize that a bit by narrowing the type,
additionally maybe you could try Object.is instead of === operator, but I'm not sure if there would be any gains