Jirico Jirico - 9 months ago 45
Ruby Question

Codility performance difference: array vs hash

I made a test in codility: https://codility.com/programmers/lessons/2-arrays/odd_occurrences_in_array/ and I noticed a performance difference between two different solutions:

1 - List solution:

def solution(list)
unmatched_elements = []
list.each{ |el|
if unmatched_elements.include? el
unmatched_elements.delete el
else
unmatched_elements.push el
end
}
unmatched_elements[0]
end


2 - Hash Solution

def solution(a)
unmatch = {}

a.each do |e|
if unmatch[e].nil?
unmatch[e] = 1
else
unmatch.delete e
end
end
unmatch.keys.first
end


The first one gave me 25% performance score with some timeouts. The second one gave me 100% performance score. Why is that? I tought pushing to a Hash would result in O(n) space complexity like a List, but it seems it's not, why?

Answer Source

It's not about space complexity, it's about time complexity. Specifically, looking up an element in an array (include?) is a N time operation since it needs to check each element until there's a match. Hash lookup [] is constant time.