Estaba pensando en clasificar los algoritmos en el software y las posibles formas en que uno podría superar el O(nlogn)obstáculo. No creo que sea posible ordenar más rápido en un sentido práctico, así que por favor no crea que lo hago.

Dicho esto, parece que con casi todos los algoritmos de clasificación, el software debe conocer la posición de cada elemento. Lo que tiene sentido, de lo contrario, ¿cómo sabría dónde colocar cada elemento de acuerdo con algunos criterios de clasificación?

Pero cuando crucé este pensamiento con el mundo real, una centrífuga no tiene idea de en qué posición se encuentra cada molécula cuando 'clasifica' las moléculas por densidad. De hecho, no le importa la posición de cada molécula. Sin embargo, puede clasificar billones y billones de elementos en un período de tiempo relativamente corto, debido al hecho de que cada molécula sigue las leyes de densidad y gravitación, lo que me hizo pensar.

¿Sería posible con algo de sobrecarga en cada nodo (algún valor o método agregado a cada uno de los nodos) para 'forzar' el orden de la lista? Algo así como una centrífuga, donde solo cada elemento se preocupa por su posición relativa en el espacio (en relación con otros nodos). ¿O esto viola alguna regla de cálculo?

Creo que uno de los grandes puntos planteados aquí son los efectos mecánicos cuánticos de la naturaleza y cómo se aplican en paralelo a todas las partículas simultáneamente.

Quizás las computadoras clásicas restringen inherentemente la clasificación al dominio de O(nlogn), mientras que las computadoras cuánticas pueden cruzar ese umbral en O(logn)algoritmos que actúan en paralelo.

El hecho de que una centrífuga sea básicamente un tipo de burbuja paralela parece ser correcto, lo que tiene una complejidad temporal de O(n).

Supongo que el siguiente pensamiento es que si la naturaleza puede intervenir O(n), ¿por qué no pueden las computadoras?

EDITAR: Había entendido mal el mecanismo de una centrífuga y parece que hace una comparación, una masivamente paralela. Sin embargo, hay procesos físicos que operan en una propiedad de la entidad que se clasifica en lugar de comparar dos propiedades. Esta respuesta cubre algoritmos que son de esa naturaleza.

Una centrífuga aplica un mecanismo de clasificación que no funciona realmente mediante comparaciones entre elementos, sino mediante una propiedad ('fuerza centrífuga') en cada elemento individual de forma aislada. Algunos algoritmos de clasificación entran en este tema, especialmente Radix Sort . Cuando este algoritmo de clasificación se paraleliza, debería acercarse al ejemplo de una centrífuga.

Algunos otros algoritmos de clasificación no comparativos son la clasificación por cubos y la clasificación por recuento . Puede encontrar que la clasificación por cubos también encaja en la idea general de una centrífuga (el radio podría corresponder a un contenedor).

Otro denominado "algoritmo de clasificación" en el que cada elemento se considera de forma aislada es la clasificación del sueño . Aquí, el tiempo, más que la fuerza centrífuga, actúa como la magnitud utilizada para la clasificación.

La complejidad computacional siempre se define con respecto a algún modelo computacional. Por ejemplo, un algoritmo que es O ( n ) en una computadora típica podría ser O (2 ⁿ ) si se implementa en Brainfuck .

El modelo computacional de centrífuga tiene algunas propiedades interesantes; por ejemplo:

• apoya el paralelismo arbitrario; no importa cuántas partículas haya en la solución, todas se pueden clasificar simultáneamente.
• no da un tipo lineal estricto de partículas por masa, sino una aproximación muy cercana (de baja energía).
• no es factible examinar las partículas individuales en el resultado.
• no es posible clasificar partículas por diferentes propiedades; solo se admite la masa.

