Rozumiem różnicę między uporządkowanymi i nieuporządkowanymi zbiorami i rozumiem, dlaczego z wielu powodów nie potrzebujemy uporządkowanych zestawów. Jednak wszystkie operacje na zbiorach są nadal możliwe na zamówionych zestawach, a zestawy i tak muszą być przechowywane wewnętrznie w jakiejś kolejności, więc dlaczego zestawy nie są domyślnie zamawiane? Czy wpływ na wydajność zachowania kolejności zestawów jest zbyt duży?
Komentarze
- Zwróć uwagę, że ” uporządkowanie ” wartości w nieuporządkowanej kolekcji może bardziej zależeć od kolejności reklamowania, a mniej (jeśli w ogóle) od samych wartości, co nie jest ' t kolejność w zwykle używanym sensie (pochodzącym od terminu matematycznego).
- To pytanie można uznać za niezwiązane z tematem, ponieważ nie jest ' t o opracowaniu konkretnego programu, ale raczej o projekcie języka.
- @outis Nie byłem ' t na pewno co do właściwej podstrony. Czy jest jeszcze jedna, sugeruje?
Odpowiedź
Nie chodzi o to, że narzut jest szczególnie duży, a raczej, że istnieje w ogóle .
Funkcje językowe muszą zawsze zachowywać równowagę między opłacalnością. Słowniki są absolutnie fundamentalne dla programowania w Pythonie, więc byłoby bardzo źle, gdyby były nawet nieco wolniejsze niż muszą być tylko po to, aby zachować kolejność wstawiania, gdy przez większość czasu nie potrzebujesz porządkowania. To była właściwa decyzja, aby odrzucić kolejność wstawiania w zamian za nieco szybszy dostęp i pozostawić strukturę danych zachowującą porządek dla specjalnych klas. Gdyby istniała inna struktura danych, która mogłaby zrobić wszystko, co może dict, a dict byłby mniej używaną pomyłką języka, może wyglądać inaczej.
Komentarze
- Moim kontrargumentem byłoby: użyj bardziej wydajnego typu nieuporządkowanego dyktowania dla słowników wewnętrznych (tak jak tam ' s
deque, aby zoptymalizować wydajność w niektórych innych kontekstach), ale niech główny typ danych dyktowania dla użytkownika zachowuje kolejność. - Poza tym, mam rację rozumiejąc, że implementacja 3.6 w CPythonie faktycznie zachowuje kolejność wstawiania dicts?
Odpowiedź
Masz rację, że produkty są przechowywane wewnętrznie z pewnym zamówieniem, ale to zamówienie wewnętrzne jest określane przez kod skrótu klucza, który umożliwia tak szybkie pobieranie. Więc jeśli zestaw / dykt powinien zostać zamówiony, musiałby utrzymywać oddzielną wewnętrzną strukturę danych (powiedzmy uporządkowaną listę kluczy) do tego.
To oczywiście zwiększyłoby rozmiar. Ale może gorzej, wpłynie to na wydajność. Na przykład usunięcie elementu z zestawu jest operacją O (1), ale jeśli musiałoby również usunąć klucz z wewnętrznej uporządkowanej listy, stałoby się O (n). Taki koszt byłby katastrofalny dla niektórych zastosowań. Biorąc pod uwagę, że dość rzadko potrzebujesz uporządkowanego zestawu, taki kompromis nie jest tego wart w przypadku standardowych typów zestawów / dykt.
Odpowiedź
Twoje założenie jest nieprawidłowe. Począwszy od Pythona 3.6, dict zapamiętują swoją kolejność reklam . To był szczegół implementacji i został awansowany do pełnej funkcji językowej w 3.7. W 3.6, dla konkretnego przypadku **kwargs, zachowanie kolejności jest szczególnie gwarantowane.
Komentarze
- Tak, nie ' nie wiedziałem o tym, zadając pytanie, ponieważ ' nie jest jeszcze funkcją języka, a jedynie implementacją szczegółowo w jednej realizacji. Wygląda jednak na to, że przynajmniej słowniki staną się uporządkowane długoterminowo i miejmy nadzieję, że także zestawy.
- @oulenz it ' nie jest już szczegółem implementacji, to ' s wymagane od Pythona 3.7
Odpowiedź
Zamówione set jest możliwy tylko wtedy, gdy elementy, które mają być przechowywane, mają na pierwszym miejscu uporządkowanie (tj. metodę porównania) – ale nie zawsze jest to dane.
Obecnie domyślną implementacją set / map w większości środowisk jest oparty na tablicy hashy autorestize, która ma następujące zalety:
- szybciej
- zużywa mniej pamięci
- nie wymaga elementów do zapewnienia porządku
i tak zestawy muszą być przechowywane wewnętrznie w jakiejś kolejności
Ale ten porządek wewnętrzny nie musi mieć żadnego znaczenia, ani nie pozostaje taki sam. Rzeczywiście, jedną z właściwości tablic mieszających, która czasami wprawia niedoświadczonych programistów w błąd, jest to, że kolejność iteracji, która jest oparta na porządku wewnętrznym, może się całkowicie zmienić po dodaniu elementów (tj. Po uruchomieniu zmiany rozmiaru) lub między różnymi biegnie.
Komentarze
- Nie ' nie rozumiem Twojej pierwszej uwagi. Nie ' nie potrzebujemy metody porównawczej, kolejność mogłaby być po prostu dziedziczona, np. z listy lub literału ciągu
{3, 5, 4}. - @oulenz: jeśli nie ' nie przejmuj się kolejnością bez znaczenia i zmieniająca się w czasie, każdy zestaw jest uporządkowany, ponieważ będzie jakiś rodzaj kolejności iteracji. Ale ” uporządkowany zestaw ” oznacza, że kolejność elementów jest semantyczna, a to nie zawsze jest możliwe. Nie ' naprawdę nie rozumiem, dlaczego chcesz, aby wszystkie zestawy były uporządkowane.
- ” Zamówiony zestaw ” nie oznacza, że kolejność jest semantyczna, tylko że istnieje pewna kolejność. Oczywiście obchodzi mnie to, że po ustaleniu kolejności jest zachowywana, chyba że jej zawartość zostanie zmodyfikowana.
- Przepraszam, nie ' nie wiedziałem, że istnieje implikacja dla niektórych ludzi. Miałem na myśli po prostu liniowo uporządkowany zbiór z matematyki. en.wikipedia.org/wiki/Total_order
- @jameslarge nie ma związku z zamówieniem ' nie muszą być mi obce. Jeśli wyprowadzę uporządkowany zestaw z listy, wiem dokładnie, jaka jest jego kolejność. Jeśli chcę zapewnić określoną kolejność, mogę posortować zestaw. Ale jeśli ' nie potrzebujesz zamówienia, możesz je po prostu zignorować.
Odpowiedz
Ogólną ideą zbioru lub słownika jest to, że planujesz wykonywać wiele operacji wyszukiwania. Jest zoptymalizowany pod kątem wspomnianych operacji wyszukiwania przy użyciu skrótu, który umożliwia wyszukiwanie O (1) w większości przypadków.
Kolejność jest wykonywana przy użyciu tablic lub połączonych list i faktycznie wykonuje operacje, w których kolejność jest ważna, są one zoptymalizowane dla tego , na przykład dołączanie wartości na końcu lub na początku.
Z natury tych dwóch struktur danych, żadna z nich nie jest zoptymalizowana dla obu. Nie oznacza to, że jest to niemożliwe, ale dotyczy obu struktur danych, jeśli chcesz zoptymalizować zarówno operacje wyszukiwania, jak i operacje na podstawie kolejności.
Więc masz ten kompromis między:
optymalizacja operacji wyszukiwania < => operacje na podstawie zamówienia < => użycie pamięci
Ogólny konsensus jest taki, że jako programista generalnie chcesz zoptymalizować pod kątem jednego lub drugiego, ale nie obu, i na pewno nikt nie jest zwolennikiem podwajania zużycia pamięci, gdy tylko potrzebujesz aby zoptymalizować jeden z dwóch.
To powiedziawszy, istnieją implementacje z obydwoma, a przynajmniej w Javie, konkretnie LinkedHashMap jest zarówno tablicą, jak i hash- słownik oparty na. Czasami możesz potrzebować obu, ale zaleca się użycie ArrayList, jeśli potrzebujesz tylko listy i HashMap, jeśli potrzebujesz tylko słownika .
Komentarze
- Hę? Java LinkedHashMap nie jest ” zarówno tablicą, jak i słownikiem opartym na skrótach „. Jest to ' w zasadzie HashMap (tj. Używa wewnętrznej tablicy) nałożonej na połączoną listę, aby umożliwić iterację w kolejności wstawiania.
- Liniowe struktury danych nie są ' t jedyne uporządkowane struktury danych; Można również zamówić drzewa binarne (takie jak czerwono-czarne i AVL). Inną operacją, która może być zaangażowana w kompromis, jest wstawianie (tablice są dość wydajne pod względem wyszukiwania, iteracji i wykorzystania pamięci, ale najwolniejsze, jeśli chodzi o wstawianie).