Algorithmes de sorting pour les données de dissortingbution statistique connue?

Il me semble que si vous connaissez la dissortingbution (au sens statistique) des données à sortinger, les performances d’un algorithme de sorting pourraient être utiles si vous teniez compte de ces informations.

Donc, ma question est la suivante: existe-t-il des algorithmes de sorting qui prennent en compte ce type d’informations? Comment sont-ils?

Edit: un exemple pour clarifier: si vous connaissez la dissortingbution de vos données pour être gaussienne, vous pouvez estimer la moyenne et la moyenne à la volée lorsque vous traitez les données. Cela vous donnerait une estimation de la position finale de chaque nombre, que vous pourriez utiliser pour les placer près de leur position finale.

Edit # 2: Je suis assez surpris que la réponse ne soit pas un lien wiki vers une page thourough traitant de ce problème. N’est-ce pas un cas très courant (le cas gaussien, par exemple)?

Edit # 3: J’ajoute une prime à cette question, car je cherche des réponses précises avec des sources, pas des spéculations. Quelque chose comme “dans le cas de données dissortingbuées gaussiennes, l’algorithme XYZ est le plus rapide en moyenne, comme l’a prouvé Smith et al. [1]”. Cependant, toute information supplémentaire est la bienvenue.

Note : je vais atsortingbuer la prime à la réponse la plus votée. Votez avec sagesse!

Si les données que vous sortingez ont une dissortingbution connue, j’utiliserais un algorithme de sorting par Bucket . Vous pourriez append un peu de logique supplémentaire pour que vous ayez calculé la taille et / ou les positions des différents compartiments en fonction des propriétés de la dissortingbution (ex: pour Gaussian, vous pourriez avoir un seau chaque (sigma / k) loin de la moyenne). où sigma est l’écart type de la dissortingbution).

En ayant une dissortingbution connue et en modifiant de cette manière l’algorithme standard de Bucket Sort, vous obtiendrez probablement l’algorithme de sorting d’histogramme ou quelque chose de proche. Bien sûr, votre algorithme serait plus rapide que l’algorithme de sorting par histogramme, car il ne serait probablement pas nécessaire d’effectuer le premier passage (décrit dans le lien) puisque vous connaissez déjà la dissortingbution.

Edit: étant donné vos nouveaux critères de votre question (bien que ma réponse précédente concernant Histogram Trier fasse le lien avec le NIST respectable et contienne des informations sur les performances), voici un article de revue par les pairs de la Conférence internationale sur le parallel processing:

Partition de données adaptative pour le sorting à l’aide de la dissortingbution de probabilités

Les auteurs affirment que cet algorithme a de meilleures performances (jusqu’à 30% de mieux) que le populaire algorithme de sorting rapide.

Il semblerait que vous souhaitiez lire des algorithmes auto-améliorés : ils permettent d’obtenir une durée d’exécution optimale optimale pour les dissortingbutions d’entrées arbitraires .

Nous donnons de tels algorithmes auto-améliorants pour deux problèmes: (i) le sorting d’une séquence de nombres et (ii) le calcul de la sortingangulation de Delaunay d’un ensemble de points planaires. Les deux algorithmes atteignent la complexité de limitation attendue optimale. Les algorithmes commencent par une phase d’apprentissage au cours de laquelle ils collectent des informations sur la dissortingbution des entrées, suivies d’un régime stationnaire dans lequel les algorithmes se contentent de leurs incarnations optimisées.

Si vous savez déjà que votre dissortingbution en entrée est approximativement gaussienne, alors une autre approche serait peut-être plus efficace en termes de complexité de l’espace, mais en termes de temps d’exécution attendu, c’est un résultat plutôt merveilleux.

Connaissant la dissortingbution de la source de données, on peut créer une bonne fonction de hachage. Connaissant bien la dissortingbution, la fonction de hachage peut s’avérer être une fonction de hachage parfaite, ou proche de la perfection pour de nombreux vecteurs d’entrée.

Une telle fonction diviserait une entrée de taille n en n poubelles, de sorte que le plus petit élément mapperait dans la première poubelle et que l’élément le plus grand serait placé dans la dernière poubelle. Lorsque le hachage est parfait, nous réussirions simplement à insérer tous les éléments dans les bacs.

Insérer tous les éléments dans une table de hachage, puis les extraire par ordre sera O (n) lorsque le hachage est parfait (en supposant que le coût de calcul de la fonction de hachage est O (1) et que les opérations de structure de données de hachage sont O (1) ).

J’utiliserais un tableau de tas de fibonacci pour implémenter la table de hachage.

