Gestione della memoria Java (thunk / pigrizia)

L'idea alla base di tutti gli elenchi semplici è la seguente:

1. Assicurati di sapere se hai una lista vuota o meno.
2. Se non è la lista vuota, hai 2 parti:
   • il capo della lista
   • e la coda (resto dell'elenco)

Poiché Java supporta le chiusure (beh, tipo di), è possibile implementare le liste pigre con il seguente trucco: invece di avere un riferimento direttamente alla coda, avere un riferimento a un oggetto che è in grado di calcolare la coda. Tale oggetto potrebbe essere un Callable<ZList> , ad esempio, se ZList è il nostro tipo di lista. E sì, una tale chiusura costruita con

 // assuming constructor ZList(int, Callable<ZList>);
 public Callable<ZList> nextNode(final int current) {
   return new Callable<ZList> {
     ZList call() {
          return new ZList(current, nextNode(current+1));
     }
   };
 }

occupa una quantità limitata di memoria. Sicuramente più di un nodo della lista dei singoli, ma inferiore a molti nodi della lista.

Per quanto riguarda i requisiti di memoria: è possibile passare attraverso un elenco così infinito e avere comunque un utilizzo costante della memoria finché l'inizio dell'elenco non viene memorizzato da nessuna parte. Perché, in quel caso, il nodo principale con cui hai finito può e sarà raccolto.

Se, tuttavia, hai il capo della lista infinita da qualche parte (in una variabile statica, per esempio) l'utilizzo della memoria aumenterà mentre attraversi la lista.

Poiché queste cose sono difficili da scrivere in Java, ci sono nuovi linguaggi JVM come Scala (functional / OO), Clojure (List) o Frege (come Haskell) che rendono facile avere tali cose nella JVM.

Frege potrebbe essere interessante per te perché a) non è severo (cioè pigro) eb) sputa java codice sorgente, quindi è possibile studiare e riprodurre le sorgenti java create da semplici programmi funzionali.

Questa è la classica inizializzazione pigra, poiché negli oggetti che non vengono mai referenziati non vengono mai creati; solo quando vengono referenziati per la prima volta avviene l'inizializzazione.

Per fare una lista infinita in java puoi fare quanto segue:

public class InfList extends AbstractList<Integer> implements RandomAccess{

    public Integer get(int i){
        return i;
    }

    public int size(){
        return Integer.MAX_value;
    }

}

o per utilizzare un elenco basato su predicati più tradizionale:

public class FibList extends AbstractSequentialList<BigInteger> {

    public ListIterator<BigInteger> listIterator(int i){
         ListIterator<BigInteger> res = new FibIterator(0,1);
         for(;i>0;i++)res.next();
         return res; 
    }

    private FibIterator implements ListIterator<BigInteger>{
        BigInteger prev,curr;int ind=0;

        FibIterator(int pr,int c){
            prev=BigInteger.valueOf(pr);
            curr=BigInteger.valueOf(c);
        }

        public boolean hasNext(){return true;}
        public boolean hasPrevious(){return true;}
        public void remove(){throw new UnsupportedOperationException();}
        public void set(BigInterger I){throw new UnsupportedOperationException();}
        public void add(BigInterger I){throw new UnsupportedOperationException();}
        public BigInteger next(){
            BigInteger tmp = curr; 
            curr=curr.add(prev); 
            prev=tmp;
            ind++;
            return tmp;
        }
        public BigInteger previous(){
            BigInteger tmp = prev; 
            prev=curr.subtract(prev); 
            curr=tmp;
            ind--;
            return tmp;
        }
        public int nextIndex(){return ind;}
        public int previousIndex(){return ind-;}
    }
}

