0、背景
在我们舆情分析系统里，有一个功能是文章搜索，返回相似性去重后的文章，这里比较耗时的是一个相似性去重的功能，就是在返回的数据集里将相似的文章去掉。
如果只是去重也还好，关键是还要进行分页，这就意味着需要计算去重后的总数。
1、原来的方案
对每一篇文章循环处理，用文章的simhash值去ES查找相似的文章ID，然后从剩余的集合里去掉这些ID，这样处理完成之后，就会得到一个去重完之后的数据集。
我一看这里，这样那行呀，要是原始数据集有一万篇文章，这个功能的极端情况就得查询一万次ES！平均可能也得查询5000次，这难怪要几分钟才出结果了，而且ES也难受呀。
赶紧指导同事进行优化吧。
2、第一个优化版本
因为输入数据集里，每个文章的simhash值已经是算好了的，那我们完全可以不查ES，而直接计算两个向量的距离呀。于是把算法的思路跟同事说清楚，其实也很简单，就是对于每个文章，直接和后面的文章相比较，如果相似度达到我们的阈值，则从集合中剔除。
同事蹭蹭蹭用三重循环的纯python就实现了，迫不及待想看到奇迹，上线测试环境，刷新。。。好久好久都没有出结果。以为是其他问题影响了，再刷新一次，还是一样。
看到日志里打印的初始集合的文章数量，大概1.7万，瞬间明白了，因为这个过滤算法的时间复杂度是N平方，这得算好几亿次相似度。。。不慢也不行呀！
3、第二个优化版本
我还是不死心，因为一次查询要查询几千次ES，就这想怎么优化效果都是有限的，也无法达到客户的预期，别说秒级了，想降到一分钟以下都不容易。
用纯python写，需要三重循环，这些循环能否转为矩阵运算呢？
显然是可以的，于是不死心的自己直接实现了一个版本：
代码语言：javascript复制print(len(data))
start = time.time()
new_data = []
for item in data:
simhash, article_id = list(item['simhash']), item['id']
# 不足64位的前面补0，文章id放到第一个值
new_data.append([article_id] ['0']*(64-len(simhash)) simhash)
np_data = np.array(new_data)
print(np_data.shape)
thr = 0.85 * 64
results = []
while np_data.shape[0] > 1:
curr_row = np_data[0]
np_data = np_data[1:]
counts = np.count_nonzero(curr_row == np_data, axis=1)
results.append((curr_row[0], np_data[counts > thr].shape[0] 1))
np_data = np_data[counts <= thr]
if len(np_data) > 0:
results.append((np_data[0][0], 1))
for item in results:
print(item)
print('time: ', time.time() - start, ' len: ', len(results))思路跟纯python的其实是一样的，只是将里面的两重循环转成了矩阵运算，充分利用numpy的特性。
在一个1.7k的测试集上效果是可以的，本机测试只要0.4秒左右，比原来使用ES要快，关键是还不用占用宝贵的ES资源。
但是如果数据量更大行不行呢？于是简单的将输入数据重复了10次（这犯了一个错误），效果还是很快，1秒以下，让人满意。
奇迹要来了的幸福就在眼前。
然而，现实的打脸来得太快，一万多的数据一跑，loading标志就在那里一直转呀转。。。转了10多分钟才停下来！
我不得不仔细想一想，这中间发生了什么？ES的几千次查询都比你快？
其实就算矩阵运算再快，那也得现算，而ES中的simhash是经过特殊处理的，有底层的倒排索引支撑，找相似的时候并不需要在全局里搜索（相当于提前剪枝）。
当数据集数量大于一定值时，基于ES倒排索引的提前剪枝的效率就体现出来的。当然，这个算法也不是一无是处，当数据量比较小的时候，这个算法可以比ES更高效。
4、总结
做算法优化，不能头脑发热撸起袖子就干，而是要先考虑清楚算法的时间复杂度和空间复杂度，如果多想一想，其实第一个版本的优化根本不会发生。
结合ES的特性来考虑，第二种情况的结果应该也是可以预见的。
后面还比较了很多聚类的算法，其实情况都类似，再好聚类算法也需要现算，这就避免不了时间延迟的问题，还不如用原来的方案。
在写这个文章的时候，就这个问题想到，算法最耗时的其实是要计算去重后的文章总数用于分页，但是这个分页是否真的是必须存在的呢？
我觉得这并不一定是要存在的，去重后的总数其实也并没有太多的作用，只要知道是否还有下一页就可以了。如果这个客户可以接受（在这个功能上，我觉得做一点小取舍，换来性能的大提升完全是非常值得的），这个时间延迟马上就能降到百毫秒的级别。
所以，解决问题并不能总是想着技术手段，有时非技术手段更直接有效。
