草庐IT

C++ 在 unsigned char 数组和 unsigned char vector 中扫描某些元素的最快方法是什么？

coder 2024-01-31 原文

我有一个小问题，扫描大型 unsigned char 数组和仅包含 unsigned char 元素的 vector 中的某些元素的最快方法是什么？直接回答会很好，但深入详细的回答会很棒。我说的快是什么意思？基本上，至少要在一秒钟内搜索某些字符。我知道这不是一个很有教养的定义......

注意:数组没有排序。

共同声明:

unsigned char* Array = new unsigned char[ 50000 ];
std::vector< unsigned char > Vec( 50000 );
/*
 * Fill Array & Vec with random bytes
 */

比方说，我想在数组中搜索字母“a”，我会简单地编写这个循环来搜索它:

注意:搜索过程会搜索多个元素。主要是 256。因此，您可以利用这个神奇的数字。

For循环方法:

unsigned int Count = 0;
for ( unsigned int Index = 0; Index != 50000; ++ Index )
   if( Array[ Index ] == 'a' ) Count ++;

std::count 方法:

unsigned int Count = std::count ( Array, Array + 50000, 'a' );

有没有更快的方法来搜索数组中的某些元素？

一些想法 - 请不要为此反对我!这只是一个想法。我想要一些意见。

排序

如果我们复制一个Array并对其进行排序，速度会不会更好？为什么要复制？好吧，因为我们需要保留原始内容。目标是基本上扫描并计算字符的出现次数。记住，速度很重要。这意味着复制过程必须很快。

Answer: No and its not worth it!

为什么？好吧，让我们读一下:

@基里尔基洛夫:

Depends. If you plan to search for a single char - absolutely not. Copying the array is an expensive operation. Sorting it - even more expensive.

Well, if you will have only one array and you plan to search for, let's say, 100 different characters, then this method could give you a better performance. Now, this really depends on your usage. And nobody will be able to give you the absolutely correct answer for this case. You need to run it and profile.

*向下滚动到@Kiril Krov 的信息性帖子了解更多信息。

答案: 到目前为止，还没有一个可靠的或答案，因为没有一个真正“快速”的方法来实现这个目标，尤其是当它没有被排序时。但是，线程 可能是一种可能的解决方案。但是，请注意我们的 CPU!这是基于@Andrea 提交的答案(向下滚动更多信息以获取更多信息)——我希望我没看错。

最佳答案

正如其他人所写，最佳算法的复杂度是 O(n)，特别是因为您的数组未排序。

为了加快搜索速度，您可以 segmentation 数组并在单独线程 中分别扫描每个部分。这将与您机器上可用的 CPU 内核数量成线性比例。

例如，如果您有四个可用内核，则生成四个线程并让每个线程扫描阵列的四分之一。

可能这个讨论可能会有所帮助:Using threads to reduce array search time

在任何情况下(对于任何与性能相关的问题都是如此)，您应该分析您的代码。为您拥有的方法创建一个测试用例，测量它花费的时间并将其作为基线。然后，对于您所做的每项修改，重新进行测量以检查它是否真的缩短了执行时间。还要确保多次执行每个测量(在同一测试用例中)并计算平均值，以减少缓存和其他预热效果(理想情况下，在开始第一次测量之前至少执行一次代码)。

这与 Java 相关，但提供了一些很好的反馈，表明并行化并非在所有情况下都有意义:A Beginner´s Guide to Hardcore Concurrency

关于C++ 在 unsigned char 数组和 unsigned char vector 中扫描某些元素的最快方法是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15542029/

unsignedcharstrongsectionc++

