Блог

Я написал базовые фрагменты python, чтобы сначала вставить значения в список, а затем поменять их местами. Я обнаружил, что существует огромная разница в скорости выполнения между методами insert и append.

Фрагмент 1:

 L = []
for i in range(10**5):
 L.append(i)
L.reverse()
  

Время, затраченное на выполнение этого :

 real    0m0.070s
user    0m0.064s
sys         0m0.008s
  

Фрагмент 2:

 l = []
for i in range(10**5):
 l.insert(0,i)
  

Время, затраченное на выполнение:

 real    0m5.645s
user    0m5.516s
sys         0m0.020s
  

Я ожидал, что фрагмент 2 будет работать намного лучше, чем фрагмент 1, поскольку я выполняю обратную операцию напрямую, вставляя числа раньше. Но затраченное время говорит об обратном. Я не понимаю, почему последний метод требует больше времени для выполнения, хотя метод выглядит более элегантно. Есть ли у кого-нибудь какое-либо объяснение этому?

Вот полный ответ от Дункана Бута:

Список реализуется массивом указателей на объекты, которые он содержит.

Каждый раз, когда вы вызываете ‘insert (0, indx)’, все указатели, уже находящиеся в списке, должны быть перемещены на одну позицию вверх, прежде чем новый можно будет вставить в начало.

Когда вы вызываете ‘append (indx)’, указатели нужно копировать только в том случае, если в текущем выделенном блоке недостаточно места для нового элемента. Если есть свободное место, то нет необходимости копировать существующие элементы, просто поместите новый элемент в конец и обновите поле длины. Всякий раз, когда необходимо выделить новый блок, это конкретное добавление будет не быстрее, чем вставка, но будет выделено некоторое дополнительное пространство на случай, если вы захотите расширить список дальше.

Если вы ожидали, что вставка будет быстрее, возможно, вы подумали, что Python использует реализацию связанного списка. Он этого не делает, потому что на практике (для большинства приложений) реализация на основе списков обеспечивает лучшую производительность.

На самом деле мне больше нечего добавить.

Обратите внимание, что ваши результаты будут зависеть от точной реализации Python. cpython (и pypy) автоматически изменяют размер вашего списка и расширяют пространство для будущих добавлений и тем самым ускоряют append дальнейшую работу.

Внутренне списки — это просто фрагменты памяти с постоянным размером (в куче). Иногда вам повезло, и вы можете просто увеличить размер фрагмента, но во многих случаях объект уже будет там. Например, предположим, что вы выделили фрагмент размером 4 для списка [a,b,c,d] , а какой-то другой фрагмент кода выделил фрагмент размером 6 для словаря:

 Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
       |a b c d| | dictionary |
  

Предположим, что ваш список состоит из 4 элементов, и добавляется еще один. Теперь вы можете просто изменить размер списка до размера 5:

 Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
       |a b c d e| dictionary |
  

Однако, что вы делаете, если вам нужен другой элемент сейчас?

Ну, единственное, что вы можете сделать, это получить новое пространство и скопировать содержимое списка.

 Memory 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
                | dictionary |a  b  c  d  e  f |
  

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

Напротив, когда вы вставляете в позицию 0, вам всегда нужно копировать свой список. Давайте вставим x :

 Memory  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
orig   |a b c d| |dictionary|
after  |x a b c d|dictionary|
  

Хотя в конце было достаточно места для добавления x, нам пришлось переместить (даже не копировать, что может быть дешевле в памяти) все остальные значения.

Если вам нужна структура данных, которая так же эффективна при вставке в начале, как и при добавлении, тогда вам следует рассмотреть deque.

Я научился вставлять x в начало списка в «Python Pocket Reference»:

 l[:0] = [x]
  

Это должно быть как-то очень похоже на l.insert(0, x), но когда я пытаюсь сравнить три варианта: append(x), insert(0, x) и l[:0] = [x], последний вариант выполняется немного быстрее, чем второй.

Вот тестовый код и результат

 import time
def test():
    n = 10**5


    t0 = time.time()
    l = []
    for i in xrange(n): l.append(i)
    t1 = time.time() - t0
    print 'appending: %.5f' % t1


    t0 = time.time()
    l = []
    for i in xrange(n): l.insert(0, i)
    t2 = time.time() - t0
    print 'insert to 0: %.5f' % t2

    t0 = time.time()
    l = []
    for i in xrange(n): l[:0] = [i]
    t3 = time.time() - t0
    print 'set slice: %.5f' % t3

    return t1, t2, t3


if __name__ == '__main__':
    t = [0] * 3
    ntimes = 10

    for _ in xrange(ntimes):
        ti = test()

        for i in xrange(3):
            t[i]  = ti[i]

    t = [i/ntimes for i in t]
    print 'average time:', t
  

среднее время

 [0.011755657196044923, 4.1943151950836182, 3.3254094839096071]
  

Почему это примерно на 25% быстрее, чем вставка (0, x)? Я попытался поменять местами блок кода для оценки t1, t2, t3, но результат тот же, так что речь идет не о кэшировании списка.

Здесь указано, что для настройки фрагмента требуется O (k n)

Вставить метод, соответствующим образом реализуемый в очереди. Операция FIFO, вставляется в начало списка. пример :. items.insert(0,item)

Метод добавления соответствующим образом реализуется в стеке. Операция LIFO, вставки в конце списка. пример :. items.append(элемент)

Когда мы используем insert data через метод INSERT, убедитесь, что все индексы повторно упорядочены.

https://wiki .python.org/moin/TimeComplexity проверьте здесь, чтобы увидеть все методы для списка и его временную сложность