I have a group of objects identified by unique (x,y) pairs and I want to
find out an object's "neighbors" in a matrix of size 2400 x 2400. [...]
There is either a neighbor, or a null value. I always know the (x,y)
pair to check the neighbors of, so is doing,
obj = grid[x][y] #lists, doesn't scale with num of objects or,
obj = grid.get((x,y),None) #dictionary, scales with num of objects
the fastest? I can't seem to find a conclusion by testing each alone,
then in the full environment. Is it that, depending on the number of
objects, each has an advantage?
Almost certainly not. Since you don't show how you test each, I have no
idea why you can't find a conclusion.
Let's start off with the question you don't ask: which uses less memory?
The answer is, the dict solution by far. Here is a test:
# populate a random matrix using both dict and list
adict = {}
alist = [[None]*2400 for i in range(2400)]
from random import randrange
for i in range(1000):
x = randrange(2400)
y = randrange(2400)
adict[(x, y)] = "something"
alist[x][y] = "something"
import sys
print(sys.getsizeof(adict))
print(sys.getsizeof(alist) + sum(sys.getsizeof(L) for L in alist))
The actual sizes printed will depend on how sparse the matrices are, but
for the same above (approximately half full), using Python 2.7, the
figures I get are:
adict: 24712
alist: 23127324
Now let's test the speed:
# randomly select matrix coordinates to look-up
test_coords = []
for i in range(1000):
x = randrange(2400)
y = randrange(2400)
test_coords.append((x, y))
# build some test code
from timeit import Timer
setup = "from __main__ import adict, alist, test_coords"
t1 = Timer("for p in test_coords: obj = adict.get(p)", setup)
t2 = Timer("for p in test_coords: obj = alist[p[0]][p[1]]", setup)
# run the test code
print(min(t1.repeat(number=10000, repeat=7)))
print(min(t2.repeat(number=10000, repeat=7)))
Again, on my system using Python 2.7, I get:
3.13823986053
2.97539305687
which shows that the two are very close, but the list solution is about
6% faster. So in this situation, a list of lists uses about 100 times
more memory than a dict, but look-ups are about 6% faster.
I would be very surprised if the timing results depended on the number of
objects in the matrices.
In case you are not familiar with timeit, let me explain what I have done:
* I pre-select 1000 random coordinates.
* I write some test code inside a Timer object that look up each of
those coordinates, plus some setup code.
* timeit runs the setup code once.
* Then it runs my test code 10000 times as a single trial, timing
it as accurately as possible.
* It does seven trials, and I report the best of the seven.
The time printed is measured in seconds. In this case, I get 3 seconds
per trial, or 3e-7 seconds = 0.3 microseconds per lookup.
I know the fastest way to retrieve them would be to have them store
pointers to their neighbors, then use those for retrieval.
How do you know that?
No offence, but if you can't even work out whether lookups in a dict or a
list are faster, I can't imagine why you think you can intuit what the
fastest way to retrieve the nearest neighbours would be.
