在另一个线程改变它时从列表中获取随机元素
Getting random elements from a list while another thread is mutating it
我正在尝试创建一个并发数据结构，它允许一个线程在另一个线程写入时从中轮询随机元素。
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 会使性能更差。
如果有人愿意回答这个问题，我会很高兴。我的英语很差，如果我的表达听起来含糊或不礼貌，请告诉我，谢谢:)
PS：我知道 CopyOnWriteArrayList 对于所有可变操作都很慢，因为它每次都需要完整的副本，这要归功于@Boris the Spider。它可以是任何类型的并发列表。这里只是一个例子。
COW 列表工作原理如下：
- 它有一个相关字段，即
Object[]，包含列表中的元素。
- 任何变化的调用（因此，
clear、add、addAll、remove 等）将复制该内部数组，将突变应用于副本，然后将其字段设置为这个新数组。考虑到 java 的工作原理，'old' 数组仍然存在，该字段只是一个指针。
- 值得注意的是，任何迭代器（
for (Foo f : theCowList) 是制作迭代器的一种方式）复制 'pointer'，这意味着任何现有的迭代器都将继续运行。他们不会涵盖您添加的任何内容。它们将覆盖您删除的任何内容——从 cowList 生成的迭代器将遍历所有元素，就像您创建迭代器时一样，而不管您之后执行的任何更改。 那是一个 COWList 的 'point'。如果您不需要该功能，那么 COWList 不太可能是适合您的类型。
COWList 本质上是原子的，对于任何单个调用都是安全的。但是，您的操作是三个调用：size()，然后是 indexOf 和 size()。 这里不保证原子性。您的担忧是有道理的.
一般心态更新
你所做的就是所谓的'check-then-act'：你检查对象的状态（它是空的吗？），然后你决定如何行动。
在并发领域，这是错误的做法。正确的模型是先行动后检查：你假设天气晴朗，执行你的行动，然后对无效状态做出反应。这也意味着需要 'act' 部分进行本质上的检查。如果没有这样的内部操作可用，两个模型都不起作用，这就是重点：在这种情况下，您必须找到一种方法来注入同步，或者操作是 impossible 在并发操作中安全地做。示例：“如果元素不在列表中，则添加一个元素”不可能 以并发方式在普通简 ArrayList.
中实现
使用并发时的第二个重要认识是，如果您想将并发检查转移到对象本身，那么与该对象安全交互的唯一方法是 单次 电话。您正在拨打 3 个电话。不好。你只得到一个。
这里有一个 可以 在这里工作的不同操作的例子：假设你有一个方法从你的列表中删除第一个项目，抛出 NSElemEx 如果列表为空。
你的'style'会这样写：
public E pollFirst() {
// This code is wrong! do not use!
if (isEmpty()) throw new NoSuchElementException();
return remove(0);
}
这是错误的 - 您混淆了 2 个调用。你只能得到一个。这是正确的方法：
public E pollFirst() {
try {
return remove(0);
} catch (ArrayIndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
注意我们首先是如何行动的，假设天气晴朗：我们只是删除第 0 个元素，一开始不知道是否有这样的元素。如果失败，我们将对失败做出反应（如果您在空 COWList 上调用 remove(0)，则会出现 ArrayIndexOutOfBoundsException，我们将在此处做出反应）。
那么我们该怎么做呢？
不幸的答案是，不可能 - COWList 没有一个调用可以执行您想要的操作，因此，您已经死在水中了。 COWList 承诺一定的并发安全；为此，它有一个名为 lock 的私有包（因此您看不到它！）字段。 remove(int index) 等操作获取此锁，因此将导致任何线程，例如还调用 remove 冻结，直到第一个线程完成。
您不能使用此锁。这会导致各种各样的问题。我们只是停留在这一点上，我们需要先返回并更正您犯下的一堆样式错误。
组合优于继承
您已决定扩展 COWList。这意味着您是说对象的任何实例在所有方面都像 COWList 一样运行，并在此基础上提供其他功能。问题是，COWList 和你想要的不一致。特别是，为了符合 'you are a COWList with bolted on extras' 的想法，您需要复制其锁定行为：您获取随机元素的操作需要锁定其他线程，因为 COWList 作为 impl 根本不提供 API 你需要在没有锁的情况下完成它，但你实际上看不到锁，这意味着你不能这样做。
不过，真正的问题是您确实不想成为'a COWList with additional functionality'。这作为一个概念很少是一个好主意：COWList 已经是一个复杂的野兽，因此根据定义 'a COWList with addons' 的任何东西都更加复杂。忘掉 COWList，您想要的要简单得多：一种数据结构，您可以向其中并发添加内容并从中获取（并发安全的）随机元素。这就是你想要的。为什么要把COWList的规则带进去呢？您在这里使用 COWlist 是因为它很方便——大部分工作都已为您完成。那很好，但是，不要 'expose' 那样。保持实施细节内部化。因此，这样写：
public class SomeList<E> extends AbstractList<E> {
private final CopyOnWriteArrayList<E> list = new CopyOnWriteArrayList<E>();
}
这里你只是采用了 List 本身的规则，但是鉴于你的类型被命名为 SomeList，我假设你是故意想要的。 AbstractList 强制执行的精神 'load' 比 COWList 强制执行的要简单得多。现在，您只需实现所有需要的方法，通常作为单行代码，将工作外包给您的 COWList。
现在我们至少更接近于做对了：您现在可以制作自己的锁对象，或者只在文档中定义所有操作都在 SomeList 实例本身上同步（这意味着您只需添加每个方法的 synchronized 关键字 - 即 shorthand 用于将整个方法主体包装在 synchronized (this) { body-goes-here }.
中
在 class 中粘贴一个字段并将许多方法实现为仅在所述字段上调用类似方法的单行代码称为 composition，与添加 extends 子句并让它作为您打算公开的大多数方法的实现，这称为 继承 。更喜欢组合而不是继承。
既然您自己负责同步，就完全不需要 COWList 了。那个内部列表可以变成一个普通的 jane ArrayList。效率更高。
效率
“只是同步所有事情”有点逃避。 synchronized (x) { ... } 只是意味着对于任何给定的 x，只有一个线程可以在这样的块中。只需 'blocking' 个线程是最简单的出路。一个非常酷的数据结构可以在不持有锁的情况下完成部分或全部工作。另外，'remove item from the middle of a large arraylist' 是一个缓慢的操作（因为必须将后面的所有元素复制到更早的一个槽中；arraylist 从根本上作为一组连续的元素工作，因此为什么在中间删除一个元素如此昂贵）。
因此，即使 'fixed' 使用组合而不是继承的情况也非常低效：它使用锁（哎哟），并从数组列表的中间删除元素（双重哎哟）。
制作仍然快速的并发安全数据结构需要三件事：
[1] 这真是一种艺术形式。你需要想出非常有创意的点子。
[2] 这是权衡取舍，所以一定要 非常具体 你的数据结构能做什么，不能做什么。为了允许无锁访问，您通常会得到在内存中占用（方式）更多 space 的数据结构。此外，通常看似简单的操作（例如 'how many elements are in you'）不可能有效地回答，因此不要提供该功能。 java.util.concurrent 包中有这么多 classes 是有原因的：没有上帝-class 可以做到这一切并在两个内存中高效地完成，CPU ，并锁定方面。
[3] 搞清楚'trends'和'guarantees'的区别。例如，编写一个快速、高效的系统要容易得多，该系统可以从庞大的元素列表中给你（并删除）一个随机元素，'trends towards' 从一堆元素中公平地挑选，而不是 保证每次都是完全均匀随机选择的。
艺术的一部分是知道什么时候你可以利用趋势而不是保证，通常数量级的加速就在于这样的实现。
这里有一些关于如何制作假设的非常快的想法：
你是否添加所有内容，然后 'switch the mode' 并且不再添加其他元素，而只是从那里移除？
如果是这样的话，一个更快的主意：
有一个对象是'modal'。它开始时只有一个 add 方法（可能还有 addAll）。没有其他的。甚至 .get（不要添加你不需要的 API，它只会限制你在尝试优化事物时的灵活性！）。它甚至不承诺并发安全行为（同时从 2 个线程调用 add 有时会灾难性地失败）。当'done'时，你调用了一个build()方法。此 returns 一个 new 对象，仅具有 poll() 方法，returns 并发安全方式中的任意元素。
如果那是你的API你可以写非常效率和完全无锁！
您的构建器只是一个非常简单的 class，它包含一个简单的 jane arraylist 并填充它：
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());
}
}
这里我们结合了一大堆属性：
- 我们根本不删除。删除往往很慢，如果我们可以避免它，为什么不呢？
- 我们依赖于 AtomicInteger，它为我们提供了一种方法来保证在并发环境中以比锁快得多的方式进行严格和完整的排序。
- 我们将实施减少到您真正需要的部分。每个方法写起来都很痛苦。我包含了一个
size() 方法来说明这一点： poll 算法的工作方式是它递增 0 到 -1 甚至更糟（如果多个线程同时尝试 poll() 一个空轮询器，那个原子整数可以低于 -1，但最终它会回到 0，所以没有 'rolling over' 我们的原子整数的风险，因为没有系统会拥有 20 亿个线程）。我们需要在 size() 方法中防止这种情况。
- 这也意味着：如果你不是特别需要效率，那就不要理会这些，做一个全局锁定的数据结构。逃避很容易而且有效（只是效率不高）。测试并发是非常困难的（因为事情只是 可能 在正确的情况下出错，他们不能保证。在测试中你想要破坏代码实际上失败，这就是问题所在。这几乎是不可能的！） - 所以不要去那里，除非你完全知道你在做什么并且你确定你需要它。
我正在尝试创建一个并发数据结构，它允许一个线程在另一个线程写入时从中轮询随机元素。
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 会使性能更差。
如果有人愿意回答这个问题，我会很高兴。我的英语很差，如果我的表达听起来含糊或不礼貌，请告诉我，谢谢:)
PS：我知道 CopyOnWriteArrayList 对于所有可变操作都很慢，因为它每次都需要完整的副本，这要归功于@Boris the Spider。它可以是任何类型的并发列表。这里只是一个例子。
COW 列表工作原理如下：
- 它有一个相关字段，即
Object[]，包含列表中的元素。 - 任何变化的调用（因此，
clear、add、addAll、remove等）将复制该内部数组，将突变应用于副本，然后将其字段设置为这个新数组。考虑到 java 的工作原理，'old' 数组仍然存在，该字段只是一个指针。 - 值得注意的是，任何迭代器（
for (Foo f : theCowList)是制作迭代器的一种方式）复制 'pointer'，这意味着任何现有的迭代器都将继续运行。他们不会涵盖您添加的任何内容。它们将覆盖您删除的任何内容——从 cowList 生成的迭代器将遍历所有元素，就像您创建迭代器时一样，而不管您之后执行的任何更改。 那是一个 COWList 的 'point'。如果您不需要该功能，那么 COWList 不太可能是适合您的类型。
COWList 本质上是原子的，对于任何单个调用都是安全的。但是，您的操作是三个调用：size()，然后是 indexOf 和 size()。 这里不保证原子性。您的担忧是有道理的.
一般心态更新
你所做的就是所谓的'check-then-act'：你检查对象的状态（它是空的吗？），然后你决定如何行动。
在并发领域，这是错误的做法。正确的模型是先行动后检查：你假设天气晴朗，执行你的行动，然后对无效状态做出反应。这也意味着需要 'act' 部分进行本质上的检查。如果没有这样的内部操作可用，两个模型都不起作用，这就是重点：在这种情况下，您必须找到一种方法来注入同步，或者操作是 impossible 在并发操作中安全地做。示例：“如果元素不在列表中，则添加一个元素”不可能 以并发方式在普通简 ArrayList.
使用并发时的第二个重要认识是，如果您想将并发检查转移到对象本身，那么与该对象安全交互的唯一方法是 单次 电话。您正在拨打 3 个电话。不好。你只得到一个。
这里有一个 可以 在这里工作的不同操作的例子：假设你有一个方法从你的列表中删除第一个项目，抛出 NSElemEx 如果列表为空。
你的'style'会这样写：
public E pollFirst() {
// This code is wrong! do not use!
if (isEmpty()) throw new NoSuchElementException();
return remove(0);
}
这是错误的 - 您混淆了 2 个调用。你只能得到一个。这是正确的方法：
public E pollFirst() {
try {
return remove(0);
} catch (ArrayIndexOutOfBoundsException e) {
throw new NoSuchElementException();
}
}
注意我们首先是如何行动的，假设天气晴朗：我们只是删除第 0 个元素，一开始不知道是否有这样的元素。如果失败，我们将对失败做出反应（如果您在空 COWList 上调用 remove(0)，则会出现 ArrayIndexOutOfBoundsException，我们将在此处做出反应）。
那么我们该怎么做呢？
不幸的答案是，不可能 - COWList 没有一个调用可以执行您想要的操作，因此，您已经死在水中了。 COWList 承诺一定的并发安全；为此，它有一个名为 lock 的私有包（因此您看不到它！）字段。 remove(int index) 等操作获取此锁，因此将导致任何线程，例如还调用 remove 冻结，直到第一个线程完成。
您不能使用此锁。这会导致各种各样的问题。我们只是停留在这一点上，我们需要先返回并更正您犯下的一堆样式错误。
组合优于继承
您已决定扩展 COWList。这意味着您是说对象的任何实例在所有方面都像 COWList 一样运行，并在此基础上提供其他功能。问题是，COWList 和你想要的不一致。特别是，为了符合 'you are a COWList with bolted on extras' 的想法，您需要复制其锁定行为：您获取随机元素的操作需要锁定其他线程，因为 COWList 作为 impl 根本不提供 API 你需要在没有锁的情况下完成它，但你实际上看不到锁，这意味着你不能这样做。
不过，真正的问题是您确实不想成为'a COWList with additional functionality'。这作为一个概念很少是一个好主意：COWList 已经是一个复杂的野兽，因此根据定义 'a COWList with addons' 的任何东西都更加复杂。忘掉 COWList，您想要的要简单得多：一种数据结构，您可以向其中并发添加内容并从中获取（并发安全的）随机元素。这就是你想要的。为什么要把COWList的规则带进去呢？您在这里使用 COWlist 是因为它很方便——大部分工作都已为您完成。那很好，但是，不要 'expose' 那样。保持实施细节内部化。因此，这样写：
public class SomeList<E> extends AbstractList<E> {
private final CopyOnWriteArrayList<E> list = new CopyOnWriteArrayList<E>();
}
这里你只是采用了 List 本身的规则，但是鉴于你的类型被命名为 SomeList，我假设你是故意想要的。 AbstractList 强制执行的精神 'load' 比 COWList 强制执行的要简单得多。现在，您只需实现所有需要的方法，通常作为单行代码，将工作外包给您的 COWList。
现在我们至少更接近于做对了：您现在可以制作自己的锁对象，或者只在文档中定义所有操作都在 SomeList 实例本身上同步（这意味着您只需添加每个方法的 synchronized 关键字 - 即 shorthand 用于将整个方法主体包装在 synchronized (this) { body-goes-here }.
在 class 中粘贴一个字段并将许多方法实现为仅在所述字段上调用类似方法的单行代码称为 composition，与添加 extends 子句并让它作为您打算公开的大多数方法的实现，这称为 继承 。更喜欢组合而不是继承。
既然您自己负责同步，就完全不需要 COWList 了。那个内部列表可以变成一个普通的 jane ArrayList。效率更高。
效率
“只是同步所有事情”有点逃避。 synchronized (x) { ... } 只是意味着对于任何给定的 x，只有一个线程可以在这样的块中。只需 'blocking' 个线程是最简单的出路。一个非常酷的数据结构可以在不持有锁的情况下完成部分或全部工作。另外，'remove item from the middle of a large arraylist' 是一个缓慢的操作（因为必须将后面的所有元素复制到更早的一个槽中；arraylist 从根本上作为一组连续的元素工作，因此为什么在中间删除一个元素如此昂贵）。
因此，即使 'fixed' 使用组合而不是继承的情况也非常低效：它使用锁（哎哟），并从数组列表的中间删除元素（双重哎哟）。
制作仍然快速的并发安全数据结构需要三件事：
[1] 这真是一种艺术形式。你需要想出非常有创意的点子。
[2] 这是权衡取舍，所以一定要 非常具体 你的数据结构能做什么，不能做什么。为了允许无锁访问，您通常会得到在内存中占用（方式）更多 space 的数据结构。此外，通常看似简单的操作（例如 'how many elements are in you'）不可能有效地回答，因此不要提供该功能。 java.util.concurrent 包中有这么多 classes 是有原因的：没有上帝-class 可以做到这一切并在两个内存中高效地完成，CPU ，并锁定方面。
[3] 搞清楚'trends'和'guarantees'的区别。例如，编写一个快速、高效的系统要容易得多，该系统可以从庞大的元素列表中给你（并删除）一个随机元素，'trends towards' 从一堆元素中公平地挑选，而不是 保证每次都是完全均匀随机选择的。
艺术的一部分是知道什么时候你可以利用趋势而不是保证，通常数量级的加速就在于这样的实现。
这里有一些关于如何制作假设的非常快的想法：
你是否添加所有内容，然后 'switch the mode' 并且不再添加其他元素，而只是从那里移除？
如果是这样的话，一个更快的主意：
有一个对象是'modal'。它开始时只有一个 add 方法（可能还有 addAll）。没有其他的。甚至 .get（不要添加你不需要的 API，它只会限制你在尝试优化事物时的灵活性！）。它甚至不承诺并发安全行为（同时从 2 个线程调用 add 有时会灾难性地失败）。当'done'时，你调用了一个build()方法。此 returns 一个 new 对象，仅具有 poll() 方法，returns 并发安全方式中的任意元素。
如果那是你的API你可以写非常效率和完全无锁！
您的构建器只是一个非常简单的 class，它包含一个简单的 jane arraylist 并填充它：
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());
}
}
这里我们结合了一大堆属性：
- 我们根本不删除。删除往往很慢，如果我们可以避免它，为什么不呢？
- 我们依赖于 AtomicInteger，它为我们提供了一种方法来保证在并发环境中以比锁快得多的方式进行严格和完整的排序。
- 我们将实施减少到您真正需要的部分。每个方法写起来都很痛苦。我包含了一个
size()方法来说明这一点：poll算法的工作方式是它递增 0 到 -1 甚至更糟（如果多个线程同时尝试poll()一个空轮询器，那个原子整数可以低于 -1，但最终它会回到 0，所以没有 'rolling over' 我们的原子整数的风险，因为没有系统会拥有 20 亿个线程）。我们需要在size()方法中防止这种情况。 - 这也意味着：如果你不是特别需要效率，那就不要理会这些，做一个全局锁定的数据结构。逃避很容易而且有效（只是效率不高）。测试并发是非常困难的（因为事情只是 可能 在正确的情况下出错，他们不能保证。在测试中你想要破坏代码实际上失败，这就是问题所在。这几乎是不可能的！） - 所以不要去那里，除非你完全知道你在做什么并且你确定你需要它。