Являются ли списки в Haskell неэффективными?

Question

Я начал делать Project Euler и получил номер проблемы 9 . Поскольку я использовал Project Euler для изучения Haskell, я решил использовать списочные представления (как показано в Learn You A Haskell ). Я делаю это, и GHCI требуется некоторое время, чтобы выяснить триплет, который, как я понял, является нормальным из-за вычислений. Вчера на работе (пока я не работаю программистом профессионально), я разговаривал с другом, который знает VBA, и он хотел попытаться найти ответы в VBA. Я подумал, что это тоже будет забавный вызов, и я произвожу некоторые базовые циклы for и if, но меня поразило то, что это намного быстрее, чем Haskell.

Мой вопрос: действительно ли понимание списка Хаскеллом невероятно неэффективно? Сначала я думал, что это только потому, что я был в интерактивном режиме GHC, но потом я понял, что VBA также интерпретируется.

Обратите внимание, я не опубликовал свой код, потому что он является ответом на проект euler. Если он ответит на мой вопрос (как, например, я делаю что-то не так), я с удовольствием выложу код.

[править] Вот мое понимание списка Хаскелла:
[(a,b,c) | c <- [1..1000], b <- [1..c], a <- [1..b], a+b+c=1000, a^2+b^2=c^2]
Думаю, я мог бы уменьшить диапазон на c, но разве это замедляет его?

Answer 1

Есть две вещи, которые вы можете делать с этой проблемой, которые могут замедлить ваш код. Одним из них является то, как вы пытаетесь значения для а, б и в. Если вы перебираете все возможные значения a, b, c от 1 до 1000, вы будете тратить много времени. Чтобы дать подсказку, вы можете использовать a + b + c = 1000, если вы измените его для c. Другое состоит в том, что если вы используете только понимание списка, оно обработает все возможные значения для a, b и c. Проблема говорит вам, что существует только один уникальный набор чисел, который удовлетворяет этой проблеме, поэтому, если вы измените свой ответ с этого:

[ a * b * c | .... ]

до:

head [ a * b * c | ... ]

тогда ленивая оценка Хаскелла означает, что он остановится после нахождения первого ответа. Это эквивалент Хаскелла выхода из цикла VBA, когда вы найдете первый ответ. Когда я воспользовался обоими этими советами, у меня был ответ, который был выполнен очень быстро (менее чем за секунду) в ghci.

Приложение. Сначала я пропустил условие a [(a, b) | b <- [1..100], a <- [1..b-1]]

Answer 2

Рассмотрим упрощенную версию понимания вашего списка:

[(a,b,c) | a <- [1..1000], b <- [1..1000], c <- [1..1000]]

Это даст все возможные комбинации a, b и c.Это все равно, что сказать: «Сколько путей могут вынести три тысячи кубиков?»Ответ 1000 *1000* 1000 = 1 000 000 000 различных комбинаций.Если для создания каждой комбинации требуется 0,001 секунды, то для завершения всех комбинаций потребуется 1 000 000 секунд (~ 11,5 дней).(Ладно, 0,001 секунды на самом деле довольно медленно для компьютера, но вы поняли идею)

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

Теперь рассмотрим ваше понимание.Похоже, это должно быть намного быстрее, верно?

[(a,b,c) | c <- [1..1000], b <- [1..c], a <- [1..b], a+b+c=1000, a^2+b^2=c^2]

Есть 1000 вариантов для c.Сколько там б и а?Что ж, средний выбор для c равен 500. Для всех вариантов c, тогда существует в среднем 500 вариантов для b (поскольку b может варьироваться от 1 до c).Аналогичным образом, для всех вариантов c и b существует в среднем 250 вариантов для a.Это очень волнисто, но я уверен, что это точно.Таким образом, 1000 вариантов для c * 1000/2 вариантов для b * 1000/4 вариантов для a = 1 млрд. / 8 ~ = 100 млн.Это в 8 раз быстрее, но если вы обратили внимание, вы заметите, что на самом деле это такая же большая сложность , что и в упрощенной версии выше.Если бы мы сравнили «упрощенные» и «улучшенные» версии той же проблемы, но из [1..100000] вместо [1..1000], «улучшенный» все равно будет только в 8 раз быстрее, чем «упрощенный».

Не поймите меня неправильно, 8x - замечательное ускорение с постоянным коэффициентом.Но если вы не хотите подождать пару часов, чтобы найти решение, вам нужно получить более качественное решение.

Как отметил Нейл, способ уменьшить сложность этой проблемы дляb и c, выберите a, который удовлетворяет a+b+c=1000.Таким образом, вы не пробуете кучу a с, которые потерпят неудачу.Это будет отбрасывать сложность большого О;вы будете рассматривать только приблизительно 1000 * 500 * 1 = 500 000 комбинаций вместо ~ 100 000 000.

Answer 3

Получив решение проблемы, вы можете проверить версии решений Haskell для других людей на сайте Project Euler, чтобы получить представление о том, как другие люди решили проблему. Кстати, вот ссылка на упомянутую проблему: http://projecteuler.net/index.php?section=problems&id=9

Answer 4

В дополнение к тому, что все остальные говорили о генерации меньшего числа элементов в генераторах, вы также можете переключиться на использование Int вместо Integer в качестве типа чисел.По умолчанию это целое число, но ваши числа достаточно малы, чтобы вписываться в Int.

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