我使用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}
递归规则并不是javascript中最快的东西。因此,您可以通过将parent
规则直接内联到查询代码中,从而使查询更快一些。
另一件事是查询不是最快的事情是javascript以及。有相当多的时间花在解析查询、分配中间集合、对它们进行迭代、管理变量等方面。在两种情况下,您可以选择查询而不是手动访问数据库/索引:
- 查询的工作速度比你自己写的快(例如,当处理大型关系时,查询将利用哈希连接,这是一件非常繁琐的手工编写的事情)
- 查询用比命令式算法更简单的方式表达你的问题
在您的例子中,这两个都不成立(您并不真正处理关系,而是线性地遍历图)。此外,还有一个错误:如果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))))