Всегда ли вложенные циклы работают медленно?

Question

Кажется, есть довольно много вопросов и ответов, связанных со скоростью вложенных циклов for - думаю, я просмотрел каждый из них! Но, к сожалению, я до сих пор не совсем понимаю, почему мой код работает медленно. Я надеюсь, что смогу получить рекомендации от вас, прекрасные люди.

Я ежедневно скачиваю CSV-файл, содержащий ~116000 записей. Элементы добавляются и удаляются из него в несогласованных местах файла, поэтому каждый день я хочу видеть, что было добавлено, а что убрано.

Получение записей из csv в список совсем не требует времени, как для старого, так и для нового списка, но я сталкиваюсь с большим снижением скорости в следующей части кода, хотя в конце он делает то, что я хочу, и выплевывает разница - элементы добавлены и элементы удалены.

Каждый из 116000 элементов в списке представляет собой словарь, например:

old or new = [{'Date Stamped': '', 'Name': '', 'Registration Number': '', 'Type': '', "Form Name':  '', 'URL': "}]

когда я дойду до этой точки:

added = [i for i in new if not i in old]
removed = [i for i in old if not i in new]

Это займет 25 минут! Мне кажется, что это надолго, но я также могу не понимать, что именно делаю.

Каждый список (старый и новый) содержит ~ 116000 пунктов. Это потому, что мне нужно перебрать ~116000 элементов 4 раза?

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

Это медленно, потому что это вложенный цикл for? Это медленно из-за размера? Я определенно любитель и очень ценю помощь каждого. Спасибо.

Answer 1

Фактически да, это медленно, потому что это вложенный цикл for из- за размера.

Python element in listоперация работает, просто просматривая весь список, элемент за элементом, в поисках нужного. Если вам нужно сделать это для каждого элемента вnew, это означает, что вы, возможно, ищете весь old для каждого элемента в new.

Списки не являются хорошей структурой данных для поиска. Вместо этого, если у вас есть такой вариант использования, вы должны преобразовать их вsetсначала - неупорядоченная коллекция (но порядок, вероятно, не имеет значения), которая использует хеш-таблицу для определения наличия в ней элементов. Теперь вместо поиска по всей структуре данных элемент за элементом он может просто хешировать искомый элемент, проверять, есть ли там элемент, и сообщать об этом, если это так.

Другими словами, element in set на порядок эффективнее, чем element in list. За относительно небольшие накладные расходы (при созданииsetS в первую очередь), это бреет огромное количество времени прочьfor петли, которые последуют:

old_set = set(old)
new_set = set(new)
added = [i for i in new if not i in old_set]
removed = [i for i in old if not i in new]

Более того, вы даже можете отказаться от понимания списка, потому что set поддерживает операции из теории множеств - взять разницу между двумя наборами (элементы в одном наборе, которых нет в другом) так же просто, как вычесть их:

added = list(new_set - old_set)  # (new_set - old_set) is identical to new_set.difference(old_set)
removed = list(old_set - new_set)

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