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.

I definitely use so much DownValues structure for some many applications like to replace some common structures in a some way. It seems that DownValues is so fast for access, and set. My question is about complexity under DownValues usages.

For take to consideration: Suppose that, I can store in a DownValues Data relations between names of persons (short and long text_String) and Choices of whatever (List) such that I could have $n = 10000000$ of these relations and I want to search for names, and likely other operations like add choices for a specific person.

I've reading and It seems like DownValues structure has a pattern matching algorithm based on rules to access correctly to values. So I should say that:

  • Searching or accessing to specific key is O(n).
  • Create a new register, relations is O(1).
  • Modify register to set will be O(1)

But, I really concern about that, I used DownValues with a lot of data, and definitely it seems, that above statements are wrong. But, I don't find in the documentation comments about it. I'm thinking that in a low-level, DownValues use some king of hashing functions to indexing, in the example case, strings, because it's seems to access be in O(1)(?) or some BST to execute a search with pattern? I don't know.

So, I share my doubts about it, and maybe help to others beginners to pay attention a this absolute useful data structure, DownValues

share|improve this question

1 Answer 1

You have the right intuition. Mathematica distinguishes between DownValues that include a pattern and those that do not. Those that do not involve a pattern are maintained with a hashtable. (Thanks to @OleksandrR. for the correction.) (On that note you may also be interested in Dispatch.) Those that include a pattern are handled with the pattern-matching engine, which is inherently slower.

So this means that how f[2] is resolved internally will depend on whether the definition looks like

f[x_Integer] = 4;

or

f[2] = 4;

The latter definition will theoretically be faster, which is what we would expect since the more general nature of "is this an integer" versus "does this equal 2" creates more complexity.

The bottom line, then, is that you are mostly right: insertions, lookups, modifications, and deletions are all (on average) O(1).

You can test this for yourself:

ClearAll[a];
n = 100000;
nn = RandomSample[Range[n]];
Table[a[i] = RandomInteger[], {i, n}]; // AbsoluteTiming
Table[a[i] = RandomInteger[], {i, n}]; // AbsoluteTiming
Table[a[i], {i, nn}]; // AbsoluteTiming
Table[a[i] =., {i, n}]; // AbsoluteTiming

{0.848307, Null}

{0.943332, Null}

{0.428151, Null}

{0.907326, Null}

Now note the linear increase:

n = 3 n;
nn = RandomSample[Range[n]];
Table[a[i] = RandomInteger[], {i, n}]; // AbsoluteTiming
Table[a[i] = RandomInteger[], {i, n}]; // AbsoluteTiming
Table[a[i], {i, nn}]; // AbsoluteTiming
Table[a[i] =., {i, n}]; // AbsoluteTiming

{2.511880, Null}

{2.820003, Null}

{1.360487, Null}

{2.716959, Null}

share|improve this answer
1  
Obviously you're right about the complexity, but I should say that DownValues are not related to SparseArray, which stores its contents in CRS format and was new in version 5. The use of hash tables for storing downvalues was introduced a long time before that, in version 2, and has nothing in common AFAIK. –  Oleksandr R. May 27 at 1:14
    
@OleksandrR. Thanks for that. I was relying on Data structures and efficient algorithms in Mathematica ("One uses [sparse arrays] to store values associated to 'indices' attached to a given 'head.') but that is from 1999. Do you know of something more current that I should read? And does that mean my explanation is completely off the mark? (I'd like to fix it if so.) –  mfvonh May 27 at 1:22
    
Your explanation is absolutely fine except for the SparseArray confusion, which is understandable given the source material. Version 5 was released in 2003, so SparseArray wasn't implemented at the time that conference presentation was written; certainly a hash table can be helpful in constructing a SparseArray, although the reverse is not really true given the storage format. You could have "sparse array" in place of "SparseArray", but since everyone knows what a hash table is anyway, I would just stay with that and remove the reference to SparseArray altogether, if I were you. –  Oleksandr R. May 27 at 1:30

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.