Kiedy powinienem wybrać Vector w Scali?

200

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?

scala vector scala-collections

— Duncan McGregor
źródło

1

Wydaje mi się, że mam na myśli to, że w Javie chciałbym pisać List<String> l = new ArrayList<String>()blogi Scala. Czy wierzysz, że wszyscy używają Listu, aby uzyskać trwałą kolekcjonerską dobroć - ale czy Vector jest wystarczający do ogólnego zastosowania, że powinniśmy go używać zamiast Listu?

— Duncan McGregor,

9

@Debilski: Zastanawiam się, co przez to rozumiesz. Dostaję, Listkiedy piszę Seq()na REPL.

— missingfaktor,

1

Hmm, cóż, tak jest napisane w dokumentach. Może dotyczy to tylko IndexedSeq.

— Debilski

1

Komentarz dotyczący domyślnego konkretnego typu Seqma ponad trzy lata. Od wersji Scala 2.11.4 (i wcześniejszych) domyślnym typem konkretnym Seqjest List.

— Mark Canlas

3

W przypadku dostępu losowego wektor jest lepszy. Dostęp do głowy, ogona jest lepszy. W przypadku operacji zbiorczych, takich jak mapa, filtr, wektor jest preferowany, ponieważ wektor jest zorganizowany z 32 elementami jako porcja, podczas gdy lista zorganizowała elementy ze wskaźnikami do siebie, nie ma gwarancji, że te elementy są blisko siebie.

— johnsam

280

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.

— Daniel Spiewak
źródło

2

2.10 jest już od jakiegoś czasu, czy dopasowanie wzorca listy jest jeszcze lepsze niż Vector?

— Tim Gautier

3

Dopasowanie wzorca listy nie jest już lepsze. W rzeczywistości jest wręcz przeciwnie. Na przykład, aby uzyskać głowę i ogon, możesz zrobić case head +: taillub case tail :+ head. Aby dopasować do pustych, możesz to zrobić case Seq()i tak dalej. Wszystko, czego potrzebujesz tam jest w API, który jest bardziej uniwersalny niż List„s

— Kai Sellgren

Listjest implementowany z pojedynczo połączoną listą. Vectorjest implementowany jak Java ArrayList.

— Josiah Yoder,

6

@JosiahYoder Zaimplementowano nic takiego jak ArrayList. ArrayList otacza tablicę, której dynamicznie zmienia rozmiar. Wektor to trójka , w której kluczami są indeksy wartości.

— John Colanduoni,

1

Przepraszam. Szukałem źródła internetowego, które było niejasne w szczegółach. Czy powinienem poprawić moje wcześniejsze oświadczenie? Czy to zła forma?

— Josiah Yoder,

93

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.

— Daniel C. Sobral
źródło

3

Dziękuję za odpowiedź. Co rozumiesz przez „ma świetną lokalizację”?

— Ngoc Dao

10

@ngocdaothanh Oznacza to, że dane są pogrupowane blisko siebie w pamięci, co zwiększa szansę, że dane znajdą się w pamięci podręcznej, gdy będą potrzebne.

— Daniel C. Sobral

1

@ user247077 Tak, listy mogą pokonać wektory pod względem wydajności, biorąc pod uwagę dane, o których wspomniałem. I nie wszystkie działania wektorów są amortyzowane O (1). W rzeczywistości w niezmiennych strukturach danych (co ma miejsce), alternatywne wstawianie / usuwanie na obu końcach w ogóle się nie amortyzuje. W takim przypadku pamięć podręczna jest bezużyteczna, ponieważ zawsze kopiujesz wektor.

— Daniel C. Sobral

1

@ user247077 Być może nie wiesz, że Vectorjest to niezmienna struktura danych w Scali?

— Daniel C. Sobral

1

@ użytkownika o znacznie większym profilu alokacji pamięci.

— Daniel C. Sobral

29

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.

— dth
źródło

24

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.

— Luigi Plinge
źródło

Ale jeśli iteracja Vectora jest szybsza niż lista, a ja również mogę zmapować fold fold itp., To oprócz niektórych wyspecjalizowanych przypadków (zasadniczo wszystkich algorytmów FP, które są wyspecjalizowane dla List), wydaje się, że List jest zasadniczo dziedzictwem.

— Duncan McGregor

@ Duncan, gdzie słyszałeś, że iteracja Vectora jest szybsza? Na początek musisz śledzić i aktualizować bieżący indeks, czego nie potrzebujesz z połączoną listą. Nie nazwałbym funkcji listy „specjalnymi przypadkami” - to chleb powszedni programowania funkcjonalnego. Nieużywanie ich byłoby jak próba programowania Java bez pętli for lub while.

— Luigi Plinge

2

Jestem pewien Vector, że iteracja jest szybsza, ale ktoś musi ją przetestować, aby mieć pewność.

— Daniel Spiewak

Myślę, że (?) Elementy Vectorfizycznie istnieją razem w pamięci RAM w grupach po 32, które pełniej mieszczą się w pamięci podręcznej procesora ... więc jest mniej miss pamięci podręcznej

— richizy

2

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 )

— Debilski
źródło

1

Tyle się nauczyć ... Co oznacza Vector jako domyślny Seq? Jeśli piszę Seq (1, 2, 3), dostaję List [Int], a nie Vector [Int].

— Duncan McGregor,

2

Jeśli masz dostęp losowy, użyj IndexedSeq. Co też jest Vector, ale to już inna sprawa.

— Daniel C. Sobral

@DuncanMcGregor: Wektor jest domyślną IndexedSeqimplementacją Seq. Seq(1, 2, 3)jest LinearSeqimplementowany przy użyciu List.

— pathikrit

0

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.

— Joshua Hartman
źródło

Trzymam się królestwa niezmiennych, trwałych kolekcji. Chodzi mi o to, że nawet jeśli nie potrzebuję dostępu losowego, czy Vector skutecznie zastąpił Listę?

— Duncan McGregor,

2

Zależy trochę od przypadku użycia. Wektory są bardziej zrównoważone. Iteracja jest szybsza niż lista, a losowy dostęp jest znacznie szybszy. Aktualizacje są wolniejsze, ponieważ nie jest to tylko lista poprzedzająca, chyba że jest to zbiorcza aktualizacja z fold, którą można wykonać za pomocą konstruktora. To powiedziawszy, uważam, że Vector jest najlepszym domyślnym wyborem, ponieważ jest tak wszechstronny.

— Joshua Hartman

Myślę, że trafia do sedna mojego pytania - wektory są tak dobre, że równie dobrze możemy je wykorzystać tam, gdzie przykłady zwykle pokazują Listę.

— Duncan McGregor,