Data.Set: czy zawsze wie najlepiej?

Potrzebuję reprezentować zestaw i zaczynam pracować z Data.Set. Widzę, że naprawdę nic nie trzeba robić - singleton, union, intersection itp. Są po prostu tam. Lubię to. Mogę wyrazić "co", a nie "jak". Ale mój wewnętrzny programator C jest niewygodny. Istnieje wiele sposobów implementacji zestawu (drzewo binarne, tablica hasłowa, tablica logiczna itp.). Czy naprawdę mogę zaufać Data.Set, aby wybrać najlepszy? Czy mogę w jakiś sposób go poprowadzić, czy po prostu poddam się jego (przyznaję, prawdopodobnie wyższemu) osądowi?Data.Set: czy zawsze wie najlepiej?

Źródło

2012-03-18 gcbenison

Idź z opcją 2, szczególnie jeśli jest przeznaczona do użycia w kodzie produkcyjnym. – Shredderroy

Data.Set nie ma wewnętrznej inteligencji (po prostu zobacz the source!). To tylko zrównoważone drzewo lub uporządkowane elementy. Możesz spojrzeć na hackage dla wielu innych struktur zestawów i zestawów o różnych parametrach wydajności. Na przykład zobacz unordered-containers (HashSet), HashTables i bloomfilter.

Źródło

2012-03-18 04:14:00

OK, dzięki. Sądzę, że następnym pytaniem jest - czy istnieje lub kiedykolwiek będzie "DataSet", któremu można zaufać, że dokonał niektórych wyborów dotyczących implementacji dla osoby dzwoniącej? tj. gdy powiedziano mu, że domena to tylko [1..8], to może on po prostu użyć bajtu? – gcbenison

Widząc wszystkie wartości w pudełkach, nie będziesz w stanie użyć bajtu. Jak wdrożysz to w Haskell? Sądzę, że sprawdziłbyś wartość danych wejściowych i ustawiłeś bit w swoim 'Word8' ręcznie, a następnie musiałbyś przydzielić wartość w ramkach dla każdego wyszukiwania? Nie brzmi dla mnie jak wygrana w wydajności. –

Wygląda na to, że wciąż można dokonać porównania równości bez żadnych przydziałów, a być może związków i przecięć z jednym przydziałem Word8. – gcbenison

Ogólne Data.Set używa zrównoważonego drzewa binarnego. Jeśli masz zestawy liczb całkowitych lub bitowych, będziesz potrzebował Data.IntSet, która używa Patricii próbuje.

Obie implementacje zostały wyostrzone przez lat w konkurencji, aby uzyskać najlepszą wydajność z Haskell.

Poddaj się Dorothy!

Źródło

2012-03-18 04:12:43

W połączeniu z odpowiedzią Thomasa razem stanowią doskonałą odpowiedź. 'Data.Set' jest świetny, ma wspaniały interfejs i jest wystarczająco szybki w większości przypadków (znacznie lepiej niż ktokolwiek z nas mógłby ręcznie), ale (jak wszystko) nie rozwiąże każdego problemu optymalnie. Nie przejmuj się tym, dopóki nie musisz; kiedy to zrobisz, sprawdź niektóre inne biblioteki. – luqui

@luqui Myślę, że gdy masz zestawy liczb całkowitych, warto przejść od razu do 'Data.IntSet'. –

Data.Set: czy zawsze wie najlepiej?

Odpowiedz

Powiązane problemy