4
>>> timeit.timeit('test.append("test")', setup='test = []')
0.09363977164165221
>>> timeit.timeit('test[0] = ("test")', setup='test = {}')
0.04957961010914147

I even tried again with a loop, and same thing:

>>> timeit.timeit('for i in range(10): test.append(i)', setup='test = []')
1.3737744340367612
>>> timeit.timeit('for i in range(10): test[i] = i', setup='test = {}')
0.8633718070233272

Why is the list slower?

davidtgq
  • 3,780
  • 10
  • 43
  • 80
  • 2
    Perhaps you should ask yourself: Why are you expecting lists to be faster? – Wboy Oct 02 '16 at 03:04
  • 2
    @Wboy Why would I ask myself that? – davidtgq Oct 02 '16 at 03:05
  • @DavidTan Because you wrote "I expected lists to be faster". It could be easier to refute that specific expectation than answer something specific to the general python implementation here. – viraptor Oct 02 '16 at 03:34
  • Perhaps that was a mistake to type; it's completely unnecessary and irrelevant to my question. I take it back. My sincere apologies sir. – davidtgq Oct 02 '16 at 03:40

1 Answers1

4

First of all, list.append and dict.__setitem__ are both O(1) average case. Of course they will have different coefficients, but there is not really any blanket reason to say that one or the other will be the faster. The coefficients may change depending on implementation detail, too.

Secondly, a more fair comparison would be to remove the attribute resolution overhead:

>>> timeit.timeit('test[0] = ("test")', setup='test = {}')
0.0813908576965332
>>> timeit.timeit('test_append("test")', setup='test = []; test_append = test.append')
0.06907820701599121

The lookup of the method name on the instance is relatively expensive, when you are looking at an extremely cheap operation such as append.

I also see lists being consistently a little faster, once there is some data inside. This example is python 3.5.2:

>>> dict_setup = 'import random; test = {random.random(): None for _ in range(1000)}'
>>> list_setup = 'import random; test = [random.random() for _ in range(1000)]; test_append=test.append'
>>> timeit.timeit('test[0] = "test"', setup=dict_setup)
0.06155529400166415
>>> timeit.timeit('test_append("test")', setup=list_setup)
0.057089386998995906
wim
  • 338,267
  • 99
  • 616
  • 750
  • I tried running that, I'm getting 0.063 for [] and 0.047 for {}. But you're right, it did make an improvement from .append()'s 0.094. Though the question still remains, because lists are still slower (at least for me) – davidtgq Oct 02 '16 at 03:10
  • In response to the most recent edit, I'm still getting faster times from the dict_setup (0.056) than list_setup (0.061). Running Python 3.5.1, Intel Lynnfield, Windows x64 – davidtgq Oct 02 '16 at 03:27
  • Well, what can I say? You should explain your reason for expecting the `list.append` to be faster. I don't think it's a reasonable expectation. – wim Oct 02 '16 at 03:36