Какова самая эффективная структура данных Ruby для отслеживания прогресса?

Question

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

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

Какая структура данных наилучшим образом соответствует этой потребности?

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

def process_link(link) 
    return if @processed_links[link] 
    # ... processing logic 
    @processed_links[link] = Time.now # or other state 
end 

Answer 1

Если вы не обеспокоены памятью, просто используйте хэш для проверки включения; вставка и время поиска - это O (1) средний случай. Сериализация проста (класс маршала Ruby должен позаботиться об этом для вас, или вы можете использовать такой формат, как JSON). Ruby's Set - это массивный объект, который поддерживается хешем, поэтому вы можете просто использовать его, если вы так склонны.

Однако, если память является проблемой, то это большая проблема для Bloom filter! Вы можете достичь установленного тестирования включения в постоянное время, и фильтр использует значительно меньше памяти, чем хэш. Компромисс - это фильтры Bloom, которые вероятностны - вы можете получить ложные включения.Вы можете исключить вероятность большинства ложных срабатываний с нужными параметрами цветения фильтра, но если дубликаты скорее исключение, чем правило, вы могли бы реализовать что-то вроде:

1. Проверьте наличие множества включения в Bloom фильтре [O (1)]
2. Если фильтр цветения сообщает, что запись найдена, выполните проверку входных данных O (n), чтобы увидеть, был ли этот элемент найден в массиве входных данных до этого момента.

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

https://github.com/igrigorik/bloomfilter-rb - это реализация фильтра Bloom, которую я использовал в прошлом; он работает красиво. Также есть фильтры Bloom с поддержкой Redis, если вам нужно что-то, что может выполнять отслеживание и тестирование членства в нескольких экземплярах приложения.

Answer 2

Как насчет Set и преобразовать ваши ссылки в объект значения (а не объект ссылки), такой как Structs. Создав объект значения, Set сможет обнаружить его уникальность. Альтернативно, вы можете использовать хэш и хранить ссылки своим ПК.

Answer 3

Структура данных может быть хэш:

current_status = { links: [link3, link4, link5], processed: [link1, link2, link3] } 

Чтобы отслеживать прогресс (в процентах):

links_count = current_status[:links].length + current_status[:processed].length 
progress = (current_status[:processed].length * 100)/links_count # Will give you percent of progress 

Для обработки ссылок:

• push любая новая ссылка вам необходимо обработать до current_status[:links].
• Используйте shift, чтобы взять с current_status[:links] следующую ссылку для обработки.
• После обработки ссылки, push его current_status[:processed]

EDIT

Как я понимаю (и понимаю ваш вопрос), логика для обработки ссылок будет:

# Add any new link that needs to be processed to the queue unless it have been processed 
def add_link_to_queue(link) 
    current_status[:to_process].push(link) unless current_status[:processed].include?(link) 
end 

# Process next link on the queue 
def process_next_link 
    link = current_status[:to_process].shift # return first link on the queue 
    # ... login process the link 
    current_status[:processed].push(link) 
end 

# shift method will not only return but also remove the link from the original array to avoid duplications