Wybór odpowiedniej struktury danych może zwiększyć wydajność programu. Oto przewodnik, który pomoże Ci dokonać właściwego wyboru.

Wybór najlepszej struktury danych dla Twoich celów może być trudny ze względu na wiele dostępnych opcji. Wybierając strukturę danych, weź pod uwagę dane, z którymi będziesz mieć do czynienia, operacje, które mają zostać wykonane na danych oraz środowisko, w którym będzie wykonywana Twoja aplikacja.

Zrozum swoje dane

Zrozumienie danych, z którymi będziesz mieć do czynienia przed wybraniem struktury danych, ma kluczowe znaczenie. Wspólne struktury danych które działają z różnymi typami danych, obejmują tablice, połączone listy, drzewa, wykresy i tabele skrótów.

Na przykład, gdy potrzebujesz losowego dostępu do elementów ze swoich danych, tablice mogą być najlepszym wyborem. W przypadku, gdy ciągle musisz dodawać lub usuwać elementy z listy, a rozmiar listy również może się zmieniać, wówczas listy połączone mogą być szczególnie przydatne.

Gdy zachodzi potrzeba efektywnego przechowywania wielu poziomów danych, takich jak struktury rekordów, oraz przeprowadzania operacji, takich jak wyszukiwanie i sortowanie, przydatne są drzewa.

instagram viewer

Kiedy trzeba opisać interakcje między jednostkami, takimi jak te w sieciach społecznościowych, i wykonać operacje, takie jak najkrótsza ścieżka i łączność, preferowane są wykresy. Tabele skrótów są pomocne przy szybkim wyszukiwaniu kluczy.

Rozważ operacje, które należy wykonać na danych

Wybierając strukturę danych, należy również wziąć pod uwagę operacje, jakie mają zostać wykonane na danych. Różne struktury danych optymalizują wiele działań, takich jak sortowanie, wyszukiwanie, wstawianie i usuwanie.

Na przykład połączone listy są lepsze do działań takich jak wstawianie i usuwanie, ale drzewa binarne są najlepsze do wyszukiwania i sortowania. Tabela skrótów może być najlepszym wyborem, jeśli aplikacja wymaga jednoczesnego wstawiania i wyszukiwania.

Oceń środowisko

Rozważając strukturę danych, należy ocenić środowisko, w którym aplikacja będzie działać. Środowisko wpływa na to, jak dobrze i szybko dostępne są struktury danych.

Oceniając swój obecny stan, weź pod uwagę następujące czynniki:

  1. Moc przetwarzania: Wybierz struktury danych dla swoich aplikacji, które działają dobrze na komputerach PC z niewielką mocą obliczeniową podczas pracy na platformie. Na przykład prostsze struktury danych, takie jak tablice, mogą być bardziej odpowiednie niż drzewa lub wykresy.
  2. Konkurencja: Należy wybrać strukturę danych bezpieczną dla wątków, która może obsłużyć jednoczesny dostęp bez uszkodzenia danych; jeśli aplikacja działa w środowisku współbieżnym, w którym wiele wątków lub procesów uzyskuje jednocześnie dostęp do struktury danych. W tym przypadku struktury danych bez blokad, takie jak Współbieżna połączona kolejka I Współbieżna mapa Hash mogą być bardziej odpowiednie niż tradycyjne, takie jak ArrayListand HashMap.
  3. Opóźnienie sieciowe: Jeśli Twoja aplikacja wymaga przesyłania danych przez sieć, podczas wybierania najlepszej struktury danych musisz wziąć pod uwagę opóźnienie sieci. W takich sytuacjach użycie struktury danych, która ogranicza połączenia sieciowe lub zmniejsza ilość przesyłanych danych, może pomóc w usprawnieniu wykonywania.

Typowe struktury danych i przypadki ich użycia

Oto podsumowanie kilku popularnych struktur danych i ich zastosowania.

  1. Tablice: Jest to prosta i wydajna struktura danych, która może zawierać serię elementów tego samego typu danych o stałym rozmiarze. Aby działały poprawnie, potrzebują szybkiego, bezpośredniego dostępu do określonych obiektów poprzez indeks.
  2. Połączone listy: Połączone listy składają się z węzłów, które zawierają element i odniesienie do następnego węzła i/lub poprzedniego węzła. Dzięki wydajnemu działaniu listy połączone najlepiej sprawdzają się w sytuacjach wymagających częstego wstawiania lub usuwania elementów. Jednak dostęp do poszczególnych elementów według indeksu na połączonych listach jest wolniejszy w porównaniu z tablicami.
  3. Kolejki i stosy: Stosy są zgodne z zasadą LIFO (ostatni na wejściu, pierwszy na wyjściu), zgodnie z którą ostatni element włożony jest pierwszym elementem usuniętym. Kolejki są zarządzane zgodnie z zasadą FIFO (First In-First-Out). gdzie pierwszy dodany element jest jednocześnie pierwszym usuniętym.
  4. Tabele skrótów: Tabele skrótów to forma struktury danych, która przechowuje pary klucz-wartość. Najlepszym rozwiązaniem jest użycie tablic mieszających, gdy liczba komponentów jest nieprzewidywalna i potrzebny jest szybki dostęp do wartości według klucza.
  5. Drzewa: Drzewa to hierarchiczne struktury danych, które mogą przechowywać grupę elementów w hierarchii. Najlepsze zastosowania dla drzewa wyszukiwania binarnego znajdują się w hierarchicznych strukturach danych, w których relacje między elementami danych mogą przedstawiać strukturę drzewiastą.

Wybór właściwej struktury danych

