algorithm - sudamericanas - Clasificación en informática versus clasificación en el mundo "real"

porque las eliminatorias sudamericanas son las mas dificiles (12)

Estaba pensando en ordenar algoritmos en software, y posibles formas de superar el obstáculo O(nlogn) . No creo que sea posible ordenar más rápido en un sentido práctico, así que por favor no pienses 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 de billones de artículos en un período de tiempo relativamente corto, debido al hecho de que cada molécula sigue las leyes de densidad y gravitacionales, 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 en la computación?

Creo que uno de los grandes puntos planteados aquí es 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) , donde las computadoras cuánticas pueden cruzar ese umbral en algoritmos O(logn) que actúan en paralelo.

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

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

¿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 clasificamos 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 el tipo de burbuja simple. Cómo surgen números más pequeños en cada iteración. Como su lógica centrífuga.

Entonces, para responder esto, ¿no hacemos algo así en la clasificación basada en software?

Considere: ¿el "tipo de centrífuga" está realmente escalando mejor? Piensa en lo que sucede a medida que escalas.

Los tubos de ensayo tienen que alargarse más y más.
Las cosas pesadas tienen que viajar más y más para llegar al fondo.
El momento de inercia aumenta, lo que requiere 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 el tipo de centrífuga. Por ejemplo, solo puede operar en una escala de tamaño estrecha. Un algoritmo de clasificación por computadora puede manejar enteros de 1 a 2 ^ 1024 y más allá, sin esfuerzo. Ponga 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 "ordenar por centrífuga" no tiene sentido en el contexto de modelos computacionales comunes, como el modelo RAM o el modelo IO o las máquinas de Turing de múltiples cintas.

EDITAR: había entendido mal el mecanismo de una centrífuga y parece que hace una comparación, masivamente paralela. Sin embargo, hay procesos físicos que operan en una propiedad de la entidad que se está ordenando 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 realmente no funciona mediante comparaciones entre elementos, sino que en realidad por una propiedad (''fuerza centrífuga'') en cada elemento individual de forma aislada. Algunos algoritmos de ordenación se incluyen en este tema, especialmente Radix Sort . Cuando este algoritmo de clasificación se paraleliza, debe acercarse al ejemplo de una centrífuga.

Algunos otros algoritmos de clasificación no comparativos son la clasificación de cubetas y la clasificación de conteo . Es posible que la clasificación de cubos también se ajuste a la idea general de una centrífuga (el radio podría corresponder a un contenedor).

Otro llamado ''algoritmo de clasificación'' donde cada elemento se considera de forma aislada es la clasificación del sueño . Aquí el tiempo, en lugar de la fuerza centrífuga, actúa como la magnitud utilizada para la clasificación.

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 que haya ordenado su lista, pero nunca esté seguro sin verificar todos los valores (átomos).

Considere la pregunta: "¿Durante 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 la ejecutó durante unos días, podría estar completamente ordenada. Sin embargo, no lo sabrías sin verificar realmente el contenido.

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

Muchos algoritmos, como quicksort, proporcionan una forma muy rápida de ordenar elementos. Podría implementar variaciones de clasificació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 carga de átomos en un grano de arena, la naturaleza tiene suficiente poder computacional para descubrir dónde debe estar cada electrón en cada átomo. Entonces, si tuviera suficientes recursos computacionales (procesadores O (n)), podría ordenar n números en el tiempo log (n).

De comentarios:

