Какова самая быстрая реализация FFT в Python?
Кажется, numpy.fft и scipy.fftpack оба основаны на fftpack, а не FFTW. Является ли fftpack столь же быстрым, как FFTW? Как насчет использования многопоточного БПФ или использования распределенного (MPI) FFT?
Конечно, вы могли бы обернуть любую реализацию FFT, которую вы хотели бы протестировать, используя Cython или другие аналогичные инструменты, которые позволяют вам обращаться к внешним библиотекам.
Если вы собираетесь тестировать реализации FFT, вы можете также взглянуть на коды на основе GPU (если у вас есть доступ к надлежащему оборудованию). Есть несколько: reikna.fft, scikits.cuda.
Существует также основанная на процессоре python FFTW-обертка pyFFTW.
(Существует pyFFTW3, но он не так активно поддерживается как pyFFTW, и он не работает с Python3. (источник))
У меня нет опыта ни с одним из них. Вероятно, вам придется немного погулять и сравнить различные коды для вашего конкретного приложения, если вам важна скорость.
Для теста, описанного в https://gist.github.com/fnielsen/99b981b9da34ae3d5035, я обнаружил, что scipy.fftpack отлично работает по сравнению с моим простым приложением pyfftw через pyfftw.interfaces.scipy_fftpack, за исключением данных с длина, соответствующая простому числу.
Кажется, есть некоторые затраты на установку, связанные с вызовом pyfftw.interfaces.scipy_fftpack.fft в первый раз. Второй раз он быстрее. Numpy и scipy fftpack с простым номером ужасно работают для размера данных, которые я пробовал. В этом случае CZT быстрее. Несколько месяцев назад на Scipy Github была поставлена проблема по поводу проблемы, см. https://github.com/scipy/scipy/issues/4288
20000 prime=False
padded_fft : 0.003116
numpy_fft : 0.003502
scipy_fft : 0.001538
czt : 0.035041
fftw_fft : 0.004007
------------------------------------------------------------
20011 prime=True
padded_fft : 0.001070
numpy_fft : 1.263672
scipy_fft : 0.875641
czt : 0.033139
fftw_fft : 0.009980
------------------------------------------------------------
21803 prime=True
padded_fft : 0.001076
numpy_fft : 1.510341
scipy_fft : 1.043572
czt : 0.035129
fftw_fft : 0.011463
------------------------------------------------------------
21804 prime=False
padded_fft : 0.001108
numpy_fft : 0.004672
scipy_fft : 0.001620
czt : 0.033854
fftw_fft : 0.005075
------------------------------------------------------------
21997 prime=True
padded_fft : 0.000940
numpy_fft : 1.534876
scipy_fft : 1.058001
czt : 0.034321
fftw_fft : 0.012839
------------------------------------------------------------
32768 prime=False
padded_fft : 0.001222
numpy_fft : 0.002410
scipy_fft : 0.000925
czt : 0.039275
fftw_fft : 0.005714
------------------------------------------------------------
Пакет pyFFTW3 уступает по сравнению с библиотекой pyFFTW, по крайней мере, мудрая реализация. Поскольку они оба обертывают библиотеку FFTW3, я думаю, что скорость должна быть одинаковой.
Сайт FFTW показывает, что fftpack работает примерно на 1/3 быстрее, чем FFTW, но с механически переведенным шагом Fortran-to-C по компиляции C, и я не знаю, использует ли numpy/scipy более прямую компиляцию Fortran. Если производительность важна для вас, вы можете подумать о компиляции FFTW в библиотеку DLL/shared и использовать ctypes для доступа к ней или создать пользовательское расширение C.
Где я работаю, некоторые исследователи скомпилировали эту библиотеку Fortran, которая настраивает и вызывает FFTW для конкретной проблемы. Эта библиотека Fortran (модуль с некоторыми подпрограммами) ожидает некоторые входные данные (2D-списки) из моей программы Python.
Что я сделал, так это создать небольшое C-расширение для Python, обертывающее библиотеку Fortran, где я в основном называет "init" для настройки планировщика FFTW и еще одну функцию для подачи моих 2D-списков (массивов) и "вычисления".
Создание C-расширений - небольшая задача, и там есть много хороших обучающих программ для этой конкретной задачи.
Хорошо, что этот подход заключается в том, что мы получаем скорость.. много скорости. Единственный недостаток заключается в C-расширении, где мы должны перебирать список Python и извлекать все данные Python в буфер памяти.
FFTW3, по-видимому, является самой быстрой версией, которая хорошо обернута. Связывание PyFFTW в первом ответе работает. Вот код, который сравнивает время выполнения: test_ffts.py