Porównanie struktur danych

1. Wprowadzenie

Python oferuje wiele wbudowanych struktur danych. Wybór odpowiedniej struktury może mieć ogromny wpływ na wydajność i czytelność kodu.

Główne struktury danych w Pythonie:

  • Lista (list) – uporządkowana, mutowalna kolekcja
  • Tuple (tuple) – uporządkowana, niemutowalna kolekcja
  • Słownik (dict) – pary klucz-wartość
  • Zbiór (set) – nieuporządkowana kolekcja unikalnych elementów

2. Porównanie podstawowych cech

Cecha Lista Tuple Słownik Zbiór
Składnia [1, 2, 3] (1, 2, 3) {"a": 1} {1, 2, 3}
Uporządkowana Tak Tak Tak (3.7+) Nie
Modyfikowalna Tak Nie Tak Tak
Duplikaty Tak Tak Klucze: Nie Nie
Indeksowanie Tak (0-n) Tak (0-n) Po kluczu Nie
Hashowalna Nie Tak Nie Nie
Zużycie pamięci Średnie Małe Duże Średnie

3. Złożoność czasowa operacji

3.1. Lista

Operacja Złożoność
lista[i] O(1)
lista.append(x) O(1)*
lista.insert(i, x) O(n)
lista.remove(x) O(n)
x in lista O(n)
lista.sort() O(n log n)

*amortyzowane

3.2. Tuple

Operacja Złożoność
tuple[i] O(1)
x in tuple O(n)
tuple.count(x) O(n)
tuple.index(x) O(n)

3.3. Słownik

Operacja Średnia Najgorszy
dict[key] O(1) O(n)
dict[key] = value O(1) O(n)
del dict[key] O(1) O(n)
key in dict O(1) O(n)

3.4. Zbiór

Operacja Średnia Najgorszy
x in set O(1) O(n)
set.add(x) O(1) O(n)
set.remove(x) O(1) O(n)
set1 | set2 O(len(set1) + len(set2))

4. Kiedy używać listy?

Używaj listy gdy:

✅ Potrzebujesz zachować kolejność elementów ✅ Elementy mogą się powtarzać ✅ Potrzebujesz dostępu po indeksie ✅ Będziesz dodawać elementy na końcu (append) ✅ Zależy Ci na prostocie

Przykłady zastosowań:

4.1. Historia operacji (undo/redo)

4.2. Sekwencja kroków

4.3. Wyniki pomiarów

5. Kiedy używać tuple?

Używaj tuple gdy:

✅ Dane nie powinny się zmieniać (niezmienność) ✅ Potrzebujesz klucza w słowniku (hashowalna) ✅ Zwracasz wiele wartości z funkcji ✅ Chcesz zaoszczędzić pamięć ✅ Potrzebujesz gwarancji niezmienności

Przykłady zastosowań:

5.1. Współrzędne geograficzne

5.2. Zwracanie wielu wartości

5.3. Stałe konfiguracyjne

6. Kiedy używać słownika?

Używaj słownika gdy:

✅ Potrzebujesz szybkiego wyszukiwania po kluczu (O(1)) ✅ Dane mają naturalne klucze (ID, nazwa, itp.) ✅ Chcesz mapować jedną wartość na drugą ✅ Potrzebujesz grupować dane ✅ Implementujesz cache lub memoizację

Przykłady zastosowań:

6.1. Konfiguracja aplikacji

6.2. Liczenie wystąpień

6.3. Cache (memoizacja)

6.4. Grupowanie danych

7. Kiedy używać zbioru?

Używaj zbioru gdy:

✅ Potrzebujesz unikalnych elementów ✅ Chcesz szybko sprawdzać przynależność (O(1)) ✅ Wykonujesz operacje matematyczne (suma, przecięcie, różnica) ✅ Musisz usunąć duplikaty ✅ Kolejność nie ma znaczenia

Przykłady zastosowań:

7.1. Usuwanie duplikatów

