La Gravedad De Ordenación :Es esto posible mediante programación?[cerrado]

Question

He estado pensando recientemente sobre el uso del diseño Orientado a Objetos en el algoritmo de ordenación.Sin embargo, yo no era capaz de encontrar una forma adecuada para siquiera acercarse en la fabricación de este algoritmo de ordenación que se hace la clasificación en O(n) tiempo.

Ok, aquí es lo que he estado pensando durante una semana.Tengo un conjunto de datos de entrada.Voy a asignar una masa para cada uno de los datos de entrada (asumir de entrada de datos de un tipo de Mass y un tipo de Sphere.Si asumimos que todos los objetos a ser perfectamente esférica de objetos con formas proporcional a su masa, la más pesada toca el suelo primero.).Voy a poner todos mis datos de entrada en el espacio de todos a la misma distancia de la tierra.Y voy a hacer que la caída libre.De acuerdo a la ley de gravitación, la más pesada golpea el suelo primero.Y el orden en el que de golpe me dará los datos ordenados.Esto es curioso, de alguna manera, pero en el fondo creo que esto debería ser posible el uso de los COJONES que he aprendido hasta la fecha

¿Es realmente posible hacer una clasificación de la técnica que utiliza la fuerza gravitacional, como escenario o soy estúpido/loco?

Editar: Resulta que todos los objetos de golpear el suelo, al mismo tiempo, de ahí que me introdujo el esférico el concepto de objeto.

Answer 1

La cosa es que, aunque uno de los Ideas de la programación orientada a objetos pueden ser para modelar el mundo real, eso no significa que no hay una correspondencia directa entre el tiempo que algo tiene en el mundo real y el tiempo que se necesitaría para simularlo con un ordenador.

Imagine los pasos reales necesarios para su procedimiento:

1. Un objeto tiene que ser construido para cada artículo en su conjunto de datos. En la mayoría del hardware moderno, esto por sí solo requeriría iteración y por lo tanto hacer que su estrategia de O (n) en mejor .
2. El efecto de la gravedad tendría que ser simulado, para cada objeto. Una vez más, la manera más obvia, sencillo de implementar esto sería iterar.
3. El tiempo que cada tierras objeto sobre la superficie de la "tierra" en su modelo de programación tendrían que ser capturado y, a través de algún mecanismo específico de la implementación, tendría que ser insertada en una lista ordenada como resultado el objeto correspondiente .

Teniendo en cuenta el problema adicional introduce complicaciones adicionales. Pregúntese esto: ¿A qué altura Qué se necesita para posicionar estos objetos para empezar? Obviamente lo suficientemente alto como para que el uno más grande en realidad cae ; es decir, más lejos de la Tierra que el radio del objeto más grande. Pero, ¿cómo saber hasta qué punto es? Que había necesidad de determinar en primer lugar el objeto más grande en la colección; esto, de nuevo, sería (probablemente) requerir la iteración. Además, uno podría imaginar que esta simulación podría ser multiproceso para tratar de simular el comportamiento en tiempo real de la noción de objetos realmente que cae; pero luego se encontrará tratando de añadir elementos a una colección (una operación que, obviamente, tiene una cantidad no nula de tiempo), potencialmente, al mismo tiempo que se están detectando nuevas colisiones. Así que esto creará problemas de threads también.

En resumen, no tengo problemas para imaginar cómo esta idea podría ser adecuadamente implementado simplemente usando programación orientada a objetos sin necesidad de hardware especial. Dicho esto, lo que realmente es una buena idea. Me recuerda, de hecho, de Bead algoritmo de ordenación --un que, aunque no el mismo que su idea, también es una solución de clasificación que se aprovecha del concepto muy físico de la gravedad y, como es lógico, requiere hardware especializado.

Answer 2

Usted acaba de reexpresado el problema. Calcular el orden de los efectos gravitacionales tendrá, en el mejor, la O de los algoritmos de clasificación que está tratando de superar.

Answer 3

cálculo de la gravitación es gratis sólo en el mundo real. En Programm que necesita para modelarlo. Será otro n en lo más mínimo la complejidad

Answer 4