Pour un vecteur d’entrée pour lequel la fonction de hachage ne serait pas parfaite (mais toujours proche de la perfection), ce serait encore bien mieux que O (nlogn). Quand il est parfait – ce serait O (n). Je ne sais pas comment calculer la complexité moyenne, mais si je suis forcé de le faire, je parierais sur O (nloglogn).

Les algorithmes de sorting informatique peuvent être classés en deux catégories, le sorting basé sur la comparaison et le sorting non basé sur la comparaison. Pour le sorting basé sur la comparaison, le temps de sorting dans sa meilleure performance est Ω (nlogn), tandis que dans le pire des cas, le temps de sorting peut atteindre O (n2). Ces dernières années, certains algorithmes améliorés ont été proposés pour accélérer le sorting basé sur des comparaisons, tels que le sorting rapide rapide en fonction des caractéristiques de dissortingbution des données. Cependant, le temps de sorting moyen de ces algorithmes est juste Ω (nlog2n), et seulement dans le meilleur des cas, il peut atteindre O (n). Contrairement au sorting basé sur la comparaison, le sorting non basé sur la comparaison, tel que le sorting par comptage, le sorting par godet et le sorting par radix, dépend principalement du calcul des clés et des adresses. Lorsque les valeurs des clés sont finies allant de 1 à m, la complexité de calcul du sorting non fondé sur la comparaison est O (m + n). En particulier, lorsque m = O (n), le temps de sorting peut atteindre O (n). Cependant, lorsque m = n2, n3,…., La limite supérieure du temps de sorting linéaire ne peut pas être obtenue. En ce qui concerne le sorting non fondé sur des comparaisons, le sorting par compartiment dissortingbue un groupe d’enregistrements avec des clés similaires dans le «compartiment» approprié, puis un autre algorithme de sorting est appliqué aux enregistrements de chaque compartiment. Avec le sorting dans les compartiments, la partition des enregistrements en m godets prend moins de temps, alors que seuls quelques enregistrements seront contenus dans chaque compartiment afin que l’algorithme de «sorting du nettoyage» puisse être appliqué très rapidement. Par conséquent, le sorting par godet a le potentiel de réduire le temps de sorting de manière asymptotique par rapport aux algorithmes Ω (nlogn). De toute évidence, la répartition uniforme de tous les enregistrements dans des compartiments joue un rôle essentiel dans le sorting des seaux. Par conséquent, vous avez besoin d’une méthode pour construire une fonction de hachage en fonction de la dissortingbution des données, qui est utilisée pour dissortingbuer uniformément n enregistrements dans n compartiments basés sur la clé de chaque enregistrement. Par conséquent, le temps de sorting de l’algorithme de sorting par godet proposé atteindra O (n) en toute circonstance.

Vérifiez cet article: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5170434&tag=1

Le type de seau vous donnerait un algorithme de sorting du temps linéaire, du moment que vous pouvez calculer le CDF de chaque point dans le temps O (1).

L’algorithme, que vous pouvez également consulter ailleurs, est le suivant:

a = array(0, n - 1, []) // create an empty list for each bucket for x in input: a[floor(n * cdf(x))].append(x) // O(1) time for each x input.clear() for i in {0,...,n - 1}: // this sorting step costs O(|a[i]|^2) time for each bucket // but most buckets are small and the cost is O(1) per bucket in expectation insertion_sort(a[i]) input.concatenate(a[i]) 

Le temps d’exécution est O (n) dans l’attente car dans l’attente il y a O (n) paires (x, y) telles que x et y tombent dans le même compartiment, et le temps d’exécution du sorting par insertion est précisément O (n + # paires dans le même seau). L’parsing est similaire à celle du hachage statique parfait de FKS .

EDIT: Si vous ne connaissez pas la dissortingbution, mais vous savez de quelle famille il s’agit, vous pouvez juste estimer la dissortingbution dans O (n), dans le cas gaussien en calculant la moyenne et la variance, puis utiliser le même algorithme (accessoirement , calculer le cdf dans ce cas est non sortingvial).

Vous pouvez utiliser cette information dans un sorting rapide pour sélectionner la valeur de pivot. Je pense que cela améliorerait la probabilité que l’algorithme rest éloigné de la complexité du pire cas de O (N ** 2).

Je pense que le sorting par cycle entre dans cette catégorie. Vous l’utilisez lorsque vous connaissez la position exacte à laquelle vous voulez que chaque élément se retrouve.

Cyclesort a quelques propriétés intéressantes – pour certains types de données restreints, il peut faire un sorting stable sur place en temps linéaire, tout en garantissant que chaque élément sera déplacé au maximum une fois.