Raccolta ordinata di coppie di chiavi simili a code in codice JavaScript

Question

Raccolta ordinata di coppie di chiavi simili a code in codice JavaScript

#1 da (1 voti)

0

Sto cercando una collezione adatta al mio scenario:

Inserirò coppie di valori-chiave (entrambi i numeri interi) di ID e timestamp. L'ID deve essere unico.
A un certo intervallo controllerò quella raccolta per gli elementi "scaduti" (come nel timestamp + X < current_timestamp) e avremo bisogno di rimuovere la coppia chiave-valore e agire sulla chiave.

Ho affermato che sto cercando una raccolta ordinata, perché penso che con la raccolta ordinata per valore (ordine discendente) potrei spezzare il ciclo sopra la raccolta nel punto in cui raggiungo prima la data / ora "scaduta" (ciò significherebbe resto di loro è attivo anche.

Prevedo che il 95% delle mie voci non sarà "scaduto" nel momento in cui eseguo il loop su di esse.

Ci saranno molti più inserimenti / modifiche che letture.

Non sono riuscito a trovare nulla che corrisponda a questo scenario, quello più vicino è SortedMap.

C'è qualcosa che sarebbe più adatto? Forse un approccio completamente diverso?

Penso che sia anche importante sottolineare che può contenere fino a 10000 chiavi (coppie).

Se c'è qualcuno con uno sfondo JavaScript (nodo), fornire anche alcuni collegamenti alle implementazioni sarebbe ottimo.

data-structures sorting map

posta pzaj 25.05.2017 - 19:28

fonte

1 risposta

Leggi altre domande sui tag data-structures sorting map

Esecuzione di più azioni su ogni riga di tabella da molti database Come includere più server in DFD

score 1 · Accepted Answer

Non è necessario avere una collezione singola che soddisfi le tue esigenze. Invece, puoi combinare due raccolte per ottenere le proprietà richieste. Quindi modifichi queste raccolte solo tramite un'interfaccia che garantisce che le due raccolte siano mantenute sincronizzate.

per l'unicità, mantieni un Set di ID.
per l'ordine, mantieni una coda di timestamp.

L'eliminazione delle voci precedenti richiede che sia possibile rimuovere gli ID dal Set, quindi è necessario trovare l'ID da un oggetto Coda. Potremmo quindi implementarlo come una mappa dagli ID ai timestamp e una coda di ID, ordinata in base al timestamp corrispondente.

Pseudocodice:

queue: min-priority queue for map[entry]

insert(map, queue, ID):
  map[ID] = now()
  queue.insert(ID)

delete-expired(map, queue):
  while map[queue.first] is expired:
    delete map[queue.first]
    queue.unqueue()

Ah, ma per quanto riguarda l'aggiornamento del timestamp? Se la memoria non è il fattore limitante, lascerei le vecchie voci in coda ma le contrassegnerò come non valide. Ciò rimanda la loro rimozione fino alla loro rimozione dalla coda.

queue: min-priority queue for entry.timestamp

insert(map, queue, ID):
  if ID in map:
    map[ID].valid = false
  entry = { timestamp: now(), id: ID, valid: true }
  map[ID] = entry
  queue.insert(entry)

delete-expired(map, queue):
  while queue is not empty:
    entry = queue.first

    if entry.valid and entry.timestamp is not expired:
      return

    delete map[entry.id]
    queue.unqueue()

In alternativa, è possibile eliminare la voce dal centro della coda. Tuttavia, la rimozione della coda in genere richiede la scansione o lo spostamento di tutti gli elementi nella coda ed è pertanto un'operazione che richiede molto tempo. Questa potrebbe essere la scelta corretta se sei vincolato alla memoria.

La coda di priorità può essere generalmente implementata come heap. Poiché si inseriscono solo elementi più recenti, anche una struttura di dati di tipo array potrebbe essere una buona scelta. Ma gli array dinamici (gli elenchi che JavaScript fornisce di default) non sono desiderabili in quanto gli elementi devono essere spostati regolarmente nello spazio liberato in primo piano dalle voci di dequeuing. Un'alternativa che non deve spostare elementi è un buffer circolare, che può essere reso auto-ridimensionato come un array dinamico.