arrays - Array vs Lista en Elm

Question

Me sorprendió saber que Array y List eran dos tipos diferentes en Elm:

• Array

• List

En mi caso, tengo una List Int de 2.000.000 de longitud y necesito unos 10.000, pero no sé de antemano cuáles diez mil. Eso será proporcionado por otra lista. En pseudocódigo:

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

Estoy usando pseudocódigo porque claramente esto no es sintaxis de Elm (podría ser JavaScript legal).

¿Se pueden hacer estas selecciones de matriz en List o Array o ambas?

Answer 1

Algo como esto debería funcionar:

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

Convierte la lista de entrada en una matriz para una indexación rápida, luego asigna la lista de índices a sus valores correspondientes en la matriz. Tomé la función fromJust de esta pregunta de StackOverflow .

Answer 2

List es una lista vinculada que proporciona un tiempo de búsqueda O (n) basado en el índice. Obtener un elemento por índice requiere atravesar la lista sobre n nodos. La función de búsqueda de índice para la List no está disponible en la biblioteca central, pero puede usar el paquete elm-community/list-extra que proporciona dos funciones para la búsqueda (que varían según el orden de los parámetros): !! y getAt .

Array permite la búsqueda de índice O (log n) . Las búsquedas de índice en Array se pueden hacer usando Array.get . Las matrices se representan como árboles equilibrados de radix relajado .

Ambos son inmutables (todos los valores en Elm son inmutables), por lo que tiene concesiones en función de su situación. List es excelente cuando haces muchos cambios porque simplemente estás actualizando los punteros de la lista vinculada, mientras que Array es excelente para la búsqueda rápida pero tiene un rendimiento algo menor para las modificaciones, lo que querrás considerar si estás realizando muchos cambios. .