麻将的C++之旅（七）性能与初步调优

凤兮丶梦兮

至此，C++混合查表法的核心业务逻辑已经初步设计完了，是时候检验综合查胡法的运行效率了，我完成了回朔法和混合查表法的C++一般实现，然后以14张一手牌为标准测试用例，做了一下性能测试。
测试用例生成的核心算法是组合数列表算法C(N,M)；M取14，是指模拟一手牌清一色的牌，N选取的不同是指模9确定每个数字的张数，比如N设为18，就是从18个数中取14个，如果下标大于8，则模9取余的，作为这个数字的第二张，以此类推。组合数列表为获取的组合数总数，不过不同的组合数，可能生成牌的No-Num表是一样的，因此需要整理后获得有效牌型。所有的有效牌型都是符合麻将逻辑合理的（每个数字的张数不超过4），通过用不同的算法找出有效牌型中能胡牌的数量，就可以得出不同算法的执行效率。为了减少干扰，两种算法都获得最终的胡牌的牌型数据，但是不再显示输出详细内容，仅仅记录个数。

N	M	组合数列表	有效牌型数	胡牌数	回溯法(万笔/秒)	混合查表法(万笔/秒)
18	14	3060	414	73	0.29	48.22
21	14	116280	3123	362	0.34	109.06
24	14	1961256	11538	1322	0.36	87.42
27	14	20058300	30276	4106	0.37	97.54

两种算法殊途同归，对于相同的有效牌找到的胡牌数量完全一致，说明两种算法的编写业务逻辑正确（这是对比的基准点）。回朔法的平均处理能力基本稳定在0.34万笔/秒，而混合查表法的平均处理能力为85.56万笔/秒，是回溯法执行效率的约250倍，初步达到了设计目标。
但是，作为一个老码农，对查表法的执行效率并不满意，因为我初步算了一下，单纯的unordered_map在3万左右的数据量时，查询效率近乎500万笔秒，混合查表法效率损失好大，于是开始了调优之旅
一、设计目标

提升混合查表法的执行效率，达到个人满意的目标。
二、分析

仔细分析NNCode和OKTable的Value的编码设计，核心其实都是不同进制整数的组合，NNCode是9个8进制数和1个16进制数的组合，Value是5个16进制数的组合，因此使用联合（Union）结构，性能应该可以有大幅提升，再结合以前的代码经验，C的位操作效率远高于其他的算数运算，因此初步确定了以下几个调优目标：
1、 Union实现Value的编解码
2、 用位操作替代NNCode的数组，
三、实现

首先调整Value的编码设计，对于不靠和七对牌型的设计不变，把普通牌型（3n+2）的AB设计从4+5*4，改为5*4+4，用Union实现，重载下标运算符，下标[0-4]存放顺/刻和对的数字（n0、n1、n2、n3、D），下标[5]四位刻顺标识，对应n0-n4，0/1：刻/顺。用uint32_t与uint8_t的联合，实现Value数据的处理。
union MJ_U_UnionNo{ //用4位存放数字的联合
  uint32_t Code32;
  uint16_t Code16[2];
  uint8_t  Code8[4];

  MJ_U_UnionNo(uint32_t I):Code32(I){}
  uint8_t  operator[](int i) { return (i&1)?(((Code8[i>>1])&(0xF0))>>4):((Code8[i>>1])&0xF);};
  const uint8_t  operator[](int i) const{ return (i&1)?(((Code8[i>>1])&(0xF0))>>4):((Code8[i>>1])&0xF);}
  inline void seti8 (int i, int N){ Code8[i>>1]=(Code8[i>>1]&((i&1)?0xF:0xF0))|(N&0xF)<<((i&1)?4:0);} //第i个Code8置为N的后4位
};
其次，用一个uint32_t替代原先的结构体设计，NN编码和解码均通过位操作实现，其次重载运算符简化后续编码。
class MJ_C_NNCode32{
private:
  const int B1[9]={4,7,10,13,16,19,22,25,28};
  const uint32_t M1[9]={ 0x7fffff8f,0x7ffffc7f,0x7fffe3ff,0x7fff1fff,0x7ff8ffff,0x7fc7ffff,0x7e3fffff,0x71ffffff,0xfffffff};
  uint32_t NNCode;
  uint8_t c;
  
