Ho bisogno di aiuto con l'algoritmo per l'elenco di ordinamento

Question

Ho bisogno di aiuto con l'algoritmo per l'elenco di ordinamento

#1 da (1 voti)

1

La risposta è probabilmente ovvia ma non a me in questo momento, quindi mi chiedevo se qualcuno che è migliore con gli algoritmi di ordinamento può aiutarmi a guidarmi nella giusta direzione. Questo non è compito a casa, sto legittimamente cercando di lavorare all'interno di un progetto esistente per qualcosa di relativo al lavoro.

In sostanza, comincio con un elenco non ordinato di oggetti dati che rappresentano qualcosa di simile ai commenti del forum. Questi oggetti POSSONO esplicitamente avere uno e solo un genitore diretto. In altre parole

Parent (1...*) ----------- (1...1) Child

Un bambino ha un riferimento al suo genitore, tuttavia un genitore non può vedere i suoi figli (esplicitamente).

Tipicamente quando si ordina una lista si passerebbe un comparatore che, dato un qualsiasi due oggetti dati nella collezione, dovrebbe restituire un numero intero che rappresenta la distanza tra i due oggetti in un grafico. La distanza tra due commenti completamente indipendenti sarà basata sul valore Timestamp dell'oggetto dati.

Il problema è che qualsiasi due oggetti dati può e deve essere confrontato solo con un timestamp con altri oggetti dati dello stesso ramo padre. Ecco un esempio:

DO1 - Time(1000ms)

|___DO3 - Time(5000ms)

DO2 - Time(2000ms)

DO1 e DO2 confrontati daranno un numero negativo, quindi questi due sono ordinati correttamente l'uno rispetto all'altro. Anche DO3 a DO1 è corretto perché posso supporre che qualsiasi ramo sopra un commento debba essere inferiore a. Il problema viene dal confronto tra DO3 e DO2. Ho pensato che in questo caso dovrei confrontare il genitore di ordine più alto con DO2 e questo funziona finché non ci sono figli DO sotto DO3.

Sto cercando di capire se il grafico dell'oggetto corrente è ancora abbastanza informazioni per un comparatore per restituire correttamente un numero appropriato per due confronti qualsiasi. Forse il comparatore deve essere inizializzato prima con la lista non ordinata in modo che possa costruire una struttura ad albero in cui posso vedere esplicitamente una lista di bambini di qualsiasi genitore dato? O forse ho bisogno di refactoring? A questo punto non sono preoccupato per le prestazioni. Grazie.

data-structures algorithms sorting

posta maple_shaft 03.02.2012 - 13:52

fonte

1 risposta

Leggi altre domande sui tag data-structures algorithms sorting

Dove devo trovare la cache in un servizio WCF? quale tipo di relazione esisterà tra un membro e una classe di rete P2P in un diagramma di classe?

score 1 · Accepted Answer

L'approccio ovvio è quello di percorrere prima la profondità dell'albero, prendendo i bambini di ciascun nodo in ordine del loro timestamp. Questo è l'ordine che desideri.

Costruire l'albero e di iterarlo ovviamente ti farà risparmiare tempo, ma puoi semplicemente prendere tutte le voci con un determinato indicatore genitore durante il test.

In alternativa puoi definire l'ordine in modo che i discendenti vengano dopo i loro predecessori e gli altri nodi siano ordinati dal timestam dei figli immediati del loro antenato comune. Quindi:

ROOT
 +- DO1 T=1
 |   +- DO2 T=5
 |   +- DO3 T=8
 |       +- DO4 T=12
 +- DO5 T=3
     +- DO6 T=11

DO2 > DO1 perché è un discendente, DO4 > DO1 because it's also descendant, DO3 > DO2 because they are both immediate children to their ancestor DO1 and DO3 has higher timestamp and DO6 > DO4 because their ancestor is ROOT to which you come from DO6 via DO5 and from DO4 via DO1 and DO5 has higher timestamp than DO1' .

Ma costruire e camminare sull'albero sarà più veloce.