std.range should support recursion (Was: One-line FFT, nice!)
Mehrdad
wfunction at hotmail.com
Tue Sep 25 17:42:07 PDT 2012
On Tuesday, 25 September 2012 at 18:33:45 UTC, jerro wrote:
>>
>> I think there is one thing in this code that will hurt
>> performance much, much, more than allocations. This code will
>> compute elements of the result lazily. So each time you want
>> to read an element from the resulting range, O(log(n))
>> functions passed to map() will need to be computed. The
>> problem is that each of those functions computes sine and
>> cosine, so sine and cosine need to be computed O(log(n)) times
>> for each element. To get all n elements, you will need to
>> compute them O(n log(n)). Because computing sine and cosine is
>> about two orders of magnitude slower than multiplication and
>> division, this will be very slow.
>
> I was wrong about the complexity. Because each element of the
> result depends on all the elements of the argument range, you
> actually need O(n) function calls to compute each element of
> the result and O(n*n) function calls(and sine and cosine
> computations) to compute all of them. You would need to use
> memoization to get reasonable complexity.
Great point, I hadn't really thought about the laziness before --
I was doing this in Python and just thought it might be fun to
translate it to D. :P
> I'd like to add that I don't think you can make this work the
> way you meant it to. The problem is that you return a chain
> when the length is 2, a chain of chains when the length is 4,
> and so on. What fft of length n would actually need to return
> is a binary tree of ranges with n leaves. The size of memory
> needed for the value returned from fft therefore depends on the
> length of the range it was given as an argument. So you need to
> either use heap allocated memory for the return type, or the
> return type needs to depend on the parameter range's length,
> which would mean that the parameter range's length needs to be
> a template parameter.
Ohh huh... sounds like you're right, lemme think about it a bit
more though.
Thanks! :)
More information about the Digitalmars-d
mailing list