Win a copy of Java Challengers this week in the Java in General forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • paul wheaton
  • Devaka Cooray
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Liutauras Vilda
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Carey Brown
  • Piet Souris
Bartenders:
  • salvin francis
  • Mikalai Zaikin
  • Himai Minh

Random Queue

 
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?

Thanks for any help!
 
Marshal
Posts: 26530
81
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Thomas Dallaire wrote:The system.arraycopy() generates a java.lang.ArrayStoreException when it is run though. Why is this?


Because...

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.
 
Thomas Dallaire
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks, for the reply Paul.

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?
 
Paul Clapham
Marshal
Posts: 26530
81
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Thomas Dallaire wrote:By just doing remove there's still a large cost for shifting all the elements in the array.


Of course there is. But that's exactly what you were doing. Did you think that your code would be faster than the code inside ArrayList which does the same thing? If so, why?
 
Ranch Hand
Posts: 781
Netbeans IDE Ubuntu Java
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Thomas Dallaire
Greenhorn
Posts: 7
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Like so?



it seems to work...thanks a lot!
 
Sheriff
Posts: 3837
66
Netbeans IDE Oracle Firefox Browser
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thomas,
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?
 
James Sabre
Ranch Hand
Posts: 781
Netbeans IDE Ubuntu Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Martin Vajsar wrote:Thomas,
I'd say you should compute the index immediatelly before removal.



++
 
You showed up just in time for the waffles! And this tiny ad:
Building a Better World in your Backyard by Paul Wheaton and Shawn Klassen-Koop
https://coderanch.com/wiki/718759/books/Building-World-Backyard-Paul-Wheaton
reply
    Bookmark Topic Watch Topic
  • New Topic