1. Trzy struktury, trzy zastosowania

Na maturze rzadko pytają wprost o strukturę danych — ale wybór złej potrafi zamienić program działający w sekundę w taki, który liczy minutami. To częsty temat pytania „dlaczego drugie rozwiązanie jest szybsze".

Lista — kolejność ma znaczenie, elementy mogą się powtarzać. Dostęp po indeksie.
Słownik — para klucz i wartość. Idealny do zliczania i wyszukiwania po nazwie.
Zbiór — tylko unikalne elementy, bez kolejności. Do sprawdzania „czy już było".

2. Dlaczego zbiór bywa szybszy od listy

Sprawdzenie x in lista wymaga przejścia po kolei przez elementy, czyli $O(n)$ . To samo sprawdzenie na zbiorze albo słowniku działa w czasie średnio stałym, $O(1)$ .

# wolno: dla kazdego elementu przechodzimy cala liste
wynik = []
for x in dane:
  if x not in wynik:      # O(n) przy kazdym obiegu
      wynik.append(x)

# szybko: sprawdzenie w zbiorze jest natychmiastowe
widziane = set()
wynik = []
for x in dane:
  if x not in widziane:   # O(1)
      widziane.add(x)
      wynik.append(x)

Pierwsza wersja ma złożoność $O(n^2)$ , druga $O(n)$ . Przy dziesięciu tysiącach danych z arkusza maturalnego to różnica między ułamkiem sekundy a wyraźnym oczekiwaniem.

3. Słownik do zliczania

Zadania typu „która litera występuje najczęściej" albo „ile razy pojawia się każde słowo" rozwiązuje się słownikiem w kilku linijkach.

licznik = {}
for znak in tekst:
  licznik[znak] = licznik.get(znak, 0) + 1

# element o najwiekszej wartosci
najczestszy = max(licznik, key=licznik.get)

Metoda get z wartością domyślną pozwala uniknąć sprawdzania, czy klucz już istnieje. To skraca kod i eliminuje najczęstszy błąd w tym zadaniu.

4. Pułapki

Zbiór gubi kolejność i duplikaty. Jeśli zadanie wymaga zachowania kolejności wystąpień, potrzebujesz zbioru i listy naraz, jak w przykładzie wyżej.
Modyfikowanie listy w trakcie iterowania po niej daje pominięte elementy. Buduj nową listę zamiast usuwać z bieżącej.
Kluczem słownika nie może być lista, bo jest zmienna. Krotka może.
Sortowanie po wartościach słownika wymaga wskazania klucza sortowania — samo sorted() uporządkuje klucze, nie wartości.

Kolekcje: Listy, Słowniki i Zbiory

1. Trzy struktury, trzy zastosowania

2. Dlaczego zbiór bywa szybszy od listy

3. Słownik do zliczania

4. Pułapki

Nadal czujesz się niepewnie?