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

python - działanie list

VPS Starter Arubacloud
0 głosów
1,687 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 (349,420 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ź 570 wizyt
0 głosów
1 odpowiedź 248 wizyt
pytanie zadane 26 grudnia 2016 w Python przez dragulaa Użytkownik (950 p.)
+1 głos
1 odpowiedź 382 wizyt
pytanie zadane 20 czerwca 2023 w Python przez Bondrusiek Maniak (61,440 p.)

93,008 zapytań

141,975 odpowiedzi

321,256 komentarzy

62,350 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 2

Można już zamawiać tom 2 książki "Wprowadzenie do bezpieczeństwa IT" - będzie to około 650 stron wiedzy o ITsec (17 rozdziałów, 14 autorów, kolorowy druk).

Planowana premiera: 30.09.2024, zaś planowana wysyłka nastąpi w drugim tygodniu października 2024.

Warto preorderować, tym bardziej, iż mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy dodatkowe 15% zniżki! Dziękujemy zaprzyjaźnionej ekipie Sekuraka za kod dla naszej Społeczności!

...