Empirically testing whether FWT or FFT is faster. Disclaimer: I don't understand wavelets.
Speed of FFT implementation doesn't care what the data is:
In [23]: a = rand(2**20)
In [24]: timeit fft(a)
10 loops, best of 3: 128 ms per loop
In [25]: a = rand(2**20)