Как итеративное углубление поиска может быть эффективно реализовано в haskell?

Question

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

data Foo =
  { fooA :: Int
  , fooB :: Int
  , fooC :: Int
  , fooD :: Int
  , fooE :: Int
}

и рейтинговая функция:

rateFoo :: myFoo -> Int

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

fooTree :: Foo -> Tree

Моя поисковая функция выглядит примерно так:

optimize :: Int -> Foo -> Foo
optimize threshold foo = undefined

Вопрос, который у меня был, прежде чем я начну, заключается в следующем:

Поскольку дерево может быть сгенерировано данными в каждой точке, возможно ли иметь только сгенерированные части дерева, которые в настоящее время необходимы алгоритму? Можно ли освободить память и восстановить дерево, если это необходимо для экономии памяти (можно создать отпуск на уровне n в O(n) и n остается маленьким, но не настолько маленьким, чтобы со временем в памяти оставалось все дерево)?

Это то, что я могу ожидать от времени выполнения? Может ли среда выполнения недооценивать выражения (превратить оцененное выражение в неоцененное)? Или что за грязный хак я должен сделать для этого?

Answer 1

Вот мой совет:

1. Просто реализуйте свой алгоритм максимально простым способом.
2. Профиль.
3. Оптимизируйте для скорости или использования памяти при необходимости.

Я очень быстро понял, что я недостаточно умен и / или не достаточно опытен, чтобы рассуждать о том, что будет делать GHC или как будет работать сборщик мусора. Иногда вещи, которые, я уверен, будут катастрофически неэффективными при работе с памятью, с первого раза будут работать гладко, а реже - вещи, которые кажутся простыми, требуют много возражений с аннотациями строгости и т. Д.

Глава реального мира на Haskell, посвященная профилированию и оптимизации, невероятно полезна, когда вы перейдете к шагам 2 и 3.

---

Например, вот очень простая реализация IDDFS, где f расширяет детей, p является предикатом поиска, и x является отправной точкой.

search :: (a -> [a]) -> (a -> Bool) -> a -> Bool
search f p x = any (\d -> searchTo f p d x) [1..]
  where
    searchTo f p d x
      | d == 0    = False
      | p x       = True
      | otherwise = any (searchTo f p $ d - 1) (f x)

Я проверил, ища "abbaaaaaacccaaaaabbaaccc" с children x = [x ++ "a", x ++ "bb", x ++ "ccc"] как f, Это кажется достаточно быстрым и требует очень мало памяти (я думаю, линейно с глубиной). Почему бы сначала не попробовать что-то подобное, а затем перейти к более сложной структуре данных, если она недостаточно хороша?

Answer 2

Среда выполнения не оценивает выражения.

Однако, есть простой способ получить то, что вы хотите.

Рассмотрим структуру, похожую на молнию для вашего дерева. Каждый узел содержит значение и символ, представляющий вниз, вверх и т. Д. Когда вы переходите к следующему узлу, вы можете либо нормально двигаться (помещая предыдущее значение узла в соответствующий слот), либо забывать (помещая выражение, которое оценивает предыдущий узел в правом слоте). Тогда у вас есть контроль над тем, сколько "истории" вы держите.