Typ słownika z określoną kolejnością klawiszy

Chciałbym użyć typu, który zachowuje się jak prosta lista par [(a,b)], który służy jako słownik, odwzorowuje klucze typu a na wartości typu b, zachowując "użytkownika" -specified ", zdefiniowana kolejność klawiszy. (tak jak w przypadku zwykłych list - chciałbym móc "dołączyć" element, który jest następnie rozpoznawany jako "ostatni element"). Jednak chciałbym wyszukać przypadkowo dostęp do kluczy o wydajności lepszej niż liniowa, tj. co Data.Map zapewnia. Jednym rozwiązaniem byłoby po prostu utrzymać mapę zwyczajne oprócz listy kluczy, która określa ich kolejność:Typ słownika z określoną kolejnością klawiszy

data OrderedDict a b = OrderedDict (Map a b) [a]

a następnie zdefiniować append operacje itp, które prowadzą dwie główne kolekcje zsynchronizowane. Wydaje się jednak, że brzydkie jest utrzymywanie dwóch oddzielnych kolekcji tych samych kluczy. Czy istnieje gotowy typ danych, który już łączy klucze uporządkowane z wydajnym wyszukiwaniem losowym według klucza?

Źródło

2012-06-08 gcbenison

Java [LinkedHashMap] (http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashMap.html) wydaje się robić coś podobnego : wątek lista kluczy przez mapę. Python's OrderedDict to po prostu lista par, więc nie są tu pomocą. –

Co masz na myśli mówiąc "zdefiniowany porządek"? Biorąc pod uwagę dwa klucze 'a1' i' a2', czy a priori ustalono, czy 'a1' poprzedza' a2', czy też jest priorytetem określonym w czasie wykonywania? – Peter

@peter Mam na myśli "zdefiniowaną kolejność" w tym samym znaczeniu, co w przypadku zwykłych list - jeśli dodam "a2" po dodaniu "a1", to "a1" poprzedza 'a2' – gcbenison

O ile nie całkowicie nie rozumiem twojego pytania, Data.Map robi dokładnie to, używając instancji typu klucza Ord do zamawiania. Ponieważ jest to drzewo binarne, implementacja zachowuje również zamówione klucze.

Data.Map.keys daje klucze do mapy w porządku rosnącym; ponieważ transformacje, takie jak map, mapy są czysto funkcjonalne, kolejność przejścia jest nieistotna, a wszystkie sposoby uzyskiwania sekwencji kluczy lub par klucz/wartość poza mapą dają uporządkowaną listę.

Źródło

2012-06-08 06:50:30 valderman

Wierzę, że gcbenison prosi o coś w rodzaju danych .Map' ale z dodaną właściwością zachowania porządku, w którym są wstawiane klucze. – huon

Jeśli masz niestandardowy typ klucza, możesz go zdefiniować własne zamówienie. Chociaż to nadal działa tylko wtedy, gdy zamówienie może być generowane proceduralnie. – Evi1M4chine

Jeśli chcesz po prostu zachować pewną stałym zamówienia (np czas wstawiania) oprócz posiadania O (log n) przeglądowych/wstawki, można po prostu korzystać z wielu map i zaktualizować je jednocześnie:

Map a b do przechowywania rzeczywistych danych i
Map Int a który daje ci klucz i-th w zamówieniu. (Jeśli trzeba także kwerendy indeks danego klucza można dodać Map a Int)

Źródło

2012-06-08 07:29:02 Peter

Spójrz na ixset biblioteki - to pozwala na utrzymanie zbiorów indeksowanych przez wielu kolumn (o a i Int w twojej walizka). To jest o wiele łatwiejsze w utrzymaniu niż utrzymywanie spójności map ręcznie

Źródło

2012-06-08 09:05:19 nponeccop

Dzięki - 'ixset' jest fajny. Nie sądzę, że to całkiem zgadza się z rachunkiem w tym przypadku, ponieważ może pozwolić na niespójny stan (wiele wpisów z tym samym polem "Int") i wymagałoby wywołującego wykonującego operację 'append' do jawnego określenia indeksu - coś nie wymagane przez zwykłe listy. – gcbenison

Typ słownika z określoną kolejnością klawiszy

Odpowiedz

Powiązane problemy