Comment surveiller/afficher la progression pendant un tri C++

Question

Je prévois d'écrire un plug-in interactif de traitement de géométrie C++ qui triera fréquemment de grandes quantités de données. Bien que les indications préliminaires indiquent que le tri ne prendra qu'une seconde ou deux, je préférerais montrer des progrès pendant cette période - c'est-à-dire que je voudrais mettre à jour un indicateur de progression plusieurs fois par seconde. Cela serait préférable d'allumer un curseur d'attente et de laisser l'utilisateur avec un programme qui se fige pendant une durée indéterminée (même s'il ne s'agit que de quelques secondes). Si j'utilisais quelque chose comme std :: sort, je pourrais utiliser la fonction de comparaison pour mettre à jour l'indicateur de progression de temps en temps, mais je n'aurais aucune idée de 'pourcentage terminé'. Je pourrais aussi décomposer le tri en sous-sortes, en mettant à jour la progression entre les sous-sortes, puis en fusionnant. Mon meilleur pari peut être d'écrire sa propre méthode de tri, bien que je ne sache pas combien d'effort il faudrait pour obtenir une performance aussi bonne que std :: sort (et assurer la correction). Dans tous les cas, cette méthode de tri envoie parfois un "pourcentage complet" à une méthode de rappel. Je me demandais si d'autres personnes avaient rencontré et résolu ce problème - j'espère qu'il y a peut-être une méthode de tri dans une bibliothèque standard qui fait ce que je veux, ou une autre technique à laquelle je n'ai pas pensé.

Mise à jour: Merci pour les bonnes réponses jusqu'à présent. Il y a eu quelques très bonnes suggestions, et je vais arrêter de choisir la réponse acceptée jusqu'à ce que j'aie eu la chance de tester les idées dans mon projet à venir.

Mise à jour 2: J'ai terminé mon projet, et cela s'est avéré être un non-problème (au moins pour le client.) Étant donné qu'ils vendront le logiciel, ils recevront peut-être des commentaires de leurs clients. leurs esprits à ce sujet). Choisir une réponse acceptée était difficile parce qu'il y avait beaucoup de bonnes réponses, mais à la fin, celui que j'ai choisi indiquait un article wiki sur Merge Sort qui avait une animation très évocatrice. Donc, c'est la première stratégie que j'aurais poursuivie si j'avais eu besoin d'aller de l'avant avec ça).

Answer 1

Comme std :: sort est basé sur un modèle, la source doit être disponible dans un en-tête. Vous pouvez en faire une copie et insérer votre rappel de progression. Le gros problème sera de prédire à quel point vous êtes proche de l'achèvement - la plupart des fonctions de tri seront basées sur Quicksort, qui ne fait pas toujours le même nombre de comparaisons.

Écrire votre propre Merge sort serait une possibilité; l'algorithme est facile et le nombre d'étapes est bien défini.

Answer 2

Je recommanderais votre deuxième option: utiliser std::sort ou une autre fonction de tri standard comme qsort, et faire en sorte que le comparateur signale sa progression. Mais ne pas mettre à jour dans toutes les comparaisons - ce serait insupportablement lente - au lieu de mettre à jour tous les (disons) 100ms.

Answer 3

Utilisez le observer pattern pour renvoyer le parent à la fin de chaque partie. En utilisant cela et le nombre total d'éléments qui ont besoin de tri, vous pouvez mettre à jour votre barre de progression en temps réel.

Answer 4

Je pense, même si vous avez écrit votre propre sorte, que vous auriez à faire beaucoup de mesure prudente si vous vouliez que l'indicateur de progression soit précis. Si vous voulez seulement un indicateur de progression approximatif, vous pouvez utiliser comme indicateur votre «mesure de la distance moyenne entre les éléments comparés» ou «nombre de comparaisons comparé au nombre moyen attendu pour le tri rapide» et implémenter l'idée de comparaison déjà mentionnée.

Et oui, je suppose que vous n'êtes pas un idiot complet et ne prévoyez pas de mettre à jour l'indicateur de progression à chaque comparaison. Si vous faisiez cela, vous passeriez beaucoup plus de temps à indiquer le progrès qu'à trier.

A titre d'exemple, vous attendez généralement environ n log2 n opérations pour le tri rapide. L'analyse du nombre de comparaisons est plus détaillée et peut être plus précise que cette mesure générale, mais pour les besoins de cet exemple, supposons simplement. Vous pouvez donc compter les comparaisons et déclarer number_of_comparisons/(n log2 n) comme estimation de vos progrès.Comme c'est juste un indicateur de moyenne, je voudrais faire quelques expériences et voir à quel point votre estimation est éteinte, et jeter quelques facteurs de fudge pour le faire correspondre à la moyenne des cas attendus. Vous pourriez également avoir une barre de progression qui indique l'incertitude en ayant une sorte de «C'est où je pense que je vais avoir terminé." indicateur et de l'espace après l'indicateur.

Même si vous avez utilisé votre propre tri et que vous avez trouvé une mesure plus précise, la barre de progression ne se mettrait pas à jour correctement et l'effet serait similaire. La seule façon dont vous savez avec certitude combien de temps votre tri va prendre est si vous utilisez une sorte un peu plus lente, mais vraiment prévisible, auquel cas vous pouvez prédire combien de temps cela prendra du nombre d'éléments, ou utiliser un très rapide un tri qui a un comportement moins prévisible dans des cas spécifiques, auquel cas il n'y a pas de véritable moyen d'avoir une barre de progression parfaitement précise.

