0

I'm in a situation that basically boils down to storing values based on 2 ID's. The ID's are sparse, from different ID pools and pretty much unpredictable so the naive approach is to just store the data in nested hash tables.

The challenge is that these values need to be stored for many sequentially created objects, there are generally only a few values (all though, I have to allow for the possibility of way more) and the performance overhead for creating all the nested hash tables is too much. Rolling my own specialized hash table is unfeasible due to the environment (javascript) so I'm having alternative ideas.

Probably every programmer is familiar with the basic 2d indexing where if you have a 100x100 grid of data, setting for example slot 32x44 would require figuring out its 1D index which would be 44 x 100 + 32 = 4432, simple.

TLDR start here: Now I'm curious if its possible to come up with a 1D index based on a 2D coordinate in a way that doesn't involve limited bounds. In my mind it should be possible, example represented as a lookup table:

my_index[0][0] = 0

my_index[0][1] = 1
my_index[1][0] = 2
my_index[1][1] = 3

my_index[0][2] = 4
my_index[1][2] = 5
my_index[2][0] = 6
my_index[2][1] = 7
my_index[2][2] = 8

...etc

Is there any kind of algorithm that does this? It doesn't have to map them exactly like that of course, could be whatever as long as it creates a unique index out of any 2 inputs. All though the above example would be extra good for my situation as its optimized towards the the two index sets being statistically square which in my case is true.

EDIT: Looking at it, I figured out the forwards function of getting the 1D coordinate just like in my example LUT

it was surprisingly simple, now I gotta figure out the reverse

EDIT 2: Nevermind, figured it out

function t1d(x, y) {
    if (x >= y) return x * x + x + y;
    else return y * y + x;
}

function t2d(v) {
    const a = Math.trunc(Math.sqrt(v));
    const b = a * a + a;
    if (v >= b) return [a, v - b] 
    else return [v - a * a, a]
}

That square root is owch for the performance but fortunately in this case, I don't even need to go in reverse!

Improve this question
5
  • 1
    I recommend to remove the answer part from your question and create a separated answer from it, that would way better fit to the site's format and makes it more visible the question already has an answer . But what I am really wondering is, why don't you simply combine your two ID numbers into one string with a separator (for example, "32_44"), and use this as the key for one hash table - no need for any nesting this way? – Doc Brown Feb 22 at 14:49
  • 1
    Do you need actually unique and reversible mapping, or a hash value which may collide? Those are quite different things. In your answer, you seem to assume that the inputs are numbers, the logic is a bit too convoluted for me to find out whether this creates collisions but I assume it does. Then you might just use any old hash scheme on the concatenation of the input values (whether in decimal or bytes doesn't matter) as @DocBrown suggests. If you need a reversible mapping, the answer given by user253751 points in the right direction. – Hans-Martin Mosner Feb 22 at 15:20
  • @Hans-MartinMosner: my suggestion is reversible, I thought that's pretty obvious. – Doc Brown Feb 22 at 16:02
  • @DocBrown Combining the ids into a string as well as using object or Map instead of a sparse array (due to key being string) was one if my initial approaches but the performance was disappointing in V8 and far outdone by even nested arrays. Hans-MartinMosner I can't afford collisions. The answer I came up with produces unique results for each combination (all though due to js Number being a double i can only use values up to 2 ^ 26 but that is good enough for me) – user81993 yesterday
  • @user81993: I still recommend to extract the answer-part from your question and put it into an answer of its own, shouldn't take more than two minutes of yours. – Doc Brown yesterday
1

You can interleave bits:

 X: 0x68    0 1 1 0 0 1 0 0
            v v v v v v v v
ID: 0x163A 0001011000111010
           ^ ^ ^ ^ ^ ^ ^ ^
 Y: 0x17   0 0 0 1 0 1 1 1

Supplementary: Bit interleaving implementations

Improve this answer
1
  • Hey that's a cool idea, interleaving bits might be too heavy duty for js but I think interleaving bytes might have potential, I got to test this – user81993 yesterday

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.