Co to jest struktura danych, która ma O (1) do dołączania, wstawiania i pobierania elementu w dowolnym miejscu?

Question

Szukam rozwiązania Java, ale jakakolwiek ogólna odpowiedź jest również OK.

wektor/ArrayList O (1) na potrzeby dołączenia i pobierania, a O (n) w przypadku PREPEND.

LinkedList (Jawa realizowane jako podwójnie związany z listy) O (1) na potrzeby dołączenia i PREPEND, ale O (n) w przypadku pobierania.

deque (ArrayDeque) wynosi O (1) za wszystko powyżej, ale nie można pobrać elementu na arbitralne indeksu.

Moim zdaniem struktura danych, które spełniają powyższe wymaganie, ma w środku 2 listy do przechowywania (jedną dla przedrostka i jedną dla dołączenia), a także przechowuje przesunięcie w celu ustalenia, gdzie element ma zostać pobrany podczas pobierania.

Answer 1

Poszukujesz podwójnej kolejki. Jest to zaimplementowane tak, jak chcesz w C++ STL, który możesz indeksować do niego, ale nie w Javie, jak zauważyłeś. Można sobie wyobrazić użycie własnych standardowych komponentów za pomocą dwóch tablic i zapisanie, gdzie jest "zero". Może to być marnotrawstwem pamięci, jeśli skończysz poruszać się daleko od zera, ale jeśli zajdziesz za daleko, możesz zmienić bazę i pozwolić, by deque przeszła do nowej tablicy.

Bardziej eleganckie rozwiązanie, które naprawdę nie wymagają tyle fanciness w zarządzaniu dwóch tablic jest narzucenie okrągły tablicę na wstępnie przydzielone tablicy. Wymagałoby to implementacji funkcji push_front, push_back i zmiany rozmiaru tablicy za nią, ale warunki zmiany rozmiaru i takie byłyby znacznie czystsze.

Answer 2

Twój pomysł może zadziałać. Jeśli są to jedyne operacje, które musisz obsłużyć, to potrzebujesz tylko dwóch Wektorów (nazwij ich Głowie i Ogonem). Aby zacząć, dołączaj do głowy i dołączaj, dołączaj do ogona. Aby uzyskać dostęp do elementu, jeśli indeks jest mniejszy od head.Length, to należy zwrócić głowę [head.Length-1-index], w przeciwnym razie zwrócić tail [index-head.Length]. Wszystkie te operacje są wyraźnie O (1).

Answer 3

Jeśli traktujesz dołączyć do ArrayList jako wektor/O (1) - co to naprawdę nie jest, ale może być na tyle blisko, w praktyce -
(EDIT - wyjaśnienie - Dołącz mogą być amortyzowane stały czas , to jest - średnio, dodatek byłby O (1), ale może być nieco gorszy na szczytach, w zależności od kontekstu i dokładnych stałych, to zachowanie może być śmiertelne).

(To nie jest Java, ale jakiś wymyślony język ...).

Jeden wektor, który zostanie nazwany "Prześlij dalej". Drugi wektor, który zostanie nazwany "wstecz".

Po wyświetleniu prośby o dołączenie - Forward.Append().

Po wyświetleniu prośby o dodanie - Backwards.Append().

Pytany kwerendy -

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

(a także sprawdzić indeksu będącego poza zakresem).

Answer 4

Potrzebna jest podwójnie zakończona kolejka (deque) podobna do STL, ponieważ Java ArrayDeque z jakiegoś powodu nie ma get().Było kilka dobrych sugestie i linki do implementacji tutaj:

• Java equivalent of std::deque?

Answer 5

deque (kolejka dwukierunkowa) mogą być realizowane, aby zapewnić wszystkie te operacje w czasie O (1) czasu, chociaż nie wszystkie wdrożenia to robią. Nigdy nie korzystałem z Java ArrayDeque, więc myślałem, że żartujesz, że nie obsługuje on dostępu losowego, ale masz absolutną rację - jako "czysty" deque, pozwala on tylko na łatwy dostęp na końcach. Rozumiem, dlaczego, ale to na pewno jest denerwujące ...

Dla mnie idealnym sposobem na wdrożenie wyjątkowo szybkiego deque jest użycie circular buffer, szczególnie, że jesteś zainteresowany tylko dodaniem usuwania z przodu iz tyłu. Nie jestem natychmiast świadomy jednego w Javie, ale napisałem jeden w Objective-C jako część open-source framework. Możesz użyć kodu tak jak jest lub jako wzorzec do implementacji własnego.

Oto WebSVN portal to the code i related documentation. Prawdziwe mięso znajduje się w pliku CHAbstractCircularBufferCollection.m - poszukaj metod: CHAbstractCircularBufferCollection.m. Istnieje również zdefiniowany niestandardowy moduł wyliczający ("iterator" w Javie). Zasadniczą okrągły logika bufor jest dość trywialne i jest ujęte w tych 3 scentralizowanych #define makr:

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

Jak widać w sposobie objectAtIndex:, wszystko, co zrobić, aby uzyskać dostęp do elementu n-tym w deque jest array[transformIndex(N)]. Zauważ, że robię tailIndex zawsze wskazywać na jeden slot poza ostatnim zapisanym elementem, więc jeśli headIndex == tailIndex, tablica jest pełna lub pusta, jeśli rozmiar wynosi 0.

Nadzieję, że pomaga. Moje przeprosiny za opublikowanie kodu innego niż Java, ale pytanie autora czy powiedzieć ogólne odpowiedzi były dopuszczalne.

Answer 6

Oto struktura danych, która obsługuje O (1), append, prepend, first, last i size. Możemy łatwo dodać inne metody z AbstractList<A> takich jak delete i 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()); 
    }