首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  Redis

请教排序问题

  •  
  •   mxm145 · 2015-05-07 09:06:47 +08:00 · 3126 次点击
    这是一个创建于 1504 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

    20 回复  |  直到 2015-05-08 16:04:28 +08:00
        1
    vietor   2015-05-07 09:10:59 +08:00
    StoreSet
        2
    mxm145   2015-05-07 09:16:43 +08:00
    @vietor 要把所有的取出来,然后存成set形式的?能不能说的详细点?redis不是很熟
        3
    zhsso   2015-05-07 09:21:23 +08:00
        4
    mxm145   2015-05-07 09:29:16 +08:00
    @zhsso 原始存的数据格式不是set的,是string。
        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   2015-05-07 09:54:31 +08:00
    感谢各位,看来还是只能用笨办法全部取出来,然后转成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数据在内存中的占用与排序开销。
        11
    wy315700   2015-05-07 11:16:06 +08:00
    @vietor

    搭车问,StoreSet存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时,全部遍历完毕。
        19
    mxm145   2015-05-08 14:40:46 +08:00
    @wy315700 我用朴素的办法存起来了,速度很不错
        20
    mxm145   2015-05-08 16:04:28 +08:00
    @sagrada 昨天很急就没来得及看所有的回复了,用了最笨的办法全部取出然后存sorted set,耗时300秒,估计数据量更大的时候就需要其他办法了
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2362 人在线   最高记录 5043   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 21ms · UTC 15:23 · PVG 23:23 · LAX 08:23 · JFK 11:23
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1