Array vs List in Elm

Я был удивлен, узнав, что Array и List были двумя разными типами в Elm:

В моем случае у меня есть List Int длиной 2 000 000, и мне нужно около 10 000 из них, но я заранее не знаю, что десять тысяч. Это будет предоставлено другим списком. В псевдокоде:

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

Я использую псевдокод, потому что ясно, что это не синтаксис Elm (это может быть законный JavaScript).

Можно ли выполнить выбор этих массивов в List или Array или обоих?

Ответ 1

List - связанный список, который обеспечивает O (n) время поиска по индексу. Получение элемента по индексу требует прохождения списка по узлам n. Функция поиска индекса для List недоступна в основной библиотеке, но вы можете использовать пакет elm-community/list-extra, который предоставляет две функции для поиска (меняя порядок параметров ): !! и getAt.

Array позволяет искать индекс O (log n). Поиск по индексу Array можно выполнить с помощью Array.get. Массивы представлены как Relaxed Radix Balanced Trees.

Оба неизменяемы (все значения в Elm неизменяемы), поэтому у вас есть компромиссы в зависимости от вашей ситуации. List отлично, когда вы делаете много изменений, потому что вы просто обновляете указатели ссылок, тогда как Array отлично подходит для быстрого поиска, но имеет несколько худшую производительность для модификаций, которые вы хотите рассмотреть, если вы делаете много изменений.

Ответ 2

Что-то вроде этого должно работать:

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

Он преобразует входной список в массив для быстрой индексации, затем сопоставляет список индексов с их соответствующими значениями в массиве. Я взял функцию fromJust из fooobar.com/info/456744/....