跟踪进度最有效的 Ruby 数据结构是什么？

Question

我正在做一个小项目，该项目逐渐增加 link 的列表，然后通过队列处理它们。 link 可能会两次进入队列，我想跟踪我的进度，这样我就可以跳过任何已经处理过的东西。我估计最多大约 10k 个独特的 links。

对于较大的项目，我会使用数据库，但这对于我正在处理的数据量来说似乎有些过分，并且更喜欢某种形式的内存解决方案，如果我想在运行中保存进度，这种解决方案可能会被序列化。

哪种数据结构最适合这种需要？

更新： 我已经在使用散列来跟踪我已完成处理的 links。这是最有效的方法吗？

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

Answer 1

如何设置并将您的链接转换为值对象（而不是引用对象），如结构。通过创建值对象，Set 将能够检测其唯一性。或者，您可以使用散列并按 PK 存储链接。

Answer 2

数据结构可以是散列：

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

要处理您的 link：

push 您需要处理到 current_status[:links] 的任何新 link。
使用shift从current_status[:links]中取出下一个link进行处理。
处理完一个link后，push变成current_status[:processed]

编辑

据我所知（并理解您的问题），处理您的 link 的逻辑是：

# 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

Answer 3

如果你不关心内存，那么就用一个Hash来检查包含；插入和查找时间是 O(1) 平均情况。序列化很简单（Ruby 的元帅 class 应该会为您处理，或者您可以使用像 JSON 这样的格式）。 Ruby 的 Set 是一个以哈希为后盾的类似数组的对象，因此如果您愿意，可以直接使用它。

但是，如果内存是一个问题，那么这对 Bloom filter 来说是个大问题！您可以在恒定时间内实现集合包含测试，并且过滤器使用的内存比散列要少得多。权衡是布隆过滤器是概率性的——你可能会得到误报。您可以使用正确的布隆过滤器参数消除大多数误报的可能性，但如果重复是例外而不是规则，您可以实施类似：

检查布隆过滤器中是否包含集合 [O(1)]
如果布隆过滤器报告找到条目，则对输入数据执行 O(n) 检查，以查看在此之前是否已在输入数据数组中找到该条目。

这将使您对常见情况进行非常快速且节省内存的查找，并且您可以选择接受假阴性的可能性（以保持整个事情小而快），或者您可以执行验证报告重复时设置包含（只在绝对必要时才做昂贵的工作）。

https://github.com/igrigorik/bloomfilter-rb 是我过去使用过的布隆过滤器实现；它工作得很好。还有 redis 支持的 Bloom 过滤器，如果您需要可以跨多个应用程序实例执行集合成员跟踪和测试的东西。

跟踪进度最有效的 Ruby 数据结构是什么？

What is the most efficient Ruby data structure to track progress?

ruby

performance

data-structures