草庐IT

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

coder 2024-02-20 原文

假设我有一组通用的索引对象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/

amp做法codevector的c++performancedata-structures

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

  1. ruby - 使用 ruby​​ 将 HTML 转换为纯文本并维护结构/格式 - 2

    我想将html转换为纯文本。不过，我不想只删除标签，我想智能地保留尽可能多的格式。为插入换行符标签，检测段落并格式化它们等。输入非常简单，通常是格式良好的html(不是整个文档，只是一堆内容，通常没有anchor或图像)。我可以将几个正则表达式放在一起，让我达到80%，但我认为可能有一些现有的解决方案更智能。 最佳答案 首先，不要尝试为此使用正则表达式。很有可能你会想出一个脆弱/脆弱的解决方案，它会随着HTML的变化而崩溃，或者很难管理和维护。您可以使用Nokogiri快速解析HTML并提取文本:require'nokogiri'h

  2. ruby - 解析 RDFa、微数据等的最佳方式是什么，使用统一的模式/词汇(例如 schema.org)存储和显示信息 - 2

    我主要使用Ruby来执行此操作，但到目前为止我的攻击计划如下:使用gemsrdf、rdf-rdfa和rdf-microdata或mida来解析给定任何URI的数据。我认为最好映射到像schema.org这样的统一模式，例如使用这个yaml文件，它试图描述数据词汇表和opengraph到schema.org之间的转换:#SchemaXtoschema.orgconversion#data-vocabularyDV:name:namestreet-address:streetAddressregion:addressRegionlocality:addressLocalityphoto:i

  3. ruby-on-rails - 如果为空或不验证数值，则使属性默认为 0 - 2

    我希望我的UserPrice模型的属性在它们为空或不验证数值时默认为0。这些属性是tax_rate、shipping_cost和price。classCreateUserPrices8,:scale=>2t.decimal:tax_rate,:precision=>8,:scale=>2t.decimal:shipping_cost,:precision=>8,:scale=>2endendend起初，我将所有3列的:default=>0放在表格中，但我不想要这样，因为它已经填充了字段，我想使用占位符。这是我的UserPrice模型:classUserPrice回答before_val

  4. ruby-on-rails - 如何在 ruby​​ 中使用两个参数异步运行 exe？ - 2

    exe应该在我打开页面时运行。异步进程需要运行。有什么方法可以在ruby​​中使用两个参数异步运行exe吗？我已经尝试过ruby​​命令-system()、exec()但它正在等待过程完成。我需要用参数启动exe，无需等待进程完成是否有任何ruby​​gems会支持我的问题？ 最佳答案 您可以使用Process.spawn和Process.wait2:pid=Process.spawn'your.exe','--option'#Later...pid,status=Process.wait2pid您的程序将作为解释器的子进程执行。除

  5. ruby - Highline 询问方法不会使用同一行 - 2

    设置:狂欢ruby1.9.2高线(1.6.13)描述:我已经相当习惯在其他一些项目中使用highline，但已经有几个月没有使用它了。现在，在Ruby1.9.2上全新安装时，它似乎不允许在同一行回答提示。所以以前我会看到类似的东西:require"highline/import"ask"Whatisyourfavoritecolor?"并得到:Whatisyourfavoritecolor?|现在我看到类似的东西:Whatisyourfavoritecolor?|竖线(|)符号是我的终端光标。知道为什么会发生这种变化吗？ 最佳答案

  6. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  7. ruby-on-rails - 如果 Object::try 被发送到一个 nil 对象，为什么它会起作用？ - 2

    如果您尝试在Ruby中的nil对象上调用方法，则会出现NoMethodError异常并显示消息:"undefinedmethod‘...’fornil:NilClass"然而，有一个tryRails中的方法，如果它被发送到一个nil对象，它只返回nil:require'rubygems'require'active_support/all'nil.try(:nonexisting_method)#noNoMethodErrorexceptionanymore那么try如何在内部工作以防止该异常？ 最佳答案 像Ruby中的所有其他对象

  8. ruby - 如果指定键的值在数组中相同，如何合并哈希 - 2

    我有一个这样的哈希数组:[{:foo=>2,:date=>Sat,01Sep2014},{:foo2=>2,:date=>Sat,02Sep2014},{:foo3=>3,:date=>Sat,01Sep2014},{:foo4=>4,:date=>Sat,03Sep2014},{:foo5=>5,:date=>Sat,02Sep2014}]如果:date相同，我想合并哈希值。我对上面数组的期望是:[{:foo=>2,:foo3=>3,:date=>Sat,01Sep2014},{:foo2=>2,:foo5=>5:date=>Sat,02Sep2014},{:foo4=>4,:dat

  9. ruby - Ruby 有 `Pair` 数据类型吗？ - 2

    有时我需要处理键/值数据。我不喜欢使用数组，因为它们在大小上没有限制(很容易不小心添加超过2个项目，而且您最终需要稍后验证大小)。此外，0和1的索引变成了魔数(MagicNumber)，并且在传达含义方面做得很差(“当我说0时，我的意思是head...”)。散列也不合适，因为可能会不小心添加额外的条目。我写了下面的类来解决这个问题:classPairattr_accessor:head,:taildefinitialize(h,t)@head,@tail=h,tendend它工作得很好并且解决了问题，但我很想知道:Ruby标准库是否已经带有这样一个类？ 最佳

  10. ruby-on-rails - 如果我将 ruby​​ 版本 2.5.1 与 rails 版本 2.3.18 一起使用会怎样？ - 2

    如果我使用ruby​​版本2.5.1和Rails版本2.3.18会怎样？我有基于rails2.3.18和ruby​​1.9.2p320构建的rails应用程序，我只想升级ruby的版本，而不是rails，这可能吗？我必须面对哪些挑战？ 最佳答案 GitHub维护apublicfork它有针对旧Rails版本的分支，有各种变化，它们一直在运行。有一段时间，他们在较新的Ruby版本上运行较旧的Rails版本，而不是最初支持的版本，因此您可能会发现一些关于需要向后移植的有用提示。不过，他们现在已经有几年没有使用2.3了，所以充其量只能让更

随机推荐