Здравствуйте, FR, Вы писали:
FR>Sum(list) не содержит в отличии от кода на Хаскеле выше алгоритма.
Для такого простого случая это не суть важно. Вряд ли бы кто описывал алгоритм, где надо просто найти сумму. В более сложном случае и счетчик цикла может перепрыгивать, и выход из цикла может произойти досрочно, и сам массив/список может быть надо будет изменить на лету...
Здравствуйте, Тролль зеленый и толстый, Вы писали:
ТЗИ>Ладно, какова алгоритмическая сложность алгоритма на Хаскеле? Если это тот же самый алгоритм, его сложность в среднем N log N, так?
Да.
ТЗИ>(Про потребление памяти скромно умолчим).
Можно и не умалчивать: в Haskell алгоритм работает не in-place, поэтому используется дополнительная память.
Здравствуйте, gandjustas, Вы писали:
G>Это заявление в духе "миллионы леммингов не могут ошибаться" ? Практика показала что могут.
Ну... вот, например, при программировании шахмат возникает достаточно много различных алгоритмических задач, которые надо реализовать оптимальным образом. При этом в списке самых сильнейших шахматных движков и близко нет написанных на функциональных языках программирования. Не потому ли, что они для этого мало приспособлены???
Здравствуйте, Mystic, Вы писали:
M>Здравствуйте, gandjustas, Вы писали:
G>>Выделенное — это твои трудности. По факту алгоритм на хаскеле или другом ФЯ оказывается гораздо читаемее.
M>Зачастую алгоритмы описывают байты и операции с ними, а также включают различные вопросы производительности, что не всегда так уж однозначно переводится на ФЯ.
Тут имеются ввиду алгоритмы, с точки зрения математики, а не алгоритмы как "конечная последовательность шагов для достижения какого-либо результата".
Потому что для последовательности шагов еще надо доказать что она приводит к этому результату.
M>Например, если взять alpha-beta поиск, то там в C-варианте будут функции DoMove, и UndoMove. Соответственно, для того, чтобы функциональный язык генерировал оптимальный код, необходимо чтобы он был в курсе сакрального равенства Position = UndoMove(DoMove(Position, Move), Move).
Тут как раз ленивость рулит, которая в хаскеле есть. Можно генерировать деревья всех вариантов, а потом отсекать неподходящие, не генерируя полное дерево. Причем из-за неизменяемости одинаковые поддеревья будут присутствовать в одном экземпляре и вычисляться не более одного раза.
Здравствуйте, Mystic, Вы писали:
M>Здравствуйте, gandjustas, Вы писали:
G>>Это заявление в духе "миллионы леммингов не могут ошибаться" ? Практика показала что могут.
M>Ну... вот, например, при программировании шахмат возникает достаточно много различных алгоритмических задач, которые надо реализовать оптимальным образом. При этом в списке самых сильнейших шахматных движков и близко нет написанных на функциональных языках программирования. Не потому ли, что они для этого мало приспособлены???
1)Пока нет
2)Для шахматных алгоритмов разработаны быстрые реализации при помощи битовых операций, которые хорошо делаются на низкоуровневых языках
3)Про скорость мы тут не говорили, мы обсуждаем понятность записи алгоритмов на различных языках
Здравствуйте, gandjustas, Вы писали:
ТЗИ>>И вообще, хватит отождествлять математику и функциональное программирование. А императивное программирование — это что ли не математика? G>Императивное программирование опирается на изменяемое состояние, которое не имеет никакого отношения к математике.
Как ни странно, но первое доказательство арифметичности вычислимых функций (то есть, утверждения о том, что для любой вычислимой функции f формула y = f(x) может быть выражена как утверждение на языке арифметики Пеано со свободными переменными x и y) было построено с использованием в качестве модели вычислений универсальных регистровых машин (то есть машин с изменяемым состоянием). А арифметичность функций, вычислимых, например, в лямбда-исчислении, следует уже из эквивалентности различных моделей вычислений (то есть возможности написать интерпретатор лямбда-исчисления на регистровых машинах). Так что я бы поостерегся говорить, что изменяемое состояние не имеет никакого отношения к математике.
Здравствуйте, gandjustas, Вы писали:
G>Тут имеются ввиду алгоритмы, с точки зрения математики, а не алгоритмы как "конечная последовательность шагов для достижения какого-либо результата". G>Потому что для последовательности шагов еще надо доказать что она приводит к этому результату.
Тогда неплохо было бы определиться с понятием, что такое алгоритм И какие алгоритмы требуется формально записывать. Сне почему-то кажется, что изначально автор интересовался именно "конечной последовательностью шагов".
G>Тут как раз ленивость рулит, которая в хаскеле есть. Можно генерировать деревья всех вариантов, а потом отсекать неподходящие, не генерируя полное дерево. Причем из-за неизменяемости одинаковые поддеревья будут присутствовать в одном экземпляре и вычисляться не более одного раза.
Рулит, да не совсем. Во-первых, к одной и той же позиции можно прийти с перестановками ходов. В этом случае в шахматных движках обычно используют Z-Orbice ключи, которые позволяю быстро определять, а была ли такая позиция. Во-вторых, при переборе на менее-более значительную глубину, количество узлов превышает оперативную память. Соответственно, позиции из боковых вариантов удаляются из хэша.
Здравствуйте, nikov, Вы писали:
N>Здравствуйте, gandjustas, Вы писали:
ТЗИ>>>И вообще, хватит отождествлять математику и функциональное программирование. А императивное программирование — это что ли не математика? G>>Императивное программирование опирается на изменяемое состояние, которое не имеет никакого отношения к математике.
N>Как ни странно, но первое доказательство арифметичности вычислимых функций (то есть, утверждения о том, что для любой вычислимой функции f формула y = f(x) может быть выражена как утверждение на языке арифметики Пеано со свободными переменными x и y) было построено с использованием в качестве модели вычислений универсальных регистровых машин (то есть машин с изменяемым состоянием). А арифметичность функций, вычислимых, например, в лямбда-исчислении, следует уже из эквивалентности различных моделей вычислений (то есть возможности написать интерпретатор лямбда-исчисления на регистровых машинах). Так что я бы поостерегся говорить, что изменяемое состояние не имеет никакого отношения к математике.
Ну еще можно машину тьюринга вспомнить.
Тем не менее большинство методов доказательств не работают с изменяемым состоянием.
Здравствуйте, gandjustas, Вы писали:
G>2)Для шахматных алгоритмов разработаны быстрые реализации при помощи битовых операций, которые хорошо делаются на низкоуровневых языках
А в чем проблема эти битовые операции перенести на функциональные языки???
Здравствуйте, Mystic, Вы писали:
M>Здравствуйте, gandjustas, Вы писали:
G>>2)Для шахматных алгоритмов разработаны быстрые реализации при помощи битовых операций, которые хорошо делаются на низкоуровневых языках
M>А в чем проблема эти битовые операции перенести на функциональные языки??? спросите у создателей языков.
Наверное в том что они мало востребованы.
Здравствуйте, Mystic, Вы писали:
M>Здравствуйте, gandjustas, Вы писали:
G>>Тут имеются ввиду алгоритмы, с точки зрения математики, а не алгоритмы как "конечная последовательность шагов для достижения какого-либо результата". G>>Потому что для последовательности шагов еще надо доказать что она приводит к этому результату.
M>Тогда неплохо было бы определиться с понятием, что такое алгоритм И какие алгоритмы требуется формально записывать. Сне почему-то кажется, что изначально автор интересовался именно "конечной последовательностью шагов".
Мне больше всех нравится определение Маркова:
Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату
Да другой это алгоритм. Для начала быстрая сортировка — это сортировка обменами. И разделение множеств там по-другому происходит, а не тупой "фильтрацией". И вопрос выбора среднего элемента там как-то опущен.
Если вам Хаскель понятнее, пишите своим женам письма на Хаскеле. И переписываться на RSDN'е можете тоже на Хаскеле.
Здравствуйте, Тролль зеленый и толстый, Вы писали:
ТЗИ>Если человек изучал математику и не изучал программирование, ему оба варианта будут непонятны. А вот нормальное описание на естественном языке он с легкостью воспримет.
Не всегда, вот то описание которое ты дал вряд-ли, там без знания основ программирования ничего ни понятно.
ТЗИ>И вообще, хватит отождествлять математику и функциональное программирование. А императивное программирование — это что ли не математика?
Математика, но гораздо более сложная чем та что описывает функциональщину хотя формально они и эквивалентны.
ТЗИ>Математика — это вообще всего лишь набор формальных соотношений. То, как в математике принято записывать формулы — всего лишь традиция.
Ну не скажи, математика все-таки стремится к максимальной простоте и понятности.
ТЗИ>То, что функциональное программирование похоже на запись формул в математике, не делает его ближе к математике, чем императивное или какое-либо другое программирование.
Делает за счет того что к ней гораздо проще применить формальный математический аппарат (ту же теорию категорий например). Попытка его применить к императивщине моментально порождает всякие гадости типа комбинаторного взрыва и необходимости решать NP полные задачи.
ТЗИ>А ты делаешь ложное противопоставление, не понимая, что функциональное и императивное программирование — всего лишь две эквивалентные формы записи формальных соотношений.
В том дело что с практической точки зрения далеко не эквивалентные.
M>Для такого простого случая это не суть важно. Вряд ли бы кто описывал алгоритм, где надо просто найти сумму. В более сложном случае и счетчик цикла может перепрыгивать, и выход из цикла может произойти досрочно, и сам массив/список может быть надо будет изменить на лету...
В более сложных случаях тоже проще и декларативнее получается.
Здравствуйте, FR, Вы писали:
FR>Другой вариант это динамические языки (питон, руби) для прототипирования они очень хороши. Я например часто сложные алгоритмы FR>которые нужно реализовать на C++ сначала делаю на питоне (сейчас больше на окамле) это дает существенный выигрыш во времени FR>разработки.
Остается только вопрос зачем с ОКамла на С++ что-то переписывать?
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
G>Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату
Для анализа алгоритма еще важны соображения эффективности. Т. е. любой алгоритм должен иметь вычислительную сложность, которую мы должны уметь вычислить.
Здравствуйте, Тролль зеленый и толстый, Вы писали:
ТЗИ>Да другой это алгоритм. Для начала быстрая сортировка — это сортировка обменами. И разделение множеств там по-другому происходит, а не тупой "фильтрацией". И вопрос выбора среднего элемента там как-то опущен.
Переключаем википедию на английский и смотрим: http://en.wikipedia.org/wiki/Quicksort#Algorithm
function quicksort(array)
var list less, greater
if length(array) ≤ 1
return array
select and remove a pivot value pivot from array
for each x in array
if x ≤ pivot then append x to less
else append x to greater
return concatenate(quicksort(less), pivot, quicksort(greater))
Почти тоже что на хаскеле, но отдельно делается filter для каждой половины, хотя это можно заоптимизировать.
ТЗИ>Если вам Хаскель понятнее, пишите своим женам письма на Хаскеле. И переписываться на RSDN'е можете тоже на Хаскеле.
Слив засчитан.
Хотя если вы с женой общаетесь на C\C++ я хочу на это посмотреть
И какие алгоритмы требуется формально записывать. Сне почему-то кажется, что изначально автор интересовался именно "конечной последовательностью шагов".
спросите у создателей языков.
