algorithm - counting sort

Clasificación por gravedad: ¿Es esto posible programáticamente? (19)

De la respuesta de Debilski :
Adaptaré un poco tu idea. Tenemos nuestros objetos pero no difieren en peso, sino en velocidad. Entonces, al principio todos los objetos se alinean en la línea de inicio y en el disparo de inicio, todos se moverán con sus respectivas velocidades hasta el final.
Lo suficientemente claro: el primer objeto en terminar emitirá una señal, diciendo que está ahí. Se captura la señal y se escribe en el documento de resultados quién era.

Lo simplificaría un paso más y diría que estos objetos son enteros positivos aleatorios. Y queremos clasificarlos en orden ascendente a medida que se acercan a cero, de modo que tengan una distancia desde cero d que inicialmente es igual al entero.

Suponiendo que la simulación se realiza en pasos de tiempo discretos, es decir, cuadros , en cada cuadro, la nueva distancia de cada objeto sería: d = d - v y un objeto se agregaría a la lista cuando d ≤ 0 . Esa es una resta y una condicional. Dos pasos discretos para cada objeto, por lo que los cálculos parecen ser O (n): lineales.

El problema es que es lineal para un solo cuadro ! Se multiplica por el número de fotogramas necesarios para finalizar. La simulación en sí es O (nf): cuadrática.

Sin embargo, si tomamos la duración de un fotograma como argumento t tenemos la capacidad de afectar el número de fotogramas f de manera inversamente proporcional. Podemos aumentar t para reducir f pero esto tiene un costo de precisión, cuanto más aumentamos t , mayor es la probabilidad de que dos objetos terminen en el mismo período de tiempo, por lo tanto, se enumeran como equivalentes, incluso si no lo son. Entonces obtenemos un algoritmo con precisión ajustable (como lo es en la mayoría de los contextos de simulación de elementos finitos)

Podemos refinarlo aún más convirtiéndolo en un algoritmo adaptable + recursivo. En código humano sería:

function: FESort: arguments: OriginalList, Tolerance define an empty local list: ResultList while OriginalList has elements define an empty local list: FinishedList iterate through OriginalList decrement the distance of each object by Tolerance if distance is less than or equal to zero, move object from OriginalList to FinishedList check the number of elements in FinishedList when zero set Tolerance to double Tolerance when one append the only element in FinishedList to ResultList when more append the result of FESort with FinishedList and half Tolerance to ResultList return ResultList

Me pregunto si hay alguna implementación similar real que funcione para alguien.

Tema interesante de hecho :)

PD. El pseudocódigo de arriba es mi idea de pseudocódigo, por favor siéntase libre de reescribirlo de una manera más legible o conforme si hay uno.

Recientemente he estado pensando en usar el diseño orientado a objetos en el algoritmo de clasificación. Sin embargo, no pude encontrar una manera adecuada de acercarme aún más al hacer este algoritmo de clasificación que realiza la clasificación en tiempo O (n).

Ok, esto es lo que he estado pensando durante una semana. Tengo un conjunto de datos de entrada. Asignaré una masa a cada uno de los datos de entrada (supongamos que los datos de entrada son un tipo de Mass y un tipo de Sphere . Si asumimos que todos los objetos son objetos perfectamente esféricos con formas proporcionales a su masa, el más pesado toca el suelo primero. ). Pondré todos mis datos de entrada en el espacio a la misma distancia de la Tierra. Y los haré caer libres. De acuerdo con la ley gravitacional, el más pesado golpea el suelo primero. Y el orden en que golpean me dará los datos ordenados. Esto es divertido de alguna manera, pero debajo siento que esto debería ser posible usando el OO que he aprendido hasta la fecha

¿Es realmente posible hacer una técnica de clasificación que use un tirón gravitacional como el escenario o soy estúpido / loco?

Edición: Resulta que todos los objetos golpean el suelo al mismo tiempo, por lo tanto, introduje el concepto de objeto esférico.

Creo que es bueno mencionar / referirse a: ¿Cuál es la relación entre P vs. NP y la capacidad de la naturaleza para resolver los problemas de NP de manera eficiente? La clasificación es O(nlog(n)) , ¿por qué no intentar resolver los problemas de NP?
Por las leyes de la física, los objetos caen en proporciones a la constante gravitatoria, la masa es despreciable.
Simular un proceso físico puede afectar la complejidad del tiempo real.

Acabas de replantearte el problema. El cálculo del orden de los efectos gravitacionales tendrá, en el mejor de los casos, la O de los algoritmos de ordenación que intenta superar.

