Posso usare una struttura dati più veloce di un albero per questo?

Question

Ho un albero decisionale binario. Prende input come una serie di float e ogni nodo branch si divide su un indice di input e il valore alla fine mi porta su una foglia.

Sto eseguendo un numero elevato di ricerche su questo albero (circa il 17% del tempo di esecuzione in base all'analisi delle prestazioni (Modifica: avendo ottimizzato altre aree è ora quasi al 40%), e mi chiedo se potrei/dovrebbe utilizzare una diversa struttura dei dati per migliorare la velocità di ricerca.

Non è possibile utilizzare una sorta di tabella hash, poiché gli input non si collegano direttamente a un nodo foglia, ma mi chiedevo se qualcuno avesse suggerito in merito ai metodi e alle strutture dati che potrei usare al posto dell'albero (o oltre?) per migliorare la velocità di ricerca.

La memoria è una preoccupazione, ma meno preoccupante della velocità.

Il codice è attualmente scritto in C#, ma ovviamente è possibile applicare qualsiasi metodo.

Modifica: C'è un po 'troppo codice per postare, ma darò maggiori dettagli sull'albero.

L'albero viene generato utilizzando calcoli del guadagno di informazioni, non è sempre uno split 50/50, il valore split può essere qualsiasi valore float. Un singolo input può anche essere suddiviso più volte aumentando la risoluzione su quell'input.

ho postato una domanda sul rendimento del iteratore qui:

Micro optimisations iterating through a tree in C#

Ma penso di aver bisogno di guardare la struttura dati stessi per migliorare ulteriormente le prestazioni.

Sto mirando al maggior numero di prestazioni possibile qui. Sto lavorando a un nuovo metodo di machine learning e l'albero si sviluppa usando un ciclo di feedback. Per il processo su cui sto lavorando, ritengo che verrà eseguito per diversi mesi, quindi un risparmio di qualche% qua e là è enorme. L'obiettivo finale è la velocità senza utilizzare troppa memoria.

Answer 1

decisioni Presumendo hanno un 50/50 possibilità:

Immaginate che avete dovuto due decisioni binarie; possibili percorsi sono 00, 01, 10, 11

Immaginate al posto dell'albero che aveste un array con quattro risultati; puoi trasformare la tua matrice di float in un numero binario che sarebbe indice in questa matrice.

Answer 2

Se ho capito bene, si dispone di intervalli in virgola mobile che devono essere associati a una decisione. Qualcosa del genere:

 x <= 0.0  : Decision A 
0.0 < x <= 0.5  : Decision B 
0.5 < x <= 0.6  : Decision C 
0.6 < x    : Decision D 

Un albero binario è un ottimo modo per gestirlo. Finché l'albero è ben bilanciato e i valori di input sono equamente distribuiti tra gli intervalli, è possibile aspettarsi O (log n) confronti, dove n è il numero di decisioni possibili.

Se l'albero non è equilibrato, si potrebbero fare molti più confronti del necessario. Nel peggiore dei casi: O (n). Quindi guarderei gli alberi e vedremo quanto sono profondi. Se lo stesso albero viene utilizzato più e più volte, il costo di riequilibrio speso una volta può essere ammortizzato su molte ricerche.

Se i valori di input non sono distribuiti uniformemente (e lo si conosce in anticipo), è possibile che si desideri specificare l'ordine dei confronti in modo speciale in modo che i casi più comuni vengano rilevati in anticipo. Puoi farlo manipolando l'albero o aggiungendo casi speciali nel codice prima di controllare effettivamente l'albero.

Se si sono esauriti i miglioramenti algoritmici e si è ancora necessario ottimizzare, è possibile esaminare una struttura dati con una località migliore rispetto a un albero binario generale. Ad esempio, è possibile inserire i limiti della partizione in un array contiguo ed eseguire una ricerca binaria su di esso. (E, se la matrice non è troppo lungo, si potrebbe anche provare una ricerca lineare sulla matrice come può essere più amichevole per la cache e il branch prediction.)

Infine, mi piacerebbe prendere in considerazione la costruzione di un indice di grossa questo ci dà un vantaggio sull'albero (o array). Ad esempio, utilizzare alcuni dei bit più significativi del valore di input come indice e verificare se è in grado di tagliare i primi pochi livelli dell'albero. Ciò può aiutare più di quanto si possa immaginare, poiché i confronti saltati hanno probabilmente una bassa probabilità di ottenere previsioni corrette delle branche.