Esiste un nome per questa raccolta di strutture di dati di array ordinati?

Esiste un nome per la seguente struttura dati? Ci sono documenti e citazioni disponibili?Esiste un nome per questa raccolta di strutture di dati di array ordinati?

Un modo to implement un efficiente insieme astratto tipo di dati è quello di avere un insieme di matrici ordinate, dove ogni matrice ha una dimensione unica potenze di 2.

Ad esempio, un insieme di 13 elementi {1, 2, ..., 13} può essere rappresentato da questa raccolta di array ordinati: {[5], [2, 3, 9, 13], [1 , 4, 6, 7, 8, 10, 11, 12]}.

In generale, gli array presenti nella raccolta hanno dimensioni corrispondenti a 1 bit nella rappresentazione binaria della dimensione dell'insieme. La struttura dei dati è efficiente perché inserimento può essere eseguita in ammortizzato O (1) tempo, e ricerca può essere eseguita in O ((log n)) tempo (che è migliore di ricerca lineare). Inoltre, utilizza solo O (log n) perdita di spazio per i puntatori, a differenza di alberi binari bilanciati e B-alberi che utilizzano O (n) spazio in più per i puntatori. Pertanto, quasi tutto lo spazio viene utilizzato per i dati del carico utile.

Ho visto Wikipedia di list of data structures ma non ho trovato una corrispondenza. È vero che il libro Introduction to Algorithms ("CLRS") descrive questa struttura di dati come un problema di compiti a casa nella sezione "Analisi ammortizzata", ma poiché è una domanda piuttosto che un esempio, il libro non dice molto su di esso.

fonte

2013-06-07 Nayuki

Ho potuto solo pensare al tag "strutture dati". Gradirei suggerimenti per tag pertinenti! – Nayuki

Queste domande esistenti riguardano la stessa struttura dati, ma chiedono informazioni su implementazione e spiegazione: http://stackoverflow.com/questions/2602110/, http://stackoverflow.com/questions/4701433/. So come funziona la struttura dati, quindi sono specificamente alla ricerca di pubblicazioni su questo. – Nayuki

Un'idea simile risale almeno a original publication on binomial heaps di Jean Vuillemin nel numero di aprile 1978 di CACM. Mi aspetterei che il documento che ha introdotto questa struttura dati citi o venga citato da Vuillemin, ma nessuno dei documenti sulle liste "referenze" e "citato da" appare promettente.

Se fossi in te, vorrei chiedere cstheory e poi scrivo CLRS, ma dato i limiti non ottimali e la mancanza di cancellazione, non mi aspetto nulla di alzare a meno che la comunità succinct data structure si è interessato a un certo punto.

C'è qualcosa in particolare che volevi sapere?

fonte

2013-06-07 17:32:43

Grazie per il riferimento SE: cstheory e succinti DSes, che sono rilevanti ma nuovi per me. Ho fatto la domanda perché voglio scrivere per questa struttura dati, cosa che posso fare. Ma voglio dargli un nome già accettato, e voglio anche costruire sulla letteratura esistente invece di basarmi solo sulle mie idee. – Nayuki

È vero che il tempo di ricerca è subottimale, ma ho approfittato della brevità di una delle mie applicazioni perché aveva bisogno di mantenere in memoria milioni di stati di gioco già visitati. Per quanto riguarda la cancellazione, CLRS dice "Discuti come implementare DELETE.", Ma su un pensiero leggero non riesco a pensare a nessun modo ovvio per implementarlo entro il tempo O (n log n) ancora ammortizzato ... – Nayuki

@NayukiMinase Vieni a pensateci, la cancellazione dovrebbe essere ammortizzata anche O (1), con il solito espediente di avere bitmap che indicano elementi non eliminati e unendo un array semivuoto verso il basso. –

Esiste un nome per questa raccolta di strutture di dati di array ordinati?

risposta

Problemi correlati