ruby loop refactor

Question

I have a loop that looks like this

def slow_loop(array)
 array.each_with_index do |item, i|
   next_item = array[i+1]
   if next_item && item.attribute == next_item.attribute
     do_something_with(next_item)
   end
 end
end

aside from changing the way do_something_with is called, how can i make this perform better?

thx,

-C

p.s.

Since it appears that this is an 'O(n)' operation, there is apparently no performance to be gained here, so the answer i chose is one that uses a ruby method that already encapsulates this operation. thanks for your help everybody

Perhaps you should let us know how many elements you have and any sort of benchmarking figures you came up with? This SHOULD be a O(n) operation. — Trey
– Trey, Commented Apr 27, 2009 at 20:20
forgive me if this sounds dumb, but, what's an O(n) operation? — Chris Drappier
– Chris Drappier, Commented Apr 27, 2009 at 20:22
Basically, the time of the operation O is a directly related to the number of elements n — Garry Shutler
– Garry Shutler, Commented Apr 27, 2009 at 20:24
It's worth noting that just because it's an O(n) algorithm doesn't mean that you can't get any more performance out of it. There are lots of times when the best possible algorithm is O(n) but you can still shoot yourself in the foot with a pathological O(n) algorithm. e.g., iterating over a matrix column-major when it's stored row-major. In your case, it's a really simple algorithm, and not much room for improvement. But keep in mind that even though you should examine the complexity of your algorithm first, getting the best performance is often about large constant factors. — Todd Gamblin
– Todd Gamblin, Commented Apr 27, 2009 at 20:54

Todd Gamblin · Accepted Answer · 2009-04-27 20:42:05Z

6

As others have mentioned you're not going to improve the performance much, but you could do this more cleanly like so:

array.each_cons(2) do |a, b|
  do_something_with(b) if a == b
end

edited Apr 27, 2009 at 20:42

answered Apr 27, 2009 at 20:28

Todd Gamblin

60k15 gold badges92 silver badges96 bronze badges

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

5 Comments

Chris Drappier Over a year ago

should next_item be 'b' here?

Sarah Mei Over a year ago

Interesting - I hadn't seen each_cons before.

Todd Gamblin Over a year ago

@Sara Mei: It's in enumerable... there is also each_slice, which is the non-sliding window version.

Chris Drappier Over a year ago

although it sucks my performance loss is not coming from the loop, this is a pretty nice way of doing this.. thx :)

Mike Woodhouse Over a year ago

Note that each_cons and each_slice are only in native Ruby as of 1.9, although they do exist in the Enumerable extensions implemented in Rails from (at least, possibly earlier) 2.1.2 onwards

Garry Shutler · Accepted Answer · 2009-04-27 20:22:06Z

2

The performance of do_something_with is the main factor. Anything else would be micro-optimisation.

This should be O(n), you could work out a way to avoid the final check, but that's not going to be that costly in the grand scheme of things.

answered Apr 27, 2009 at 20:22

Garry Shutler

32.8k13 gold badges90 silver badges120 bronze badges

1 Comment

Chris Drappier Over a year ago

if that's the case, I guess my only other question would be, is there a ruby method that already encapsulates this type of procedure?

Sarah Mei · Accepted Answer · 2009-04-27 20:30:13Z

0

I tend to agree with Garry on the optimization potential, but it can certainly be written more simply.

prev_attr = nil
my_array.each |item|
  do_something_with(item) if prev_attr and prev_attr == item.attribute
  prev_attr = item.attribute
end

answered Apr 27, 2009 at 20:30

Sarah Mei

18.5k5 gold badges47 silver badges45 bronze badges

Collectives™ on Stack Overflow

ruby loop refactor

3 Answers 3

5 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

5 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related