DownValues Type Access and Timing

Question

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

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}