CODEWITHSUNDEEP
rubyperformancebig-o
Jirico
Jirico

Reputation: 1262

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?

Upvotes: 0

Views: 510

Answers (1)

max pleaner
max pleaner

Reputation: 26768

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.

This answer explains why Hash has O(1) search time: https://stackoverflow.com/a/4363602/1034681

Upvotes: 3

Related Questions