Adaptaré un poco tu idea. Tenemos nuestros objetos pero no difieren en peso, sino en velocidad. Entonces, al principio todos los objetos se alinean en la línea de inicio y en el disparo de inicio, todos se moverán con sus respectivas velocidades hasta el final.

Lo suficientemente claro: el primer objeto en terminar emitirá una señal, diciendo que está ahí. Usted captura la señal y escribe en el documento de resultados quién era.

Bien, entonces querrás simular eso.

Tomamos la longitud de su campo para que sea L=1 . Con el tamaño de paso, cada uno de sus N objetos se mueve una longitud de vᵢ∙∆t a la vez. Eso significa que cada objeto necesita s sᵢ = L / (vᵢ∙∆t) pasos antes de llegar al final.

El punto es ahora, para poder distinguir dos objetos con velocidades muy cercanas, tendrá que tener un tamaño de paso diferente para todos sus objetos.

Ahora, en el mejor de los casos, esto significa que el objeto 1 termina en un paso, el objeto 2 en dos y así sucesivamente. Por lo tanto, el número total de pasos es S = 1 + 2 + … + N = N∙(N + 1)/2 . Esto es de orden N∙N

Si no es el mejor de los casos y las velocidades no son tan cercanas entre sí, tendrá que reducir el tamaño del paso y, en efecto, repetir muchas veces más.

Analizar: (1) Todos los centros de esferas están alineados en el inicio (2) mayor número ==> masa mayor ==> radio mayor ==> distancia al suelo inferior (3) en ''vacío'' misma aceleración = misma velocidad evolución = => la misma distancia para el centro ==> cuánto mayor es el radio ... cómo antes la esfera tocará el suelo ==> conceptualmente OK, buena técnica física si cuando una esfera toca el suelo puede enviar una señal de indentificación + tiempo de golpe ... que proporcionará la lista ordenada Prácticamente ... no es una técnica numérica "buena"

Creo que el problema se puede simplificar de la siguiente manera: desea colocar los fondos de las esferas a diferentes alturas, de modo que cuando caiga a una gravedad idéntica, la más grande toque el suelo primero, el segundo más grande, etc. Esto es esencialmente equivalente a usar líneas en lugar de esferas ... en cuyo caso solo puede decir que heightOffTheGround = MAX_VALUE - mass.

Tampoco debe preocuparse por la aceleración con el tiempo ... ya que no le importa lo rápido que vayan o la física realista, puede darles a todos una velocidad inicial x, e ir de allí.

El problema es, entonces, que básicamente hemos reformulado el problema y lo resolvimos así (pseudocódigo):

int[] sortedArray; // empty int[] unsortedArray; // full of stuff int iVal = MAX_INT_VALUE; while (true) { foreach (currentArrayValue in sortedArray) { if (iVal = current array value { put it in my sortedArray remove the value from my unsortedArray } } if (unsortedArray is empty) { break; // from while loop } iVal-- }

El problema es que para ejecutar el motor de física, tienes que recorrer cada unidad de tiempo, y eso será O (1) ... con una constante muy grande ... el número constante de valores delta que el sistema ejecutarse en. El inconveniente es que para la gran mayoría de estos valores delta, esencialmente no estarás acercándote a la respuesta: en cualquier iteración dada, es muy probable que todas las esferas / líneas / lo que sea se hayan movido ... pero ninguna golpeará

Podrías intentar simplemente decir, bueno, ¡saltemos muchos pasos intermedios y avancemos hasta que uno llegue! Pero eso significa que debes saber cuál es el más grande ... y volverás al problema de clasificación.

Definitivamente, solo debería tener el hardware adecuado para ello. De lo contrario, esto suena una idea genial. Espero que alguien presente un documento de IEEE para hacer que este loco sueño se visualice.

El cálculo de la gravitación es gratuito solo en el mundo real. En el programa necesitas modelarlo. Será otra n en complejidad mínima.

En realidad, hay un algoritmo de clasificación bastante famoso llamado tipo Spaghetti que es similar al suyo. Puede consultar algunos de los muchos análisis de la misma en la web. por ejemplo, en cstheory .

En una "computadora gravitatoria" ficticia, este tipo de clasificación llevaría a O (1) para ser resuelto. Pero con las computadoras reales como las conocemos, su pensamiento lateral no ayudaría.

Hace unas semanas estuve pensando en lo mismo.

