当前位置 : 主页 > 编程语言 > 其它开发 >

不要使用短路逻辑编写 stl sorter 多条件比较

来源:互联网 收集:自由互联 发布时间:2022-06-29
搞 c++ 十多年了,居然被小小的 sorter 绊倒了,记录一下… 前言 最近工期紧、任务多,没有时间更新博客,就水一期吧。虽然是水,也不能太水,刚好最近工作中遇到一个 sorter 多条件
搞 c++ 十多年了,居然被小小的 sorter 绊倒了,记录一下… 前言

最近工期紧、任务多,没有时间更新博客,就水一期吧。虽然是水,也不能太水,刚好最近工作中遇到一个 sorter 多条件排序的问题,花费了半天时间来定位解决,就说说它吧。

背景

公司产品是一个跨端的数据传输 sdk,当下载资源时,会先从服务器拉取一批 peer,每个 peer 是包含要下载资源分片的 p2p 端,每个节点有一个序号,sdk 根据这个值从小到大排序后依次选取 peer 进行连接,序号是由服务器决定的,主要根据地域、连通率、带宽等决定的,可以简化为下面的 demo:

#include <stdio.h> 
#include <vector>
#include <string>
#include <algorithm>

struct PeerInfo
{
    std::string peerid; 
    std::string ip; 
    short port; 
    int begin; 
    int end; 
    int seq; 

    void print(void); 
};

void PeerInfo::print(void)
{
    printf ("peer %s: %d, %s:%d, %d-%d\n", 
            peerid.c_str(), seq, 
            ip.c_str(), port, begin, end); 
}

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        return lhs.seq < rhs.seq; 
    }
};

int main (void)
{
    std::vector<PeerInfo> vpi; 
    // init this vector by server response
    // ...
    std::sort (vpi.begin(), vpi.end(), PeerInfoSorter()); 
    for (auto it = vpi.begin(); it != vpi.end(); ++ it)
    {
        it->print(); 
    }
}

在下载过程中会向服务器请求多次,每批返回的 peer 都放在一个容器中排序,但是序号是基于批的,多个批次之间的 peer 如果仅按照 seq 排序的话,就会将前面批次旧的  peer 排在前面,从而导致一些新 peer 没有机会被用到,发生饥饿现象。

问题的产生

了解到这个情况后,采取了按批和序号同时排序的方案,即为 peer 增加一个  batch 字段用于记录批号,在排序时只有 batch 相同时才去比较 seq,代码类似下面这样:

struct PeerInfo
{
    std::string peerid; 
    std::string ip; 
    short port; 
    int begin; 
    int end; 
    int seq; 
    int batch; 

    void print(void); 
};

void PeerInfo::print(void)
{
    printf ("peer %s: %d-%d, %s:%d, %d-%d\n", 
            peerid.c_str(), batch, seq, 
            ip.c_str(), port, begin, end); 
}

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        return lhs.batch < rhs.batch || lhs.seq < rhs.seq; 
    }
};

当时的想法比较直接,先比较 batch,如果 batch 已经小了就直接短路返回结果;再比较 seq。看着逻辑没什么问题,但是运行起来后发现还是有旧批次的 peer 排在前面,以上面那个 demo 为例,制造一些测试数据:

    // ...
    vpi.push_back ({"1a2b", "10.0.1.29", 8001, 0, 16384, 1, 1}); 
    vpi.push_back ({"3c4d", "10.0.1.30", 8002, 16384, 32768, 2, 1}); 
    vpi.push_back ({"5e6f", "10.0.1.31", 8003, 8192, 24576, 1, 2}); 
    vpi.push_back ({"7a8b", "10.0.5.22", 8081, 32768, 49152, 2, 2}); 
    vpi.push_back ({"9c0d", "10.0.5.23", 8082, 49152, 65536, 1, 3}); 
    vpi.push_back ({"afec", "10.0.5.24", 8083, 0, 65536, 2, 3}); 

其中最后两个字段分别是 seq 与 batch 的初始值。执行后输出如下:

$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer afec: 3-2, 10.0.5.24:8083, 0-65536

 peer 1-2 排在 2-1 后面明显不是我们想要的,那是哪里出了问题呢?

问题的解决

看起来是 sorter 写的有问题,重新考察一下它的逻辑:

  • lhs.batch < rhs.batch 时,直接返回 true 并短路后面的条件,这是正确的
  • lhs.batch = rhs.batch 时,结果退化为 seq 之间的比较,也是正确的
  • lhs.batch > rhs.batch 时,结果退化为 seq 之间的比较,问题出在这里,此时应当直接返回 false

