Je pensais aux algorithmes de tri dans les logiciels et aux moyens possibles de surmonter l' O(nlogn)obstacle. Je ne pense pas qu'il soit possible de trier plus rapidement dans un sens pratique, alors ne pensez pas que je le fasse.

Cela dit, il semble qu'avec presque tous les algorithmes de tri, le logiciel doit connaître la position de chaque élément. Ce qui a du sens, sinon comment saurait-il où placer chaque élément selon certains critères de tri?

Mais quand j'ai croisé cette pensée avec le monde réel, une centrifugeuse n'a aucune idée de la position de chaque molécule lorsqu'elle «trie» les molécules par densité. En fait, il ne se soucie pas de la position de chaque molécule. Cependant, il peut trier des milliards et des milliards d'articles dans un laps de temps relativement court, en raison du fait que chaque molécule suit les lois de densité et de gravitation - ce qui m'a fait réfléchir.

Serait-il possible avec une certaine surcharge sur chaque nœud (une valeur ou une méthode attachée à chacun des nœuds) de «forcer» l'ordre de la liste? Quelque chose comme une centrifugeuse, où seul chaque élément se soucie de sa position relative dans l'espace (par rapport aux autres nœuds). Ou est-ce que cela viole une règle de calcul?

Je pense que l'un des grands points soulevés ici est les effets de la mécanique quantique de la nature et la façon dont ils s'appliquent en parallèle à toutes les particules simultanément.

Peut-être que les ordinateurs classiques restreignent intrinsèquement le tri au domaine de O(nlogn), où les ordinateurs quantiques peuvent être capables de franchir ce seuil en O(logn)algorithmes agissant en parallèle.

Le fait qu'une centrifugeuse soit essentiellement un tri à bulles parallèle semble être correct, ce qui a une complexité temporelle de O(n).

Je suppose que la prochaine pensée est que si la nature peut trier O(n), pourquoi pas les ordinateurs?

EDIT: J'avais mal compris le mécanisme d'une centrifugeuse et il semble qu'il fasse une comparaison, une comparaison massivement parallèle à cela. Cependant, il existe des processus physiques qui opèrent sur une propriété de l'entité en cours de tri plutôt que de comparer deux propriétés. Cette réponse couvre les algorithmes de cette nature.

Une centrifugeuse applique un mécanisme de tri qui ne fonctionne pas vraiment au moyen de comparaisons entre éléments, mais en fait par une propriété («force centrifuge») sur chaque élément individuel de manière isolée. Certains algorithmes de tri entrent dans ce thème, en particulier Radix Sort . Lorsque cet algorithme de tri est parallélisé, il devrait s'approcher de l'exemple d'une centrifugeuse.

Certains autres algorithmes de tri non comparatifs sont le tri par compartiment et le tri par comptage . Vous constaterez peut-être que le tri Bucket s'inscrit également dans l'idée générale d'une centrifugeuse (le rayon peut correspondre à un bac).

Un autre «algorithme de tri» où chaque élément est considéré isolément est le tri de sommeil . Ici, le temps plutôt que la force centrifuge agit comme la grandeur utilisée pour le tri.

La complexité de calcul est toujours définie par rapport à un modèle de calcul. Par exemple, un algorithme qui est O ( n ) sur un ordinateur typique peut être O (2 ⁿ ) s'il est implémenté dans Brainfuck .

Le modèle de calcul de la centrifugeuse a des propriétés intéressantes; par exemple:

• il prend en charge le parallélisme arbitraire; peu importe le nombre de particules dans la solution, elles peuvent toutes être triées simultanément.
• il ne donne pas une sorte linéaire stricte de particules en masse, mais plutôt une approximation très proche (basse énergie).
• il n'est pas possible d'examiner les particules individuelles dans le résultat.
• il n'est pas possible de trier les particules selon différentes propriétés; seule la masse est prise en charge.

Étant donné que nous n'avons pas la capacité d'implémenter quelque chose comme ça dans du matériel informatique à usage général, le modèle peut ne pas avoir de pertinence pratique; mais cela peut encore valoir la peine d'être examiné, pour voir s'il y a quelque chose à en tirer. Les algorithmes non déterministes et les algorithmes quantiques ont tous deux été des domaines de recherche actifs, par exemple, même si aucun n'est réellement implémentable aujourd'hui.

