- nowość
Struktury danych z przymrużeniem oka. Zabawna przygoda z przykładami pachnącymi kawą - ebook
Struktury danych z przymrużeniem oka. Zabawna przygoda z przykładami pachnącymi kawą - ebook
O strukturach danych można myśleć jako o konstruktach do organizowania i zapisywania danych. Zrozumienie, czym są, jak je tworzyć i do czego się przydają, jest jednym z fundamentów programowania. Bez tego nie można pisać efektywnego i skalowalnego kodu. Jednak dla wielu osób opanowanie struktur danych stanowi poważne wyzwanie.
Dzięki tej książce ta trudna sztuka musi Ci się udać! Znajdziesz tu gruntowne, a przy tym zabawne wprowadzenie do tworzenia i używania struktur danych. Naukę oprzesz na przejrzystych schematach i dowcipnych porównaniach, aby już wkrótce móc tworzyć wydajniejszy i elastyczny kod. Nieistotne, jakim językiem programowania się posługujesz - podczas lektury zaimplementujesz za pomocą pseudokodu kilkanaście głównych struktur danych, w tym stosy, filtry Blooma, drzewa czwórkowe i grafy. Fantazyjne przykłady ułatwią Ci intuicyjne posługiwanie się tymi strukturami danych. Dowiesz się, jak indeksować przedmioty kolekcjonerskie, optymalizować wyszukiwanie za pomocą latającej wiewiórki, a nawet jak znaleźć najbliższy kubek kawy!
Z tą książką nauczysz się:
- znajdować równowagę między szybkością, elastycznością i zużyciem pamięci
- projektować struktury danych, które dynamicznie rosną lub maleją
- łączyć proste struktury danych, by przeprowadzać zaawansowane operacje
- znajdować i uzyskiwać dane w tabelach z haszowaniem
- przyspieszać wyszukiwanie za pomocą binarnych drzew poszukiwań
- poprawiać wydajność poszukiwań przy użyciu B-drzew
Nalej sobie kawy i wyjdź poza standardowe podejścia!
Spis treści
O autorze
Podziękowania
Wstęp
- Dla kogo jest ta książka?
- Bez konkretnego języka programowania
- Analogie i parzenie kawy
- Jak korzystać z tej książki?
1. Informacje w pamięci
- Zmienne
- Złożone struktury danych
- Tablice
- Sortowanie przez wstawianie
- Łańcuchy znaków
- Dlaczego to takie ważne?
2. Wyszukiwanie binarne
- Problem
- Przeszukiwanie liniowe
- Algorytm wyszukiwania binarnego
- Nieobecne wartości
- Implementacja wyszukiwania binarnego
- Przystosowanie wyszukiwania binarnego
- Czas wykonywania się algorytmu
- Dlaczego to takie ważne?
3. Dynamiczne struktury danych
- Ograniczenia tablic
- Wskaźniki i referencje
- Listy
- Działania na listach
- Wstawianie do listy
- Usuwanie z listy
- Listy dwukierunkowe
- Tablice i listy
- Dlaczego to takie ważne?
4. Stosy i kolejki
- Stosy
- Stosy jako tablice
- Stosy jako listy
- Kolejki
- Kolejki jako tablice
- Kolejki jako listy
- Znaczenie kolejności
- Przeszukiwanie w głąb
- Przeszukiwanie wszerz
- Dlaczego to takie ważne?
5. Binarne drzewa poszukiwań
- Budowa binarnego drzewa poszukiwań
- Wyszukiwanie w binarnych drzewach poszukiwań
- Wyszukiwania iteracyjne i rekurencyjne
- Wyszukiwanie w drzewach a wyszukiwanie w posortowanych tablicach
- Wprowadzanie zmian w binarnych drzewach poszukiwań
- Dodawanie węzłów
- Usuwanie węzłów
- Zagrożenia związane z niewyważonymi drzewami
- Rozbudowana struktura binarnego drzewa poszukiwań
- Dlaczego to takie ważne?
6. Drzewa trie oraz przystosowywanie struktury danych
- Binarne drzewa poszukiwań z łańcuchami znaków
- Łańcuchy znaków w drzewach
- Koszt porównywania łańcuchów znaków
- Drzewa trie
- Wyszukiwanie w drzewach trie
- Dodawanie i usuwanie węzłów
- Dlaczego to takie ważne?
7. Kolejki priorytetowe i kopce
- Kolejki priorytetowe
- Kopce typu max
- Dodawanie elementów do kopca
- Usuwanie z kopca elementów o najwyższym priorytecie
- Zapisywanie dodatkowych informacji
- Aktualizowanie priorytetów
- Kopce typu min
- Sortowanie przez kopcowanie
- Dlaczego to takie ważne?
8. Siatki
- Wprowadzenie do wyszukiwania najbliższego sąsiada
- Wyszukiwanie najbliższego sąsiada za pomocą przeszukiwania liniowego
- Wyszukiwanie danych przestrzennych
- Siatki
- Struktura siatki
- Budowanie siatek i wstawianie punktów
- Usuwanie punktów
- Przeszukiwanie siatek
- Odrzucanie pojemników
- Przeszukiwanie liniowe pojemników
- Wyszukiwanie zwiększające zasięg
- Uproszczone wyszukiwanie zwiększające zasięg
- Istota rozmiaru siatki
- Więcej niż dwa wymiary
- Poza danymi przestrzennymi
- Dlaczego to takie ważne?
9. Drzewa przestrzenne
- Drzewa czwórkowe
- Budowa jednolitych drzew czwórkowych
- Dodawanie punktów
- Usuwanie punktów
- Przeszukiwanie jednolitych drzew czwórkowych
- Kod wyszukiwania najbliższego sąsiada
- Drzewa kd
- Struktura drzewa kd
- Węższe ograniczenia przestrzenne
- Tworzenie drzew kd
- Działania na drzewach kd
- Dlaczego to takie ważne?
10. Tablice z haszowaniem
- Przechowywanie i wyszukiwanie z użyciem kluczy
- Tablice haszujące
- Kolizje
- Metoda łańcuchowa
- Próbkowanie liniowe
- Funkcje skrótu
- Obsługa kluczy nieliczbowych
- Przykładowy przypadek użycia
- Dlaczego to takie ważne?
11. Pamięć podręczna
- Wprowadzenie do pamięci podręcznej
- Eksmisja LRU a pamięć podręczna
- Tworzenie pamięci podręcznej typu LRU
- Aktualizowanie znacznika ostatniego użycia
- Inne strategie eksmitowania
- Dlaczego to takie ważne?
12. B-drzewa
- Struktura B-drzewa
- Przeszukiwanie B-drzew
- Dodawanie kluczy
- Algorytm wstawiający
- Przykłady dodawania kluczy
- Usuwanie klucza
- Naprawa niedostatecznie wypełnionych węzłów
- Szukanie klucza o najmniejszej wartości
- Algorytm usuwania
- Przykłady usuwania kluczy
- Dlaczego to takie ważne?
13. Filtry Blooma
- Wprowadzenie do filtrów Blooma
- Tablice haszujące ze wskaźnikami
- Filtr Blooma
- Kod dla filtru Blooma
- Dobieranie parametrów filtru Blooma
- Filtry Blooma a tabele z haszowaniem
- Dlaczego to takie ważne?
14. Listy z przeskokami
- Deterministyczne a losowe struktury danych
- Wprowadzenie do listy z przeskokami
- Przeszukiwanie list z przeskokami
- Dodawanie węzłów
- Usuwanie węzłów
- Czas działania
- Dlaczego to takie ważne?
15. Grafy
- Wprowadzenie do grafów
- Reprezentacja grafów
- Przeszukiwanie grafów
- Szukanie najkrótszej ścieżki za pomocą algorytmu Dijkstry
- Szukanie minimalnych drzew rozpinających za pomocą algorytmu Prima
- Sortowanie topologiczne za pomocą algorytmu Kahna
- Dlaczego to takie ważne?
Zakończenie
- Jaki wpływ ma struktura danych?
- Czy potrzebujemy dynamicznych struktur danych?
- Jaki jest koszt amortyzacji?
- Jak możemy przystosować strukturę danych do określonego problemu?
- Jaki jest związek między pamięcią a czasem działania?
- Jak możemy ulepszyć naszą strukturę danych?
- Jak losowość wpływa na spodziewane działanie?
- Dlaczego to takie ważne?
Kategoria: | Bazy danych |
Zabezpieczenie: |
Watermark
|
ISBN: | 978-83-289-1007-2 |
Rozmiar pliku: | 4,6 MB |