Блог

Главная - Вопросы по программированию - Добавить в Python не в O (1)

Добавить в Python не в O (1)

#python

#python

Вопрос:

Я пытаюсь отслеживать сложность в списках Python. Итак, я написал приведенный выше сценарий, думая, что у меня будет сложность O (1) для вставки элемента в конце и сложность O (n) для вставки в начале, как написано здесь

 import time

for p in [3,4,5,6,7]:

    n = 10**p
    print("n =", n, ":")
    
    # Creation of a list [0, 1, ..., n]
    li = list(range(n))
    
    start = time.perf_counter()
    # Adding item at the end
    li.append('a')
    stop = time.perf_counter()
    duration = round((stop - start)*1000, 3)
    
    print("Time for insertion at the end :", duration, "ms")
    
    start = time.perf_counter()
    # Adding item at the beginning
    li.insert(0,'a')
    stop = time.perf_counter()
    duration = round((stop - start)*1000, 3)

    print("Time for insertion at the beginning :", duration, "ms")
    print()

И результат :

 n = 1000 :
Time for insertion at the end : 0.001 ms
Time for insertion at the beginning : 0.001 ms

n = 10000 :
Time for insertion at the end : 0.003 ms
Time for insertion at the beginning : 0.007 ms

n = 100000 :
Time for insertion at the end : 0.036 ms
Time for insertion at the beginning : 0.098 ms

n = 1000000 :
Time for insertion at the end : 0.05 ms
Time for insertion at the beginning : 1.001 ms

n = 10000000 :
Time for insertion at the end : 0.257 ms
Time for insertion at the beginning : 11.453 ms

Итак, вставка в начале явно O (n), но вставка в конце явно не O (1) .

Кто-нибудь может мне это объяснить?

конфигурация: Python 3.8.5 на Ubuntu 20.04.1 LTS

Итак, я попробовал с timeit (как было предложено), и результаты такие, какими они должны быть.

в начале O (n):

 >>> timeit.timeit("liste.insert(0,'a')",setup='liste = list(range(10**3))', number=1000)
0.0012012630177196115
>>> timeit.timeit("liste.insert(0,'a')",setup='liste = list(range(10**4))', number=1000)
0.008087130001513287
>>> timeit.timeit("liste.insert(0,'a')",setup='liste = list(range(10**5))', number=1000)
0.06115017700358294
>>> timeit.timeit("liste.insert(0,'a')",setup='liste = list(range(10**6))', number=1000)
1.0330771339940839
>>> timeit.timeit("liste.insert(0,'a')",setup='liste = list(range(10**7))', number=1000)
11.236097862012684

в конце O (1):

 >>> timeit.timeit("liste.append('a')",setup='liste = list(range(10**3))', number=1000000)
0.05697788399993442
>>> timeit.timeit("liste.append('a')",setup='liste = list(range(10**4))', number=1000000)
0.05759519099956378
>>> timeit.timeit("liste.append('a')",setup='liste = list(range(10**5))', number=1000000)
0.05135001099552028
>>> timeit.timeit("liste.append('a')",setup='liste = list(range(10**6))', number=1000000)
0.0584335429884959
>>> timeit.timeit("liste.append('a')",setup='liste = list(range(10**7))', number=1000000)
0.04910806700354442

Поскольку timeit выполняет настройку только один раз, он добавляет один элемент снова и снова в один и тот же список.

Итак, я попробовал это:

 import time

for p in [3,4,5,6,7]:
    
        n = 10**p
        print("n =", n, ":")
        
        # Creation of a list [0, 1, ..., n]
        li = list(range(n))
        
        for j in range(3):
            start = time.perf_counter()
            # Adding item at the end
            li.append('a')
            stop = time.perf_counter()
            duration = round((stop - start)*1000, 3)
            
            print("Time for insertion at the end :", duration, "ms")
        

        for j in range(3):
            start = time.perf_counter()
            # Adding item at the beginning
            li.insert(0,'a')
            stop = time.perf_counter()
            duration = round((stop - start)*1000, 3)

            print("Time for insertion at the beginning :", duration, "ms")
        
        print()

