Быстрее ли обрезать список, сделав его равным срезу, или используя del?

Предположим, у меня есть list TruncList с некоторым количеством элементов, превышающим n. Если я хочу удалить n элементов из конца этого списка, будет ли быстрее переопределить список как фрагмент самого себя, сохранив нужные элементы, как TruncList = TruncList[:-n], или удалить фрагмент нежелательных элементов из списка, как del TruncList[-n:]?

Изменится ли ответ, если я удалю первые n элементы из TruncList, как в случае TruncList = TruncList[n:] и del TruncList[:n]?

Помимо скорости, является ли один из этих методов более Pythonic, чем другой?

Я полагаю, что метод переопределения может быть медленнее, поскольку он перебирает TruncList, а затем переназначает его, в то время как del усекает список на месте, но я не уверен, что это так.

Я бы также предположил, что del - лучший маршрут, потому что это похоже на естественное использование функции.


person Augusta    schedule 22.03.2015    source источник
comment
Почему бы тебе не попробовать? См. модуль timeit.   -  person mhawke    schedule 22.03.2015
comment
@mhawke Это может быть лучший вопрос из всех. :v Я сделаю это сейчас.   -  person Augusta    schedule 22.03.2015
comment
@Augusta А затем отправьте ответ на свой вопрос с вашими результатами, чтобы будущие поколения узнали :)   -  person halex    schedule 22.03.2015
comment
@halex Я так и сделаю!   -  person Augusta    schedule 22.03.2015
comment
Зависит от того, что вы будете делать со списком потом. Если вы pop() каждый элемент, то это оставит список на месте с пустыми записями, которые можно использовать повторно. В CPython более эффективно всплывать справа. Последующие добавления в список будут использовать записи без изменения размера (при одинаковом количестве элементов или меньшем). Конечно, эффект производительности будет варьироваться в зависимости от размера списка. Удаление фрагмента слева будет означать изменение размера (перераспределение или эквивалент).   -  person cdarke    schedule 22.03.2015


Ответы (2)


Это будет полностью зависеть от сколько элементов вы удалите.

В CPython тип list использует стратегию динамического перераспределения, чтобы избежать слишком частого изменения размера базового массива C. Существует array для хранения элементов, и он всегда остается слишком большим.

Удаление (с использованием del TruncList[-n:]) может быть практически бесплатной операцией, при условии, что n достаточно мало. Фактически, вы можете безопасно удалить до половины размера перераспределенного массива до того, как произойдет изменение размера. Изменение размера требует копирования всех существующих ссылок в новый массив.

Использование фрагмента всегда приводит к созданию нового объекта списка, что требует выделения памяти и копирования задействованных элементов. Это немного больше работы, чем перераспределение данных.

Таким образом, без измерения производительности по времени (с использованием timeit) я ожидаю, что параметр del будет быстрее, чем нарезка; в случае n < len(TruncList) // 2 (менее половины длины) во многих случаях вы даже не подвергаетесь изменению размера, и даже если вы это сделали, необходимо выполнить немного меньше работы, поскольку необходимо воссоздать только внутренний массив.

Когда вы удаляете элементы спереди, вам всегда придется заново создавать внутренний массив. Тогда различия не будут резкими, но создание среза все равно приведет к выделению для совершенно нового объекта.

person Martijn Pieters    schedule 22.03.2015
comment
У меня есть список, который (по внешним причинам) содержит вдвое больше элементов, которые мне нужны (это пакеты из 3). Когда я хочу избавиться от дубликатов с помощью def deldup(al): for i in reversed(range(len(al))): if i%6>2: del al[i]; return al, это происходит почти мгновенно и не занимает памяти. когда я делаю def deldup(al): return [x for i,x in enumerate(al) if i%6>2], это занимает вечность и приводит к сбою моего компьютера из-за использования памяти (даже если я del(al)).... что я делаю неправильно во втором подходе? - person BUFU; 01.10.2020
comment
@BUFU ваше понимание списка копирует вторую половину (все 4-й, 5-й и 6-й элементы), где первая версия удаляет эти элементы, чтобы сохранить только первую половину. Я понятия не имею, насколько велик ваш вклад, но я ожидаю, что что-то еще будет отличаться от реализации deldup(), показанной здесь, чтобы иметь проблемы, подобные описанным вами. Извините, это не то, с чем я могу помочь в комментариях. - person Martijn Pieters; 02.10.2020
comment
да, я тоже пробовал i%6<3, разницы нет. Но все равно спасибо. Мне просто интересно, была ли какая-то очевидная глупость с моей стороны, которая привела к моей кончине. :D Тогда я просто пойду с del. - person BUFU; 02.10.2020

Поэтому я проверил это сам, используя timeit с этими образцами:

  ## Make a list of 500 elements and then remove the first 80...
