如何有效地找到一组数组中的哪个数组有成员

Question

如何有效地找到数组列表中的哪个数组有成员。

上下文用于消息代理。我有一个队列列表，需要定期将它们的内容推送给消费者，但是由于队列的数量可能很大，所以我想快速找出哪些队列中有元素。

我目前唯一的解决方案基本上是保留一个单独的列表，该列表跟踪哪个数组中仍有内容，但对替代方案很好奇，这让我很烦 ;)

我正在使用 javascript，但我希望能更全面地了解我应该研究哪种算法。

Answer 1

我打算让这个语言不可知并让我的回答简短明了。

维护并行数据结构：另一组存储数组 ID，但仅存储非空数组的那些。

• 创建新的（空）数组时，仅将其添加到第一个数组中。
• 当您添加到一个数组时，将其添加到第二组，前提是它还不存在。
• 从数组中删除时，如果数组现在为空，请将其从第二组中删除。
• 当您删除一个数组时，将其从第一组（和第二组，如果存在的话）中移除。

如果您为第二组使用哈希集，则插入和删除时间不会改变。这是人们可能要求的最有效的事情，而且这种类型的混合数据结构是必要的 AFAICT。

然后您可以通过遍历第二组来找到所有非空数组。