Здравствуйте, kochetkov.vladimir, Вы писали:
KV>Здравствуйте, PC_2, Вы писали:
PC_>>Спасибо, но это не Квик сорт. Это его пародия. PC_>>Алгоритм Квик сорт включает перемещение элементов на "одном участке" памяти. PC_>>Тоесть не требует дополнительных ресурсов памяти.
PC_>>Тоесть банально этот код не решает поставленную задачу. Точка.
KV>Предлагаю со столь смелым заявлением отправляться сразу сюда: http://rsdn.ru/forum/decl/, а я пока за попкорном сбегаю. Троеточие...
Давно хотел задать этот вопрос. Меня это интересует совсем не с той целью, чтобы убедиться в том, что кратко записанный алгоритм не может быть перобразован в оптимальный код, а наоборот, мне хотелось вы увидеть, что действительно может быть преобразован и понять, как.
1. Может ли?
2. Если да, то как? Интересует последовательность преобразований, алгоритм работы оптимизирующего компилятора в данном конкретном случае (общие стространичные статьи по устройству оптимизатора, например, в хаскеле на данный момент не интересуют).
Хотелось бы увидеть не эвристический алгоритм.
3. Хотелось бы увидеть код на высокоуровневом языке программирования и листинг машинного или байт кода.
Разумеется требуется получить код, который выполняет быструю сортировку без использования дополнительной памяти больше чем с*lg(n).
PS На самом деле, это очень важный вопрос и его разрешение сильно помогло бы популяризации функциональных языков программирования. Уверен, многие из тех, кто интересуется функциональным программированием, но так и не начал использовать его для чего-то большего чем просто "поиграться", не делают этого именно потому, что у них не укладывается в голове, как это можно писать такие неоптимальные с точки зрения производительности (не программиста, а вычисления на компьютере ) программы.
Статьи по функциональому программированию нужно начинать не с определения натурального числа (мне всегда было, что же там получается в итоге при компиляции. кстати что?) или факториала сверткой по списку и как это круто, а с того, что некоторый код на традиционном ЯП можно кратко записать использовав ФП, а в резулятате получить тот же машинный код. И таким образом показывать, какие же реальные проблемы может решить функционально программирования, не создав новых.
Re: Quicksort: краткость записи vs производительность кода
Здравствуйте, Aleх, Вы писали:
A>Разумеется требуется получить код, который выполняет быструю сортировку без использования дополнительной памяти больше чем с*lg(n).
Здравствуйте, pierre, Вы писали:
P>Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort,
это никак не видно из кода на наскеле. это просто так получается из за особеностей реализации
[y|y->xs,y<=x]
P> а классический inplace qsort на C -- не stable.
т.е. можно периписать хаскельный код так чтобы он был не stable, но такой же оптимальный как и сишный?
и при этом не потерял простоты описания?
... << RSDN@Home 1.2.0 alpha 4 rev. 1227>>
Re[3]: Quicksort: краткость записи vs производительность код
Здравствуйте, cvetkov, Вы писали:
C>Здравствуйте, pierre, Вы писали:
P>>Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort, C>это никак не видно из кода на наскеле. это просто так получается из за особеностей реализации
Очень даже видно, особенно если прочитать статью на википедии, где ровно то же написано псевдокодом. Ну, еще, правда, надо знать что list comprehensions сохраняют порядок.
C>т.е. можно периписать хаскельный код так чтобы он был не stable, но такой же оптимальный как и сишный? C>и при этом не потерял простоты описания?
Хаскельный -- вряд ли, там не одобряются изменяемые структуры данных. А так можно думать как короче записать классический partition. С ходу ничего хорошего не получается, все-таки это довольно интеллектуальный лохоритм.
Re[2]: Quicksort: краткость записи vs производительность код
Здравствуйте, DarkGray, Вы писали:
DG>inplace qsort легко превратить в stable. достаточно хвост разворачивать обратно — это даст итогую сложность 2 * n log n
А "хвост разворачивать обратно" -- это как?
Re[4]: Quicksort: краткость записи vs производительность код
Казалось бы, из любой нестабильной сортировки легко получить стабильную, если модифицировать функцию сравнения таким образом, чтобы при равенстве аргументов она учитывала их взаимное расположение и считала, что тот, который идет раньше — он меньше (если мы сортируем по возрастанию).
Re[3]: Quicksort: краткость записи vs производительность код
Здравствуйте, cvetkov, Вы писали:
C>т.е. можно периписать хаскельный код так чтобы он был не stable, но такой же оптимальный как и сишный? C>и при этом не потерял простоты описания?
Хаскельный код сортирует список, а не массив, и всегда просматривает этот список в одном направлении.
Конкретно этот алгоритм легко выраждается в O(n^2), если список изначально отсортирован.
Re[3]: Quicksort: краткость записи vs производительность код
Здравствуйте, Pzz, Вы писали:
Pzz>Здравствуйте, pierre, Вы писали:
P>>Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort, а классический inplace qsort на C -- не stable. Это http://en.wikipedia.org/wiki/Quicksort#Simple_version и http://en.wikipedia.org/wiki/Quicksort#Complex_version соответственно, они делают разные вещи.
Pzz>Казалось бы, из любой нестабильной сортировки легко получить стабильную, если модифицировать функцию сравнения таким образом, чтобы при равенстве аргументов она учитывала их взаимное расположение и считала, что тот, который идет раньше — он меньше (если мы сортируем по возрастанию).
А наоборот?
Мозгом-то много что много из чего можно получить, а оптимизация должна сохранять смысл кода, что при переходе stable->unstable очевидно невозможно
Хотя алгоритм, такое делающий, был бы очень интересен.
Re: Quicksort: краткость записи vs производительность кода
Здравствуйте, Aleх, Вы писали:
A>Давно хотел задать этот вопрос. Меня это интересует совсем не с той целью, чтобы убедиться в том, что кратко записанный алгоритм не может быть перобразован в оптимальный код, а наоборот, мне хотелось вы увидеть, что действительно может быть преобразован и понять, как.
На одном из проектов я сейчас наблюдаю 3-кратное ускорение при переписывании кода с C++ на C# и переходе к immutable структурам данных (к сожалению, не могу сейчас написать детали).
Re: Quicksort: краткость записи vs производительность кода
A>Давно хотел задать этот вопрос. Меня это интересует совсем не с той целью, чтобы убедиться в том, что кратко записанный алгоритм не может быть перобразован в оптимальный код, а наоборот, мне хотелось вы увидеть, что действительно может быть преобразован и понять, как.
A>1. Может ли? A>2. Если да, то как? Интересует последовательность преобразований, алгоритм работы оптимизирующего компилятора в данном конкретном случае (общие стространичные статьи по устройству оптимизатора, например, в хаскеле на данный момент не интересуют). A>Хотелось бы увидеть не эвристический алгоритм. A>3. Хотелось бы увидеть код на высокоуровневом языке программирования и листинг машинного или байт кода.
A>Разумеется требуется получить код, который выполняет быструю сортировку без использования дополнительной памяти больше чем с*lg(n).
Как уже сказали, алгоритмы разные и не получится.
Можно попробовать обратную задачу написать на императивном языке аналог Хаскельного кода и сравнить по читабельности и быстродействию.
Re[2]: Quicksort: краткость записи vs производительность код
Здравствуйте, FR, Вы писали: FR>Как уже сказали, алгоритмы разные и не получится. FR>Можно попробовать обратную задачу написать на императивном языке аналог Хаскельного кода и сравнить по читабельности и быстродействию.
Окей, это я понял. В таком случае, два варианта развития событий. Либо написать на высокоуровневом функциональном ЯП нестабильную сортировку(тогда алгоритм будет одинаков) и решить, можно ли её преобразовать в сортировку на Си.
Насколько я понимаю, если операция list comprehension не будет сохранять порядок, то так и получится.
def quicksort(l)
{
| [] => [];
| x :: xs => quicksort( $[ y | y in xs, y <= x ] ) + [x] + quicksort( $[y | y in xs, y > x] );
}
Здравствуйте, Aleх, Вы писали:
A>Окей, это я понял. В таком случае, два варианта развития событий. Либо написать на высокоуровневом функциональном ЯП нестабильную сортировку(тогда алгоритм будет одинаков) и решить, можно ли её преобразовать в сортировку на Си. A>Насколько я понимаю, если операция list comprehension не будет сохранять порядок, то так и получится.
Не стабильность является препятствием оптимизации иммутабельной сортировки в инплейс сортировку, а именно иммутабельность. Если двигать элементы — то иммутабельности больше не будет. Теоретически такая оптимизация может быть произведена в случае если сортируемые данные никто не "видит". Но это малоинтересно, выбирать метод сортировки в зависимости от того, видит кто-то данные или нет. Анализ видимости обойдется дороже.
С другой стороны, сборщик мусора из дотнета умеет двигать объекты прозрачным для программы образом. Т.е. программа не узнает о том что они передвинулись. Но и сортировку таким образом не сделать, т.к. ее результаты тоже будут невидны.
Re[3]: Quicksort: краткость записи vs производительность код
Здравствуйте, Aleх, Вы писали:
A>Здравствуйте, pierre, Вы писали: P>>Нет, получить такой код нельзя никакой оптимизацией, т.к. код на хаскеле реализует stable sort, а классический inplace qsort на C -- не stable. Это http://en.wikipedia.org/wiki/Quicksort#Simple_version и http://en.wikipedia.org/wiki/Quicksort#Complex_version соответственно, они делают разные вещи.
A>Здравствуйте, FR, Вы писали: FR>>Как уже сказали, алгоритмы разные и не получится. FR>>Можно попробовать обратную задачу написать на императивном языке аналог Хаскельного кода и сравнить по читабельности и быстродействию.
A>Окей, это я понял. В таком случае, два варианта развития событий. Либо написать на высокоуровневом функциональном ЯП нестабильную сортировку(тогда алгоритм будет одинаков) и решить, можно ли её преобразовать в сортировку на Си. A>Насколько я понимаю, если операция list comprehension не будет сохранять порядок, то так и получится. A>
A>def quicksort(l)
A>{
A> | [] => [];
A> | x :: xs => quicksort( $[ y | y in xs, y <= x ] ) + [x] + quicksort( $[y | y in xs, y > x] );
A>}
A>
A>inplace qsort легко превратить в stable. достаточно хвост разворачивать обратно — это даст итогую сложность 2 * n log n
A>Тогда алгоритмы тоже будут одинаковы.
Более простая задача:
Как следующий код преобразовать в код на С++, данный ниже:
def partition(l)
{
| [] => [];
| x :: xs => $[ y | y in xs, y <= x ] + [x] + $[y | y in xs, y > x]; //где $[...] не сохраняет последовательность
}
void partition(int a[], int p, int r)
{
int x = a[p];
int j = p;
for (int i = p + 1; i < r; i++)
{
if (x > a[i])
{
j = j + 1;
swap(a[j], a[i]);
}
}
a[p] = a[j];
a[j] = x;
}
Re[4]: Quicksort: краткость записи vs производительность код
Здравствуйте, samius, Вы писали:
S>Здравствуйте, Aleх, Вы писали:
A>>Окей, это я понял. В таком случае, два варианта развития событий. Либо написать на высокоуровневом функциональном ЯП нестабильную сортировку(тогда алгоритм будет одинаков) и решить, можно ли её преобразовать в сортировку на Си. A>>Насколько я понимаю, если операция list comprehension не будет сохранять порядок, то так и получится.
S>Не стабильность является препятствием оптимизации иммутабельной сортировки в инплейс сортировку, а именно иммутабельность. Если двигать элементы — то иммутабельности больше не будет. Теоретически такая оптимизация может быть произведена в случае если сортируемые данные никто не "видит". Но это малоинтересно, выбирать метод сортировки в зависимости от того, видит кто-то данные или нет. Анализ видимости обойдется дороже.
Какие препятствия для сохранения иммутабельности на уровне языка?
Предполагается что оптимизация в инплейс сортировку будет выполнена если неотсортированные данные уже больше "не нужны" (ничего на них не ссылается). Для самой программы это должно выглядеть как если бы отсортированные данные расположились в том же месте, где и исходные (то есть перемешать данные — всё равно что удалить массив данных и создать его заново в том же месте). Кстати, я вообще не пойму какие могут быть с этим проблемы, если нет адресной арифметики в языке. Должно быть пофигу где физически вообще расположены данные и что там с ними происходит. То есть принципиально для программы на языке должо быть всё равно созданы отсортированные данные в новом месте или в старом.
В том случае, если на данные есть ссылки, то скопировать их и так же отсортировать "на месте".
S>С другой стороны, сборщик мусора из дотнета умеет двигать объекты прозрачным для программы образом. Т.е. программа не узнает о том что они передвинулись. Но и сортировку таким образом не сделать, т.к. ее результаты тоже будут невидны.
Re: Quicksort: краткость записи vs производительность кода
A>Давно хотел задать этот вопрос. Меня это интересует совсем не с той целью, чтобы убедиться в том, что кратко записанный алгоритм не может быть перобразован в оптимальный код, а наоборот, мне хотелось вы увидеть, что действительно может быть преобразован и понять, как.
вопрос очень правильный, и, как я понимаю, вопросами эффективной компиляции такого кода много занимаются.
Но можно посмотреть и с другой стороны: на своем любимом декларативно-функциональном языке ты можешь написать программу, которая не будет сортировать сама, а сгенерирует оптимальный императивный код.
Re[2]: Quicksort: краткость записи vs производительность код
Здравствуйте, dilmah, Вы писали:
A>>Давно хотел задать этот вопрос. Меня это интересует совсем не с той целью, чтобы убедиться в том, что кратко записанный алгоритм не может быть перобразован в оптимальный код, а наоборот, мне хотелось вы увидеть, что действительно может быть преобразован и понять, как.
D>вопрос очень правильный, и, как я понимаю, вопросами эффективной компиляции такого кода много занимаются.
D>Но можно посмотреть и с другой стороны: на своем любимом декларативно-функциональном языке ты можешь написать программу, которая не будет сортировать сама, а сгенерирует оптимальный императивный код.
Можно раскрыть мысль? Чтобы сгенерировать оптимальный код нужно ведь очень много вещей учитывать, то есть внешней программой это делать будет не удобно.
К тому же я как раз и создал тему, потому что мне интересно, существует ли такой неэвристический алгоритм (даже не алгоритм а метод), который мог бы сгенерировать оптимальную программу сортировки.
Re[5]: Quicksort: краткость записи vs производительность код
Здравствуйте, Aleх, Вы писали:
A>Здравствуйте, samius, Вы писали:
S>>Не стабильность является препятствием оптимизации иммутабельной сортировки в инплейс сортировку, а именно иммутабельность. Если двигать элементы — то иммутабельности больше не будет. Теоретически такая оптимизация может быть произведена в случае если сортируемые данные никто не "видит". Но это малоинтересно, выбирать метод сортировки в зависимости от того, видит кто-то данные или нет. Анализ видимости обойдется дороже.
A>Какие препятствия для сохранения иммутабельности на уровне языка? A>Предполагается что оптимизация в инплейс сортировку будет выполнена если неотсортированные данные уже больше "не нужны" (ничего на них не ссылается).
А если нужны, то что сортировать не надо? В иммутабельных языках довольно сильный реюз данных. Ждать пока данные освободятся для сортировки нет смысла.
A>Для самой программы это должно выглядеть как если бы отсортированные данные расположились в том же месте, где и исходные (то есть перемешать данные — всё равно что удалить массив данных и создать его заново в том же месте).
Что за массив данных? Массива нет в общем случае функциональных языков. В гибридных есть — так там и средства для их inplace сортировки имеются как-правило.
A>Кстати, я вообще не пойму какие могут быть с этим проблемы, если нет адресной арифметики в языке. Должно быть пофигу где физически вообще расположены данные и что там с ними происходит. То есть принципиально для программы на языке должо быть всё равно созданы отсортированные данные в новом месте или в старом.
Представь что ты сортируешь деревья по их размеру. После сортировки новые деревья должны вырасти?
A>В том случае, если на данные есть ссылки, то скопировать их и так же отсортировать "на месте".
А не будет дороже, чем отсортировать иммутабельной сортировкой?
) программы.
