Performance: iterate over an array except for an element

Question

I am using Ruby on Rails 3.0.7 and I would like to iterate over an array of objects (class istances) except for the element with id equal to 1 (the id refers to the array[1] index).

I know that I can use an if statement "internally" to an each statement and doing that I check for each "current"\"considered" element if id == 1. However, since the array is populated of a lot of data, I would like to find another way in order to accomplish the same things in a more performant way (avoiding to run the if each time).

How can I do?

Why not ensure the array is not populated with the id of 1 to begin with? — Mark Thomas
– Mark Thomas, Commented Jun 22, 2011 at 2:15

DigitalRoss · Accepted Answer · 2011-06-21 23:36:13Z

Make program work
Profile
Optimize

Donald Knuth said:

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.

Now, you could do something like:

def f do_something end f 0 for i in 2..n f i end

Or even:

def f yield 0 for i in 2..@n yield i end end f do |i| do_something end

But you probably do not want to do anything of the sort, and if you did, it would only be after finding out that it matters.

And finally, suppose this ugly trick actually makes your server run ever so slightly faster. Was it worth it?

+1, exactly what I was about to say. if id == 1 is generally going to be very performant. Don't sweat it unless you discover actual performance problems down the road, then fire up your profiler.

Nemo157 · Accepted Answer · 2011-06-22 01:48:41Z

a = ['a', 'b', 'c'] a.each_with_index.reject {|el,i| i == 1}.each do |el,i| # do whatever with the element puts el end

Is IMHO a better way of doing the selection instead of using your own explicit if statement. I believe, however, that it will result in approximately the same performance as using if, maybe even slightly lower.

If after benchmarking as others have suggested you know that the time this takes is definitely slower than what you can allow it, and it is the selection causing the slowness then this can be easily modified to remove the selection in a number of ways:

a = ['a', 'b', 'c'] n = 1 (a.first(n) + a.drop(n + 1)).each do |el| # do whatever with the element puts el end

Unfortunately I believe this will also be slower than running the simple if. One that I believe might have the potential for speed is:

a = ['a', 'b', 'c'] n = 1 ((0...n).to_a+((n+1)...a.size).to_a).map{|i| a[i]}.each do |el| # do whatever with the element puts el end

But this again has a high possibility of being slower.

EDIT

Benchmark is in this gist. These results actually surprised me, reject is by far the slowest option, followed by the ranges. The highest performing after not removing the element at all was using first and drop to select all the elements around it.

The results as a percentage using no selection as a baseline:

with if 146% with first and drop 104% without if 100%

Obviously this is highly dependant on what you do with the elements, this was testing with probably the fastest operation Ruby can perform. The slower the operation the less difference these will have. As always: Benchmark, Benchmark, Benchmark

Simon Perepelitsa · Accepted Answer · 2011-06-22 00:38:44Z

if statement is a very cheap operation. You can check that using standard benchmarking tools.

require "benchmark" array = [1] * 100_000 Benchmark.bm do |bm| bm.report "with if" do array.each_with_index do |element, i| next if i == 1 element - 1 end end bm.report "without if" do array.each do |element| element - 1 end end end

Results:

 user system total real with if 0.020000 0.000000 0.020000 ( 0.018115) without if 0.010000 0.000000 0.010000 ( 0.012248)

It is about 0.006 second difference on a 100 000 elements array. You shouldn't care about that unless it becomes a bottleneck and I doubt it will.

butthead · Accepted Answer · 2011-06-22 16:54:39Z

Testing an actual for loop might be worth the five minutes it would take. It may be frowned on in Ruby circles, but that doesn't mean it is not ever worth using. When you call each or map or whatever, those methods use for loops any way. Avoid absolutes.

It also depends how big the array can get, at some n, one might become faster than the other. In this case, it is definitely not worth it.

If you don't need a specific element, maybe you don't need to store that row of data in a database. What is the difference between row 1 and the rest of the rows, in other words, why are you skipping it? Is the row with id=1 always going to have the the same data in it? If so, storing it as a constant would likely be better, and would make your question moot. Performance almost always costs more memory.

Unless Rails 3 does things differently, and you pull out the data and use id as the finder key, id=1 will be in element 0.

Unfortunately, Knuth's quote gets misinterpreted a lot and get used to excuse crappy, inefficient code that would not be written if the programmer was sufficiently educated, and thought about it for 5 seconds. Sure, spending a week trying to speed up code that you don't know is a problem or is a minor problem but this is more what Knuth was talking about. Performance is one of the most misunderstood and abused concepts in computer science.

Collectives™ on Stack Overflow

Performance: iterate over an array except for an element

4 Answers 4

1 Comment

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

Comments

Comments

Comments

Related