L'astuce est là, que vous n'avez qu'une probabilité de trier votre liste à l'aide d'une centrifugeuse. Comme avec les autres sortes du monde réel [citation nécessaire], vous pouvez changer la probabilité que vous ayez trié votre liste, mais ne soyez jamais certain sans vérifier toutes les valeurs (atomes).

Considérez la question: "Pendant combien de temps devez-vous faire fonctionner votre centrifugeuse?"
Si vous ne l'avez exécuté que pendant une picoseconde, votre échantillon peut être moins trié que l'état initial. Ou si vous l'avez exécuté pendant quelques jours, il peut être complètement trié. Cependant, vous ne le sauriez pas sans en vérifier le contenu.

Un exemple réel de "commande" basée sur ordinateur serait les drones autonomes qui fonctionnent en coopération les uns avec les autres, appelés "essaims de drones". Les drones agissent et communiquent à la fois en tant qu'individus et en tant que groupe, et peuvent suivre plusieurs cibles. Les drones décident collectivement quels drones suivront quelles cibles et la nécessité évidente d'éviter les collisions entre drones. Les premières versions de cela étaient des drones qui traversaient des points de passage tout en restant en formation, mais la formation pouvait changer.

Pour un «tri», les drones pourraient être programmés pour former une ligne ou un motif dans un ordre spécifique, initialement libérés dans n'importe quelle permutation ou forme, et collectivement et en parallèle, ils formeraient rapidement la ligne ou le motif ordonné.

Pour en revenir à un tri basé sur ordinateur, un problème est qu'il existe un bus de mémoire principal et qu'il n'y a aucun moyen pour un grand nombre d'objets de se déplacer en mémoire en parallèle.

connaître la position de chaque élément

Dans le cas d'un tri sur bande, la position de chaque élément (enregistrement) n'est "connue" que de la "bande" et non de l'ordinateur. Un tri basé sur bande ne doit fonctionner qu'avec deux éléments à la fois et un moyen de désigner les limites de tirage sur une bande (marque de fichier ou enregistrement de taille différente).

À mon humble avis, les gens réfléchissent trop (n). O (nlog (n)) EST pratiquement O (n). Et vous avez besoin de O (n) juste pour lire les données.

De nombreux algorithmes tels que le tri rapide fournissent un moyen très rapide de trier les éléments. Vous pouvez implémenter des variantes de tri rapide qui seraient très rapides dans la pratique.

Par nature, tous les systèmes physiques sont infiniment parallèles. Vous pourriez avoir une charge d'atomes dans un grain de sable, la nature a suffisamment de puissance de calcul pour déterminer où chaque électron de chaque atome devrait être. Donc, si vous disposiez de suffisamment de ressources de calcul (processeurs O (n)), vous pourriez trier n nombres en temps log (n).

Des commentaires:

1. Étant donné un processeur physique qui a k ​​nombre d'éléments, il peut atteindre une parallélisme d'au plus O (k). Si vous traitez arbitrairement n nombres, il le traiterait toujours à un taux lié à k. En outre, vous pouvez formuler ce problème physiquement. Vous pouvez créer n billes d'acier avec des poids proportionnels au nombre que vous souhaitez encoder, ce qui pourrait être résolu par une centrifugeuse dans une théorie. Mais ici, la quantité d'atomes que vous utilisez est proportionnelle à n. Alors que dans un cas standard, vous avez un nombre limité d'atomes dans un processeur.

2. Une autre façon de penser à cela est, disons que vous avez un petit processeur attaché à chaque numéro et que chaque processeur peut communiquer avec ses voisins, vous pouvez trier tous ces nombres en temps O (log (n)).

J'ai travaillé dans un bureau les étés après le lycée quand j'ai commencé l'université. J'avais étudié en informatique AP, entre autres, le tri et la recherche .

J'ai appliqué ces connaissances dans plusieurs systèmes physiques dont je me souviens:

Tri par fusion naturelle pour commencer…

