Array vs listy w Elm

Question

Byłem zaskoczony, aby dowiedzieć się, że Array i List były dwa różne typy w Elm:

• Array

• List

W moim przypadku, posiadam List Int o długości 2 000 000 i potrzebuję około 10 000, ale nie wiem z góry, które dziesięć tysiąc. Zostanie to zapewnione przez inną listę. W Pseudokod:

x = [ 1,1,0,30,...,255,0,1 ] 
y = [ 1,4,7,18,36,..., 1334823 , ... 1899876 ] 
z = [ y[x[0]], y[x[1]], ... ] 

Używam Pseudokod bo wyraźnie nie jest to składnia Elm (może to być legalne JavaScript).

Czy te selekcje można wykonać w List lub Array lub obu?

Answer 1

List jest połączoną listą, która zapewnia czas wyszukiwania O (n) w oparciu o indeks. Uzyskiwanie elementu według indeksu wymaga przechodzenia przez listę nad węzłami o numerach n. Funkcja wyszukiwania indeksu dla List nie jest dostępna w bibliotece rdzenia, ale można użyć pakietu elm-community/list-extra, który zapewnia dwie funkcje wyszukiwania (różniące się w zależności od kolejności parametrów): !! i getAt.

Array pozwala na O (log n) indeksowania. Wyszukiwanie indeksu na Array można wykonać za pomocą Array.get. Tablice są reprezentowane jako Relaxed Radix Balanced Trees.

Obie są niezmienne (wszystkie wartości w Wiąz są niezmienne), więc masz kompromisy w zależności od twojej sytuacji. List jest świetny, gdy wprowadzasz wiele zmian, ponieważ tylko aktualizujesz wskaźniki listy połączonych, natomiast Array świetnie nadaje się do szybkiego wyszukiwania, ale ma nieco gorszą wydajność dla modyfikacji, które powinieneś rozważyć, jeśli robisz wiele zmian .

Answer 2

Coś jak to powinno działać:

import Array 
import Debug 

fromJust : Maybe a -> a 
fromJust x = case x of 
    Just y -> y 
    Nothing -> Debug.crash "error: fromJust Nothing" 

selectFromList : List a -> List Int -> List a 
selectFromList els idxs = 
    let arr = Array.fromList els 
    in List.map (\i -> fromJust (Array.get i arr)) idxs 

Przekształca listę wejściową do tablicy do szybkiego indeksowania, a następnie odwzorowuje listę indeksów do odpowiadających im wartości w tablicy. Przyjąłem funkcję fromJust z this StackOverflow question.