How can I index duplicate items in an array?

Question

Starting with the following array (of hashes):

[
  {: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/"}
]

How can I add an index of the duplicate urls like so:

[
  {: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}
]

michael_wu · Accepted Answer · 2011-09-30 10:22:35Z

5

I would use a hash for keeping track of the indices. Scanning the previous entries again and again seems inefficient

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

or a bit cleaner

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

edited Sep 30, 2011 at 10:22

answered Sep 30, 2011 at 10:08

michael_wu

16k5 gold badges66 silver badges77 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

fl00r Over a year ago

I think it is inefficient too, but depends on Array size.

fl00r Over a year ago

you can use liek @mu each_with_object here: array.each_with_object(Hash.new(0)){ |counts, hash| hash[:index] = counts[hash[:url]] = counts[hash[:url]] + 1}

Luke Over a year ago

both @fl00r and this answer worked great; just found this one easier to grok.

michael_wu Over a year ago

@floor: Thanks, updated. This is because I'm using 1.8.6 here which does not have each_with_object.

fl00r · Accepted Answer · 2011-09-30 10:16:52Z

3

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}
]

edited Sep 30, 2011 at 10:16

answered Sep 30, 2011 at 9:59

fl00r

83.7k33 gold badges222 silver badges239 bronze badges

6 Comments

Luke Over a year ago

Excellent, now I'm just trying to get my head around how that works... :)

millimoose Over a year ago

I reformatted the inject call to hopefully make it clearer. inject loops over the receiving array, and in every call to the inject block, ar will contain the URLs (and their running counts) it's seen "so far" - because they're being added at the end of the block. So at the start, you count how many of the "current" URL you've seen so far, and add that. It's a little clunky to explain because it's really a recursive operation in disguise. (With thanks to @fl00r for graciously letting me try and make his code comprehensible.)

Serabe Over a year ago

I would replace count_so_far = ar.count{|i| i[:url] == it[:url]} with count_so_far = ar[ar.rindex{|i| i[:url] == it[:url]}][:index]If you have a lot of elements will have better performance.

Serabe Over a year ago

@Sii why? When in G the rindex will return 3, as I would expect it to.

millimoose Over a year ago

@Serabe: Actually, no, you're right, I missed that you're retrieving the previous running count. It just took me a while to handle the case where rindex returns nil

|

tokland · Accepted Answer · 2011-10-14 11:21:44Z

0

If I wanted it to be efficient, I'd write:

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]

answered Oct 14, 2011 at 11:21

tokland

68.2k13 gold badges151 silver badges174 bronze badges

Collectives™ on Stack Overflow

How can I index duplicate items in an array?

3 Answers 3

4 Comments

6 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

6 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related