jjzjj

c++ - 在 set<int> 与 vector<bool> 与 vector<boolean_t> 之间进行选择以用作位图(位集/位数组)

coder 2024-02-16 原文

给定一系列索引(标识符)，我想将每个索引映射到一个 bool 值，即:

// interface pseudocode
interface bitmap {
  bool identifier_is_set(unsigned int id_idx) const;
  void set_identifier(unsigned int id_idx, bool val) const;
};

这样我就可以设置和查询每个 ID(索引)是否已设置，您更喜欢用什么来实现它？

我认为这叫做位数组或位图或位集，如果我错了请纠正我。

假设最大标识符是预先确定的并且不大于 1e6 (1m)，可能更小 (10k - 100k)。(这意味着 sizeof(int)*maximum_id_idx 使用的大小很容易适合存入内存。)

目前我看到的可能的解决方案:

  • std::set<size_t> - 根据需要向该集合添加或删除标识符。只要我们有稀疏位图，这就允许任意大的标识符。
  • std::vector<bool> - 调整到适当的最大值，为每个 id_idx 存储 true 或 false。
  • std::vector<char> - 同样的事情，但没有遭受怪异 std::vector<bool>问题。使用的内存少于 vector<int> .
  • std::vector<int> - 使用 int作为 bool 标志，让容器使用机器的自然字大小。 (不知道这是否会有所作为。)

请回答您更喜欢哪种容器类型以及原因，考虑到上面引用的最大 id 限制，特别是考虑查询位图的性能方面(插入性能无关紧要).

注:vector的接口(interface)用法与 set没关系，因为它无论如何都会隐藏在它的包装类后面。

编辑:添加到关于 std::bitset 的讨论中:std::bitset 会将整个数组大小合并到对象中，即 sizeof(std::bitset<1m>) 的大小约为 1/8 兆字节，这构成了一个巨大的单个对象，并构成了一些你不能再放在堆栈上的东西(这可能相关也可能不相关)。

最佳答案

在不知道您运行此代码的平台和您的访问模式的情况下，很难说 vector<bool> 是否有效。会比 vector<char> 快(或 vector<int> )甚至 set<int>或 unordered_set<int> .