Dado un procesador físico que tiene k número de elementos, puede lograr un 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á utilizando es proporcional a n. Mientras que en un caso estándar tiene un número limitado de átomos en un procesador.
Otra forma de pensar en esto es, digamos que tiene un pequeño procesador conectado a cada número y cada procesador puede comunicarse con sus vecinos, puede ordenar todos esos números en tiempo O (log (n)).

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 de la lógica (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 es un gran problema el principio de incertidumbre de Heisenberg .

Tercero, si desea mapear las centrifugadoras y su funcionamiento en el mundo real, en el mundo de las computadoras, es como si alguien (Dios) le hubiera dado una supercomputadora con todas las reglas de física aplicadas y usted está haciendo una 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 gran simulación física que se está realizando en segundo plano ...

La centrífuga no está clasificando los nodos, aplica una fuerza a ellos y luego reaccionan en paralelo. Entonces, si tuviera que implementar un tipo de burbuja 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, donde en una computadora puede tener un máximo de tareas paralelas reales igual a la cantidad de unidades de procesamiento físico.

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

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

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

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

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 centrífugo tiene algunas propiedades interesantes; por ejemplo:

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

Dado que no tenemos la capacidad de implementar algo como esto en el hardware informático de uso general, el modelo puede no tener relevancia práctica; pero aún puede valer 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, a pesar de que ninguno de ellos es implementable en la actualidad.

Otra perspectiva es que lo que está describiendo con la centrífuga es análogo a lo que se ha llamado el "tipo de espagueti" ( https://en.wikipedia.org/wiki/Spaghetti_sort ). Digamos que tiene una caja de varillas de espagueti sin cocinar de diferentes longitudes. Sosténgalos en su puño y afloje su mano para bajarlos verticalmente para que todos 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 colocarlas en un ... estante de espagueti, supongo?)

Puede notar que es O (constante) en el número de piezas de espagueti, pero, debido a la velocidad finita del sonido en el espagueti, es O (n) en la longitud del filamento más largo. Entonces nada viene gratis.

Trabajé en una oficina de verano después de la secundaria cuando comencé la universidad. Había estudiado en AP Computer Science, entre otras cosas, ordenando y buscando .

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

Tipo de fusión natural para comenzar ...

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

Comencé con un montón de ellos y ordené el montón para empezar. El primer paso es recoger 5 más o menos, lo suficiente como para colocarlos fácilmente en orden en su mano. Coloque el paquete ordenado hacia abajo, entrecruzando cada pila para mantenerlos separados.

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

... Clasificación de inserción para completar

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

Tipo Radix

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

Es necesario ordenar una gran caja de talones de cheques (el tamaño de las tarjetas perforadas). Parece jugar al solitario en una mesa grande: repartir, apilar, repetir.

En general

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

Ir más allá de los equivalentes bien entendidos

Recuerdo un ensayo sobre su tema, y sacó a relucir el tipo de espagueti . Recorta una longitud de fideos secos para indicar el valor clave y lo etiqueta con la ID del registro. Esto es O (n), simplemente procesando cada elemento una vez.

Luego agarras el paquete y tocas un extremo de la mesa. Se alinean en los bordes inferiores y ahora están ordenados. Puedes quitarte 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 corresponden a los algoritmos. Primero, alinear los bordes es una operación paralela. Cada elemento de datos también es un procesador (se le aplican las leyes de la física). Entonces, en general, escala el procesamiento disponible con n, dividiendo esencialmente su complejidad clásica por un factor en n.

En segundo lugar, ¿cómo se logra la alineación de los bordes? La verdadera clasificación está en la lectura que le permite encontrar la más larga en un solo paso, aunque las haya comparado todas para encontrar la más larga. Nuevamente, divida por un factor de n, entonces encontrar el mayor es ahora 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 la cantidad de componentes que interactúan, no con la cantidad de elementos preparados. Entonces el cálculo se escala con n². El ejemplo en el que estoy pensando es un cálculo de múltiples factores ponderado, que se realizó perforando agujeros en un mapa, colgando pesos de cuerdas que pasan a través de los agujeros y reuniendo todas las cadenas en un anillo.

Un ejemplo del mundo real de un "pedido" basado en computadora serían los drones autónomos que cooperan 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 qué objetivos y la necesidad obvia 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 podí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 ordenados.

Volviendo a un tipo basado 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.

saber la posición de cada elemento

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