c++ - 组合的快速排名/取消排名(64 位)

Question

有这么棒的帖子 https://stackoverflow.com/a/3143594/6589735 概述排名/取消排名组合的算法。 此外，还有 C++ 中的具体实现，例如这里https://people.sc.fsu.edu/~jburkardt/cpp_src/combo/combo.cpp

我需要一个非常快的 C++ 实现，它在 x64 Haswell CPU 上将排名/非排名组合编码为 unsigned long long。

我的尝试非常需要改进。

unsigned long long rank(unsigned long long comb, int card)
{
    unsigned long long rank = 0;

    for (int i = 1; i <= card; i++)
    {
        unsigned long index;
        _BitScanForward64(&index, comb);
        rank += binCoef[index][i];  // the binCoef table is precomputed
        comb &= (comb - 1);
    }

    return rank;
}

unsigned long long unrank(unsigned long long rank, int card)
{
    unsigned long long comb = 0;

    unsigned long long m = rank;
    for (int i = card - 1; i >= 0; i--)
    {
        int p = i;
        while (binCoef[p + 1][i + 1] <= m)
            p++;
        m -= binCoef[p][i + 1];
        comb |= (1 << p);
    }

    return comb;
}

Answer 1

我认为您已经走得很好了。也许你在做一些与扑克相关的事情？ (我只是在谷歌上搜索了不排名算法)。一些注意事项:

1) 对于少量项目，手动计算二项式可能比内存访问更快，但考虑到 long long，这在您的情况下极不可能。

2) 但是，根据编译器的智慧，您可以通过计算预计算表的二维索引来节省内存访问:

binCoef[(index<<6) + i]; // instead of binCoef[index][i]

3) 不确定 binCoef 有多好在计算期间适合 L1 缓存，但您可能会使用身份 C(n, k) == C(n, n-k) 节省一半的查找空间，但需要一个额外的条件成本。也许值得测试？

4) 在 unrank 中，我认为内部 while 循环是最慢的部分。有两个明显的优化:要么实现二进制搜索来定位 p，要么...

5) 如果您正在处理 card 的小值，您甚至可以考虑使用成熟的查找解决方案来取消排序:有 C(52, 5) = 260 万手牌，这只是几 MB 的查找。

6) 同样，您可能会看到 map<int, long long> rank可以用来完全取代排名算法。二叉树的查找复杂度为 O(log N)， HashMap 可能具有更好的性能。只需预先计算它:

map<long long, int> rank5;
for(int i=0; i<N; i++) rank5[unrank(i, 5)] = i; //ranks of 5 card hands

如果您需要较大的 card 值，那么查找方法将不起作用，而且我认为您几乎无法使用二进制搜索优化。祝你好运!