Python: List vs Dict for look up table

by

Speed

Lookups in lists are O(n), lookups in dictionaries are amortized O(1), with regard to the number of items in the data structure. If you don’t need to associate values, use sets.

Memory

Both dictionaries and sets use hashing and they use much more memory than only for object storage. According to A.M. Kuchling in Beautiful Code, the implementation tries to keep the hash 2/3 full, so you might waste quite some memory.

If you do not add new entries on the fly (which you do, based on your updated question), it might be worthwhile to sort the list and use binary search. This is O(log n), and is likely to be slower for strings, impossible for objects which do not have a natural ordering.

More Related Contents:

  1. Why is “1000000000000000 in range(1000000000000001)” so fast in Python 3?
  2. String formatting: % vs. .format vs. f-string literal
  3. When should I (not) want to use pandas apply() in my code?
  4. How to measure elapsed time in Python?
  5. Replace values in list using Python [duplicate]
  6. Pandas: peculiar performance drop for inplace rename after dropna
  7. Python threads all executing on a single core
  8. Get the second largest number in a list in linear time
  9. Speed of calculating powers (in python)
  10. Optimal HDF5 dataset chunk shape for reading rows
  11. Interactive large plot with ~20 million sample points and gigabytes of data
  12. Python – How to check list monotonicity
  13. Why “numpy.any” has no short-circuit mechanism?
  14. Fastest way to sort each row in a pandas dataframe
  15. Multiprocessing – Pipe vs Queue
  16. Vectorizing Haversine distance calculation in Python
  17. Numpy and line intersections
  18. Searching for a string in a large text file – profiling various methods in python
  19. High Memory Usage Using Python Multiprocessing
  20. Why is a `for` over a Python list faster than over a Numpy array?
  21. Performance: Matlab vs Python
  22. Creating an empty list in Python
  23. Dictionary vs Object – which is more efficient and why?
  24. time.time vs. timeit.timeit
  25. sum each value in a list of tuples
  26. Detecting thresholds in HSV color space (from RGB) using Python / PIL
  27. Looking for a fast way to find the polygon a point belongs to using Shapely
  28. Multiple matrix multiplication
  29. Which is the most efficient way to iterate through a list in python?
  30. Length of longest word in a list

Leave a Comment