0

There are 2 functions.

def f1(n):
    t = time()
    m = []
    for i in range(n):
        m.insert(0, 0)
    return time() - t

def f2(n):
    t = time()
    m = []
    for i in range(n):
        m[:0] = [0]
    return time() - t

They both insert many elements to list. But the second uses slice. I know that these algorithms are bad(because O(N^2)) but looks like f2 faster than f1(I tried both Python 2 and Python 3).

(You can see time here http://rextester.com/XSPGVO38315)

Is it random or there is a reson for which f2 is better than f1? Are these function equal? If no, what is better(faster)?

smci
  • 32,567
  • 20
  • 113
  • 146
moskalenco_a
  • 289
  • 1
  • 6
  • 6
    You should use the `timeit` module for benchmarking. – Barmar Feb 01 '18 at 00:50
  • 1
    Better is to not build a list by adding elements to the front in the first place. Append them to the end, and then reverse the list if you really need to. – Ned Batchelder Feb 01 '18 at 00:56
  • consider using `collections.deque` which has better `insert(0, v)` performance: https://stackoverflow.com/q/23487307/9209546 – jpp Feb 01 '18 at 00:58
  • So from the link @Barmar posted, the C implementation for slice seems to be faster, I think because of memmove instead of a loop. On my machine about 1.5X faster for 10k elements. – sbond Feb 01 '18 at 01:14
  • @Barmar, I tried with timeit and now time of f1 is almost equal to the time of f2. Thanks. – moskalenco_a Feb 01 '18 at 01:16

0 Answers0