Kiedy powinienem wybrać Vector w Scali?

Wygląda na to, że Vectorspóźniło się na imprezę kolekcjonerską Scali i wszystkie wpływowe posty na blogu już odeszły.

W Javie ArrayListjest domyślną kolekcją - mogę jej użyć, LinkedListale tylko wtedy, gdy przemyślałem algorytm i staram się go zoptymalizować. Czy w Scali powinienem używać Vectorjako domyślnego Seq, czy próbować ustalić, kiedy Listjest to bardziej odpowiednie?

Zasadniczo domyślnie jest używane Vector. Jest to szybsze niż Listna prawie wszystko i więcej pamięci efektywne dla większych niż trywialne wielkości sekwencji. Zobacz tę dokumentację względnej wydajności Vector w porównaniu do innych kolekcji. Jest kilka wad do zrobienia Vector. Konkretnie:

• Aktualizacje na czele są wolniejsze niż List(choć nie tak bardzo, jak mogłoby się wydawać)

Kolejnym minusem przed Scalą 2.10 było to, że lepsza była obsługa dopasowania wzorca List, ale zostało to naprawione w 2.10 za pomocą uogólnień +:i :+ekstraktorów.

Istnieje również bardziej abstrakcyjny, algebraiczny sposób podejścia do tego pytania: jaki rodzaj sekwencji masz koncepcyjnie ? Co koncepcyjnie z tym robicie? Jeśli widzę funkcję, która zwraca an Option[A], wiem, że funkcja ma pewne dziury w swojej dziedzinie (a zatem jest częściowa). Możemy zastosować tę samą logikę do kolekcji.

Jeśli mam sekwencję typów List[A], skutecznie stwierdzam dwie rzeczy. Po pierwsze, mój algorytm (i dane) ma całkowicie strukturę stosu. Po drugie, twierdzę, że jedyne, co zamierzam zrobić z tą kolekcją, to pełne, O (n) wędrówki. Te dwa naprawdę idą w parze. I odwrotnie, jeśli mam coś typu Vector[A], jedyne, co zapewniam, to to, że moje dane mają dobrze określoną kolejność i skończoną długość. Zatem twierdzenia są słabsze Vector, a to prowadzi do większej elastyczności.

Cóż, Listmoże być niewiarygodnie szybko, jeśli algorytm może być realizowany wyłącznie z ::, headi tail. Miałem lekcję tego bardzo niedawno, kiedy pokonałem Javę, splitgenerując Listzamiast Array, i nie byłem w stanie pobić tego niczym innym.

Jednak Listma zasadniczy problem: to nie działa z algorytmów równoległych. Nie mogę podzielić Listna wiele segmentów ani połączyć ich w efektywny sposób.

Istnieją inne rodzaje kolekcji, które znacznie lepiej radzą sobie z równoległością - i Vectorjest jedną z nich. Vectorma również doskonałą lokalizację - co Listnie ma - co może być prawdziwym plusem dla niektórych algorytmów.

Biorąc wszystko pod uwagę, Vectorjest to najlepszy wybór, chyba że masz określone względy, które sprawiają, że jedna z pozostałych kolekcji jest lepsza - na przykład możesz wybrać, Streamczy chcesz leniwej oceny i buforowania ( Iteratorjest szybszy, ale nie buforuje), lub Listjeśli algorytm jest naturalnie implementowany wraz z operacjami, o których wspomniałem.

Nawiasem mówiąc, to korzystne jest użycie Seqlub IndexedSeqjeśli nie chcesz kawałek specyficzną API (takich jak List„s ::), albo nawet GenSeqczy GenIndexedSeqjeśli algorytm może być prowadzony równolegle.

Niektóre stwierdzenia tutaj są mylące lub nawet błędne, szczególnie idea niezmienności. Wektor w Scali przypomina coś w rodzaju ArrayList. Zarówno lista, jak i wektor są niezmiennymi, trwałymi (tzn. „Tanio, aby otrzymać zmodyfikowaną kopię”) strukturami danych. Nie ma rozsądnego domyślnego wyboru, ponieważ może to być zmienne struktury danych, ale zależy to raczej od tego, co robi twój algorytm. Lista jest pojedynczo połączoną listą, podczas gdy Vector jest liczbą całkowitą 32, tj. Jest rodzajem drzewa wyszukiwania z węzłami stopnia 32. Korzystając z tej struktury, Vector może zapewnić dość popularne operacje dość szybko, tj. W O (log_32 ( n)). Działa to w przypadku prepend, append, update, random access, dekompozycji w głowie / ogonie. Iteracja w kolejności sekwencyjnej jest liniowa. Z drugiej strony lista zapewnia po prostu liniową iterację i stały czas wyprzedzania, rozkład głowy / ogona.

