pluribus第二课：利用三角形不等公式加速kmeans

pluribus第二课：利用三角形不等公式加速k-means

• 写在前面
• • 利用三角形不等公式加速k-means
  • c++并行的经验

本文主要的目的是记录自己实现pluribus的过程中，编程和程序执行过程中遇到的问题！希望能和大家分享经验，这篇文章仍然讲的是聚类牌组的阶段。poker ai的前期数据处理的难点在于基础数据庞大，河牌阶段的牌组就有上亿种可能，对于这种较大的数据，程序的效率成为成败的关键，方案不好很可能在计算数周乃至数月的时间，最开始尝试的时候，我使用的是python 计算聚类，发现计算emd距离较为耗时，大概为0.1ms每次，利用kmeans算法，如果迭1次需要计算200亿次emd，那么就需要至少200万秒，大概是24天。这是迭代一次的时间，如果等待它迭代收敛不知道要几个月，那么这个项目基本告别我们想要的答案了。本文做了两点优化了kmeans算法和提高程序执行效率。一是利用c++重头写算法，并尽可能不使用stl库，二是使用了并行充分利用多核的优势，三是last but most重要的利用三角形不等公式加速 k-means 。

利用三角形不等公式加速k-means

算法可以参考：https://blog.csdn.net/haimengao/article/details/29553767.
算法的c++实现可以参考：https://github.com/yiqingGit/AccKMeans

c++并行的经验

c++并行计算的话，我有过很多想法，想过用cuda来利用gpu并行的优势来提高程序执行的效率，但是执行过程中发现，cuda不熟悉的话，效率还不如直接cpu计算的快，最后还是放弃了使用cuda，而是利用openmp并行cpu进行计算，速度提高了不少8核运算的话迭代一次需要90分钟左右。openmp执行过程中也遇到过一个坑，比如openmp只在release模式下才能有并行的作用。