Array vs Liste in Elm

Question

Ich war überrascht zu erfahren, dass Array und List zwei verschiedene Arten in Elm waren:

• Array

• List

In meinem Fall, ich habe eine List Int von der Länge 2.000.000 und ich brauche etwa 10.000 von ihnen, aber ich weiß nicht im Voraus welche zehn tausend. Das wird von einer anderen Liste zur Verfügung gestellt. In Pseudo-Code:

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

Ich bin mit Pseudo-Code, da dies eindeutig nicht Elm Syntax ist (es könnte legal JavaScript sein).

Können diese Array-Auswahlen in List oder Array oder beiden vorgenommen werden?

Answer 1

List ist eine verkettete Liste, die O (n) Lookup-Zeit basierend auf Index bietet. Um ein Element nach Index zu erhalten, müssen Sie die Liste über n Knoten durchlaufen. Eine Index-Lookup-Funktion für List ist in der Core-Bibliothek nicht verfügbar. Sie können jedoch das elm-community/list-extra-Paket verwenden, das zwei Funktionen zum Nachschlagen (je nach Parameterreihenfolge) bietet: !! und getAt.

Array ermöglicht O (log n) Indexsuche. Index-Lookups auf Array können mit Array.get durchgeführt werden. Arrays werden als Relaxed Radix Balanced Trees dargestellt.

Beide sind unveränderlich (alle Werte in Elm sind unveränderlich), so dass Sie Kompromisse abhängig von Ihrer Situation haben. List ist großartig, wenn Sie eine Menge Änderungen vornehmen, weil Sie nur verknüpfte Listenzeiger aktualisieren, während Array für schnelle Suche geeignet ist, aber eine etwas schlechtere Leistung für Änderungen aufweist, die Sie berücksichtigen sollten, wenn Sie viele Änderungen vornehmen .

Answer 2

So etwas sollte funktionieren:

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 

Er wandelt die Eingabeliste in ein Array für eine schnelle Indizierung, dann ordnet die Liste der Indizes auf ihre entsprechenden Werte im Array. Ich nahm dieFunktion von this StackOverflow question.