• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

python - działanie list

0 głosów
516 wizyt
pytanie zadane 24 listopada 2018 w Python przez Maciej Złotorowicz Gaduła (4,230 p.)
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.

1 odpowiedź

0 głosów
odpowiedź 24 listopada 2018 przez Arkadiusz Sikorski Pasjonat (20,160 p.)
wybrane 24 listopada 2018 przez Maciej Złotorowicz
 
Najlepsza

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.

komentarz 24 listopada 2018 przez Maciej Złotorowicz Gaduła (4,230 p.)
Nie istnieją "zwykłe" szybkie listy jak z c++? btw dzięki za szybkie odpisanie.
komentarz 24 listopada 2018 przez adrian17 Ekspert (322,800 p.)
edycja 25 listopada 2018 przez adrian17

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 :)

komentarz 25 listopada 2018 przez Arkadiusz Sikorski Pasjonat (20,160 p.)

"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.

Podobne pytania

0 głosów
1 odpowiedź 270 wizyt
0 głosów
1 odpowiedź 182 wizyt
pytanie zadane 26 grudnia 2016 w Python przez dragulaa Użytkownik (970 p.)
0 głosów
1 odpowiedź 47 wizyt
pytanie zadane 13 września w Python przez Ziom Początkujący (400 p.)

89,082 zapytań

137,670 odpowiedzi

307,610 komentarzy

59,140 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...