Reversing dictionary: time and space

Question

Assuming I have the following code, I have some questions.

>>> asd = {}
>>> asd[1] ='a'
>>> asd[2] = 'b'
>>> asd[3] = 'c'
>>> asd
{1: 'a', 2: 'b', 3: 'c'}

>>> dict((v,k) for k, v in asd.iteritems())
{'a': 1, 'c': 3, 'b': 2}

>>> if 'a' in asd:
    print("1")


>>> if 'a' in dict((v,k) for k, v in asd.iteritems()):
    print("1")
1

When I reverse a dictionary how much time will it take assuming my dictionary contains 10gb+ of data.

If I do not store the reversed dictionary to another dict then reversing it by itself as an instance will it consume space over memory?

I need the reversed dictionary because I want O(1) lookups over values, for some operations. Some others require key lookups.

Answer 1

Whenever you construct a new container object in Python, using its comprehension notation will be slightly faster than any other means. In this case, if you want to construct reverse-lookup dictionary, you can use dictionary comprehension, like this

d = {i: i * 2 for i in range(10000)}
from timeit import timeit
print timeit("{d[k]: k for k in d}", "from __main__ import d", number = 10000)
# 7.22010397911
print timeit("dict((v, k) for k, v in d.iteritems())", "from __main__ import d", number = 10000)
# 10.6085851192

For value lookups, I would recommend using dict.viewvalues like this

d = {i: i * 2 for i in range(10000)}
print 10 in d.viewvalues()
# True

But if the dictionary is not gonna change over time, then converting the values to a set would be a better option.

values_set = set(d.viewvalues())

Answer 2

When I reverse a dictionary how much time will it take assuming my dictionary contains 10gb+ of data.

The only valid answer is "run it and check it". It depends on your computer's architecture. From the theoretical point of view you need a linear time if the dict is hash-based and O(nlogn) if it is tree based.

If I do not store the reversed dictionary to another dict then reversing it by itself as an instance will it consume space over memory?

You will need temporarly the memory for both dicts, one of which will be discarded after the process (if you use the code provided). It would be however possible to make it without additonal memory by performing iterative process ("take first element from dict"; "remove it"; "add to new one")