草庐IT

c++ - If-else-if 与 map

coder 2024-02-07 原文

假设我有这样一个 if/else-if 链:

if( x.GetId() == 1 )
{
}
else if( x.GetId() == 2 )
{
}
// ... 50 more else if statements

我想知道的是，如果我保留一张 map ，它在性能方面会不会更好？ (假设键是整数)

最佳答案

map (通常)是使用红黑树实现的，它提供 O(log N) 查找，因为树始终保持平衡。您的 if 语句线性列表将是 O(N) 最坏的情况。所以，是的， map 的查找速度会快得多。

许多人建议使用 switch 语句，这对您来说可能不会更快，具体取决于您的实际 if 语句。编译器有时可以通过使用 O(1) 的跳转表来优化 switch，但这仅适用于未定义标准的值；因此这种行为可能有些不确定。虽然这里有一篇很棒的文章，其中包含一些关于优化 switch 语句的技巧 Optimizing C and C++ Code .

从技术上讲，您甚至可以手动制定一个平衡树，这最适合静态数据，我最近刚好创建了一个函数来快速找到字节中设置了哪个位(这在 I/上的嵌入式应用程序中使用O pin 中断并且当 99% 的时间只有 1 位会在字节中设置时必须很快):

unsigned char single_bit_index(unsigned char bit) {
    // Hard-coded balanced tree lookup
    if(bit > 0x08)
        if(bit > 0x20)
            if(bit == 0x40)
                return 6;
            else
                return 7;
        else
            if(bit == 0x10)
                return 4;
            else
                return 5;
    else
        if(bit > 0x02)
            if(bit == 0x04)
                return 2;
            else
                return 3;
        else
            if(bit == 0x01)
                return 0;
            else
                return 1;
}

这为 8 个值中的任何一个提供了 3 个步骤的持续查找，这给了我非常确定的性能，线性搜索——给定随机数据——将平均 4 个步骤查找，最好的情况是 1，最坏的情况是8步的情况。

这是编译器可能不会优化为跳转表的范围的一个很好的例子，因为我正在搜索的 8 个值相距甚远:1、2、4、8、16、32、64 和128. 它必须创建一个非常稀疏的 128 位置表，其中只有 8 个元素包含一个目标，这在具有大量 RAM 的 PC 上可能不是什么大问题，但在微 Controller 上它会是 killer 。

关于c++ - If-else-if 与 map，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/2460363/

If-else-ifampsectionelsereturnc++performancemap

有关c++ - If-else-if 与 map的更多相关文章

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

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

  2. ruby-on-rails - `a ||= b` 和 `a = b if a.nil 之间的区别？ - 2

    我正在检查一个Rails项目。在ERubyHTML模板页面上，我看到了这样几行:我不明白为什么不这样写:在这种情况下，||=和ifnil?有什么区别？ 最佳答案 在这种特殊情况下没有区别，但可能是出于习惯。每当我看到nil?被使用时，它几乎总是使用不当。在Ruby中，很少有东西在逻辑上是假的，只有文字false和nil是。这意味着像if(!x.nil?)这样的代码几乎总是更好地表示为if(x)除非期望x可能是文字false。我会将其切换为||=false，因为它具有相同的结果，但这在很大程度上取决于偏好。唯一的缺点是赋值会在每次运行

  3. ruby - ruby 中有 each_if 吗？ - 2

    假设我在Ruby中有这个each循环。@list.each{|i|putsiifi>10breakend}我想循环遍历列表直到满足条件。这让我感到“不像Ruby”，因为我是Ruby的新手，是否有Ruby方法可以做到这一点？ 最佳答案 您可以使用Enumerable#detect或Enumerable#take_while，取决于您想要的结果。@list.detect{|i|putsii>10}#Returnsthefirstelementgreaterthan10,ornil.正如其他人所指出的，更好的风格是先进行子选择，然后再对其

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

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

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

  6. ruby-on-rails - rails : check if the model was really saved in after_save - 2

    ActiveRecord用于在每次调用保存方法时调用after_save回调，即使模型没有更改并且没有生成插入/更新查询也是如此。这实际上是默认行为。在大多数情况下这没问题。但是一些after_save回调对模型是否实际保存的事情很敏感。有没有办法确定模型是否实际保存在after_save中？我正在运行以下测试代码:classStage 最佳答案 ActiveRecordusetocallafter_savecallbackeachtimesavemethodiscalledevenifthemodelwasnotchangedan

  7. ruby - 你会如何在 Ruby 中表达成语 "with this object, if it exists, do this"？ - 2

    在Ruby(尤其是Rails)中，您经常需要检查某物是否存在，然后对其执行操作，例如:if@objects.any?puts"Wehavetheseobjects:"@objects.each{|o|puts"hello:#{o}"end这是最短的，一切都很好，但是如果你有@objects.some_association.something.hit_database.process而不是@objects呢？我将不得不在if表达式中重复两次，如果我不知道实现细节并且方法调用很昂贵怎么办？显而易见的选择是创建一个变量，然后测试它，然后处理它，但是你必须想出一个变量名(呃)，它也会在内存中

  8. ruby - 在 Ruby 的 if 语句中检查 bash 命令 - 2

    如何在Ruby的if语句中检查bash命令的返回值(true/false)。我想要这样的东西，if("/usr/bin/fswscell>/dev/null2>&1")has_afs="true"elsehas_afs="false"end它会提示以下错误含义，它总是返回true。(irb):5:warning:stringliteralincondition正确的语法是什么？更新:/usr/bin/fswscell寻找afs安装和运行状态。它会抛出这样的字符串，Thisworkstationbelongstocell如果afs没有运行，命令以状态1退出 最

  9. ruby - 在 ruby​​ 中使用 .try 函数和 .map 函数 - 2

    我需要从json记录中获取一些值并像下面这样提取curr_json_doc['title']['genre'].map{|s|s['name']}.join(',')但对于某些记录，curr_json_doc['title']['genre']可以为空。所以我想对map和join()使用try函数。我试过如下curr_json_doc['title']['genre'].try(:map,{|s|s['name']}).try(:join,(','))但是没用。 最佳答案 你没有正确传递block。block被传递给参数括号外的方法

  10. ruby - 变量赋值后的 if 语句 - 有多常见？ - 2

    我最近与一位同事讨论了以下Ruby语法:value=ifa==0"foo"elsifa>42"bar"else"fizz"end我个人并没有看到太多这种逻辑，但我的同事指出，这实际上是一种相当普遍的Rubyism。我试着用谷歌搜索这个主题，但没有找到任何文章、页面或SO问题来讨论它，这让我相信这可能是一种非常实际的技术。然而，另一位同事发现语法令人困惑，而是将上面的逻辑写成这样:ifa==0value="foo"elsifa>42value="bar"elsevalue="fizz"end缺点是value=的重复声明和隐式elsenil的丢失，如果我们想使用它的话。这也感觉它与Ruby

随机推荐