Dlaczego używamy tablic zamiast innych struktur danych?

Podczas programowania nie widziałem instancji, w której tablica lepiej nadaje się do przechowywania informacji niż inna jej forma. Naprawdę doszedłem do wniosku, że dodane „funkcje” w językach programowania poprawiły się i zastąpiły je. Widzę teraz, że nie są one zastępowane, ale raczej dają nowe życie, że tak powiem.

Więc w zasadzie, po co używać tablic?

Nie chodzi tak bardzo o to, dlaczego używamy tablic z komputerowego punktu widzenia, ale raczej, dlaczego mielibyśmy używać tablic z punktu widzenia programowania (subtelna różnica). To, co komputer robi z tablicą, nie było pytaniem.

Czas cofnąć się w czasie na lekcję. Chociaż dzisiaj nie myślimy o tych rzeczach w naszych fantazyjnych językach zarządzanych, są one oparte na tym samym fundamencie, więc spójrzmy, jak zarządza się pamięcią w C.

Zanim się zanurzę, krótkie wyjaśnienie znaczenia terminu „ wskaźnik ”. Wskaźnik to po prostu zmienna, która „wskazuje” miejsce w pamięci. Nie zawiera rzeczywistej wartości w tym obszarze pamięci, zawiera adres pamięci. Pomyśl o bloku pamięci jak o skrzynce pocztowej. Wskaźnik będzie adresem tej skrzynki pocztowej.

W C tablica jest po prostu wskaźnikiem z przesunięciem, przesunięcie określa, jak daleko w pamięci szukać. Zapewnia to czas dostępu O (1) .

  MyArray   [5]
     ^       ^
  Pointer  Offset

Wszystkie inne struktury danych albo się na tym opierają, albo nie używają sąsiedniej pamięci do przechowywania, co powoduje skrócenie czasu wyszukiwania losowego dostępu (chociaż istnieją inne korzyści z nieużywania pamięci sekwencyjnej).

Załóżmy na przykład, że mamy tablicę z 6 liczbami (6,4,2,3,1,5), w pamięci wyglądałoby to tak:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================

W tablicy wiemy, że każdy element znajduje się obok siebie w pamięci. Tablica AC (nazywana MyArraytutaj) jest po prostu wskaźnikiem do pierwszego elementu:

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^
MyArray

Gdybyśmy chcieli spojrzeć w górę MyArray[4], dostęp byłby możliwy w następujący sposób:

   0     1     2     3     4 
=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
                           ^
MyArray + 4 ---------------/
(Pointer + Offset)

Ponieważ możemy bezpośrednio uzyskać dostęp do dowolnego elementu w tablicy, dodając przesunięcie do wskaźnika, możemy wyszukać dowolny element w tym samym czasie, niezależnie od wielkości tablicy. Oznacza to, że uzyskanie MyArray[1000]zajmie tyle samo czasu, co uzyskanie MyArray[5].

Alternatywna struktura danych to połączona lista. Jest to liniowa lista wskaźników, z których każdy wskazuje na następny węzeł

========    ========    ========    ========    ========
| Data |    | Data |    | Data |    | Data |    | Data |
|      | -> |      | -> |      | -> |      | -> |      | 
|  P1  |    |  P2  |    |  P3  |    |  P4  |    |  P5  |        
========    ========    ========    ========    ========

P(X) stands for Pointer to next node.

Zauważ, że utworzyłem każdy „węzeł” we własnym bloku. Wynika to z faktu, że nie ma gwarancji, że będą (i najprawdopodobniej nie będą) przylegać do pamięci.

Jeśli chcę uzyskać dostęp do P3, nie mogę uzyskać bezpośredniego dostępu, ponieważ nie wiem, gdzie jest w pamięci. Wiem tylko, gdzie jest root (P1), więc zamiast tego muszę zacząć od P1 i podążać za każdym wskaźnikiem do pożądanego węzła.

Jest to czas wyszukiwania O (N) (Koszt wyszukiwania rośnie wraz z dodawaniem każdego elementu). Dostanie się do P1000 jest znacznie droższe niż dotarcie do P4.

Struktury danych wyższego poziomu, takie jak tabele skrótów, stosy i kolejki, wszystkie mogą wewnętrznie korzystać z tablicy (lub wielu tablic), natomiast listy połączone i drzewa binarne zwykle używają węzłów i wskaźników.

Można się zastanawiać, dlaczego ktokolwiek użyłby struktury danych wymagającej przejścia liniowego w celu wyszukania wartości zamiast po prostu użycia tablicy, ale ma to swoje zastosowanie.

Weź ponownie naszą tablicę. Tym razem chcę znaleźć element tablicy, który ma wartość „5”.

=====================================
|  6  |  4  |  2  |  3  |  1  |  5  |
=====================================
   ^     ^     ^     ^     ^   FOUND!

