Slow Datascript Abfrage

Question

Ich benutze Datascript um eine Baumstruktur für den letzten gemeinsamen Vorfahren von 2 Knoten mit gegebenen Namen, here's, was ich bisher habe, aber es ist wirklich langsam - jede Idee warum (oder Gibt es einen besseren Weg)?

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

ich zunächst alle höheren Vorfahren als der letzt gemeinsam man ausschließen würde not verwenden, aber Datascript zurzeit nicht not daher die beiden Elternklauseln nicht unterstützt.

Das Schema ist:

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

Answer 1

Nun, rekursive Regeln in Datascript nicht die schnellste Sache sind. So können Sie Ihre Anfrage wahrscheinlich ein wenig schneller machen, indem Sie die Regel parent direkt in den Abfragecode einfügen.

Eine andere Sache ist, dass Abfragen nicht das schnellste Ding sind, ist auch DataScript. Es gibt ziemlich viel Zeit, um die Abfrage ausgegeben Parsen Zwischen Sammlungen Zuteilung über sie iterieren, Variablen Verwaltung, etc. Es sind zwei Situationen, in denen Sie Abfrage über manuelle Datenbank bevorzugen, können/Indizes zugreifen:

1. Abfrage funktioniert schneller als Sie selbst schreiben würde (zB bei großen Beziehungen arbeiten, werden nutzen Abfrage Hashverknüpfungen, eine Sache, die sehr mühsam manuell zu schreiben)
2. Abfrage Ihr Problem auf viel einfachere Art und Weise als zwingend notwendig Algorithmus ausdrücken

In Ihrem Fall ist beides nicht wahr (Sie arbeiten nicht wirklich mit Beziehungen, Sie den Graphen linear durchlaufen). Außerdem gibt es einen Fehler: Ihre Abfrage funktioniert nicht, wenn Knoten1 und Knoten2 gemeinsame direkte Eltern haben.

Was ich empfehle ist, das gleiche durch den direkten Zugriff auf Entitäten zu tun. Entitäten sind nur Index-Lookups, die keinen Overhead mit Abfragen enthalten, daher sollten sie in einem so einfachen Fall viel schneller arbeiten.

So etwas sollte genügen:

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