Как и итеративное углубление поиска реализована эффективным в 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 или как будет работать сбор мусора. Иногда вещи, которые я уверен, что будет катастрофически неэффективным памятью работать гладко впервые, а менее часто - вещами, которые кажутся простыми, требуют большого количества суеты со строгостью аннотации и т. Д.

То Real World 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

Время выполнения не распространяется на выражения.

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

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