Java - 最高效的随机访问多线程列表

Question

选择的列表结构:

同步链表。

场景:

我的程序需要在网格中渲染一些(相当计算的)生成的图像。每当某些数据值发生变化(在另一个线程上)时，这些图像就必须更新，因此，我有一个渲染队列来管理它。

渲染队列是一个同步的 LinkedList，在低优先级线程上，它不断地被迭代以检查是否需要执行某些渲染工作。由于图像基于各种数据，每个数据都可以独立更改，因此我需要某种形式的队列来组合更改。

数据往往会成 block 变化，因此当大量数据通过时，我会看到一条假想线沿着重新渲染图 block 的区域延伸。为了美化一点，我决定不以标准顺序渲染，而是以随机顺序渲染它们(以产生“溶解入/出”效果)。

它看起来很可爱，但唯一的问题是，运行此效果所需的时间存在显着差异。

问题:

我推测随机访问此列表而不是迭代访问此列表会导致如此明显的延迟的几个原因。首先，随机数生成器的 nextInt 方法可能会占用足够多的时间。其次，由于它是一个 LinkedList，当列表的大小在 4000 秒范围内时，获取第 n 项也可能很重要。

是否还有其他我可能忽略的延迟原因？除了使用随机数生成器，甚至链表之外，我还能如何有效地实现随机访问并从列表中删除？如果您已经阅读了该场景，也许您可​​以想出另一种方式来完全解决这个问题？

要求:

• 多线程添加和修改列表。
• 随机访问和删除列表中的项目。
• 高效运行，数据集大且运行次数多

Answer 1

您可以使用ArrayList以及一些简单的操作来非常有效地实现这一点。

• 要插入，请始终在列表末尾插入新工作(摊销常量时间操作)。
• 要提取随机作品，请选择一个随机数 i，将 i 处的元素与列表末尾的元素交换，然后提取并返回新的最后一个元素。

这里的代码(未经测试，未编译):

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