Pensé usar la biblioteca Phys2D para implementarla. Puede que no sea práctico pero solo por diversión. También puede asignar pesos negativos a los objetos para representar números negativos. Con la biblioteca phys2d puede definir la gravedad para que los objetos con peso negativo vayan al techo y los objetos con peso positivo se caigan. Luego, organice todos los objetos en el medio entre el piso y el techo con la misma distancia entre el piso y el techo. Supongamos que tiene una matriz resultante r [] de longitud = número de objetos. Luego, cada vez que un objeto toca el techo, lo agrega al comienzo de la matriz r [0] e incrementa el contador, la próxima vez que un objeto toque el techo lo agregue en r [1], cada vez que un objeto llegue al piso donde está agréguelo al final de la matriz r [r.length-1], la próxima vez que lo agregue en r [r.length-2]. Al final, los objetos que no se movieron (se mantuvieron flotando en el medio) se pueden agregar en el centro de la matriz (estos objetos son los 0).

Esto no es eficiente pero puede ayudarlo a implementar su idea.

Hmmmm Tipo de gravedad.

Ignorar su modelo específico de gravedad es incorrecto, veamos a dónde nos lleva esta idea.

La realidad física tiene 10 ^ 80 procesadores.

Se sabe que los límites inferiores reales de clasificación son log (N) si tiene procesadores N / 2 para ordenar N objetos.

Si tiene varios núcleos de CPU disponibles, no hay razón para que no pueda ejecutar mergesort en varios subprocesos.

Ignorando todos los defectos que todos los demás han mencionado, esencialmente esto se reduce a un algoritmo O(n^2) , no O(n) . Tendría que recorrer todas las "esferas", encontrar la más "pesada" o la "más grande", y luego insertarla en una lista, luego enjuagar y repetir. es decir, para encontrar el que toca el suelo primero, debes recorrer toda la lista, si es el último, tomaría O(n) tiempo, el segundo podría tomar O(n-1) , etc. ... pero peor que eso, tienes que realizar un montón de operaciones matemáticas cada vez solo para calcular un valor de "tiempo" inútil cuando podrías haber clasificado el valor que te interesaba en primer lugar.

La clasificación de propósito general es, en el mejor de los casos, una O (n log n). Para mejorar esto, debe saber algo acerca de los datos, además de cómo comparar valores.

Si los valores son todos los números, la clasificación de radix da O (n) suponiendo que tiene límites superior e inferior para los números. Este enfoque se puede ampliar para manejar cualquier número, y en última instancia, todos los datos en una computadora se representan mediante números. Por ejemplo, puede dividir las cadenas por orden, en cada pasada, clasificando por un carácter como si fuera un dígito.

Desafortunadamente, el manejo de tamaños variables de datos significa hacer un número variable de pases a través de la clasificación de radix. Usted termina con O (n log m), donde m es el valor más grande (ya que k bits le da un valor de hasta (2 ^ k) -1 para sin signo, la mitad para firmado). Por ejemplo, si está ordenando los enteros de 0 a m-1, bueno, realmente tiene O (n log n) de nuevo.

Traducir un problema a otro puede ser un muy buen enfoque, pero a veces simplemente se agrega otra capa de complejidad y sobrecarga.

La cuestión es que, si bien una de las ideas de OOP puede ser modelar el mundo real, eso no significa que haya una correspondencia directa entre el tiempo que tarda algo en el mundo real y el tiempo que tardaría en simularlo con una computadora.

Imagine los pasos reales requeridos para su procedimiento:

Se debe construir un objeto para cada elemento en su conjunto de datos. En la mayoría de los hardware modernos, esto solo requeriría una iteración y, por lo tanto, sería su estrategia O (n) en el mejor de los casos .
El efecto de la gravedad tendría que ser simulado, para cada objeto. Una vez más, la forma más obvia y directa de implementar esto sería iterar.
El tiempo que cada objeto aterrice en la superficie de la "Tierra" en su modelo de programación tendría que ser capturado y, a través de algún mecanismo específico de implementación, el objeto correspondiente tendría que insertarse en una lista ordenada como resultado.

Teniendo en cuenta el problema introduce complicaciones adicionales. Pregúntate esto: ¿hasta qué punto necesitas posicionar estos objetos para comenzar? Obviamente lo suficientemente alto como para que caiga el más grande; es decir, más lejos de la Tierra que el radio del objeto más grande. Pero, ¿cómo sabes qué tan lejos está? Primero deberías determinar el objeto más grande de la colección; esto, nuevamente, (probablemente) requeriría iteración. Además, uno podría imaginar que esta simulación podría ser multiproceso para intentar simular el comportamiento en tiempo real de la noción de objetos que realmente caen; pero luego se encontrará intentando agregar elementos a una colección (una operación que obviamente toma una cantidad de tiempo distinta de cero) potencialmente al mismo tiempo que se detectan nuevas colisiones. Así que esto creará problemas de subprocesos también.

