Le tri en informatique par opposition au tri dans le monde réel

Question

Je pensais à des algorithmes de tri dans le logiciel, et que les moyens on pourrait surmonter l' O(nlogn) barrage. Je ne pense pas qu'il EST possible de trier plus vite dans un sens pratique, de sorte s'il vous plaît ne pense pas que je fais.

Avec cela dit, il semble que presque tous les algorithmes de tri, le logiciel doit connaître la position de chaque élément. Ce qui est logique, sinon, comment serait-il savoir où placer chaque élément en fonction de certains critères de tri?

Mais quand j'ai traversé cette réflexion avec le monde réel, une centrifugeuse n'a aucune idée de ce que la position de chaque molécule est quand il 'sortes' molécules par la densité. En fait, il ne s'occupe pas la position de chaque molécule. Cependant il est possible de trier milliards sur milliards de milliards d'éléments dans une période relativement courte de temps, en raison du fait que chaque molécule suit la densité et de la gravité de lois - qui m'a fait réfléchir.

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

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

Peut-être les ordinateurs classiques intrinsèquement restreindre le tri du domaine de l' O(nlogn),, où, comme les ordinateurs quantiques peuvent être en mesure de franchir ce seuil en O(logn) algorithmes qui agissent en parallèle.

Au point qu'une centrifugeuse étant à la base un parallèle tri à bulles semble être correct, qui a une complexité temporelle de l' O(n).

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

Answer 1

EDIT: j'avais mal compris le mécanisme d'une centrifugeuse, et il semble que l'on fait une comparaison, un massivement parallèle. 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 qui sont de cette nature.

Une centrifugeuse applique un mécanisme de tri ne fonctionne pas vraiment par le biais de comparaisons entre les éléments, mais en réalité par une propriété (la "force centrifuge") sur chaque élément individuel dans l'isolement.Certains algorithmes de tri tomber dans ce thème, en particulier de Tri Radix. Lors de cet algorithme de tri est parallélisé il est de l'approche de l'exemple d'une centrifugeuse.

Certains autres non-comparative des algorithmes de tri sont Seau de tri et de Comptage de Tri. Vous pouvez trouver que le Seau de tri s'inscrit aussi dans l'idée générale d'une centrifugeuse (le rayon pourrait correspondre à une bin).

Un autre soi-disant 'algorithme de tri", où chaque élément est considéré isolément est le Sommeil de Tri. Ici le temps plutôt que de la force centrifuge agit comme la grandeur utilisée pour le tri.

Answer 2

La complexité algorithmique est toujours définie par rapport à un certain modèle de calcul. Par exemple, un algorithme est O(n) sur un ordinateur typique pourrait être O(2ⁿ) si mis en œuvre en Brainfuck.

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

• il prend en charge arbitraire parallélisme; peu importe le nombre de particules dans la solution, ils peuvent tous être triés simultanément.
• il n'en a strictement linéaire de tri de particules en masse, mais plutôt un très proche (basse énergie) rapprochement.
• il n'est pas possible d'examiner les particules individuelles dans le résultat.
• il n'est pas possible de trier les particules par des propriétés différentes; seulement la masse est prise en charge.

Étant donné que nous n'avons pas la capacité de mettre en place quelque chose comme ça dans le matériel informatique, le modèle ne peut pas avoir de pertinence pratique; mais il peut encore être utile d'examiner, pour voir si il y a quelque chose à apprendre de lui. Les algorithmes non-déterministes et les algorithmes quantiques ont tous deux été actifs domaines de la recherche, par exemple, même si aucune n'est réellement mises en œuvre aujourd'hui.

Answer 3

L'astuce est là, que vous avez seulement une probabilité de tri de la liste à l'aide d'une centrifugeuse. Comme avec d'autres sortes [citation nécessaire], vous pouvez modifier la probabilité que vous avez triés votre liste, mais jamais être certain, sans vérification de toutes les valeurs (les atomes).

Considérez la question: "Combien de temps vous devez exécuter votre centrifugeuse?"
Si vous avez seulement il a couru pendant une picoseconde, votre échantillon peut être moins triés que l'état initial.. ou si vous avez manqué pendant ces quelques jours, il peut être complètement trié. Cependant, vous ne savez pas sans vérifier le contenu.

Answer 4

Un exemple réel d'un ordinateur basé sur "passer commande" autonome des drones qui coopérer les uns avec les autres, connus comme les "essaims de drones". Les drones d'agir et de communiquer à la fois en tant qu'individus et en tant que groupe, et peut suivre plusieurs cibles. Les drones décider collectivement drones qui va suivre et des objectifs et de la nécessité évidente d'éviter les collisions entre les drones. Les premières versions de ce étaient des drones qui s'est déplacé à travers des points de passage, tout en restant dans la formation, mais la formation peut changer.

Pour un "tri", les drones pourraient être programmés pour former une ligne ou d'un motif dans un ordre spécifique, initialement publié en toute permutation ou de la forme, et collectivement, et en parallèle, ils seraient rapidement forme commandés ligne ou un motif.

Pour en revenir à un ordinateur de tri, l'un des problèmes est qu'il y a une mémoire principale de bus, et il n'y a aucun moyen pour un grand nombre d'objets à déplacer dans la mémoire en parallèle.

connaître la position de chaque élément

Dans le cas d'une bande de tri, la position de chaque élément (record) n'est "connu" de la "bande", et non pas à l'ordinateur. Une bande de tri ne doit travailler avec les deux éléments à la fois, et une manière de désigner exécuter des limites sur une cassette (fichier de la marque, ou un enregistrement de taille différente).

Answer 5

À mon humble avis, les gens overthink log(n). O(nlog(n)) EST pratiquement O(n). Et vous avez besoin de O(n) pour lire les données.

De nombreux algorithmes tels que quicksort fournissent un moyen très rapide pour trier les éléments. Vous pourriez mettre en œuvre les variations de quicksort qui serait très rapide dans la pratique.

Par essence, tous les systèmes physiques sont infiniment parallèle. Vous pourriez avoir un buttload d'atomes dans un grain de sable, la nature a suffisamment de puissance de calcul pour comprendre où chaque électron de chaque atome doit être. Donc, si vous avez eu assez de ressources de calcul (O(n) processeurs) vous pouvez trier n nombres en log(n) fois.

De commentaires:

1. Étant donné un processeur physique qui a k nombre d'éléments, il est possible d'atteindre un parallelness d'au plus O(k). Si vous le processus de n nombres arbitrairement, il ne serait procédé à un taux lié à k. Aussi, vous pourriez formuler ce problème de physique. Vous pouvez créer n billes d'acier d'un poids proportionnel à la quantité 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 à propos de ce qui est, disons que vous avez un petit processeur attaché à chaque nombre et chaque processeur peut communiquer avec ses voisins, vous pouvez trier tous ces chiffres en O(log(n)) de temps.