Pythonのスライシングが遅い話

slicing.py

# using:utf-8
import time

def test(n):
    start = time.time()
    xs = [None]*n
    while xs:
        xs = xs[1:]
    end = time.time()
    print("{}: {:.3f} sec".format(n, end-start))

# for i in range(1000, 100000, 1000):
#     test(i)

# 1000: 0.016 sec
# 2000: 0.018 sec
# 3000: 0.044 sec
# 4000: 0.078 sec
# 5000: 0.114 sec
# 6000: 0.152 sec
# 7000: 0.200 sec
# 8000: 0.327 sec
# 9000: 0.362 sec
# 10000: 0.448 sec
# 11000: 0.524 sec
# 12000: 0.597 sec
# 13000: 0.709 sec
# 14000: 0.805 sec
# 15000: 0.931 sec
# 16000: 1.066 sec
# 17000: 1.198 sec
# 18000: 1.343 sec
# 19000: 1.506 sec
# 20000: 1.654 sec
# 21000: 1.838 sec
# 22000: 2.013 sec
# 23000: 2.186 sec
# 24000: 2.386 sec
# 25000: 2.584 sec
# 26000: 3.261 sec
# 27000: 3.125 sec
# 28000: 3.230 sec
# 29000: 3.473 sec
# 30000: 3.719 sec
# 31000: 3.972 sec
# 32000: 4.236 sec
# 33000: 4.502 sec
# 34000: 4.777 sec
# 35000: 5.054 sec
# 36000: 5.336 sec
# 37000: 5.643 sec
# 38000: 5.956 sec
# 39000: 6.280 sec
# 40000: 6.619 sec

def test2(n):
    start = time.time()
    xs = [None]*n
    while xs:
        xs.pop()
    end = time.time()
    print("{}: {:.3f} sec".format(n, end-start))

# for i in range(1000, 100000, 10000):
#     test2(i)

# 1000: 0.000 sec
# 11000: 0.016 sec
# 21000: 0.000 sec
# 31000: 0.016 sec
# 41000: 0.014 sec
# 51000: 0.016 sec
# 61000: 0.033 sec
# 71000: 0.032 sec
# 81000: 0.026 sec
# 91000: 0.042 sec

def test3(n):
    start = time.time()
    xs = [None]*n
    while xs:
        xs = xs[:-1]
    end = time.time()
    print("{}: {:.3f} sec".format(n, end-start))

# for i in range(1000, 100000, 1000):
#     test3(i)

# 1000: 0.005 sec
# 2000: 0.021 sec
# 3000: 0.043 sec
# 4000: 0.076 sec
# 5000: 0.113 sec
# 6000: 0.150 sec
# 7000: 0.212 sec
# 8000: 0.283 sec
# 9000: 0.390 sec
# 10000: 0.442 sec
# 11000: 0.525 sec
# 12000: 0.596 sec
# 13000: 0.708 sec
# 14000: 0.828 sec
# 15000: 0.967 sec
# 16000: 1.086 sec
# 17000: 1.233 sec
# 18000: 1.380 sec
# 19000: 1.518 sec
# 20000: 1.681 sec
# 21000: 1.872 sec
# 22000: 2.043 sec
# 23000: 2.223 sec
# 24000: 2.432 sec
# 25000: 2.612 sec
# 26000: 2.840 sec
# 27000: 3.080 sec
# 28000: 3.257 sec
# 29000: 3.467 sec
# 30000: 3.719 sec

# tips
def func():
    xs = [0, 0, 0, 0, 0]
    ys = xs[1:]
    ys[0] = 1
    assert(ys == [1, 0, 0, 0])
    assert(xs == [0, 0, 0, 0, 0])
    assert(ys != xs[1:])