Potatura di alberi binari

1

Ho un albero binario generico che è usato per calcolare combinazioni di cose - cioè un powerset in linguaggio formale.

Il più delle volte è usato per calcolare sottoinsiemi di dimensioni N .

Come esempio reale, diciamo che abbiamo 10 giocatori in una squadra di pallacanestro e vogliamo calcolare ogni 5 di partenza.

Nel mio particolare dominio del problema, questo viene eseguito milioni di volte, quindi sto provando a spremere ogni singola prestazione possibile. Dove sono interessato solo ai sottoinsiemi, sto cercando di potare l'albero mentre lo costruisco poiché sembra essere qui dove giace il collo di bottiglia.

L'albero è costruito dalle foglie in basso quindi suppongo di poter contare gli antenati mentre costruisco e (nell'esempio sopra) fermare quel ramo ogni volta che ne ho 5, ma mentre questo funzionerebbe, penso che probabilmente aggiungerebbe altro overhead di quello che salverebbe.

Qualche idea (oltre a provarlo)?

Esempio

Questi dati:

Rendequestoprofilo:

AddGeneration costruisce ogni livello dell'albero mentre TraverseTree tira i risultati. Come puoi vedere, c'è qualcosa come una divisione di 99: 1 in termini di sforzo tra i due.

    
posta Robbie Dee 03.08.2016 - 13:30
fonte

0 risposte

Leggi altre domande sui tag