Che cos'è una struttura dati con O (1) per aggiungere, anteporre e recuperare elementi in qualsiasi posizione?

Question

Sto cercando una soluzione Java ma qualsiasi risposta generale è OK.

Vector/ArrayList è O (1) per aggiungere e recuperare, ma O (n) per anteporre.

LinkedList (in Java implementato come doppiamente-linked-list) è O (1) per append e prepend, ma O (n) per il recupero.

Deque (ArrayDeque) è O (1) per tutto quanto sopra ma non può recuperare elemento su un indice arbitrario.

Nella mia mente una struttura di dati che soddisfa il requisito di cui sopra ha 2 liste crescibili all'interno (una per ante e una per append) e memorizza anche un offset per determinare dove ottenere l'elemento durante il recupero.

Answer 1

Stai cercando una coda a doppio attacco. Questo è implementato nel modo in cui lo si desidera nel C++ STL, che è possibile indicizzare in esso, ma non in Java, come hai notato. Si potrebbe concepire il rollover dai componenti standard usando due array e memorizzando dove è "zero". Questo potrebbe essere uno spreco di memoria se si finisce per spostarsi da zero, ma se si arriva troppo lontano è possibile rebase e consentire al deque di eseguire la scansione in un nuovo array.

Una soluzione più elegante che non richiede davvero tanta fantasia nella gestione di due array è quella di imporre un array circolare su un array pre-assegnato. Ciò richiederebbe l'implementazione di push_front, push_back e il ridimensionamento dell'array dietro di esso, ma le condizioni per il ridimensionamento e simili sarebbero molto più pulite.

Answer 2

La tua idea potrebbe funzionare. Se quelle sono le sole operazioni che devi supportare, allora sono sufficienti due Vettori (chiamali Testa e Coda). Per anteporre, si aggiunge alla testa, e per aggiungere, si aggiunge alla coda. Per accedere a un elemento, se l'indice è inferiore a head.Length, quindi restituire head [head.Length-1-index], altrimenti restituire tail [index-head.Length]. Tutte queste operazioni sono chiaramente O (1).

Answer 3

Se trattate accodare ad un vettore/ArrayList come O (1) - che in realtà non è, ma potrebbe essere abbastanza vicino in pratica -
(EDIT - per chiarire - accodamento può essere ammortizzato costante di tempo , in media, l'aggiunta sarebbe O (1), ma potrebbe essere un po 'peggio per i picchi: a seconda del contesto e delle costanti esatte, questo comportamento può essere mortale).

(Questo non è Java, ma un linguaggio inventato ...).

Un vettore che verrà chiamato "Inoltra". Un secondo vettore che sarà chiamato "Indietro".

Alla richiesta di aggiungere - Forward.Append().

Alla richiesta di anteporre - Backwards.Append().

Quando ha chiesto di interrogare -

if (Index < Backwards.Size()) 
{ 
    return Backwards[ Backwards.Size() - Index - 1 ] 
} 
else 
{ 
    return Forward[ Index - Backwards.Size() ] 
} 

(e di controllare anche per l'indice di essere fuori dai limiti).

Answer 4

Quello che si desidera è una coda a doppio attacco (deque) come la STL, dal momento che Java ArrayDeque non è compatibile con get().Ci sono stati alcuni buoni suggerimenti e collegamenti ad implementazioni qui:

• Java equivalent of std::deque?

Answer 5

Un deque (Deque) può essere implementato per fornire tutte queste operazioni in O (1) tempo, anche se non tutte le implementazioni fanno. Non ho mai usato ArrayDeque di Java, quindi ho pensato che stavi scherzando sul fatto che non supportava l'accesso casuale, ma hai assolutamente ragione - come un deque "puro", consente solo un facile accesso alle estremità. Posso capire perché, ma quello è sicuramente fastidioso ...

Per me, il modo ideale per implementare una deque estremamente veloce è utilizzare uno circular buffer, soprattutto perché si è interessati solo ad aggiungere la rimozione nella parte anteriore e posteriore. Non ne sono immediatamente a conoscenza in Java, ma ne ho scritto uno in Objective-C come parte di un framework open source. Sei libero di usare il codice, sia come-sia che come modello per implementare il tuo.

Ecco uno WebSVN portal to the code e lo related documentation. La vera carne è nel file CHAbstractCircularBufferCollection.m - cerca i metodi appendObject: e prependObject:. È anche definito un enumeratore personalizzato ("iteratore" in Java). La logica buffer circolare essenziale è abbastanza banale, ed è catturato in questi 3 centralizzati #define macro:

#define transformIndex(index) ((headIndex + index) % arrayCapacity) 
#define incrementIndex(index) (index = (index + 1) % arrayCapacity) 
#define decrementIndex(index) (index = ((index) ? index : arrayCapacity) - 1) 

Come si può vedere nel metodo objectAtIndex:, tutto si fa per accedere all'elemento Nth in una deque è array[transformIndex(N)]. Nota che faccio tailIndex puntare sempre a uno slot oltre l'ultimo elemento memorizzato, quindi se headIndex == tailIndex, l'array è pieno, o vuoto se la dimensione è 0.

Sperare che aiuti. Le mie scuse per la pubblicazione di codice non Java, ma l'autore della domanda ha fatto dire che le risposte generali erano accettabili.

Answer 6

Ecco una struttura dati che supporta O (1) append, anteporre, first, last e size. Siamo in grado di aggiungere facilmente altri metodi da AbstractList<A> quali delete e update

import java.util.ArrayList; 

public class FastAppendArrayList<A> { 
    private ArrayList<A> appends = new ArrayList<A>(); 
    private ArrayList<A> prepends = new ArrayList<A>(); 

    public void append(A element) { 
     appends.add(element); 
    } 

    public void prepend(A element) { 
     prepends.add(element); 
    } 

    public A get(int index) { 
     int i = prepends.size() - index; 
     return i >= 0 ? prepends.get(i) : appends.get(index + prepends.size()); 
    } 

    public int size() { 
     return prepends.size() + appends.size(); 
    } 

    public A first() { 
     return prepends.isEmpty() ? appends.get(0) : prepends.get(prepends.size()); 
    } 

    public A last() { 
     return appends.isEmpty() ? prepends.get(0) : appends.get(prepends.size()); 
    }