Кули Тьюки фактор твиддл в простом скрипте Python

Question

Я читаю, как работает метод Кули Тьюки , но у меня есть несколько проблем со следующим скриптом Python:

def fft_CT_twiddles(x, inverse = False, verbose = False, twiddles = None) :
    """
    Computes the DFT of x using Cooley-Tukey's FFT algorithm. Twiddle factors
    are precalculated in the first function call, then passed down recursively.
    """
    t = time.clock()
    N = len(x)
    inv = -1 if not inverse else 1
    if N % 2 :
        return dft(x, inverse, False)
    M = N // 2
    if not twiddles :
        twiddles = [math.e**(inv*2j*math.pi*k/N) for k in xrange(M)]+[N]
    x_e = x[::2]
    x_o  = x[1::2]
    X_e = fft_CT_twiddles(x_e, inverse, False, twiddles)
    X_o  = fft_CT_twiddles(x_o, inverse, False, twiddles)
    X = []
    for k in range(M) :
        X += [X_e[k] + X_o[k] * twiddles[k * twiddles[-1] // N]]
    for k in range(M,N) :
        X += [X_e[k-M] - X_o[k-M] * twiddles[(k - M) * twiddles[-1] // N]]
    if inverse :
        X = [j/2 for j in X]
    t = time.clock() - t
    if verbose :
        print "Computed","an inverse" if inverse else "a","CT FFT of size",N,
        print "in",t,"sec."
    return X

Что означает twiddles = [math.e ** (inv * 2j * math.pi * k / N) для k в xrange (M)] + [N] линия делает? Похоже на массив, но почему + [N]?

А зачем тогда обращаться к значению twiddles [-1]?

Я не могу понять это

Answer 1

Пытаться объяснить код, когда уровень знаний человека, задающего вопрос, неизвестен, затруднительно.Тем не менее, здесь говорится:

1. В python есть оператор конкатенации для последовательностей nl.+ поэтому строка twiddles = создает последовательность некоторого рода и добавляет к ней число N.
2. twiddles[-1] обращается к последнему элементу в последовательности здесь, к номеру N, как предлагают комментарии.
3. выражение последовательности twiddles использует комплексные числа для генерации последовательности, состоящей из N точек на единичном круге, путем деления ее на N равных срезов.

Answer 2

Код, о котором вы спрашивали, делает следующее:

+[N] # appends N to the end of the array


twiddles[-1] # is the last element of the array ( the N in this case ).

Код, по-видимому, добавляет 'N' в конец массива twiddles просто для удобства, чтобы его можно было использовать позже, и чтобы его можно было легко передать в функцию как часть аргумента twiddles вместо передавая его как отдельную переменную.