Algorithmes de tri pour les données de statistique de la distribution?

Question

Il vient de se produire pour moi, si vous savez quelque chose à propos de la distribution (au sens statistique) de données à trier, la performance d'un algorithme de tri qui pourraient en bénéficier si vous tenir compte de ces informations.

Donc ma question est, existe-il des algorithmes de tri qui prennent en compte ce genre d'information? Comment sont-elles bonnes?

Edit : un exemple pour clarifier: si vous connaissez la distribution de vos données à Gaussien, vous pouvez estimer la moyenne et moyenne à la volée comme vous traiter les données. Ce serait vous donner une estimation de la position finale de chaque numéro, ce qui permet de les placer à proximité de leur position finale.

Edit #2: je suis assez surpris de la réponse n'est pas un lien wiki vers un exhaustives à la page de discuter de cette question. N'est-ce pas un cas très commun (le cas Gaussien, par exemple)?

Edit #3: je suis l'ajout d'une prime à cette question, parce que je suis à la recherche de réponses définitives avec les sources, pas de la spéculation. Quelque chose comme "dans le cas de la gaussienne de données distribuées, XYZ est l'algorithme le plus rapide en moyenne, comme l'a prouvé par Smith et coll. [1]". Cependant, toute information complémentaire est la bienvenue.

Note: je vais d'attribution de la prime à la plus haute a voté réponse. Vote à bon escient!

Answer 1

Si les données de tri a une distribution connue, je voudrais utiliser un Seau de Tri algorithme. Vous pourriez ajouter un peu de logique supplémentaire pour elle alors que vous avez calculé la taille et/ou les positions des différents seaux basée sur les propriétés de la distribution (ex: pour Gaussien, vous pourriez avoir un seau à chaque (sigma/k) à l'abri de la moyenne, où sigma est l'écart type de la distribution).

En ayant une aire de répartition connue et la modification de la norme Seau algorithme de Tri de cette façon, vous auriez probablement obtenir l' Histogramme de Tri algorithme ou quelque chose d'approchant. Bien sûr, votre algorithme serait de calcul plus rapide que l'Histogramme de l'algorithme de Tri, car il y aurait probablement pas besoin de faire la première passe (décrit dans le lien) puisque vous connaissez déjà la distribution.

Edit: compte tenu des nouveaux critères de votre question, (si ma réponse précédente concernant l'Histogramme de Tri des liens vers la respectable NIST et contient de l'information sur le rendement), voici un examen par les pairs des articles de revue de la Conférence Internationale sur le Traitement en Parallèle:

Adaptative Partition de Données pour le Tri à l'Aide de la Probabilité de Distribution

