6
$\begingroup$

I have an algorithm that produces certain entries of data and appends them to a list myList = {};. For example, after five iterations the list might look like:

myList = {entry1, entry2, entry3, entry4, entry5};

Whenever a new entry newEntry is produced, the algorithm first has to check whether this entry already exists in the list (no duplicates are added). Right now I do the check as:

pos = Flatten[Position[myList, newEntry] /. ({}) -> {0}][[1]];

If pos>0, then the entry exists and the new one is not added, if pos===0 then the entry is new and is appended to the list.

As the list grows very large, the process of finding the position becomes very slow. In part this is because all the entries have rather complicated list structure. Therefore, I thought about switching to a hash model, which would work as follows:

Entries should be stored in separate variables as myStorage[hsh[newEntry]] = newEntry; where the hash function hsh[x_] is something along the lines of:

hsh[x_]:=Hash[x,"MD5"]

with this, instead of searching the entire list every time I need to check whether an entry already exists, I can just use ValueQ[myStorage[hsh[newEntry]]] (and can store all existing hashes in a separate list to access the results later). This promises a great speedup. However, I heard that collisions are possible for hash functions. If two different entries should produce the same hash number, the results would become wrong. Therefore, I would like to ask if a completely collision free hash function exists? The documentation for Hash lists the functions:

"Adler32","CRC32","MD2","MD5","SHA","SHA256","SHA384","SHA512"

Is any of them guaranteed collision free? Which one should I use to minimize collision risk? Maybe I should do something else entirely, to improve the performance of my algorithm? Thanks for any suggestion!

$\endgroup$
  • $\begingroup$ Any particular reason not to use MemberQ ? $\endgroup$ – Gustavo Delfino Dec 6 '16 at 21:10
  • $\begingroup$ @GustavoDelfino I also need to actually know the position of the entry, if it already exists. $\endgroup$ – Kagaratsch Dec 6 '16 at 21:14
  • 2
    $\begingroup$ Why not use something like an association with entry -> index? You are essentially trying to reimplement a subset of its functionality. $\endgroup$ – Szabolcs Dec 6 '16 at 21:51
  • 2
    $\begingroup$ BTW no hash function can be strictly collision free due to the fact that they map a larger set to a smaller one. $\endgroup$ – Szabolcs Dec 6 '16 at 21:53
  • 2
    $\begingroup$ Use an Association where the keys are the entries of your list. This will make it fast to test if an expression is already in the collection. You said that you also need the position of the entry, if it exists. So make the values be the "positions". The nth added key should have value n. $\endgroup$ – Szabolcs Dec 6 '16 at 23:27
4
$\begingroup$

Mathematica's associations do not permit duplicate keys. You could make use of this.

I make a simple association to illustrate my point. Since I am only interested in the keys, the values are all zero.

With[{n = 3}, 
  stuff = AssociationThread[Array[thing, n], ConstantArray[0, n]]]

Association[thing[1] -> 0, thing[2] -> 0, thing[3] -> 0]

Appending a new element.

AssociateTo[stuff, thing[42] -> 0]

Association[thing[1] -> 0, thing[2] -> 0, thing[3] -> 0, thing[42] -> 0]

But I can't add a duplicate.

AssociateTo[stuff, thing[2] -> 0]

Association[thing[1] -> 0, thing[3] -> 0, thing[42] -> 0, thing[2] -> 0]

Yes, the order has changed but since it's a hash, the order shouldn't matter.

When the list form is needed:

myList = Keys @ stuff

{thing[1], thing[2], thing[3], thing[42]}

$\endgroup$
  • $\begingroup$ I heard that appending new elements to a list copies the entire list plus one more element to a new list (which can get very slow). Is it the same for associations? Or are association elements added on a one by one basis with no overhead due to the already existing association elements? $\endgroup$ – Kagaratsch Dec 7 '16 at 14:22
  • 1
    $\begingroup$ @Kagaratsch. I think it is true for AppendTo, but not for AssociateTo, which is what I recommend.However, I have not done any serious performance testing. $\endgroup$ – m_goldberg Dec 7 '16 at 18:24
2
$\begingroup$

Placeholder answer, because I am just about to be called into a meeting...

I would use Downvalues, and have used them successfully for MMA version 9.0 and earlier

Clear[mylistDownvalues];
mylistDownvalues[_]=False;

(* how you fill with entries, set downvalues *)
mylistDownvalues[entry1]=1;
mylistDownvalues[entry2]=2;
mylistDownvalues[entry3]=3;
mylistDownvalues[entry4]=4;
mylistDownvalues[entry5]=5;

(* trivial to make a helper function *)

myCount=6;
mylistHelper[v_]:=(mylistDownvalues[v]=myCount;myCount+=1)

mylistHelper[entry6];
mylistHelper[entry7];

(* how you get list of entries *)
mylist = SortBy[Select[#[[1,1,1]]->#[[2]]& /@ 
 DownValues[mylistDownvalues],#[[2]]=!=False&],#[[2]]&];
(* Out[]= {entry1->1,entry2->2,entry3->3,entry4->4, *)
(*         entry5->5,entry6->6,entry7->7} *)

(* membership test is fast, insertion is fast, getting index is fast *)

(* membership *)
mylistMemberQ[v_]:=mylistDownvalues[v]=!=False

mylistMemberQ[entry4]
(* Out[]= True *)
mylistMemberQ[entry8]
(* Out[]= False *)

(* getting index *)
mylistDownvalues[entry5]
(* Out[]= 5 *)
$\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.