4
$\begingroup$

If I have a series of list of the form $L_k=\{a_1, a_2,...a_n\}_k$ with $-4<a_i<4$ and $a_i\in\mathbb Z$, then I can make a unique ID number for $L_k$ using ID_k = FromDigits[L + 4] and I can go back to $L_k$ using First[RealDigits[ID]] - 4.(If I am not mistaken)

For example if:

L = {-3, -2, 0, 1, 3}
ID = 12457

ID should be unique I think, and I can go from L to ID and from ID to L without ambiguity.

Now how should I adapt this process if $-6<a_i<6$? The problem is that now $L+7$ contains double digits numbers or decimal numbers...

Question: Is there an easy way that displays both unicity and reversibility and that is not time consuming (I have to go back from list to ID many many times)? How would you do it ?

I think hashing is not collision free (I have about 11 000 000 such lists ) and it is not clear to me how I should go back from the hash code to the list without storing additional information.

I think I can do it using for example the alphabet, for example:

list = {{-2, 2}, {2, 2}, {-4, 4}, {4, 4}, {2, 2}, {2, 2}}
id = (StringRiffle[Flatten[FromLetterNumber[list + 7]], ""] // 
    AbsoluteTiming)[[2]]
LetterNumber[StringSplit[id, ""]] - 7 // AbsoluteTiming

But string IDs are heavier to store than number IDs and these operations are quite slow (2 ms on my machine). Do you have better?

$\endgroup$
5
$\begingroup$

If you are doing all the lookups within a single kernel session, then you can just store the ID numbers as down values:

Module[{lastID = 0, ids, reverse, addEntry},
    addEntry[list_] := With[
        {newID = PreIncrement @ lastID},
        ids[list] = newID;
        reverse[newID] = list;
        newID
    ];
    toId[list_] := Replace[ids @ list, _ids :> addEntry[list]];
    fromId[id_] := Replace[reverse @ id, _reverse :> $Failed];
]

The timing is comparable to the FromDigits method above:

In[2]:= lists = RandomInteger[{-5, 5}, {200000, 8}];
idlist = toId /@ lists; // AbsoluteTiming
roundTripped = fromId /@ idlist; // AbsoluteTiming
lists === roundTripped

Out[3]= {1.38589, Null}

Out[4]= {0.438251, Null}

Out[5]= True
$\endgroup$
3
$\begingroup$

You can simply use a larger base.

n = 8;
p = 6-1;
base = 2 p + 1;
L = RandomInteger[{-p, p}, {200000, n}];

ClearAll[toID, fromID];
toID[L_] := FromDigits[L + p, base];
fromID[ID_] := IntegerDigits[ID, base, n] - p;

Here a usage example:

IDs = toID /@ L; // AbsoluteTiming // First
L2 = fromID /@ IDs; // AbsoluteTiming // First
L2 == L

0.877335

1.05924

True

It is not really super fast, though, because we have to use Map because FromDigits and IntegerDigits are vectorized. But it gives an idea.

$\endgroup$

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.