Remove sequential duplicates from Ruby array

Question

Let's say I have the following array and I would like to get rid of contiguous duplicates:

arr = [1,1,1,4,4,4,3,3,3,3,5,5,5,1,1,1]

I would like to get the following:

=> [1,4,3,5,1]

It would be great if there's something simpler and more efficient than my solutions (or variants thereof):

(arr + [nil]).each_cons(2).collect { |i| i[0] != i[1] ? i[0] : nil }.compact

or

(arr + [nil]).each_cons(2).each_with_object([]) { 
   |i, memo| memo << i[0] unless i[0] == i[1] 
 }

EDIT: It looks like @ArupRakshit's solution below is very simple. I'm still looking for better efficiency than my solution.

EDIT:

I'll be benchmarking responses as they come:

require 'fruity'
arr = 10000.times.collect { [rand(5)] * (rand(4) + 2) }.flatten

compare do
  abdo { (arr + [nil]).each_cons(2).collect { 
    |i| i[0] != i[1] ? i[0] : nil }.compact 
  }
  abdo2 { 
          (arr + [nil]).each_cons(2).each_with_object([]) { 
           |i, memo| memo << i[0] unless i[0] == i[1] 
          }
  }
  arup { arr.chunk(&:to_i).map(&:first) }
  arupv2 { arr.join.squeeze.chars.map(&:to_i) }
  agis {
    i = 1
    a = [arr.first]

    while i < arr.size
      a << arr[i] if arr[i] != arr[i-1]
      i += 1
     end
    a
  }
  arupv3 { arr.each_with_object([]) { |el, a| a << el if a.last != el } }
end

Benchmark results:

agis is faster than arupv3 by 39.99999999999999% ± 10.0%
arupv3 is faster than abdo2 by 1.9x ± 0.1
abdo2 is faster than abdo by 10.000000000000009% ± 10.0%
abdo is faster than arup by 30.000000000000004% ± 10.0%
arup is faster than arupv2 by 30.000000000000004% ± 10.0%

If we use:

arr = 10000.times.collect { rand(4) + 1 } # less likelihood of repetition

We get:

agis is faster than arupv3 by 19.999999999999996% ± 10.0%
arupv3 is faster than abdo2 by 1.9x ± 0.1
abdo2 is similar to abdo
abdo is faster than arupv2 by 2.1x ± 0.1
arupv2 is similar to arup

"I'll be benchmarking responses as they come"... followed by acceptance of the first answer, ensuring responses won't come... — Mark Thomas
– Mark Thomas, Commented Feb 12, 2014 at 14:32
I'm sure people (especially Rubyists) don't stop posting after an answer has been accepted. — Abdo
– Abdo, Commented Feb 12, 2014 at 14:37
@MarkThomas I totally understand your point but at the same time, over the past few days, I've seen a bunch of guys (such as: aruprakshit, careswoveland, steenslag, matt) answering questions from a while ago and improving them just for because they enjoy to! — Abdo
– Abdo, Commented Feb 12, 2014 at 14:52
Why would you prefer a slightly faster solution over a clearer one? Is this code a demonstrated bottleneck in your application? — Wayne Conrad
– Wayne Conrad, Commented Feb 12, 2014 at 15:57
@WayneConrad I have accepted the clearer solution below as you can see =) Check my comments on Agis' response :-) — Abdo
– Abdo, Commented Feb 12, 2014 at 15:58

Community · Accepted Answer · 2017-05-23 10:33:59Z

14

Do as below using Enumerable#chunk :

arr = [1,1,1,4,4,4,3,3,3,3,5,5,5,1,1,1]
arr.chunk { |e| e }.map(&:first)
# => [1, 4, 3, 5, 1]
# if you have only **Fixnum**, something magic
arr.chunk(&:to_i).map(&:first)
# => [1, 4, 3, 5, 1]

UPDATE

as per @abdo's comment, here is another choice :

arr.join.squeeze.chars.map(&:to_i)
# => [1, 4, 3, 5, 1]

another choice

arr.each_with_object([]) { |el, a| a << el if a.last != el }

edited May 23, 2017 at 10:33

CommunityBot

11 silver badge

answered Feb 12, 2014 at 14:01

Arup Rakshit

119k30 gold badges270 silver badges328 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Abdo Over a year ago

It looks like mine are faster :s .. I'll post benchmarks above

Arup Rakshit Over a year ago

@Abdo Done.. Don't remove( from the original comment box) the linked comment of your in my answer. :)

Arup Rakshit Over a year ago

@Abdo check again! :)

Wayne Conrad Over a year ago

The join.squeeze method will only work for single digit numbers. The first solution is very nice: it is succinct, easy to understand, works with any comparable data type, and is almost certainly fast enough.

Abdo Over a year ago

@WayneConrad I like the different (educational) approach taken by join.squeeze in case we're using characters vs numbers and am glad aruprakshit provided alternatives :-)

|

Agis · Accepted Answer · 2014-02-12 15:55:01Z

4

The less elegant yet most efficient solution:

require 'benchmark'

arr = [1,1,1,4,4,4,3,3,3,3,5,5,5,1,1,1]

GC.disable
Benchmark.bm do |x|
  x.report do
    1_000_000.times do
      i = 1
      a = [arr.first]

      while i < arr.size
        a << arr[i] if arr[i] != arr[i-1]
        i += 1
      end
    end
  end
end
#      user     system      total        real
# 1.890000   0.010000   1.900000 (  1.901702)

GC.enable; GC.start; GC.disable

Benchmark.bm do |x|
  x.report do
    1_000_000.times do
      (arr + [nil]).each_cons(2).collect { |i| i[0] != i[1] ? i[0] : nil }.compact
    end
  end
end
#      user     system      total        real
# 6.050000   0.680000   6.730000 (  6.738690)

edited Feb 12, 2014 at 15:55

answered Feb 12, 2014 at 15:17

Agis

33.8k4 gold badges77 silver badges81 bronze badges

3 Comments

Abdo Over a year ago

Yup, this is at least 2x faster than my fastest solution. (My benchmarks are different because I'm using a larger array). Your solution, however, is buggy: can you try: agis([0,1,4,4,4,3,3,3,3,5,5,5,1]) => returning [0, 0, 1, 4, 3, 5, 1] expected: [0, 1, 4, 3, 5, 1] . Let me know when fixed so I can post alongside my benchmarks =)

Arup Rakshit Over a year ago

I doubt, how many Ruby coder would use, such a loop for this kind of solution.. :)

Abdo Over a year ago

@Agis, you get a +1. ArupRakshit 's last solution is very close in efficiency to your solution. His solution, however, is much easier on the eyes. My question required BOTH simplicity and efficiency.

Collectives™ on Stack Overflow

Remove sequential duplicates from Ruby array

2 Answers 2

6 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related