CODEWITHSUNDEEP
python
coiax
coiax

Reputation: 640

Memory, CPU, complexity tradeoffs for Python dict v. list with large 2D arrays

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

Answers (1)

vartec
vartec

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

Related Questions