缓慢的 Datascript 查询

Question

我正在使用 Datascript 查询树结构以查找 2 个节点有名字，here's 到目前为止我已经知道了，但它真的很慢 -- 知道为什么（或者有更好的方法）吗？

(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 也是如此。有相当多的时间花在解析查询、分配中间集合、迭代它们、管理变量等方面。在两种情况下，您可以更喜欢查询而不是手动 database/indexes 访问：

查询比您自己编写的查询速度更快（例如，在处理大型关系时，查询将使用散列连接，手动编写非常乏味）
查询以比命令式算法更简单的方式表达您的问题

在您的情况下，这些都不是真的（您实际上并没有处理关系，而是线性地遍历图表）。此外，还有一个错误：如果 node1 和 node2 具有共同的直接父级，则您的查询将不起作用。

我推荐的是通过直接访问实体来做同样的事情。实体只是索引查找，没有任何与查询相关的开销，因此在这种简单的情况下，它们应该工作得更快。

像这样应该就足够了：

(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))))

缓慢的 Datascript 查询

Slow Datascript query

clojure

datascript