clasificación de propósito general es demostrable en el mejor de O (n log n). Para mejorar esto, usted tiene que saber algo acerca de los datos que no sea sólo la manera de comparar los valores.

Si los valores son todos los números, radix clasificación 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 un ordenador se representa usando números. Por ejemplo, puede radix-ordenar cadenas por, en cada pasada, la clasificación por un personaje como si fuera un dígito.

Desafortunadamente, el manejo de tamaños variables de los datos significa hacer un número variable de pases a través de la radix tipo. Se 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 firmar, la mitad que para firmado). Por ejemplo, si está ordenando los números enteros de 0 a m-1, así - que ha hecho tiene O (n log n) de nuevo

.

traducir un problema a otro puede ser un método muy bueno, pero a veces es simplemente añadiendo otra capa de complejidad y los gastos generales.

Answer 5

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 lo que está sucediendo en paralelo. Para modelar el tipo gravitacional como describiría usted tendría que empezar por pensar cada objeto en un hilo separado con un hilo de manera segura para añadirlos a una lista en el orden en que terminen. Siendo realistas en términos de rendimiento de clasificación es probable que sólo tiene que utilizar una especie rápido en los tiempos, o ya que están a la misma distancia de la tasa de caída. Sin embargo, si su fórmula es proporcional a la masa, usted acaba de saltarse todo eso y ordenar la masa.

Answer 6

En un "ordenador gravitatoria" ficticia este tipo de clasificación llevaría O (1) que hay que resolver. Pero con los ordenadores reales como la conocemos, el pensamiento lateral no ayudaría.

Answer 7

Una vez que haya calculado todas las veces que se toman para golpear el suelo, usted todavía tiene que ordenar esos valores. Usted no está realmente ganar nada, sólo toque lavar diferentes números después de realizar algunos cálculos innecesarios adicional.

Editar : Los chillidos. ¿Ha olvidado la física 101. Por supuesto, todos ellos se golpean al mismo tiempo. :)

Cualquier tipo de modelado como esto simplemente transforma un problema de clasificación en otra. Usted no va a ganar nada.

Answer 8

Haciendo caso omiso de todos los defectos que todo el mundo ha mencionado, esencialmente, esto se reduce a un O(n^2) algoritmo, no O(n).Tendrías que iterar sobre todas las "esferas", encontrar el más "pesadas" o "el más grande" y, a continuación, empuje en una lista, a continuación, enjuague y repita.es decir, para encontrar el que golpea el suelo primero, tienes que recorrer toda la lista, si es el último, me gustaría tomar O(n) el tiempo, la segunda se podría tomar O(n-1), etc...pero peor que eso, usted tiene que realizar un montón de operaciones matemáticas cada vez apenas para calcular algunos inútiles "tiempo" value cuando se podría haber clasificado en el valor que estaban interesados en en el primer lugar.

Answer 9

Hmmmm. Gravedad tipo.

Haciendo caso omiso de su modelo específico de gravedad está mal, vamos a ver donde esta idea nos lleva.

La realidad física tiene 10 ^ 80 procesadores.

Los límites inferiores reales de tipo es conocido por ser log (N) si tiene N 2 procesadores / para ordenar N objetos.

Si tiene varios núcleos de CPU disponibles no hay razón por la que no se puede ejecutar mergesort en varios hilos.

Answer 10

En realidad, hay una muy famoso algoritmo de ordenación denominada espaguetis especie que es algo así similar a la suya. Se puede extraer de algunos de los muchos análisis de la misma en la web. p.ej. en cstheory .

Answer 11

Debe ser sin duda única que debe tener el hardware adecuado compatible con él. De lo contrario, esto parece una idea muy fresca. Espero que alguien presenta un documento IEEE para hacer de este sueño loco visualizado.

Answer 12

Me encanta la idea! Es inteligente. Mientras que sí lo que otros dicen es en general correcta, que el O (n log n) unido es un demostrablemente límite inferior en el problema de la separación en general, tenemos que tener en cuenta que ese límite inferior es cierto sólo para base los modelos de comparación. Lo que aquí se propone es un modelo completamente diferente, que se merece mayor 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, es obvio que hay que adaptar el modelo a algo donde el objeto más pesado (número) sería de hecho viajar más rápido / más (o lento / más menos) para que de alguna manera puede distinguir los números (una centrífuga viene a la mente también).

