Haskell - простой способ кеширования вызова функции

Question

У меня есть такие функции, как:

millionsOfCombinations = [[a, b, c, d] | 
  a <- filter (...some filter...) someListOfAs, 
  b <- (...some other filter...) someListOfBs, 
  c <- someListOfCs, d <- someListOfDs]

aLotOfCombinationsOfCombinations = [[comb1, comb2, comb3] | 
  comb1 <- millionsOfCombinations, 
  comb2 <- millionsOfCombinations,
  comb3 <- someList,
  ...around 10 function calls to find if
    [comb1, comb2, comb3] is actually useful]

Оценка millionsOfCombinations занимает 40 секунд.на очень быстрой рабочей станции.Оценка aLotOfCombinationsOfCombinations !! 0 заняла 2 дня: - (

Как я могу ускорить этот код? До сих пор у меня было 2 идеи - использовать профилировщик. Пробовал запускать myapp +RTS -sstderr после компиляции с GHC,но получить пустой экран и не хочу ждать дни, пока он не закончится.

2-я мысль была как-то кешировать millionsOfCombinations. Правильно ли я понимаю, что для каждого значения в aLotOfCombinationsOfCombinations, millionsOfCombinationsоценивается несколько раз? Если это так, как я могу кешировать результат? Очевидно, я только начал изучать Haskell. Я знаю, что есть способ сделать кеширование вызовов с помощью монады, но я все еще не понимаю этих вещей.

Answer 1

Используйте флаги -fforce-recomp, -O2 и -fllvm

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

Профиль Ваш код

Флаг -sstderr не совсем профилирует. Когда люди говорят о профилировании, они обычно говорят о профилировании кучи или профилировании времени с помощью флагов -prof и -auto-all.

Избегайте дорогостоящих примитивов

Если вам нужен весь список в памяти (т. Е. Он не будет оптимизирован), рассмотрите неупакованные векторы. Если вместо Integer подойдет Int, учтите это (но Integer - разумное значение по умолчанию, когда вы не знаете!). Используйте рабочие / упаковочные преобразования в нужное время. Если вы сильно опираетесь на Data.Map, попробуйте использовать Data.HashMap из библиотеки неупорядоченных контейнеров. Этот список можно продолжать и продолжать, но, поскольку у вас еще нет интуиции относительно того, куда уходит ваше время вычислений, профилирование должно идти первым!

Answer 2

Я думаю, что нет пути.Обратите внимание, что время для создания списка растет с каждым списком.Таким образом, вы получаете около 1000000 ³ комбинаций для проверки, что действительно занимает много времени.Кэширование списка невозможно, но вряд ли что-либо изменит, поскольку новые элементы могут быть созданы практически мгновенно.Возможно, единственный способ - изменить алгоритм.

Если millionsOfCombinations является константой (а не функцией с аргументами), она автоматически кэшируется.Иначе, сделайте его константой, используя предложение where:

aLotOfCombinationsOfCombinations = [[comb1, comb2, comb3] | 
  comb1 <- millionsOfCombinations, 
  comb2 <- millionsOfCombinations,
  comb3 <- someList,
  ...around 10 function calls to find if
    [comb1, comb2, comb3] is actually useful] where

  millionsOfCombinations = makeCombination xyz