Экваординация для больших структур DAG в Haskell

Question

Я новичок в Haskell (пару месяцев). У меня есть программа Haskell, которая собирает большое выражение DAG (а не дерево, DAG), потенциально глубокое и с несколькими путями слияния (т. Е. Количество разных путей от корня до листьев огромно). Мне нужен быстрый способ протестировать эти dags для равенства. По умолчанию Eq-деривация будет только повторять, исследуя одни и те же узлы несколько раз. В настоящее время это приводит к тому, что моя программа занимает 60 секунд для относительно небольших выражений и даже не заканчивается для более крупных. Профилировщик указывает, что он занят проверкой равенства большую часть времени. Я хотел бы реализовать пользовательский Eq, который не имеет этой проблемы. У меня нет способа решить эту проблему, которая не требует много переписывания. Поэтому я хочу услышать ваши мысли.

Моя первая попытка состояла в том, чтобы узлы дерева «инструмента» с хешем, который я вычисляю поэтапно, используя Data.Hashable.hash, когда я создаю дерево. Этот подход дал мне простой способ проверить, что две вещи не равны, не заглядывая глубоко в структуру. Но часто в этой DAG из-за путей в объединении DAG структуры действительно равны. Таким образом, хэши равны, и я возвращаюсь к полномасштабному тестированию равенства.

Если бы у меня был способ сделать физическое равенство, тогда многие мои проблемы исчезли бы: если они физически равны, то это все. В противном случае, если хэш отличается, то это все. Только углубляйтесь, если они физически не совпадают, но их хэш соглашается.

Я мог бы также имитировать git и вычислить SHA1 на узел, чтобы решить, равны ли они периоду (нет необходимости рекурсивно). Я знаю, что это помогло бы, потому что, если я позволю равенству быть решенным полностью в терминах хэш-равенства, то программа будет работать в десятки миллисекунд для самых больших выражений. Этот подход также имеет приятное преимущество в том, что если по какой-то причине есть два равных дага, они физически не равны, а являются равными по содержанию, я бы также смог быстро обнаружить его в этом случае. (С идентификаторами Id все равно должен сделать обход в этой точке). Поэтому мне больше нравится семантика.

Этот подход, однако, требует гораздо большей работы, чем просто вызов функции Data.Hashable.hash, потому что я должен получить ее для каждого варианта типа узла dag. И более того, у меня есть несколько представлений о даге, с немного отличающимися определениями узлов, поэтому мне нужно будет в основном делать эту хэширующую трюкную вещь дважды или более, если я решу добавить больше представлений.

Что вы хотите сделать?

Answer 1

Часть проблемы в том, что Haskell не имеет понятия об идентичности объекта, поэтому, когда вы говорите, что у вас есть группа DAG, где вы ссылаетесь на тот же узел дважды, насколько Haskell затрагивает его только два значения в разных местах на дерево. Это принципиально отличается от концепции OO, где объект индексируется по его местоположению в памяти, поэтому различие между «одним и тем же объектом» и «разными объектами с равными полями» имеет смысл.

Чтобы решить вашу проблему, вам необходимо обнаружить, когда вы посещаете тот же объект, что и раньше, и для этого вам необходимо иметь концепцию «того же объекта», которая не зависит от значения. Есть два основных способа атаковать это:

• Храните все ваши объекты в векторе (т.е. массив), и использовать векторную индекс в качестве идентичности объекта. Заменяйте значения индексами во всей структуре данных.

• Дайте каждому объекту уникальное поле «identity», чтобы вы могли узнать, видели ли вы это раньше, когда проходите DAG.

Первый способ заключается в том, как модуль Data.Graph в упаковке контейнеров. Одно из преимуществ заключается в том, что если у вас есть одно сопоставление от DAG к вектору, то равенство DAG становится просто векторным равенством.

Answer 2

Любой эффективный способ проверки равенства будет переплетаться с тем, как вы создаете значения DAG.

Вот идея, которая отслеживает все узлы, когда-либо созданные на карте. По мере добавления новых узлов на карту им присваивается уникальный идентификатор.

Создание узлов теперь становится монодичным, поскольку вы нарисовали эту карту (и следующий доступный идентификатор) во время вычислений.

В этом примере узлы выполнены в виде Роза деревьев, и порядок детей не имеет значения - отсюда и призыв к sort при выводе ключа в карте.

import Control.Monad.State 
import Data.List 
import qualified Data.Map as M 

data Node = Node { _eqIdent:: Int  -- equality identifier 
        , _value :: String -- value associated with the node 
        , _children :: [Node] -- children 
        } 
    deriving (Show) 

type BuildState = (Int, M.Map (String,[Int]) Node) 

buildNode :: String -> [Node] -> State BuildState Node 
buildNode value nodes = do 
    (nextid, nodeMap) <- get 
    let key = (value, sort (map _eqIdent nodes)) -- the identity of the node 
    case M.lookup key nodeMap of 
    Nothing -> do let n = Node nextid value nodes 
         nodeMap' = M.insert key n nodeMap 
        put (nextid+1, nodeMap') 
        return n 
    Just node -> return node 

nodeEquality :: Node -> Node -> Bool 
nodeEquality a b = _eqIdent a == _eqIdent b 

Одно из предостережений - этот подход требует, чтобы вы знали всех дочерних узлов узла при его создании.