Javascript: Most efficient way to store 20,000 numeric IDs and check against them?

Question

So I've got IDs as int32 going from 0 to 20000 and I need to have them on an array in JavaScript. So the array might be as big as 20,000 items long.

Then I need to check a few IDs to see if they are in that list.

What's the most efficient way to do it, so we don't crash the browser's memory?

Maybe this other question could be helpful. It also refers to the most efficient way to check if an object can be found in an array. http://stackoverflow.com/questions/237104/how-do-i-check-if-an-array-includes-an-object-in-javascript — Davis, Jul 23 '16 at 01:55
an array of 20000 may be a problem for NCSA Mosaic, but I doubt you'll "crash the browsers memory" (whatever the heck that means) with any browser today — Jaromanda X, Jul 23 '16 at 01:55
20000 array elements are nothing. JS can do millions of operations per second on arrays. — Pier, Jul 23 '16 at 01:57
Even completely full, that would only take up about 80 kb of memory. There's no need to worry about space. To be most efficient with speed, keep the array sorted, and use a binary search when checking for ids. — 4castle, Jul 23 '16 at 02:01

score 1 · Accepted Answer · answered Jul 23 '16 at 02:07

If you want to reduce the memory, store the numbers in typed array of 16-bit unsigned integers, which would allow you to store numbers from 0 to 65535, included.

However, searching would be slow. And 20000 numbers won't waste excessive memory.

20000 * 64 bit = 1280000 bit = 160000 byte = 156.25 kibibyte

So I would suggest a Set or an object. Set operations are required to be sublinear on average.

var s = new Set();
s.add(id); // store id
s.has(id); // check id
s.delete(id); // remove id
s.size; // count ids
for(var id of s) {} // iterate ids, in insertion order

var s = Object.create(null);
s[id] = true; // store id
id in s; // check id
delete s[id]; // remove id
for(var id in s) {} // iterate stringified ids, in implementation-defined order

score 1 · Answer 2 · answered Jul 23 '16 at 02:46

If the range of your numbers is limited, the most efficient way is to store them in packed bit array, one bit per number. The bit array can be represented as Uint8Array, then, to check if the number N is in array (=its bit is set), compute

array[N >> 3] & (1 < (N & 7))

Javascript: Most efficient way to store 20,000 numeric IDs and check against them?

2 Answers2