Ordinamento per gravità:Questo è possibile a livello di programmazione?[Chiuso]

Question

Recentemente ho pensato di utilizzare la progettazione orientata agli oggetti nell'algoritmo di ordinamento.Tuttavia non sono riuscito a trovare un modo adeguato per avvicinarmi ancora di più alla realizzazione di questo algoritmo di ordinamento che esegue l'ordinamento in tempo O (n).

Ok, ecco cosa penso da una settimana.Ho una serie di dati di input.Assegnerò una massa a ciascuno dei dati di input (assumo che i dati di input siano di tipo Mass e un tipo di Sphere.Se assumiamo che tutti gli oggetti siano oggetti perfettamente sferici con forme proporzionali alla loro massa, quello più pesante tocca per primo il suolo.).Metterò tutti i miei dati di input nello spazio, tutti alla stessa distanza dalla terra.E li farò cadere liberamente.Secondo la legge gravitazionale, quello più pesante tocca terra per primo.E l'ordine in cui colpiscono mi darà i dati ordinati.In un certo senso è divertente, ma sotto sotto sento che dovrebbe essere possibile utilizzando l'OO che ho imparato fino ad oggi

È davvero possibile realizzare una tecnica di smistamento che utilizzi uno scenario simile all'attrazione gravitazionale o sono stupido/pazzo?

Modificare: Risulta che tutti gli oggetti colpiscono il suolo nello stesso momento, quindi ho introdotto il concetto di oggetto sferico.

Answer 1

Il fatto è che, sebbene uno dei idee di OOP può essere quello di modellare il mondo reale, ciò non significa che ci sia una corrispondenza diretta tra quanto tempo impiega qualcosa nel mondo reale e quanto tempo occorrerebbe per simularlo con un computer.

Immagina i passaggi effettivi richiesti per la tua procedura:

1. È necessario costruire un oggetto per ogni elemento nel set di dati.Sulla maggior parte dell'hardware moderno, questo da solo richiederebbe un'iterazione e quindi renderebbe la tua strategia O(n) at migliore.
2. L'effetto della gravità dovrebbe essere simulato, per ciascun oggetto.Ancora una volta, il modo più ovvio e diretto per implementarlo sarebbe l'iterazione.
3. Il tempo in cui ogni oggetto atterra sulla superficie della "Terra" nel tuo modello di programmazione dovrebbe essere catturato e, tramite un meccanismo specifico dell'implementazione, l'oggetto corrispondente dovrebbe essere inserito di conseguenza in un elenco ordinato.

Considerare ulteriormente il problema introduce ulteriori complicazioni.Chiediti questo:quanto in alto devi posizionare questi oggetti per iniziare?Ovviamente abbastanza alto da essere il più grande in realtà cascate;cioè, più lontano dalla Terra rispetto al raggio dell'oggetto più grande.Ma come fai a sapere quanto è lontano?Dovresti prima determinare l'oggetto più grande nella raccolta;questo, ancora una volta, richiederebbe (probabilmente) un'iterazione.Inoltre, si potrebbe immaginare che questa simulazione possa essere multithread per tentare di simulare il comportamento in tempo reale della nozione di oggetto In realtà cadente;ma poi ti ritroverai a tentare di aggiungere elementi a una raccolta (un'operazione che ovviamente richiede un tempo diverso da zero) potenzialmente nello stesso momento in cui vengono rilevate nuove collisioni.Quindi questo creerà anche problemi di threading.

In breve, ho difficoltà a immaginare come questa idea possa essere implementata correttamente semplicemente utilizzando l'OOP senza hardware speciale.Detto questo, davvero È una buona idea.Mi ricorda, infatti, di Ordinamento delle perline--un algoritmo che, sebbene non sia uguale alla tua idea, è anche una soluzione di smistamento che sfrutta il concetto fisico di gravità e, non a caso, richiede hardware specializzato.

Answer 2

Hai appena riaffermato il problema.Il calcolo dell'ordine degli effetti gravitazionali avrà, nella migliore delle ipotesi, l'O degli algoritmi di ordinamento che stai cercando di battere.

Answer 3

Il calcolo della gravitazione è gratuito solo nel mondo reale.Nel programma devi modellarlo.Sarà un altro n di complessità minima

Answer 4

L'ordinamento per scopi generali è probabilmente nella migliore delle ipotesi O(n log n).Per migliorare questo aspetto, devi sapere qualcosa sui dati oltre a come confrontare i valori.

Se i valori sono tutti numeri, ordinamento digitale restituisce O(n) presupponendo che siano presenti limiti superiore e inferiore per i numeri.Questo approccio può essere esteso per gestire qualsiasi numero e, in definitiva, tutti i dati in un computer vengono rappresentati utilizzando numeri.Ad esempio, è possibile ordinare in modo digitale le stringhe, in ogni passaggio, ordinandole per carattere come se fosse una cifra.

