Denis Koroskin wrote:
On Tue, 03 Feb 2009 21:25:21 +0300, Sean Kelly <[email protected]>
wrote:
Andrei Alexandrescu wrote:
Ary Borenszweig wrote:
Andrei Alexandrescu escribió:
I've updated my code and documentation to include series (as in
math) in the form of infinite ranges. Also series in closed form
(given n can compute the nth value without iterating) are supported
as random-access ranges.
Also Stride is provided. The Matrix container (speaking of
scientific computing with D!) will support various representational
choices, most importantly the ones endorsed by high-performance
libraries. For Matrix, Stride is an important component as I'm sure
anyone who's ever written a matrix knows.
http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_range.html
http://ssli.ee.washington.edu/~aalexand/d/web/phobos/std_algorithm.html
Back to series. Finally my dream has come true: I can define a
decent Fibonacci series clearly and efficiently in one line of
code. No more idiotic recursive function that takes exponential
time to finish!
auto fib = series!("a[n-1] + a[n]")(1, 1);
// write 10 Fibonacci numbers
foreach (e; take(10, fib)) writeln(e);
That is *SO* awesome!!
Thanks! Constant-space factorial is just a line away:
auto fact = series!("a[n] * (n + 1)")(1);
foreach (e; take(10, fact)) writeln(e);
Awesome :-) I think that proves the efficacy of the approach all by
itself.
Sean
I wonder how efficent it is? Does it store last few sequence elements or
re-compute then again and again?
I wouldn't use it in the latter case.
I wouldn't use it either, in fact I have a dim view of all books,
articles, and courses that promote exponential-time Fibonacci and
linear-space factorial. It just promotes sloppy algorithmic thinking
under the pretense that recursion is cool. (I also have a dim view of
the FP proponents who promote the quicksort that actually doesn't sort
in place and returns new arrays by value every iteration, consuming O(n
log n) extra memory. But I digress.)
The size of the state held by a series is equal to the number of initial
arguments passed when it is constructed. The arguments are stored in a
fixed-size array sitting in the series object. So:
auto fib = series!("a[n-1] + a[n]")(1, 1);
holds an int[2], initialized with [1, 1]. The current index in the
series (a size_t initialized to 0) completes the state size.
When fib.next is called, the ((n+1) % 2)th element in the array is
overwritten with the result of a[(n-1)%2] + a[n%2]. Then n is
incremented. fib.head returns a[n%2].
In the factorial case it's simpler because the state size is 1. Since
the state size is used as a compile-time constant, the compiler has the
opportunity to optimize away calculations like n%1.
Andrei
