Select repeated sequence of an number in an array?

Question

Given an array of numbers, how can I select the number in the array that's has been repeated the most times?

arr = [4,3, 3, 2, 1, 3, 3, 3, 4, 4, 4, 4, 0, 0, 0, 1, 3, 4, 0]

@NicholasAlek Do you mean repeated **in a row**? What number wins in this case: `[1, 1, 2, 2, 2, 1, 1]` 2 or 1? — user229044, Sep 09 '13 at 19:55
I see, just repeated. It really doesn't matter in which order numbers come. — Nicholas Alek, Sep 09 '13 at 19:58

Arup Rakshit · Accepted Answer · 2013-09-10T04:42:42.243

2

Here it is for just repeated:

arr = [4,3, 3, 2, 1, 3, 3, 3, 4, 4, 4, 4, 0, 0, 0, 1, 3, 4, 0]
arr.group_by{|e| e}.max_by{|k,v| v.size}.first
# => 4

or

arr = [4,3, 3, 2, 1, 3, 3, 3, 4, 4, 4, 4, 0, 0, 0, 1, 3, 4, 0]
arr.uniq.max_by{|e| arr.count(e)}
# => 4

Another is for repeated consecutively :

arr = [4,3, 3, 2, 1, 3, 3, 3, 4, 4, 4, 4, 0, 0, 0, 1, 3, 4, 0]
arr.chunk{|e| e}.max_by{|e| e.last.size}.first
# => 4

As per the @Tessi Benchmark report :

require 'benchmark'
iterations = 10_000
arr = Array.new(1000) {(rand()*100).to_i}

def max_babai1(arr)
  arr.group_by{|e| e}.max_by{|k,v| v.size}.first
end

def max_babai2(arr)
  arr.uniq.max_by{|e| arr.count(e)}
end

Benchmark.bm do |bm|
  bm.report('babai1') do
    iterations.times do
      max_babai1 arr
    end
  end

  bm.report('babai2') do
    iterations.times do
      max_babai2 arr
    end
  end
end

Output

ruby --version
ruby 2.0.0p247 (2013-06-27 revision 41674) [x86_64-linux]

ruby bench.rb         
       user     system      total        real
babai1  1.700000   0.000000   1.700000 (  1.707292)
babai2 29.630000   0.010000  29.640000 ( 29.769966)

edited Sep 10 '13 at 04:42

answered Sep 09 '13 at 19:50

Arup Rakshit

116,827
30
260
317

That's the one!!! Thanks. Can you walk me through your code? – Nicholas Alek Sep 09 '13 at 19:55
@NicholasAlek which one is your one? First one(*repeated*) or last one(*repeated consecutively*) ? :) – Arup Rakshit Sep 09 '13 at 19:55
Ahhh, doesn't matter which order, first or last. – Nicholas Alek Sep 09 '13 at 19:59
for the `repeated` one you can use `chunk` if you sort first: `arr.sort.chunk{|v|v}.max_by{|val,a| a.size}.first`. Although neither implementation handles ties. – firien Sep 09 '13 at 20:07
@firien why sort is needed ? You probably didn't catch the difference between the 2 codes. – Arup Rakshit Sep 09 '13 at 20:08
i don't believe the repeated consecutively works. put a "5" in the first slot and check the result. and yes i understood the difference – firien Sep 09 '13 at 20:11
@firien give me the array please..:) I will test it. – Arup Rakshit Sep 09 '13 at 20:12
arr = [5,4,3, 3, 2, 1, 3, 3, 3, 4, 4, 4, 4, 0, 0, 0, 1, 3, 4, 0] arr.chunk{|e| e}.max_by{|e| e.size}.first – firien Sep 09 '13 at 20:13
@firien fixed it now.. :) – Arup Rakshit Sep 09 '13 at 20:14
@firien see now - `arr = [5,4,3, 3, 2, 1, 3, 3, 3, 4, 4, 4, 4, 0, 0, 0, 1, 3, 4, 0,5,5,5,5,5,5,5] arr.chunk{|e| e}.max_by{|e| e.last.size}.first # => 5` .. – Arup Rakshit Sep 09 '13 at 20:17
yep. so my point was that you could use your exact same code from _repeated consecutively_ to find most _duplicates_ if you threw a `sort` in right before `chunk.` – firien Sep 09 '13 at 20:25
@firien see my update. It is more elegant! :) – Arup Rakshit Sep 09 '13 at 20:27
I *highly* suggest to use @Babai's first approach. The second one is an order of magnitude slower: https://gist.github.com/tessi/6501753 – tessi Sep 09 '13 at 21:27
@tessi I have added the benchmark report! :) – Arup Rakshit Sep 10 '13 at 04:43
Wow. The first line of code wins by miles! What a difference it makes to know which method would work the best. Thanks @Babai! – Nicholas Alek Sep 10 '13 at 15:31

Select repeated sequence of an number in an array?

1 Answers1