Accessing dictionary items by position in Python 3.6+ efficiently

by

For an OrderedDict it’s inherently O(n) because the ordering is recorded in a linked list.

For the builtin dict, there’s a vector (a contiguous array) rather than a linked list, but pretty much the same thing in the end: the vector contains a few kind of “dummies”, special internal values that mean “no key has been stored here yet” or “a key used to be stored here but no longer”. That makes, e.g., deleting a key extremely cheap (just overwrite the key with a dummy value).

But without adding auxiliary data structures on top of that, there’s no way to skip over the dummies without marching over them one at a time. Because Python uses a form of open addressing for collision resolution, and keeps the load factor under 2/3, at least a third of the vector’s entries are dummies. the_vector[i] can be accessed in O(1) time, but really has no predictable relation to the i’th non-dummy entry.

More Related Contents:

  1. Are dictionaries ordered in Python 3.6+?
  2. Is there anything faster than dict()?
  3. Why is a class __dict__ a mappingproxy?
  4. Accessing class variables from a list comprehension in the class definition
  5. How to return dictionary keys as a list in Python?
  6. Replace values in a pandas series via dictionary efficiently
  7. When is del useful in Python?
  8. How to merge multiple dicts with same key or different key?
  9. How does asyncio actually work?
  10. The `is` operator behaves unexpectedly with non-cached integers
  11. Why is dictionary ordering non-deterministic?
  12. Error: ” ‘dict’ object has no attribute ‘iteritems’ “
  13. How to save a dictionary to a file?
  14. Two variables in Python have same id, but not lists or tuples
  15. How do I format a string using a dictionary in python-3.x?
  16. One liner: creating a dictionary from list with indices as keys
  17. Get all keys of a nested dictionary [duplicate]
  18. Unpack dictionary from Pandas Column
  19. Updating a dictionary in python
  20. python is operator behaviour with string [duplicate]
  21. Creating an Ordered Counter
  22. Integer File Descriptor “0” in open()
  23. Will OrderedDict become redundant in Python 3.7?
  24. How to create a Python dictionary with double quotes as default quote format?
  25. Python – Printing a dictionary as a horizontal table with headers
  26. list comprehension filtering – “the set() trap”
  27. Improving performance of very large dictionary in Python
  28. How to convert string representation of dictionary in Pandas DataFrame to a new columns?
  29. How to convert only numbers in a mixed list into float
  30. TypedDict when keys have invalid names

Leave a Comment