requiere más pensamiento, pero su idea es fuerte!

(Edit) Mira ahora en Phys2D idea de Enrique, creo que tiene mucho más sentido.

Una cosa que sugeriría es ignorar definitivamente el aspecto de eficiencia por ahora. (Ya sé, ya sé que era la meta entera). Se trata de un nuevo modelo, y lo primero que tiene que cerrar la brecha entre la idea y su puesta en práctica. Sólo entonces podemos comprender lo que significa la complejidad del tiempo incluso para este modelo.

Answer 13

Creo que el problema puede ser más sencilla como esto: usted quiere poner el fondo de las esferas a diferentes alturas de modo que cuando se deja caer en gravedades idénticas la mayor tocará el suelo primero, segundo, etc. segundo mayor Esto es esencialmente equivalente a usar líneas en lugar de esferas ... en cuyo caso sólo se puede decir que heightOffTheGround = MAX_VALUE -. masa

Es posible que no necesita preocuparse por la aceleración con el tiempo ... ya que no importa lo rápido que van o física realista, se puede dar a todos una velocidad inicial x, e ir de allí.

El problema es entonces que nos hemos esencialmente sólo reexpresamos el problema y lo resolvimos como esto (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 en iteración cada unidad de tiempo, y que será O (1) ... con un muy constante grande ... el número constante de valores delta que el sistema se ejecutará en. El inconveniente es que para la gran mayoría de estos valores delta, básicamente van a estar recibiendo más cerca de la respuesta: en cualquier iteración dada, es muy probable que todas las esferas / líneas / lo que se habrá movido ... pero ninguno golpeará.

Se podría tratar de simplemente decir, bueno, vamos a omitir una gran cantidad de pasos intermedios y acaba de saltar por delante hasta que uno de visitas! Pero eso significa que usted tiene que saber cuál es el más grande ... y ya está de nuevo a la cuestión de la clasificación.

Answer 14

Voy a adaptar su idea un poco. Tenemos nuestros objetos, pero no difieren en el peso, pero en velocidad. Así, al principio todos los objetos se alinean en la línea de partida y en el disparo de salida, todos ellos se mueven con sus respectivas velocidades hasta el final.

Borrar suficiente: Primer objeto en acabado emitirá una señal, diciendo que es allí. Se captura la señal y escribir en el papel de resultados quién era.

De acuerdo, así que es conveniente para simular eso.

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

El punto es que ahora, con el fin de distinguir entre dos objetos con velocidades muy cercanas, usted necesita tener un tamaño de paso diferente para todos sus objetos.

Ahora, en el mejor caso, esto significa que objeto 1 acabados en un solo paso, 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 N∙N orden.

Si no es el mejor de los casos y las velocidades no son igual de cerca uno del otro, tendrá que reducir el tamaño del paso y, en efecto, iterar muchas veces más.

Answer 15

Si un equipo se construye en que se ordenan los objetos de la base de ciertos criterios (que no es totalmente ridículo pensar), entonces creo que el orden de complejidad no tendría nada que ver con el número de objetos, sino más bien la tasa de local de la aceleración debida a la gravedad.Asumiendo que es modelada en la Tierra, la complejidad sería O(g₀) donde g₀ es:

El simple razonamiento es que el número de objetos esféricos (n) es irrelevante si sus centros están alineados en el inicio.Por otra parte, la aceleración debida a la gravedad tendrá un impacto mucho más grande que la altura de sí misma a medida que aumenta.Por ejemplo, si se aumenta la altura de todos los objetos de 10x, no tarda ellos 10x el momento de golpear el suelo, pero mucho menor.Esto incluye varios insignificante aproximaciones como la aceleración en realidad depende de la distancia entre dos objetos, pero que pueden ser ignorados como estamos más interesados en una imagen más grande en lugar de un valor específico.

Brillante idea, sin embargo.

También, me encanta la moneda de ordenación video publicado por @Jeremy.Y, finalmente, objeto de orientedness sería el menor de mis preocupaciones en la construcción de una máquina.Pensar más sobre él, aquí está mi estúpido granito de arena en la construcción de una máquina:

O 0 o O o

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

Todos los objetos son de diferentes tamaños proporcionales a los criterios que desee ordenar.Inicialmente se mantienen juntas horizontalmente por una fina varilla que pasa por el centro de cada esfera.El = en la parte inferior están especialmente diseñadas para el registro de un valor (opcionalmente su posición) en un lugar tan pronto como se chocan con una esfera.Después de todas las esferas chocan, vamos a tener nuestra orden basado en los valores registrados.

Answer 16

  

partir de Debilski respuesta :

     

Voy a adaptar su idea un poco. Hacemos   Disponemos de objetos, pero no difieren   en peso, pero en la velocidad. Así, en el   comenzando todos los objetos están alineados en   la línea de salida y en la partida   tiro, todos ellos se mueven con su   respectivas velocidades hasta el final.

     

Borrar suficiente: Primer objeto en acabado   emitirá una señal, diciendo que es   ahí. Se captura la señal y escribir   a los resultados de papel que era

Me simplificar un paso más allá y decir que estos objetos son números enteros positivos al azar. Y queremos que los clasifique en un orden ascendente cuando se acercan a cero, por lo que tienen un Distancia de cero d que inicialmente es igual a la propia entero.

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

El problema es, que es lineal para un cuadro solamente! Se multiplica por el número de fotogramas f requieren para terminar. La simulación en sí es O (nf):. Cuadrática

Sin embargo, si tomamos la duración de una trama como el 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 viene a costa de la precisión, más aumentamos t, más la probabilidad de que dos objetos se terminan en el mismo período de tiempo, por tanto, ser considerada equivalente, incluso si no lo son. Por lo que tenemos un algoritmo con una precisión ajustable (como lo es en los contextos de simulación de elementos finitos más)

Podemos perfeccionar este convirtiéndola en una adaptación + algoritmo recursivo. En el código humana 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 real similar que funciona para otra.

tema interesante de hecho:)