有关C++ 在 unsigned char 数组和 unsigned char vector 中扫描某些元素的最快方法是什么？的更多相关文章

  1. ruby - 如何使用 Nokogiri 的 xpath 和 at_xpath 方法 - 2

    我正在学习如何使用Nokogiri，根据这段代码我遇到了一些问题:require'rubygems'require'mechanize'post_agent=WWW::Mechanize.newpost_page=post_agent.get('http://www.vbulletin.org/forum/showthread.php?t=230708')puts"\nabsolutepathwithtbodygivesnil"putspost_page.parser.xpath('/html/body/div/div/div/div/div/table/tbody/tr/td/div

  2. ruby - 如何从 ruby​​ 中的字符串运行任意对象方法？ - 2

    总的来说，我对ruby​​还比较陌生，我正在为我正在创建的对象编写一些rspec测试用例。许多测试用例都非常基础，我只是想确保正确填充和返回值。我想知道是否有办法使用循环结构来执行此操作。不必为我要测试的每个方法都设置一个assertEquals。例如:describeitem,"TestingtheItem"doit"willhaveanullvaluetostart"doitem=Item.new#HereIcoulddotheitem.name.shouldbe_nil#thenIcoulddoitem.category.shouldbe_nilendend但我想要一些方法来使用

  3. ruby - 为什么我可以在 Ruby 中使用 Object#send 访问私有(private)/ protected 方法？ - 2

    类classAprivatedeffooputs:fooendpublicdefbarputs:barendprivatedefzimputs:zimendprotecteddefdibputs:dibendendA的实例a=A.new测试a.foorescueputs:faila.barrescueputs:faila.zimrescueputs:faila.dibrescueputs:faila.gazrescueputs:fail测试输出failbarfailfailfail.发送测试[:foo,:bar,:zim,:dib,:gaz].each{|m|a.send(m)resc

  4. ruby - Facter::Util::Uptime:Module 的未定义方法 get_uptime (NoMethodError) - 2

    我正在尝试设置一个puppet节点，但ruby​​gems似乎不正常。如果我通过它自己的二进制文件(/usr/lib/ruby/gems/1.8/gems/facter-1.5.8/bin/facter)在cli上运行facter，它工作正常，但如果我通过由ruby​​gems(/usr/bin/facter)安装的二进制文件，它抛出:/usr/lib/ruby/1.8/facter/uptime.rb:11:undefinedmethod`get_uptime'forFacter::Util::Uptime:Module(NoMethodError)from/usr/lib/ruby

  5. ruby-on-rails - Rails - 子类化模型的设计模式是什么？ - 2

    我有一个模型:classItem项目有一个属性“商店”基于存储的值，我希望Item对象对特定方法具有不同的行为。Rails中是否有针对此的通用设计模式？如果方法中没有大的if-else语句，这是如何干净利落地完成的？ 最佳答案 通常通过Single-TableInheritance. 关于ruby-on-rails-Rails-子类化模型的设计模式是什么？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.co

  6. ruby-on-rails - 在 Ruby 中循环遍历多个数组 - 2

    我有多个ActiveRecord子类Item的实例数组，我需要根据最早的事件循环打印。在这种情况下，我需要打印付款和维护日期，如下所示:ItemAmaintenancerequiredin5daysItemBpaymentrequiredin6daysItemApaymentrequiredin7daysItemBmaintenancerequiredin8days我目前有两个查询，用于查找maintenance和payment项目(非排他性查询)，并输出如下内容:paymentrequiredin...maintenancerequiredin...有什么方法可以改善上述(丑陋的)代

  7. Ruby 方法() 方法 - 2

    我想了解Ruby方法methods()是如何工作的。我尝试使用“ruby方法”在Google上搜索，但这不是我需要的。我也看过ruby​​-doc.org，但我没有找到这种方法。你能详细解释一下它是如何工作的或者给我一个链接吗？更新我用methods()方法做了实验，得到了这样的结果:'labrat'代码classFirstdeffirst_instance_mymethodenddefself.first_class_mymethodendendclassSecond使用类#returnsavailablemethodslistforclassandancestorsputsSeco

  8. ruby - 什么是填充的 Base64 编码字符串以及如何在 ruby​​ 中生成它们？ - 2

    我正在使用的第三方API的文档状态:"[O]urAPIonlyacceptspaddedBase64encodedstrings."什么是“填充的Base64编码字符串”以及如何在Ruby中生成它们。下面的代码是我第一次尝试创建转换为Base64的JSON格式数据。xa=Base64.encode64(a.to_json) 最佳答案 他们说的padding其实就是Base64本身的一部分。它是末尾的“=”和“==”。Base64将3个字节的数据包编码为4个编码字符。所以如果你的输入数据有长度n和n%3=1=>"=="末尾用于填充n%

  9. 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

  10. ruby - 多次弹出/移动 ruby​​ 数组 - 2

    我的代码目前看起来像这样numbers=[1,2,3,4,5]defpop_threepop=[]3.times{pop有没有办法在一行中完成pop_three方法中的内容？我基本上想做类似numbers.slice(0,3)的事情，但要删除切片中的数组项。嗯...嗯，我想我刚刚意识到我可以试试slice! 最佳答案 是numbers.pop(3)或者numbers.shift(3)如果你想要另一边。 关于ruby-多次弹出/移动ruby​​数组，我们在StackOverflow上找到一

随机推荐