Какой язык для быстрого прототипирования эвристики в комбинаторной оптимизации?

Question

Мне нужно разработать быстрый эвристический алгоритм для сложной комбинаторной задачи. Поэтому я думаю, что для решения этой проблемы лучше всего сначала выучить более выразительный язык, чем С ++, потому что я думаю, что для решения моего задания требуется много разных алгоритмических попыток.

Некоторые личные мнения о некоторых языках, которые являются кандидатами:

Python:

хороший синтаксис, хорошая выразительность, но не строго типизированный -> Я предпочитаю ошибки компилятора, а не ошибки времени выполнения и не хочу разрабатывать тестовые наборы для каждого алгоритма.

Haskell:

хороший синтаксис, хорошая выразительность, строгий тип, но я думаю, что мне придется дважды подумать обо всех вещах, которые я хочу применить -> возможно, слишком много границ из-за чистоты языка

Что я хочу / люблю? (может быть взаимоисключающим!)

• хорошая выразительность для быстрого развития
• сильная типизация
• функционально-языковые функции высшего порядка
• изменяемые типы данных, такие как массивы
• возможно какие-то дженерики / шаблоны
• может быть, возможность декларативного программирования (для подзадач в комбинаторной опции)

Что мне не нужно:

• Современное исполнение кода (проблема в классе np, поэтому допустимые линейные издержки из-за неправильного использования лени должны быть терпимы)
• распараллеливание

Я должен признать, что мне нравится выразительность Python, но я не создаю хороший и надежный код с ним.

Я люблю искусство функционального программирования, но мне также нравятся изменяемые структуры данных. Может быть, потому что я не достаточно опытен, чтобы производить алгоритмы за короткое время с такой "чистотой" в языке.

Любые рекомендации? Какие-нибудь подобные события?

А как насчет Clean, F#, Erlang ...?

Answer 1

Я думаю, что вы обнаружите, что большинство популярных языков очень высокого уровня, которые идеально подходят для прототипирования, "слабо типизированы".

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

Вы упомянули Python, поэтому я рекомендую, не будучи знакомым с haskell сам. Python имеет Numpy и очень хорошо интегрируется с C. У него также есть модуль itertools в stdlib, который очень хорош для комбинаторной работы (разумно примененный, он может превзойти немного лучше, чем посредственный C). В настоящее время я работаю над аналогичным проектом, и я прототипировал его с помощью Python. В настоящее время я нахожусь в процессе перевода большей части этого на C. Это хороший процесс, потому что у меня уже есть реализация каждого алгоритма на python, поэтому, как только я заверну свой C для python, я смогу проверить их друг против друга, чтобы убедитесь, что они дают одинаковый вывод на идентичный ввод. Итак, поскольку я создал прототип на python, я получил очень дешевую среду тестирования для своего приложения и модуль python, написанный на C.

Кроме того, я уже нашел оптимальные (или, по крайней мере, достаточные) алгоритмы, и если мне придет в голову новый, я могу быстро изменить питон в другой ветке, чтобы проверить его на эффективность.

Какой бы язык вы ни выбрали, убедитесь, что он хорошо интегрируется с вашим конечным целевым языком, чтобы воспользоваться преимуществами подобных привилегий.

Answer 2

Я программист на Haskell более 7 лет, и с тех пор я не использовал другой язык для серьезной работы. Моя рекомендация, конечно же, Haskell.:-)

По моему опыту, вот что вы можете ожидать от Haskell:

• Изучение Хаскелла требует времени. Математически склонные люди склонны очень быстро это понимать, но большинству программистов требуется некоторое время, чтобы отучиться от своего предыдущего опыта и познакомиться с чисто функциональным программированием. Если ваш проект должен был быть завершен вчера, тогда вам лучше использовать язык, который вы уже знаете.
• Примерно в 4x-10x меньше кода, чем в C. Например, здесь прототип реализации быстрой сортировки

:

 qsort :: Ord a => [a] -> [a]
 qsort []     = []
 qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs)

• Как только ваш исходный код компилируется, он обычно корректен с первой попытки. Система типов и чистота, то есть отсутствие изменяемых структур данных, во многом ответственны за это.
• Haskell заставляет вас задуматься над проблемой. Если компилятор подходит, это, как правило, признак того, что у вас пока нет четкого понимания вашей проблемной области.
• Утечки пространства и переполнение стека. Они случаются, но их, как правило, нетрудно исправить, когда они появляются. Однако это требует хорошего понимания модели исполнения, то есть ленивой оценки. Вот типичный пример космической утечки.
• Сообщество Haskell - отличный ресурс. Если вы столкнулись с камнем преткновения, посещение канала IRC#haskell или запрос в списках рассылки [e-mail] или [e-mail], скорее всего, решит вашу проблему.

