我一直在使用sinter来处理无序整数集的交集.有没有更快的交叉方式,因为我不介意事先排序(或执行任何其他预处理)？
编辑: 发现一些信息[这里] [1]
编辑2: 特定答案的赏金:比烧结更快的zinterstore？基准测试也很酷.
在列表中,列表的集合具有复杂度O(N),其中N是最小集合的基数.
使用SET(烧结/SINTERSTORE),如果有数据疏林/应保持RAM低(O(N*M) ),并使用BITSET(SETBIT/BITOP在所有其他情况下()O(N) .就像你编辑一个信息.
Redis BIT密钥操作具有复杂度O(N),其中N是最小密钥的基数.并且bitops具有基于CPU缓存的最佳执行速度(查看bitops.c源代码).所以这可能是绝对的赢家,你没有解析数据或者内存对你来说不重要(这里是 Redis中更多的字符串).
不要使用ZSET(zinterstore)你有简单的整数列表,并希望与它们相交.Redis中的排序集是存储密钥ziplist或skiplist内部编码的复杂结构 .最后一个用于存储排序分数,但密钥存储在其他结构中.在ZSET交叉点的情况下,比较SET总是很复杂:
ZSET交集:O(N*K)+ O(M*log(M))最坏的情况,N是最小的输入有序集,K是输入有序集的数量,M是结果有序集中的元素数.
SET交集:O(N*M)最坏的情况,其中N是最小集合的基数,M是集合的数量.实际上数学基础理论上是最小的.
SET使用dict/ intsetdata结构来存储数据,在你的情况下(无序整数集)intset将被使用.IntsetRedis中最大的内存保存结构.并且具有最佳的读取速度与ziplist(双链表,更多关于此数据结构内部)的比较.
| 归档时间： |
|
| 查看次数： |
1857 次 |
| 最近记录： |