  inline const uint8_t geti8(int i) const {return (NNCode&~M1)>>B1;}
  bool const AddCheck(const MJ_C_NNCode32 *N, const MJ_C_NNCode32 *C=NULL) const;
  void enCodeNN(uint32_t I);
  void enCodeNN(uint *NN, int Len=9); //NN表编码，9个int数组，同一花色
  void enCodeComb(uint32_t Comb, int Mask); //组合数编码
  void enCodeID(vector<uint> &IDs, int M); //IDs 编码，指定花色；
public:
  MJ_C_NNCode32(uint32_t I=0):NNCode(I){} //以Code初始化

  bool seti8 (int i, int N);//第i个8进制赋值
  bool addi8(int i, int c=1); //第i个8进制数+C;
  const inline uint32_t getCode() const {return NNCode;}

  //重载下标运算符，i为[0,8]，返回指定的数值；i>9返回NNcode,
  uint32_t operator[](const int i) { return (i<9)?((NNCode&~M1)>>B1):NNCode; }
  const uint32_t operator[](const int i) const { return (i<9)?((NNCode&~M1)>>B1):NNCode; }
  //重载强制类型转换运算符 （int）
  operator int() {return NNCode;}
  operator unsigned int() {return NNCode;}
  //重载+、+=运算符，
  const MJ_C_NNCode32 & operator+=(const MJ_C_NNCode32 &C);
  MJ_C_NNCode32  operator+ (const MJ_C_NNCode32 &C) const;
  //重载=运算符，实现直接赋值；
  const MJ_C_NNCode32 & operator= (const MJ_C_NNCode32 &C) { this->NNCode=C.getCode(); return *this; }
  const MJ_C_NNCode32 & operator= (const uint32_t C) { this->NNCode=C; return *this; }
  //重载<<=，标识NN编码
  const MJ_C_NNCode32 & operator<<= (uint32_t C) { this->enCodeNN(C); return *this; }
  const MJ_C_NNCode32 & operator<<= (vector<uint> &A) { this->enCodeNN(&A[0],(int)A.size()); return *this; }
  const MJ_C_NNCode32 & operator<<= (vector<int> &A) { this->enCodeNN((uint *)&A[0],(int)A.size()); return *this; }
  //重载&=，标识Comb编码 pair<uint32_t Comb, uint32_t M>,Comb组合数，M为模数3个4位组成，(PX<<8|HS<<4|m)
  const MJ_C_NNCode32 & operator&= (pair<uint32_t, int> C) { this->enCodeComb(C.first,C.second); return *this; }
  //重载&=，标识ID编码 pair<vector<uint> IDs, int M> ,IDs:牌ID编码，M为模数，2个4位组成，(isNID<<4|HS)
  const MJ_C_NNCode32 & operator|= (pair<vector<uint>, int> C) { this->enCodeID(C.first, C.second); return *this; }
  
  inline const uint32_t deCodeNum() const { return NNCode&0xF;} //获得B区数量
  inline const uint32_t deCodeNN()  const { return NNCode>>4;} //解码出NN表，返回9个8进制
  int  deCodeNN(uint *N); //解码出NN表，返回9个int数组,返回总张数
  uint8_t deCodeID(MJ_C_UniBase64 &UC); //解码出非0的ID表
  uint8_t deCodeID(MJ_C_UniBase64 &UC, MJ_E_PaiXing PX);
  bool  deCodeID(uint *CardsNo, MJ_E_PaiXing PX); //按照牌型，解码出非0的为ID数组，返回是否解码成功
  
  void Show(string s="");
};
四、结果
经过以上的优化，混合查表法的平均处理能力提升到约148万笔/秒，提升近了72%。

柳述

楼下的接上