Implementazione di array in erlang

La mia domanda è, come vengono implementati gli array in Erlang, anziché gli elenchi.Implementazione di array in erlang

Con tipi immutabili fare le cose come,

move ([X | Xs], Ys) -> 
    [X | Ys]. 

Ls = move([1,2,3], [2,3,4])

prenderebbe costante mem nel mucchio, poiché questo è tutto il lavoro di riferimento.

Ma per la stessa roba in array

move (A1, A2) -> 
    array:set(0, array:get(0,A1),A2). 

A1 = array:from_list([1,2,3]). 
A2 = array:from_list([0,2,3,4]). 
A3 = move(A1,A2).

Will move qui usano dimensioni proporzionali alla A2 o sarà in grado di farlo in uno spazio costante come con gli array?

fonte

2013-05-08 Martin Kristiansen

Il modulo 'array' crea una struttura tupla annidata. È sia di dimensioni che di velocità efficiente. – rvirding

@rvirding, cosa intendi per struttura a tuple annidata? mi stai dicendo che le occhiate non sono O (1)? –

Per (si spera) chiarire un po 'le cose. Ricorda che in Erlang TUTTI i dati sono immutabili! Questo influisce profondamente su come manipoli i dati.

Il modulo array crea una struttura di tuple annidate in cui tutti gli slot di matrice contenenti dati si trovano allo stesso livello. La dimensione di ogni tupla è 10, quindi per l'accesso all'array abbiamo O (lg10 (N)). L'uso di una struttura annidata come questa è comune nelle lingue con dati immutabili. È possibile mantenere una matrice in una tupla piatta che potrebbe darvi letture veloci, ma le scritture diventerebbero lente e il hogging della memoria per grandi matrici/tuple dato che ogni scrittura implicherebbe la creazione di una nuova tupla. L'utilizzo di una struttura ad albero significa che molto meno dati vengono creati in una scrittura.

Il modo in cui la funzione move/2 influisce sull'utilizzo della memoria dipende un po 'dal fatto che si stia scrivendo in uno slot utilizzato o non utilizzato nell'array. Se lo slot è già in uso, l'utilizzo della memoria risultante sarà lo stesso. Se stai scrivendo su uno slot precedentemente inutilizzato, potresti dover far crescere l'array, il che significa che verrà utilizzata più memoria.

Questo è esattamente lo stesso del caso elenco.

Dipende anche dall'eventuale presenza di riferimenti alla vecchia struttura dati.

fonte

2013-05-09 14:34:45 rvirding

Vedo ciò che dici, e sono d'accordo sul fatto che gli array sono incompatibili con la pura programmazione funzionale e con i tipi di dati immutabili - tuttavia erlang è una strana borsa di api, e cose come ets, digraph e altri trucchi potrebbero significare che era possibile fare matrici in modo incisivo. Un array potrebbe essere implementato in modo tale da ottenere e impostare, semplicemente mutato un c nif o qualcos'altro. –

@MartinKristiansen tu * potresti * usare i NIF, ma se scrivi in un heap di processo di erlang dovresti assolutamente evitare di mutare i dati, il gc non se lo aspetta e otterrai strani comportamenti.L'ETS è in realtà abbastanza vicino a un processo se ci pensi, per esempio è legato ai processi e se ne va muore. Quindi non è così brutto come sembra prima. – rvirding

@rvinding, scommetto che potrei distruggere Erlang e implementare un array con i suoi dati nell'heap del sistema e configurare un monitor che lo pulisse nel caso in cui il proprietario fosse morto. Ma sì, se è allocata sull'heap del processo, tutto si rompe. La mia conclusione è che la denominazione è ... fuorviante, poiché indica O (1) aggiornato alla struttura, e non è questo il caso. –

È possibile trovare il codice sorgente here. Sembra, come menzionato @rvirding, che un array sia un albero funzionale. Non ho studiato profondamente l'implementazione - e non c'è alcun riferimento nella fonte all'origine della struttura dati - ma una rapida panoramica suggerisce che la peggiore è un qualche fattore logaritmico di N.

Mi piacerebbe una correzione se qualcun altro ha più familiarità con questa fonte/ha un momento per studiarlo.

fonte

2013-05-08 20:42:43 troutwine

Ho visto l'output dell'array: from_list (liste: duplicate (N,) 1), e sembra che qualcosa con una costante ricerca e aggiornamento - fondamentalmente una specie di albero. –

Implementazione di array in erlang

risposta

Problemi correlati