Struktura danych obsługująca o(1) dostęp losowy i najgorszy przypadek o (1) dołączenie?

Question

Struktura danych obsługująca o(1) dostęp losowy i najgorszy przypadek o (1) dołączenie?

Zdaję sobie sprawę, że indeksowana kolekcja, która używa tablicy do przechowywania swoich elementów (jak List<T> W. NET lub ArrayList w Javie), ma amortyzowany o(1) czas wstawiania na końcu kolekcji. Ale zawsze jest to jedna brzydka wstawka w krytycznych punktach, gdzie zbiór matylko osiągnął swoją pojemność, a następne wstawienie wymaga pełnej kopii wszystkich elementów w wewnętrznej tablicy na nową (przypuszczalnie dwa razy większą).

Częsty błąd (moim zdaniem) jest pójście z połączoną listą, aby" naprawić " ten problem; ale wierzę, że narzut przydzielania węzła dla każdego elementu może być dość marnotrawny, a w rzeczywistości przyćmiłby korzyści z gwarantowanego wstawiania O (1) w tym rzadkim przypadku, że wstawianie tablicy jest kosztowne-podczas gdy w rzeczywistości każde {7]}Inne {8]} wstawianie tablicy jest znacznie tańsze (i szybsze).

To, o czym myślałem, może mieć sens, to hybrydowe podejście składające się z połączonej listy tablic, gdzie za każdym razem aktualna tablica "head" osiąga swoją pojemność, nowa tablica dwa razy większa jest dodawana do listy linkowanych. Wtedy żadna Kopia nie będzie konieczna, ponieważ połączona lista nadal będzie miała oryginalną tablicę. Zasadniczo wydaje się to analogiczne (dla mnie) do podejścia List<T> LUB ArrayList, z tym wyjątkiem, że gdziekolwiek wcześniej ponosisz koszty kopiowania wszystkich elementów tablicy wewnętrznej, tutaj ponosisz tylko koszt przydzielenia nowej tablicy plus wstawianie pojedynczego węzła.

Oczywiście, to skomplikowałoby inne funkcje, gdyby były pożądane (np. wstawianie/usuwanie do/ze środka kolekcji); ale jak wyraziłem w tytule, tak naprawdę Szukam kolekcji add-only (i iterate).

Czy istnieją struktury danych idealnie nadające się do tego celu? A może sam sobie wymyślisz?

30

language-agnostic performance big-o arrays data-structures

Author: templatetypedef, 2011-01-29

Source

4 answers

Kiedy potrzebuję takiego kontenera, używam mojej implementacji struktury opisanej w "tablice z możliwością zmiany rozmiaru w optymalnym czasie i przestrzeni"

4

Author: AShelly,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-01-29 01:35:27

OK. To, co opisałeś, jest prawie dokładnie tym, co std::deque znajduje się w bibliotece standardowej C++. Różnica polega na tym, że tablica(zwykle) jest używana do przechowywania wskaźników do tablic podrzędnych zamiast używania listy połączonej.

1

Author: AraK,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-01-29 01:25:39

Jednym z pomysłów byłoby stworzenie listy kilku elementów, takich jak:

struct item
{
    int data[NUM_ITEMS];
    item *next;
}

W tym przypadku insert zajmie O(1) i jeśli osiągniesz limit, po prostu utwórz nowy blok i dołącz go do końca listy

0

Author: Elalfer,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-01-29 01:26:58

score 59 · Accepted Answer

Istnieje piękna struktura zwana rozszerzalną tablicą, która ma najgorsze wstawianie O(1) I O(n) narzutu pamięci (to znaczy, że jest asymptotycznie porównywalna do tablicy dynamicznej, ale ma o(1) najgorsze wstawianie). Sztuczka polega na podejściu, którego używa wektor - podwajanie i kopiowanie-ale aby kopiowanie było leniwe. Na przykład, załóżmy, że masz tablicę czterech elementów takich jak ta:

[1] [2] [3] [4]

Jeśli chcesz dodać nową liczbę, powiedzmy 5, zaczynasz od przydzielenia tablicy to jest dwa razy większe:

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

Następnie wstawiamy 5 do nowej tablicy:

[1] [2] [3] [4]
[ ] [ ] [ ] [ ] [5] [ ] [ ] [ ]

Na koniec ściągnij 4 ze starej tablicy do nowej:

[1] [2] [3] [ ]
[ ] [ ] [ ] [4] [5] [ ] [ ] [ ]

Od teraz, za każdym razem, gdy wykonasz wstawianie, Dodaj element do nowej tablicy i pociągnij w dół jeszcze jeden element ze starej tablicy. Na przykład po dodaniu 6 otrzymamy

[1] [2] [ ] [ ]
[ ] [ ] [3] [4] [5] [6] [ ] [ ]

Po wstawieniu dwóch kolejnych wartości kończymy tutaj:

[ ] [ ] [ ] [ ]
[1] [2] [3] [4] [5] [6] [7] [8]

Jeśli teraz musimy dodać jeszcze jeden element, odrzucamy teraz pustą starą tablicę i przydzielić tablicę dwa razy większą od bieżącej tablicy (mogącą pomieścić 16 elementów):

[1] [2] [3] [4] [5] [6] [7] [8]
[ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]

I powtórz ten proces. Pomijając koszt alokacji pamięci (który jest zwykle podlinkowany wielkością tablicy), wykonujesz co najwyżej O(1) pracę na wstawianie.

Lookupy są nadal O(1), ponieważ po prostu decydujesz, która z dwóch tablic ma zajrzeć, podczas gdy wstawki w środku to O(n) z powodu tasowania.

Jeśli jesteście ciekawi, mam implementację Javy tej struktury na mojej osobistej stronie. Nie wiem, jak przydatny go znajdziesz, ale możesz go wypróbować.

Mam nadzieję, że to pomoże!

edytuj: Jeśli chcesz zainwestować trochę czasu czytając pracę badawczą i próbując zaimplementować dość złożoną strukturę danych, możesz uzyskać ten sam wynik (najgorszy przypadek o (1) załączyć) w O (√n) przestrzeni napowietrznej (która jest provably optymalne, nawiasem mówiąc) za pomocą pomysły w tym artykule. I never got Około do faktycznego wdrożenia tego, ale na pewno warto przeczytać, jeśli pamięć jest bardzo deficytowym zasobem. Co ciekawe, wykorzystuje powyższą konstrukcję jako podprogram!