и результаты:

 n = 1000 :
Time for insertion at the end : 0.004 ms
Time for insertion at the end : 0.0 ms
Time for insertion at the end : 0.0 ms
Time for insertion at the beginning : 0.001 ms
Time for insertion at the beginning : 0.001 ms
Time for insertion at the beginning : 0.001 ms

n = 10000 :
Time for insertion at the end : 0.002 ms
Time for insertion at the end : 0.0 ms
Time for insertion at the end : 0.0 ms
Time for insertion at the beginning : 0.007 ms
Time for insertion at the beginning : 0.006 ms
Time for insertion at the beginning : 0.006 ms

n = 100000 :
Time for insertion at the end : 0.042 ms
Time for insertion at the end : 0.001 ms
Time for insertion at the end : 0.001 ms
Time for insertion at the beginning : 0.113 ms
Time for insertion at the beginning : 0.099 ms
Time for insertion at the beginning : 0.087 ms

n = 1000000 :
Time for insertion at the end : 0.064 ms
Time for insertion at the end : 0.001 ms
Time for insertion at the end : 0.001 ms
Time for insertion at the beginning : 1.362 ms
Time for insertion at the beginning : 1.144 ms
Time for insertion at the beginning : 0.943 ms

n = 10000000 :
Time for insertion at the end : 0.336 ms
Time for insertion at the end : 0.002 ms
Time for insertion at the end : 0.001 ms
Time for insertion at the beginning : 15.727 ms
Time for insertion at the beginning : 15.441 ms
Time for insertion at the beginning : 13.837 ms

Так что это просто «первый доступ» к списку, который занимает некоторое дополнительное время. Если я изменю порядок, дополнительное время будет потрачено на вставку в начале.

Тем не менее, мое любопытство не удовлетворено. Почему существует эта задержка, которая зависит от размера списка, при первом доступе? (извините за длинный пост)

Комментарии:

1. Вы используете insert not append , прочитайте вашу ссылку еще раз, insert это O (n), 5-я строка таблицы

2. … и прочитайте сноску [1]

3. Также я бы сказал, что вы не можете подсчитать связь для 1 операции, это так зависит от другой вещи, подсчитайте время последовательных вставок 1k, 1m и 1g, тогда у вас может быть хорошее среднее время

4. @azro Они использовали как append, так и insert .

5. Не могли бы вы дать нам несколько подробностей, версию Python, ОС, спецификации? Поскольку, запуская этот код, я получаю довольно четкое поведение O (1) для добавления.

Ответ №1:

Размер списков в Python является динамическим. Однако не все добавления имеют одинаковую стоимость из-за способа работы с динамическим списком.
Изначально для списка выделяется фиксированное пространство. Когда выделенное пространство заполнено, и мы хотим добавить элемент, для списка выделяется новое пространство, в два раза превышающее предыдущее пространство, и все элементы списка копируются в новое местоположение. Поэтому, если выделенное пространство не заполнено, для добавления требуется O (1), но если выделенное пространство заполнено, требуется O (n) (потому что сначала нам нужно скопировать).

Стоимость добавления n элементов (при условии, что изначально выделено две единицы пространства):

   (1)   (1)    # costs of appending the first two items
  (2 1)   (1)  # costs of appending the next two items
  (4 1)   (1)   (1)   (1)  # costs of appending the next four items
  (8 1)   (1)   (1)   (1)   (1)   (1)   (1)   (1) # costs of appending the next eight items
  (16 1)   (1)   (1)   (1)   (1)   (1)   (1)   (1)   (1)   (1)   (1)   (1)   (1)   (1)   (1)   (1)
  (32 1)   ...
...

Это равно 2 4 8 16 ... n примерно 2n. Таким образом, n append операций стоят в общей сложности 2n. Так что в среднем каждый стоит O(1) . Это называется амортизированной стоимостью.