Find index of first non zeo value in array

ruby-talk
21

dblack@wobblini.net wrote:

  This message is in MIME format. The first part should be readable text,
  while the remaining parts are likely unreadable without MIME-aware
  tools.

Mr. Black:

When you post MIME content in a plain-text Usenet newsgroup, people using
canonical Usenet software cannot reply to your posts without taking
extraordinary steps. Please follow established conventions for Usenet
posts.

Now, after a bit of cutting and pasting:

This exchange relates to something I've been pondering for a while,
namely: is there always (or very, very often) an inverse relation
between elegance of code and efficiency?

I venture to guess there as many exceptions to this rule as there are
examples of it -- which, if you think about it, reduces the correlation to
chance, e.g. no correlation.

One of my favorite examples that _confirms_ the thesis is computing
Fibonacci numbers in a way that seems elegant but is extremely inefficient:

def fib(n)
  if(n > 1)
    n = fib(n-1) + fib(n-2)
  end
  return n
end

This approach is often seen in programming textbooks meant to introduce the
idea of recursion. But if it is examined critically or profiled, it is
terribly inefficient compared to its alternatives.

By contrast, there are many examples where an elegant solution is
simultaneously easier to understand and more efficient than a more
laborious alternative. Here is a way to get several levels of numerical
derivatives from a function in a way that is easier to grasp than its
alternatives, and yet represents an efficient aproach:

···

------------------------------------------------

#!/usr/bin/ruby -w

def nderive(x,dx,n,proc)
   if(n > 0)
      return (nderive(x+dx,dx,n-1,proc)
        - nderive(x-dx,dx,n-1,proc)) / (2 * dx)
   else
      return proc.call(x)
   end
end

x = 2
dx = 0.01;

minp = 1
maxp = 6
maxd = 5

printf("%7s","")
0.upto(maxd) do |n|
   s = "f" + "'" * n + "(x)"
   printf("%-12s",s)
end

puts

minp.upto(maxp) do |p|
   proc = Proc.new {|q| q ** p }
   print "#{"#{x}^#{p}"}"
   0.upto(maxd) do |n|
      y = nderive(x,dx,n,proc)
      printf("%12.6f",y)
   end
   puts ""
end

------------------------------------------------

Output:

       f(x) f'(x) f''(x) f'''(x) f''''(x) f'''''(x)
2^1 2.000000 1.000000 -0.000000 -0.000000 0.000000 0.000000
2^2 4.000000 4.000000 2.000000 0.000000 0.000000 0.000000
2^3 8.000000 12.000100 12.000000 6.000000 0.000000 0.000002
2^4 16.000000 32.000800 48.000800 48.000000 24.000000 0.000010
2^5 32.000000 80.004000 160.008000 240.006000 240.000000 120.000009
2^6 64.000000 192.016000 480.048000 960.072000 1440.048000 1440.000066

I want to emphasize this is not just an example pulled out a hat. There are
plenty of confirming examples for the thesis that "elegant" can be
strongly, positively correlated with "efficient".

I think overall there is no general correlation between the elegant and the
efficient. I can't prove it, but I think it's true.

--
Paul Lutus
http://www.arachnoid.com

22

Devin Mullins wrote:

James Edward Gray II wrote:
> I believe there has been talk in the past of having index() take a
> block for matching.
Meh... talk schmalk...

class Array
   alias orig_index index
   def index(*args)
     return orig_index(*args) unless block_given?
     (0...length).each do |i|
       return i if yield self[i]
     end
     nil
   end
end

Hrm, I assumed that using #each_with_index would be speedier, since
there would be no Ruby call to the # method of the array for each
iteration. Instead, it's much slower:

class Array
    alias orig_index index

    def index1(*args)
      return orig_index(*args) unless block_given?
      (0...length).each do |i|
        return i if yield self[i]
      end
      nil
    end

  def index2( *args )
    return orig_index(*args) unless block_given?
    each_with_index{ |value,index| return index if yield value }
    nil
  end
end

require 'benchmark'
N = 1000
a = (1..1000).to_a
Benchmark.bmbm{ |x|
  x.report( '0...length' ){
    N.times{ |i| a.index1{ |v| v==i } }
  }

  x.report( 'each_with_i' ){
    N.times{ |i| a.index2{ |v| v==i } }
  }
}

#=> Rehearsal -----------------------------------------------
#=> 0...length 2.060000 0.030000 2.090000 ( 2.333379)
#=> each_with_i 3.340000 0.050000 3.390000 ( 3.727040)
#=> -------------------------------------- total: 5.480000sec
#=>
#=> user system total real
#=> 0...length 2.060000 0.020000 2.080000 ( 2.286168)
#=> each_with_i 3.350000 0.040000 3.390000 ( 3.716824)

23

Phrogz wrote:

Hrm, I assumed that using #each_with_index would be speedier, since
there would be no Ruby call to the # method of the array for each
iteration. Instead, it's much slower:

Hrm, that is odd. I assure you it was purely by accident that I picked the faster implementation. Maybe it has something to do with each_with_index being implemented by Enumerable, vice Array? I dunno why.... should just delegate to each, and keep a counter around.

?
Devin

24

Devin Mullins wrote:

Phrogz wrote:
> Hrm, I assumed that using #each_with_index would be speedier, since
> there would be no Ruby call to the # method of the array for each
> iteration. Instead, it's much slower:
Hrm, that is odd. I assure you it was purely by accident that I picked
the faster implementation. Maybe it has something to do with
each_with_index being implemented by Enumerable, vice Array? I dunno
why.... should just delegate to each, and keep a counter around.

My totally uninformed guess is that it has something to do with more
than one parameter to the block, possibly creating a temporary array
for the value/index pair and then splatting them on each call.