redis:最快的交叉方式是什么？

Question

我一直在使用sinter，它做无序整数集的交集。如果我不介意事先进行排序(或者执行任何其他预处理)，那么是否有更快的方法来处理交集？

编辑：在这里找到了一些信息

EDIT2: Bounty的具体答案是:锌库比烧结矿快吗？标杆也会很酷。

Answer 1

快速回答

理论上，列表的交集具有复杂性O(N)，其中N是最小集的基数。

使用集(烧结矿/正弦波)如果有稀疏数据/应该保持内存低(O(N*M))，在所有其他情况下(O(N) )使用BITSET(SETBIT/BITOP)。就像编辑一个信息一样。

BITSET

Redis位密钥运算具有复杂性O(N)，其中N是最小键的基数。并且基于CPU缓存(查看bitops.c源代码)，bitops具有非常好的执行速度。因此，这可以是绝对赢家，在您没有分散的数据或内存不重要对您(这是更多关于字符串在Redis)。

ZSET对SET (锌库对烧结矿)

不要使用ZSET (zinterstore)，您有一个简单的整数列表，并希望将它们相交。Redis中的排序集是一个复杂的结构，其密钥存储在ziplist或skiplist内部编码中。最后一个用来存储排序分数，但键存储在其他结构中。在ZSET交集中，比较集总是非常复杂的：

ZSET相交：O(N * K) + O(M * log(M))最坏的情形是N是最小的输入排序集，K是输入排序集的个数，M是得到的排序集中的元素数。 集交：O(N * M)最坏情况，其中N是最小集的基数，M是集合数。实际上理论上是基于数学的最小值。

SET使用dict / intset数据结构来存储数据，在您的情况下(无序整数集)将使用intset。内存最多的Intset在Redis中保存了结构。与ziplist (双链接列表，这里有更多关于数据结构内部的信息。)相比，具有最佳的读取速度。