Two-dimensional vs. One-dimensional dictionary efficiency in Python

What is more efficient in terms of memory and speed between

d[(first,second)]

and

d[first][second],

where d is a dictionary of either tuples or dictionaries?

Answers


Here is some very basic test data that indicates that for a very contrived example(storing 'a' a million times using numbers as keys) using 2 dictionaries is significantly faster.

$ python -m timeit 'd = {i:{j:"a" for j in range(1000)} for i in range(1000)};a = [d[i][j] for j in range(1000) for i in range(1000)];'
10 loops, best of 3: 316 msec per loop
$ python -m timeit 'd = {(i, j):"a" for j in range(1000) for i in range(1000)};a = [d[i, j] for j in range(1000) for i in range(1000)];'
10 loops, best of 3: 970 msec per loop

Of course, these tests do not necessarily mean anything depending on what you are trying to do. Determine what you'll be storing, and then test.

A little more data:

$ python -m timeit 'a = [(hash(i), hash(j)) for i in range(1000) for j in range(1000)]'
10 loops, best of 3: 304 msec per loop
$ python -m timeit 'a = [hash((i, j)) for i in range(1000) for j in range(1000)]'
10 loops, best of 3: 172 msec per loop
$ python -m timeit 'd = {i:{j:"a" for j in range(1000)} for i in range(1000)}'
10 loops, best of 3: 101 msec per loop
$ python -m timeit 'd = {(i, j):"a" for j in range(1000) for i in range(1000)}'
10 loops, best of 3: 645 msec per loop

Once again this is clearly not indicative of real world use, but it seems to me like the cost of building a dictionary with tuples like that is huge and that's where the dictionary in a dictionary wins out. This surprises me, I was expecting completely different results. I'll have to try a few more things when I have time.


Need Your Help

Using Instrumentation to record unhandled exception

java aspectj instrumentation javaagents

I was trying to debug java application using instrumentation. The problem with current system are

Is placing script tag before </body> tag equivalent to jQuery's document.ready method

javascript jquery

If we call a javascript method myMethod() in a script tag which is before closing body, is it equivalent to calling myMethod() inside jQuery's document.ready function ? If not, Why ?