Sfortunatamente, gestire dimensioni variabili dei dati significa effettuare un numero variabile di passaggi attraverso l'ordinamento digitale.Alla fine otterrai O(n log m) dove m è il valore più grande (poiché k bit ti dà un valore fino a (2^k)-1 per senza segno, metà di quello con segno).Ad esempio, se stai ordinando i numeri interi da 0 a m-1, beh, in realtà hai di nuovo O(n log n).

Tradurre un problema in un altro può essere un ottimo approccio, ma a volte significa semplicemente aggiungere un altro livello di complessità e sovraccarico.

Answer 5

L'idea potrebbe sembrare semplice, ma la differenza tra il mondo reale e quello modellato in questo caso è che nel mondo reale tutto avviene in parallelo.Per modellare l'ordinamento gravitazionale come descrivi dovresti iniziare pensando a ciascun oggetto su un thread separato con un modo thread-safe per aggiungerli a un elenco nell'ordine in cui finiscono.Realisticamente in termini di prestazioni di ordinamento probabilmente utilizzeresti semplicemente un ordinamento rapido sui tempi o, poiché sono alla stessa distanza, sulla velocità di caduta.Tuttavia, se la tua formula è proporzionale alla massa, salteresti tutto questo e ordineresti la massa.

Answer 6

In un immaginario "computer gravitazionale" questo tipo di ordinamento richiederebbe O(1) per essere risolto.Ma con i veri computer come li conosciamo, il tuo pensiero laterale non aiuterebbe.

Answer 7

Una volta calcolati tutti i tempi necessari per toccare il suolo, dovrai comunque ordinare questi valori.In realtà non stai guadagnando nulla, stai solo ordinando numeri diversi dopo aver eseguito calcoli extra non necessari.

MODIFICARE:Ops.Ho dimenticato la fisica 101.Naturalmente colpiranno tutti allo stesso tempo.:)

Qualsiasi tipo di modellazione come questa trasforma semplicemente un problema di ordinamento in un altro.Non otterrai nulla.

Answer 8

Ignorando tutti i difetti menzionati da tutti gli altri, essenzialmente questo si riduce a un O(n^2) algoritmo, no O(n).Dovresti scorrere tutte le "sfere", trovare quella "più pesante" o "più grande", quindi inserirla in un elenco, quindi risciacquare e ripetere.cioè, per trovare quello che tocca terra per primo, devi scorrere l'intero elenco, se è l'ultimo, ci vorrebbe O(n) tempo, il secondo potrebbe durare O(n-1), eccetera...ma peggio di così, devi eseguire ogni volta una serie di operazioni matematiche solo per calcolare qualche inutile valore "temporale" quando avresti potuto ordinare il valore che ti interessava in primo luogo.

Answer 9

Hmmmm.Ordinamento per gravità.

Ignorare il tuo modello specifico di gravità è sbagliato, vediamo dove ci porta questa idea.

La realtà fisica ha 10^80 processori.

È noto che il limite inferiore effettivo dell'ordinamento è log(N) se si dispone di N/2 processori per ordinare N oggetti.

Se sono disponibili diversi core della CPU, non c'è motivo per cui non sia possibile eseguire Mergesort su più thread.

Answer 10

In realtà esiste un algoritmo di ordinamento abbastanza famoso chiamato Spaghetti sort che è in qualche modo simile al tuo.Puoi controllare alcune delle numerose analisi sul web.per esempio.SU cteoria.

Answer 11

Dovrebbe essere sicuramente solo tu che dovresti avere l'hardware adeguato supportato per questo.Altrimenti sembra un'idea davvero interessante.Spero che qualcuno presenti un documento IEEE per visualizzare questo folle sogno.

Answer 12

Adoro l'idea!È intelligente.Mentre sì, quello che dicono gli altri è generalmente corretto, che il limite O(n log n) è un limite inferiore dimostrabile per il problema di ordinamento in generale, dobbiamo tenere presente che quel limite inferiore è vero solo per basato sul confronto Modelli.Quello che proponi qui è un modello completamente diverso e merita un’ulteriore riflessione.

Inoltre, come hanno sottolineato James e Matrix, quello più pesante non viaggia più velocemente di quello più leggero, ovviamente è necessario adattare il modello a qualcosa in cui l'oggetto più pesante (numero) viaggerebbe effettivamente più velocemente/più lontano (o più lentamente/meno ulteriormente) in modo da poter in qualche modo distinguere i numeri (mi viene in mente anche una centrifuga).

Richiede più riflessione, ma la tua idea è brillante!

(Modifica) Ora guardando l'idea Phys2D di Enrique, penso che abbia molto più senso.

