On Oct 3, 2004, at 9:09 AM, Gavin Kistner wrote:
> Hrm, which gives me a good idea for my Ouroboros#separate_duplicates 
> method; currently if I find a family duplicate I just swap the second 
> one with it's following neighbor, and either hope that it's not the 
> same family or wait until the next pass in the loop to fix that one. I 
> suspect I would get much quicker sorting if I 'filtered' the 
> pool...search ahead for the next person who isn't in the same family 
> and swap them.
>
> That smells like it should be an O(n) performer, rather than ~O(n^2).

Indeed, with 3072 people in the pathological case (where half are one 
family, one quarter another, one eighth another, etc.) the above 
optimization brings the time down to 20 seconds, instead of 254 seconds 
using the code I originally created :)

I've updated Ouroboros.rb to reflect the new, more efficient code.
For the overly-curious who want to see the slow code, the new and old 
methods are below (with irrelevant bits trimmed out).

   def separate_duplicates!
     max_crawls = @size*@size
     keys = {}
     @all.each{ |list_item|
       keys[list_item] = block_given? ? yield(list_item) : list_item
     }

     crawls=0
     dup_distance = 0
     while dup_distance < @size && (crawls < max_crawls)
       if keys[@current] == keys[@current.next]
         dup_distance = 0
         n = 1
         begin; swapper = self[n+=1]; end until (keys[@current] != 
keys[swapper]) || (n==@size)
         self.swap( @current.next, swapper )
       else
         dup_distance += 1
       end
       self.increment
       crawls+=1
     end
     raise "Error: #separate_duplicates! was unsuccessful after 
#{crawls} rounds." if dup_distance < @size
     self
   end

   def separate_duplicates_old!
     #...
     while dup_distance < @size && (crawls < max_crawls)
       if keys[@current] == keys[@current.next]
         dup_distance = 0
         self.swap( @current.next, self[2] )
       else
         dup_distance += 1
       end
       self.increment
       crawls+=1
     end
     #...
   end