Zaskoczyło mnie, że niedawno odkryłem, że chociaż dykty gwarantują zachowanie kolejności wstawiania w Pythonie 3.7+, zestawy nie są:
>>> d = {'a': 1, 'b': 2, 'c': 3}
>>> d
{'a': 1, 'b': 2, 'c': 3}
>>> d['d'] = 4
>>> d
{'a': 1, 'b': 2, 'c': 3, 'd': 4}
>>> s = {'a', 'b', 'c'}
>>> s
{'b', 'a', 'c'}
>>> s.add('d')
>>> s
{'d', 'b', 'a', 'c'}
Jakie jest uzasadnienie tej różnicy? Czy te same ulepszenia wydajności, które doprowadziły zespół Python do zmiany implementacji dict, nie dotyczą również zestawów?
Nie szukam wskaźników do implementacji zestawów uporządkowanych ani sposobów używania dykt jako stand-ins dla zestawów. Zastanawiam się tylko, dlaczego zespół Python nie stworzył wbudowanych zestawów w celu zachowania porządku w tym samym czasie, co w przypadku nagrań.
dictisetod 2.7.Odpowiedzi:
Zestawy i dykty są zoptymalizowane dla różnych przypadków użycia. Podstawowym zastosowaniem zestawu jest szybkie testowanie członkostwa, które jest niezależne od porządku. W przypadku nagrań koszt wyszukiwania jest najbardziej krytyczną operacją, a klucz jest bardziej prawdopodobny. W przypadku zestawów obecność lub brak elementu nie jest z góry znana, dlatego implementacja zestawu musi zostać zoptymalizowana zarówno dla znalezionego, jak i nie znalezionego przypadku. Ponadto niektóre optymalizacje dla typowych operacji na zestawach, takich jak łączenie i przecinanie, utrudniają zachowanie kolejności zestawów bez obniżania wydajności.
Chociaż obie struktury danych są oparte na haszowaniu, powszechne jest błędne przekonanie, że zestawy są po prostu implementowane jako dykty z zerowymi wartościami. Jeszcze przed wdrożeniem kompaktowego dykta w CPython 3.6 implementacje zestawu i dyktowania znacznie się różniły, a ponowne użycie kodu było niewielkie. Na przykład dykty używają losowego sondowania, ale zestawy używają kombinacji sondowania liniowego i otwartego adresowania, aby poprawić lokalizację pamięci podręcznej. Początkowa sonda liniowa (domyślnie 9 kroków w CPython) sprawdzi serię sąsiednich par klucz / skrót, poprawiając wydajność poprzez zmniejszenie kosztów obsługi kolizji skrótu - kolejny dostęp do pamięci jest tańszy niż rozproszone sondy.
dictobject.c- master , v3.5.9setobject.c- master , v3.5.9Byłoby to możliwe w teorii, aby zmienić ustawioną realizację CPython by być podobny do kompaktowego dict, ale w praktyce nie są wady i godne deweloperzy rdzeniowe byli przeciwni dokonania takiej zmiany.
- Guido van Rossum
- Raymond Hettinger
Szczegółową dyskusję na temat tego, czy kompaktować zestawy dla wersji 3.7, oraz odpowiedzi na temat tego, dlaczego zdecydowano się na nie, można znaleźć na listach dyskusyjnych python-dev.
Podsumowując, główne punkty są takie, że wzorce użycia są różne (dyktaty porządkowania wstawiania, takie jak ** kwargs są przydatne , mniej tak dla zestawów), oszczędność miejsca dla zestawów kompaktujących jest mniej znacząca (ponieważ istnieje tylko tablica kluczy i skrótów do zagęszczać, w przeciwieństwie do kluczy, skrótów i wartości), a wspomniana wyżej liniowa optymalizacja sondowania w zestawach jest niezgodna z kompaktową implementacją.
Odtworzę post Raymonda poniżej, który obejmuje najważniejsze punkty.
Z [Python-Dev] Python 3.6 dict staje się kompaktowy i otrzymuje wersję prywatną; a słowa kluczowe zostaną uporządkowane , wrzesień 2016 r.
źródło
Dyskusje
Twoje pytanie jest nierozstrzygnięte i zostało już ciężko omówione na python-devs jeszcze niedawno. R. Hettinger udostępnił listę uzasadnień w tym wątku . Stan problemu wydaje się teraz otwarty, wkrótce po tej szczegółowej odpowiedzi T. Petersa.
Krótko mówiąc, implementacja współczesnych dykt, która zachowuje porządek wstawiania, jest wyjątkowa i nie jest uważana za odpowiednią dla zbiorów. W szczególności dyktaty są używane wszędzie do uruchamiania Pythona (np.
__dict__W przestrzeniach nazw obiektów). Główną motywacją stojącą za współczesnym dyktatem było zmniejszenie rozmiaru, dzięki czemu Python jest bardziej wydajny pod względem pamięci. W przeciwieństwie do tego, zestawy są mniej rozpowszechnione niż dykty w rdzeniu Pythona i dlatego zniechęcają do takiego refaktoryzacji. Zobacz także przemówienie R. Hettingera na temat wdrażania nowoczesnego dyktatora.Perspektywy
Nieuporządkowana natura zbiorów w Pythonie przypomina zachowanie zbiorów matematycznych . Zamówienie nie jest gwarantowane.
Gdyby do Pythona wprowadzono jakikolwiek porządek , zachowanie to byłoby zgodne z całkowicie oddzielną strukturą matematyczną, a mianowicie uporządkowanym zbiorem (lub Osetem). Osety odgrywają osobną rolę w matematyce, szczególnie w kombinatorykach. Jedno praktyczne zastosowanie Osetów obserwuje się przy zmianie dzwonów .
Posiadanie nieuporządkowanych zestawów jest spójne z bardzo ogólną i wszechobecną strukturą danych, która odpiera większość współczesnej matematyki, tj . Teorię zbiorów . Poddaję, że nieuporządkowane zestawy w Pythonie są dobre.
Zobacz także powiązane posty, które rozwijają się na ten temat:
źródło