Czy istnieje biblioteka, która udostępnia strukturę danych, która zachowuje kolejność pozycji i nie zawiera żadnych duplikatów? I czy istnieje odpowiednia nazwa takiej struktury danych?Lista bez duplikatów lub zamówionego zestawu
Oczekuję, że zachowa się jak lista z nub zastosowaną po każdej operacji na niej. Oczywiście nie spodziewam się, że zostanie to wdrożone bezskutecznie.
Oto jedno rozwiązanie:
Użyj fingertree z monoid Set jako swojej miary. Następnie w przypadku wkładek sprawdź najpierw członkostwo, korzystając z measure pełnego ustawienia palca. To daje O(log(n)) minusów i snoc, O(1) usuwa.
Oto inne rozwiązanie:
Pair normalny lista z normalnym Set i dostać w zasadzie ten sam efekt. Otrzymujesz lepsze stałe czynniki, ale O(log(n)) usuwa.
Oto pytanie: co chcesz zrobić po wstawieniu duplikatu? Czy należy zachować obecną pozycję? Nowa pozycja? Kolejki priorytetów mogą być zbliżone do tego, co chcesz.
To przypomina mi Java [LinkedHashSet] (http://docs.oracle.com/javase/6/docs/api/java/util/LinkedHashSet.html). Więc przypuszczam, że podobne podejście mogłoby zostać użyte dla niezmiennej funkcjonalnej struktury danych. –
Jeśli twój typ należy do 'Ord', możesz użyć' Data.Set' do zapisu i 'ordNub', który pobiera' O (n * log m) ', gdzie' n' to liczba elementów i 'm 'liczba unikalnych elementów. Jeśli 'Hashable', a nie' Ord', możesz zrobić to samo z 'Data.HashSet'. Czy byłoby to wystarczająco nieefektywne? –
Witaj 2013, czy dotarłeś do rozwiązania? – akst