Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

In my algorithm I need to maintain a set (an unordered list of distinct elements) of expressions supporting two operations:

  • Test an expression for membership in the set
  • Adding a new expression to the set

Expressions are to be compared using SameQ. The set can have hundreds of thousands of elements and I want it to work as fast as possible. In most programming languages I would use a hash-table or a balanced tree to implement such a set. Is there any better data structure in Mathematica for this purpose than a plain List? Is it worth trying to manually implement a better structure?

share|improve this question
    
Try linked lists. –  Spawn1701D Jun 7 '13 at 20:13
2  
You can use a hash table implicit in DownValues, just by introducing some symbol (say, presentQ). Starting definition is presentQ[_]=False. Then,adding is as simple as presentQ[expr] = True, and presentQ itself tests for membership. This seems the easiest option. You can also use System`Utilities`HashTable as an alternative. –  Leonid Shifrin Jun 7 '13 at 20:47
1  
@LeonidShifrin Using downvalues is a simple and great idea! I should have realized this myself. –  Vladimir Reshetnikov Jun 7 '13 at 21:46
    
@VladimirReshetnikov This is a standard and most common way to implement this sort of things. Sometimes one can also use SubValues, although the difference is mostly syntactic. But I have not seen a clear exposition in the documentation which would have explained that hash table functionality in Mathematica is most easily achieved via DownValues. –  Leonid Shifrin Jun 7 '13 at 22:10
    
@LeonidShifrin I implemented the approach you suggested, but later found a bug in my implementation: when expr is a pattern, the plain presentQ[expr] = True does not have the intended meaning. The fix is to use presentQ[Verbatim[expr]] = True instead. –  Vladimir Reshetnikov Jun 25 '13 at 1:26
show 1 more comment

1 Answer 1

up vote 5 down vote accepted

Per Leonid's comment:

You can use a hash table implicit in DownValues, just by introducing some symbol (say, presentQ). Starting definition is presentQ[_] = False. Then, adding is as simple as presentQ[expr] = True, and presentQ itself tests for membership. This seems the easiest option. You can also use System`Utilities`HashTable as an alternative.

However, Vladimir notes:

When expr is a pattern, the plain presentQ[expr] = True does not have the intended meaning. The fix is to use presentQ[Verbatim[expr]] = True instead.

I would also add that the new Association data structure in Mathematica 10 is likely to be a faster and perhaps more convenient approach than using either downvalues or the System`Utilities`HashTable.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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