W tej sytuacji nie wiem, jakie przesunięcie dodać do wskaźnika, aby go znaleźć, więc muszę zacząć od 0 i podążać w górę, aż go znajdę. Oznacza to, że muszę wykonać 6 kontroli.

Z tego powodu wyszukiwanie wartości w tablicy jest uważane za O (N). Koszt wyszukiwania rośnie, gdy tablica się powiększa.

Pamiętasz wyżej, gdzie powiedziałem, że czasami użycie niesekwencyjnej struktury danych może mieć zalety? Wyszukiwanie danych jest jedną z tych zalet, a jednym z najlepszych przykładów jest Drzewo Binarne.

Drzewo binarne to struktura danych podobna do listy połączonej, jednak zamiast łączenia z pojedynczym węzłem, każdy węzeł może łączyć się z dwoma węzłami potomnymi.

         ==========
         |  Root  |         
         ==========
        /          \ 
  =========       =========
  | Child |       | Child |
  =========       =========
                  /       \
            =========    =========
            | Child |    | Child |
            =========    =========

 Assume that each connector is really a Pointer

Gdy dane są wstawiane do drzewa binarnego, używa kilku reguł, aby zdecydować, gdzie umieścić nowy węzeł. Podstawową koncepcją jest to, że jeśli nowa wartość jest większa niż rodzice, wstawia ją w lewo, a jeśli jest niższa, wstawia ją w prawo.

Oznacza to, że wartości w drzewie binarnym mogą wyglądać następująco:

         ==========
         |   100  |         
         ==========
        /          \ 
  =========       =========
  |  200  |       |   50  |
  =========       =========
                  /       \
            =========    =========
            |   75  |    |   25  |
            =========    =========

Szukając drzewa binarnego o wartości 75, musimy odwiedzić tylko 3 węzły (O (log N)) z powodu tej struktury:

• Czy 75 jest mniejsze niż 100? Spójrz na Right Node
• Czy 75 jest większe niż 50? Spójrz na lewy węzeł
• Jest 75!

Mimo że w naszym drzewie znajduje się 5 węzłów, nie musieliśmy patrzeć na pozostałe dwa, ponieważ wiedzieliśmy, że oni (i ich dzieci) nie mogą zawierać wartości, której szukaliśmy. Daje nam to czas wyszukiwania, który w najgorszym przypadku oznacza, że ​​musimy odwiedzić każdy węzeł, ale w najlepszym przypadku musimy odwiedzić tylko niewielką część węzłów.

To tam tablice pobierają rytm, zapewniają liniowy czas wyszukiwania O (N), pomimo czasu dostępu O (1).

Jest to niezwykle ogólny przegląd struktur danych w pamięci, pomijający wiele szczegółów, ale mam nadzieję, że ilustruje siłę i słabość tablicy w porównaniu do innych struktur danych.

Dla losowego dostępu O (1), którego nie można pokonać.

Nie wszystkie programy robią to samo lub działają na tym samym sprzęcie.

Jest to zazwyczaj odpowiedź na pytanie, dlaczego istnieją różne funkcje językowe. Tablice to podstawowa koncepcja informatyki. Zastąpienie tablic listami / macierzami / wektorami / dowolną zaawansowaną strukturą danych miałoby poważny wpływ na wydajność i byłoby wręcz niewykonalne w wielu systemach. Istnieje wiele przypadków, w których należy używać jednego z tych „zaawansowanych” obiektów do gromadzenia danych z powodu danego programu.

W programowaniu biznesowym (co większość z nas robi) możemy atakować sprzęt o stosunkowo dużej mocy. Korzystanie z Listy w języku C # lub Vector w Javie jest właściwym wyborem w takich sytuacjach, ponieważ struktury te pozwalają deweloperowi szybciej osiągać cele, co z kolei pozwala na bardziej funkcjonalne oprogramowanie tego typu.

Podczas pisania oprogramowania wbudowanego lub systemu operacyjnego tablica może być często lepszym wyborem. Chociaż tablica oferuje mniejszą funkcjonalność, zajmuje mniej pamięci RAM, a kompilator może bardziej efektywnie optymalizować kod do wyszukiwania tablic.

Jestem pewien, że pomijam szereg korzyści w tych przypadkach, ale mam nadzieję, że rozumiesz.

Spojrzenie na zalety macierzy polega na sprawdzeniu, gdzie wymagana jest zdolność dostępu do macierzy O (1), a tym samym wielkie litery:

1. W tabelach przeglądowych aplikacji (statyczna tablica umożliwiająca dostęp do niektórych odpowiedzi kategorycznych)

2. Zapamiętywanie (obliczone już wyniki funkcji złożonej, aby nie obliczać ponownie wartości funkcji, powiedzmy log x)

3. Aplikacje do wizji komputerowej High Speed ​​wymagające przetwarzania obrazu ( https://en.wikipedia.org/wiki/Lookup_table#Lookup_tables_in_image_processing )