7.2. Sprawdzanie wspólnych elementów

7.3. Filtrowanie

7.4. Sprawdzanie unikalności

8. Porównanie wydajności

8.1. Wyszukiwanie elementu

8.2. Dodawanie elementów

9. Zużycie pamięci

Wnioski: - Tuple zajmują najmniej pamięci - Słowniki i zbiory zużywają znacznie więcej pamięci - Wybór struktury to trade-off między pamięcią a wydajnością

10. Praktyczne scenariusze – drzewo decyzyjne

Pytania do zadania sobie:

START
│
├─ Czy dane muszą być unikalne?
│  ├─ TAK
│  │  ├─ Czy potrzebujesz par klucz-wartość?
│  │  │  ├─ TAK → SŁOWNIK
│  │  │  └─ NIE → ZBIÓR
│  │
│  └─ NIE
│     ├─ Czy dane będą się zmieniać?
│     │  ├─ TAK
│     │  │  ├─ Czy potrzebujesz szybkiego wyszukiwania?
│     │  │  │  ├─ TAK → SŁOWNIK
│     │  │  │  └─ NIE → LISTA
│     │  │
│     │  └─ NIE → TUPLE
│
└─ Czy potrzebujesz dostępu po indeksie?
   ├─ TAK → LISTA lub TUPLE
   └─ NIE → rozważ ZBIÓR lub SŁOWNIK

11. Przykłady z życia

11.1. E-commerce

11.2. Social media

11.3. System edukacyjny

12. Zaawansowane struktury z collections

12.1. deque – szybka kolejka

Użyj deque gdy: - Często dodajesz/usuwasz z początku i końca - Implementujesz kolejkę (FIFO)

12.2. defaultdict – słownik z wartością domyślną

Użyj defaultdict gdy: - Grupujesz dane - Często dodajesz do kolekcji w słowniku

12.3. Counter – licznik wystąpień

Użyj Counter gdy: - Liczysz wystąpienia elementów - Szukasz najczęstszych/najrzadszych elementów

12.4. namedtuple – tuple z nazwami pól

Użyj namedtuple gdy: - Chcesz czytelniejszy kod - Potrzebujesz lekkiej alternatywy dla klasy

13. Antywzorce – czego unikać

❌ Anty-wzorzec 1: Lista zamiast zbioru do sprawdzania przynależności

❌ Anty-wzorzec 2: Lista zamiast słownika do mapowania

❌ Anty-wzorzec 3: Modyfikowalna tuple (lista w tuple)

14. Podsumowanie – cheat sheet

Potrzebujesz... Użyj...
Uporządkowanej kolekcji Lista/Tuple
Szybkiego wyszukiwania Zbiór/Słownik
Unikalnych elementów Zbiór
Par klucz-wartość Słownik
Niezmiennej kolekcji Tuple
Klucza w słowniku Tuple/frozenset
Częstego dodawania na końcu Lista
Częstego dodawania na początku deque
Liczenia wystąpień Counter
Grupowania danych defaultdict
Operacji matematycznych na zbiorach Zbiór

15. Finalne wskazówki

1. Optymalizacja przedwczesna to zło

Zacznij od prostej struktury (najczęściej lista). Optymalizuj tylko gdy: - Mierzysz rzeczywisty problem wydajności - Profiler wskazuje wąskie gardło

2. Czytelność > Wydajność

W 95% przypadków czytelność wygrywa!

3. Używaj wbudowanych funkcji

Python ma zoptymalizowane wbudowane funkcje – używaj ich!

16. Co dalej warto poznać?

  • Zaawansowane struktury: deque, heapq, bisect
  • Struktury danych w algorytmach: drzewa, grafy, kopce
  • Własne struktury: klasy, dataclass
  • Biblioteki: pandas (DataFrame), numpy (ndarray)
  • Profilowanie: timeit, cProfile do mierzenia wydajności
Wróć do spisu lekcji