Jakie są zasady działania menedżerów pamięci w listach i krotkach Pythona. Jakie są różnice w modyfikacji/dodawaniu elementów w liście i krotce i jak wpływa to na wydajność?

Odpowiedź

W Pythonie listy (list) są strukturami mutowalnymi, a krotki (tuple) są niemutowalne.

• list: Podczas dodawania nowych elementów (append, extend, insert) Python przydziela "z zapasem" bloki pamięci, aby zminimalizować liczbę alokacji podczas wzrostu tablicy ("strategia over-allocation"). Usuwanie elementów (pop, remove) przebiega szybko, ale czasami może powodować przemieszczenie pamięci.
• tuple: Rozmiar krotki jest stały, elementów nie można zmieniać ani dodawać — zapewnia to dużą prędkość operacji odczytu i mniejsze zużycie pamięci w porównaniu do list przy przechowywaniu dużej liczby niemutowalnych danych.

Przykład ilustrujący zmianę listy i krotki:

lst = [1, 2, 3]
lst.append(4)    # OK
lst[1] = 20      # OK

tup = (1, 2, 3)
tup[1] = 20      # TypeError

Wydajność:

• Listy doskonale nadają się do często zmieniających się kolekcji.
• Krotki są nieco szybsze, bardziej optymalne pod względem pamięci (dzięki stałemu rozmiarowi i zasadom haszowania), nadają się do kluczy słowników, wartości zwracanych z funkcji (niemutowalne dane).

---

Pytanie z pułapką

Pytanie: Dlaczego operacje dodawania elementów do listy zazwyczaj są wykonywane szybko (O(1)), skoro z punktu widzenia tablicy powinny prowadzić do przemieszczenia pamięci?

Odpowiedź:

Python implementuje dynamiczne tablice dengan "przydzieleniem nadmiarowej pamięci" od razu dla kilku elementów. Dlatego append zazwyczaj zajmuje O(1), a przemieszczenie pamięci zachodzi tylko wtedy, gdy faktycznie wyczerpano rezerwowy blok.

Przykład:

import sys
lst = []
for i in range(10):
    lst.append(i)
    print(len(lst), sys.getsizeof(lst))  # Rozmiar pamięci rośnie nie ściśle liniowo

---

Historia

Przykład 1

---

W jednym projekcie do kluczy słownika używano list. Programista nie wiedział, że listy nie są haszowane (mutowalność), co spowodowało błąd "TypeError: unhashable type: 'list'".

---

Przykład 2

---

Programista często tworzył długie listy, łącząc je poprzez +. Prowadziło to do dodatkowych kopiowań tablicy i wysokich kosztów pamięci i czasu. Efektywniej było używać append w pętli lub generatorów.

---

Przykład 3

---

W systemie logowania do przechowywania znaczników czasu wybrano krotki, myśląc, że dzięki immutability będzie szybciej. Jednak czasami zachodziła potrzeba modyfikacji, co wymagało ciągłego tworzenia nowych krotek (copy-on-write) i prowadziło do spowolnienia w porównaniu do używania list.

---