PS. El pseudocódigo anterior es mi idea de pseudocódigo, no dude en volver a escribir de una forma más legible o conformes si es que existe.

Answer 17

Hace

Algunas semanas yo estaba pensando en lo mismo.

pensé usar Phys2D biblioteca para ponerlo en práctica. Puede que no sea práctico, pero sólo por diversión. También puede asignar pesos negativos a los objetos para representar números negativos. Con la biblioteca phys2d se puede definir la gravedad para objetos con peso negativo irán a la azotea y objetos con peso positivo se va a caer .A continuación, organizar todos los objetos en el medio entre el suelo y el techo con la misma distancia entre el suelo y el techo. Suponga que tiene una matriz resultante [] de longitud del número de objetos r =. Entonces, cada vez que un objeto toca el techo que añadir que al comienzo de la matriz [0] r e incrementar el contador, la próxima vez que un objeto toca el techo que añadir que en r [1], cada vez que un objeto llega a la planta añadirlo al final de la matriz r [r.length-1], la próxima vez que lo agregue en r [r.length-2]. En los objetos finales que no se movían (quedaron flotando en el medio) puede ser añadido en el medio de la matriz (estos objetos son el 0 de).

Esto no es eficiente, pero puede ayudarle a implementar su idea.

Answer 18

1. Creo que es buen mencionar / referirse a: ¿Cuál es la relación entre P versus NP y de la naturaleza habilidad para resolver problemas NP eficiente? La clasificación es O(nlog(n)), ¿por qué no tratar de resolver los problemas NP-duro?
2. Por las leyes de la física de los objetos caen con proporciones a la constante gravitacional la masa es despreciable.
3. Simulación de un proceso físico puede afectar a la complejidad en tiempo real.

Answer 19

Analizar: (1) Todos los centros de las esferas están alineados al inicio (2) mayor número ==> mayor masa ==> radio mayor ==> distancia al suelo inferior (3) en el 'vacío' misma aceleración = misma evolución velocidad ==> misma distancia para el centro ==> cómo mayor de radio ... la forma anterior de la esfera tocará el suelo ==> conceptualmente bien, buena técnica física si cuando una esfera de caer al suelo se puede enviar una señal de identificacion + tiempo de golpear ... wich dará la lista ordenada Prácticamente ... no es una 'buena' técnica numérica