<div class="gmail_quote">On 9 September 2012 01:56, Mehrdad <span dir="ltr"><<a href="mailto:wfunction@hotmail.com" target="_blank">wfunction@hotmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
I was pretty excited to figure out that a one-liner FFT is<br>
possible in D!<br>
creal[] dft(creal[] v) { return v.length > 1 ? (p => chain(map!(q<br>
=> q[0] + q[1])(p), map!(q => q[0] -<br>
q[1])(p)))(zip(dft(v.stride(2)<u></u>.array()), map!(p => p[1] *<br>
expi(p[0] * -2 * PI / v.length))(zip(iota(v.length / 2),<br>
dft(v.drop(1).stride(2).array(<u></u>)))))).array() : v; }<br>
<br>
Of course, the Python version is still shorter:<br>
def dft(v): return (lambda e, o: map(add, e, o) + map(sub, e,<br>
o))(dft(v[0::2]), [o * rect(1, k * -2 * pi / len(v)) for k, o in<br>
enumerate(dft(v[1::2]))]) if len(v) > 1 else v<br>
<br>
but it's still cool (barring the unreadability, haha).<br>
Yay D!<br>
</blockquote></div><br><div>Very curious to know how this performs. Since it's making use of lots of templates from the standard library, how much do they influence efficiency? How well does the compiler do its job optimising this?</div>