From: Paul Lutus <nospam@...>
Date: 2006-11-27T04:45:12+09:00
Subject: Re: find index of first non zeo value in array

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