草庐IT

读取标准输入的 C++ 最快的 cin？

coder 2024-02-18 原文

我在 Linux 上使用 cachegrind 分析了一个计算量大的 C++ 程序。令人惊讶的是，事实证明我的程序的瓶颈不在于任何排序或计算方法......而是在于读取输入。

这是 cachegrind 的屏幕截图，以防我错误地解释分析器结果(参见 scanf()):

我希望我说的是对的scanf()占用了我 80.92% 的运行时间。

我使用 cin >> int_variable_here 读取输入，像这样:

std::ios_base::sync_with_stdio (false); // Supposedly makes I/O faster
cin >> NumberOfCities;
cin >> NumberOfOldRoads;
Roads = new Road[NumberOfOldRoads];

for (int i = 0; i < NumberOfOldRoads; i++)
{
    int cityA, cityB, length;    

    cin >> cityA;
    //scanf("%d", &cityA);    // scanf() and cin are both too slow
    cin >> cityB;
    //scanf("%d", &cityB);
    cin >> length;
    //scanf("%d", &length);

    Roads[i] = Road(cityA, cityB, length);
}

如果您没有发现此输入读取代码有任何问题，能否请您推荐一种更快的读取输入的方法？我正在考虑尝试 getline() (在我等待回复的同时处理它)。我的猜测是 getline() 可能运行得更快，因为它必须进行更少的转换并且解析流的总次数更少(这只是我的猜测，尽管我最终也必须将字符串解析为整数)。

我所说的“太慢”的意思是，这是一项较大的家庭作业的一部分，它会在一段时间后超时(我相信是 90 秒)。我非常有信心瓶颈就在这里，因为我故意注释掉了程序其余部分的主要部分，但它仍然超时。我不知道导师通过我的程序运行了哪些测试用例，但它必须是一个巨大的输入文件。那么，我可以用什么来最快地读取输入？

输入格式严格:3个整数，每行一个空格，多行:

示例输入:

7 8 3
7 9 2
8 9 1
0 1 28
0 5 10
1 2 16

我需要制作一个 Road每行中的整数。

另外请不要将输入重定向到我的程序到标准输入(myprogram < whatever_test_case.txt)。我不是在阅读特定文件。我刚从 cin 读到.

更新

使用 Slava's方法:

输入读取似乎花费更少的时间，但它仍然超时(可能不再是由于输入读取)。 Slava 的方法在 Road() ctor 中实现(从 main 向下 2 个)。所以现在它需要 22% 的时间而不是 80%。我正在考虑优化 SortRoadsComparator()因为它被调用了 26,000,000 次。

比较器代码:

// The complexity is sort of required for the whole min() max(), based off assignment instructions
bool SortRoadsComparator(const Road& a, const Road& b)
{
    if (a.Length > b.Length) 
        return false;

    else if (b.Length > a.Length) 
        return true;

    else
    {
        // Non-determinism case
        return ( (min(a.CityA, a.CityB) < min(b.CityA, b.CityB)) ||
            (
            (min(a.CityA, a.CityB) == min(b.CityA, b.CityB)) && max(a.CityA, a.CityB) < max(b.CityA, b.CityB)                                     
            )
            );
    }
}

使用 enhzflep's方法

考虑解决

我会认为这个问题已经解决了，因为瓶颈不再是读取输入。 Slava 的方法对我来说是最快的。

最佳答案

众所周知，流非常慢。不过，这并不奇怪——他们需要处理本地化、条件等。一种可能的解决方案是通过 std::getline( std::::cin, str ) 逐行读取文件，并通过类似的方式将字符串转换为数字这个:

std::vector<int> getNumbers( const std::string &str )
{
   std::vector<int> res;
   int value = 0;
   bool gotValue = false;
   for( int i = 0; i < str.length(); ++i ) {
      if( str[i] == ' ' ) {
         if( gotValue ) res.push_back( value );
         value = 0;
         gotValue = false;
         continue;
      }
      value = value * 10 + str[i] - '0';
      gotValue = true;
   }
   if( gotValue ) res.push_back( value );
   return res;
}

我没有测试这段代码，写它是为了展示这个想法。我假设您不希望在输入中得到任何东西，但空格和数字，因此它不会验证输入。

要优化排序，首先您应该检查是否真的需要对整个序列进行排序。对于比较器，我会编写方法 getMin() getMax() 并将该值存储在对象中(而不是一直计算它们):

bool SortRoadsComparator(const Road& a, const Road& b)
{
    if( a.Length != b.Length ) return a.Length < b.length;
    if( a.getMin() != b.getMin() ) return a.getMin() < b.getMin();
    return a.getMax() < b.getMax();
}

如果我了解您当前的比较器如何正常工作。

关于读取标准输入的 C++ 最快的 cin？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15036878/

amp最快codestrongsectionc++performance