En resumen, tengo problemas para imaginar cómo esta idea podría implementarse correctamente simplemente usando OOP sin hardware especial. Dicho esto, realmente es una buena idea. De hecho, me recuerda a Bead Sort, un algoritmo que, aunque no es lo mismo que su idea, también es una solución de clasificación que aprovecha el concepto muy físico de la gravedad y, como es lógico, requiere hardware especializado.

La idea puede parecer simple, pero la diferencia entre el mundo real y el modelado en este caso es que en el mundo real todo sucede en paralelo. Para modelar la clasificación gravitacional como lo describe, debe comenzar por pensar cada objeto en un hilo separado con una forma segura de subprocesos para agregarlos a una lista en el orden en que terminan. Siendo realistas, en términos de rendimiento de clasificación, probablemente solo usaría una clasificación rápida en los tiempos, o dado que están a la misma distancia que la velocidad de caída. Sin embargo, si su fórmula es proporcional a la masa, simplemente omitiría todo eso y clasificaría la masa.

Me encanta la idea! Es inteligente Si bien lo que otros están diciendo es, en general , correcto, que el límite O (n log n) es probablemente un límite inferior en el problema de clasificación en general, debemos tener en cuenta que ese límite inferior es cierto solo para los modelos basados en comparación . Lo que está proponiendo aquí es un modelo completamente diferente, merece más reflexión.

Además, como James y Matrix han señalado, el más pesado no viaja más rápido que el más ligero, obviamente necesita adaptar el modelo a algo donde el objeto más pesado (número) viajaría más rápido / más lejos (o más lento / menos) más adelante) para que pueda distinguir los números de alguna manera (una centrífuga también viene a la mente).

Requiere mas pensamiento, pero tu idea es aguda!

(Editar) Ahora, viendo la idea de Enrique en Phys2D, creo que tiene mucho más sentido.

Una cosa que sugeriría es ignorar definitivamente el aspecto de eficiencia por ahora. (Lo sé, sé que esa era toda la meta). Es un modelo nuevo, y primero debemos cerrar la brecha entre la idea y su implementación. Solo así podremos comprender lo que significa la complejidad del tiempo para este modelo.

Si se construyera una computadora que ordenara los objetos según algunos criterios (que no es del todo ridículo pensar), entonces creo que el orden de la complejidad no tendría nada que ver con la cantidad de objetos, sino con la velocidad de la aceleración local. Debido a la gravedad. Suponiendo que está modelado en la Tierra, la complejidad sería O (g ₀ ) donde g ₀ es:

El razonamiento simple es que el número de objetos esféricos (n) es irrelevante si sus centros están alineados al inicio. Además, la aceleración debida a la gravedad tendrá un impacto mucho mayor que la altura misma a medida que aumenta. Por ejemplo, si aumentamos la altura de todos los objetos en 10x, no les tomará 10 veces el tiempo para golpear el suelo, pero mucho menos. Esto incluye varias aproximaciones despreciables, ya que la aceleración realmente depende de la distancia entre dos objetos, pero eso puede ignorarse ya que estamos más interesados en una imagen más grande que en un valor específico.

Brillante idea sin embargo.

Además, me encanta el video de clasificación de monedas publicado por @Jeremy. Y finalmente, la orientación a objetos sería la menor de mis preocupaciones en la construcción de tal máquina. Pensando más en eso, aquí están mis estúpidos dos centavos para construir una máquina como esta:

~~O 0 o O o~~

. . . . . . . . . . . . . . . = = = = =

Todos los objetos son de tamaños variables proporcionales a los criterios por los que queremos clasificar. Inicialmente, se mantienen unidos horizontalmente por una varilla delgada que atraviesa el centro de cada esfera. Los = en la parte inferior están diseñados especialmente para registrar un valor (opcionalmente su posición) en algún lugar tan pronto como colisionen con una esfera. Después de que todas las esferas hayan colisionado, tendremos nuestro orden clasificado basado en los valores registrados.

Una vez que haya calculado todas las veces que toman para golpear el suelo, todavía tendrá que ordenar esos valores. Realmente no estás ganando nada, solo estás ordenando diferentes números después de realizar algún cálculo adicional innecesario.

EDIT : Whoops. Olvidé la física 101. Por supuesto que todos golpearán al mismo tiempo. :)

Cualquier tipo de modelado como este simplemente transforma un problema de clasificación en otro. No ganarás nada.