假设我有一组通用的索引对象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++ 数据结构,但这个问题并不是真正特定于语言的。
最佳答案
我认为这 3 种方法都没有(主要)问题。在决定选择其中之一时,您必须考虑:
- 代码可读性
- 代码可维护性
- 表现
代码可读性
理解代码的作用是多么容易和直观。代码不应有任何令人惊讶的行为。
如果使用良好的命名和干净的结构化代码,这三者都可以相本地具有同等的可读性。
代码可维护性
调试、测试、扩展代码有多容易。
具有两个结构的变体成本略高。但只是轻微的。与其他的相比,我没有看到更多的复杂性。您可以在单元测试中进行测试以检查方案的完整性。 IE。检查 bool vector 和整数 vector 是否同意 S
是什么。
性能
您可能整天都在假设什么变体以及变体的速度有多快,但归根结底,如果没有实际的分析,任何关于性能的讨论都是毫无意义的。如果性能对您来说是一个重要因素,那么实现所有 3 种方法并测量它们的实际性能。
关于c++ - 如果同一数据位于不同的数据结构中,则维护它们的两个拷贝是否是一种不好的做法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/47153546/