Текст ниже взят из лекций "Кафедра Кибернетики МИФИ: Функциональное программирование, группы К7-222 и К7-223. В настоящем варианте читаются с 2001 года.".
Пример 1. Быстрая сортировка Хоара на C.
void quickSort (int a[], int l, int r)
{
int i = l;
int j = r;
int x = a[(l + r) / 2];
do
{
while (a[i] < x) i++;
while (x < a[j]) j--;
if (i <= j)
{
int temp = a[i];
a[i++] = a[j];
a[j--] = temp;
}
}
while (i <= j);
if (l < j) quickSort (a, l, j);
if (i < r) quickSort (a, i, r);
}
Пример 2. Быстрая сортировка Хоара на абстрактном функциональном языке.
quickSort ([]) = []
quickSort ([h : t]) = quickSort (n | n ∈ t, n <= h) + [h] + quickSort (n | n ∈ t, n > h)
Пример 2 следует читать так:
1. Если список пуст, то результатом также будет пустой список.
2. Иначе (если список не пуст) выделяется голова (первый элемент) и хвост (список из оставшихся элементов, который может быть пустым). В этом случае результатом будет являться конкатенация (сращивание) отсортированного списка из всех элементов хвоста, которые меньше либо равны голове, списка из самой головы и списка из всех элементов хвоста, которые больше головы.
Пример 3. Быстрая сортировка Хоара на языке Haskell.
quickSort [] = []
quickSort (h : t) = quickSort [y | y <- t, y < h] ++ [h] ++ quickSort [y | y <- t, y >= h]
Как видно, даже на таком простом примере функциональный стиль программирования выигрывает и по количеству написанного кода и по его элегантности.
Вы согласны с тем, что пример на Haskell действительно лучше?
Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет, пишущему на Basic или Pascal или С++. И к этому коду нет пояснений в лекции, он самодостаточен. А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
Так ... так ли на самом деле хорош этот элегантный, как написано в лекции, и короткий код на Haskell?
Сделана человеческая разметка. Не забывайте делать предпросмотр!!! — Кодт
Здравствуйте, md03t4, Вы писали:
M>Обращу внимание на то, что код на С понятен почти любому программисту
Мне не понятен. Не потрудитесь в двух словах рассказать, что там происходит? Ну, кроме того, что сортировка.
M>Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет, пишущему на Basic или Pascal или С++.
Неверно.
M>И к этому коду нет пояснений в лекции, он самодостаточен. А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
Бездоказательно. Более того, он изобилует деталями реализации, которые затрудняют понимание алгоритма. На хаскелле код — именно то, что он делает. Пояснений не читал.
M>Так ... так ли на самом деле хорош этот элегантный, как написано в лекции, и короткий код на Haskell?
Да, хорош. Хоть и не самый эффективный вариант. Эффективная реализация этого алгоритма будет менее лаконичной, конечно.
Но квиксорт — это все мелочи. Вот есть два языка — Boo и Haxe. Оба — высокоуровневые языки со статической типизацией и
выводом типов. Компилятор одного реализован на C#, компилятор второго — частично на OCaml. Можете попробовать сравнить,
например, как там и там реализована система типов, и в коде на каком языке быстрее разберетесь.
Здравствуйте, md03t4, Вы писали:
M>Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет
Это неверно. Не путай знание синтаксиса с понятностью. Пояснение к примеру на хаскель дается потому что читатель не знает, что означают эти значки. Если б читатель не знал и Cи, ему б потребовалось объяснение и для первого примера. Переведи оба примера на чисто русский язык, и сам всё увидишь.
Re: Простая и короткая программа на Haskell
От:
Аноним
Дата:
14.05.09 08:44
Оценка:
Здравствуйте, md03t4, Вы писали:
M>Вы согласны с тем, что пример на Haskell действительно лучше?
Да.
M>Обращу внимание на то, что код на С понятен почти любому программисту,
Не понятен совершенно. Много букав. Алгоритм в голове прокручивать приходится.
M> А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
Не требуется — классическая запись для множеств, любому математику понятная.
M>void quickSort (int a[], int l, int r)
M>{
M> int i = l;
M> int j = r;
M> int x = a[(l + r) / 2];
M> do
M> {
M> while (a[i] < x) i++;
M> while (x < a[j]) j--;
M> if (i <= j)
M> {
M> int temp = a[i];
M> a[i++] = a[j];
M> a[j--] = temp;
M> }
M> }
M> while (i <= j);
M> if (l < j) quickSort (a, l, j);
M> if (i < r) quickSort (a, i, r);
M>}
M>
M>Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет, пишущему на Basic или Pascal или С++. И к этому коду нет пояснений в лекции, он самодостаточен.
Это все потому что Вы умеете программировать на императивном языке, умеете работать с массивами и наработан опыт:
Взгляните на код — разгадываем ребус:
//от работы с элементами списка перешли к работе
// с индексами (хотя в описании алгоритма про индексы ни слова)int i = l; int j = r;
// да это же обмен значениями! ну и конечно очевидно,
// что вместе с обменом значениями передвигаются и указатели int temp = a[i]; a[i++] = a[j]; a[j--] = temp; на элементы (индексы)
// легко! поиск элемента (<x)while (a[i] < x) i++;
// легко! поиск элемента (>x) while (x < a[j]) j--;
// а точно! мы же просматриваем массив сразу с двух сторон,
// а это условие завершенияdo ... while (i <= j);
Это все у Вас происходит в голове.
M>Пример 3. Быстрая сортировка Хоара на языке Haskell. M>
M>quickSort [] = []
M>quickSort (h : t) = quickSort [y | y <- t, y < h] ++ [h] ++ quickSort [y | y <- t, y >= h]
M>
M>Вы согласны с тем, что пример на Haskell действительно лучше?
Конечно, да!
Вы пытались разобраться в этом коде? Я попробую рассказать, как прочитать этот код, чтобы было понятно.
Изменим названия переменных немного, т.к. обычно в haskell краткие названия списков заканчиваются на s, так привычнее.
quickSort (x:xs) = quickSort [y | y <- xs, y < x] ++ [x] ++ quickSort [y | y <- xs, y >= x]
Рассмотрим определение функции "quickSort ps = ...", здесь описывается функция quickSort с одним параметром — списком. Чтобы получить голову списка мы можем использовать функцию head (например, head ps), а для получения хвоста списка можем использовать функцию tail (например, tail ps). А можем просто указать haskell, что мы хотим рассматривать данный параметр в виде пары (голова:хвост). Поэтому выражение "quickSort (x:xs) = ..." обозначает функцию quickSort с одним параметром (списком), голову которого назовем x, а хвост xs. Теперь нам не нужно писать в тексте head и tail для получения головы и хвоста, эти переменные у нас уже есть.
Выражение "... ++ ... ++ ..." обозначает соединение списков. Например [1,2] ++ [3,4] = [1,2,3,4]. Однако, мы не можем написать [1,2] ++ 3, т.к. "3" не является списком. Зато мы можем легко превратить число 3 в список содержащий число 3, заключив его в квадратные скобки — [3]. По этой причине у нас присутствует выражение "... ++ [x] ++ ...".
Еще есть у нас выражения вот такие: [y | y <- xs, y < x]. Общий вид их такой:
[ что_хотим_получить(элем1,элем2,..) | элем1 <- список1, элем2 <- список2, ..., условие1, условие2, ...]
Работает это так:
foreach(элем1:список1)
foreach(элем2:список2)
..
if (условие1 и условие2 и ...)
посчитать что_хотим_получить и включить это значение в результат
end
end
end
Т.е. для [y | y <- xs, y < x] можно просто сказать так: для всех y из xs, таких что y < x, вернуть y (не забываем, что х — голова параметра, xs — хвост). Для [y | y <- xs, y >= x] аналогично. Вообще-то эти выражения можно было бы записать и на основе функции filter: filter (<x) xs и filter (>=x) xs соответственно.
Все, что я описал выше никакого отношения к задаче фактически не имеет. Это принципы программирования на haskell. Например, pattern-matching, когда мы представляли параметр в виде (x:xs). И list comprehension [y | y <- xs, y < x]. Эти вещи изучаются один раз и через некоторое время при чтении на этом даже не заостряется внимание.
M>А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
Толмач должен выглядеть так: Мы выделили один элемент из списка (x), а осташиеся элементы (xs) разделили на две группы (<x) и (>=x), каждую группу отсортировали и потом все это дело соединили.
Я бы вообще пример написал так:
Б> Т.е. для [y | y <- xs, y < x] можно просто сказать так: для всех y из xs, таких что y < x, вернуть y (не забываем, что х — голова параметра, xs — хвост).
Можно то представить в математической нотации:
{y | y ∈ xs, y < x}
То есть множество y, где y ∈ xs и y < x В общем, list comprehensions, в принципе, это и описывают
Здравствуйте, md03t4, Вы писали:
M>Вы согласны с тем, что пример на Haskell действительно лучше?
M>Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет, пишущему на Basic или Pascal или С++. И к этому коду нет пояснений в лекции, он самодостаточен. А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
M>Так ... так ли на самом деле хорош этот элегантный, как написано в лекции, и короткий код на Haskell?
Э!!! Ты привёл два разных алгоритма — разрушающий (на Си) и неразрушающий (на Хаскелле), и пытаешься их сравнивать на понятность.
Если для тебя этот факт ускользнул, то значит, что код на Си оказался кое в чём непонятен
Код на Си требует комментариев, и довольно тщательных.
В частности, там заинлайнен алгоритм разбиения массива (std::partition).
Хорошо известно из горького опыта, что написание таких очевидных вещей сопровождается детскими граблями — плюс-минус единичками на границах диапазонов, например.
void quickSort (int a[], int l, int r)
{
// Вопрос: мы работаем с полуоткрытым интервалом или с закрытым? [l..r) или [l..r] ?
// Ладно, обозначим правую границу загадочным }int i = l;
int j = r;
int x = a[(l + r) / 2];
// почему в роли медианы взяли значение из середины массива?
// при каких условиях здесь произойдёт вылет за границы?
// инвариант цикла: a[l..i} < x < [j..r}
// на каждой итерации диапазон [i..j} сужается
// постусловие - a[i..j} == x (причём очевидно, что этот интервал не пуст, ведь ему принадлежит медиана)do
{
while (a[i] < x) i++; // кажется, всё-таки работаем с закрытыми интерваламиwhile (x < a[j]) j--;
// замечательный сплав swap() и автоинкрементов, очень "интуитивно"if (i <= j)
{
int temp = a[i];
a[i++] = a[j];
a[j--] = temp;
}
}
while (i <= j); // Зачем проверку диапазона делаем только после первой итерации? Она что, раньше нам не нужна?if (l < j) quickSort (a, l, j);
if (i < r) quickSort (a, i, r);
}
Чем обусловлен выбор закрытых интервалов, хотя бОльшая часть стандартных алгоритмов работает с полуоткрытыми?
Ну что, самодостаточен код, говоришь? Передай преподу из МИФИ, что он или халтурщик, или провокатор (в злом или добром смысле этого слова).
И ещё раз возвращаясь к алгоритмам на Си и Хаскелле.
Попробуй объяснить, почему на Си медиану дёрнули из середины массива, а на Хаскелле — из головы?
На что это влияет?
Если бы мы писали не на ленивом Хаскелле, а на энергичном ML, например — что изменилось бы?
Этюд для тестеров: сгенерировать такой массив, который обрушил бы сишный квиксорт в том виде, какой он есть у тебя.
Какая природа этого обрушения?
То же самое касается и Хаскелла.
Здравствуйте, eao197, Вы писали:
E>Оссмысленное название переменной y все еще подчеркивает мощность программиста на Haskell.
Это ирония?
1. Сравни области действия переменной i в С и переменной y в Haskell.
2. Сравнив, можно сделать вывод, что в некоторых случаях (а там именно такой)
удобнее написать f(x) = x*x
чем f(value) = value * value
Обзывать переменные цикла именами i и j имеет очень и очень давние корни. Которые можно наблюдать в высшей математике. Наверное, даже запись вида A0,A1,...,Ai,...,An уже демонстрирует убогость математического аппарата.
Б>1. Сравни области действия переменной i в С и переменной y в Haskell.
Это ирония?
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Это — классический пример, его где хочешь можно найти.
А сравнивать деструктивный алгоритм и недеструктивный, кстати, неумно.
Да и вариант на Хаскелле, хоть и проще для понимания, по скорости явно будет сливать. На каждом шагу два раза проходить один и тот же список и два раза делать ++. Мрак как "красиво".
Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C.
Здравствуйте, Rtveliashvili Denys, Вы писали: RD>Это — классический пример, его где хочешь можно найти.
Ага.
RD>А сравнивать деструктивный алгоритм и недеструктивный, кстати, неумно.
+1
RD>Да и вариант на Хаскелле, хоть и проще для понимания, по скорости явно будет сливать. На каждом шагу два раза проходить один и тот же список и два раза делать ++. Мрак как "красиво".
Таки не забывай что это учебный курс.
Стало быть приводятся примеры именно алгоритмов а не их оптимозированных реализаций.
Так что оба варианта вполне выполняют в данном контексте свои функции.
RD>Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C.
Опять же посмотри "хороший" промышленный вариант быстрой сортировки на С/С++ в любой реализации STL-я. Сложность будет изрядно выше приведённой здесь реализации.
Здравствуйте, md03t4, Вы писали:
M>Текст ниже взят из лекций "Кафедра Кибернетики МИФИ: Функциональное программирование, группы К7-222 и К7-223. В настоящем варианте читаются с 2001 года.".
Текст ниже на самом деле практически без изменений выдран из FAQ конференции comp.lang.functional. Лекция МИФИ не является первоисточником.
M>Вы согласны с тем, что пример на Haskell действительно лучше?
Конечно.
M>Обращу внимание на то, что код на С понятен почти любому программисту, знакомому с Haskell или нет, пишущему на Basic или Pascal или С++. И к этому коду нет пояснений в лекции, он самодостаточен.
Человек, который не знает алгоритма quicksort, данный код будет расшифровывать достаточно долго, потому что в варианте на С записан не просто quicksort, а оптимизированный quicksort в варианте Хоара.
Вариант на Хаскеле как слышытся так и пишется — и он читается прямолинейно.
M>А вот к абстрактной записи и к ее почти копии на Haskell требуется толмач. И он приведен.
Обратите внимание, что смысл фразы "против этого нечего возразить; что правда, то правда" пояснять не надо, он самодостаточен, а для ее почти копии "dagegen ist nichts zu machen" требуется толмач.
Язык программирования надо все-таки изучать, чтобы понимать смысл программ, написанных на нем.
M>Так ... так ли на самом деле хорош этот элегантный, как написано в лекции, и короткий код на Haskell?
RD>>Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C.
T>Докажиземлюешь.
Мне незачем кому-либо что-либо доказывать. Нет, видите ли, финансовой заинтересованности.
Если считаете, что соптимизировнный на Haskell вариант будет короче приведенного варианта на C — welcome демострировать. Посмотрим, насколько он хороший и оптимальный. Заодно будет реклама Haskell'ю.
Здравствуйте, Rtveliashvili Denys, Вы писали:
RD>>>Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C.
T>>Докажиземлюешь.
RD>Мне незачем кому-либо что-либо доказывать. Нет, видите ли, финансовой заинтересованности.
RD>Если считаете, что соптимизировнный на Haskell вариант будет короче приведенного варианта на C — welcome демострировать. Посмотрим, насколько он хороший и оптимальный. Заодно будет реклама Haskell'ю.
Этот вариант, в целом, не надо оптимизировать. Из-за ленивых вычислений он гораздо оптималенее, чем кажется на первый вгляд (выполняется он _совсем_ не так, как кажется на первый взгляд, например, операция ++ дается почти бесплатно, а вовсе не стоит O(N)) и вычисляется с разумной производительностью.
Возьмем такой вариант использования. У тебя массив из миллиона чисел. Тебе надо его отсортировать, и взять первые два десятка элементов. На данном примере с таким кодом на С ты будешь очень долго догонять по скорости Хаскельный вариант.
Здравствуйте, Mr.Cat, Вы писали: G>>операция ++ дается почти бесплатно MC>А можно с этого места поподробнее?
Ааа, я кажется понял. При чтении элементов списка сперва будет вычитываться результат выражения перед ++, и когда он закончится — начнется выполнение выражения после ++? — как-то так?
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, Gaperton, Вы писали: G>>операция ++ дается почти бесплатно MC>А можно с этого места поподробнее?
Она "ленивая". Конкатенация списков не приводит к немедленной пробежке по списку, она откладывается на момент чтения этого списка. Ленивость превращает многие алгоритмы на списках, которые O(N^2) в строгом виде, в O(N). За подробностями лучше, например, к thesz. Мне думать очень лень о релятивистских эффектах ленивости, строго говоря, я в этом не специалист.
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, Mr.Cat, Вы писали: G>>>операция ++ дается почти бесплатно MC>>А можно с этого места поподробнее?
MC>Ааа, я кажется понял. При чтении элементов списка сперва будет вычитываться результат выражения перед ++, и когда он закончится — начнется выполнение выражения после ++? — как-то так?
Здравствуйте, Mr.Cat, Вы писали:
MC>Здравствуйте, Mr.Cat, Вы писали: G>>>операция ++ дается почти бесплатно MC>>А можно с этого места поподробнее? MC>Ааа, я кажется понял. При чтении элементов списка сперва будет вычитываться результат выражения перед ++, и когда он закончится — начнется выполнение выражения после ++? — как-то так?
Что-то мне подсказывает, что это не так.
Забудем на время о rewrite rules и оптимизациях в компиляторе, рассмотрим только эффекты ленивого порядка вычислений на временную сложность.
Интуиция подсказывает, что сэкономить здесь можно только в том случае, если львиную долю вычислений делать не надо — например, генерируем огромный список и берем из него только первых 10 элементов. А сортировка требует вычисления результата конкатенации целиком.
Возьмем такой вариант использования. У тебя массив из миллиона чисел. Тебе надо его отсортировать, и взять первые два десятка элементов. На данном примере с таким кодом на С ты будешь очень долго догонять по скорости Хаскельный вариант.
По-моему выделенные слова противоположны друг другу, нет?
К>Возьмем такой вариант использования. У тебя массив из миллиона чисел. Тебе надо его отсортировать, и взять первые два десятка элементов. На данном примере с таким кодом на С ты будешь очень долго догонять по скорости Хаскельный вариант.
К>По-моему выделенные слова противоположны друг другу, нет?
Я спорил с утверждением "операция ++ дается почти бесплатно". Это не так. Выполнение фукнции (++) "размазано" во времени, но при условии потребления всего списка она выполняется полностью.
Здравствуйте, Gaperton, Вы писали:
G>Он проверяет другое — сложность операции конкатенации. Она все равно не получается O(N).
Я думаю, что получается. Это довольно просто проверить, надо всего-то поэкспериментировать с различными длинами списков и построить график, но мне лень .
Здравствуйте, palm mute, Вы писали:
К>>По-моему выделенные слова противоположны друг другу, нет?
PM>Я спорил с утверждением "операция ++ дается почти бесплатно". Это не так. Выполнение фукнции (++) "размазано" во времени, но при условии потребления всего списка она выполняется полностью.
Это не следует из проведенного эксперимента.
1) Надо исключить влияние времени генерации длинного списка.
2) Конкатенировать для чистоты лучше не пустой список, а тот же список многократно. Исключив фактор свопа — все должно гарантировано поместится в памяти. Для гарантии этого, каждый эксперимент должен повторяться многократно.
3) И потом посмотреть, будет ли у last выраженная квадратичная асимптотика, или ей можно пренебречь. Точек должно быть не меньше пяти.
4) И еще посмотреть, как будет себя вести first.
5) И делать все это не в консоли, а в ghc с включенными оптимизациями.
G>1) Надо исключить влияние времени генерации длинного списка.
Эта мысль мне сразу пришла в голову, вот результат:
Prelude> let appendEmpty xs = xs ++ []
Prelude> let xs = [1 .. 10000000]
Prelude> :s +s
Prelude> last xs
10000000
(1.95 secs, 402124972 bytes) -- вот здесь мы исключили влияние времени генерации
Prelude> last xs -- повторный замер показывает, что список уже сгенерирован
10000000
(0.08 secs, 0 bytes)
Prelude> last $ appendEmpty xs
10000000
(0.18 secs, 281025096 bytes)
Prelude> last $ appendEmpty $ appendEmpty xs
10000000
(0.32 secs, 561513668 bytes)
Prelude> last $ appendEmpty $ appendEmpty $ appendEmpty xs
10000000
(0.45 secs, 842527844 bytes)
Prelude> last $ appendEmpty $ appendEmpty $ appendEmpty $ appendEmpty xs
10000000
(0.60 secs, 1122493452 bytes)
Prelude>
G>2) Конкатенировать для чистоты лучше не пустой список, а тот же список многократно. Исключив фактор свопа — все должно гарантировано поместится в памяти. Для гарантии этого, каждый эксперимент должен повторяться многократно.
Для свопа тут маловато данных. Конкатенировать непустой список необязательно, достаточно показать линейную зависимость от длины первого слагаемого — это напрямую следует из реализации оператора (++). G>3) И потом посмотреть, будет ли у last выраженная квадратичная асимптотика, или ей можно пренебречь. Точек должно быть не меньше пяти. G>4) И еще посмотреть, как будет себя вести first.
Это все хорошие, годные предложения, но делать мне это точно лень.
G>5) И делать все это не в консоли, а в ghc с включенными оптимизациями.
В консоли ленивые вычисления никуда не деваются. А вот rewrite rules, deforestation и прочая магия не работают. Здесь оптимизации ни к чему, для чистоты эксперимента надо изолировать эффекты ленивости.
RD>>>Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C. T>>Докажиземлюешь. RD>Мне незачем кому-либо что-либо доказывать. Нет, видите ли, финансовой заинтересованности. RD>Если считаете, что соптимизировнный на Haskell вариант будет короче приведенного варианта на C — welcome демострировать. Посмотрим, насколько он хороший и оптимальный. Заодно будет реклама Haskell'ю.
Твой тезис, тебе и доказывать.
Или это не твой тезис?
Yours truly, Serguey Zefirov (thesz NA mail TOCHKA ru)
Здравствуйте, palm mute, Вы писали:
G>>Он проверяет другое — сложность операции конкатенации. Она все равно не получается O(N).
PM>Я думаю, что получается. Это довольно просто проверить, надо всего-то поэкспериментировать с различными длинами списков и построить график, но мне лень .
Ладно, тогда разберемся "аналитически". Ну, короче, как в принципе устроен ++? Ну, например, так. Я на Эрланге напишу, мне так проще, и в принципе один хрен.
%% Вот это - достаточно понятно.
concat( [], X ) -> X;
%% Как, собственно, и вот это
concat( [ H | T ], X ) ->
[ H | concat( T, X ) ].
Как у нас будет выполняться concat( A, B) в ленивом языке? Для простоты, пусть у нас ленивые только конструкторы списка, остальное неважно.
C = concat( A, B ) имеет сложность O(1)
Пробежка по результату приведет к дополнительному ленивому вызову concat, который будет возвращать копию элемента списка H для каждого элемента А, и будет стоить столько же для элементов B. То есть, пробежка по С будет чуть дороже, чем пробежка по А или Б. Однако, налицо неплохой потенциал для оптимизации в ghc — компилятор может избежать задействования хипа, если выведет last use для элементов C. Это уже кое-что, не так ли?
D = concat( concat( A, B ), B1 ) — само по себе тоже O(1), разумеется, это не интересно.
А пробежка по D... Два накладных вызова на len( A ), один — на len( A + B ) — len( A ), и ноль на len( B1 ). Та же картина по last use для ghc.
Итак, при наращивании глубины конкатенации по данной цепочке, имеем очень легкую, почти незаметную в сравнении со строгим случаем квадратичность (за счет отсутствия переливаний из памяти в память), которая будет почти незаметна на фоне обработки.
Смотрим второй вариант:
D = concat( B1, concat( A, B ) )
Имеем один накладной вызов при любой вложенности подобных операций конкатенации. То есть, квадратичности нет. Прикольно, не так ли?
Будем проверять теорию экспериментом?
Да, вариант с хвостовой рекурсией я не рассматривал, ибо интуиция мне подсказывает ее ненужность в "ленивом" случае.
Здравствуйте, palm mute, Вы писали:
PM>Здравствуйте, Gaperton, Вы писали:
G>>1) Надо исключить влияние времени генерации длинного списка. PM>Эта мысль мне сразу пришла в голову, вот результат:
Да, это напоминает линейную зависимость.
G>>5) И делать все это не в консоли, а в ghc с включенными оптимизациями. PM>В консоли ленивые вычисления никуда не деваются. А вот rewrite rules, deforestation и прочая магия не работают. Здесь оптимизации ни к чему, для чистоты эксперимента надо изолировать эффекты ленивости.
Ну, в реальности я думаю эта зависимость будет не так страшна и заметна. И должна сильно сгладится "магией" ghc. См. мой соседний пост тебе с "теорией".
И кстати, в случае, если мы берем первые несколько элементов, квадратичность точно не будет заметна из-за размазанности операции concat по всему списку. И будет строгий выигрышь.
RD>>>>Предполагаю, что "хороший" вариант в плане скорости написанный на Хаскелле имеет шансы быть страшнее и непонятнее чем на C. T>>>Докажиземлюешь. RD>>Мне незачем кому-либо что-либо доказывать. Нет, видите ли, финансовой заинтересованности. RD>>Если считаете, что соптимизировнный на Haskell вариант будет короче приведенного варианта на C — welcome демострировать. Посмотрим, насколько он хороший и оптимальный. Заодно будет реклама Haskell'ю.
T>Твой тезис, тебе и доказывать. T>Или это не твой тезис?
Мне достаточно наслаждаться жизнью. Доказывать кому-то что-то нужно Вам. А мне и так хорошо.
P.S. Это не тезис и я в отличии от некоторых никому и ничего не доказываю. Не напрягайтесь.
RD>Мне достаточно наслаждаться жизнью. Доказывать кому-то что-то нужно Вам. А мне и так хорошо. RD>P.S. Это не тезис и я в отличии от некоторых никому и ничего не доказываю. Не напрягайтесь.
Ну вот, например, более эффективная реализация. Нельзя сказать, что бы она была особо сложной для понимания.
qsort3 :: Ord a => [a] -> [a]
qsort3 x = qsort3' x []
qsort3' (x:xs) y = part xs [] [x] []
where
part [] l e g = qsort3' l (e ++ (qsort3' g y))
part (z:zs) l e g
| z > x = part zs l e (z:g)
| z < x = part zs (z:l) e g
| otherwise = part zs l (z:e) g
G>Да, вариант с хвостовой рекурсией я не рассматривал, ибо интуиция мне подсказывает ее ненужность в "ленивом" случае.
Хотя почему бы и нет. Конкатенация с хвостовой рекурсией, которая должна быть более оптимальна для строгих языков:
concat( A, B ) -> reverse_concat( reverse_concat( A, [] ), B ).
reverse_concat( [], B ) -> B;
reverse_concat( [ H | T ], B ) -> reverse_concat( T, [ H | B ] ).
Хм. Что тут будет в ленивом случае? По ходу дела, вообще ничего хорошего. Здесь нельзя получить первый элемент списка, не вычислив все. Не подвела меня интуиция .
Здравствуйте, Gaperton, Вы писали:
G>А пробежка по D... Два накладных вызова на len( A ), один — на len( A + B ) — len( A ), и ноль на len( B1 ). Та же картина по last use для ghc.
Здесь намудрил, это можно сказать проще. При пробежке по D будет 2 накладных вызова для элементов А, 1 элементов B, и ноль для элементов B1. Принцип понятен. Вызовы будут, будет также, вероятно, определен last use, и цепочка из 2-х вызовов для элементов A должна оказаться дешевле, чем сумма накладных расходов для чтения двух элементов B. Что и приведет к менее "квадратичной" асимптотике. Разумеется, если смотреть не в hugs а в ghc.
dmz>Ну вот, например, более эффективная реализация. Нельзя сказать, что бы она была особо сложной для понимания.
dmz>
dmz>qsort3 :: Ord a => [a] -> [a]
dmz>qsort3 x = qsort3' x []
dmz>qsort3' (x:xs) y = part xs [] [x] []
dmz> where
dmz> part [] l e g = qsort3' l (e ++ (qsort3' g y))
dmz> part (z:zs) l e g
dmz> | z > x = part zs l e (z:g)
dmz> | z < x = part zs (z:l) e g
dmz> | otherwise = part zs l (z:e) g
dmz>
Боюсь, что я не настолько силен в Haskell чтобы сходу понять. В частности, не ясно что происходит с "y" в qsort3'. Название "part" тоже ясности не добавляет.
Мой ghc, кстати, тоже в непонятках. Говорит "Non-exhaustive patterns in function qsort3'".
Здравствуйте, Rtveliashvili Denys, Вы писали:
RD>Боюсь, что я не настолько силен в Haskell чтобы сходу понять. В частности, не ясно что происходит с "y" в qsort3'. Название "part" тоже ясности не добавляет. RD>Мой ghc, кстати, тоже в непонятках. Говорит "Non-exhaustive patterns in function qsort3'".
Я не dmz, но представлю, по-сути аналогичное, но рабочее решение.
Все как и раньше, но:
1. На каждой итерации список просматривается один раз (достигается за счет split)
2. Сортировка идет относительно значения из середины списка (mean), а не головы списка.
qsort [] = []
qsort xs = qsort lesser ++ equals ++ qsort greater
where (lesser,equals,greater) = split mean xs
mean = xs !! (length xs `div` 2)
-- делит список xs на три части, возвращает тупл (элементы меньшие mean, равные mean, большие mean)
split mean xs = split' [] [] [] xs
where split' ls es gs [] = (ls,es,gs)
split' ls es gs (p:ps) | p < mean = split' (p:ls) es gs ps
| p == mean = split' ls (p:es) gs ps
| p > mean = split' ls es (p:gs) ps
Здравствуйте, Rtveliashvili Denys, Вы писали:
RD>Мой ghc, кстати, тоже в непонятках. Говорит "Non-exhaustive patterns in function qsort3'".
Выпала пара клауз:
qsort3 :: Ord a => [a] -> [a]
qsort3 x = qsort3' x []
qsort3' [] y = y -- +++
qsort3' [x] y = x:y -- +++
qsort3' (x:xs) y = part xs [] [x] []
where
part [] l e g = qsort3' l (e ++ (qsort3' g y))
part (z:zs) l e g
| z > x = part zs l e (z:g)
| z < x = part zs (z:l) e g
| otherwise = part zs l (z:e) g
Z>qsort3 :: Ord a => [a] -> [a]
Z>qsort3 x = qsort3' x []
Z>qsort3' [] y = y -- +++
Z>qsort3' [x] y = x:y -- +++
Z>qsort3' (x:xs) y = part xs [] [x] []
Z> where
Z> part [] l e g = qsort3' l (e ++ (qsort3' g y))
Z> part (z:zs) l e g
Z> | z > x = part zs l e (z:g)
Z> | z < x = part zs (z:l) e g
Z> | otherwise = part zs l (z:e) g
Z>
Спасибо, теперь все заметно понятнее :)
Попробовал сделать bench и сравнить три имеющихся варианта. Результаты для 1 000 000 случайных чисел на ghc -O2:
Version: Vanilla
Time taken: 8.376607 seconds
Time taken: 2.953175 seconds
Time taken: 2.874494 seconds
Time taken: 2.930531 seconds
Time taken: 2.854348 seconds
-----------------
Version: Buravchik's
Time taken: 2.190905 seconds
Time taken: 2.301595 seconds
Time taken: 2.318359 seconds
Time taken: 2.234913 seconds
Time taken: 2.26321 seconds
-----------------
Version: dmz / z00n
Time taken: 1.388251 seconds
Time taken: 1.462289 seconds
Time taken: 1.387326 seconds
Time taken: 1.510869 seconds
Time taken: 1.223017 seconds
-----------------
По-моему неплохо. Хотя императивный алгоритм в той же Javа справляется за 0.15 секунд, в некоторых случаях это не критично. А когда нужна только часть результата то у Хаскеля есть все шансы порвать императивных конкурентов.
P.S. Всплеск в первом проходе в "vanilla" видимо вызван тем, что что-то недовычислилось в исходных данных. Я в Haskell не силен, так что сделать все strict у меня не получилось.
Здравствуйте, Rtveliashvili Denys, Вы писали:
RD>По-моему неплохо. Хотя императивный алгоритм в той же Javа справляется за 0.15 секунд, в некоторых случаях это не критично. А когда нужна только часть результата то у Хаскеля есть все шансы порвать императивных конкурентов. RD>P.S. Всплеск в первом проходе в "vanilla" видимо вызван тем, что что-то недовычислилось в исходных данных. Я в Haskell не силен, так что сделать все strict у меня не получилось.
Здесь надо понимать, что императивный вариант использует технику Хоара, а в случае Хаскеля применяются однонаправленные списки. Хаскельный вариант на полной сортировке никогда не обгонит quicksort в варианте Хоара на массиве.
Здравствуйте, Rtveliashvili Denys, Вы писали:
RD>По-моему неплохо. Хотя императивный алгоритм в той же Javа справляется за 0.15 секунд, в некоторых случаях это не критично. А когда нужна только часть результата то у Хаскеля есть все шансы порвать императивных конкурентов.
Кстати, в приведенном варианте функция part использует хвостовую рекурсию, и поэтому должна вычисляться полностью при обращении к первому элементу. Анализатор строгости ghc, соответственно, в компиляторе должен будет убить ленивость в part. Это может плохо сказаться на характеристике получения части результата. И наоборот — хорошо сказаться при вычислении всего результата. По хорошему, надо ее переписать без хвостовой рекурсии, и сравнить на частичных результатах.
RD>>По-моему неплохо. Хотя императивный алгоритм в той же Javа справляется за 0.15 секунд, в некоторых случаях это не критично. А когда нужна только часть результата то у Хаскеля есть все шансы порвать императивных конкурентов. RD>>P.S. Всплеск в первом проходе в "vanilla" видимо вызван тем, что что-то недовычислилось в исходных данных. Я в Haskell не силен, так что сделать все strict у меня не получилось.
G>Здесь надо понимать, что императивный вариант использует технику Хоара, а в случае Хаскеля применяются однонаправленные списки. Хаскельный вариант на полной сортировке никогда не обгонит quicksort в варианте Хоара на массиве.
Насчет разницы алгоритмов — согласен. Но быть может есть какой-то purely functional вариант quicksort что порвет вариант Хоара даже на полной сортировке. Так или иначе, результат в целом неплохой при умеренной сложности самого алгоритма. :-)
Здравствуйте, Rtveliashvili Denys, Вы писали:
RD>Насчет разницы алгоритмов — согласен. Но быть может есть какой-то purely functional вариант quicksort что порвет вариант Хоара даже на полной сортировке.
Нету. Вариант Хоара — самый оптимальный и экономный вариант quicksort из известных человечеству, сформулированный в терминах, близких к железу . Так как Хаскельный вариант выполняется на том же железе, то быстрее на полной сортировке он в принципе оказаться не может .
Тем более, что если не оперировать списками, то пропадет вся приятная функциональшина. Ибо список — самый "функциональный" тип данных. Так же как массив — самый "императивный".
RD>Так или иначе, результат в целом неплохой при умеренной сложности самого алгоритма.
А вот это — да. Собственно, об этом и надо говорить, ИМХО Немногие программы сейчас требуют производительности любой ценой. Скажем так, отношение производительности программы к умственным затратам программиста существенно превосходит таковые для языка С. Поэтому, в реальных условиях Хаскельные программы могут оказаться быстрее, чем С++. Или, по крайней мере, не сильно медленнее. Зато — проще и надежнее.
Это если не говорить о встраиваемых системах, высоконагруженных серверных приложениях (они по принципам программирования похожи на предыдущие), и вообще — задачах, требующих реакций реального времени.
-- Вариант 0 (quick sort "в лоб")
qsort0 [] = []
qsort0 (x:xs) = qsort0 (filter (<x) xs) ++ [x] ++ qsort0 (filter (>=x) xs)
-- Вариант 1 (мой вариант) - один проход по списку
-- сортировка относительно середины списка
qsort2 [] = []
qsort2 xs = qsort2 lesser ++ equals ++ qsort2 greater
where (lesser,equals,greater) = split mean xs
mean = xs !! (length xs `div` 2)
split mean xs = split' [] [] [] xs
where split' ls es gs [] = (ls,es,gs)
split' ls es gs (p:ps) | p < mean = split' (p:ls) es gs ps
| p == mean = split' ls (p:es) gs ps
| p > mean = split' ls es (p:gs) ps
-- Вариант 1 (dmz / z00n)
qsort3 x = qsort3' x []
qsort3' [] y = y
qsort3' [x] y = x:y
qsort3' (x:xs) y = part xs [] [x] []
where
part [] l e g = qsort3' l (e ++ (qsort3' g y))
part (z:zs) l e g
| z > x = part zs l e (z:g)
| z < x = part zs (z:l) e g
| otherwise = part zs l (z:e) g
Результаты. Каждая клетка обозначает:
Время / память для 100 тыс. элементов
Время / память для 1 млн. элементов
Сортируемый список --> Алгоритм сортировки
Случайные
значения
Отсортированные
значения
В обратном
порядке
Вариант 0
("простая программа" на Haskell)
1.06 sec / 10 Mb
103.77 sec / 92 Mb
480.72 sec / 7 Mb
* Более 600 sec *
* out of memory *
* out of memory *
Вариант 1 (мой)
0.17 sec / 12 Mb
1.86 sec / 122 Mb
0.17 sec / 6 Mb
2.08 sec / 56 Mb
0.16 sec / 6 Mb
2.03 sec / 56 Mb
Вариант 2 (dmz / z00n)
0.08 sec / 6 Mb
1.08 sec / 57 Mb
258.28 sec / 7 Mb
* Более 600 sec *
259.47 sec / 7 Mb
* Более 600 sec *
Sort из стандартной библиотеки
(merge sort)
0.34 sec / 17 Mb
5.67 sec / 150 Mb
0.13 sec / 9 Mb
1.64 sec / 75 Mb
0.16 sec / 12 Mb
1.83 sec / 121 Mb
Выводы:
Как видно, некоторые алгоритмы проваливаются при сортировке уже отсортированных списков (в прямолм или обратном порядке).
Самый быстрый алгоритм на случайных данных — вариант 2 (dmz / z00n), начальный вариант 0 в 10 раз медленнее.
На отсортированных списках лучше всех работает merge sort, хотя он и проседает на случайных данных.
Вариант 1 (мой) — что-то среднее между этим всеми алгоритмами Работает стабильно на всех типах входных данных.
В предыдущем сообщении я представлял замеры для случайных и отсортированных списков.
И если для отсортированных все понятно — там использовались списки [1..n] и [n,n-1 .. 1], то со случайными есть вопрос.
Похоже, у меня получился какой-то неправильный случайный список Поэтому оказались не верны и результаты для случайных списков.
Исправляя данную оплошность я сделал изменения:
— длина списков 200 тыс, 400 тыс, 800 тыс., 1,6 млн, 3,2 млн
— случайные списки формируются 5 раз с разными seed
rnds seed = randomRs (1,1000000) (mkStdGen seed) :: [Int]
list = take n $ rnds seed
1. Как и было ранее лучшим был признан алгоритм (dmz / z00n)
2. В два раза от победителя отстает простейший qsort (раньше отставал сильнее).
3. Мой алгоритм qsort2 раньше отставал в 1,7 раз. Сейчас при увеличении длины списка отстает от победителя все сильнее и сильнее. Очевидно, что сложность его выше.
4. Худшим стал стандартный sort (на основе merge sort). Судя по исходникам бывший когда-то quicksort заменили на mergesort. Время работы растет быстрее, чем у qsort и qsort3, и даже быстрее чем у qsort2.
Так, что стабильность моего алгоритма отменяется
В общем, вот такая ситуация для случайных списков...
Может вообще перед сортировкой проверять насколько сильно уже отсортирован список и потом вызывать соответствующий тип сортировки:
для отсортированных списков — Data.List.sort, для неотсортированных — qsort3?
Здравствуйте, D. Mon, Вы писали:
Б>> mean = xs !! (length xs `div` 2)
DM>Вот эта часть очень смущает. Полтора раза по списку проходит?
Ну, в общем-то да. Но это позволяет хоть как-то отрабатать на отсортированных списках. И я не знаю иного способа найти в них подходящий опорный элемент.
Вот интересно, можно ли за один проход по списку найти его медиану? Построением дерева какого-нибудь, например. Частный случай со списком чисел не рассматриваем.