这是一个创建于 3523 天前的主题，其中的信息可能已经有所发展或是发生改变。
redis存储了40w条key=>value数据，value的值都是整形的
现在希望取value值最大的前200条，
请问除了把所有的全部取出来比较之外有没有其他更好的办法
 |
1
vietor 2015-05-07 09:10:59 +08:00
StoreSet
|
 |
3
WDsUO7HnS2Na1DFC 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秒，估计数据量更大的时候就需要其他办法了
|
Select Language