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

Question

Я работаю над простым веб-сканером в python и не хочу создавать простой класс очереди, но я не совсем уверен, как лучше начать. Мне нужно что-то, что содержит только уникальные элементы для обработки, чтобы сканер сканировал каждую страницу только один раз за запуск скрипта (просто чтобы избежать бесконечного зацикливания). Кто-нибудь может дать мне или указать на простой пример очереди, из которого я мог бы убежать?

Answer 1

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

>>> q = set([9, 8, 7, 7, 8, 5, 4, 1])
>>> q.pop()
1
>>> q.pop()
4
>>> q.pop()
5
>>> q.add(3)
>>> q.add(3)
>>> q.add(3)
>>> q.add(3)
>>> q
set([3, 7, 8, 9]

Answer 2

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

Я бы использовал комбинацию набора и списка:

visited = set()
to_visit = []

def queue_page(url):
    if url not in visited:
        to_visit.append(url)

def visit(url):
    visited.add(url)
    ... # some processing

    # Add all found links to the queue
    for link in links:
        queue_page(link)

def page_iterator(start_url):
    visit(start_url)
    try:
        yield to_visit.pop(0)
    except IndexError:
        raise StopIteration

for page in page_iterator(start):
    visit(page)

Конечно, это немного надуманный пример, и вам, вероятно, лучше всего это как-то инкапсулировать, но это иллюстрирует концепцию.

Answer 3

Очень простым примером было бы вставить URL каждого элемента в dict, но не как значение, а как ключ. Затем обрабатывайте только следующий элемент, если его URL-адрес отсутствует в ключах этого диктанта:

visited = {}
# grab next url from somewhere
if url not in visited.keys():
  # process url
  visited[url] = 1 # or whatever, the value is unimportant
# repeat with next url

Конечно, вы можете добиться большей эффективности, но это будет просто.

Answer 4

Почему бы не использовать список, если вам нужен порядок (или даже heapq, как ранее предлагалось zacherates до того, как вместо него был предложен набор), а также использовать набор для проверки на наличие дубликатов?

Answer 5

Я бы расширил класс списка, добавив в него уникальный код тестирования для любых методов списка, которые вы используете. Это может варьироваться от простого добавления .append_unique(item) к классу или переопределения всех append, insert, extend, __setitem__, __setslice__ и т. Д., Чтобы вызвать исключение (или молчать, если Вы хотите) в случае неуникального предмета.

Например, если вы просто хотите убедиться, что метод добавления поддерживает уникальность:

class UniqueList(list):
    def append(self, item):
        if item not in self:
            list.append(self, item)