On Tuesday, 25 September 2012 at 17:48:49 UTC, jerro wrote:
import std.algorithm, std.math, std.range;
typeof(R.init.stride(0)) dft(R)(R v)
{
return v.length <= 1
? v.stride(1)
: (p =>
chain(map!(q => q[0] + q[1])(p),
map!(q => q[0] - q[1])(p)))
(zip(dft(v.stride(2)),
map!(p => p[1] * expi(p[0] * -2 * PI / v.length))
(zip(iota(v.length / 2),
dft(v.drop(1).stride(2))))));
}
void main() { dft([1.0, 2, 3]); }
Which gives the following error:
Test.d(5): Error: incompatible types for ((stride(v,1u)) ?
((*delegate @system
Result(Zip!(Result,MapResult!(__lambda8,Zip!(Result,Result)))
p)
{
return chain(map(p),map(p));
}
)(zip(dft(stride(v,2u)),map(zip(iota(v.length() /
2u),dft(stride(drop(v,1u),2u)))))))): 'Result' and 'Result'
Test.d(10): Error: template instance Test.dft!(Result) error
instantiating
Test.d:19: instantiated from here: dft!(double[])
Test.d(5): Error: incompatible types for ((stride(v,1u)) ?
((*delegate @system
Result(Zip!(Result,MapResult!(__lambda8,Zip!(Result,Result)))
p)
{
return chain(map(p),map(p));
}
)(zip(dft(stride(v,2u)),map(zip(iota(v.length /
2u),dft(stride(drop(v,1u),2u)))))))): 'Result' and 'Result'
Test.d(19): Error: template instance Test.dft!(double[]) error
instantiating
How should I interpret it?
Thanks!
One possible reason for this error could be that you are
returning a result of chain() if length is larger than 1 and a
result of stride() otherwise.
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.
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.
