Reputation: 640
Suppose I have an approximately 1280 by 800 two dimensional array, and I want to be able to store approximately 4KiB of data in some array slots. (Maybe a couple of hundred?)
What are the memory usage/CPU time/code complexity trade-offs for using a Python list
or dict
?
A quick example for storing "blob.." at (123,456).
coord = (123, 456)
L = []
L[to_index(coord)] = "blob.."
# to_index() probably returns (456*1280) + 123
or
coord = (123, 456)
D = {}
L[coord] = "blob.."
Upvotes: 1
Views: 389
Reputation: 134731
Lists won't be particularly efficient for storing this data, because you take no advantage in the fact that it's sparse. Basically you'd have to create a list of 1024000 elements, initially set to None
. Internally it'd be a vector or 1024000 pointers, 8-bytes each on 64-bit system. Once this list is created, accessing and setting particular cell will be O(1) operation.
OTOH, dictionary is implemented as hash table. So you'll only need space for elements you've inserted. If you're dealing with sparse data it's better option. Inserts have amortized cost of O(1), access is obviously O(1) also.
You can read more about these datastructures in PyCon presentation "Core Python Containers: under-the-hood" (PPT) (also available as video)
Upvotes: 4