CODEWITHSUNDEEP
ruby-on-railsrubyarraysperformanceindexing
user502052
user502052

Reputation: 15259

Performance: iterate over an array except for an element

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?

Upvotes: 3

Views: 7868

Answers (4)

butthead
butthead

Reputation: 11

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.

Upvotes: 1

Nemo157
Nemo157

Reputation: 3589

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

Upvotes: 1

Simon Perepelitsa
Simon Perepelitsa

Reputation: 20639

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.

Upvotes: 1

DigitalRoss
DigitalRoss

Reputation: 146053

  1. Make program work
  2. Profile
  3. 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?

Upvotes: 8

Related Questions