Array vs List a Elm

Sono stato sorpreso di apprendere che Array e List erano due tipi diversi a Elm:Array vs List a Elm

Nel mio caso, ho avere un List Int di lunghezza 2.000.000 e ho bisogno di circa 10.000 di loro ma non so in anticipo quali dieci mille. Questo sarà fornito da un'altra lista. In pseudocodice:

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

Sto usando pseudocodice perché chiaramente questo non è la sintassi Elm (potrebbe essere legale JavaScript).

Queste selezioni di array possono essere eseguite in List o Array o in entrambi?

fonte

2016-06-08 john mangual

'List' è una struttura a lista collegata, quindi l'espressione' y [x [i]] 'è una ricerca O (n) per' i'th in 'x' più un'altra ricerca O (n) per l'elemento in 'y'. In altre parole, per 10000 ricerche tra 2mil elementi questo sarà proibitivamente lento. Usa matrice. –

A meno che non sia garantito l'ordinamento di y, allora funzionerà un diverso algoritmo –

Solo per curiosità: qual è il problema più ampio della tua risoluzione selezionando 10.000 elementi da una lista di 2.000.000 di elementi? –

List è un elenco collegato che fornisce il tempo di ricerca O (n) in base all'indice. Ottenere un elemento per indice richiede attraversare la lista oltre i nodi n. Una funzione di ricerca indice per List non è disponibile nella libreria principale ma è possibile utilizzare il pacchetto elm-community/list-extra che fornisce due funzioni per la ricerca (che variano in base all'ordine dei parametri): !! e getAt.

Array consente la ricerca dell'indice O (log n). Le ricerche dell'indice su Array possono essere eseguite utilizzando Array.get. Gli array sono rappresentati come Relaxed Radix Balanced Trees.

Entrambi sono immutabili (tutti i valori in Elm sono immutabili), quindi i trade-off dipendono dalla situazione. List è fantastico quando si apportano molte modifiche perché si stanno semplicemente aggiornando i puntatori degli elenchi collegati, mentre lo Array è ottimo per una ricerca rapida ma ha prestazioni leggermente inferiori per le modifiche, che è necessario prendere in considerazione se si apportano molte modifiche .

fonte

2016-06-08 16:17:36

Non ho controllato, ma avrei pensato che Array fosse una forma di albero rosso-nero con O (lg n) lookup? –

@ SørenDebois hai assolutamente ragione, la ricerca è O (lg n) in 'Array' di Elm – halfzebra

Sembra che Array stia usando [Relaxed Radix Balanced Trees] (http://elm-lang.org/blog/announce/0.12. 1 # array) sotto il cofano. Ho aggiornato la mia risposta. –

Qualcosa del genere dovrebbe funzionare:

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

converte la lista di input per un array per l'indicizzazione veloce, quindi mappa l'elenco degli indici ai valori corrispondenti nell'array. Ho preso la funzione fromJust da this StackOverflow question.

fonte

2016-06-08 16:27:07

risposta

Problemi correlati