2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Есть ли связь между сортировкой и преоб Фурье?
Сообщение26.10.2011, 13:28 
можно ли с помощью преобразования Фурье (прямого и обратного) отсортировать массив?
Если функциональная связь данных алгоритмов

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение26.10.2011, 14:18 
Аватара пользователя
Нет. Нельзя. Несмотря на то, что некоторая аналогия в структуре алгоритмов БПФ и некоторых алгоритмов сортировки существует.

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение26.10.2011, 14:41 
спасибо. У кого можно прочитать про обоснования не возможности и следствия из этого.

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение26.10.2011, 18:21 
Аватара пользователя
Вопрос не корректный. Что значит с помощью преобразования Фурье сделать сортировку?
Я могу к примеру определить MySort как MySort=QSort(IFFR(FFT(a))) это значит что я сделал сортировку c помощью Фурье или не значит?

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение27.10.2011, 09:15 
Точнее формулирую.

Существует ли обобщающая функция f(X, (x,x)->x) после свертки дающая
sort(X)=f(X,(x1,x2)->(x1>x2)?(x1,x2):(x2,x1))
fuer(X)=f(X,(x1,x2)....)

либо как вариант выполняющий сортировку с использованием константного числа преобразования фурье и количества операций операций пропорциональное числу элементов

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение27.10.2011, 09:27 
Аватара пользователя
Между всеми алгоритмами есть связь - все они состоят из блоков, ветвлений и циклов :). Сортировка происходит по какому-то критерию, преобразование Фурье даёт упорядоченные данные - спектр. Почитайте "Алгебраическая алгоритмика", там должно быть что-то такое, хотя я может быть путаю с умножением полиномов.

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение27.10.2011, 18:57 
2erwins
Цитата:
Существует ли обобщающая функция f(X, (x,x)->x) после свертки дающая...

Увы, совершенно не понятно, что вам нужно. Кстати, не представляю как вообще можно сортировку выполнять через свертку, надо подумать...

Хотя вопроса вашего не понял и искомую функцию предложить не смогу, но попробую пофантазировать.

Например, пусть вместо вашей "(x,x)->x" будет просто функция g_sort с побочным эффектом, что-то вроде (это даже не псевдокод, а какой-то небрежный слепок потока сознания :) ):
Код:
y[]

g_sort(i, j)
{
    if(j>=n-1) return;

    if(y[j]>y[j+1])
        swap(y[j], y[j+1]);
}


Это я её под сортировку пузырьком подогнал. Тогда f будет примерно такой:
Код:
f(x[], g)
{
    y=x;

    for(i=0; i<length(x); i++)
        for(j=0; j<length(y); j++)
            g(i, j);

    x=y;
}


А можно, существенно не изменяя f, подсунуть ей вместо g_sort другую функцию g_dft:
Код:
g_dft(i, j)
{
    re[i]+=y[j]*cos(2*pi*i*j/length(y));
    im[i]-=y[j]*sin(2*pi*i*j/length(y));
}


В результате:
Код:
sort(x[]) {f(x, g_sort);}
fourier(x[]) {f(x, g_dft);}


Если свернуть побочные эффекты (офункционализировать код :) ) и реализовать более адекватную схему сортировки, e.g. вариацию на тему сортирующих сетей, то что-то близкое к требуемой вами f(...) может быть и получится (а может быть в моей писанине и вовсе нет никакого смысла :) )...

Но как это связано с первоначальным вопросом? :)

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение27.10.2011, 20:44 
просто. Есть сортировка Хола имеющая порядок для конечного домена $n\ln(\ln(n))2^{\ln!(n)}$ где $\ln!(n)$ суперлогорифм
Возможно ли изменение преобразования фурье аналогичным образом?

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение27.10.2011, 20:55 
Аватара пользователя
Что-то я такой сортировки не найду. Ни в книжке Холла не в книге Кнута. Откуда вы её взяли?

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение27.10.2011, 21:09 
Извияюсь, Хана, вот только у Кнута ее быть не могло, так как она появилась в 2002
http://web.mit.edu/benmv/Public/thorup.pdf

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение27.10.2011, 21:51 
Аватара пользователя
Свёртка ведь соответствует действию линейного фильтра на некоторый сигнал, а преобразование Фурье позволяет заменить свёртку функций умножением. Сигнал здесь - последовательность значений $X$. Оператор сортировки $F: X \to N$ отображающий множество значений $X$ на множество порядковых номеров $N$, если он линеен, не должен зависеть от предыстории, то есть должен определять номер по значению локально, что в случае сортировки невозможно. То есть $F$ у нас - нелинейный и свёрткой не представим. Вроде так?

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение27.10.2011, 22:10 
2erwins
Спасибо за ссылку, надо будет почитать.

Возможно вам будет интересна вот эта странная тема: количество сложений и умножений при вычислении формул.

 
 
 
 Re: Есть ли связь между сортировкой и преоб Фурье?
Сообщение27.10.2011, 22:37 
Аватара пользователя
Circiter
Возьмём сортировку пузырьком и на её основе построим через преобразование Фурье.
Берем Фурье переходим в спектральную область.
Дальше делаем пузырьковую сортировку. Сравнение есть, вычитание двух элементов и сравнение знака.
Вычитание для спектральной области заменимо свёрткой (аналогично дифференцирования) или можно через две свёртке с вычитанием.
Что касается обмена элементов, то это можно проделать через 2 операции вычитания и сравнения знака.

erwins

Цитата:
преобразование Фурье есть n*ln(n) и есть ли вероятность что возможен шаг похожий на сортировку Хола

как и в случае обычной сортировки, преобразование Фурье на произвольном кольце имеет порядок n*ln(n)

в тоже время, если в сортировке добавить требование конечности кольца, то удается получить порядка n*ln(ln(n))*2^(ln*(n)) что значительно меньше.


Есть по разрядная сортировка, которая выполняется за O(n), а есть обычная быстрая сортировка O(n*Log(n))
Вполне логично что мы можем построить сортировку по скорости между этими двумя.

Что касается преобразования Фурье. То его можно делать через свёртку. Свёртка может быть O(n).
Вот в конечном поле бпф можно делать быстрее чем O(n*log(n)) умножений. Но полноценного доказательства у меня нету.

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group