Algorithmes de tri proches - Quand utiliser?

Question

De temps en temps, je navigue sur le Web et cherche des algorithmes et des infrastructures de données intéressants à mettre dans mon sac à malice. Il y a un an, je suis tombé sur la structure de données Soft Heap et ai appris à connaître le tri proche.

L’idée sous-jacente est qu’il est possible de briser la barrière O (n log n) des tris fondés sur la comparaison si vous pouvez vivre avec le fait que l’algorithme de tri triche un peu. Vous obtenez une liste presque triée mais vous devez aussi vivre avec des erreurs.

J'ai joué avec les algorithmes dans un environnement de test, mais je ne les ai jamais utilisés.

Alors la question: Est-ce que quelqu'un a déjà utilisé le tri proche en pratique? Si oui, dans quel type d'applications? Pouvez-vous imaginer un cas d'utilisation où le tri proche est la bonne chose à faire?

Answer 1

Il y a beaucoup de "gourmands" des heuristiques où vous sélectionnez périodiquement le minimum d'un ensemble. L'heuristique gourmande n'est pas parfaite, alors même si vous choisissez le minimum, vous n'êtes pas assuré d'obtenir la meilleure réponse finale. En fait, dans la méta-heuristique GRASP , vous introduisez intentionnellement des erreurs aléatoires de manière à générer plusieurs erreurs finales. solutions et sélectionnez le meilleur. Dans ce cas, introduire une erreur dans votre routine de tri en échange de rapidité constituerait un bon compromis.

Answer 2

Ceci est une conjecture totale, mais compte tenu de la subjectivité inhérente à la "pertinence". Lors du tri des résultats de recherche, j’oserais dire qu’il importe peu qu’ils soient parfaitement triés ou non. La même chose pourrait être dite pour les recommandations. Si vous pouvez faire en sorte que toutes les autres parties de votre algorithme pour ces choses soient O (n), vous pouvez éviter un tri.

Sachez également que, dans le pire des cas, votre " presque trié " Les données ne ne répondent pas à une idée intuitive possible de "presque triées", à savoir qu'elle ne contient qu'un petit nombre d'inversions. La raison en est simplement que si vos données ne contiennent que des inversions O (n), vous pouvez terminer le tri en un temps O (n) en utilisant un tri par insertion ou un tri à cocktail (c'est-à-dire un tri par bulle bidirectionnelle). Il s'ensuit que vous ne pouvez pas avoir atteint ce point si vous n’êtes pas complètement trié, en temps O (n) (en utilisant des comparaisons). Vous recherchez donc des applications dans lesquelles un sous-ensemble majoritaire de données est trié et le reste dispersé, pas pour des applications nécessitant que chaque élément se trouve à proximité de sa position correcte.

Answer 3

Je ne fais que spéculer, mais j'imagine une chose est l'optimisation des requêtes dans les bases de données.

Une requête dans une base de données dans un langage déclaratif tel que SQL doit être traduite en un programme pas à pas appelé "plan d'exécution". Une requête SQL peut généralement être traduite en un certain nombre de plans d'exécution de ce type, qui donnent tous le même résultat mais peuvent avoir des performances très variables. L’optimiseur de requêtes doit trouver le plus rapide ou au moins raisonnablement rapide.

Les optimiseurs de requêtes basés sur les coûts ont une "fonction de coût", qu'ils utilisent pour estimer la durée d'exécution d'un plan donné. Des optimiseurs exhaustifs passent en revue tous les plans possibles (pour une valeur de "tout possible") et sélectionnent le plus rapide. Pour les requêtes complexes, le nombre de plans possibles peut être prohibitif, ce qui entraîne des temps d'optimisation excessivement longs (avant même de commencer la recherche dans la base de données!). Il existe donc également des optimiseurs non exhaustifs. Ils ne se penchent que sur certains plans, avec peut-être un élément aléatoire pour choisir lesquels. Cela fonctionne, car il y a généralement un grand nombre de "bons" plans, et il n'est peut-être pas si important de trouver le meilleur qui soit - il est probablement préférable de choisir un plan de 5 secondes plutôt que le plan optimal de 2 secondes, si plusieurs minutes d'optimisation sont nécessaires pour trouver le temps de 2 secondes. plan.

Certains algorithmes d'optimisation utilisent une file d'attente triée de "prometteurs". plans (partiels). Si le fait de trouver le plan qui vous convient le mieux n'a pas vraiment d'importance, vous pourriez peut-être utiliser une file d'attente presque triée?

Une autre idée (et je ne fais que spéculer) est un planificateur pour les processus ou les threads dans un système de partage du temps, dans lequel il peut ne pas être important si un processus ou un thread donné obtient son intervalle de temps quelques millisecondes plus tard que si strictement trié par priorité.

Answer 4

Une application courante pour le quasi-tri est lorsqu'un humain effectue la comparaison par paires et que vous ne souhaitez pas lui poser autant de questions.

Supposons que vous ayez de nombreux éléments que vous voudriez qu'un humain trie via une comparaison par paires. Vous pouvez réduire considérablement le nombre de comparaisons dont vous avez besoin si vous êtes prêt à accepter que la commande ne soit pas exacte. Vous pouvez, par exemple, ne pas vous soucier de savoir si les éléments adjacents ont été échangés longtemps, car les éléments préférés sont en haut.

Answer 5

Partout

1. vous êtes censé réagir rapidement,
2. vous ne promettez pas le comportement exact au client,
3. mais en interne, vous avez des règles

vous pouvez l'utiliser. Que diriez-vous de " pas si strict " file d'attente prioritaire basée sur des règles? Où cela serait-il utile? Peut-être que la planification des threads / processus / ressources. Dans la planification de threads / processus, vous ne promettez vraiment pas qu'un seul thread vienne en premier, en second ou en dernier, mais vous voulez généralement donner une chance à chacun. Vous voudrez peut-être appliquer une règle souple afin qu’elle soit préemptive, hiérarchisée, blabla ..

Un exemple de planning de ressources serait de réagir à la livraison de pizzas ou à l’envoi de cartons de livres à des personnes, etc. prévisible.

Answer 6

O (n log n) est déjà assez rapide. Je ne pense pas que quiconque commencerait à utiliser en utilisant un algorithme de tri proche. Vous commenceriez avec un code qui effectue simplement un tri complet (car votre langage de programmation choisi fournit probablement une fonction tri et non une fonction nearsort ), et lorsque vous avez trouvé des informations empiriques. que le tri prenait trop de temps, vous pourriez vous demander si vos données vraiment doivent être entièrement triées et envisagez d'utiliser un tri proche.

En gros, vous n’envisagez même jamais d’utiliser un tri proche, à moins que vous ne découvriez au préalable que le tri est un goulot d’étranglement important dans votre programme.