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

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

3 голосов
/ 21 сентября 2010

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

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

Вопрос, который у меня был до того, как я начал это:

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

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

Ответы [ 2 ]

4 голосов
/ 21 сентября 2010

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

Существует простой способ получить то, что вы хотите.

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

3 голосов
/ 21 сентября 2010

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

  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. Это кажется достаточно быстрым и требует очень мало памяти (я думаю, линейно с глубиной). Почему бы сначала не попробовать что-то подобное, а затем перейти к более сложной структуре данных, если она недостаточно хороша?

...