6

I have a dictionary such as:

d = {'a':'a-val', 'b':'b-val', 'c':'c-long-val'*1000}

And I need to repeatedly access d['c'] as in:

print('value of c is', d['c'])
x_queue.put(d['c'])
some_function(d['c'])

But I'm wondering if it would be faster to assign d['c'] to a variable and use it each time:

c_value = d['c']` # is this assignment "worth it"?
print('value of c is', c_value)
x_queue.put(c_value)
some_function(c_value)

My hunch is it may depend on

  • number of elements in d (finding key is more costly with bigger d)
  • size of d['c'] (assignment is more costly with bigger d['c'])

But I'm really not sure if one of those options (or another?) is faster or more pythonic.

Dan Pittsley
  • 143
  • 7
  • Just try, measure and decide... – Thierry Lathuille Sep 06 '19 at 16:03
  • Thanks, I could (and will) try and measure for my specific case, but I still would like to know *why* one turns out better - if it does. Are my assumptions of the cost tradeoffs above correct? – Dan Pittsley Sep 06 '19 at 16:11
  • In almost all languages, getting a value from a variable is usually faster than retrieving it from a container. – Barmar Sep 06 '19 at 16:11
  • One just reads from a memory location, the other has to perform some extra calculation. – Barmar Sep 06 '19 at 16:12
  • There are some exceptions, like variables in closures, which need to go through activation records. – Barmar Sep 06 '19 at 16:13
  • For hunch #1: the size of the dict doesn't really matter, the only thing that can make access slower would be collisions in the hash table. For hunch #2: No copy takes place, your variable is just a new name for the object it refers to, so again the size doesn't matter. For #1, you can have a look at https://stackoverflow.com/questions/43690191/why-are-dict-lookups-always-better-than-list-lookups – Thierry Lathuille Sep 06 '19 at 16:29

2 Answers2

1

Although accessing a dict value by key has an average time complexity of O(1), it has a worst-case time complexity of O(n) after incurring the overhead of calculating the hash value of the key. A variable assignment and the retrieval of its value on the other hand, take very minimal, constant time, so avoid re-evaluating a dict value by key whenever possible.

blhsing
  • 91,368
  • 6
  • 71
  • 106
  • 1
    They're both O(1), but hashing has a larger coefficient. – Barmar Sep 06 '19 at 16:13
  • Again, when I mentioned *O(n)* I was talking about the *worst-case* time complexity for the retrieval of a value from the dict heap after calculating the hash value. – blhsing Sep 06 '19 at 16:15
  • In other words, you're confusing hashing (which takes *O(1)*) with hash collision resolution (which takes *O(n)* in worst case). – blhsing Sep 06 '19 at 16:28
  • 1
    Big-O notation is the wrong thing to worry about here. Ignoring collision resolution, calculating a hash value is still much slower than reading a variable. – Barmar Sep 06 '19 at 16:31
0

The keys are hashed in a dictionary. So when you ask for d['c'], a hash is calculated first and then the corresponding value found. Lot more steps then a simple assignment.

Neeraj Agarwal
  • 1,059
  • 6
  • 5