Ordinamento efficiente di oggetti online

Question

Ordinamento efficiente di oggetti online

#1 da (2 voti)

1

Ho una lista con oggetti memorizzati in un database. Questi oggetti sono mostrati in un elenco e l'utente può trascinarli e rilasciarli per ordinarli in un modo specifico. Voglio che l'ordine specifico venga archiviato.

Come posso farlo in modo efficiente? Ho pensato alle seguenti opzioni:

Mantenere una matrice con l'ordine desiderato. La matrice può essere memorizzata localmente (non un'opzione nel mio progetto corrente) o online (tabella extra :(). Non mi piace molto questa soluzione.
Aggiungi un campo "priorità" a ciascun oggetto e ordina gli oggetti per esso. Trascinando e rilasciando la priorità di un oggetto si cambia in un valore < l'oggetto sopra e > rispetto all'oggetto sottostante. Dovrebbe esserci un grande margine tra questi valori di priorità, oppure dovrei usare dimezzare i numeri / float (infinito alla definizione float della piattaforma). Altrimenti uno potrebbe finire per provare a decidere quale numero è più grande di 2 e più piccolo di 3, per esempio. Aggiorna solo l'oggetto aggiornato.
Come 2. ma aggiorna TUTTI gli oggetti dopo un'operazione di trascinamento e rilascio e li memorizza tutti. Questo sembra un po 'inefficiente e inutile.

Mi manca l'ovvio? C'è un modo migliore?

programming-logic

posta Mathijs 30.03.2015 - 16:18

fonte

1 risposta

Leggi altre domande sui tag programming-logic

Come organizzare grandi progetti poliglotta? I documenti di metodo differiscono tra documenti Java e documenti Android

score 2 · Accepted Answer

Probabilmente stai pensando troppo all'aspetto dell'efficienza. Qualsiasi elenco abbastanza piccolo da essere umano da riordinare ragionevolmente tramite il trascinamento della selezione è banale da manipolare per un computer, anche con algoritmi molto "inefficienti". Tieni anche presente che gli umani sono molto lenti e l'aggiornamento dell'ordine è un'operazione relativamente poco frequente rispetto alle query per questo.

Tuttavia, ritengo che l'algoritmo con i migliori compromessi tra tempo di interrogazione e tempo di aggiornamento sia quello che chiamo l'algoritmo BASIC. I programmi BASIC utilizzavano numeri di linea interi per semplificare la programmazione interattiva. Perché potresti dover inserire una linea tra due linee, inizieresti a numerarle per 10 secondi. Se avessi bisogno di inserire una linea, lo faresti un multiplo di 5, e così via. Se hai esaurito lo spazio intermedio, c'era un comando renum che riportava tutto a multipli di 10.

Utilizzare questo metodo per ordinare gli oggetti significherebbe la maggior parte del tempo, è sufficiente aggiornare una riga, con la rinumerazione occasionale dell'intero elenco quando si esaurisce lo spazio nel mezzo. Poiché i numeri non sono visibili all'utente, è possibile inserire un po 'di spazio intermedio, quindi le rinumerazioni dovrebbero essere relativamente rare. Questo ti dà un peggior aggiornamento di O(n) , ma un aggiornamento ammortizzato vicino a O(1) .