Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have been developing an Immutable queue in java, but the version I have developed is supposedly slow and I have been suggested to create a faster version of the same and I have no idea as to how to accomplish that.

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();
}
}

Please suggest any improvements in the implementation or the libraries used .

We remove elements from immutable lists all the time and dequeue is just a special case of that. The point is that the result is not really the element, but another immutable list without it. The point of this design is mutation safety and way better in parallelized settings than mutable data structures.

share|improve this question
    
I think the best way to start is to use a profiler and check where the class is slow. –  Uwe Plonus Jan 16 '13 at 8:13
1  
I need to learn something: What is the point of an immutable queue? –  mouviciel Jan 16 '13 at 8:39
1  
immutable queue is an oxumoron. dequeue is supposed to mutate queue internals; cloning array at it looks just... perverse - unless of course you did this in order to (most likely incorrectly) solve some underlying problem which you told us nothing about –  gnat Jan 16 '13 at 9:46
2  
Not that much of an oxymoron really. We remove elements from immutable lists all the time and dequeue is just a special case of that. The point is that the result is not really the element, but another immutable list without it. @mouviciel: mutation safety and way better in parallelized settings than mutable datastructures –  Frank Jan 16 '13 at 10:28
    
@Frank - I can understand immutable lists, dictionaries, strings or whatever sets. But the purpose of a queue is to send messages from a task/thread/process to another one running in parallel. If the queue is not really the same after enqueing or dequeing, you just move the mutation safety problem from the queue to its references in both tasks. –  mouviciel Jan 16 '13 at 10:56

2 Answers 2

You should read up on structure sharing for immutable datatypes. Obviously, when your enqueue involves creating a complete clone of that list, then your enqueue is O(n). The whole idea of structure sharing is that you return a new object, that in some way reuses the original object such as to avoid this duplication.

For your queue implementation in particular, you cannot simply rely on a mutable Java ArrayList. Take a look at some functional language and cons-cells for constructing immutable list datastructures. They allow you to simply keep track of start and end elements of your queue and derive a new queue object by reusing all cons-cells and simply adding a new one. The new object reuses the original cons-cells, but has a different end-pointer to the newly added cons cell.

Long story short: When writing immutable datastructures avoid copies and share structures instead.

In response to the comment about Java: All of this is language-agnostic. It is just that functional languages have been working with immutable datastructures for decades, whereas it is a relatively recent trend to add immutability to OO languages. All of this structure sharing, cons-cells, etc. is implementable in any programming language (well, Turing-complete that is).

share|improve this answer
2  
Usually you take two immutable (linked) Lists and glue them together. –  Landei Jan 16 '13 at 9:02
3  
read Okasaki's 'Purely Functional Data Structures' for more examples, all of which can be ported to Java books.google.co.uk/books/about/… –  Pete Kirkham Jan 16 '13 at 13:43
    
That strategy is going to least to a leak. I guess you'd need to rebuild the list once in a while (some kind of linearish function of waste to list size to keep O(1) time, I guess). (+1 for Okasaki's book.) –  Tom Hawtin - tackline Jan 16 '13 at 19:36

This is an untested sketch of the usual functional implementation. First you need immutable Lists:

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();
            }
        };
    }
}

Then you take two lists. The front one is for enqueueing items, the back one is for dequeueing. If the back one gets empty, the reversed front becomes the new back.

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 you can't get it much faster with immutable data structures.

share|improve this answer
1  
Can you please explain how this implementation supersedes the previous one in performance? –  Anirudh Vemula Jan 16 '13 at 12:38
    
Informally: You have to clone the whole underlying data structure on every single operation, I just do a reverse now and then, reusing what I have with very little changes. For complexity analysis I'd rather like to refer you to cs.cmu.edu/~rwh/theses/okasaki.pdf (chapter 3.1). Generally, if you are seriously interested in immutable data structures, Chris Okasaki's work is a great starting point –  Landei Jan 16 '13 at 19:05
    
@Landei : Rather than using two custom-made Immutablelists you cloud have made only 1 List and not provided setters method for the list. While adding just simply add and while removing simply remove, so then what's the purpose of making ImmutableLists ?? TIA –  The_Lost_Avatar Sep 1 at 19:06
    
@The_Lost_Avatar : Of course you can do that, but then you have a mutable queue. My implementation is immutable, a variable holding a reference to it will never observe any change, all you can do is to get a new, changed immutable queue back. If you are interested in this topic, I highly recommend reading the paper mentioned before ( cs.cmu.edu/~rwh/theses/okasaki.pdf ) –  Landei Sep 2 at 20:22

protected by gnat Sep 15 at 7:45

Thank you for your interest in this question. Because it has attracted low-quality answers, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.