Я не думаю, что это можно подкрепить чем-то другим, кроме опыта; Итак, вы должны поверить мне на слово.

Официально было опубликовано несколько отчетов об опыте, см. Также страницу Haskell in Industry. Я нашел, что Haskell против Ada против C++ против Awk против... Эксперимент по повышению производительности программного прототипирования [pdf] был особенно поучительным.

Answer 3

Я не использовал Python, и я лишь немного использовал Haskell именно для той цели, которую вы описываете - создание прототипов. Здесь следует обратить внимание не на замедление, которое дает вам лень, а на тот факт, что, казалось бы, алгоритмы с постоянным пространством могут иметь утечки пространства, которые потребляют всю доступную память с помощью блоков, представляющих неоцененные куски кода. Космические утечки трудно увидеть.

Конечно, вы можете беспокоиться о них и обыскивать свою программу, разыскивая их seq и другие формы уродства... Но смысл использования языка прототипов состоит в том, чтобы избежать всех этих головных болей.

Если вы играете с задачами настолько маленького размера, что не имеет значения, если в памяти создается отрывок для каждого шага оценки в вашей программе от начала до конца, тогда я мог бы порекомендовать Haskell.

Answer 4

Хотя я бы посоветовал вам выучить больше языков, если ваша цель - как можно быстрее создать прототип этой проблемы, я бы использовал C++ (как вы, кажется, уже владеете этим).

в то время как другие языки, вероятно, лучше подходят для создания прототипов в целом, если вы знаете только C++ сейчас, у вас, вероятно, будет достаточно большая кривая обучения, которая замедлит вас настолько, что вы потеряете его преимущество по крайней мере для этого проекта (особенно если вы смотрите на основные смена парадигмы также).

с другой стороны, если на самом деле речь идет о расширении ваших знаний на будущее, тогда подойдет практически любой из языков сценариев.

Answer 5

Haskell может действительно сиять, если вы можете выразить проблемный домен как "язык, специфичный для встроенного домена" (eDSL). На самом деле это просто библиотека функций с претензиями, но хитрость заключается в том, чтобы определить базовую абстракцию и функции для ее манипулирования. Его сложно объяснить более конкретными терминами без лучшего понимания вашей области, но я ожидаю, что вы захотите дать базовому комбинаторному алгоритму некоторые подсказки о том, какие части проблемы следует решить в первую очередь, и как определить многообещающие частичные решения.

Начните с просмотра списка монады. Если ваша проблема не слишком сложна, то это может быть все, что вам нужно. Более подробную информацию можно найти на этой странице, чтобы узнать, как добавить возврат и сокращение.

Answer 6

C# 4.0

Он имеет почти все функции, которые вам требуются.

1. Функциональное программирование
2. Функции высшего порядка
3. Параллельные расширения.NET
4. ленивости
5. Дженерики
6. Массивы

Некоторые примеры ProjectEular

ПРИМЕЧАНИЕ: я бы сам пошел с Python и написал несколько модулей на C++.;)

Answer 7

Может быть, R это ответ, который вы ищете?

Answer 8

Я бы не стал использовать C++, потому что он не поймет, что не хватает индексации в конце массивов, и потому что он не предоставит вам сборщик мусора. Лично я бы использовал Java только потому, что с этим я знаком.

Я бы подумал о том, с чем вы знакомы, с какими людьми, с которыми вы хотите работать или, по крайней мере, общаться, знакомы, и какие библиотеки доступны для использования. Это может включать такие вещи, как ввод / вывод или графические библиотеки для результатов постобработки, а также специализированные комбинаторные алгоритмы. Вы можете также искать инструменты профилирования, чтобы вы могли видеть, где ваш алгоритм тратит все свое время.

Answer 9

Мне нужно разработать быстрый эвристический алгоритм для сложной комбинаторной задачи.

Для таких проблем, сделайте себе вкус и выберите функциональный язык. Они намного лучше для выражения математических свойств и абстракций. Язык, который поддерживает функции высшего порядка, лямбды и замыкания, должен быть подходящим для вашего типа работы.

Примечание: Smalltalk и Ruby также могут пойти очень далеко по этому пути, потому что они полуфункциональны (они имеют выдающуюся поддержку для замыканий, в частности, потому что синтаксис для замыканий блоков очень легкий и читаемый), но я думаю, вы найдете такой язык, как Haskell или Lisp, лучше соответствует типу алгоритмов, которые вы разрабатываете.

Answer 10

Я хотел бы предложить D выстрел. Это близко к C++, но намного легче рассуждать и без всех отвратительных бородавок. Если вы думаете о написании окончательной реализации на C++, гораздо проще перевести D на C++ как Python, и, кроме того, у вас есть возможность остаться с D, поскольку производительность находится на одном уровне с C++.