2
\$\begingroup\$

So I have this simple code in Java. It enqueue (adds) and element to the end of the queue (implemented by an ArrayList) without changing the original queue.

public class MyQueue<T>{
    private List<T> body;

    // some constructors and helper functions.

    //copy constructor
    public MyQueue(List<T> list){
        this.body = list;
    }

    //this is the function
    public MyQueue<T> enqueue(T obj){
        List<T> temp = new ArrayList<T>(body);
        temp.add(obj);
        return new Queue<T>(temp);
    }

The whole idea is to make enqueue faster and more efficient, and again, as you notice, without changing the value of the original queue. Any ideas?

UPDATE For the sake of completing the idea.

1- This is an assignment so university, the skeleton provided is not to be changed, the task is to make the function enqueue faster (i do realize i am copying twice and thats the slow part).

2- As for the helper functions, they are simple:

public T peek(){
if(body.isEmpty()){
   thrown new NoSuchElementException();
}
return body.get(0);
}

public int size(){
return body.size();
}
\$\endgroup\$
  • 4
    \$\begingroup\$ What is the sense of doing so? \$\endgroup\$ – Alexei Kaigorodov Nov 16 '13 at 17:28
  • \$\begingroup\$ public Queue(List<T> list){ is not a constructor at all. It's more a compiler error. I guess it should be public MyQueue(List<T> list){ \$\endgroup\$ – Simon Forsberg Nov 16 '13 at 19:00
  • \$\begingroup\$ It's rather hard to "answer" this question without knowing how you are using your MyQueue class, or what the hidden constructors and helper methods are. \$\endgroup\$ – Simon Forsberg Nov 16 '13 at 19:05
  • \$\begingroup\$ I am confused, it's not to be changed but you want to make it faster? \$\endgroup\$ – Malachi Nov 22 '13 at 4:19
2
\$\begingroup\$

It seems like what you are trying to accomplish here is to make your Queue class immutable. That in itself is good, but there are a couple of issues with your approach:

  • Creating a new class for this is not needed. There already exists classes for that. Use Collections.unmodifiableList to create one.
  • Your class does not implement the List interface (or the Queue interface for that matter). I guess there is a way to access the embedded List<T> such as getList hidden among "some constructors and helper functions", but if all that does is to return this.body; then your entire list is still accessible and modifiable.
  • The List<T> body field could be, and should be, declared final.

Instead of your entire Queue class, you might want to use this static method:

public static <E> List<E> addToList(List<E> oldList, E newElement) {
    List<E> temp = new ArrayList<E>(oldList);
    temp.add(newElement);
    return Collections.unmodifiableList(temp);
}

I should add however, that there is a difference between an unmodifiable list and what I understood about your approach. An unmodifiable list in Java does not allow any change to the list at all, such as list.set(index, obj).

\$\endgroup\$
  • \$\begingroup\$ I think your code example was meant to have List<E> temp = new ArrayList<E>(oldList);? \$\endgroup\$ – Corbin Nov 16 '13 at 19:11
2
\$\begingroup\$

I doubt with this implementation. Queue is a very basic data structure -- by "enqueue" I would assume that the element is going be added to the original queue. Now as you mentioned you wanted to make this faster, but to achieve that you are copying the original queue. So both time and space will suffer due to a temp array created every time when enqueue is called. Did you execute a performance test on your implementation to see how actually this could be beneficial?

\$\endgroup\$
2
\$\begingroup\$

The problem with your enqueue approach is that it copies the existing content into a new list. Assuming you enqueue n elements this would result in 1 + 2 + 3 + 4 + .. + n copy operations - which is (if you know your ole Gauss) n * (n + 1) / 2 or in other words O(n^2). This is not very efficient.

Getting immutable data structures right and efficient is not always a trivial task. The best advise I can give is to point you to Eric Lipperts blog who has written a whole series about immutable data structures - I found that an extremely interesting read (queues are discussed starting part 4). He uses C# (no surprise there) but I'm sure the ideas can be applied to Java just as well.

\$\endgroup\$
1
\$\begingroup\$

Basically you are trying to improve a basic and common data structure that is Queue. You have two choices available to implement queue - using linked list and other one is using array (here you have used similar by java's ArrayList).

A very brief compassion of two different type of implementation -

Using linked list

  • enqueue has constant time 0(1) and dequeue has 0(n) complexity in worst case

  • Uses extra time and space to deal with the links

Using Array

  • enqueue operation takes constant time 0(1) in amortized array.(amortized array is - resizing array as per need for efficiently using space)

  • Less wasted space.

First off, you are trying to improve an operation which already has a good performance whether it is array or linked list.

If you had used array, then you had to maintain resize array functionality yourself to achieve amortized time. But since you are using Arralist so you do not have to write extra code to resize array because ArraList inherently provides this functionality.

I suggest that you implement another Queue class using basic array instead of ArrayList. Now start profiling both the implementation and see how they differ in terms of execution time.

While testing, create "very large" queue and perform different operation on it. I feel using a basic array on a large queue may have some advantage over ArrayList. I can not claim this statement but profiling two different implementation will give better conclusion.

\$\endgroup\$
  • \$\begingroup\$ "Every operation takes constant time 0(1) in worst case" - Really? Since when is lookup by index a constant time operation on a linked list? Also less wasted space is not quite correct: typically array based structures resize the backing array by doubling the capacity when it's full. So your wasted space is (n/2) - 1 bytes in worst case (which can be a lot). \$\endgroup\$ – ChrisWue Nov 17 '13 at 7:01
  • \$\begingroup\$ I think the trick here is to somehow work around the need for 2 stages of copying. since the original should never be changed. and the type returned should be MyQueue. But I cannot seem to work around that. \$\endgroup\$ – MandM Nov 17 '13 at 7:14
  • \$\begingroup\$ @ChrisWue - you are right, let me edit my answer \$\endgroup\$ – Kinjal Nov 17 '13 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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