kiedy używać listy, a kiedy wektora?

Thread View: pl.comp.lang.c

3 messages

[T] Back to Threads [V] Tree View [G] Group Articles

3 total messages Started by M.M. Mon, 18 Apr 2016 15:41

#308447

Author: M.M.
Date: Mon, 18 Apr 2016 15:41

58 lines
3902 bytes

Kiedyś myślałem, że odpowiedź na pytanie w tytule jest prosta...

Główną wadą wektora jest to, że usuwanie elementu zachodzi w
pesymistycznym czasie N, a nawet w średnim 0.5*N. Niby wniosek
jest oczywisty: jeśli zajdzie konieczność usuwania elementów ze
środka wektora, to wszelkie prawdziwe lub potencjalne zalety
wektora zostaną pochłonięte przez straty z powolnego usuwania, 
więc należy użyć listy.

Ale ale ale...
Przecież można se na kolanie napisać (albo znaleźć gotowy)
wektor który zamiast typu T, przechowuje strukturę Item:

template<class T>
struct Item {
  int next;
  T t;
};

Pole next to następny wolne element lub wartość -1 gdy element
przechowuje dane. Czyli pole next pełni rolę listy wolnych elementów.

Dodawanie jest tak samo szybkie jak do wektora, a nawet szybsze, bo 
nie alokujemy, tylko kopiujemy na wcześniej prealokowane pozycje. 
Usuwanie jest bardzo szybkie, tylko wpisujemy w next następną
wolną pozycję a usuwaną zapamiętujemy jako głowę listy. Przeiterowanie
takiego wektora będzie też szybsze niż przeiterowanie listy, oczywiście
pod warunkiem, że nie usuniemy więcej niż kilka procent elementów.

Więc odpowiedź na pytanie w tytule już się robi trudna, bo zależy od
tego, ile dodamy elementów maksymalnie, ile średnio usuniemy i jak
często będziemy iterować po całości. A to dopiero rozgrzewka. Dlaczego
to dopiero rozgrzewa? 

A no dlatego, że w wektorze można usuwać poprzez zastąpienie elementu
usuwanego elementem ostatnim. Rozwiązanie takie ma wadę: będzie trzeba
zmienić wszystkie odwołania w całym programie do ostatniego elementu.

Na tym nie koniec. Można zadeklarować zbiór usuniętych elementów. Zbiór
oparty o hash-table szybko testuje, czy wpis spod indexu x jest wolny
czy zajęty, jednak w trakcie iterowania trzeba wykonać N testów - mimo
wszystko może to być wolne. 

Można zamiast hash-table użyć drzewa do zapamiętania zwolnionych pozycji.
Szukamy pierwszej pozycji wolnej w drzewku i iterujemy po elementach 
zajętych aż do napotkania wcześniej znalezionej pozycji wolnej. Potem 
szukamy następnej pozycji wolnej. Czyli test w drzewie będzie 
wykonany tylko tyle razy, ile zostało zwolnionych elementów - wydaje 
się to bardzo szybkim rozwiązaniem.

To ostatnie rozwiązanie wydaje się bardzo dobre dla wektorów z 
których usuwa się czasami mały odsetek elementów. Rozwiązanie na
drzewie (chodzi oczywiście o drzewo poszukiwań binarnych) będzie
wymagało mało testów i będzie miało mały narzut pamięciowy.

Co myślicie o tym wszystkim?

Pozdrawiam

Re: kiedy używać listy, a kiedy wektora?

#308448

Author: Wiktor S.
Date: Mon, 18 Apr 2016 20:16

10 lines
1318 bytes

> Główną wadą wektora jest to, że usuwanie elementu zachodzi w
> pesymistycznym czasie N, a nawet w średnim 0.5*N.

I taką samą wadę ma lista podczas iterowania, więc jeśli chcesz z listy 
usunąć N-ty element nie mając ustawionego nań iteratora, usuwanie elementu 
będzie tak samo powolne jak w wektorze, bo trzeba będzie najpierw do 
elementu dojechać.

-- 
Wiktor S.

Re: kiedy używać listy, a kiedy wektora?

#308449

Author: M.M.
Date: Mon, 18 Apr 2016 21:50

18 lines
2153 bytes

On Monday, April 18, 2016 at 10:16:40 PM UTC+2, Wiktor S. wrote:
> > Główną wadą wektora jest to, że usuwanie elementu zachodzi w
> > pesymistycznym czasie N, a nawet w średnim 0.5*N.
> 
> I taką samą wadę ma lista podczas iterowania, więc jeśli chcesz z listy 
> usunąć N-ty element nie mając ustawionego nań iteratora, usuwanie elementu 
> będzie tak samo powolne jak w wektorze, bo trzeba będzie najpierw do 
> elementu dojechać.

Jeśli przed usunięciem musimy wyszukać liniowo, to w obu strukturach
wyszukujemy w średnim czasie 0.5*N, następnie w liście usuwamy w 
czasie stałym, a w wektorze w średnim czasie 0.5*N - więc i tu i 
tu czas liniowy, ale w liście 2 razy mniej operacji. Niestety w
trakcie przeszukiwania listy nie zawsze działa cache, więc w
praktyce w tym teście lista może być wolniejsza pomimo że 
wykonuje się na niej dwa razy mniej operacji.

Pozdrawiam

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads