Come monitorare/mostrare lo stato di avanzamento durante un ordinamento C++

Question

Sto pianificando di scrivere un plug-in di elaborazione della geometria interattivo in C++ che ordinerà spesso grandi quantità di dati. Sebbene le indicazioni preliminari suggeriscano che l'ordinamento richiederà solo un secondo o due, preferirei mostrare i progressi in quel periodo, ad esempio vorrei aggiornare un indicatore di avanzamento alcune volte al secondo. Sarebbe preferibile attivare un cursore di attesa e lasciare all'utente un programma che si blocca per un periodo di tempo indeterminato (anche se sono solo pochi secondi).

Se dovessi usare qualcosa come std :: sort, potrei usare la funzione di confronto per aggiornare l'indicatore di avanzamento di tanto in tanto, ma non avrei idea di 'percentuale completa'. Potrei anche suddividere l'ordinamento in sotto-ordinamenti, aggiornando l'avanzamento tra i sotto-ordinamenti e quindi l'unione. La mia migliore scommessa potrebbe essere quella di scrivere il proprio metodo di ordinamento, anche se non so quanto impegno richiederebbe per ottenere prestazioni pari a std :: sort (e garantire la correttezza). In ogni caso, quel metodo sort invierà occasionalmente una "percentuale completa" ad un metodo di callback.

Mi chiedevo se altre persone hanno incontrato e risolto questo problema - spero che forse ci sia un metodo di ordinamento in una libreria standard che fa quello che voglio, o qualche altra tecnica che non ho pensato.

Aggiornamento: Grazie per le grandi risposte finora. Ci sono stati alcuni suggerimenti molto validi, e ho intenzione di non scegliere la risposta accettata finché non avrò avuto la possibilità di testare le idee nel mio prossimo progetto.

Aggiornamento 2: Ho completato il mio progetto e questo è risultato essere un non-problema (almeno per il cliente. Poiché venderanno il software, potrebbero comunque ricevere feedback dai clienti che cambieranno le loro menti su questo). Scegliere una risposta accettata è stato difficile perché c'erano molte buone risposte, ma alla fine quella che ho scelto puntava a un articolo wiki su Merge Sort che aveva un'animazione molto evocativa. Quindi questa è la prima strategia che avrei perseguito se avessi avuto bisogno di andare avanti con questo).

Answer 1

Poiché std :: sort è basato sul modello, l'origine deve essere disponibile in un'intestazione. Puoi crearne una copia e inserire la tua richiamata di avanzamento. Il grosso problema sarà la previsione di quanto sei vicino al completamento: la maggior parte delle funzioni di ordinamento sarà basata su Quicksort, che non sempre esegue lo stesso numero di confronti.

scrivere il proprio Merge sort sarebbe una possibilità; l'algoritmo è semplice e il numero di passaggi è ben definito.

Answer 2

Vorrei raccomandare la seconda opzione: utilizzare std::sort o un'altra funzione di ordinamento standard come qsort e fare in modo che il comparatore riferisca i suoi progressi. Ma non aggiornare in ogni confronto - che sarebbe insopportabile lento - invece aggiornare ogni (dire) 100 ms.

Answer 3

Utilizzare il observer pattern per segnalare al genitore quando ciascuna parte completa. Usando questo e il numero totale di elementi che devono essere ordinati, puoi aggiornare la tua barra di avanzamento in tempo reale.

Answer 4

Penso che, anche se hai scritto il tuo tipo, dovresti fare molte misurazioni accurate se vuoi che l'indicatore di avanzamento sia accurato. Se si desidera solo un indicatore di progresso approssimativo, è possibile utilizzare una metrica come "distanza media tra elementi confrontati" o "numero di confronti rispetto al numero medio previsto per quicksort" come metrica e implementare l'idea di confronto che si è già menzionata.

E sì, presumo che tu non sia un completo idiota e non pianifichi di aggiornare l'indicatore di avanzamento ad ogni confronto. Se lo facessi, passeresti molto più tempo a indicare il progresso rispetto all'ordinamento.

Ad esempio, generalmente ci si aspetta circa le operazioni n log2 n per quicksort. L'analisi di quanti confronti sono coinvolti è più dettagliata e può essere più accurata di quella misura generale, ma per gli scopi di questo esempio, lasciamo presumere. Quindi puoi contare i confronti e segnalare number_of_comparisons/(n log2 n) come la tua stima dei progressi.

Poiché si tratta solo di un indicatore medio, eseguirò alcuni esperimenti e vedrò fino a che punto la tua stima non è attiva, e introdurre alcuni fattori fondenti per farlo allineare al caso medio previsto. Si potrebbe anche avere una barra di avanzamento che indica l'incertezza avendo una specie di "Questo è dove penso che sarò fatto". indicatore e un po 'di spazio dopo l'indicatore.

Anche se si è utilizzato il proprio tipo e si è arrivati ​​a una misura più apparentemente precisa, la barra di avanzamento non si aggiornerebbe regolarmente e l'effetto sarebbe simile. L'unico modo per sapere con certezza quanto tempo impiegherà il tuo ordinamento è se usi un tipo un po 'più lento, ma davvero prevedibile, nel qual caso puoi predire quanto tempo ci vorrà dal numero di elementi, o usare un modo veramente veloce ordina che ha un comportamento meno prevedibile in casi specifici, nel qual caso non esiste un modo reale per avere una barra di avanzamento perfettamente accurata.

La prevedibilità delle attività secondarie e la prevedibilità del numero totale di confronti sono fortemente correlate. Quindi davvero non penso che le sottoattività facciano una misura migliore del numero totale di confronti.

