请教排序问题

[mxm145]

redis存储了40w条key=>value数据，value的值都是整形的
现在希望取value值最大的前200条，
请问除了把所有的全部取出来比较之外有没有其他更好的办法

[vietor]

StoreSet

[mxm145]

@vietor 要把所有的取出来，然后存成set形式的？能不能说的详细点？redis不是很熟

[zhsso]

http://redis.cn/commands.html#sorted_set

[mxm145]

@zhsso 原始存的数据格式不是set的，是string。

[vietor]

简单的说，是你的存储结构设计有问题，本来应该用StoredSet。现在的情况是，你先用笨方法。

[zts1993]

这个确实应该用SortedSet，虽然有点浪费空间。

[fenzlie]

如果你不怕其它查询请求被堵塞的话，可以用LUA脚本实现一个简易的冒排。冒200次就可以了。

[mxm145]

感谢各位，看来还是只能用笨办法全部取出来，然后转成SortedSet

[abscon]

value是整形的？韩国哪个组合？（逃

[cloud107202]

1. 数据一定到取出来。如果不想这样，从redis层面优化只能换redis的数据结构了，这里不太熟
2. 在程序里有优化空间，使用一个size=200的最大堆，然后把所有取出的数据依次扔到这个堆里即可（比如Java中的PriorityQueue）。与朴素做法相比，避免掉对40w数据在内存中的占用与排序开销。

[wy315700]

@vietor

搭车问，StoreSet存40W数据的性能怎么样

[cloud107202]

@cloud107202 第二点说的有点问题。数据入堆前，要先与堆顶元素判断，如果小于则pass 大于则入堆。这里容量可变的PriorityQueue并不合适，应该使用一个固定容量的结构，搜了一下有guava的MinMaxPriorityQueue

[northisland]

"
除了把所有的全部取出来比较之外有没有其他更好的办法
"

你不把所有数据遍历完，能做这件事儿。。。我想你肯定算命很准

[northisland]

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+ ... )

我想的方法，求指点

[vietor]

StoredSet 一般用于游戏的排行榜，普普通通就几百万的，没什么不妥的。

[Magic347]

一个经典的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)

[ETiV]

为什么sorted被好几个人打成了stored……

[sagrada]

用redis命令scan，每次取一些值（默认10个左右），插入列表，如果列表<20，继续；如果>20，插入并排序，只保留前20；当scan返回0时，全部遍历完毕。

[mxm145]

@wy315700 我用朴素的办法存起来了，速度很不错

[mxm145]

@sagrada 昨天很急就没来得及看所有的回复了，用了最笨的办法全部取出然后存sorted set，耗时300秒，估计数据量更大的时候就需要其他办法了