From: Robert Klemme <shortcutter@...>
Date: 2012-04-22T20:46:16+09:00
Subject: Re: finding duplicates in an array and its index number

OK folks,

news from the service department.  Here's the shootout:
https://gist.github.com/2463600


Turns out quickest is one of the less arcane solutions:

      dups = {}

      dat.each_with_index do |val, idx|
        (dups[val] ||= []) << idx
      end

      dups.delete_if {|k,v| v.size == 1}

A few remarks:

It's amazing how many forms even the same algorithm can take in Ruby.
Just the different options for adding to a Hash (#default_proc,
#fetch, ||=) can make a huge visual difference although the underlying
strategy of all these algorithms is the same.

Downside of Jan's first approach is that it has effort O(n**2) in
terms of elements in the array because of the nested iteration.  Sam's
approach has a similar quality although less obvious (it's in the
#count).

Allocating multiple Hash instances is what makes Jan's second approach slow.

As always, #inject (or #reduce) approaches are slower than others.

The best strategy is to create a Hash with elements as keys and Arrays
of indexes as values.  This approach won't suffer for large inputs
from the O(n**2) issue.

For one off scripts and infrequent execution it doesn't really matter much. :-)

Kind regards

robert

-- 
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/