La prévisibilité des sous-tâches et la prévisibilité du nombre total de comparaisons sont fortement liées. Donc, je ne pense vraiment pas que les sous-tâches font une meilleure mesure que le nombre total de comparaisons.

Si vous souhaitez utiliser votre propre tri et la prévisibilité est votre objectif le plus élevé, optez pour heapsort. C'est toujours un tri O(n log2 n), et c'est presque un genre de comparaison minimum (ou je me souviens d'avoir lu Knuth). Il faut aussi une quantité de temps très prévisible pour compléter quel que soit le jeu de données qu'il nourrit. C'est l'un des plus lents O(n log2 n), mais quand même.

Comme l'a mentionné un de vos commentateurs, vous résolvez peut-être un problème qui n'existe pas réellement. Faites quelques expériences en premier. Le problème est un défi intellectuel amusant, peu importe son utilité. :-)

Answer 5

Je vois votre problème comme suit:

1. Vous voulez des événements discrets à feu au cours d'un seul processus continu.
2. Cette sous-division est juste pour dire à l'utilisateur que les choses sont en cours.

Mes suggestions:

1. Utilisez une icône de chargement de quelque chose comme http://ajaxload.info/, ou si elle pas un environnement basé sur IUG, juste préciser le chargement. Puisque l'événement est inférieur à 2 secondes, cela ne posera aucun problème. Les raccrocs sont attendus si le temps d'attente dépasse 10 secondes. L'écriture de votre propre méthode de tri génère de nombreux problèmes de sécurité des threads, ce qui peut poser problème si votre code utilise le multithreading ou qu'il le fera à l'avenir.

3.Another informations importantes que vous devriez considérer à quel point de l'ordre les données seront chaque fois que vous voulez trier, donc en effet que vous serez mesurer le degré de caractère aléatoire présent, et le nombre prévu de calculs que vous pourriez avoir besoin de faire. Vous pouvez utiliser cette information comme un indicateur du nombre de swaps requis, lesquels peuvent être pris en compte au fur et à mesure que vous parcourez le tri. Jouez avec les données.

Answer 6

utilisation force brute :)

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 

(au cas où vous ne voulez pas implémenter votre propre std :: sort() et depuis que je suis manque exigences complètes)

Answer 7

Je ne Je recommande de tenter de bidouiller std :: sort. Cela est généralement implémenté avec introsort et est une opération NLogN extrêmement rapide. Construire le conteneur que vous allez trier sera généralement plus coûteux que de trier les données. Cependant, si vous voulez implémenter une barre de progression, je vous recommande de placer le tri dans un fil séparé. Normalement, les applications multithread sont plus difficiles à écrire et à maintenir que les applications monothread, mais vous pouvez le faire d'une manière qui n'est pas dans cette barre de progression. Votre application peut toujours être principalement monothread sans qu'aucune opération simultanée ne soit effectuée à l'exception de cette barre de progression et probablement une certaine gestion d'événement pour que l'interface utilisateur reste réactive. Lorsque vous êtes prêt à trier les données, lancez simplement un autre thread pour le faire et placez le thread principal dans une boucle d'attente jusqu'à ce que le thread de tri soit terminé, dormez ici et là et mettez à jour la barre de progression. Vous pouvez généraliser cette approche non intrusive à n'importe quel type d'opération qui prend du temps sans avoir à saupoudrer les appels de type update_progress_bar() dans votre code ou à creuser dans les implémentations de std :: sort ou à essayer de réinventer les roues. Parce que le thread principal sera dans un état de barre de progression en attente/mise à jour et donc bloquant dans un sens jusqu'à ce que votre thread de travail soit terminé, vous n'avez aucun des problèmes associés au multithreading (besoin de synchronisation de threads pour accéder aux ressources partagées). application à l'exception du compteur de progression, conditions de course, serrures mortes, etc.). Il s'agira également du plus simple compteur de progression que vous pourrez mettre en œuvre, car il sera mis à jour simultanément.

Si vous êtes préoccupé par l'efficacité associée au verrouillage du compteur de progression, utilisez simplement les opérations atomiques pour l'incrémenter. Pour déterminer à quel point l'algorithme de tri a progressé, il existe deux façons de le faire. La première consiste à le laisser s'exécuter une fois avec la taille des données dont vous disposez et à essayer de prédire le temps nécessaire pour les exécutions suivantes. C'est complètement non intrusif mais un peu difficile à faire, mais s'il est bien fait, il surveillera le progrès plus précisément que l'incrémentation d'un compteur à intervalles réguliers (ce qui omet le fait que les intervalles ne prennent même pas beaucoup de temps). La deuxième approche qui est plus simple mais un peu mauvaise consiste à modifier votre prédicat de comparateur pour incrémenter un compteur de progression. Faire des prédicats avec l'état est généralement mal vu, mais c'est moins mal que d'essayer d'implémenter votre propre introsort juste parce que vous voulez un compteur de progression.

De plus, si votre introsort prend tellement de temps, je me demande si votre conteneur contient ces objets triangulaires ou ces pointeurs. Si le premier, vous pourriez vouloir considérer le dernier comme il devrait accélérer les choses dramatiquement.