Hi, Im trying to implement a random queue class that polls() a random element in constant time.
The logic behind this is to implement the queue with an ArrayList. When poll is called, a random number is picked (next) and the ArrayList is split and recombined so that next is at the front of the ArrayList, then remove the first element. This is to avoid the cost of removing a random element in an arraylist.
The system.arraycopy() generates a java.lang.ArrayStoreException when it is run though.
Why is this? How should I fix it? Is there a better way to remove a random element?
Thomas Dallaire wrote:The system.arraycopy() generates a java.lang.ArrayStoreException when it is run though. Why is this?
API documentation wrote:Throws:
ArrayStoreException - if an element in the src array could not be stored into the dest array because of a type mismatch.
Thomal Dallaire wrote:How should I fix it? Is there a better way to remove a random element?
Your goal is to choose an element from the ArrayList and remove it from that list? Use simpler code which does that:
I hope you don't mind, but I find that variables named "l" are very unreadable, especially in the presence of the digit "1" and the letter "I", so I renamed your list variable to "list". I'm also a little confused by the way you compute "next" immediately after using it, but that wasn't what you asked about so I will just leave that alone.
The problem is that I'm trying to speed up the removal of a random object in the Array. By just doing remove there's still a large cost for shifting all the elements in the array. I was hoping to use System.arraycopy to quickly get and element to a position where it is easy and inexpensive to remove.
Would dumping the arraylist into something that isnt ordered be a better way?
You solution is O(N). As I see it, since you are extracting a random element from the array the order of the elements in the array does not matter. This admits a very rapid O(1) solution.
Assume an array (or ArrayList) to hold the values and a count of how may values it currently holds (this count is built in to an ArrayList)..
1) Choose a random index.
2) Extract the item at that index.
3) Move the last value in the array (or ArrayList) to the random position index.
4) Reduce the count by 1.
5) Return the value extracted in step 2.
No array or ArrayList copying required for this operation.
Retired horse trader.
Note: double-underline links may be advertisements automatically added by this site and are probably not endorsed by me.
I'd say you should compute the index immediatelly before removal. Your current implementation is somewhat too complicated. Furthermore, what if new items arrive to the queue between two poll() calls, especially after the queue has been emptied by the last poll() call?