Dado que no tenemos la capacidad de implementar algo como esto en hardware informático de propósito general, es posible que el modelo no tenga relevancia práctica; pero vale la pena examinarlo para ver si hay algo que aprender de él. Los algoritmos no deterministas y los algoritmos cuánticos han sido áreas activas de investigación, por ejemplo, aunque ninguno de ellos es realmente implementable en la actualidad.

El truco está ahí, que solo tienes una probabilidad de ordenar tu lista usando una centrífuga. Al igual que con otros tipos del mundo real [cita requerida], puede cambiar la probabilidad de haber ordenado su lista, pero nunca esté seguro sin verificar todos los valores (átomos).

Considere la pregunta: "¿Cuánto tiempo debe hacer funcionar su centrífuga?"
Si solo lo ejecutó durante un picosegundo, su muestra puede estar menos ordenada que el estado inicial ... o si lo ejecutó durante unos días, puede estar completamente ordenado. Sin embargo, no lo sabría sin verificar realmente el contenido.

Un ejemplo del mundo real de una "ordenación" basada en computadora serían los drones autónomos que trabajan cooperativamente entre sí, conocidos como "enjambres de drones". Los drones actúan y se comunican como individuos y como grupo, y pueden rastrear múltiples objetivos. Los drones deciden colectivamente qué drones seguirán a qué objetivos y la obvia necesidad de evitar colisiones entre drones. Las primeras versiones de esto eran drones que se movían a través de puntos de paso mientras permanecían en formación, pero la formación podría cambiar.

Para una "clasificación", los drones podrían programarse para formar una línea o patrón en un orden específico, inicialmente liberados en cualquier permutación o forma, y ​​colectivamente y en paralelo formarían rápidamente la línea o patrón ordenado.

Volviendo a una ordenación basada en computadora, un problema es que hay un bus de memoria principal y no hay forma de que una gran cantidad de objetos se muevan en la memoria en paralelo.

conocer la posición de cada elemento

En el caso de una clasificación de cinta, la posición de cada elemento (registro) sólo es "conocida" por la "cinta", no por la computadora. Una clasificación basada en cinta solo necesita funcionar con dos elementos a la vez y una forma de indicar los límites de ejecución en una cinta (marca de archivo o un registro de diferente tamaño).

En mi humilde opinión, la gente piensa demasiado en log (n). O (nlog (n)) ES prácticamente O (n). Y necesita O (n) solo para leer los datos.

Muchos algoritmos, como el ordenamiento rápido, proporcionan una forma muy rápida de ordenar elementos. Podría implementar variaciones de ordenación rápida que serían muy rápidas en la práctica.

Inherentemente, todos los sistemas físicos son infinitamente paralelos. Es posible que tenga una gran cantidad de átomos en un grano de arena, la naturaleza tiene suficiente poder computacional para averiguar dónde debería estar cada electrón en cada átomo. Entonces, si tuviera suficientes recursos computacionales (O (n) procesadores), podría ordenar n números en log (n) tiempo.

De comentarios:

1. Dado un procesador físico que tiene k número de elementos, puede lograr una paralelismo de como máximo O (k). Si procesa n números arbitrariamente, aún lo procesará a una velocidad relacionada con k. Además, podría formular este problema físicamente. Podría crear n bolas de acero con pesos proporcionales al número que desea codificar, lo que podría resolverse mediante una centrífuga en una teoría. Pero aquí la cantidad de átomos que estás usando es proporcional an. Mientras que en un caso estándar tiene un número limitado de átomos en un procesador.

2. Otra forma de pensar sobre esto es, digamos que tiene un pequeño procesador adjunto a cada número y cada procesador puede comunicarse con sus vecinos, podría ordenar todos esos números en tiempo O (log (n)).

Trabajé en una oficina los veranos después de la secundaria cuando comencé la universidad. Había estudiado Ciencias de la Computación AP, entre otras cosas, ordenando y buscando .

Apliqué este conocimiento en varios sistemas físicos que puedo recordar:

Orden de fusión natural para comenzar ...

