Как именно Python проверяет список?

Я делал одно из курсовых упражнений по codeacademy для python, и у меня было несколько вопросов, на которые я не смог найти ответ:

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

Кроме того, как повлиял бы этот код, если бы он выполнялся с огромным списком чисел (тысяч или миллионов)? Будет ли он замедляться по мере увеличения размера списка, и есть ли лучшие альтернативы?

numbers = [1, 1, 2, 3, 5, 8, 13]

def remove_duplicates(list):
  new_list = []
  for i in list: 
    if i not in new_list:
      new_list.append(i)
  return new_list

remove_duplicates(numbers)

Спасибо!

PS Почему этот код не функционирует одинаково?

numbers = [1, 1, 2, 3, 5, 8, 13]

def remove_duplicates(list):
  new_list = []
  new_list.append(i for i in list if i not in new_list)
  return new_list
Источник

4 ответа

Решение

Для того, чтобы выполнить i not in new_list Python должен выполнить линейное сканирование списка. Цикл сканирования прерывается, как только результат теста известен, но если i на самом деле не в списке, весь список должен быть отсканирован, чтобы определить это. Он делает это на скорости C, поэтому он быстрее, чем цикл Python, явно проверяет каждый элемент. Делать случайные in some_list Тест в порядке, но если вам нужно сделать много таких тестов членства, гораздо лучше использовать set,

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

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

Конечно, если вы используете set тогда вы получаете дедупликацию бесплатно, так как невозможно добавить дубликаты в набор.

Одна проблема с множествами состоит в том, что они обычно не сохраняют порядок. Но вы можете использовать набор как вспомогательную коллекцию, чтобы ускорить дедупликацию. Вот иллюстрация одного из распространенных методов дедупликации списка или другой упорядоченной коллекции, которая сохраняет порядок. Я буду использовать строку в качестве источника данных, потому что мне лень печатать список.;)

new_list = []
seen = set()
for c in "this is a test":
    if c not in seen:
        new_list.append(c)
        seen.add(c)
print(new_list)

выход

['t', 'h', 'i', 's', ' ', 'a', 'e']

Посмотрите, как вы удаляете дубликаты из списка, сохраняя порядок? для большего количества примеров. Спасибо, Жан-Франсуа Фабр, за ссылку.

Что касается вашего PS, этот код добавляет один объект-генератор к new_list, он не добавляет то, что генерирует генератор.

Я полагаю, вы уже пытались сделать это с пониманием списка:

new_list = [i for i in list if i not in new_list]

Это не работает, потому что new_list не существует, пока не завершится работа списка компов, поэтому in new_list поднимет NameError, И даже если вы сделали new_list = [] перед списком comp, он не будет изменен списком comp, а результат списка comp просто заменит этот пустой объект списка новым.

Кстати, пожалуйста, не используйте list как имя переменной (даже в примере кода), так как это скрывает встроенный list типа, что может привести к загадочным сообщениям об ошибках.

Источник

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

Вы сканируете список по одному, что занимает 1 единицу работы. Это потому, что получение чего-либо из списка O(1), Если вы знаете индекс, его можно получить за 1 операцию.

Список, к которому вы собираетесь добавить его, увеличивается в худшем случае на 1 за раз. Так что в любой момент времени unique список предметов будет иметь размер n,

Теперь, чтобы добавить предмет, который вы выбрали в unique Список предметов собирается взять на работу в худшем случае. Потому что мы должны отсканировать каждый элемент, чтобы решить это.

Таким образом, если вы подытожите общую работу на каждом этапе, это будет 1 + 2 + 3 + 4 + 5 + ... n который n (n + 1) / 2, Так что если у вас есть миллион предметов, вы можете найти это, применив n = million в формуле.

Это не совсем верно из-за того, как list работает. Но теоретически это поможет визуализировать этот путь.

Источник

Чтобы ответить на вопрос в заголовке: Python имеет более эффективные типы данных, но list() Объект - это простой массив, если вы хотите более эффективный способ поиска значений, вы можете использовать dict() который использует хэш сохраненного объекта, чтобы вставить его в дерево, которое, как я полагаю, было тем, о чем вы подумали, когда упомянули "более быстрый процесс".

что касается второго фрагмента кода:list().append() вставляет любое значение, которое вы даете, в конец списка, i for i in list if i not in new_list является объектом генератора, и он вставляет этот генератор как объект в массив, list().extend() делает то, что вы хотите: он принимает итеративный и добавляет все свои элементы в список

Источник

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

Хорошо, допустим, у вас есть тысячи или миллионы номеров. Откуда именно? Допустим, они были сохранены в каком-то txtfile, тогда вы, вероятно, захотите использовать numpy (если вы придерживаетесь Python). Пример:

import numpy as np

numbers = np.array([1, 1, 2, 3, 5, 8, 13], dtype=np.int32)
numbers = np.unique(numbers).tolist()

Это будет более эффективным (прежде всего по сравнению с эффективным использованием памяти), чем чтение его с помощью Python и выполнение списка (set..)

numbers = [1, 1, 2, 3, 5, 8, 13]
numbers = list(set(numbers))
Источник
Другие вопросы по тегам