有关读取标准输入的 C++ 最快的 cin？的更多相关文章

  1. ruby - 如何将脚本文件的末尾读取为数据文件(Perl 或任何其他语言) - 2

    我正在寻找执行以下操作的正确语法(在Perl、Shell或Ruby中):#variabletoaccessthedatalinesappendedasafileEND_OF_SCRIPT_MARKERrawdatastartshereanditcontinues. 最佳答案 Perl用__DATA__做这个:#!/usr/bin/perlusestrict;usewarnings;while(){print;}__DATA__Texttoprintgoeshere 关于ruby-如何将脚

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

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

  3. Ruby 写入和读取对象到文件 - 2

    好的，所以我的目标是轻松地将一些数据保存到磁盘以备后用。您如何简单地写入然后读取一个对象？所以如果我有一个简单的类classCattr_accessor:a,:bdefinitialize(a,b)@a,@b=a,bendend所以如果我从中非常快地制作一个objobj=C.new("foo","bar")#justgaveitsomerandomvalues然后我可以把它变成一个kindaidstring=obj.to_s#whichreturns""我终于可以将此字符串打印到文件或其他内容中。我的问题是，我该如何再次将这个id变回一个对象？我知道我可以自己挑选信息并制作一个接受该信

  4. ruby - 将 spawn() 的标准输出/标准错误重定向到 Ruby 中的字符串 - 2

    我想使用spawn(针对多个并发子进程)在Ruby中执行一个外部进程，并将标准输出或标准错误收集到一个字符串中，其方式类似于使用Python的子进程Popen.communicate()可以完成的操作。我尝试将:out/:err重定向到一个新的StringIO对象，但这会生成一个ArgumentError，并且临时重新定义$stdxxx会混淆子进程的输出。 最佳答案 如果你不喜欢popen，这是我的方法:r,w=IO.pipepid=Process.spawn(command,:out=>w,:err=>[:child,:out])

  5. 世界前沿3D开发引擎HOOPS全面讲解——集3D数据读取、3D图形渲染、3D数据发布于一体的全新3D应用开发工具 - 2

    无论您是想搭建桌面端、WEB端或者移动端APP应用，HOOPSPlatform组件都可以为您提供弹性的3D集成架构，同时，由工业领域3D技术专家组成的HOOPS技术团队也能为您提供技术支持服务。如果您的客户期望有一种在多个平台（桌面/WEB/APP，而且某些客户端是“瘦”客户端）快速、方便地将数据接入到3D应用系统的解决方案，并且当访问数据时，在各个平台上的性能和用户体验保持一致，HOOPSPlatform将帮助您完成。利用HOOPSPlatform，您可以开发在任何环境下的3D基础应用架构。HOOPSPlatform可以帮您打造3D创新型产品，HOOPSSDK包含的技术有：快速且准确的CAD

  6. ruby-on-rails - 标准化文件名的字符串，删除重音和特殊字符 - 2

    我正在尝试找到一种方法来规范化字符串以将其作为文件名传递。到目前为止我有这个:my_string.mb_chars.normalize(:kd).gsub(/[^\x00-\x7F]/n,'').downcase.gsub(/[^a-z]/,'_')但第一个问题:-字符。我猜这个方法还有更多问题。我不控制名称，名称字符串可以有重音符、空格和特殊字符。我想删除所有这些，用相应的字母('é'=>'e')替换重音符号，并将其余的替换为'_'字符。名字是这样的:“Prélèvements-常规”“健康证”...我希望它们像一个没有空格/特殊字符的文件名:“prelevements_routin

  7. 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.你能做的最好的事情是:

  8. python - 如何读取 MIDI 文件、更改其乐器并将其写回？ - 2

    我想解析一个已经存在的.mid文件，改变它的乐器，例如从“acousticgrandpiano”到“violin”，然后将它保存回去或作为另一个.mid文件。根据我在文档中看到的内容，该乐器通过program_change或patch_change指令进行了更改，但我找不到任何在已经存在的MIDI文件中执行此操作的库.他们似乎都只支持从头开始创建的MIDI文件。 最佳答案 MIDIpackage会为您完成此操作，但具体方法取决于midi文件的原始内容。一个MIDI文件由一个或多个音轨组成，每个音轨是十六个channel中任何一个上的

  9. STM32读取串口传感器数据（颗粒物传感器，主动上传） - 2

    文章目录1.开发板选择*用到的资源2.串口通信（个人理解）3.代码分析（注释比较详细）1.主函数2.串口1配置3.串口2配置以及中断函数4.注意问题5.源码链接1.开发板选择我用的是STM32F103RCT6的板子，不过代码大概在F103系列的板子上都可以运行，我试过在野火103的霸道板上也可以，主要看一下串口对应的引脚一不一样就行了，不一样的就更改一下。*用到的资源keil5软件这里用到了两个串口资源，采集数据一个，串口通信一个，板子对应引脚如下：串口1，TX：PA9，RX：PA10串口2，TX：PA2，RX：PA32.串口通信（个人理解）我就从串口采集传感器数据这个过程说一下我自己的理解，

  10. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

随机推荐