Les auteurs affirment cet algorithme a un meilleur rendement (jusqu'à 30% de mieux) que les populaire de Tri Rapide de l'Algorithme.

Answer 2

On dirait que vous voudrez peut-être lire l'Auto-Amélioration des Algorithmes: ils réalisent une éventuelle optimale devrait courir de temps pour arbitraire d'entrée distributions.

Nous donnons à ces auto-amélioration des algorithmes pour les deux problèmes: (i) le tri des séquence de chiffres et de (ii) le calcul de la triangulation de Delaunay d'un plan de jeu de points. Les deux algorithmes atteindre optimale devrait limiter la complexité. Les algorithmes de commencer par une formation phase au cours de laquelle ils recueillent informations sur les données en entrée de distribution, suivi par un stationnaire régime dans lequel les algorithmes de régler à leur optimisé incarnations.

Si vous connaissez déjà votre entrée de distribution est approximativement Gaussienne, alors peut-être une autre approche serait plus efficace en termes d'espace que de la complexité, mais en termes de temps de course c'est plutôt un résultat merveilleux.

Answer 3

Sachant que la source de données de distribution, on peut construire une bonne fonction de hachage. La connaissance de la répartition ainsi, la fonction de hachage peut s'avérer être un parfait fonction de hachage, ou proche de la perfection pour de nombreux vecteurs en entrée.

Une telle fonction serait de diviser une entrée de taille n en n de bacs, de telle sorte que le plus petit élément de la carte dans le 1er bin, et le plus grand élément de la carte à la dernière cellule. Lorsque la valeur de hachage est parfait - nous permettrait d'atteindre une sorte juste être l'insertion de tous les articles dans les bacs.

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

Je voudrais utiliser un tableau de tas de fibonacci à mettre en œuvre la table de hachage.

Pour un vecteur d'entrée pour laquelle la fonction de hachage ne sera pas parfait (mais tout de même proche de la perfection), il serait encore beaucoup mieux que O(nlogn). Quand il est parfait il serait O(n). Je ne suis pas sûr de la façon de calculer la moyenne de la complexité, mais s'il fallait, je serais prêt à parier sur O(nloglogn).

Answer 4

Ordinateur algorithmes de tri peuvent être classés en deux catégories, comparaison de tri et de non-comparaison de tri. Pour comparaison le tri, le tri de temps dans son meilleur des cas, la performance est Ω (nlogn), tandis que dans ses pires performances de l' le tri de temps peut s'élever jusqu'à O(n2 ). Au cours des dernières années, certains amélioré les algorithmes ont été proposés pour accélérer comparaison basée sur le tri, comme la technologie avancée tri rapide selon les données de distribution de caractéristiques . Cependant, la moyenne de tri de temps pour que ces algorithmes est juste Ω (nlog2n), et que dans le meilleur des cas, peut-il atteindre O(n). Différente de la comparaison de tri, non-comparaison de tri tels que le comte de tri, seau de tri et tri radix dépend principalement de la clé et adresse de calcul. Lorsque les valeurs de clés sont finis allant de 1 à m, le calcul de l' la complexité de la non-comparaison de tri est O(m+n). En particulier, lorsque m=O(n), le tri de temps peut atteindre O(n). Toutefois, lorsque m=n2, n3, ...., l' la limite supérieure de tri linéaire du temps ne peut pas être obtenu. Parmi les non-comparaison de tri, seau tri distribue un groupe d'enregistrements avec les mêmes clés dans le approprié "seau", puis un autre algorithme de tri est appliquée aux documents dans chaque seau. Avec seau le tri, la partition de dossiers en m seaux est moins beaucoup de temps, alors que seuls quelques dossiers seront contenues dans chaque seau de sorte que le "nettoyage de tri" l'algorithme peut être appliqué très rapide. Par conséquent, seau de tri a le potentiel pour asymptotiquement enregistrer le tri de temps par rapport à Ω (nlogn) des algorithmes. Évidemment, la façon de distribuer uniformément tous les enregistrements dans seaux joue un rôle essentiel dans le seau de tri. Par conséquent, ce que vous avez besoin est une méthode pour construire une fonction de hachage selon les données de la distribution, qui est utilisé pour distribuer uniformément les enregistrements n en n seaux basé sur la clé de chaque enregistrement. Par conséquent, le tri moment de l' proposé seau algorithme de tri atteindra O(n) en toute circonstance.

vérifiez le présent document: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5170434&tag=1

Answer 5

Seau de tri serait de vous donner un temps linéaire algorithme de tri, aussi longtemps que vous pouvez calculer le CDF de chaque point dans le O(1) fois.

L'algorithme, que vous pouvez également regarder ailleurs, est comme suit:

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) tels que x et y de l'automne dans le même seau, et le temps d'exécution de l'insertion, le tri est précisément en O(n + # paires dans le même seau). L'analyse est similaire à celle de FKS statique parfait de hachage.

EDIT: Si vous ne connaissez pas la distribution, mais vous savez à quelle famille il appartient, vous pouvez l'estimation de la distribution en O(n), dans le cas Gaussien par le calcul de la moyenne et de la variance, et ensuite utiliser le même algorithme (d'ailleurs, le calcul de la cdf dans ce cas est non trivial).