Что использовать вместо списка в python для циклов - пример Фурье из Java - PullRequest
Новая
       16

Что использовать вместо списка в python для циклов - пример Фурье из Java

0 голосов
/ 01 мая 2019

Я пытаюсь закодировать преобразование Фурье вручную в Python, но у меня меньше опыта в Python, чем в Java.

Я предполагаю, что списки - не лучшая вещь для использования в цикле for, и я также предполагаю, что этот код не очень питоничен, и может быть лучший синтаксис для того, что я пытаюсь сделать.

Я ввожу простой тест = [10, 10, 10, -10, -10, -10, 10, 10, 10, -10, -10, -10]

Я получаю сообщение об ошибке «list». Атрибут объекта «instert» доступен только для чтения.

Какой тип данных будет лучше? 


import math
pi = math.pi

def dft(x):
    X=[]
    N = len(x)
    re = 0
    im = 0
    for k in range(0,N):
        for n in range(0,N):
            phi = (2*pi*k*n)/N

            re += (x[n]*math.cos(phi))
            im -= (x[n]*math.sin(phi))

    re = re/N
    im = im/N
    h = (re, im)
    X.insert = (k,h) #object with real and imaginary component

    return (X)

Ответы [ 2 ]

2 голосов
/ 01 мая 2019

Список в порядке.

X.insert = (k,h) пытается присвоить кортеж (k, h) атрибуту insert, равному X. Вместо этого вы хотите вызвать метод insert. 

X.insert(k,h)

Примечание: Вам также необходимо проверить отступ. Это утверждение в настоящее время не находится внутри цикла.

0 голосов
/ 01 мая 2019

Чтобы ответить на ваш вопрос напрямую: у вас правильная структура данных (т. Е. list).Тем не менее, у вас также есть некоторые серьезные проблемы с Python / алгоритмом. Давайте начнем с проблем высокого уровня, а затем перейдем оттуда ...

Прежде всего, то, что у вас есть, наивноDFT, а не FFT .Вопрос помечен БПФ, хотя вы нигде не упоминаете БПФ в самом вопросе, поэтому, возможно, вы уже знаете это, но я подумал, что упомяну это для тех, кто не может этого сделать.БПФ работает в O(N log N).То, что у вас есть, работает в O(N^2).Большая разница.Они оба выводят одно и то же, так как оба являются преобразованиями Фурье (хотя масштабные коэффициенты могут отличать их с точки зрения реализации), но один из них быстрый (отсюда F FT).Использование наивного DFT обычно не приносит вам большой выгоды: мы используем FFT, потому что они эффективны в вычислительном отношении.Если бы это было не так, мы бы сделали все во временной области и покончили бы с этим!

Во-вторых, ваш отступ / алгоритм неверен. Вам необходимо иметь: 

re = 0
im = 0

прямо перед каждым внутренним циклом.Кроме того, у вас должен быть этот раздел (который я изменил для корректности): 

# re = re/N This is not a part of the definition, remove it
# im = im/N Also not a part of the definition, remove it
h = (re, im)
X.insert(k, h)

внутри первого цикла.

В-третьих, Python имеет встроенный типпредставлять комплексные числа. Итак, вы хотите: 

# There are other (more idiomatic?) ways to create a complex number, 
# but this probably looks natural to a Java dev
h = complex(re, im)

Итак, мои модификации, чтобы сделать DFT-код корректным (по определению Википедии), выглядят так: 

import math
pi = math.pi

def dft(x):
    X=[]
    N = len(x)
    for k in range(0,N):
        re = 0
        im = 0
        for n in range(0,N):
            phi = (2*pi*k*n)/N

            re += (x[n]*math.cos(phi))
            im -= (x[n]*math.sin(phi))

        h = (re, im)
        X.insert(k, complex(re, im))

    return (X)

Наконец, в Python есть несколько чрезвычайно мощных встроенных и сторонних библиотек, и разумно воспользоваться ими. Хотя numpy технически не встроен, он так широко используетсячто это также может быть (и я думаю, что на самом деле он поставляется с CPython на MacOS).numpy будет быстрее, правильнее и будет иметь лучшую функциональность / поддержку / инструментарий, чем все, что вы собираетесь собрать вместе.БПФ уже давно решаемая проблема: нет смысла изобретать велосипед!Вы можете получить numpy в своей экосистеме с простым pip install numpy в вашей оболочке (да, это так просто, нет Maven, нет Gradle, нет ANT, нет чепухи!)

После исправлений, описанных выше, мыget: 

import numpy as np
def pretty_print_result(x):
    for item in x:
        print(item)
numpy_result = np.fft.fft([1,2,3,4,5,6])  # <-- This is the most "Pythonic" thing to do imo!
our_result = dft([1,2,3,4,5,6])
print('Numpys: ')
pretty_print_result(numpy_result)
print()
print('Ours: ')
pretty_print_result(our_result)

вывод: 

Numpys:
(21+0j)
(-3+5.19615242271j)
(-3+1.73205080757j)
(-3+3.10862446895e-15j)
(-3-1.73205080757j)
(-3-5.19615242271j)

Ours:
(21+0j)
(-3.000000000000001+5.196152422706631j)
(-2.999999999999996+1.7320508075688759j)
(-3-1.286250527486674e-14j)
(-3.0000000000000084-1.7320508075688812j)
(-3.000000000000009-5.196152422706645j)

Это тот же результат, за исключением некоторых махинаций с плавающей запятой.Опять же, numpy почти наверняка будет более точным и быстрым, чем все, что вы собираетесь собирать вместе, и я не могу рекомендовать его достаточно для научных вычислений.

Быстрое сравнение скорости (после загрузки этого в IPython и сохранения измененной функции dft в файле с именем test.py): 

In [1]: from test import dft

In [2]: import numpy as np

In [3]: %timeit np.fft.fft([1,2,3,4,5])
The slowest run took 9.24 times longer than the fastest. This could mean that an intermediate result is being cached.
100000 loops, best of 3: 12.5 µs per loop

In [4]: %timeit dft([1,2,3,4,5])
10000 loops, best of 3: 21.7 µs per loop

Хмм выглядит не так уж плохо.Это примерно в два раза быстрее.Но помните, что numpy алгоритмически быстрее (ну ... он также запускает и собственный код), что означает, что с ростом входных данных сам коэффициент ускорения будет увеличиваться с ростом входных данных: 

In [5]: %timeit np.fft.fft(range(1000))
10000 loops, best of 3: 130 µs per loop

In [6]: %timeit dft(range(1000))
1 loop, best of 3: 922 ms per loop

Теперь numpy более чем в 1000 раз быстрее, и он будет становиться все быстрее и быстрее по сравнению с простой версией при увеличении размера ввода.

HTH!И удачи на вашем пути Python!

...