Se si desidera utilizzare il proprio ordinamento e la prevedibilità è il tuo obiettivo più alto, vai su heapsort. È ancora un ordinamento O(n log2 n), ed è quasi un ordinamento di comparazione minima (o almeno mi ricordo di aver letto Knuth). Richiede anche una quantità di tempo molto prevedibile per completare indipendentemente dal set di dati che alimenta. È uno degli ordinamenti più lenti O(n log2 n), ma ancora.

Come uno dei tuoi commentatori ha menzionato, potresti risolvere un problema che in realtà non esiste. Esegui prima alcuni esperimenti. Il problema è una divertente sfida intellettuale, indipendentemente dalla sua utilità. :-)

Answer 5

vedo il problema come il seguente:

1. Volete eventi discreti per essere alimentate nel corso di un unico processo continuo.
2. Questa suddivisione serve solo a comunicare all'utente le cose in corso.

miei suggerimenti sono:

1. utilizzare un'icona di caricamento da qualcosa come http://ajaxload.info/, o, se non è un ambiente GUI basata, basta precisare carico. Poiché l'evento è inferiore a 2 secondi, questo non sarà un problema. Sono previsti hang up se il tempo di attesa supera i 10 secondi.

2. Scrivere il proprio metodo di ordinamento comporta molti problemi di sicurezza dei thread, che potrebbero causare problemi se il codice utilizza il multithreading o è destinato a farlo in futuro.

informazioni 3.Another importante che si dovrebbe considerare quanto male fuori uso i dati saranno ogni volta che si desidera ordinare, così in effetti si sarà misurare il grado di casualità presente, e il numero atteso di calcoli che potrebbe essere necessario fare. è possibile utilizzare queste informazioni come un indicatore di quanti swap sono richiesti, che a loro volta possono essere contati mentre si itera attraverso l'ordinamento. Gioca con i dati.

Answer 6

usare la forza bruta :)

int elem_num = raw_data.size(); 
int percentage_delta = 100/(elem_num/20); 
int percentage = 0; 
int i = 0; 
std::multiset<Elem*> sorted_data(&compareElemFunc); 
foreach(Elem& elem, raw_data) 
{ 
    sorted_data.insert(&elem); 
    if(i%20) 
    { 
     updateProgressBar(percentage); 
     percentage += percentage_delta; 
    } 
    i++; 
} 
//now, your data is perfectly sorted, iterate through sorted_data 

(nel caso in cui non si desidera implementare il proprio std :: sort() e dato che mi manca requisiti completi)

Answer 7

I don' t consiglio di provare a hackerare std :: sort. Questo è generalmente implementato con introsort ed è un'operazione NLogN estremamente veloce. Costruire il contenitore che stai per ordinare sarà in genere più costoso rispetto all'ordinamento dei dati.

Tuttavia, se avete intenzione di implementare una barra di avanzamento, vi consiglio di mettere l'ordinamento in un thread separato. Normalmente le applicazioni multithread sono più difficili da scrivere e gestire rispetto a quelle a thread singolo, ma puoi farlo in un modo in cui non è adatto a questo caso. L'applicazione può ancora essere prevalentemente a thread singolo senza che vengano eseguite operazioni simultanee ad eccezione di questa barra di avanzamento e probabilmente qualche gestione degli eventi per mantenere l'interfaccia utente reattiva. Quando sei pronto per ordinare i dati, fai semplicemente fuoco su un altro thread per farlo e metti il ​​thread principale in un loop di attesa fino a quando il thread di ordinamento è finito, dormendo qua e là e aumentando la barra di avanzamento nel frattempo.

È possibile generalizzare questo approccio non intrusivo a qualsiasi tipo di operazione che richiede tempo senza dover cospargere di chiamate di tipo update_progress_bar() lungo tutto il codice o scavare nelle implementazioni di std :: sort o provare a reinventare le ruote. Poiché il thread principale si troverà in uno stato di barra di stato di attesa/aggiornamento e quindi in un certo senso blocco fino al termine del thread di lavoro, non si avranno problemi associati al multithreading (è necessario che la sincronizzazione dei thread acceda alle risorse condivise durante applicazione ad eccezione del segnalino avanzamento, condizioni di gara, serrature morte ecc.). Sarà anche il contatore di progresso più semplice che puoi implementare poiché verrà aggiornato contemporaneamente.

Se siete preoccupati per l'efficienza con associato con il blocco del contatore di avanzamento, è sufficiente utilizzare le operazioni atomiche ad incrementarlo.

Per quanto riguarda la determinazione quanto l'algoritmo di ordinamento è progredita, ci sono un paio di modi per farlo. Uno è lasciarlo correre una volta con la dimensione dei dati che hai e cercare di prevedere il tempo che ci vorrebbe per le corse successive. Questo è completamente non intrusivo ma un po 'difficile da fare, tuttavia, se fatto bene, monitorerà i progressi in modo più accurato rispetto all'incremento di un contatore a intervalli regolari (che omette il fatto che gli intervalli potrebbero non richiedere anche una quantità di tempo). Il secondo approccio che è più semplice ma un po 'malvagio è quello di modificare il predicato del comparatore per incrementare un contatore di progresso. Realizzare predicati con stato è generalmente disapprovato, ma è meno malvagio che cercare di implementare il proprio introsort solo perché si desidera un contatore di progressi.

Inoltre se il vostro introsort sta prendendo così tanto tempo, mi chiedo, fa il vostro negozio contenitore di questi oggetti triangolo o puntatori a loro? Se il primo, si potrebbe voler considerare quest'ultimo come dovrebbe accelerare le cose drammaticamente.