2
$\begingroup$

I have the following problem :

I have a programm which can generate a lot of 3x3 matrices whose elements take integer values in [-3;3], example :{{1,2,3},{-3,0,-2},{1,1,1}}.

Each time my programm generates a Matrix M, I want to store it in a storage structure L. The thing is, if my programm generates a second time the matrix M, I do not want to add it again to the list.

Therefore each time I generate a matrix, I must compare through some sort of identification if the matrix M already exists in my list L.

Therefore I would like to have a unique ID for each matrix, which ensures a fast verfification of whether or not the newly generated matrix exists in the storage structure L.

I have heard of hashing (I am not from the programming world). So my idea is the following:

I generate M,

I calculate Hash[M]

Then I add the association Hash[M]->M to a list L.

If I generate a second matrix M', I calculate Hash [M'], and I check if the key Hash[M'] exists in L, if not I add the association Hash[M']->M' to L etc..

The thing is I am not sure the hash function is a bijection (I think it's not).

Second, I do not know how fast the checking part ("check if the key Hash[M'] exists in L") is ! My list is going to be big, so I need the checking to be efficient !!

Can anyone enlighten me or give me a better faster solution?

Thank you very much for your help !

$\endgroup$
2
  • 2
    $\begingroup$ Hashes are generally not bijective. Faced with your problem I might roll my own 'hash-like' operation such as FromDigits[4 + Flatten[M]] and keep those 9-digit integers in your list L. As to the speed of this approach, I'm not sure and not in a position to test right now, which is why I'm only commenting. While you wait for an answer, do some research into Bloom filters. $\endgroup$ Apr 29, 2020 at 10:53
  • $\begingroup$ Do you really need to do this each time a new matrix is generated? If not, then a simple thing to do is to generate all the matrices, and take the Union[ ]. This will remove all the duplicate entries. $\endgroup$
    – bill s
    Apr 29, 2020 at 15:29

1 Answer 1

5
$\begingroup$

You can use an Association e.g. as follows:

input = RandomInteger[{0, 1}, {100000, 3, 3}];

ClearAll[a];
a = Association[];
Do[a[A] = 1;, {A, input}]; // AbsoluteTiming // First
output1 = Keys[a];

0.173041

Internally Association uses hashes and quite many other tricks to make the addition, modification, and lookup of entries efficient.

Alternatively, you can use the hash table that manages the DownValues of a symbol as follows:

ClearAll[a];
Do[a[A] = 1;, {A, input}]; // AbsoluteTiming // First
output2 = Extract[DownValues[a][[All, 1]], {All, 1, 1}];

0.189094

Both are equally fast and produce the same result up to ordering:

Sort[output1] == Sort[output2]

True

I prefer the first method because an Association is a more structured and encapsulated way of storing data; it can be easily erased with a=. and be send to other functions/contexts etc. without having to mess around with the Mathematica's name space management.

$\endgroup$
2
  • $\begingroup$ Thank you very much for this answer. I do not really understand the downValues thing, so I'll go with the first alternative for now. $\endgroup$
    – DarkBulle
    Apr 29, 2020 at 11:24
  • $\begingroup$ You're welcome. $\endgroup$ Apr 29, 2020 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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