(sì, la lista basata sull'iterazione è un dolore)

Per ottenere un elenco infinito di elementi, hai bisogno di due cose:

1. La possibilità di ottenere il primo elemento
2. La possibilità di ottenere un elenco contenente il resto degli articoli.

Ci sono nomi diversi per questo modello come first / rest, head / tail.

Penso che tu stia cercando qualcosa in più sulla falsariga di quanto segue. Non implementa le interfacce di java's List, ma sarebbe possibile.

import java.math.BigInteger;

public class InfiniteList {

    private BigInteger _current;

    public InfiniteList(BigInteger start){
        _current = start;
    }

    public BigInteger first(){
        return _current;
    }

    public InfiniteList rest(){
        return new InfiniteList(_current.add(BigInteger.ONE));
    }
}

Ha un modo per ottenere il primo elemento, ma poi ha anche un modo per ottenere una lista contenente il resto. L'elenco assegna solo una quantità di memoria sufficiente per un elemento e quindi ti consente di ottenere un nuovo elenco, contenente il resto degli elementi, ma ovviamente l'elenco successivo assegna solo un elemento, ma ti offre un modo per ottenere il resto.

Se chiami rest 99 volte e poi chiami per primo, avrà assegnato solo 100 elementi in totale. Se non tieni alcuno degli elementi quando stai attraversando l'elenco, quelli all'inizio possono ottenere la raccolta dei dati inutili.

Il classico esempio della sequenza infinita è quello di una sequenza lenta da una programmazione funzionale.

Da Wikibooks Programmazione Clojure: Lazy Fibonacci ci sono un certo numero di sequenze pigre per il calcolo della sequenza di Fibonacci . Un esempio:

(def fib-seq 
  ((fn rfib [a b] 
     (lazy-seq (cons a (rfib b (+ a b)))))
   0 1))
user> (take 20 fib-seq)
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

In questo, la sequenza non viene valutata finché non ne viene richiesta una e può continuare a essere interrogata per ottenere il valore successivo nella sequenza.

Si noti che questa è una sequenza e non una matrice.

L'idea di una struttura che nasconde il calcolo dietro di essa non è certamente unica per i linguaggi funzionali puri.

In perl un esempio di un array in cui si chiede $primes[199] restituendo il 200esimo primo può essere trovato in Math::Prime::TiedArray . Allo stesso modo, in Python, questa domanda di overflow dello stack crea un iterator / generator (non sono un pitone, non sono esattamente sicuro della termonologia) che genererà un flusso infinito di numeri primi.

Si noti che con i numeri primi si assegna ancora memoria in quanto genera i numeri per rendere il setaccio più ottimale. Se richiedi più oggetti di quanti possano essere contenuti nella memoria, riempirai la memoria. Tuttavia, non calcola il valore finché non lo chiedi.

Specificamente per Java, si potrebbe fare ciò che si desidera in clojure e quindi chiamare il codice clojure da Java - sono entrambe lingue jvm. È un'opzione, anche se non la consiglio.

Per Java, iteratore è un'interfaccia per qualcosa che si muove in una direzione. Il punto chiave è che questa è un'interfaccia - puoi implementarla.

Si consideri:

package com.michaelt.se;

import java.util.Iterator;

public class EvenIter implements Iterator<Integer>
{
    private int value = 0;

    @Override
    public boolean hasNext() {
        return true;
    }

    @Override
    public Integer next() {
        return (value++ * 2);
    }

    @Override
    public void remove() { }
}

e la demo per eseguirlo

package com.michaelt.se;

public class IterDemo
{
    public static void main(String[] args)
    {
        EvenIter evens = new EvenIter();
        for(int i = 0; i < 10; i++) {
            System.out.println(i + ": " + evens.next());
        }
    }
}

Questa è una "lista" infinita di numeri che richiede una piccola quantità costante di memoria. L'ho fatto con l'iterabile, potrebbe essere fatto anche con altre interfacce. Le diapositive della presentazione su flussi infiniti fanno da stream.

Il thunk in particolare è una chiusura da richiamare in seguito quando necessario. Le chiusure sono qualcosa che si trova in Java 7.

Ancora, uno può fare cose simili in Java come codice creando un oggetto con un getter che ha un metodo associato che è quindi memoized . L'idea è "sì, calcolerò questo valore quando effettivamente lo vuoi, ma fino a quel momento, resisti a questo."

La domanda della lista infinita di numeri interi interi (che si tratti di numeri naturali, numeri primi, Fibonacci o qualche altra sequenza) può essere implementata pigra in vari modi in Java. Si riduce davvero a ciò che si vuole fare al di là del "dovrebbe essere pigro e non mangiare tutta la memoria come ottengo grandi numeri".

Indipendentemente da come si taglia la torta, un intero occupa spazio nella memoria (a 32 bit in Java per l'esattezza) e un numero infinito di essi occuperà una quantità infinita di spazio. Ciò causerà l'esaurimento della memoria ( 1 ). Qualsiasi soluzione che pretenda di creare una lista infinita in realtà non sta creando una lista, solo un'illusione. Ad esempio, il tuo ciclo renderebbe System.out.println(list.get(10000); stampato 10000. Potrei facilmente ideare un oggetto semplice con un metodo chiamato get(int x) che restituisce solo x . Ciò creerebbe l'illusione di una lista infinita di numeri interi.

Nota a margine ( 1 ): a seconda della quantità di memoria che puoi allocare alla lista, potresti raggiungere la dimensione massima massima di ~ 2 miliardi prima di esaurire la memoria. Ciò richiederebbe qualcosa nel campo di gioco di 15 GB di memoria per raggiungere questo limite.