CODEWITHSUNDEEP
javamultithreadingperformancelistrandom
Perry Monschau
Perry Monschau

Reputation: 901

Java - Most efficient random-access multi-threaded list

Chosen List Structure:

Synchronised LinkedList.

Scenario:

My program requires rendering some (rather computational) generated images in a grid. These images must update whenever some data value changes (on another thread), hence, I have a rendering queue to manage this.

The rendering queue is a synchronised LinkedList, where on a low-priority thread, it is constantly being iterated over to check if some render work needs doing. Since the images are based on all kinds of data, each of which could change independently, I needed some form of queue to combine changes.

Data tends to change in chunks, and so when a large batch comes through I see an imaginary line run down the area where it's re-rendering the tiles. To pretty this up a bit, I decided rather than rendering in standard order, I'd render them in a random order (to give a 'dissolve in/out' effect).

It looks lovely, but the only problem is, there is a notable different in the amount of time it takes to complete with this effect running.

Problem:

I've theorised a couple of reasons accessing this list randomly instead of iteratively would cause such a notable delay. Firstly, the Random number generator's nextInt method might take up a significant enough amount of time. Secondly, since it's a LinkedList, getting the nth item might also be significant when the size of the list is in the 4000s range.

Is there any other reason for this delay that I might have overlooked? Rather than using a random number generator, or even a linked list, how else might I efficiently achieve a random access & remove from a list? If you've read the scenario, perhaps you can think of another way I could go about this entirely?

Requirements:

Upvotes: 0

Views: 175

Answers (2)

jacobm
jacobm

Reputation: 14035

You can use an ArrayList along with a couple of simple operations to implement this very efficiently.

  • To insert, always insert new work at the end of the list (an amortized constant time operation).
  • To extract a random piece of work, pick a random number i, swap the element at i with the element at the end of the list, and then extract and return that new last element.

Here's code (untested, uncompiled):

class RandomizedQueue<T> { 
  private final List<T> workItems = new ArrayList<>();
  private final Random random;

  RandomizedQueue(Random random) {
    this.random = random;
  }

  public synchronized void insert(T item) {
    workItems.add(item);
  }

  public synchronized T extract() {
    if (workItems.isEmpty()) {
      return null;  // or throw an exception
    }

    int pos = random.nextInt(workItems.size());
    int lastPos = workItems.size() - 1;
    T item = workItems.get(pos);
    workItems.set(pos, workItems.get(lastPos));
    return workItems.remove(lastPos);
  }
}

Upvotes: 1

john16384
john16384

Reputation: 8074

You could perhaps use a PriorityQueue, and when adding things to this queue give each item a random priority. The rendering can just always take the top element on the queue since it is randomized already. Inserting at a "random" position in a PriorityQueue (or better put, with a random priority) is really fast.

Upvotes: 0

Related Questions