組み合わせのランキング（ランキング64.4）

Question

ランキングが高い順/ランキングのアルゴリズムの概要を示す https://stackoverflow.com/a/3143594/6589735 また、C++には具体的な実装があります。ここhttps://people.sc.fsu.edu/~jburkardt/cpp_src/combo/combo.cpp

私は、x64ハスウェルCPUにunsigned long longとしてエンコードランク/ unrank組み合わせを行うC++で非常に高速実装を必要としています。

私の試みは、改善が非常に必要です。

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

あなたは既にかなり上手いと思います。あなたはおそらくいくつかのポーカーをやっていますか？ （私はちょうどそれをするときに無名のアルゴリズムをgoogled）。いくつかの考慮事項：

1）2項目は、メモリアクセスよりも手作業で計算する方が速いかもしれませんが、長い間考えてみると、あなたのケースではほとんどありません。 、

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

3）binCoefは、計算中にL1キャッシュに収まるどれだけわからない：

2）ただし、コンパイラの知恵に応じて、あなたはprecalcテーブルの2D指標を算出してメモリアクセスを救うかもしれません検索スペースの半分を、条件C（n、k）== C（n、nk）で保存することができます。多分テストに値するでしょうか？

4）アンランクでは、内部のwhileループが最も遅い部分だと思います。 cardの小さな値を扱っている場合は、unrankのための完全な検索ソリューションを検討することもできます：C （52,5）= 260万ポーカーの手で、ほんの数MBのルックアップです。

6）同様に、map<int, long long> rankを使用してランクアルゴリズムを完全に置き換えることができます。バイナリツリーはルックアップのためにO（log N）であり、ハッシュマップはさらに優れたパフォーマンスを持つかもしれません。ちょうどそれをprecalc：あなたはcardの大きな値が必要になります場合は

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

、その後、ルックアップメソッドは動作しません、と私はあなたはかなりこだわって二分探索最適化だと思います。がんばろう！