функция питона замедляется без видимой причины

Question

У меня есть функция python, определенная следующим образом, которую я использую для удаления из списка1 элементов, которые уже находятся в списке2. Я использую Python 2.6.2 на Windows XP

def compareLists(list1, list2):
    curIndex = 0
    while curIndex < len(list1):
        if list1[curIndex] in list2:
            list1.pop(curIndex)
        else:
            curIndex += 1

Здесь list1 и list2 являются списками списков

list1 = [ ['a', 11221, '2232'], ['b', 1321, '22342'] .. ]

# list2 has a similar format.

Я пробовал эту функцию с list1 с 38 000 элементов и list2 с 150000 элементов. Если я вставлю оператор print для печати текущей итерации, я обнаружу, что функция замедляется с каждой итерацией. Сначала он обрабатывает около 1000 или более элементов в секунду, а затем через некоторое время уменьшается до 20-50 секунд. Почему это может происходить?

РЕДАКТИРОВАТЬ: в случае с моими данными curIndex остается 0 или очень близко к 0, поэтому операция pop в list1 почти всегда выполняется для первого элемента.

Если возможно, может ли кто-нибудь также предложить лучший способ сделать то же самое по-другому?

Answer 1

Попробуйте более питонический подход к фильтрации, что-то вроде

[x for x in list1 if x not in set(list2)]

Преобразование обоих списков в наборы несущественно, и будет очень медленным и потребует много памяти для больших объемов данных.

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

list2_set = set([tuple(x) for x in list2])
diff = [x for x in list1 if tuple(x) not in list2_set]

Я проверил вашу исходную функцию и мой подход, используя следующие данные теста:

list1 = [[x+1, x*2] for x in range(38000)]
list2 = [[x+1, x*2] for x in range(10000, 160000)]

Время - не научное, но все же:

 #Original function
 real    2m16.780s
 user    2m16.744s
 sys     0m0.017s

 #My function
 real    0m0.433s
 user    0m0.423s
 sys     0m0.007s

Answer 2

Есть 2 проблемы, из-за которых ваш алгоритм плохо масштабируется:

1. x in list - операция O (n).
2. pop(n) где n в середине массива - это операция O (n).

Обе ситуации приводят к плохому масштабированию O (n ^ 2) для больших объемов данных. Реализация gnud, вероятно, будет лучшим решением, поскольку она решает обе проблемы без изменения порядка элементов или удаления потенциальных дубликатов.

Answer 3

Единственная причина, по которой код может стать медленнее, заключается в том, что в обоих списках есть большие элементы, которые имеют много общих элементов (поэтому list1[curIndex] in list2 занимает больше времени).

Вот несколько способов исправить это:

• Если вам не важен порядок, конвертируйте оба списка в set s и используйте set1.difference(set2)

• Если порядок в списке1 важен, то по крайней мере конвертируйте list2 в набор, потому что in намного быстрее с set.

• Наконец, попробуйте фильтр: filter(list1, lambda x: x not in set2)

[EDIT] Поскольку set() не работает с рекурсивными списками (не ожидал этого), попробуйте:

result = filter(list1, lambda x: x not in list2)

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

Answer 4

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

Питон сидит в джакузи iowait , когда происходит такое замедление? Что-нибудь еще происходит в окружающей среде?

(Если вы не уверены, обновитесь с вашей платформой, и один из нас скажет вам, как это сделать.)

Answer 5

РЕДАКТИРОВАТЬ: я обновил свой ответ в учетной записи для списков, не подлежащих изменению, а также некоторые другие отзывы. Этот даже проверен.

Вероятно, это связано с затратами на извлечение предмета из середины списка.

В качестве альтернативы вы пытались использовать наборы для обработки этого?

def difference(list1, list2):
    return [x for x in list1 if tuple(x) in set(tuple(y) for y in list2)]

Затем вы можете установить список один в результирующий список, если вы этого хотите, выполнив

list1 = difference(list1, list2)

Answer 6

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

Вы можете

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