因此 sorter 正确的写法应该是这样:

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        if (lhs.batch != rhs.batch)
           return lhs.batch < rhs.batch; 

        return lhs.seq < rhs.seq; 
    }
};

前面的条件只要不相等就直接短路了,更正后输出正常了:

$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer afec: 3-2, 10.0.5.24:8083, 0-65536

现在回过头来看前面错误的代码,看上去它至少保证了 batch 的顺序,那么这是真的吗?稍微调整一下容器数据的初始顺序:

    vpi.push_back ({"9c0d", "10.0.5.23", 8082, 49152, 65536, 1, 3}); 
    vpi.push_back ({"afec", "10.0.5.24", 8083, 0, 65536, 2, 3}); 
    vpi.push_back ({"1a2b", "10.0.1.29", 8001, 0, 16384, 1, 1}); 
    vpi.push_back ({"3c4d", "10.0.1.30", 8002, 16384, 32768, 2, 1}); 
    vpi.push_back ({"5e6f", "10.0.1.31", 8003, 8192, 24576, 1, 2}); 
    vpi.push_back ({"7a8b", "10.0.5.22", 8081, 32768, 49152, 2, 2}); 

得到的输出打破了这一"幻觉":

$ ./peer
peer 1a2b: 1-1, 10.0.1.29:8001, 0-16384
peer 5e6f: 2-1, 10.0.1.31:8003, 8192-24576
peer 3c4d: 1-2, 10.0.1.30:8002, 16384-32768
peer 7a8b: 2-2, 10.0.5.22:8081, 32768-49152
peer 9c0d: 3-1, 10.0.5.23:8082, 49152-65536
peer afec: 3-2, 10.0.5.24:8083, 0-65536

很显然 1-2  排在了 2-1 之后。再分析之前的逻辑,当 lhs.batch > rhs.batch 时,结果是由 seq 决定的,所以完全可能出现上面的场景。而到底对哪些元素进行对比完全是由输入序列和对比算法决定的,怎么构造反例还真不好设计,只有当数据量大时才会表现的比较明显。

总结

再回头来看逻辑短路操作,如果写成下面形式:

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        return lhs.batch < rhs.batch || lhs.seq < rhs.seq; 
    }
};

则当 lhs.batch > rhs.batch 时不会短路,从而引发错误。如果写成下面的形式:

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        return lhs.batch < rhs.batch && lhs.seq < rhs.seq; 
    }
};

则当 lhs.batch < rhs.batch 时不会短路,也引发错误。

总结一下就是,我们需要返回 batch 或 seq 的 operator < 结果来作为比较结果,但是这个条件对于 || 和 &&  在一半的情况下是不会短路的,具体而言就是:

  • 使用 ||  逻辑短路时,lhs.batch < rhs.batch 得到满足,lhs.batch > rhs.batch 没有得到满足
  • 使用 && 逻辑短路时, lhs.batch > rhs.batch 得到满足,lhs.batch < rhs.batch 没有得到满足

那它们能得到全部满足吗?当短路发生时,lhs.batch < rhs.batch 这一条件有 true 和 false 两种情况需要返回,而短路逻辑 || 和 && 只能允许其中一种通过,所以答案是不能。除非可以预判只有其中一种条件发生 (只返回 true 或 false),然后有针对性的写 || 或 && 语句,不过那样的话这个字段也就没有参与比较的意义了。

最终结论就是,不要使用短路逻辑处理 sorter 多条件之间的判断。

后记

回到前面项目中,再给它加一点需求:服务器返回不同批次的 peer 可能重复,通过 peerid 可以去重,但当新 batch 中的 peer 在之前出现并连接过时,我们希望它的优先级变低,以保证未连接过的 peer 不发生饥饿现象。对于这样的需求,怎么改呢?想必大家心中已经有了答案,现在和正确答案对比一下吧:

struct PeerInfoSorter
{
    bool operator() (PeerInfo const& lhs, PeerInfo const& rhs) { 
        if (lhs.connect_cnt != rhs.connect_cnt)
            return lhs.connect_cnt < rhs.connect_cnt;

        if (lhs.batch != rhs.batch)
           return lhs.batch < rhs.batch; 

        return lhs.seq < rhs.seq; 
    }
};

其中 connect_cnt 新字段表示连接的次数,每连接一次增加一个计数,将这个条件放在最前面以便保证连接次数最少的 peer 排在最前面,只有当连接次数相同时 (新 peer 的 connect_cnt == 0),才对比 batch 与 seq。

举这个例子的目的是为了说明,sorter 多条件对比时,只要按重要性一个个排就可以了,你学会了吗?

上一篇:centos7 离线升级/在线升级操作系统内核
下一篇:没有了
网友评论