同时从列表中获取随机元素

Question

我试图创建一个并发的数据结构，它允许一个线程轮询随机元素，而另一个线程正在写入它。

public class SomeList<E> extends CopyOnWriteArrayList<E> {
    private final Random random = new Random();

    public E pollRandom() {
        if (size() == 0) {
            throw new NoSuchElementException();
        }
        return remove(random.nextInt(size()));
    }
}

我担心的是：在极端情况下，例如，在线程A调用size（）（在pollRandom（）中）之后，线程B删除最后一个元素。不幸的是，随机索引恰好是最后一个元素（已被删除）的索引。因此，remove（）调用将抛出未捕获的IndexOutOfBoundsException。这是我所不期望的-调用pollRandom（）失败，即使此列表中仍有元素。

所以我想问：我的担心是真的吗？也许我误解了CopyOnWriteArrayList（或任何其他类型的并发列表）实际上是做什么的？如果我的担心是真的，有没有办法解决这个问题？我不想将synchronized添加到所有方法中，因为添加synchronized会使性能更差。

如果有人愿意回答这个问题，我会很高兴的。我的英语很差，如果我的表达听起来模糊或不礼貌，请让我知道，谢谢：）

附言：我知道CopyOnWriteArrayList对于所有突变操作来说都很慢，因为它每次都需要完整的副本，这要归功于@Boris the Spider。它可以是任何类型的并发列表。这里只是一个例子。

Answer 1

COW列表的工作原理如下：

• 它有一个单独的相关字段，即Object[]，包含列表中的元素
• 任何发生变异的调用（因此，clear，add，addAll，remove，等等）都将复制该内部数组，将变异应用于副本，然后将其字段设置为此新数组。考虑到java的工作方式，“旧”数组仍然存在，该字段只是一个指针
• 值得注意的是，任何迭代器（for（Foo f:theCowList）都是在“指针”上进行复制的一种方法，这意味着任何现有迭代器都只是保持在truckin上。他们不会涵盖你添加的任何内容。它们将覆盖您删除的任何内容-从cowList生成的迭代器将遍历所有元素，就像生成迭代器时一样，而不管您之后执行的任何变化。这就是牛仔名单的“要点”。如果您不需要该功能，那么COWList不太可能是适合您的类型

COWList本质上是原子的，对任何一个调用都是安全的。但是，您的操作是三次调用：size（），然后再次调用indexOf和size（）。这里不能保证原子性。你的担心是正确的。

你所做的就是所谓的“检查然后行动”：你检查对象的状态（它是空的吗？），然后你决定如何行动。

在并发领域，这是错误的方法。正确的模式是先行动后检查：你假设天气晴朗，执行你的行动，然后对无效状态做出反应。这也意味着“act”部分需要在本质上进行检查。如果没有这样的内部操作可用，则两个模型都不起作用，这就是问题所在：在这种情况下，您必须找到注入同步的方法，否则在并发操作中不可能安全地执行操作。例如：在普通janeArrayList中，不可能以并发方式添加列表中的元素。

在处理并发性时，第二个重要的认识是，如果您想将并发性检查转移到对象本身，那么与该对象交互的唯一安全方法就是单次调用。你打了3个电话。无益。你只得到一个。

下面是一个可以在这里工作的不同操作的示例：假设您有一个方法从列表中删除第一项，如果列表是空的，则抛出NSElemEx。

你的“风格”是这样写的：

public E pollFirst() {
  // This code is wrong! do not use!
  if (isEmpty()) throw new NoSuchElementException();
  return remove(0);
}

这是错误的-你混淆了两个电话。你只得到一个。这是正确的方法：

public E pollFirst() {
  try {
    return remove(0);
  } catch (ArrayIndexOutOfBoundsException e) {
    throw new NoSuchElementException();
  }
}

请注意，假设天气晴朗，我们是如何首先采取行动的：我们只是删除了第0个元素，而不知道在第一个位置是否有这样的元素。如果失败，我们将对失败作出反应（如果在空COWList上调用remove（0），则会出现ArrayIndexOutOfBoundsException，我们将在此处对此作出反应）。

不幸的答案是，不可能——COWList没有一个调用可以做你想要的，因此，你已经死在水里了。COWListpromise某些并发安全性；为此，它有一个私有的包（所以你看不到它！）字段称为lock。操作，如删除（int index）获取这个锁，因此将导致任何线程，例如也调用删除冻结，直到第一个线程完成。

你不能使用这个锁。这导致了各种各样的问题。我们只是被困在这一点上，我们需要首先回去纠正你犯的一系列风格错误。

您决定扩展COWList。这意味着你说你的对象的任何实例在所有方面都像一个COWList，并在此基础上提供了额外的功能。问题是，COWList和你想要的不一致。特别是，为了符合'you are a COWList with Bolted on临时元素'的想法，您需要复制它的锁定行为：抓取随机元素的操作需要锁定其他线程，因为COWList作为impl根本不提供您需要的API没有锁，但你实际上看不到锁，这意味着你不能这样做。

