Wydajność pamięci: jeden duży słownik czy słownik mniejszych słowników?

Piszę aplikację w Pythonie (2.6), która wymaga ode mnie użycia słownika jako magazynu danych.

Jestem ciekaw, czy bardziej wydajne jest posiadanie jednego dużego słownika, czy też rozbicie go na wiele (dużo) mniejszych słowników, a następnie posiadanie słownika "indeksowego", który zawiera odniesienie do wszystkich mniejszych słowników.

Wiem, że w ogóle jest dużo narzutów z listami i słownikami. Czytałem gdzieś, że python wewnętrznie przydziela wystarczająco dużo miejsca, aby słownik / lista # przedmiotów do potęgi 2.

Jestem na tyle nowy w Pythonie, że nie jestem pewien, czy istnieją inne nieoczekiwane wewnętrzne zawiłości/niespodzianki, takie jak to, że nie jest oczywiste dla przeciętnego użytkownika, że powinienem wziąć pod uwagę.

Jedną z trudności jest wiedza, jak moc 2 systemu liczy "przedmioty"? Czy każda para key: jest liczona jako 1 przedmiot? To wydaje się ważne, aby wiedzieć, bo jeśli masz 100 pozycji monolityczny słownik to przestrzeń 100^2 pozycje zostaną przydzielone. Jeśli masz 100 pojedynczych słowników pozycji (1 klucz:para), to każdy słownik będzie tylko alokacją 1^2 (aka bez dodatkowej alokacji)?

Wszelkie jasno sprecyzowane informacje byłyby bardzo pomocne!

Author: Brandon K, 2009-03-22
Source

7 answers

Trzy propozycje:

  1. Użyj jednego słownika.
    Jest to łatwiejsze, bardziej proste, a ktoś inny już zoptymalizował ten problem dla Ciebie. Dopóki nie zmierzysz kodu i nie wyśledzisz problemu z wydajnością do tej części, nie masz powodu, aby nie robić prostej, prostej rzeczy.

  2. Zoptymalizuj później.
    Jeśli naprawdę martwisz się o wydajność, abstrakcyjny problem zrób klasę do owinięcia niezależnie od tego, jakiego mechanizmu wyszukiwania używasz i napisz swój kod, aby użyć tej klasy. Możesz zmienić implementację później, jeśli okaże się, że potrzebujesz innej struktury danych dla większej wydajności.

  3. Poczytaj na tablicach hashowych.
    Słowniki to tabele hash , a jeśli martwisz się o ich czas lub przestrzeń, powinieneś przeczytać, jak są zaimplementowane. To Podstawy informatyki. W skrócie jest to, że tabele hash są:

    • średni przypadek O (1) Czas wyszukiwania
    • O (n) przestrzeń (spodziewaj się około 2n , w zależności od różnych parametrów)

    Nie wiem, gdzie czytałeś, że były O(N^2) przestrzenią, ale gdyby były, to nie byłyby w powszechnym, praktycznym użyciu, jak w większości dzisiejszych języków. Te ładne właściwości tabel hashowych mają dwie zalety:

    1. O(1) w czasie Wyszukiwania za posiadanie większego słownika, ponieważ czas wyszukiwania nie zależy od rozmiaru.
    2. O(n) przestrzeń oznacza, że nie zyskujesz zbyt wiele z rozbicia swojego słownika na mniejsze kawałki. Skale przestrzenne liniowo z liczbą elementów, więc wiele małych słowników nie zajmie znacznie mniej miejsca niż jeden duży lub odwrotnie. Nie byłoby to prawdą, gdyby były O(N^2) przestrzenią, ale na szczęście nie są.

    Oto niektóre więcej zasobów, które mogą pomóc:

    • Artykuł W Wikipedii na temat tabel Hashowych Zawiera świetną listę różnych schematów wyszukiwania i alokacji używanych w hashtablach.
    • Dokumentacja GNU Scheme documentation zawiera miłą dyskusję na temat tego, ile miejsca można oczekiwać od hashtabli, w tym formalną dyskusję na temat tego, dlaczego "ilość miejsca użytego przez tabelę hashową jest proporcjonalna do liczby skojarzeń w tabeli". To może zainteresować ty.

    Oto kilka rzeczy, które możesz wziąć pod uwagę, jeśli okaże się, że potrzebujesz zoptymalizować implementację słownika:

    • Oto kod źródłowy języka C dla słowników Pythona, jeśli chcesz poznać wszystkie szczegóły. Tu jest obszerna dokumentacja.:
    • Oto implementacja Pythona tego, jeśli nie lubisz czytać C.
      (Dzięki Ben Peterson )
    • dokumentacja klasy Java Hashtable mówi trochę o tym, jak działają czynniki obciążenia i jak wpływają na miejsce, które zajmuje Twój hash. Zauważ, że istnieje kompromis między współczynnikiem obciążenia a tym, jak często trzeba przebijać. Ponowne leczenie może być kosztowne.
 70
Author: tgamblin,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2017-11-22 02:32:43

Jeśli używasz Pythona, nie powinieneś się martwić o tego typu rzeczy. Po prostu Zbuduj swoją strukturę danych tak, jak najlepiej odpowiada ona twoim potrzebom, a nie komputerowi.]}

