Эффективная альтернатива "в"

Question

Я пишу сканер с конечной целью - создать карту пути, по которому прошел сканер.Хотя я и понятия не имею, с какой скоростью работают другие, и, безусловно, более совершенные сканеры сбрасывают страницы, у меня тактовая частота составляет около 2000 страниц в минуту.

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

for href in tempUrl:
    ...
    if href not in urls:
         collect(href,parent,depth+1)

Этот метод, кажется, становится проблемой, когда его объем составляет около 300 000 страниц.На данный момент сканер в среднем работает со скоростью 500 страниц в минуту.

Итак, мой вопрос: каков еще один метод достижения той же функциональности при одновременном повышении ее эффективности?

Я подумал, что может помочь уменьшение размера каждой записи, поэтому вместо добавленияВесь URL, я добавляю первые 2 и последние к символам каждого URL в виде строки.Это, однако, не помогло.

Есть ли способ, которым я мог бы сделать это с сетами или что-то в этом роде?

Спасибо за помощь

edit: Как примечание,моя программа еще не многопоточная.Я решил, что должен устранить это узкое место, прежде чем приступить к изучению потоков.

Answer 1

Возможно, вы могли бы использовать set вместо list для URL, которые вы видели до сих пор .

Answer 2

Просто замените свой «список просканированных URL-адресов» на «set просканированных URL-адресов». Наборы оптимизированы для произвольного доступа (с использованием тех же алгоритмов хеширования, что и словари), и они чертовски намного быстрее. Операция поиска по спискам выполняется с использованием линейного поиска, поэтому она не особенно быстрая. Вам не нужно менять реальный код, который выполняет поиск.

Проверьте это.

In [3]: timeit.timeit("500 in t", "t = list(range(1000))")
Out[3]: 10.020853042602539

In [4]: timeit.timeit("500 in t", "t = set(range(1000))")
Out[4]: 0.1159818172454834

Answer 3

У меня была похожая проблема. Завершено профилирование различных методов (list / file / sets / sqlite) для памяти в зависимости от времени. Смотрите эти 2 сообщения. Наконец, sqlite был лучшим выбором. Вы также можете использовать URL-хэш, чтобы уменьшить размер

Поиск строки в большом текстовом файле - профилирование различных методов в python

Создание базы данных sqlite с миллионами строк url ​​- медленный массовый импорт из csv

Answer 4

Вместо этого используйте диктовку с URL-адресами в качестве ключей (O (1) время доступа).

Но набор также будет работать.См

http://wiki.python.org/moin/TimeComplexity