returning value from list vs dictionary

Question

I'm making a chess engine and for my piece square tables i can use lists or dictionaries. As the implementation of the piece square tables made the engine two times slower, i was wondering if i use the wrong data structure. I'm using lists, but am wondering if dictionaries might be a better idea?

List example:

list_ex = [50, 30, 30, 30
           20, 30, 50, 40]
call = list_ex[2]

Dictionary example:

dict_ex = {0: 50, 1: 30, 2: 30, 3: 30,
           4: 20, 5: 30, 6: 50, 7: 40}
call = dict_ex[2]

as you can see, i always know the index, i just need to return the value associated with that index. Which data structure would be faster for this, dictionaries or lists?

Answer 1

As you can see in the python wiki on TimeComplexity, list and dict they both have the same complexity in the average case on getting an item of O(1). So there should be not that much of a difference for simple index based look-ups.

EDIT: I just wrote a little benchmarking code that gets the first element, one from the center and the last. You see that a list has a small advance (although a deviation of 0.01s is not that large when considering that the code runs 1000000 times).

In summary I would use a list if I were in your situation, as it also fits better to the problem of an index based request.

>>> from timeit import Timer
>>> t=Timer("(l[0], l[3], l[7])","l=[50, 30, 30, 30, 20, 30, 50, 40]")
>>> sorted(t.repeat(5))
[0.17861513267149576, 0.17863279532627985, 0.17883092423682, 0.17892576501373014, 0.18901037296996037]
>>> t=Timer("(l[0], l[3], l[7])","l={0: 50, 1: 30, 2: 30, 3: 30, 4: 20, 5: 30, 6: 50, 7: 40}")
>>> sorted(t.repeat(5))
[0.18541179903735383, 0.1855488765975224, 0.1855757545505412, 0.18578041096390052, 0.21753940019925722]

Answer 2

You are better off using a list than a dict in terms of lookup speed. Tuple is even a bit faster.

timeit dict_ex[2]
10000000 loops, best of 3: 148 ns per loop

timeit list_ex[2]
10000000 loops, best of 3: 116 ns per loop

tuple_ex=tuple(list_ex)

timeit tuple_ex[2]
10000000 loops, best of 3: 112 ns per loop