Return value from list to dictionary

Question

I make a chess engine, and for my square square tables I can use lists or dictionaries. Since the implementation of square square tables made the engine run twice as slow, I was wondering if I was using the wrong data structure. I use lists, but I wonder if dictionaries could 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 this index. Which data structure will be faster for this, dictionaries or lists?

Answer 1

As you can see in the python wiki TimeComplexity , list and dict , they both have the same complexity in the average case of getting an O (1) element. So there shouldn't be that much difference for simple index based indexes.

EDIT: I just wrote a little benchmarking that gets the first element, one from the center and the last. You can see that the list has little progress (although the deviation of 0.01 s is not so great considering that the code works 1,000,000 times).

In conclusion, I would use a list if I were in your situation, as it is also better suited to the index-based query problem.

 >>> 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 dict in terms of search speed. Tuple is even a little 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 

Answer 3

You can easily compare this with the timeit module ( python -m timeit -S "setup" -- "statement" ). But in this case, I can say that dictionaries will not beat lists, because list search is trivial compared to search by query. Both will be fast, independent of the key and the number of elements in the collection, but the list will win micro-tests. Of course, this should not make a decision. Go for clarity, optimize algorithms instead of minor details, premature optimization, etc. Ad nauseam.

But I still think that the list is more appropriate, both semantically (you do not have a free form display, you have a sequence), and to prevent errors (by deviating out of range and a non-integer index).

Answer 4

Python will generally be slow for something like this.

Take a look at this other SO question , first answer.

I would say that it is best to use tuples if your object can be immutable. If not, stick to the lists. In any case, there will not be much difference between list and dict .

I see that halex also answered and seems to agree.