Simile all'accesso in C++ per riferimento?

Question

Sto costruendo un algoritmo di clustering in C++, ma non mi occupo bene di OOP e dello stato delle variabili (dati dei membri) che cambiano. Per un algoritmo di una certa complessità, trovo questo un ostacolo al mio sviluppo.

Quindi, stavo pensando di cambiare il linguaggio di programmazione, in uno dei linguaggi funzionali: Ocaml o F #. Oltre a dover cambiare la mia mentalità su come affrontare la programmazione, c'è qualcosa che ho bisogno di chiarire. In C++, utilizzo una coda doppia per far scorrere una finestra di tempo attraverso i dati. Dopo un certo periodo di tempo, i dati più vecchi vengono rimossi e vengono aggiunti nuovi dati. I dati che non sono ancora troppo vecchi rimangono nella coda del doppio fine.

Un altro compito, più impegnativo, è confrontare le proprietà di uno di ciascun oggetto. Ogni oggetto è i dati di un certo periodo di tempo. E se ho un migliaio di oggetti dati in una determinata finestra temporale, ho bisogno di confrontarli tra nessuno o venti o trenta, a seconda. E alcune proprietà dell'oggetto confrontato potrebbero cambiare come risultato di questo confronto. In C++, faccio tutto usando i riferimenti, il che significa che accedo agli oggetti in memoria, che non vengono mai copiati, quindi l'algoritmo funziona alla massima velocità (per la mia conoscenza di C++).