def slice_front():
    "Make the list equal to all but the first eighty elements."
    trunc = 80
    TruncList = range(500)
    TruncList = TruncList[trunc:]

def del_front():
    "Use del to remove the first eighty elements."
    trunc = 80
    TruncList = range(500)
    del TruncList[:trunc]


  ## Make a list of 500 elements and then remove the last 80...
def slice_end():
    "Make the list equal to all but the last eighty elements."
    trunc = 80
    TruncList = range(500)
    TruncList = TruncList[:-trunc]

def del_end():
    "Delete the last eighty elements from the list using del."
    trunc = 80
    TruncList = range(500)
    del TruncList[-trunc:]

... и получил следующие результаты:

>>> timeit.timeit(slice_front, number = 66666)
1.3381525804258112
>>> timeit.timeit(del_front, number = 66666)
1.0384902281466895
>>> timeit.timeit(slice_end, number = 66666)
1.3457694381917094
>>> timeit.timeit(del_end, number = 66666)
1.026411701603827

Похоже, что del быстрее и с большим отрывом.


ИЗМЕНИТЬ

Если я запускаю те же образцы, но вместо этого с trunc = 2, это результаты:

>>> timeit.timeit(slice_front, number = 66666)
1.3947686585537422
>>> timeit.timeit(del_front, number = 66666)
1.0224893312699308
>>> timeit.timeit(slice_end, number = 66666)
1.4089230444569498
>>> timeit.timeit(del_end, number = 66666)
1.042288032264116

del еще быстрее.

Вот тест, в котором удалены почти все элементы списка: trunc = 80 и TruncList = range(81)...

>>> timeit.timeit(slice_front, number = 66666)
0.25171681555993247
>>> timeit.timeit(del_front, number = 66666)
0.2696609454136185
>>> timeit.timeit(slice_end, number = 66666)
0.2635454769274057
>>> timeit.timeit(del_end, number = 66666)
0.294670910710936

В этом случае del несколько медленнее, чем метод переопределения.

person Augusta    schedule 22.03.2015
comment
Вы удаляете гораздо меньше половины элементов, поэтому (внутреннее) изменение размера не происходит. - person Martijn Pieters; 22.03.2015
comment
@MartijnPieters Я подумал, что задействованные длины могут иметь какое-то отношение к этому сразу после того, как я опубликовал первый набор чисел, поэтому я провел еще несколько тестов с другими параметрами. Примерно так, как вы говорите. - person Augusta; 22.03.2015
comment
Время было бы лучше, если бы вы могли заранее создать списки тестов; создайте N списков одинакового размера для N timeit тестов и заставьте каждый тест обрезать один из этих объектов. Это лучше проиллюстрирует разницу между ними. - person Martijn Pieters; 22.03.2015
comment
@MartijnPieters Я пересмотрю метод, чтобы отразить это сейчас, спасибо! - person Augusta; 22.03.2015
comment
На самом деле довольно сложно заставить внешние значения работать с timeit. :s Я забрал эту штуку всего полчаса назад, так что это может занять некоторое время... - person Augusta; 22.03.2015
comment
Вы можете использовать from __main__ import ... в аргументе настройки (второй аргумент для timeit для импорта имен из интерактивного интерпретатора, а затем использовать строку для первого аргумента для использования этих имен. Например, from __main__ import slice_front as test, long_list_of_lists; testdata = iter(long_list_of_lists), а первым аргументом может быть test(next(testdata)) для передачи в каждом элемент от long_list_of_lists до slice_front на каждой итерации запуска timeit. - person Martijn Pieters; 22.03.2015
comment
@MartijnPieters В этом случае будет ли long_list_of_lists содержать новый список для каждого цикла, который timeit ожидает запуска? Что в данном наборе тестов эквивалентно long_list_of_lists = [[range(500) * 66666]? Если да, то это действительно очень длинный список списков! - person Augusta; 22.03.2015
comment
Да, в том-то и дело, что вы уничтожаете списки. Используйте меньший аргумент number, чтобы ограничить количество тестов. - person Martijn Pieters; 22.03.2015
comment
@MartijnPieters Можно ли также использовать testdata = iter([range(500)] * cycles и изменить setup timeit.timeit(..) на "from __main__ import slice_front as test, testdata, ..", или это будет мешать таймеру, поскольку итератор каждый раз создает новый range вместо того, чтобы извлекать его из существующего list? - person Augusta; 22.03.2015
comment
Вы можете сделать это; хотя весь список по-прежнему создается заранее. Понимание списка выполняется сначала перед вызовом iter(). - person Martijn Pieters; 22.03.2015
comment
Хорошо знать! Я немного обновлю это. У меня есть версия, построенная в соответствии с вашим примером, которая работает лишь в небольшой части времени. - person Augusta; 22.03.2015