J'ai 9 valeurs sous la forme d'une matrice et j'ai besoin de calculer la médiane à partir de ces valeurs dans le cadre d'un processus de simulation.le tri rapide en C++ est lent
J'utilise le tri rapide en C++ (c'est-à-dire qsort()) ce qui fait que le processus est lent (car ce processus itère plusieurs fois).
Existe-t-il un meilleur algorithme de tri que je pourrais utiliser?
tri pour obtenir une médiane est très inefficace vous pouvez utiliser STL nth_element à la place..
#include <algorithm>
// Assuming you keep the elements in a vector v of size len
std::nth_element(v.begin(), v.begin()+len/2, v.end());
median = v[len/2];
//... or, if the elements are in a simple array v[len], then
std::nth_element(v, v+len/2, v+len);
median = v[len/2];
note: le nth_element modifiera le vecteur/tableau v. Faire ac opy d'abord si vous devez conserver l'original.
insertion Trier ..
Sur les petits ensembles de données, vous pouvez utiliser différents algorithmes pour obtenir des performances optimales. QuickSort brille une fois que l'ensemble de données se développe.
Il existe différentes approches. Vous pouvez utiliser des structures de données dans lesquelles vous triez sur insert, et il existe des zones où vous triez l'ensemble de données complet. Vous avez juste besoin de trouver votre algorithme optimal.
Le tri par insertion devrait être un peu plus rapide sur des données aléatoires, n'est-ce pas? –
En fait, certains tris rapides utiliseront automatiquement le tri par sélection lorsque les tailles des partitions ou de la liste deviennent très petites. –
@Jeremy Peut-être que c'était le genre d'insertion ... –
Comme on le mentionne, il n'est pas nécessaire de trier complètement pour obtenir une médiane. STL a trier algorithme qui peut habituellement effectuer une comparaison. Il a également un algorithme plus intelligent que garanti par qsort, avec worstcase de O (NlgN).
Salut, Merci. Donc, je n'ai pas besoin de trier complètement pour obtenir la médiane? Dans ce cas, y a-t-il un meilleur moyen d'obtenir le résultat? Merci. –
RE point 2: a probablement un compromis dans l'espace, cependant. (comme le tri des arbres binaires) –
@Bi: Il existe un algorithme linéaire pour la médiane - voir le lien sur le commentaire onebyone. – EFraim
Seulement 9 valeurs? Quicksort est exagéré. Il est possible que vous utilisiez un tri par insertion, un tri à bulles ou d'autres algorithmes de tri plus simples lorsque vous travaillez avec des ensembles de données plus petits.
Performance
genre Bubble a le pire des cas et la complexité moyenne à la fois О (n²), où n est le nombre d'éléments à trier. Il existe de nombreux algorithmes de tri avec la complexité du pire cas ou de la complexité moyenne de O (n log n). Même les autres algorithmes de tri О (n²), tels que le tri par insertion, ont tendance à avoir de meilleures performances que le tri à bulles. Par conséquent, le tri des bulles n'est pas un algorithme de tri pratique lorsque n est grand.
Cependant, accordé, vous n'avez même pas eu à trier pour obtenir la médiane comme d'autres l'ont suggéré.
L'utilisation de quicksort pour seulement 9 valeurs sera plutôt inefficace. Pour une taille d'échantillon aussi petite, il vaut mieux utiliser un tri par sélection ou un tri par remplacement ... il y a très peu de frais généraux dans ces méthodes de tri.
Quicksort et Mergesort brillent vraiment une fois que votre taille d'échantillon atteint un seuil, peut-être 50+.
Dans ces situations, j'écrirais mon propre code plutôt que d'utiliser une fonction intégrée.
S'il vous plaît s'il vous plaît s'il vous plaît ne recommandez jamais trier bulle sauf aux masochistes!
Pour les petites valeurs, insertion le tri est le meilleur, et c'est bon pour d'autres applications (données presque triées de n'importe quelle longueur). Editer: mise en forme nettoyée, en soulignant la réponse suggérée.
Je connaissais un professeur qui avait l'habitude de gérer une grande équipe de développement d'une société de logiciels que tout le monde connaît. Il nous dit qu'il a dû faire un voyage en Australie pour régler les problèmes de performance d'un client, et quand il est arrivé, il y avait une sorte de bulle avec des commentaires «devrait éventuellement changer pour quelque chose de mieux». Il a dit qu'il avait viré le gars ce jour-là pour avoir coûté des milliers de dollars à l'entreprise. –
@jeremy - Je pense que le manager et QA auraient dû être virés - pas le développeur ... – Tim
@time Ouais, je suis d'accord. Mais au moins, c'est suffisamment dissuasif pour savoir qu'il y a des gens qui pourraient vous tirer d'avoir écrit ça. –
Vous n'avez pas assez de valeurs pour travailler avec Quicksort et vous devez utiliser des algorithmes moins avancés (ex: tri Bubble, tri par insertion, ... explanation here
Il y a un coût associé à la configuration de Quicksort et quand. vous n'avez pas assez de valeurs, il est inutile d'utiliser cette bête
Appeler Quicksort une bête est ... Euh ... je ne sais pas. L'algorithme One-Liner ne peut pas être une bête. – EFraim
Err, la seule chose que je reçois quand je google "un tri rapide" est une tonne de hits Haskell (et cette question: P). Pouvez-vous me donner un tri simple en C++? :) –
L'algorithme std :: sort() est presque toujours préférable à qsort(). Il est généralement plus facile à utiliser et s'exécute plus rapidement.
Si vous voulez entrer dans les détails, il existe une famille d'algorithmes de tri. Stroustrup écrit dans Le langage de programmation C++ que std :: sort n'est souvent pas la bonne chose à utiliser. Dans ce cas, std :: nth_element() est probablement ce que vous voulez.
Vous n'avez pas besoin de trier complètement les valeurs pour trouver la médiane: http://en.wikipedia.org/wiki/Selection_algorithm –
Donc, vous pensez que std :: sort fonctionnerait mieux. Ma taille de l'échantillon est soit 9 ou 30.Merci. –
Comme c'est bizarre. Je suis intrigué par ce que les jeux de données sont toujours 9 et 30. :) Désolé, je suis curieux. –