L'invention concerne un système qui imprime des formulaires en plusieurs parties comprenant une déchirure de la taille d'une carte de classement, qui doit être classée dans une banque de tiroirs.

J'ai commencé avec une pile et j'ai trié la pile pour commencer. La première étape consiste à en ramasser environ 5, assez peu pour être facilement mis en ordre dans votre main. Placez le paquet trié en traversant chaque pile pour les garder séparés.

Ensuite, fusionnez chaque paire de piles, produisant une pile plus grande. Répétez jusqu'à ce qu'il n'y ait qu'une seule pile.

… Tri par insertion à terminer

Il est plus facile de classer les cartes triées, car chacune des cartes suivantes est un peu plus loin dans le même tiroir ouvert.

Tri Radix

Celui-ci, personne d'autre n'a compris comment je l'ai fait si vite, malgré des tentatives répétées pour l'enseigner.

Une grande boîte de talons de chèque (de la taille des cartes perforées) doit être triée. Cela ressemble à jouer au solitaire sur une grande table - distribuer, empiler, répéter.

En général

Il y a 30 ans, j'ai remarqué ce que vous demandez: les idées sont transférées assez directement vers les systèmes physiques car il y a des coûts relatifs de comparaison et de gestion des enregistrements , et des niveaux de mise en cache.

Aller au-delà des équivalents bien compris

Je me souviens d'un essai sur votre sujet, qui évoquait le genre de spaghetti . Vous coupez une longueur de nouilles séchées pour indiquer la valeur de clé et l'étiquetez avec l'ID d'enregistrement. Ceci est O (n), traitant simplement chaque élément une fois.

Ensuite, vous prenez le paquet et appuyez sur une extrémité de la table. Ils s'alignent sur les bords inférieurs et sont maintenant triés. Vous pouvez facilement enlever le plus long et recommencer. La lecture est également O (n).

Il y a deux choses qui se passent ici dans le «monde réel» qui ne correspondent pas aux algorithmes. Tout d'abord, l'alignement des bords est une opération parallèle. Chaque donnée est également un processeur (les lois de la physique s'y appliquent). Ainsi, en général, vous mettez à l'échelle le traitement disponible avec n, en divisant essentiellement votre complexité classique par un facteur sur n.

Deuxièmement, comment l'alignement des bords accomplit-il un tri? Le vrai tri est dans la lecture qui vous permet de trouver le plus long en une seule étape, même si vous l'avez fait comparez tous pour trouver la plus longue. Encore une fois, divisez par un facteur de n, donc trouver le plus grand est maintenant O (1).

Un autre exemple est l'utilisation de l'informatique analogique: un modèle physique résout le problème «instantanément» et le travail de préparation est O (n). En principe, le calcul est mis à l'échelle avec le nombre de composants en interaction, et non avec le nombre d'éléments préparés. Ainsi, le calcul est mis à l'échelle avec n². L'exemple auquel je pense est un calcul multifactoriel pondéré, qui a été effectué en perçant des trous dans une carte, en suspendant des poids à des chaînes passant à travers les trous et en rassemblant toutes les chaînes sur un anneau.

Le tri est toujours une durée totale de O (n). Que c'est plus rapide que cela est dû à la parallélisation .

Vous pouvez voir une centrifugeuse comme un tri à godets de n atomes, parallélisé sur n cœurs (chaque atome agit comme un processeur).

Vous pouvez rendre le tri plus rapide par parallélisation mais uniquement par un facteur constant car le nombre de processeurs est limité, O (n / C) est toujours O (n) (les processeurs ont généralement <10 cœurs et les GPU <6000)

La centrifugeuse ne trie pas les nœuds, elle leur applique une force puis ils réagissent en parallèle. Donc, si vous deviez implémenter un tri à bulles où chaque nœud se déplace lui-même en parallèle vers le haut ou vers le bas en fonction de sa "densité", vous auriez une implémentation de centrifugeuse.

Gardez à l'esprit que dans le monde réel, vous pouvez exécuter un très grand nombre de tâches parallèles où, dans un ordinateur, vous pouvez avoir un maximum de tâches parallèles réelles égal au nombre d'unités de traitement physiques.

Au final, vous seriez également limité avec l'accès à la liste des éléments car elle ne peut pas être modifiée simultanément par deux nœuds ...

Serait-il possible avec une certaine surcharge sur chaque nœud (une valeur ou une méthode attachée à chacun des nœuds) de «forcer» l'ordre de la liste?

Lorsque nous trions à l'aide de programmes informatiques, nous sélectionnons une propriété des valeurs triées. C'est généralement l'ampleur du nombre ou de l'ordre alphabétique.

Quelque chose comme une centrifugeuse, où seul chaque élément se soucie de sa position relative dans l'espace (par rapport aux autres nœuds)

Cette analogie me rappelle à juste titre le simple tri à bulles. Comment des nombres plus petits bouillonnent à chaque itération. Comme votre logique de centrifugeuse.

Donc, pour répondre à cela, ne faisons-nous pas vraiment quelque chose de ce genre dans le tri basé sur logiciel?

Tout d'abord, vous comparez deux contextes différents, l'un est la logique (ordinateur) et l'autre est la physique qui (jusqu'à présent) est prouvé que nous pouvons en modéliser certaines parties en utilisant des formules mathématiques et nous, en tant que programmeurs, pouvons utiliser ces formules pour simuler (certaines parties de) la physique dans le travail logique (par exemple, moteur physique dans le moteur de jeu).

