Dlaczego zestawy Python nie zachowują kolejności wstawiania?

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

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.9
• setobject.c- master , v3.5.9
• issue18771 - zestaw zmian w celu zmniejszenia kosztów kolizji mieszania dla zestawów obiektów w Pythonie 3.4.

Był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.

Zestawy pozostają nieuporządkowane. (Dlaczego? Wzorce użytkowania są różne. Także inna implementacja.)

- Guido van Rossum

Zestawy używają innego algorytmu, który nie jest tak łatwy do zmiany w zachowaniu kolejności wstawiania. Operacje „set-to-set” tracą elastyczność i optymalizacje, jeśli wymagana jest kolejność. Matematyka zbiorów jest zdefiniowana w kategoriach zbiorów nieuporządkowanych. Krótko mówiąc, porządkowanie zestawów nie nastąpi w najbliższej przyszłości.

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

14 września 2016 o 15:50 Eric Snow napisał:

Potem zrobię to samo z setami.

O ile się nie zrozumiałem, Raymond był przeciwny wprowadzeniu podobnej zmiany do zestawu.

Zgadza się. Oto kilka przemyśleń na ten temat, zanim ludzie zaczną szaleć.

• W przypadku kompaktowego dyktatu oszczędność miejsca była wygraną netto, przy czym dodatkowa przestrzeń zajęta przez indeksy, a ogólna alokacja tablic klucz / wartość / skrót zostały zrekompensowane przez poprawioną gęstość tablic klucz / wartość / skrót. Jednak w przypadku zestawów sieć była znacznie mniej korzystna, ponieważ nadal potrzebujemy wskaźników i ogólnej alokacji, ale możemy jedynie zrównoważyć koszt przestrzeni, zagęszczając tylko dwie z trzech tablic. Innymi słowy, kompaktowanie ma większy sens, gdy tracisz miejsce na klucze, wartości i skróty. Jeśli stracisz jedną z tych trzech, przestanie to być przekonujące.

• Wzór użycia dla zestawów różni się od dykt. Ten pierwszy zawiera więcej wyszukiwań typu hit lub miss. Ten ostatni ma zwykle mniej brakujących kluczowych wyszukiwań. Ponadto niektóre optymalizacje dla operacji ustawiania zestawu utrudniają zachowanie kolejności zestawów bez wpływu na wydajność.

• Podjąłem alternatywną ścieżkę, aby poprawić wydajność zestawu. Zamiast kompaktować (co nie było dużo wygranej przestrzeni i poniosło koszt dodatkowej pośredniczości), dodałem sondowanie liniowe, aby zmniejszyć koszt kolizji i poprawić wydajność pamięci podręcznej. To ulepszenie jest niezgodne z podejściem do kompaktowania, które zalecałem w przypadku słowników.

• Na razie efekt uboczny porządkowania słowników nie jest gwarantowany, więc przedwczesne jest naleganie, aby zestawy również zostały uporządkowane. Dokumenty już zawierają link do przepisu na utworzenie zestawu zamówień ( https://code.activestate.com/recipes/576694/ ), ale wygląda na to, że absorpcja była prawie zerowa. Ponadto, teraz, gdy Eric Snow dał nam szybki OrDERDict, zbudowanie OrDERSet z MutableSet i OrdersDict jest łatwiejsze niż kiedykolwiek, ale znowu nie zauważyłem żadnego prawdziwego zainteresowania, ponieważ typowe analizy danych typu set-to-set nie są tak naprawdę potrzebujesz lub zależy ci na zamówieniu. Podobnie, podstawowym zastosowaniem szybkich testów członkostwa jest agnostyk porządkowy.

• To powiedziawszy, myślę, że jest miejsce na dodanie alternatywnych implementacji zestawu do PyPI. W szczególności istnieją interesujące przypadki specjalne dla danych, które można zamawiać, w których operacje przyspieszone można przyspieszyć, porównując całe zakresy kluczy (patrz https://code.activestate.com/recipes/230113-implementation-of- zestawy przy użyciu sortowanych list dla punktu początkowego). IIRC, PyPI ma już kod dla zestawów filtrów Bloom i haszowania kukułki.

• Rozumiem, że ekscytujący jest fakt, że duży blok kodu jest akceptowany w rdzeniu Pythona, ale nie powinien on być otwarty na zalewy w celu angażowania się w większe przeróbki innych typów danych, chyba że mamy pewność, że jest to uzasadnione.

- Raymond Hettinger

Z [Python-Dev] Python 3.6 dict staje się kompaktowy i otrzymuje wersję prywatną; a słowa kluczowe zostaną uporządkowane , wrzesień 2016 r.

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.

Odpowiadająca jej koncepcja matematyczna jest nieuporządkowana i byłoby dziwnie narzucać takie jak porządek - R. Hettinger

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:

• Przekształcenie listy w zestaw zmienia kolejność elementów
• Uzyskaj unikalne wartości z listy w Pythonie