Un sistema imprimía formularios de varias copias, incluido un corte del tamaño de una tarjeta de archivo, que debía archivarse en un banco de cajones.

Empecé con un montón de ellos y ordené el montón para empezar. El primer paso es recoger 5 o más, lo suficientemente pocos como para ponerlos en orden fácilmente en su mano. Coloque el paquete clasificado, cruzando cada pila para mantenerlos separados.

Luego, combine cada par de pilas, produciendo una pila más grande. Repita hasta que solo quede una pila.

… Orden de inserción para completar

Es más fácil archivar las tarjetas ordenadas, ya que cada una de las siguientes está un poco más abajo en el mismo cajón abierto.

Orden de radix

Este nadie más entendió cómo lo hice tan rápido, a pesar de los repetidos intentos de enseñarlo.

Es necesario clasificar una caja grande de talones de cheques (del tamaño de tarjetas perforadas). Parece jugar al solitario en una mesa grande: repartir, acumular, repetir.

En general

Hace 30 años, noté lo que está preguntando: las ideas se transfieren a los sistemas físicos de manera bastante directa porque hay costos relativos de comparaciones y manejo de registros , y niveles de almacenamiento en caché.

Ir más allá de equivalentes bien entendidos

Recuerdo un ensayo sobre su tema y mencionó el tipo de espagueti . Recorta un trozo de fideos secos para indicar el valor clave y lo etiqueta con el ID de registro. Esto es O (n), simplemente procesando cada artículo una vez.

Luego agarras el paquete y golpeas un extremo en la mesa. Se alinean en los bordes inferiores y ahora están ordenados. Puede quitarse trivialmente el más largo y repetir. La lectura también es O (n).

Hay dos cosas que suceden aquí en el "mundo real" que no se corresponden con los algoritmos. Primero, alinear los bordes es una operación paralela. Cada elemento de datos es también un procesador (se le aplican las leyes de la física). Entonces, en general, escala el procesamiento disponible con n, esencialmente dividiendo su complejidad clásica por un factor en n.

En segundo lugar, ¿cómo se logra una clasificación alineando los bordes? La clasificación real está en la lectura de salida que le permite encontrar la más larga en un solo paso, a pesar de que hizo comparar todos ellos para encontrar la más larga. Nuevamente, divida por un factor de n, por lo que encontrar el más grande ahora es O (1).

Otro ejemplo es el uso de la computación analógica: un modelo físico resuelve el problema "instantáneamente" y el trabajo de preparación es O (n). En principio, el cálculo se escala con el número de componentes que interactúan, no con el número de elementos preparados. Entonces el cálculo escala con n². El ejemplo en el que estoy pensando es un cálculo multifactor ponderado, que se realizó perforando agujeros en un mapa, colgando pesos de cuerdas que pasan por los agujeros y reuniendo todas las cuerdas en un anillo.

La clasificación sigue siendo O (n) tiempo total. Que sea más rápido que eso se debe a la Paralelización .

Puede ver una centrífuga como un tipo de cubo de n átomos, paralelizados sobre n núcleos (cada átomo actúa como un procesador).

Puede hacer que la clasificación sea más rápida mediante la paralelización, pero solo mediante un factor constante porque el número de procesadores es limitado, O (n / C) sigue siendo O (n) (las CPU suelen tener <10 núcleos y las GPU <6000)

La centrífuga no clasifica los nodos, les aplica una fuerza y ​​luego reaccionan en paralelo. Entonces, si tuviera que implementar una clasificación de burbujas donde cada nodo se mueve en paralelo hacia arriba o hacia abajo en función de su "densidad", tendría una implementación de centrífuga.

Tenga en cuenta que en el mundo real puede ejecutar una gran cantidad de tareas paralelas, mientras que en una computadora puede tener un máximo de tareas paralelas reales igual al número de unidades de procesamiento físico.