Deuxièmement, nous avons des possibilités dans le monde informatique (logique) qui sont presque impossibles en physique, par exemple, nous pouvons accéder à la mémoire et trouver l'emplacement exact de chaque entité à chaque instant, mais en physique, c'est un énorme problème Principe d'incertitude de Heisenberg . .

Troisièmement, si vous voulez cartographier les centrifugeuses et leur fonctionnement dans le monde réel, dans le monde informatique, c'est comme si quelqu'un (le Dieu) vous avait donné un super-ordinateur avec toutes les règles de la physique appliquées et vous y faites votre petit tri ( en utilisant une centrifugeuse) et en disant que votre problème de tri a été résolu en o (n), vous ignorez l'énorme simulation physique qui se déroule en arrière-plan ...

Une autre perspective est que ce que vous décrivez avec la centrifugeuse est analogue à ce que l'on appelle le "tri spaghetti" ( https://en.wikipedia.org/wiki/Spaghetti_sort ). Disons que vous avez une boîte de tiges de spaghetti non cuites de différentes longueurs. Tenez-les dans votre poing et desserrez votre main pour les abaisser verticalement afin que les extrémités reposent toutes sur une table horizontale. Boom! Ils sont triés par hauteur. Temps O (constant). (Ou O (n) si vous incluez le fait de choisir les tiges en hauteur et de les mettre dans un ... support à spaghetti, je suppose?)

Vous pouvez y noter que c'est O (constant) dans le nombre de morceaux de spaghetti, mais, en raison de la vitesse finie du son dans les spaghettis, c'est O (n) dans la longueur du brin le plus long. Donc, rien n'est gratuit.

Considérez: le "tri par centrifugation" est-il vraiment meilleur? Pensez à ce qui se passe à mesure que vous évoluez.

• Les tubes à essai doivent être de plus en plus longs.
• Les trucs lourds doivent voyager de plus en plus loin pour arriver au fond.
• Le moment d'inertie augmente, nécessitant plus de puissance et des temps plus longs pour accélérer jusqu'à la vitesse de tri.

Cela vaut également la peine de considérer d'autres problèmes avec le tri par centrifugation. Par exemple, vous ne pouvez opérer que sur une échelle de taille étroite. Un algorithme de tri informatique peut gérer des nombres entiers de 1 à 2 ^ 1024 et au-delà, pas de soucis. Mettez quelque chose qui pèse 2 ^ 1024 fois plus qu'un atome d'hydrogène dans une centrifugeuse et, eh bien, c'est un trou noir et la galaxie a été détruite. L'algorithme a échoué.

Bien sûr, la vraie réponse ici est que la complexité de calcul est relative à un modèle de calcul, comme mentionné dans une autre réponse. Et le "tri par centrifugation" n'a pas de sens dans le contexte des modèles de calcul courants, tels que le modèle de RAM ou le modèle IO ou les machines à ruban à bandes multiples.