Эффективное сокращение списка в python

Question

Итак, у меня есть список из 85 предметов.Я хотел бы постоянно сокращать этот список вдвое (по сути, бинарный поиск по элементам) - тогда мой вопрос, каков наиболее эффективный способ сокращения списка?Понимание списка будет постоянно создавать копии списка, что не идеально.Я хотел бы удалить диапазоны из моего списка до тех пор, пока у меня не останется один элемент.

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

Answer 1

По правде говоря, всего для 85 предметов практически любой метод, который вы хотите использовать, будет более чем достаточно быстрым.Не оптимизируйте преждевременно.

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

Со списком, если вы хотите скопировать или удалить непрерывный диапазон элементов (скажем, первые 42), вы можете сделать это с помощью среза.Предполагая, что половина списка удаляется при каждом проходе, копирование элементов в новый список будет в среднем медленнее, чем удаление элементов из существующего списка (удаление требует перемещения половины списка, который не удаляется, «влево» в памяти, что будетпримерно столько же времени, сколько копирование другой половины, но вам не всегда нужно это делать; при удалении второй половины списка не нужно ничего перемещать).

Чтобы сделать это с помощью deque эффективно, вы бы хотели pop() или popleft() элементы, а не разрезать их (много доступа к атрибутам и вызовам методов, которые относительно дороги в Python), и вам нужно было бы написать цикл, который контролируетоперация в Python, которая будет медленнее, чем операция с собственным слайсом.

Поскольку вы сказали, что это в основном бинарный поиск, возможно, быстрее всего будет просто найти элемент, который вы хотите сохранить, без изменения исходного контейнера вообщеи затем верните новый контейнер, содержащий этот единственный элемент.list будет быстрее для этого, чем deque, так как вы будете делать много доступа к элементам по индексу.Для этого в deque потребуется, чтобы Python следовал за связанным списком с самого начала каждый раз, когда вы обращаетесь к элементу, тогда как доступ к элементу по индексу - это простой и быстрый расчет для list.

Answer 2

1. 85 предметов даже не стоит думать.Компьютеры действительно быстрые.
2. Зачем вам удалять диапазоны из списка, вместо простого выбора одного результата?
3. Если есть веская причина, по которой вы не можете это сделать (2): Сохранитьисходный список и измените только два индекса: начальный и конечный индексы подсписка, который вы просматриваете.

Answer 3

Не уверен, что это то, что вам действительно нужно, но:

x = range(100)
while len(x) > 1:
    if condition:
        x = x[:int(len(x)/2)]
    else:
        x = x[int(len(x)/2):]

Answer 4

collections.deque реализуется через связанный список, поэтому двоичный поиск будет намного медленнее, чем линейный поиск. Переосмыслите свой подход.

Answer 5

По предыдущему вопросу я сравнил несколько методов удаления списка элементов с заданным предикатом.(То есть у меня есть функция, которая возвращает True или False, чтобы сохранить определенный элемент.) Насколько я помню, использование списка было самым быстрымДело в том, что копирование действительно очень дешево.

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