然而，真正的问题是，你真的不想成为“一个具有额外功能的牛仔列表”。作为一个概念，这很少是一个好主意：COWList已经是一个复杂的野兽，因此任何定义为“带插件的COWList”的东西都更加复杂。忘记COWList，您想要的要简单得多：一个数据结构，您可以在其中并发添加内容并从中获取（并发安全的）随机元素。这就是你想要的。为什么要把牛仔队的规则纳入其中？您在这里使用COWlist是因为它很方便-大部分工作都是为您完成的。这很好，但是，不要“暴露”它。保持实现细节内部化。因此，请这样写：

public class SomeList<E> extends AbstractList<E> {
  private final CopyOnWriteArrayList<E> list = new CopyOnWriteArrayList<E>();
}

在这里，您只需采用List本身的规则，但鉴于您的类型名为SomeList，我假设您有意这样做。AbstractList实施的思想“负载”比COWList实施的要简单得多。现在，您只需实现所有需要的方法，通常作为一行程序，将工作分配给您的COWList。

现在，我们至少离正确操作更近了：您现在可以创建自己的锁对象，或者在文档中定义所有操作在SomeList实例本身上同步（这意味着您只需将synchronized关键字添加到每个方法中-这是将整个方法体包装在synchronized中的缩写（此）{body goes here}。

在一个类中粘贴一个字段并实现多个方法作为一行程序，只调用所述字段上的类似方法称为composition，而不是添加一个extends子句并让它作为要公开的大多数方法的实现，这称为继承。喜欢组合而不是继承。

现在，您可以自己处理同步了，绝对不再需要COWList了。内部列表可以变成一个简单的janeArrayList。效率更高。

“只是在所有事情上同步”是一种逃避<代码>已同步（x）{…} 简单地说，对于任何给定的x，只有一个线程可以在这样的块中。只是“阻塞”线程是简单的解决方法。一个真正酷的数据结构可以在不持有锁的情况下完成部分或全部工作。另外，“从一个大数组中移除项是一个缓慢的操作”（因为后面的所有元素都必须更早地复制到一个时隙中；ARARYLAST基本上是连续的一组元素，因此为什么在中间删除一个是非常昂贵的）。

因此，即使是使用组合而不是继承的“固定”情况也是非常低效的：它使用锁（哎哟），并从数组列表中间删除元素（双哎哟）。

要使并发安全的数据结构仍然快速，需要三件事：

[1]这是一种艺术形式。你需要想出非常有创意的想法。

[2] 这是一种权衡，所以一定要非常具体地说明数据结构可以做什么和不能做什么。为了允许无锁访问，通常会导致数据结构占用更多内存空间。另外，通常看起来很简单的操作，比如“你体内有多少元素”是不可能有效回答的，所以不要提供这种功能。这是java的一个原因。util。concurrent包中有这么多类：没有一个god类可以在内存、CPU和锁方面都有效地完成这一切。

[3] 明确“趋势”和“保证”之间的区别。例如，编写一个快速、高效的系统，可以从大量元素列表中“倾向于”公平地选择一个随机元素（并从中删除），而不是确保每次都完全一致地随机选择一个随机元素，这要容易得多。

艺术的一部分是要知道什么时候你可以适应趋势而不是保证，通常在这样的实现中会有数量级的加速。

以下是一些关于如何制作假设非常快的产品的想法：

如果是这样，一个更快的想法：

有一个对象是“模态的”。它从一个add方法开始（可能还有addAll）。没有别的了。甚至。获取（不要添加您不需要的API，它只会限制您在尝试优化时的灵活性！）。它甚至不保证并发安全行为（同时从两个线程调用add，有时会失败）。“完成”后，调用build（）方法。这将返回一个新对象，该对象只有poll（）方法，该方法以并发安全的方式返回任意元素。

如果这是你的应用编程接口，你可以写得非常高效，完全免费！

构建器只是一个非常简单的类，它包含一个普通的jane数组列表并填充它：

class RandomPollerBuilder<E> {
  private final ArrayList<E> data = new ArrayList<E>();
  private boolean open = true;

  public void add(E elem) {
    if (!open) throw new IllegalStateException();
    data.add(elem);
  }

  public RandomPoller<E> build() {
    open = false;
    data.trimToSize();
    Collection.shuffle(data);
    return new RandomPoller<E>(data);
  }
}

然后随机轮询器看起来像：

public class RandomPoller<E> {
  private final AtomicInteger pos;
  private final List<E> input;

  RandomPoller<E>(List<E> input) {
    this.input = input;
    this.pos = new AtomicInteger(input.size());
  }

  public E poll() {
    int idx = pos.decrementAndGet();
    if (idx >= 0) return input.get(idx);
    pos.incrementAndGet();
    throw new NoSuchElementException();
  }

  public int size() {
    return Math.max(0, pos.get());
  }
}

在这里，我们结合了大量的属性：

• 我们根本不移除。移除往往很慢，如果我们可以避免，为什么不呢