python - działanie list

Question

W jaki sposób są zaimplementowane listy w pythonie? Czy działa to tak samo jak std::list z c++? i jak jest rozwiązany problem trzymania wielu różnych elementów? czy lista w pythone to tak naprawdę lista wskaźników na różne elementy?
Nieprzyzwyczajony jestem do takich luzów, za prosty ten Python dla mnie.

Answer 1

To zależy od implementacji pythona, ale w CPythonie wygląda to tak.

Jest to dynamicznie alokowana tablica wskaźników na PyObject.

Wiedząc to, trzeba pamiętać, że usuwanie i dodawanie elementów z miejsc innych niż koniec będzie kosztowniejsze.

Comments

Nie istnieją "zwykłe" szybkie listy jak z c++? btw dzięki za szybkie odpisanie.

---

Nie istnieją "zwykłe" szybkie listy jak z c++?

"zwykłe" linkowane listy są zazwyczaj wolniejsze od większości alternatyw. CPythonowa lista jest zaimplementowana analogicznie do std::vectora z C++a, który też jest domyślnym wydajnym kontenerem do większości zastosowań w C++ie.

Jeśli przypadek jest tak specyficzny że jakimś cudem linkowana lista dawałaby znaczącą poprawę wydajnościową względem listy i deque, to prawdopodobnie Python od początku nie byłby do tego zastosowania użyty - stąd brak ich popularności w Pythonie :)

---

"zwykłe" linkowane listy są zazwyczaj wolniejsze od większości alternatyw. 

^ dokładnie o to chodzi.

Częsta alokacja jest dość wolna, więc alokowanie każdego node'a w liście linkowanej byłoby kosztowne. Lepiej zaalokować pamięć na zapas (problemów z pamięcią raczej nie mamy).

Ponadto przewagą jest stały czas odwołania się do elementu z listy, która jest w formie ciągłego fragmentu pamięci.
W przypadku listy linkowanej musielibyśmy skakać od node'a do node'a, żeby znaleźć i-ty element, czyli złożoność operacji dostępu byłaby liniowa, a nie stała.

Jeśli by porównać częstość operacji w liście:

• odwołanie się do elementu
• dodawania na koniec / usuwanie z końca
• dodawania na początek/w środek

to okazuje się, że pierwsze dwa podpunkty są najczęstsze, czyli zależy nam na szybkim dostępie i dodawaniu na koniec i usuwaniu z końca. Wniosek z tego taki, że lepiej mieć stały czas dostępu i dodawania/usuwania (z dokładnością to sporadycznej alokacji w przypadku braku potrzebnej pamięci), a rzadziej wykonywane operacje mogą być kosztowniejsze.