Conserva la raccolta ordinata aggiornando il minor numero possibile di campi 'ordine'

Question

Conserva la raccolta ordinata aggiornando il minor numero possibile di campi 'ordine'

#1 da (3 voti)

4

Sto lavorando per integrare un widget UI di elenchi riordinabili con una raccolta Meteor.js (MongoDB, in effetti):

{
  order: ???,  // what type to use here?
  property1: ...,
  ...
  propertyN: ...
}

Ogni documento nella raccolta ha un campo order . L'interfaccia utente ottiene la raccolta dal server, la ordina dal campo order e la visualizza in un elenco. Quando l'utente trascina un elemento in una nuova posizione nell'elenco, ottengo il oldIndex del documento e il newIndex relativo all'inizio dell'elenco (dove è stato rilasciato). Ora devo aggiornare il campo order e salvare i documenti interessati nella raccolta.

Quale dovrebbe essere la natura del campo order per ridurre al minimo il numero di aggiornamenti, ma non limitare il numero di volte in cui un documento può essere riordinato?

Una implementazione ingenua utilizza interi e imposta order del oggetto caduto alla media aritmetica dei documenti prima di un dopo. Naturalmente, questo verrà eseguito in limiti di precisione in virgola mobile (50 riordini in JavaScript se inizi con interi consecutivi).

Un'altra implementazione (suggerita anche in questa domanda cambierebbe il order di tutti i documenti intermedi tra oldIndex e newIndex del documento rilasciato, o tra l'inizio / la fine dell'elenco e l'articolo scartato (che coinvolge meno elementi). Ovviamente, questo è meno efficiente, in particolare per le liste più grandi.

Qualcosa di più intelligente? Usando una stringa o un oggetto di qualche tipo per il campo order ?

collections list order

posta Dan Dascalescu 15.12.2014 - 01:42

fonte

1 risposta

Leggi altre domande sui tag collections list order

Progettazione, come utilizzare l'hardware (più thread e / o GPU) durante l'indicizzazione (tramite un database) di un set molto grande di file binari Come gestire la logica personalizzata per più clienti

score 3 · Answer 1

Una soluzione ovvia è usare aritmetica di precisione arbitraria.

Come implementazione con big.js :

var Big = require('./big.js');

function average(x, y) {
  // exact result; .div(2) requires specifying .DP
  return Big(x).plus(y).times(0.5);
}

var x = new Big(1);
var y = new Big(2);

for (i = 0; i <= 10; i++) {
  x = average(x, y);
  console.log(x.toString());
}

Lo svantaggio, ovviamente, è che ogni riordino aggiungerà un byte al campo order . Un metodo normalize potrebbe analizzare gli ordini e convertirli in 0..N.