スローDatascriptクエリ

Question

私は、名前を与えられた 2ノードの最後の共通祖先のツリー構造を照会するDatascriptを使用して、私がこれまで持っているもの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ので、2つの 親句をサポートしていません。

スキーマは次のとおりです。

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

Answer 1

まあ、再帰的なルールはDataScriptで最速のものではありません。したがって、クエリコードに直接parentルールをインライン展開することで、クエリを少し速くすることができます。

もう1つのことは、クエリーがDataScriptでも最速のものではないことです。変数を管理し、それらを反復処理、中間コレクションを割り当て、クエリを解析費やした時間のかなりの量は、ありますなど、手動のデータベース上でクエリを好むことが可能な2つの状況が/インデックスがありアクセスしている：

1. クエリはより速く動作しますあなたは（大規模な関係で作業する場合など、クエリを手動で書くために、ハッシュ結合は非常に面倒である事を利用します）
2. クエリが不可欠アルゴリズムよりもはるかに簡単な方法であなたの問題を表現する自分自身を書きたいよりも

あなたの場合、どちらも真実ではありません。グラフを直線的に歩く）。また、バグがあります。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))))