Al final, también estarías limitado con el acceso a la lista de elementos porque no puede ser modificado simultáneamente por dos nodos ...

¿Sería posible con algo de sobrecarga en cada nodo (algún valor o método agregado a cada uno de los nodos) para 'forzar' el orden de la lista?

Cuando ordenamos usando programas de computadora, seleccionamos una propiedad de los valores que se ordenan. Esa es comúnmente la magnitud del número o el orden alfabético.

Algo así como una centrífuga, donde solo cada elemento se preocupa por su posición relativa en el espacio (en relación con otros nodos)

Esta analogía me recuerda acertadamente al tipo de burbuja simple. Cómo aparecen números más pequeños en cada iteración. Como su lógica centrífuga.

Entonces, para responder a esto, ¿no hacemos algo de ese tipo en la clasificación basada en software?

En primer lugar, está comparando dos contextos diferentes, uno es la lógica (computadora) y el otro es la física que (hasta ahora) está comprobado que podemos modelar algunas partes usando fórmulas matemáticas y nosotros, como programadores, podemos usar estas fórmulas para simular (algunas partes de) la física en el trabajo lógico (por ejemplo, motor de física en el motor del juego).

En segundo lugar, tenemos algunas posibilidades en el mundo de la computadora (lógica) que es casi imposible en física, por ejemplo, podemos acceder a la memoria y encontrar la ubicación exacta de cada entidad en cada momento, pero en física ese es un gran problema, el principio de incertidumbre de Heisenberg .

En tercer lugar, si desea mapear centrifugadoras y su funcionamiento en el mundo real, en el mundo de las computadoras, es como si alguien (El Dios) le hubiera dado una supercomputadora con todas las reglas de la física aplicadas y usted estuviera haciendo su pequeña clasificación en ella ( usando centrífuga) y al decir que su problema de clasificación se resolvió en o (n), está ignorando la enorme simulación física que se desarrolla en segundo plano ...

Otra perspectiva es que lo que está describiendo con la centrífuga es análogo a lo que se ha llamado "tipo espagueti" ( https://en.wikipedia.org/wiki/Spaghetti_sort ). Supongamos que tiene una caja de varillas de espagueti crudas de diferentes longitudes. Sosténgalos en su puño y afloje su mano para bajarlos verticalmente de modo que los extremos descansen sobre una mesa horizontal. ¡Auge! Están ordenados por altura. O (constante) tiempo. (O O (n) si incluye recoger las varillas por altura y ponerlas en una ... rejilla para espaguetis, ¿supongo?)

Puede notar allí que es O (constante) en el número de piezas de espagueti, pero, debido a la velocidad finita del sonido en los espaguetis, es O (n) en la longitud de la hebra más larga. Así que nada viene gratis.

Considere: ¿el "tipo centrífugo" realmente se escala mejor? Piense en lo que sucede a medida que aumenta la escala.

• Los tubos de ensayo tienen que alargarse cada vez más.
• Las cosas pesadas tienen que viajar más y más lejos para llegar al fondo.
• El momento de inercia aumenta, requiriendo más potencia y tiempos más largos para acelerar hasta la velocidad de clasificación.

También vale la pena considerar otros problemas con la centrifugación. Por ejemplo, solo puede operar en una escala de tamaño reducida. Un algoritmo de clasificación por computadora puede manejar números enteros de 1 a 2 ^ 1024 y más, sin preocupaciones. Pon algo que pese 2 ^ 1024 veces más que un átomo de hidrógeno en una centrífuga y, bueno, eso es un agujero negro y la galaxia ha sido destruida. El algoritmo falló.

Por supuesto, la respuesta real aquí es que la complejidad computacional es relativa a algún modelo computacional, como se menciona en otra respuesta. Y el "tipo centrífugo" no tiene sentido en el contexto de modelos computacionales comunes, como el modelo RAM o el modelo IO o las máquinas Turing de varias cintas.