Улучшение производительности FFT в Python

Какова самая быстрая реализация FFT в Python?

Кажется, numpy.fft и scipy.fftpack оба основаны на fftpack, а не FFTW. Является ли fftpack столь же быстрым, как FFTW? Как насчет использования многопоточного БПФ или использования распределенного (MPI) FFT?

Ответы

Ответ 1

Конечно, вы могли бы обернуть любую реализацию FFT, которую вы хотели бы протестировать, используя Cython или другие аналогичные инструменты, которые позволяют вам обращаться к внешним библиотекам.

GPU на основе

Если вы собираетесь тестировать реализации FFT, вы можете также взглянуть на коды на основе GPU (если у вас есть доступ к надлежащему оборудованию). Есть несколько: reikna.fft, scikits.cuda.

CPU на основе

Существует также основанная на процессоре python FFTW-обертка pyFFTW.

(Существует pyFFTW3, но он не так активно поддерживается как pyFFTW, и он не работает с Python3. (источник))

У меня нет опыта ни с одним из них. Вероятно, вам придется немного погулять и сравнить различные коды для вашего конкретного приложения, если вам важна скорость.

Ответ 2

Для теста, описанного в 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
------------------------------------------------------------

Ответ 3

Пакет pyFFTW3 уступает по сравнению с библиотекой pyFFTW, по крайней мере, мудрая реализация. Поскольку они оба обертывают библиотеку FFTW3, я думаю, что скорость должна быть одинаковой.

https://pypi.python.org/pypi/pyFFTW

Ответ 4

Сайт FFTW показывает, что fftpack работает примерно на 1/3 быстрее, чем FFTW, но с механически переведенным шагом Fortran-to-C по компиляции C, и я не знаю, использует ли numpy/scipy более прямую компиляцию Fortran. Если производительность важна для вас, вы можете подумать о компиляции FFTW в библиотеку DLL/shared и использовать ctypes для доступа к ней или создать пользовательское расширение C.

Ответ 5

Где я работаю, некоторые исследователи скомпилировали эту библиотеку Fortran, которая настраивает и вызывает FFTW для конкретной проблемы. Эта библиотека Fortran (модуль с некоторыми подпрограммами) ожидает некоторые входные данные (2D-списки) из моей программы Python.

Что я сделал, так это создать небольшое C-расширение для Python, обертывающее библиотеку Fortran, где я в основном называет "init" для настройки планировщика FFTW и еще одну функцию для подачи моих 2D-списков (массивов) и "вычисления".

Создание C-расширений - небольшая задача, и там есть много хороших обучающих программ для этой конкретной задачи.

Хорошо, что этот подход заключается в том, что мы получаем скорость.. много скорости. Единственный недостаток заключается в C-расширении, где мы должны перебирать список Python и извлекать все данные Python в буфер памяти.

Ответ 6

FFTW3, по-видимому, является самой быстрой версией, которая хорошо обернута. Связывание PyFFTW в первом ответе работает. Вот код, который сравнивает время выполнения: test_ffts.py