问C++优化if/else条件

EN

让我以这样一个事实作为开场白:我将在这里概述的内容是脆弱的，并且不是完全可移植的--但是在正确的环境下(与您指定的差不多)，我可以合理地确定它应该能够正常工作。

它依赖的一点是IEEE浮点数经过精心设计，因此如果您将它们的位模式视为整数，它们仍然会按正确的顺序排序(对一些事情进行模运算，如NaNs，这实际上没有“正确的顺序”)。

为了利用这一点，我们要做的就是打包条目，这样构成我们的key的两个部分之间就没有填充了。然后，我们确保整个结构与8字节的边界对齐。我还将_id更改为int32_t，以确保它保持32位，即使在64位系统/编译器上也是如此(这几乎肯定会产生用于此比较的最佳代码)。

然后，我们转换结构的地址，这样我们就可以将浮点数和整数一起视为一个64位整数。由于您使用的是小端处理器，为了支持这一点，我们需要将较低有效部分( id)放在第一位，将较高有效部分( cost)放在第二位，因此当我们将它们视为64位整数时，浮点部分将成为最高有效位，而整数部分将成为较低有效位：

struct __attribute__ ((__packed__)) __attribute__((aligned(8)) Entry {
  // Do *not* reorder the following two fields or comparison will break.
  const int32_t _id;
  const float _cost;

  // some other vars

    Entry(long id, float cost) : _cost(cost), _id(id) {} 
};

然后我们有了丑陋的小比较函数：

bool operator<(Entry const &a, Entry const &b) { 
   return *(int64_t const *)&a < *(int64_t const *)&b;
}

一旦我们正确地定义了结构，比较就变得相当简单:只需获取每个结构的前64位，并将它们作为64位整数进行比较。

最后，给出一些测试代码，以确保它对某些值正确工作：

int main() { 
    Entry a(1236, 1.234f), b(1234, 1.235f), c(1235, 1.235f);

    std::cout << std::boolalpha;

    std::cout << (b<a) << "\n";
    std::cout << (a<b) << "\n";
    std::cout << (b<c) << "\n";
    std::cout << (c<b) << "\n";
    return 0;
}

至少对我来说，这会产生预期的结果：

false
true
true
false

现在，一些可能的问题:如果这两个项在它们之间重新排列，或者结构的任何其他部分放在它们之前或之间，比较肯定会中断。其次，我们完全依赖于每个剩余32位的项的大小，所以当它们连接在一起时，它们将是64位。第三，如果有人从结构定义中删除了__packed__属性，我们可能会在_id和_cost之间填充，再次破坏比较。同样，如果有人删除了对齐的(8)，代码可能会失去一些速度，因为它试图加载不与8字节边界对齐的8字节量(在另一个处理器上，这可能会完全失败)。编辑: Oops。@rici提醒了我一些我本想在这里列出的东西，但是忘记了:只有当_id和cost都是正数时，它才能正确工作。如果_cost为负，比较将会因为IEEE浮点使用带符号的幅度表示而变得混乱。如果_id为负数，则其符号位将被视为数字中间的正常位，因此负_id将显示为大于正_id。

总而言之:这是脆弱的。这一点是毫无疑问的。尽管如此，它应该是相当快的--特别是如果您使用的是64位编译器，在这种情况下，我希望比较结果是两次加载和一次比较。长话短说，您所处的位置可能根本无法使比较本身更快--您所能做的就是尝试并行执行更多操作，优化内存使用模式等。

我很难相信：

a)比较函数在30秒内运行1.8亿次

和

cpu b)比较函数占用

时间的25%

都是真的。即使是Core 2 Duo也应该能够轻松地在不到一秒的时间内运行1.8亿次比较(毕竟，声称它可以做大约12000 MIPS，如果这实际上意味着什么的话)。因此，我倾向于相信，通过分析软件进行比较，还存在其他因素。(例如，为新元素分配内存。)

但是，您至少应该考虑这样一种可能性: std::set不是您要查找的数据结构。如果在实际需要排序值(或最大值，甚至是最大值)之前执行数百万次插入，那么最好将这些值放入一个向量中，这是一种在时间和空间上都更便宜的数据结构，并按需对其进行排序。

如果您因为担心冲突而实际需要set，那么您可以考虑使用unordered_set，它稍微便宜一些，但不如向量便宜。(正是因为向量不能保证您的唯一性。)但老实说，看看这种结构定义，我很难相信唯一性对你来说很重要。

“基准”

在我的小核心i5笔记本电脑上，我运行了几个测试，将1000万个随机的唯一条目(只有两个比较字段)插入到std::set和std::vector中。最后，我对向量进行排序。

我这样做了两次；一次是用一个随机生成器，它可能会产生独特的成本，另一次是用一个生成器，它会产生两种不同的成本(这应该会使比较变慢)。1000万次插入导致的比较结果略多于OP报告的结果。

              unique cost         discrete cost
           compares     time    compares     time
set       243002508    14.7s   241042920    15.6s   
vector    301036818     2.0s   302225452     2.3s

为了进一步隔离比较时间，我使用std::sort和std::partial_sort重做了向量基准测试，使用了10个元素(本质上是对前10名的选择)和10%的元素(即一百万)。更大的partial_sort的结果让我大吃一惊--谁会想到对一个向量的10%进行排序会比对所有向量进行排序都要慢--但它们表明算法成本比比较成本要重要得多：

                     unique cost         discrete cost
                  compares     time    compares     time
partial sort 10   10000598     0.6s    10000619     1.1s
partial sort 1M   77517081     2.3s    77567396     2.7s
full sort        301036818     2.0s   302225452     2.3s   

结论:比较时间越长，但容器操作占主导地位。在总共52秒的计算时间内，1000万组插入的总成本是显而易见的。一千万次向量插入的总成本就不那么明显了。

小纸条，值得用

我从那一小段汇编代码中得到的一件事是，通过将成本设置为float，并没有节省任何东西。它实际上为浮点数分配了8个字节，所以你没有节省任何内存，而且你的cpu进行单次浮点数比较的速度不会比单次双精度比较快。只是说说而已(也就是说，提防过早优化)。

Downvoter，介意解释一下吗？

一种简单的解决方案是预先计算一个排序标识符，该标识符由最重要的成本和其余部分的id组成。

例如，

struct Entry
{
    double cost_;
    long id_;
    long long sortingId_;

  // some other vars

    Entry( double cost, float id )
        : cost_( cost ), id_( id ), sortingId_( 1e9*100*cost + id )
    {} 
};

根据您对取值范围的假设调整sortingId_值。

然后，现在只需对sortingId_进行排序。

或者，作为同一想法的变体，如果您不能对数据做出适当的假设，那么可以考虑专门为memcmp准备数据。

对于更高级别的解决方案，请记住std::set::insert有一个带有提示参数的重载。如果您的数据已经按近乎有序的顺序排列，这可能会严重减少对比较器函数的调用次数。

你可能会考虑一个std::unordered_set是否足够了？例如，是否需要按排序顺序列出数据。或者排序只是std::set元素插入的内部内容。

最后，对于其他读者( OP已经明确表示他知道这一点)，请记住测量。