c++ - 如果同一数据位于不同的数据结构中，则维护它们的两个拷贝是否是一种不好的做法？

Question

假设我有一组通用的索引对象U，以及这些对象的子集S。 S 很大(例如，1,000,000 个元素)，但是 U 大得多(例如，至少 100,000,000 个元素)。

我想对这些集合执行两个基本操作:

(1) 给定从 0 到 U 的大小减 1 的任何整数 x，检查 S 的成员资格，如果不是成员，然后将x添加到S，和

(2) 从S中选择(并移除)一个随机元素。

为了执行操作 (1) 的第一部分，我认为保留一个大小为 U 的 bool vector v 是有意义的，其中值为true 如果元素 x 是集合 S 的成员。

但是，因为U比S大很多，所以在v中随机选择一个元素，希望它也是S中的一个元素S 没有意义。如果 U 比 S 大 100 倍，那么它只会找到 S 的一个元素，平均每 100 次尝试一次。

因此，为了执行第二个操作，维护 S 中元素的索引列表并从中选择一个随机元素是有意义的。

现在唯一的问题是，现在有相同数据的两个拷贝，并且每个操作都需要分别更新它们。这是第一个操作的伪代码:

** operation 1 - check membership and add **
input: boolean vector, v
       integer vector, S
       integer, x

if v[x] is not true:
    v[x] = true
    append x to S
return

这相对简单，但它必须更新索引 vector ，即使它没有使用它。这是第二个操作:

** operation 2 - select and remove random element of S **
input: boolean vector, v
       integer vector, S

generate random integer x between 0 and size of S
set v[S[x]] to false
remove S[x] from S
return

维护数据的两个拷贝使这两个操作变得更加复杂，因为每个操作都必须更新两个数据结构，即使它只需要一个。这是不好的做法吗？

我能想到的唯一选择是使用一个或另一个。但这使得一个操作更简单，但另一个更复杂。例如(只给出比较复杂的):

** operation 1 - check membership and add**
input: integer vector, S
       integer, x

iterate over S
if x in S:
    return
else:
    append x to S
    return

所以每次，它都必须遍历整个 S，而不是单个查找，并且

** operation 2 - select and remove random element of S **
input: boolean vector, v

while true:
    generate random integer x between 0 and size of S
    if v[x] true:
        v[x] = false
        return

这两个看起来都非常低效，特别是如果 U 和 S 的大小很大，并且 U 和 之间的差异>S 也很大。有没有一种方法可以仅使用一种数据结构来高效地执行这两种操作？或者维护同一事物的两个拷贝真的不是什么大问题吗？

编辑:

我正在编写的代码是用 c++ 编写的，所以我想我是在特别询问 c++ 数据结构，但这个问题并不是真正特定于语言的。

Answer 1

我认为这 3 种方法都没有(主要)问题。在决定选择其中之一时，您必须考虑:

• 代码可读性
• 代码可维护性
• 表现

代码可读性

理解代码的作用是多么容易和直观。代码不应有任何令人惊讶的行为。

如果使用良好的命名和干净的结构化代码，这三者都可以相本地具有同等的可读性。

代码可维护性

调试、测试、扩展代码有多容易。

具有两个结构的变体成本略高。但只是轻微的。与其他的相比，我没有看到更多的复杂性。您可以在单元测试中进行测试以检查方案的完整性。 IE。检查 bool vector 和整数 vector 是否同意 S 是什么。

性能

您可能整天都在假设什么变体以及变体的速度有多快，但归根结底，如果没有实际的分析，任何关于性能的讨论都是毫无意义的。如果性能对您来说是一个重要因素，那么实现所有 3 种方法并测量它们的实际性能。