Slow Datascript запрос

Question

Я использую Datascript для запроса древовидной структуры для последнего общего предка 2 узлов, имеющих имена, вот что я получил до сих пор, но это действительно медленно - есть идеи почему (или есть лучший способ)?

(defn lca
  "Last common ancestor"
  [db name1 name2]
  (d/q '[
          :find [(pull ?anc [:db/id :name]) ...]
          :in    $ % ?name1 ?name2
          :where
            (?node1 :name ?name1)
            (?node2 :name ?name2)
            (anc ?anc1 ?node1)
            (anc ?anc2 ?node2)
            [(not= ?anc1 ?anc2)]
            (parent ?anc ?anc1)
            (parent ?anc ?anc2)
          ]
          @db
          '[
            [ (parent ?par ?child)
              (?par :children ?child)]
            [ (anc ?par ?child)
              (?par :children ?child)]
            [ (anc ?anc ?child)
              (?par :children ?child)
              (anc ?anc ?par)]
            ]
          name1
          name2))

Я изначально собирался использовать not исключить всех более высоких предков, чем последний общий, но Datascript в настоящее время не поддерживает not отсюда два родительских предложения.

Схема такая:

:children {:db/valueType :db.type/ref 
           :db/cardinality :db.cardinality/many 
           :db/index true}
:name {:db/index true}

Answer 1

Ну, рекурсивные правила не самая быстрая вещь в DataScript. Таким образом, вы можете сделать свой запрос немного быстрее, вставив parent Править прямо в код запроса.

Другое дело, что запросы не самая быстрая вещь - это и DataScript. На анализ запроса уходит немало времени, выделение промежуточных коллекций, итерации по ним, управление переменными и т. Д. Существует две ситуации, в которых вы можете предпочесть запрос над ручным доступом к базе данных / индексам:

1. Запрос работает быстрее, чем вы пишете сами (например, при работе с большими отношениями запрос будет использовать хеш-соединения, что очень утомительно писать вручную)
2. Запрос выражать вашу проблему гораздо проще, чем императивный алгоритм

В вашем случае, ни то, ни другое не верно (вы не работаете с отношениями, вы ходите по графику линейно). Также есть ошибка: ваш запрос не будет работать, если у узла 1 и узла 2 есть общий прямой родитель.

Я рекомендую делать то же самое, напрямую обращаясь к сущностям. Объекты - это просто поиск по индексу без каких-либо накладных расходов, связанных с запросами, поэтому в таком простом случае они должны работать намного быстрее.

Что-то вроде этого должно быть достаточно:

(defn parent [node]
  (first (:_children node)))


(defn ancestors [node]
  (->> node
       (iterate parent)
       (take-while some?)
       reverse))


(defn last-common-ancestor [db name1 name2]
  (let [node1 (d/entity db [:name name1])
        node2 (d/entity db [:name name2])]
         ;; zipping ancestor chains together
    (->> (map vector (ancestors node1) (ancestors node2))
         ;; selecting common prefix
         (take-while (fn [[ac1 ac2]] (= ac1 ac2)))
         ;; last item in common prefix is what you looking for
         (last))))