Sto progettando un DSL (in clojure, in particolare, sebbene questa domanda sia più generale di quella) in cui le "entità" sono tracciate come hash / mappe immutabili e dove l'appartenenza a "concetto" di un'entità è determinata dinamicamente da le chiavi e i valori delle mappe. Un esempio di come questo apparirebbe:
(defconcept AnnotatedEntity :contains [annotations meta-data])
(defconcept PointCloud :contains vertices)
(defconcept Polygon :contains [vertices edges])
(defconcept Triangle
:isa Polygon
:condition (= (count vertices) 3))
(defconcept Rectangle
:isa Polygon
:condition (= (count vertices) 4))
(concepts {:vertices [[0 0], [0 1], [1 0]] :edges [[0 1] [1 2] [2 0]]})
#{PointCloud Polygon Triangle}
(concepts {:vertices [[0 0] [0 1] [1 1] [1 0]]
:annotations {:name "unit-rectangle point-cloud"}
:meta-data {}})
#{PointCloud AnnotatedEntity}
Poiché il :condition di un concetto è solo una funzione che viene eseguita sulla mappa, possiamo ignorare questa parte del test (e quindi eventuali requisiti sui valori) per ora; il mio interesse è nell'individuare in modo efficiente tutti i possibili concetti in cui una determinata mappa potrebbe mantenere l'appartenenza in base alle sue chiavi. Ad esempio, semplifichiamo quanto sopra solo per questo:
(defconcept AnnotatedEntity :contains [annotations meta-data])
(defconcept PointCloud :contains [vertices])
(defconcept Polygon :contains [vertices edges])
(defconcept Triangle :contains [vertices edges])
(defconcept Rectangle :contains [vertices edges])
(possible-concepts {:vertices [[0 0], [0 1], [1 0]]
:edges [[0 1] [1 2] [2 0]]})
#{PointCloud Polygon Triangle Rectangle}
(possible-concepts {:vertices [[0 0] [0 1] [1 1] [1 0]]
:annotations {:name "unit-rectangle point-cloud"}
:meta-data {}})
#{PointCloud AnnotatedEntity}
Attualmente, eseguo questo con la forza bruta, che è molto efficiente per gli esempi di giocattoli, ma che non è abbastanza efficiente per un pezzo centrale di una libreria che a volte viene chiamato molte volte al millisecondo con mappe arbitrariamente grandi e arbitrariamente molte concetti.
Un semplice esempio di ottimizzazione che migliora questo processo è di tenere traccia di una mappa di tutte le chiavi incluse in qualsiasi concetto in modo tale che i valori siano insiemi di concetti contenenti la chiave; per l'esempio precedente:
(def concepts-of-keys {:annotations #{AnnotatedEntity}
:meta-data #{AnnotatedEntity}
:vertices #{PointCloud Polygon Triangle Rectangle}
:edges #{Polygon Triangle Rectangle}})
(defn possible-concepts [ent]
(set (filter #(every? (partial contains? ent) (.getKeys %))
(apply clojure.set/union (map concepts-of-keys (keys ent))))))
Questo è un po 'meglio del semplice test su ogni concetto possibile, ma solo se i concetti hanno chiavi abbastanza uniche. Se ogni concetto dipende da una singola chiave come :meta-data o :id o qualcosa di molto comune (o tutti i concetti ereditano da un singolo concetto di base), allora questo è fondamentalmente tanto inefficiente quanto il controllo di ogni concetto.
Di conseguenza non credo che nessuna di queste sia la soluzione migliore. Ad esempio, si potrebbe immaginare di costruire un albero decisionale (che verrebbe, in pratica, avvolto in un ref o in un atomo e aggiornato come i concetti sono definiti):
(def concept-decision-tree
"
Each element of the decision tree is [test-keys if-every if-not-every] where
test-keys is a key or set of keys that should be tested for membership in a
given entity; if the entity contains all these keys, descend along the
if-every element and along the if-not-every otherwise. These values are sets
if the membership of the entity has been deduced by the most recent
decision.
"
[#{:annotations :meta-data} ;; if the entity has all of these elements...
;; descend into this subtree
[:vertices [:edges #{AnnotatedEntity PointCloud Polygon Triangle Rectangle}
#{AnnotatedEntity PointCloud}]
#{AnnotatedEntity}]
;; otherwise, descend into this subtree...
[:vertices [:edges #{PointCloud Polygon Triangle Rectangle}
#{PointCloud}]
#{}]])
(defn possible-concepts [ent]
(loop [[test-keys if-every if-not-every] concept-decision-tree]
(if (every? (partial contains? ent)
(if (set? test-keys) test-keys [test-keys]))
(if (set? if-every) if-every (recur if-every))
(if (set? if-not-every) if-not-every (recur if-not-every)))))
Questo è ancora meglio, supponendo che possiamo mantenere l'albero delle decisioni; quello che mi chiedo è qual è il modo migliore per farlo o, alternativamente, quale alternativa è ugualmente / più efficiente? Non è ovvio per me come si possa bilanciare un tale albero decisionale con l'aggiunta di concetti.
La mia intuizione è che questo problema ha una teoria che è ampiamente capita e che io non conosco il nome formale del problema; del resto, dovrei menzionare il fatto che sono intellettualmente interessato alla risposta più ottimale e non alla risposta che può essere scritta più velocemente o che un project manager apprezzerebbe di più.
In altre parole, quello che sto cercando in una risposta:
- Una soluzione al problema di aggiornamento dell'albero decisionale, concettualmente con sufficienti dettagli da implementare, o una semplice implementazione di esempio
- Una soluzione alternativa a questo problema che è ugualmente / similmente / più efficiente
- Un puntatore a una letteratura scientifica su questo argomento
- Un nome formale / standard per questo problema
- Esempi di librerie o linguaggi che implementano questo tipo di digitazione dinamicamente
Cosa non sto cercando in una risposta:
- una soluzione brute-force (ne ho già una!)
- "< qualcosa di simile > l'ottimizzazione prematura è la radice di tutto il male, < qualcosa qualcosa > quindi solo forza bruta."
Un'altra cosa che dovrei menzionare: sebbene io abbia scritto questi esempi usando mappe standard, non mi oppongo a una soluzione che coinvolge una sottoclasse speciale della persistente classe di mappe che tiene traccia delle sue chiavi e annota le mappe appena create con le loro tipi come sono creati. Ad esempio, un tipo speciale che imita le mappe ma sa che quando incontra (dissoc ent-map :vertices) la nuova mappa dovrebbe avere concetti come PointCloud, Polygon, ecc. Rimossi dal suo elenco di concetti.
Grazie in anticipo!