Una cosa che suggerirei è di ignorare definitivamente l’aspetto dell’efficienza per ora.(Lo so, lo so che era l'intero obiettivo).È un nuovo modello e dobbiamo prima colmare il divario tra l’idea e la sua attuazione.Solo allora potremo comprendere cosa significhi la complessità temporale per questo modello.

Answer 13

Penso che il problema possa essere semplificato in questo modo:vuoi mettere il fondo delle sfere a diverse altezze in modo che, quando lasciate cadere a gravità identica, la più grande tocchi prima il suolo, la seconda più grande per seconda, ecc.Ciò equivale essenzialmente a usare linee anziché sfere... nel qual caso puoi semplicemente dire che altezzaOffTheGround = MAX_VALUE - massa.

Inoltre, non devi preoccuparti dell'accelerazione nel tempo... poiché non ti interessa la velocità con cui stanno andando o la fisica realistica, puoi dare a tutti loro una velocità iniziale x e partire da lì.

Il problema è quindi che essenzialmente abbiamo semplicemente riaffermato il problema e risolto in questo modo (pseudocodice):

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--
}

Il problema è che per far funzionare il motore fisico, devi ripetere ogni unità di tempo, e quella sarà O(1)...con a molto costante grande...il numero costante di valori delta su cui verrà eseguito il sistema.Lo svantaggio è che per la stragrande maggioranza di questi valori delta, essenzialmente non ti avvicinerai alla risposta:in ogni data iterazione, è molto probabile che tutte le sfere/linee/qualunque cosa si sia mossa... ma nessuna colpirà.

Potresti provare a dire semplicemente, beh, saltiamo molti passaggi intermedi e andiamo avanti finché non ne colpisce uno!Ma ciò significa che devi sapere qual è il più grande... e torni al problema dell'ordinamento.

Answer 14

Adatterò un po' la tua idea.Abbiamo i nostri oggetti ma non differiscono in peso, ma in velocità.Quindi, all'inizio tutti gli oggetti sono allineati sulla linea di partenza e durante la ripresa iniziale si muoveranno tutti con le rispettive velocità fino al traguardo.

Abbastanza chiaro:Il primo oggetto che arriva alla fine emetterà un segnale, dicendo che è lì.Prendi il segnale e scrivi sul foglio dei risultati chi era.

Ok, quindi ti consigliamo di simularlo.

Consideriamo la lunghezza del tuo campo L=1.Con dimensione del passo ∆t ciascuno dei tuoi N gli oggetti si muovono per una lunghezza di vᵢ∙∆t Al tempo.Ciò significa che ogni oggetto ha bisogno sᵢ = L / (vᵢ∙∆t) gradini prima di raggiungere il traguardo.

Il punto è ora che, per distinguere tra due oggetti con velocità molto vicine, dovrai avere una dimensione del passo diversa per tutti i tuoi oggetti.

Ora, nel migliore In questo caso, ciò significa che l'oggetto 1 termina in un passaggio, l'oggetto 2 in due e così via.Pertanto, il numero totale di passaggi è S = 1 + 2 + … + N = N∙(N + 1)/2.Questo è normale N∙N.

Se non è il caso migliore e le velocità non sono ugualmente vicine tra loro, dovrai ridurre la dimensione del passo e in effetti ripetere molte più volte.

Answer 15

Se si costruisse un computer in grado di ordinare gli oggetti in base a determinati criteri (il che non è del tutto ridicolo a pensarci), allora credo che l’ordine di complessità non avrebbe nulla a che fare con il numero di oggetti, ma piuttosto con il tasso di accelerazione locale a causa della gravità.Supponendo che sia modellato sulla Terra, la complessità sarebbe O(g₀) dove g₀ È:

Il semplice ragionamento è che il numero di oggetti sferici (n) è irrilevante se i loro centri sono allineati all'inizio.Inoltre, l'accelerazione dovuta alla gravità avrà un impatto molto maggiore dell'altezza stessa man mano che aumenta.Ad esempio, se aumentassimo l'altezza di tutti gli oggetti di 10 volte, non impiegherebbero 10 volte il tempo per toccare il suolo, ma molto meno.Ciò include varie approssimazioni trascurabili poiché l'accelerazione dipende in realtà dalla distanza tra due oggetti, ma ciò può essere ignorato poiché siamo più interessati a un quadro più ampio piuttosto che a un valore specifico.

Idea geniale comunque.

Inoltre, adoro il video sullo smistamento delle monete pubblicato da @Jeremy.E infine l'orientamento agli oggetti sarebbe l'ultima delle mie preoccupazioni nella costruzione di una macchina del genere.Pensandoci più a fondo, ecco i miei stupidi due centesimi sulla costruzione di una macchina del genere:

O 0 o O o

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