Ho letto sulla programmazione funzionale e l'idea che ottengo è che ogni funzione esegue un'operazione e che i dati originali (l'input) non vengono modificati. Ciò significa che la lingua copia la struttura dei dati ed esegue la trasformazione richiesta. In tal caso, l'utilizzo della programmazione funzionale ritarderà notevolmente l'esecuzione dell'algoritmo. È corretto? Altrimenti, se esiste un modo rapido per eseguire la trasformazione dei dati, è possibile mostrarmi come farlo? Un esempio molto piccolo sarebbe fantastico.

Spero di avere qualche tipo di struttura. Ho letto che sia Ocaml che F # sono utilizzati in progetti di ricerca e scientifici.

Answer 1

A un livello elevato la domanda è se l'utilizzo di dati immutabili sia più lento rispetto all'utilizzo di dati mutabili. La risposta a questo è sì, in alcuni casi è più lenta. Ciò che sorprende (per me) è quanto sia piccola la penalità. Nella maggior parte dei casi (nella mia esperienza) il tempo extra, che è spesso un fattore di log, vale la modularità e la chiarezza extra dell'utilizzo di dati immutabili.E in numerosi altri casi non vi è alcuna penalità.

Il motivo principale per cui non è più lento di quanto ci si aspetterebbe è che si possa riutilizzare liberamente qualsiasi parte dei vecchi dati. Non c'è motivo di preoccuparsi che qualche altra parte del calcolo cambierà i dati in seguito: è immutabile!

Per un motivo simile, tutti gli accessi ai dati immutabili sono come riferimenti in C++. Non è necessario fare copie di dati, poiché altre parti del calcolo non possono cambiarle.

Se si desidera lavorare in questo modo, è necessario strutturare i dati per ottenere un riutilizzo. Se non puoi farlo facilmente, potresti voler usare una mutazione (controllata).

Sia OCaml che F # sono lingue a paradigma misto. Ti consentono di utilizzare i dati mutabili se lo desideri.

Il resoconto più illuminante delle operazioni sui dati immutabili (IMHO) è il libro di Chris Okasaki Purely Functional Data Structures. (Questo link Amazon è solo per informazioni, non necessariamente un suggerimento per acquistare il libro :-) Puoi anche trovare gran parte di queste informazioni in Phd thesis di Okasaki.

Answer 2

Ciò significa che le copie lingua la struttura di dati ed esegue la trasformazione richiesta

Non necessariamente. Se gli oggetti sono immutabili (come predefinito per i tipi di record F #, in C++ se tutti i membri di dati sono const senza alcun utilizzo di mutable), quindi l'utilizzo di un riferimento va bene.

In tal caso, l'utilizzo della programmazione funzionale ritarderà notevolmente l'esecuzione dell'algoritmo. È corretto?

Anche con quanto sopra, le lingue funzionali tendono a supportare operazioni pigre. In F #, con le giuste strutture/metodi dati, questo sarà il caso. Ma può anche essere desideroso.

Un esempio (non è terribile idiomatica, ma cercando di essere chiari):

let Square (is : seq<'t>) = is |> Seq.map(fun n -> n*n) 

e poi in

let res = [1; 2; 3; 4] |> Square 

non calcolerà una delle piazze fino a leggere i valori da re.

Answer 3

È possibile implementare uno pointer machine in OCaml e F #. In modo da poter memorizzare riferimenti diretti e aggiornarli. Ad esempio,

type 'a cell = { 
    data : 'a; 
    mutable lhs : 'a cell; 
    mutable rhs : 'a cell; 
} 

In OCaml questo sarà rappresentato come un puntatore ad una struttura di dati, che contiene tre parole: un puntatore ad un dato, e due puntatori a pari livello i nodi:

+--------+   +-------+  +-------+ 
    | cell |-------->| data |----->|  | 
    +--------+   |-------|  +-------+ 
        +---| lhs | 
        | |-------| 
        | | rhs |--+ 
        | +-------+ | 
        | +-------+ | +-------+ 
        +-->| data | --->| data | 
         |-------|  |-------| 
         | lhs |  | lhs | 
         |-------|  |-------| 
         | rhs |  | rhs | 
         +-------+  +-------+ 

Quindi, ci non è niente di speciale qui. È lo stesso, in quanto è possibile scegliere tra un'implementazione persistente e imperativa in C++. Ma in C++ di solito si paga un costo più significativo per la persistenza, a causa della mancanza di un supporto di una lingua stessa. In OCaml c'è un garbage collector generativo, con costi di allocazione molto economici e altre ottimizzazioni.

Quindi, sì, è possibile implementare la struttura dati in modo regolare (imperativo). Ma prima di fare questo, devi essere abbastanza sicuro, che sei pronto a pagare per questo. È molto più facile ragionare sul codice funzionale, piuttosto che imperativo. Questo è il motivo principale per cui le persone scelgono e usano il paradigma FP.

Answer 4

È importante comprenderlo in termini di due fattori: mutazione e condivisione. Sei (sembra essere) concentrato sull'aspetto della mutazione e sembra che trascuri la condivisione.

Prendere la lista standard-append '@'; copia l'argomento di sinistra e condivide il diritto

Quindi, sì è vero che si perde efficienza copiando ma si guadagna corrispondentemente condividendo. Quindi, se organizzi le tue strutture dati per massimizzare la condivisione di , puoi guadagnare da ciò che hai perso con l'immutabilità causata dalla copia.

Per la maggior parte questo "succede". Tuttavia a volte è necessario modificarlo.

esempio comune pigrizia coinvolgendo in haskell:

ones = 1 : ones 

ciò denota un elenco infinito di 1s [1,1,1,...] E l'attuazione può essere previsto ottimizzarlo per un loop (circolare grafico)

 +-----------+ 
    |   | 
    V   | 
+---------+  | 
|   |  | 
| 1 |-->---+ 
|   | 
+---------+ 

Tuttavia quando lo generalizziamo in un elenco infinito di x-es

repeat x = x : repeat x 

l'attuazione ha un tempo più difficile rilevare il ciclo perché la variabile ones ora è diventato un (ricorsiva) chiamata di funzione repeat x

Change a

repeat x = let repeat_x = x : repeat_x in repeat_x 

e il ciclo (cioè condivisione) è reintegrato.