Może to wyglądać tak, jakby Vector był dobrym zamiennikiem listy w prawie wszystkich przypadkach, ale poprzedzanie, dekompozycja i iteracja są często kluczowymi operacjami na sekwencjach w programie funkcjonalnym, a stałe tych operacji są (znacznie) wyższe dla wektora z powodu do bardziej skomplikowanej struktury. Zrobiłem kilka pomiarów, więc iteracja jest około dwa razy szybsza dla list, prepend jest około 100 razy szybszy na listach, rozkład głowy / ogona jest około 10 razy szybszy na listach, a generowanie z ruchu jest około 2 razy szybsze dla wektorów. (Jest tak prawdopodobnie dlatego, że Vector może przydzielić tablice 32 elementów jednocześnie, gdy budujesz go za pomocą konstruktora zamiast dodawania lub dodawania elementów jeden po drugim).

Więc jakiej struktury danych powinniśmy użyć? Zasadniczo istnieją cztery typowe przypadki:

• Musimy tylko transformować sekwencje za pomocą operacji takich jak mapowanie, filtrowanie, składanie itp.: W zasadzie nie ma to znaczenia, powinniśmy zaprogramować nasz algorytm ogólnie, a może nawet skorzystać z akceptacji sekwencji równoległych. W przypadku operacji sekwencyjnych lista jest prawdopodobnie nieco szybsza. Ale powinieneś przeprowadzić analizę porównawczą, jeśli musisz zoptymalizować.
• Potrzebujemy dużo losowego dostępu i różnych aktualizacji, więc powinniśmy użyć wektora, lista będzie zbyt powolna.
• Działamy na listach w klasyczny funkcjonalny sposób, budując je przez poprzedzanie i iterację przez rekurencyjny rozkład: lista użycia, wektor będzie wolniejszy o współczynnik 10-100 lub więcej.
• Mamy algorytm krytyczny pod względem wydajności, który jest w zasadzie konieczny i zapewnia losowy dostęp do listy, coś w rodzaju szybkiego sortowania: użyj imperatywnej struktury danych, np. ArrayBuffer, lokalnie i kopiuj dane zi do niego.

W przypadku niezmiennych kolekcji, jeśli chcesz sekwencję, twoją główną decyzją jest, czy użyć znaku IndexedSeqa lub a LinearSeq, który daje różne gwarancje wydajności. IndexedSeq zapewnia szybki losowy dostęp do elementów i szybką operację długości. LinearSeq zapewnia szybki dostęp tylko do pierwszego elementu za pośrednictwem head, ale ma również szybką tailoperację. (Zaczerpnięte z dokumentacji Seq.)

Dla IndexedSeqzwykle wybierasz Vector. Rangesi WrappedStringsą również indeksowanymi sekwencjami.

W LinearSeqprzypadku zwykle wybierasz Listleniwy odpowiednik Stream. Inne przykłady to Queues i Stacks.

Tak więc w języku Java, ArrayListużywane podobnie do Scali Vectori LinkedListpodobnie do Scali List. Ale w Scali wolałbym używać Listy częściej niż Vector, ponieważ Scala ma znacznie lepszą obsługę funkcji, które obejmują przechodzenie przez sekwencję, takich jak mapowanie, składanie, iterowanie itp. Będziesz miał tendencję do używania tych funkcji do manipulowania listą jako cały, a nie losowy dostęp do poszczególnych elementów.

W sytuacjach, w których występuje losowy dostęp i losowa mutacja, a Vector(lub - jak mówią doktorzy - a Seq) wydaje się być dobrym kompromisem. Tak sugerują również parametry wydajności .

Ponadto Vectorklasa wydaje się ładnie grać w środowiskach rozproszonych bez dużego powielania danych, ponieważ nie ma potrzeby wykonywania kopiowania przy zapisie dla całego obiektu. (Zobacz: http://akka.io/docs/akka/1.1.3/scala/stm.html#persistent-datastructures )

Jeśli programujesz niezmiennie i potrzebujesz dostępu losowego, Seq jest właściwą drogą (chyba że potrzebujesz zestawu, co często robisz). W przeciwnym razie lista działa dobrze, z tym wyjątkiem, że jej operacji nie można zrównoleglać.

Jeśli nie potrzebujesz niezmiennych struktur danych, trzymaj się ArrayBuffer, ponieważ jest to Scala odpowiednik ArrayList.