You have a non-trivial problem but I'm gonna blast right through so ask questions if I lose you somewhere along the line. This solution does not cast the coordinate into a String or serialise it using other techniques like JSON.stringify -
Start with a way to create coordinates -
const Coord = (x, y) =>
[ x, y ]
To demonstrate the solution, I need to construct many random coordinates -
const rand = x =>
Math.floor(Math.random() * x)
const randCoord = x =>
Coord(rand(x), rand(x))
console.log(randCoord(1e3))
// [ 655, 89 ]
Now we make an array of 1 million random coordinates -
const million =
Array.from(Array(1e6), _ => randCoord(1e3))
Now we make a function to filter all of the unique values using DeepMap, a tiny module I developed in this answer.
const uniq = (coords = []) =>
{ const m = new Map
const r = []
for (const c of coords)
if (!DeepMap.has(m, c))
{ DeepMap.set(m, c, true)
r.push(c)
}
return r
}
Because for and DeepMap have excellent performance, uniq can identify all of the unique values in less than one second -
console.time("uniq")
const result = uniq(million)
console.timeEnd("uniq")
console.log("uniq length:", result.length)
console.log("sample:", result.slice(0,10))
// uniq: 535 ms
// uniq length: 631970
// sample:
// [ [ 908, 719 ]
// , [ 532, 967 ]
// , [ 228, 689 ]
// , [ 942, 546 ]
// , [ 716, 180 ]
// , [ 456, 427 ]
// , [ 714, 79 ]
// , [ 315, 480 ]
// , [ 985, 499 ]
// , [ 212, 407 ]
// ]
Expand the snippet below to verify the results in your own browser -
const DeepMap =
{ has: (map, [ k, ...ks ]) =>
ks.length === 0
? map.has(k)
: map.has(k)
? DeepMap.has(map.get(k), ks)
: false
, set: (map, [ k, ...ks ], value) =>
ks.length === 0
? map.set(k, value)
: map.has(k)
? (DeepMap.set(map.get(k), ks, value), map)
: map.set(k, DeepMap.set(new Map, ks, value))
}
const Coord = (x, y) =>
[ x, y ]
const rand = x =>
Math.floor(Math.random() * x)
const randCoord = x =>
Coord(rand(x), rand(x))
const million =
Array.from(Array(1e6), _ => randCoord(1e3))
const uniq = (coords = []) =>
{ const m = new Map
const r = []
for (const c of coords)
if (!DeepMap.has(m, c))
{ DeepMap.set(m, c, true)
r.push(c)
}
return r
}
console.time("uniq")
const result = uniq(million)
console.timeEnd("uniq")
console.log("uniq length:", result.length)
console.log("sample:", result.slice(0,10))
// uniq: 535 ms
// uniq length: 631970
// sample:
// [ [ 908, 719 ]
// , [ 532, 967 ]
// , [ 228, 689 ]
// , [ 942, 546 ]
// , [ 716, 180 ]
// , [ 456, 427 ]
// , [ 714, 79 ]
// , [ 315, 480 ]
// , [ 985, 499 ]
// , [ 212, 407 ]
// ]
By using generating smaller random coordinates, we can verify that uniq is generating a correct output. Below we generate coordinates up to [ 100, 100 ] for a maximum possibility of 10,000 unique coordinates. When you run the program below, because the coordinates are generated at random, it's possible that result.length will be under 10,000, but it should never exceed it - in which case we'd know an invalid (duplicate) coordinate was added -
const million =
Array.from(Array(1e6), _ => randCoord(1e2))
console.time("uniq")
const result = uniq(million)
console.timeEnd("uniq")
console.log("uniq length:", result.length)
console.log("sample:", result.slice(0,10))
// uniq: 173 ms
// uniq length: 10000
// sample:
// [ [ 50, 60 ]
// , [ 18, 69 ]
// , [ 87, 10 ]
// , [ 8, 7 ]
// , [ 91, 41 ]
// , [ 48, 47 ]
// , [ 78, 28 ]
// , [ 39, 12 ]
// , [ 18, 84 ]
// , [ 0, 71 ]
// ]
Expand the snippet below to verify the results in your own browser -
const DeepMap =
{ has: (map, [ k, ...ks ]) =>
ks.length === 0
? map.has(k)
: map.has(k)
? DeepMap.has(map.get(k), ks)
: false
, set: (map, [ k, ...ks ], value) =>
ks.length === 0
? map.set(k, value)
: map.has(k)
? (DeepMap.set(map.get(k), ks, value), map)
: map.set(k, DeepMap.set(new Map, ks, value))
}
const Coord = (x, y) =>
[ x, y ]
const rand = x =>
Math.floor(Math.random() * x)
const randCoord = x =>
Coord(rand(x), rand(x))
const uniq = (coords = []) =>
{ const m = new Map
const r = []
for (const c of coords)
if (!DeepMap.has(m, c))
{ DeepMap.set(m, c, true)
r.push(c)
}
return r
}
const million =
Array.from(Array(1e6), _ => randCoord(1e2))
console.time("uniq")
const result = uniq(million)
console.timeEnd("uniq")
console.log("uniq length:", result.length)
console.log("sample:", result.slice(0,10))
// uniq: 173 ms
// uniq length: 10000
// sample:
// [ [ 50, 60 ]
// , [ 18, 69 ]
// , [ 87, 10 ]
// , [ 8, 7 ]
// , [ 91, 41 ]
// , [ 48, 47 ]
// , [ 78, 28 ]
// , [ 39, 12 ]
// , [ 18, 84 ]
// , [ 0, 71 ]
// ]
Lastly, I'll include the DeepMap module used here -
const DeepMap =
{ has: (map, [ k, ...ks ]) =>
ks.length === 0
? map.has(k)
: map.has(k)
? DeepMap.has(map.get(k), ks)
: false
, set: (map, [ k, ...ks ], value) =>
ks.length === 0
? map.set(k, value)
: map.has(k)
? (DeepMap.set(map.get(k), ks, value), map)
: map.set(k, DeepMap.set(new Map, ks, value))
, get: (map, [ k, ...ks ]) =>
// ...
, entries: function* (map, fields = [])
// ...
}
For a complete implementation, see the linked Q&A. Fwiw, I do think you will find the link interesting as it provides more context for the complexity of this problem.