例如，如果您有一个极其稀疏的数组，则线性搜索 vector<int>只包含索引集的可能是最好的答案。 ( See Mike Abrash's article on optimizing Pixomatic for x86. )

另一方面，您的数组可能有点稀疏。有点稀疏是指集合元素的数量远大于 L1 或 L2。在这种情况下，更多底层细节以及您的实际访问模式开始发挥作用。

例如，在某些平台上，可变位移位非常昂贵。因此，如果您正在查询一组随机标识符，您执行此操作的频率越高，vector<char> 就越多或 vector<int>成为比 bitset<...> 更好的主意或 vector<bool> . (后两者使用移位来查找位。)另一方面，如果您按顺序迭代稀疏位 vector 并且只想设置位，则可以优化该迭代以消除变量移位的开销。

此时，您可能还想知道稀疏标识符的实际分布情况。如果它们聚集在一起，您需要知道最佳内存读取大小和一次读取一个字符之间的权衡。这将决定更频繁地访问缓存是否会抵消非 native 大小数据的读取。

如果标识符是分散的，您可以通过使用哈希集 (unordered_set<int>) 而不是位 vector 来获得显着的胜利。然而，这取决于负载。

关于c++ - 在 set<int> 与 vector<bool> 与 vector<boolean_t> 之间进行选择以用作位图(位集/位数组)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4155847/

ampvectorcode稀疏c++performance

有关c++ - 在 set<int> 与 vector<bool> 与 vector<boolean_t> 之间进行选择以用作位图(位集/位数组)的更多相关文章

  1. ruby-on-rails - 如何从 format.xml 中删除 <hash></hash> - 2

    我有一个对象has_many应呈现为xml的子对象。这不是问题。我的问题是我创建了一个Hash包含此数据，就像解析器需要它一样。但是rails自动将整个文件包含在.........我需要摆脱type="array"和我该如何处理？我没有在文档中找到任何内容。 最佳答案 我遇到了同样的问题；这是我的XML:我在用这个:entries.to_xml将散列数据转换为XML，但这会将条目的数据包装到中所以我修改了:entries.to_xml(root:"Contacts")但这仍然将转换后的XML包装在“联系人”中，将我的XML代码修改为

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

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

  3. ruby-on-rails - 如何使用 instance_variable_set 正确设置实例变量？ - 2

    我正在查看instance_variable_set的文档并看到给出的示例代码是这样做的:obj.instance_variable_set(:@instnc_var,"valuefortheinstancevariable")然后允许您在类的任何实例方法中以@instnc_var的形式访问该变量。我想知道为什么在@instnc_var之前需要一个冒号:。冒号有什么作用？ 最佳答案 我的第一直觉是告诉你不要使用instance_variable_set除非你真的知道你用它做什么。它本质上是一种元编程工具或绕过实例变量可见性的黑客攻击

  4. ruby-on-rails - rspec should have_select ('cars' , :options => ['volvo' , 'saab' ] 不工作 - 2

    关闭。这个问题需要detailsorclarity.它目前不接受答案。想改进这个问题吗？通过editingthispost添加细节并澄清问题.关闭8年前。Improvethisquestion在首页我有:汽车:VolvoSaabMercedesAudistatic_pages_spec.rb中的测试代码:it"shouldhavetherightselect"dovisithome_pathit{shouldhave_select('cars',:options=>['volvo','saab','mercedes','audi'])}end响应是rspec./spec/request

  5. ruby-on-rails - Nokogiri:使用 XPath 搜索 <div> - 2

    我使用Nokogiri(Rubygem)css搜索寻找某些在我的html里面。看起来Nokogiri的css搜索不喜欢正则表达式。我想切换到Nokogiri的xpath搜索，因为这似乎支持搜索字符串中的正则表达式。如何在xpath搜索中实现下面提到的(伪)css搜索？require'rubygems'require'nokogiri'value=Nokogiri::HTML.parse(ABBlaCD3"HTML_END#my_blockisgivenmy_bl="1"#my_eqcorrespondstothisregexmy_eq="\/[0-9]+\/"#FIXMEThefoll

  6. ruby - Rails 3 的 RGB 颜色选择器 - 2

    状态:我正在构建一个应用程序，其中需要一个可供用户选择颜色的字段，该字段将包含RGB颜色代码字符串。我已经测试了一个看起来很漂亮但效果不佳的。它是“挑剔的颜色”，并托管在此存储库中:https://github.com/Astorsoft/picky-color.在这里我打开一个关于它的一些问题的问题。问题:请建议我在Rails3应用程序中使用一些颜色选择器。 最佳答案 也许页面上的列表jQueryUIDevelopment:ColorPicker为您提供开箱即用的产品。原因是jQuery现在包含在Rails3应用程序中，因此使用基

  7. ruby - Sinatra set cache_control to static files in public folder编译错误 - 2

    我不知道为什么，但是当我设置这个设置时它无法编译设置:static_cache_control，[:public，:max_age=>300]这是我得到的syntaxerror,unexpectedtASSOC,expecting']'(SyntaxError)set:static_cache_control,[:public,:max_age=>300]^我只想将“过期”header设置为css、javaascript和图像文件。谢谢。 最佳答案 我猜您使用的是Ruby1.8.7。Sinatra文档中显示的语法似乎是在Ruby1.

  8. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  9. ruby - Arrays Sets 和 SortedSets 在 Ruby 中是如何实现的 - 2

    通常，数组被实现为内存块，集合被实现为HashMap，有序集合被实现为跳跃列表。在Ruby中也是如此吗？我正在尝试从性能和内存占用方面评估Ruby中不同容器的使用情况 最佳答案 数组是Ruby核心库的一部分。每个Ruby实现都有自己的数组实现。Ruby语言规范只规定了Ruby数组的行为，并没有规定任何特定的实现策略。它甚至没有指定任何会强制或至少建议特定实现策略的性能约束。然而，大多数Rubyist对数组的性能特征有一些期望，这会迫使不符合它们的实现变得默默无闻，因为实际上没有人会使用它:插入、前置或追加以及删除元素的最坏情况步骤复

  10. ruby-on-rails - 在 Ruby on Rails 中添加 boolean 列值 - 2

    我正在开发一个创建网络博客的RubyonRails项目。我希望将一个名为featured的boolean数据库字段添加到Post模型中。该字段应该可以通过我添加的事件管理界面进行编辑。我使用了以下代码，但我什至没有在网站上显示另一列。$railsgeneratemigrationaddFeaturedfeatured:boolean$rakedb:migrate我是RubyonRails的新手，非常感谢任何帮助。我的index.html.erb文件中的相关代码(views):FeaturedPost架构.rb:ActiveRecord::Schema.define(:version=>

随机推荐