redis存储了40w条key=>value数据,value的值都是整形的
现在希望取value值最大的前200条,
请问除了把所有的全部取出来比较之外有没有其他更好的办法
1
vietor 2015-05-07 09:10:59 +08:00
StoreSet
|
3
zhsso 2015-05-07 09:21:23 +08:00
|
5
vietor 2015-05-07 09:39:34 +08:00
简单的说,是你的存储结构设计有问题,本来应该用StoredSet。现在的情况是,你先用笨方法。
|
6
zts1993 2015-05-07 09:47:37 +08:00 via Android
这个确实应该用SortedSet,虽然有点浪费空间。
|
7
fenzlie 2015-05-07 09:48:20 +08:00
如果你不怕其它查询请求被堵塞的话,可以用LUA脚本实现一个简易的冒排。冒200次就可以了。
|
8
mxm145 OP 感谢各位,看来还是只能用笨办法全部取出来,然后转成SortedSet
|
9
abscon 2015-05-07 10:43:06 +08:00
value是整形的?韩国哪个组合?(逃
|
10
cloud107202 2015-05-07 11:14:48 +08:00
1. 数据一定到取出来。如果不想这样,从redis层面优化只能换redis的数据结构了,这里不太熟
2. 在程序里有优化空间,使用一个size=200的最大堆,然后把所有取出的数据依次扔到这个堆里即可(比如Java中的PriorityQueue)。与朴素做法相比,避免掉对40w数据在内存中的占用与排序开销。 |
12
cloud107202 2015-05-07 11:29:25 +08:00
@cloud107202 第二点说的有点问题。数据入堆前,要先与堆顶元素判断,如果小于则pass 大于则入堆。这里容量可变的PriorityQueue并不合适,应该使用一个固定容量的结构,搜了一下有guava的MinMaxPriorityQueue
|
13
northisland 2015-05-07 12:14:58 +08:00
"
除了把所有的全部取出来比较之外有没有其他更好的办法 " 你不把所有数据遍历完,能做这件事儿。。。我想你肯定算命很准 |
14
northisland 2015-05-07 12:38:01 +08:00
N = 40w
M = 200 建立一个size为M的List,初始化全为-NAN 遍历一遍,大于List[M-1]的,按desc顺序插入List中 要做N次比较~和[M, N]次针对List的插入~~ Best: O( N+M×1 ) Worst: O( N+N×M ) Average: O( N+ ... ) 我想的方法,求指点 |
15
vietor 2015-05-07 13:22:30 +08:00
StoredSet 一般用于游戏的排行榜,普普通通就几百万的,没什么不妥的。
|
16
Magic347 2015-05-07 15:53:30 +08:00 1
一个经典的topK问题,这里N = 40w,K = 200,
全量排序再取topK的代价是O(NlgN),另外,全量排序的内存开销至少是O(N),不是最优解,可进一步优化。 这里因为要找前topK大,可以为此维护一个最小堆,堆的size始终维护为K, (1)初始化最小堆,顺序扫描所有N个值中的前K个,将K个入堆 (2)顺序扫描剩余N - K个值,发现比最小堆堆顶小时,不必入堆(必定不是topK大); 若发现比最小堆堆顶大时,弹出当前堆顶,并入堆这一新值。 以上时间代价O(NlgK),空间代价O(K) |
17
ETiV 2015-05-07 15:56:03 +08:00 via iPhone
为什么sorted被好几个人打成了stored……
|
18
sagrada 2015-05-07 16:48:28 +08:00
用redis命令scan,每次取一些值(默认10个左右),插入列表,如果列表<20,继续;如果>20,插入并排序,只保留前20;当scan返回0时,全部遍历完毕。
|
20
mxm145 OP @sagrada 昨天很急就没来得及看所有的回复了,用了最笨的办法全部取出然后存sorted set,耗时300秒,估计数据量更大的时候就需要其他办法了
|