Итеративная перепроверка огромного списка

У меня есть список из примерно 100 000 URL, сохраненных на моем компьютере. (эти 100000 могут очень быстро превратиться в несколько миллионов.) Для каждого URL-адреса я проверяю эту веб-страницу и собираю все дополнительные URL-адреса на этой странице, но только если каждой дополнительной ссылки еще нет в моем большом списке. Проблема здесь в том, чтобы итеративно перезагружать этот огромный список в память, чтобы я мог постоянно иметь точный список. где объем используемой памяти, вероятно, очень скоро станет слишком большим, и, что еще более важно, время между перезагрузкой списка становится больше, что серьезно замедляет прогресс проекта.

Мой список сохранен в нескольких разных форматах. Один формат заключается в том, что все ссылки содержатся в одном текстовом файле, где я открываю (filetext) .readlines (), чтобы превратить его прямо в список. Другой формат, который я сохранил, который кажется более полезным, - это сохранить дерево папок со всеми ссылками и превратить его в список с помощью os.walk (путь).

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

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

Peter Wood 10.09.2018 09:48

Если быть консервативным, если для ссылки используется 1 КБ, то 1 миллион ссылок составляет 1 ГБ.

Peter Wood 10.09.2018 09:52

Я не уверен, честно говоря, возможно, память не такая большая проблема, как я думал. У меня 8-граммовый баран, но я еще не дошел до этого из-за того, сколько времени требуется, чтобы даже загрузить весь список.

JilliamWones 10.09.2018 09:53

@JilliamWones Список строк не должен быть таким длинным для загрузки. Несколько секунд вверху. Не могли бы вы поделиться своим кодом?

Mathieu 10.09.2018 09:57

Действительно ли проблема здесь в памяти или в том, что вы пытаетесь неоднократно искать, существует ли определенная запись в list? И что вы каждый раз перечитываете этот список из файла? Вы пробовали просто держать set в памяти? Если память является (также) проблемой, и если многие URL-адреса имеют общие части (например, подстраницы на более крупной веб-странице), вы также можете рассмотреть возможность использования префиксного дерева / Trie.

tobias_k 10.09.2018 10:09
0
5
53
3

Ответы 3

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

Вы должны попытаться рассмотреть несколько мыслей; среди которых sets и pandas. Первый вариант, вероятно, будет оптимальным решением.

Теперь, когда вы подумали об использовании дерева папок с URL-адресами в качестве имен папок, я могу придумать один способ, который может быть быстрее. Вместо того, чтобы создавать список с помощью os.walk(path), попробуйте проверить, существует ли уже папка. Если нет, это означает, что у вас еще не было этого URL-адреса. По сути, это база данных поддельных графов. Для этого вы можете использовать функцию os.path.isdir(). Если вам нужна настоящая графическая БД, вы можете, например, заглянуть в OrientDB.

Память не должна быть проблемой. Если для каждого URL-адреса требуется 1 КБ для хранения в памяти (очень много), 1 миллион URL-адресов будет 1 ГБ. Вы говорите, что у вас 8 ГБ ОЗУ.

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

Вы можете рекурсивно очищать страницы:

def main():
    with open('urls.txt') as urls:
        known_urls = set(urls)

    for url in list(known_urls):
        scrape(url, known_urls)


def scrape(url, known_urls):
    new_urls = _parse_page_urls(url)
    for new_url in new_urls:
        if new_url not in known_urls:
            known_urls.add(new_url)
            scrape(new_url, known_urls)

Вы рассматривали возможность сопоставления таблицы IP-адресов с URL-адресом? Конечно, это будет работать только в том случае, если вы ищете уникальные домены, а не тысячи страниц в одном домене. Преимущество в том, что вы будете иметь дело с 12 целочисленным адресом. Обратной стороной является необходимость в дополнительных табличных структурах данных и дополнительных процессах для сопоставления данных.

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

tobias_k 10.09.2018 11:07

Другие вопросы по теме