Uczę się Haskell i czytam kilka artykułów dotyczących różnic w wydajności list Haskell i tablic (wstaw swój język).

Będąc uczniem, oczywiście po prostu używam list, nawet nie myśląc o różnicy w wydajności. Niedawno rozpocząłem badanie i znalazłem wiele bibliotek struktur danych dostępnych w Haskell.

Czy ktoś może wyjaśnić różnicę między listami, tablicami, wektorami, sekwencjami bez głębokiego zagłębiania się w informatyczną teorię struktur danych?

Czy są też jakieś typowe wzorce, w których można użyć jednej struktury danych zamiast innej?

Czy brakuje mi innych form struktur danych, które mogą być przydatne?

Listy Rock

Zdecydowanie najbardziej przyjazną strukturą danych sekwencyjnych w Haskell jest Lista

 data [a] = a:[a] | []

Listy dają ϴ (1) minusy i dopasowanie do wzorca. Standardowa biblioteka, a do tego znaczenia, preludium, jest pełna lista użytecznych funkcji, które powinien miot kod ( foldr, map, filter). Listy są trwałe , aka czysto funkcjonalne, co jest bardzo miłe. Listy Haskell nie są tak naprawdę „listami”, ponieważ są koindukcyjne (inne języki nazywają te strumienie), więc takie rzeczy

ones :: [Integer]
ones = 1:ones

twos = map (+1) ones

tenTwos = take 10 twos

pracować cudownie. Nieskończone struktury danych rock.

Listy w Haskell zapewniają interfejs podobny do iteratorów w imperatywnych językach (z powodu lenistwa). Ma więc sens, że są szeroko stosowane.

Z drugiej strony

Pierwszym problemem związanym z listami jest to, że ich indeksowanie (!!)zajmuje ϴ (k) czasu, co jest denerwujące. Dodatki mogą być również powolne ++, ale leniwy model oceny Haskella oznacza, że ​​można je traktować jako w pełni zamortyzowane, jeśli w ogóle się zdarzają.

Drugi problem z listami polega na tym, że mają słabą lokalizację danych. Rzeczywiste procesory mają wysokie stałe, gdy obiekty w pamięci nie są ułożone obok siebie. Tak więc w C ++ std::vectorma szybsze „snoc” (umieszczanie obiektów na końcu) niż jakakolwiek znana struktura danych z listami połączonymi, o których wiem, chociaż nie jest to trwała struktura danych, która jest mniej przyjazna niż listy Haskella.

Trzeci problem z listami polega na tym, że mają one mało miejsca. Wiązki dodatkowych wskaźników zwiększają pojemność pamięci (niezmiennie).

Sekwencje są funkcjonalne

Data.Sequencejest wewnętrznie oparty na drzewkach palców (wiem, że nie chcesz tego wiedzieć), co oznacza, że ​​mają pewne fajne właściwości

1. Czysto funkcjonalny. Data.Sequenceto w pełni trwała struktura danych.
2. Cholerny szybki dostęp do początku i końca drzewa. ϴ (1) (amortyzowane), aby uzyskać pierwszy lub ostatni element lub dołączyć drzewa. Na liście rzeczy są najszybsze, Data.Sequenceco najwyżej stały wolniej.
3. ϴ (log n) dostęp do środka sekwencji. Obejmuje to wstawianie wartości w celu tworzenia nowych sekwencji
4. API wysokiej jakości

Z drugiej strony Data.Sequencenie robi wiele dla problemu lokalizacji danych i działa tylko w przypadku kolekcji skończonych (jest mniej leniwy niż listy)

Tablice nie są dla osób o słabym sercu

Tablice są jedną z najważniejszych struktur danych w CS, ale nie pasują bardzo dobrze do leniwego, czystego, funkcjonalnego świata. Tablice zapewniają ϴ (1) dostęp do środka kolekcji i wyjątkowo dobrą lokalizację danych / stałe czynniki. Ale ponieważ nie pasują bardzo dobrze do Haskell, używanie ich jest uciążliwe. W obecnej bibliotece standardowej istnieje wiele różnych typów tablic. Należą do nich w pełni trwałe tablice, zmienne tablice dla monady IO, modyfikowalne tablice dla monady ST i nieopakowane wersje powyższych. Aby uzyskać więcej informacji, odwiedź wiki haskell

Wektor jest „lepszym” zestawem

