Jakie są główne różnice, zalety i wady między statycznymi i dynamicznymi strukturami danych?Różnice między statycznymi i dynamicznymi strukturami danych
Under które kategorie zrobić najczęstsze struktury danych spadać?
Jak mogłem wiedzieć, w jakiej sytuacji użyć każdego?
Aby rozpocząć z uproszczeniem:
Istnieje kilka podstawowych rodzajów struktur danych: tablic, listach i drzew. Cała reszta może być złożona przy użyciu różnych typów tych dwóch struktur (na przykład tablica haszująca może być zaimplementowana z tablicą dla wartości mieszania i jedną listą dla każdej wartości mieszania dla obsługi kolizji).
Z tych struktur tablice są statyczne (tj. Ich ślad pamięci nie zmienia się w czasie, gdy wykonywane są na nich operacje), a wszystko inne jest dynamiczne (tj. W ogólnym przypadku zmienia się ślad pamięci).
Różnice między tymi dwoma rodzajami struktur może pochodzić z powyższym:
Istnieją również inne różnice, które jednak mogą wejść w grę tylko w przypadku sortowania danych. Nie mogę podać obszernej listy, ponieważ istnieje wiele dynamicznych struktur danych, które wykazują różne charakterystyki wydajności dla różnych operacji ("dodaj", "usuń", "znajdź"), a więc nie mogą być umieszczone pod tym samym dachem.
bardzo widoczna różnica jest taka, że posortowane tablice wymagają ruchu (ewentualnie) wiele rzeczy wokół w pamięci dla każdej operacji innych niż „znaleźć”, podczas gdy konstrukcje dynamiczne ogólnie wykonać mniej pracy.
Tak więc, aby podsumować:
Edit: nie wspominając wykresy, inny rodzaj dynamicznej struktury danych, które prawdopodobnie nie może składać się z prostych elementów (z definicji, drzewo ma dokładnie jeden odnośnik dzieje „na” dowolnego węzła z wyjątkiem korzenia, podczas gdy wykresy mogą mieć więcej niż jeden). Jednak wykresów nie można tak naprawdę porównać z innymi strukturami w scenariuszu "co byłoby lepiej używać", ponieważ albo trzeba użyć wykresu, albo nie (inne struktury mogą wykazywać różne wyniki, ale w końcu wszystkie wspierają ten sam zestaw operacji).
To zawsze na odwrót, jeśli pójdziesz statycznie, stracisz pamięć, natomiast w przypadku dynamiki wydajność spadnie. Najlepszy projekt korzystałby ze struktur danych wydajnie, nie ma jednej doskonałej odpowiedzi.
Statyczne struktury danych (SDS) są wielkościami stałymi (np. Tablice), ilość pamięci przydzielonej do nich nie może się zmienić w czasie wykonywania, podczas gdy dynamiczne struktury danych (DDS) (np. Listy połączone) mają elastyczny rozmiar, mogą rosnąć lub zmniejszyć w razie potrzeby, aby pomieścić dane, które mają być przechowywane.
SDS to liniowe struktury danych, które umożliwiają szybki dostęp do przechowywanych w nich elementów, ale operacje wstawiania/usuwania są drogie w porównaniu do DDS, gdzie dostęp do elementów jest wolniejszy, ale wstawianie/usuwanie jest szybsze.
Większość DS to Dynamic DS.
W przypadku SDS powierzchnia jest przydzielana przed faktycznym wstawieniem danych, więc miejsce może zostać zmarnowane lub może być niewystarczające kilka razy, więc powinny być używane tylko w przypadku, gdy dokładna ilość danych do wstawienia jest znana z góry, jeśli powinien być znany w czasie wykonywania DDS.
prostych wskazówek
Dynamiczne struktury danych mają następujące cechy:
statyczne struktury danych mają następujące cechy:
Podsumowując, nie jest skuteczne w użyciu struktur dynamicznych do przechowywania zestawu danych, które są znane, nie zmieniać. Użycie statycznej struktury danych w takim przypadku pozwoli zaoszczędzić zasoby systemowe i zapewni szybszy dostęp do elementów. Jeśli wiadomo, że rozmiar danych zmienia się z drugiej strony, użyj struktur dynamicznych.
Na pewnym poziomie lista jest tylko zdegenerowanym drzewem. Można powiedzieć, że istnieją dwa rodzaje struktur danych, blokowane i oparte na węzłach (i różne hybrydy z tych dwóch). –
Ponadto nie zgadzam się z 1). Nie ma powodu, dla którego nie mógłbyś napisać klasy "BoundedList", która wygenerowałaby błąd (lub cokolwiek innego) po dodaniu elementu N + 1. Zgadzam się jednak, że nie jest to dokładnie podstawowa struktura danych - bardziej hack. –
@ Drew: masz rację w obu liczbach. Prawdę mówiąc, zacząłem pisać o dwóch rodzajach struktur, zostawiając z nich drzewa i wykresy, ale uważałem za pewne, że ktoś mnie poprawi. Wygląda na to, że nie możesz tego obejść :-).Jeśli chodzi o ograniczoną listę, myślę, że zgodzisz się, że ktoś na poziomie wiedzy implikowanym przez pierwotne pytanie nie ma nic do zyskania na tym, że został poinformowany o tej technice. – Jon