Tutti gli oggetti hanno dimensioni variabili proporzionali ai criteri in base ai quali vogliamo ordinarli.Inizialmente sono tenuti insieme orizzontalmente da una sottile asta che attraversa il centro di ciascuna sfera.IL = in basso sono appositamente progettati per registrare un valore (opzionalmente la loro posizione) da qualche parte non appena entrano in collisione con una sfera.Dopo che tutte le sfere si saranno scontrate, avremo il nostro ordine in base ai valori registrati.

Answer 16

da La risposta di Debilski:

Adatterò un po' la tua idea.Abbiamo i nostri oggetti ma non differiscono in peso, ma alla velocità.Quindi, all'inizio tutti gli oggetti sono allineati sulla linea di partenza e sul tiro iniziale, si muoveranno tutti con le rispettive velocità al traguardo.

Abbastanza chiaro:Il primo oggetto in finitura emetterà un segnale, dicendo che è lì.Catturi il segnale e scrivi sul documento dei risultati chi era

Lo semplificherei ulteriormente e direi che questi oggetti sono numeri interi positivi casuali.E vogliamo ordinarli in ordine crescente man mano che si avvicinano allo zero, quindi hanno a distanza da zero d che inizialmente è uguale all'intero stesso.

Supponendo che la simulazione avvenga in fasi temporali discrete, ad es. cornici, in ogni fotogramma, la nuova distanza di ogni oggetto sarebbe: d = d - v e un oggetto verrebbe aggiunto all'elenco quando è d ≤ 0.Questa è una sottrazione e una condizionale.Due passaggi discreti per ciascun oggetto, quindi i calcoli sembrano essere O(n):lineare.

Il problema è che è lineare un fotogramma soltanto!Viene moltiplicato per il numero di fotogrammi f necessario per finire.La simulazione stessa è O(nf):quadratico.

Tuttavia, se prendiamo come argomento la durata di un fotogramma t abbiamo la possibilità di influenzare il numero di fotogrammi f in maniera inversamente proporzionale.Possiamo aumentare t ridurre f ma questo va a scapito della precisione, tanto più aumentiamo t, maggiore è la probabilità che due oggetti finiscano nello stesso intervallo di tempo e vengano quindi elencati come equivalenti, anche se non lo sono.Quindi otteniamo un algoritmo con precisione regolabile (come nella maggior parte dei contesti di simulazione agli elementi finiti)

Possiamo perfezionarlo ulteriormente trasformandolo in un algoritmo adattivo+ricorsivo.Nel codice umano sarebbe:

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

Mi chiedo se esiste una vera implementazione simile che funzioni per qualcuno.

Argomento interessante davvero :)

PS.Lo pseudocodice sopra è la mia idea di pseudocodice, sentitevi liberi di riscriverlo in un modo più leggibile o conforme se ce n'è uno.

Answer 17

Alcune settimane fa stavo pensando alla stessa cosa.

Ho pensato di usare Phys2D libreria per implementarlo.Potrebbe non essere pratico, ma solo per divertimento.Potresti anche assegnare pesi negativi agli oggetti per rappresentare numeri negativi.Con la libreria phys2d puoi definire la gravità in modo che gli oggetti con peso negativo vadano sul tetto e gli oggetti con peso positivo cadano. Quindi disponi tutti gli oggetti al centro tra il pavimento e il tetto con la stessa distanza tra pavimento e tetto.Supponiamo di avere un array risultante r[] di lunghezza=numero di oggetti.Quindi ogni volta che un oggetto tocca il tetto lo aggiungi all'inizio dell'array r[0] e incrementi il ​​contatore, la prossima volta che un oggetto tocca il tetto lo aggiungi a r[1], ogni volta che un oggetto raggiunge il pavimento tu aggiungilo alla fine dell'array r[r.length-1], la prossima volta lo aggiungi a r[r.length-2].Alla fine gli oggetti che non si sono mossi (sono rimasti fluttuanti nel mezzo) possono essere aggiunti al centro dell'array (questi oggetti sono gli 0).

Questo non è efficiente ma può aiutarti a implementare la tua idea.

Answer 18

1. Credo sia bello citare/riferire a: Qual è la relazione tra p vs.La capacità di NP e Natura di risolvere i problemi NP in modo efficiente?L'ordinamento è O(nlog(n)), perché non provare a risolvere i problemi NP-hard?
2. Secondo le leggi della fisica gli oggetti cadono con proporzioni rispetto acostante gravitazionale la massa è trascurabile.
3. La simulazione di un processo fisico può influenzare la complessità temporale effettiva.

Answer 19

Analizzare:; Stessa distanza per il centro ==> Come maggiore è il raggio ... come prima la sfera colpirà il terreno ==> concettualmente ok, buona tecnica fisica se quando una sfera colpisce il terreno può inviare un segnale di indentinzione + time di colpire .. .che darà all'elenco ordinato praticamente ... non una "buona" tecnica numerica