Implementing Array#uniq in Ruby

Question

I've implemented a working version of Array#uniq in Ruby to answer the question here: http://www.rubeque.com/problems/like-a-snowflake, but I'd like to see if there's ways to clean up my code or some better practices I should follow? This is my version:

class Array
 def uniq(&block)
 objs = []
 yield_vals = []
 self.each do |obj|
 yield_val = yield obj
 unless yield_vals.include?(yield_val)
 yield_vals.push(yield_val)
 objs.push(obj)
 end
 end
 objs
 end
end

Answer 1

For one, I'd use the << operator rather than push just out of convention.

Second, you still have other Array/Enumerable methods at your disposal. So there's no need to create a new array and add unique items to it. Try filtering the array instead.

Update: Whoo boy, I was still asleep when I wrote that first answer. In my defense it was early

You can actually just do

def uniq(&block)
 group_by(&block).values.map(&:first)
end

As for my previous answer... well, I did say it could be done better. Just pretend it didn't happen.

• TenJack: Great! Thanks a lot, both of your solutions really helped me.
• tokland: Nice simple solution. Only that you pay a bit of storage penalty.
• Flambino: @tokland thanks, and yeah, I'm not claiming this is particularly efficient, nor does it match the built-in Array#uniq (this one requires a block). I was just aiming for a solution that would pass the (rather narrow) Rubeque tests
• Cary Swoveland: Wouldn't group_by(&block).keys be more straigtforward?
• Flambino: @CarySwoveland That wouldn't work, I'm afraid. The keys produced by group_by are the result of the block - not the actual array values. So you wouldn't get the unique values of the original array, but something else. I.e. [1.1, 2.2].group_by(&:to_i).keys would give you [1, 2] instead of the expected [1.1, 2.2]

Answer 2

Some notes:

• Ruby's Array#uniq works with and without a block, yours probably should do the same.
• Array#include? is O(n), so it's not a good idea to use it within loops. Sets and hashes, on the other hand, do have O(1) inclusion predicates.
• Your solution is very, very imperative (do this, do that), I'd try a more functional approach (based on expressions instead of change of state).

I'd write:

class Array
 def my_uniq
 reduce(Hash.new) do |acc, x|
 key = block_given? ? yield(x) : x
 acc.has_key?(key) ? acc : acc.update(key => x)
 end.values
 end
end

Note that if we had the abstraction Hash#reverse_update in the core (it's in active_support) the block could be simplified: acc.reverse_update((block_given? ? yield(x) : x) => x).

• Nakilon: Using Fold without reducing dimensions of a vector looks fun, but is actually bad.
• tokland: @Nakilon: why is it bad?
• Cary Swoveland: A slight variant: each_with_object({}) {|x,acc| acc[block_given? ? yield(x) : x] = x}.values.
• tokland: @CarySwoveland: Note that you should not override values already present in the accumulator.