Data.VectorPakiet zawiera wszystkie dobroci tablicy w poziomie i czystszego wyższej API. O ile naprawdę nie wiesz, co robisz, powinieneś ich użyć, jeśli potrzebujesz wydajności podobnej do tablicy. Oczywiście nadal obowiązują pewne zastrzeżenia - zmienne tablice, takie jak struktury danych, po prostu nie działają dobrze w czysto leniwych językach. Mimo to czasami potrzebujesz wydajności O (1) i Data.Vectordajesz ją w użytecznym pakiecie.

Masz inne opcje

Jeśli chcesz tylko listy z możliwością skutecznego wstawiania na końcu, możesz użyć listy różnic . Najlepszy przykład list zepsuć wydajność zwykle pochodzi z [Char]aliasu preludium jako String. Charlisty są wygodne, ale zwykle działają 20 razy wolniej niż łańcuchy C, więc możesz swobodnie używać Data.Textlub bardzo szybko Data.ByteString. Jestem pewien, że istnieją inne biblioteki zorientowane na sekwencje, o których teraz nie myślę.

Wniosek

Ponad 90% czasu potrzebuję sekwencyjnego gromadzenia na listach Haskella odpowiedniej struktury danych. Listy są jak iteratory, funkcje wykorzystujące listy mogą być łatwo używane z dowolną z tych innych struktur danych przy użyciu toListfunkcji, które są z nimi związane. W lepszym świecie preludium byłoby w pełni parametryczne co do typu używanego kontenera, ale obecnie []zaśmieca standardową bibliotekę. Tak więc używanie list (prawie) w każdym miejscu jest zdecydowanie w porządku.
Możesz uzyskać w pełni parametryczne wersje większości funkcji listy (i możesz z nich korzystać)

Prelude.map                --->  Prelude.fmap (works for every Functor)
Prelude.foldr/foldl/etc    --->  Data.Foldable.foldr/foldl/etc
Prelude.sequence           --->  Data.Traversable.sequence
etc

W rzeczywistości Data.Traversabledefiniuje interfejs API, który jest mniej więcej uniwersalny w każdej „liście takiej jak”.

Mimo to, chociaż potrafisz być dobry i pisać tylko w pełni parametryczny kod, większość z nas nie jest i używa listy w dowolnym miejscu. Jeśli się uczysz, zdecydowanie też to robisz.

EDIT: Na podstawie wypowiedzi zdaję sobie sprawę, że nigdy nie wyjaśnił, kiedy użyć Data.Vectorvs Data.Sequence. Macierze i wektory zapewniają niezwykle szybkie operacje indeksowania i dzielenia, ale są zasadniczo przejściowymi (imperatywnymi) strukturami danych. Czyste funkcjonalne struktury danych, takie jak Data.Sequencei []pozwalają wydajnie generować nowe wartości ze starych wartości, tak jakbyś zmodyfikował stare wartości.

  newList oldList = 7 : drop 5 oldList

nie modyfikuje starej listy i nie musi jej kopiować. Więc nawet jeśli oldListjest niewiarygodnie długi, ta „modyfikacja” będzie bardzo szybka. podobnie

  newSequence newValue oldSequence = Sequence.update 3000 newValue oldSequence 

stworzy nową sekwencję z newValuefor zamiast zamiast 3000 elementów. Ponownie nie niszczy starej sekwencji, po prostu tworzy nową. Ale robi to bardzo skutecznie, biorąc O (log (min (k, kn)), gdzie n jest długością sekwencji, a k jest zmodyfikowanym indeksem.

Nie możesz tego łatwo zrobić za pomocą Vectorsi Arrays. Można je modyfikować, ale jest to prawdziwa konieczność, dlatego nie można tego zrobić w zwykłym kodzie Haskell. Oznacza to operacje w Vectorpakiecie, które dokonują modyfikacji snoci consmuszą kopiować cały wektor, więc poświęć trochę O(n)czasu. Jedynym wyjątkiem jest to, że można używać wersji mutable ( Vector.Mutable) wewnątrz STmonady (lub IO) i wykonywać wszystkie modyfikacje tak, jak w trybie rozkazującym. Kiedy skończysz, „zamrażasz” wektor, aby przekształcić się w niezmienną strukturę, której chcesz używać z czystym kodem.

Mam wrażenie, że powinieneś domyślnie używać, Data.Sequencejeśli lista nie jest odpowiednia. Używaj Data.Vectortylko wtedy, gdy wzorzec użytkowania nie wymaga wielu modyfikacji lub jeśli potrzebujesz wyjątkowo wysokiej wydajności w obrębie monad ST / IO.

Jeśli całe to gadanie o STmonadzie wprawia cię w zakłopotanie: tym bardziej powód, by trzymać się czysto szybko i pięknie Data.Sequence.