如何在数组中索引重复的元素？

Question

从以下数组（哈希）开始：

[
  {:name=>"site a", :url=>"http://example.org/site/1/"}, 
  {:name=>"site b", :url=>"http://example.org/site/2/"}, 
  {:name=>"site c", :url=>"http://example.org/site/3/"}, 
  {:name=>"site d", :url=>"http://example.org/site/1/"}, 
  {:name=>"site e", :url=>"http://example.org/site/2/"}, 
  {:name=>"site f", :url=>"http://example.org/site/6/"},
  {:name=>"site g", :url=>"http://example.org/site/1/"}
]

我该如何添加重复URL的索引呢？例如：

[
  {:name=>"site a", :url=>"http://example.org/site/1/", :index => 1}, 
  {:name=>"site b", :url=>"http://example.org/site/2/", :index => 1}, 
  {:name=>"site c", :url=>"http://example.org/site/3/", :index => 1}, 
  {:name=>"site d", :url=>"http://example.org/site/1/", :index => 2}, 
  {:name=>"site e", :url=>"http://example.org/site/2/", :index => 2}, 
  {:name=>"site f", :url=>"http://example.org/site/6/", :index => 1},
  {:name=>"site g", :url=>"http://example.org/site/1/", :index => 3}
]

- Luke

Answer 1

我建议使用哈希表来跟踪索引。 反复扫描先前的条目似乎效率低下。

counts = Hash.new(0)
array.each { | hash | 
  hash[:index] = counts[hash[:url]] = counts[hash[:url]] + 1
}

或者更简洁一些

array.each_with_object(Hash.new(0)) { | hash, counts | 
  hash[:index] = counts[hash[:url]] = counts[hash[:url]] + 1
}

- undur_gongor

---

我认为这也是低效的，但取决于数组大小。 - fl00r

你可以在这里使用 each_with_object，像这样：array.each_with_object(Hash.new(0)){ |counts, hash| hash[:index] = counts[hash[:url]] = counts[hash[:url]] + 1} - fl00r

两个答案都很好，但我觉得这个更容易理解。 - Luke

@floor：谢谢，已更新。这是因为我在这里使用的是1.8.6版本，它没有each_with_object。 - undur_gongor

Answer 2

array = [
  {:name=>"site a", :url=>"http://example.org/site/1/"}, 
  {:name=>"site b", :url=>"http://example.org/site/2/"}, 
  {:name=>"site c", :url=>"http://example.org/site/3/"}, 
  {:name=>"site d", :url=>"http://example.org/site/1/"}, 
  {:name=>"site e", :url=>"http://example.org/site/2/"}, 
  {:name=>"site f", :url=>"http://example.org/site/6/"},
  {:name=>"site g", :url=>"http://example.org/site/1/"}
]

array.inject([]) { |ar, it| 
    count_so_far = ar.count{|i| i[:url] == it[:url]}
    it[:index] = count_so_far+1
    ar << it
}
#=>
[
  {:name=>"site a", :url=>"http://example.org/site/1/", :index=>1}, 
  {:name=>"site b", :url=>"http://example.org/site/2/", :index=>1}, 
  {:name=>"site c", :url=>"http://example.org/site/3/", :index=>1}, 
  {:name=>"site d", :url=>"http://example.org/site/1/", :index=>2}, 
  {:name=>"site e", :url=>"http://example.org/site/2/", :index=>2}, 
  {:name=>"site f", :url=>"http://example.org/site/6/", :index=>1}, 
  {:name=>"site g", :url=>"http://example.org/site/1/", :index=>3}
]

- fl00r

---

太好了，现在我只是试图理解它的工作原理... :) - Luke

我重新格式化了inject调用，希望能使它更清晰。inject循环遍历接收数组，并在每次调用注入块时，ar将包含它“到目前为止”看到的URL（及其运行计数）-因为它们被添加到块的末尾。所以在开始时，您要计算到目前为止已经看到了多少个“当前”URL，并将其添加。这有点笨拙，因为它实际上是一个伪装的递归操作。（感谢@fl00r慷慨地让我试图让他的代码可理解。） - millimoose

我会用 count_so_far = ar[ar.rindex{|i| i[:url] == it[:url]}][:index] 替换 count_so_far = ar.count{|i| i[:url] == it[:url]}。如果有很多元素，性能会更好。 - Serabe

@Sii 为什么？当在 G 中时，rindex 将返回3，正如我所期望的那样。 - Serabe

@Serabe：实际上，你是对的，我错过了你正在检索的先前运行计数。只是花了我一些时间来处理“rindex”返回“nil”的情况。 - millimoose

@Sii请查看此处的文档：[http://www.ruby-doc.org/core/classes/Array.html#M000238] - Serabe

Answer 3

如果我想要它高效，我会这样写:

items_with_index = items.inject([[], {}]) do |(output, counts), h|
  new_count = (counts[h[:url]] || 0) + 1
  [output << h.merge(:index => new_count), counts.update(h[:url] => new_count)]
end[0]

- tokland