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, Apr 27 '09 at 20:20
forgive me if this sounds dumb, but, what's an O(n) operation? — Chris Drappier, Apr 27 '09 at 20:22
Basically, the time of the operation O is a directly related to the number of elements n — Garry Shutler, Apr 27 '09 at 20:24
Also http://stackoverflow.com/questions/133008/what-is-big-o-notation-do-you-use-it (and more links in the question). — Michael Myers, Apr 27 '09 at 20:25
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, Apr 27 '09 at 20:54
O(n) just defines how the function's execution time scales with the size of the dataset it's operating on. Something that takes five years per element is still O(n). — Chuck, Apr 28 '09 at 01:20

Todd Gamblin · Accepted Answer · 2009-04-27T20:42:05.510

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 '09 at 20:42

answered Apr 27 '09 at 20:28

Todd Gamblin

58,354
15
89
96

should next_item be 'b' here? – Chris Drappier Apr 27 '09 at 20:32
Interesting - I hadn't seen each_cons before. – Sarah Mei Apr 27 '09 at 20:32
@Sara Mei: It's in enumerable... there is also each_slice, which is the non-sliding window version. – Todd Gamblin Apr 27 '09 at 20:34
although it sucks my performance loss is not coming from the loop, this is a pretty nice way of doing this.. thx :) – Chris Drappier Apr 27 '09 at 20:34
1

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 – Mike Woodhouse Apr 28 '09 at 09:55

score 2 · Answer 2 · answered Apr 27 '09 at 20:22

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 '09 at 20:22

Garry Shutler

32,260
12
84
119

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? – Chris Drappier Apr 27 '09 at 20:24

score 0 · Answer 3 · answered Apr 27 '09 at 20:30

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 '09 at 20:30

Sarah Mei

18,154
5
45
45

ruby loop refactor

3 Answers3