To oznacza przedwczesną optymalizację, a nie poprawę wydajności. Profiluj swój kod, jeśli coś faktycznie jest wąskie, ale do tego czasu pozwól Pythonowi robić to, co robi i skoncentruj się na rzeczywistym zadaniu programistycznym, a nie na podstawowej mechanice.

 17
Author: Soviut,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-03-22 19:12:25

" proste "jest ogólnie lepsze niż" sprytne", zwłaszcza jeśli nie masz przetestowanego powodu, aby wyjść poza"proste". W każdym razie "pamięć efektywna" jest wieloznacznym terminem, a istnieją kompromisy, gdy rozważasz uporczywe, serializowanie, buforowanie, zamianę i całą masę innych rzeczy, które ktoś inny już przemyślał, więc w większości przypadków nie musisz tego robić.

Pomyśl o "najprostszym sposobie poprawnego obchodzenia się z nim" zoptymalizuj znacznie później.

 8
Author: dkretz,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-03-22 19:19:15

Przedwczesna optymalizacja bla bla, nie rób tego bla bla.

Myślę, że się mylisz co do mocy dwóch dodatkowych przydziałów. Myślę, że to tylko mnożnik z dwóch. x*2, nie x^2.

Widziałem to pytanie kilka razy na różnych listach dyskusyjnych Pythona.

Jeśli chodzi o pamięć, oto parafrazowana wersja jednej z takich dyskusji (ten post chciał przechowywać setki milionów liczb całkowitych):

  1. zbiór() to więcej przestrzeni wydajne niż dict(), jeśli chcesz po prostu przetestować członkostwo
  2. gmpy ma klasę typu bitvector do przechowywania gęstych zbiorów liczb całkowitych
  3. Dicty są przechowywane pomiędzy 50% a 30% puste, a wpis ma około ~12 bajtów (choć prawdziwa ilość będzie się różnić w zależności od platformy).

Tak więc, im mniej obiektów masz, tym mniej pamięci będziesz używać, i mniej wyszukiwań będziesz robić (ponieważ będziesz musiał szukać w indeksie, a następnie drugie wyszukiwanie w rzeczywistym wartość).

Jak inni, powiedział, profil, aby zobaczyć swoje wąskie gardła. Utrzymywanie wartości set() I value dict () może być szybsze, ale będziesz używać więcej pamięci.

Sugerowałbym również przeniesienie tego do listy specyficznej dla Pythona, takiej jak comp.lang.python, który jest pełen o wiele bardziej kompetentnych ludzi niż ja, którzy dadzą ci wszelkiego rodzaju przydatne informacje.

 6
Author: Richard Levasseur,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-03-22 19:36:51

Jeśli Twój Słownik jest tak duży, że nie mieści się w pamięci, możesz rzucić okiem na ZODB, bardzo dojrzałą bazę danych obiektów dla Pythona.

'root' db ma taki sam interfejs jak słownik i nie trzeba ładować całej struktury danych do pamięci naraz, np. można iterację tylko nad częścią struktury, podając klucze start i end.

Zapewnia również transakcje i wersjonowanie.

 5
Author: EoghanM,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-04-29 10:37:13

Szczerze mówiąc, nie będziesz w stanie odróżnić tak czy inaczej, zarówno pod względem wydajności, jak i zużycia pamięci. O ile nie masz do czynienia z dziesiątkami milionów lub więcej przedmiotów, wpływ wydajności lub pamięci jest po prostu szum.

Z twojego drugiego zdania wynika, że jeden wielki słownik jest twoją pierwszą skłonnością i bardziej pasuje do problemu, który próbujesz rozwiązać. Jeśli to prawda, idź z tym. To, co znajdziesz w Pythonie, to to, że rozwiązania, które każdy uważa za "właściwe", prawie zawsze okazują się takie, które są tak jasne i proste, jak to tylko możliwe.

 2
Author: DNS,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-03-22 19:19:59

Często, słowniki słowników są przydatne z innych powodów niż wydajność. pozwalają one na przechowywanie informacji kontekstowych o danych bez konieczności posiadania dodatkowych pól na samych obiektach i sprawiają, że zapytania podzbiorów danych są szybsze.

Jeśli chodzi o zużycie pamięci, można by przypuszczać, że jeden duży słownik będzie zużywał mniej pamięci ram niż wiele mniejszych. Pamiętaj, że jeśli zagnieżdżasz słowniki, każda dodatkowa warstwa zagnieżdżania podwoi mniej więcej liczba słowników, które musisz przydzielić.

Jeśli chodzi o szybkość zapytań, wiele DIC będzie trwało dłużej ze względu na zwiększoną liczbę wymaganych wyszukiwań.

Więc myślę, że jedynym sposobem na odpowiedź na to pytanie jest profilowanie własnego kodu. Jednak moja sugestia polega na użyciu metody, która sprawia, że Twój kod jest najczystszy i najłatwiejszy w utrzymaniu. Ze wszystkich funkcji Pythona, słowniki są prawdopodobnie najbardziej podrasowane w celu uzyskania optymalnej wydajności.

 1
Author: Daniel Naab,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2009-03-22 21:33:47