Come aumentare l'efficienza di una coda immutabile in java?

Question

Come aumentare l'efficienza di una coda immutabile in java?

#1 da (10 voti)
#2 da (5 voti)

3

Ho sviluppato una coda Immutable in java, ma la versione che ho sviluppato è presumibilmente lenta e mi è stato suggerito di creare una versione più veloce della stessa e non ho idea di come ottenerlo.

import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;
public class ImmutableQueueImpl<E> implements ImmutableQueue<E>
{

    private List<E> queue;
    public ImmutableQueueImpl()
    {
       queue=new ArrayList<E>();
    }

    public ImmutableQueueImpl(List<E> queue)
    {
       this.queue=queue;
    }

    public ImmutableQueue<E> enqueue(E e)
    {
            if(e==null) throw new IllegalArgumentException();
            List<E> clone = new ArrayList<E>(queue);
            clone.add(e);
            return new ImmutableQueueImpl<E>(clone);
    }

    public ImmutableQueue<E> dequeue()
    {
            if(queue.isEmpty())
            {
              throw new NoSuchElementException();
            }
            List<E> clone = new ArrayList<E>(queue);
            clone.remove(0);
            return new ImmutableQueueImpl<E>(clone);
    }

    public E peek()
    {
            if(queue.isEmpty()) throw new NoSuchElementException();
            return queue.get(0);
    }


public int size()
{
    return queue.size();
}
}

Suggerisci eventuali miglioramenti all'implementazione o alle librerie utilizzate.

_{Rimuoviamo elementi da elenchi immutabili tutto il tempo e dequeue è solo un caso speciale di questo. Il punto è che il risultato non è realmente l'elemento, ma un altro elenco immutabile senza di esso. Il punto di questo disegno è la sicurezza delle mutazioni e il modo migliore nelle impostazioni in parallelo rispetto alle strutture di dati mutevoli.}

immutability java data-structures queue

posta Anirudh Vemula 16.01.2013 - 09:09

fonte

2 risposte

Leggi altre domande sui tag immutability java data-structures queue

Come vengono chiamate le funzioni quando si passa ++ Cos'è l'automazione dello sviluppo?

score 10 · Answer 1

Dovresti leggere su condivisione della struttura per i tipi di dati immutabili. Ovviamente, quando enqueue comporta la creazione di un clone completo di quell'elenco, il tuo accodamento è O(n) . L'intera idea della condivisione delle strutture è che tu restituisca un nuovo oggetto, che in qualche modo riutilizzi l'oggetto originale, per evitare questa duplicazione.

In particolare, per l'implementazione della tua coda, non puoi semplicemente fare affidamento su una% diArrayList Java mutabile. Dai un'occhiata ad alcuni linguaggi funzionali e alle cons-cell per la costruzione di datastrutture di elenchi immutabili. Ti permettono semplicemente di tenere traccia degli elementi di inizio e fine della tua coda e ricavare un nuovo oggetto di coda riutilizzando tutte le celle di controllo e aggiungendone semplicemente uno nuovo. Il nuovo oggetto riutilizza le celle originali originali, ma ha un puntatore finale diverso rispetto alla cella di controllo appena aggiunta.

Per farla breve: quando si scrivono strutture immutabili, si evitano copie e strutture di condivisione.

In risposta al commento su Java: tutto ciò è indipendente dalla lingua. È solo che i linguaggi funzionali hanno lavorato con datastrutture immutabili per decenni, mentre è una tendenza relativamente recente ad aggiungere immutabilità ai linguaggi OO. Tutta questa condivisione della struttura, le cellule consolari, ecc. È implementabile in qualsiasi linguaggio di programmazione (beh, Turing-completo che è).

score 5 · Answer 2

Questo è uno schizzo non testato della solita implementazione funzionale. Innanzitutto hai bisogno di elenchi immutabili:

import java.util.Iterator;
import java.util.NoSuchElementException;

public class ImmutableList<T> implements Iterable<T> {
    @SuppressWarnings("unchecked")
    private final static ImmutableList NIL = new ImmutableList(null, null);

    public final T head;
    public final ImmutableList<T> tail;


    public ImmutableList(T head, ImmutableList<T> tail) {
        this.head = head;
        this.tail = tail;
    }

    public ImmutableList<T> add(T t) {
        return new ImmutableList<T>(t, this);
    }

    public boolean isEmpty() {
        return this == NIL;
    }

    public ImmutableList<T> reverse() {
        ImmutableList<T> result = nil();
        for (T t : this) {
            result = result.add(t);
        }
        return result;
    }

    @SuppressWarnings("unchecked")
    public static <T> ImmutableList<T> nil() {
        return NIL;
    }

    @Override
    public Iterator<T> iterator() {
        return new Iterator<T>() {
            private ImmutableList<T> list = ImmutableList.this;

            @Override
            public boolean hasNext() {
                return !list.isEmpty();
            }

            @Override
            public T next() {
                if (!hasNext()) throw new NoSuchElementException();
                T t = list.head;
                list = list.tail;
                return t;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException();
            }
        };
    }
}

Quindi prendi due liste. Quello anteriore è per l'accodamento degli oggetti, quello anteriore per la rimozione. Se il retro diventa vuoto, il fronte invertito diventa il nuovo dietro.

import java.util.NoSuchElementException;

public class ImmutableQueue<T> {

    private final ImmutableList<T> front;
    private final ImmutableList<T> back;


    private ImmutableQueue(ImmutableList<T> front, ImmutableList<T> back) {
        this.front = front;
        this.back = back;
    }

    public static <T> ImmutableQueue<T> empty() {
        return new ImmutableQueue<T>(ImmutableList.<T>nil(), ImmutableList.<T>nil());
    }

    public boolean isEmpty() {
        return front.isEmpty() && back.isEmpty();
    }

    public ImmutableQueue<T> enqueue(T t) {
        return new ImmutableQueue<T>(front.add(t), back);
    }

    public DequeueResult<T> dequeue(T t) {
        if (isEmpty()) throw new NoSuchElementException();
        if (back.isEmpty()) {
            ImmutableList<T> tnorf = front.reverse();
            return new DequeueResult<T>(tnorf.head, new ImmutableQueue<T>(ImmutableList.<T>nil(), tnorf.tail));
        } else {
           return new DequeueResult<T>(back.head, new ImmutableQueue<T>(front, back.tail));
        }
    }

    //Sorry, no tuples in Java land...
    public static class DequeueResult<T> {
        public final T t;
        public final ImmutableQueue<T> queue;

        public DequeueResult(T t, ImmutableQueue<T> queue) {
            this.t = t;
            this.queue = queue;
        }
    }
}

AFAIK non puoi ottenerlo molto più velocemente con strutture di dati immutabili.