On 09/06/11 18:49, Steven Schveighoffer wrote:
On Thu, 09 Jun 2011 13:31:18 -0400, Ben Grabham <evil.nebs...@gmail.com>
wrote:
On 09/06/11 18:11, Steven Schveighoffer wrote:
On Thu, 09 Jun 2011 13:06:54 -0400, Ben Grabham <evil.nebs...@gmail.com>
wrote:
On 09/06/11 17:57, bearophile wrote:
Ben Grabham:
import std.range;
import std.stdio;
int main() {
auto a = recurrence!("a[n-1] + a[n-2]")(0,1);
int i = 0;
foreach(int n; a) {
if(i++> 20) break;
writefln("%d", n);
}
return 0;
}
This program does something similar to yours (but it doesn't print
newlines):
import std.stdio, std.range;
void main() {
auto fib = recurrence!q{ a[n-1] + a[n-2] }(0, 1);
writeln(take(fib, 21));
}
Bye,
bearophile
Yeah, thanks
I just wanted to post a bit of code which went wrong :P
Didn't look for optimisations.
Also, how come recurrence isn't properly lazy?
If I define a recurrence and iterate over it twice with foreach, it
takes the same amount of time due to the stack size being set. Is
there a way of defining a lazy list that stores the results when
calculated?
That's not lazy, that's caching. lazy is 'calculate this when asked'.
You can cache with array:
auto cached = array(take(fib, 21));
// cached now contains the first 21 elements of fib.
-Steve
I tried that, but how can I calculate the values only when I want
them? Would I have to store them in a linked list? Since if I know
that I will need 100000 prime numbers, it takes my old pc about 4.7
seconds to calculate them. But can I only calculate them when I need
them?
It's a recurring sequence. As such, each element depends on the previous
n elements. I don't see how you can only calculate them when needed,
unless you want to do some sort of memoization with recursion.
recurrence expects to be traversed in a certain order, it's sort of like
dynamic programming.
The array simply stores all the values needed to an array, so you can
re-access the same values without running through the recurrence.
One thing you could do is using Appender, you can continue a recurrence.
So let's say you need the 5th element of the array:
alias recurrence!q{ a[n-1] + a[n-2] } fib;
Appender!int app;
app.put(take(fib(0, 1), 5));
auto elems = app.data;
auto the5thElement = elems[4];
And now, you need the 10th element:
app.put(take(fib(elems[$-2], elems[$-1]), 10 - elems.length)); // extend
sequence to 10 elements
elems = app.data; // need to re-retrieve the elements
auto the10thElemet = elems[9];
Kind of ugly, but maybe it's close enough to what you want.
I am running through the recurrence twice so I don't want to calculate
it twice.
Yes, you only run through it once, then use the array with the cached
data to retrieve what you want. Accessing the array does not recalculate
the data.
The Appender solution simply keeps a running cache of the data. You
could probably abstract out the 'extending' function. In fact, this
whole thing could be abstracted into a 'cached recurrence' type.
-Steve
Thanks, that should do the trick!
At the moment I was using auto elems = array(chain(elems, take(primes -
elems.length))); or something similar to that
Also, when using a foreach, is there a special syntax that says include
the last number?
As an example, if I want to loop from -n to +n, I have to do foreach(i;
-n..n+1)
Thanks,
Nebster