Przed wybraniem struktury danych należy wziąć pod uwagę dane, obowiązki i środowisko aplikacji. Idąc z wyborem, pomyśl o następujących elementach:

  1. Złożoność czasu: Złożoność czasowa struktury danych może znacząco wpłynąć na wydajność aplikacji. Jeśli Twoja aplikacja wymaga częstych operacji wyszukiwania lub pobierania, użyj struktury danych o zmniejszonej złożoności czasowej, takiej jak tablica skrótów.
  2. Złożoność przestrzeni: Kolejną ważną kwestią jest złożoność przestrzenna struktury danych. Jeśli Twoja aplikacja wymaga dużej ilości pamięci, wybierz strukturę danych o mniejszej złożoności przestrzennej, na przykład tablicę. Jeśli przestrzeń nie jest problemem, możesz użyć struktury danych o większej złożoności przestrzennej, takiej jak drzewo.
  3. Czytaj vs. Operacje zapisu: Jeśli Twoja aplikacja wykorzystuje wiele operacji zapisu, wybierz strukturę danych o szybszej wydajności wstawiania, na przykład tablicę mieszającą. Jeśli Twoja aplikacja wymaga wielu operacji odczytu, wybierz strukturę danych o większej szybkości wyszukiwania, na przykład drzewo wyszukiwania binarnego.
  4. Typ danych: dane, z którymi masz do czynienia, mogą również wpływać na wybraną strukturę danych. Na przykład możesz użyć struktury danych opartej na drzewie, jeśli twoje dane są hierarchiczne. Jeśli masz proste dane, do których dostęp musi być losowy, wybór struktury danych opartej na tablicy może być najlepszym rozwiązaniem.
  5. Dostępne biblioteki: Rozważ biblioteki, które są łatwo dostępne dla rozważanej struktury danych. Może być łatwiejsze do wykonania i utrzymania, jeśli twój język programowania ma wbudowane biblioteki dostępne dla określonej struktury danych.

Poniższy przykład języka Python pokazuje, jak wybrać najlepszą strukturę danych dla określonego przypadku użycia.

Rozważ przypadek, w którym tworzysz aplikację systemu plików, która musi przechowywać i pobierać pliki w hierarchii. Musisz wybrać strukturę danych, która może skutecznie reprezentować tę hierarchiczną strukturę i szybko wykonywać operacje, takie jak wyszukiwanie, wstawianie i usuwanie.

Dobrym pomysłem może być użycie struktury danych opartej na drzewie, takiej jak wyszukiwanie binarne lub B-drzewo. Jeśli liczba wpisów w każdym katalogu jest stosunkowo niewielka, a drzewo nie jest bardzo głębokie, drzewo wyszukiwania binarnego będzie działać dobrze. B-drzewo byłoby bardziej odpowiednie dla większej liczby plików i głębszych struktur katalogów.

Poniżej znajduje się przykład drzewa wyszukiwania binarnego w Pythonie.

klasaWęzeł:
pok__w tym__(jaźń, wartość):
 wartość własna = wartość
 self.left_child = Nic
 self.right_child = Nic


klasaDrzewo wyszukiwania binarnego:


pok__w tym__(samego siebie):
 własny.root = Nic
pokwstawić(jaźń, wartość):


Jeśli własny.root JestNic:
 self.root = Węzeł (wartość)


w przeciwnym razie:
 self._insert (wartość, self.root) 
pok_wstawić(ja, wartość, bieżący_węzeł):


Jeśli wartość < bieżący_węzeł.wartość:
Jeśli current_node.left_child JestNic:
 current_node.left_child = Węzeł (wartość)


w przeciwnym razie:
 self._insert (wartość, current_node.left_child)
Elif wartość > bieżący_węzeł.wartość:
Jeśli current_node.right_child JestNic:
 current_node.right_child = Węzeł (wartość)
w przeciwnym razie:
 self._insert (wartość, current_node.right_child)


w przeciwnym razie:
 wydrukować(„Wartość już istnieje w drzewie”.)
pokszukaj(jaźń, wartość):
Jeśli własny.root JestnieNic:
powrót self._search (wartość, self.root)


w przeciwnym razie:
powrótFAŁSZ
pok_szukaj(ja, wartość, bieżący_węzeł):


Jeśli wartość == bieżący_węzeł.wartość:
powrótPRAWDA


Elif wartość < bieżący_węzeł.wartość I current_node.left_child JestnieNic:
powrót self._search (wartość, current_node.left_child)


Elif wartość > bieżący_węzeł.wartość I current_node.right_child JestnieNic:
powrót self._search (wartość, current_node.right_child)
w przeciwnym razie:
powrótFAŁSZ

W tej implementacji konstruujesz dwie klasy: a Drzewo wyszukiwania binarnego klasa, która zarządza operacjami wstawiania i wyszukiwania oraz a Węzeł klasa symbolizująca węzeł w drzewie wyszukiwania binarnego.

Podczas gdy metoda insert wstawia nowy węzeł w odpowiednie miejsce w drzewie w zależności od jego wartości, metoda search wyszukuje węzeł o określonej wartości. Złożoność czasowa obu operacji w zrównoważonym drzewie wynosi O(log n).

Wybierz optymalną strukturę danych

Szybkość i możliwości adaptacyjne aplikacji można znacznie poprawić dzięki wybranej strukturze danych. Uwzględnienie danych, operacji i środowiska może pomóc w wybraniu najlepszej struktury danych.

Ważne są kwestie, takie jak złożoność czasowa, złożoność przestrzenna, operacje odczytu i zapisu, współbieżność, typ danych i dostępność biblioteki.

Oceniając wagę każdego komponentu, powinieneś wybrać strukturę danych, która spełnia wymagania Twojej aplikacji.