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

请教排序问题

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

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

    20 条回复    2015-05-08 16:04:28 +08:00
    vietor
        1
    vietor  
       2015-05-07 09:10:59 +08:00
    StoreSet
    mxm145
        2
    mxm145  
    OP
       2015-05-07 09:16:43 +08:00
    @vietor 要把所有的取出来,然后存成set形式的?能不能说的详细点?redis不是很熟
    zhsso
        3
    zhsso  
       2015-05-07 09:21:23 +08:00
    mxm145
        4
    mxm145  
    OP
       2015-05-07 09:29:16 +08:00
    @zhsso 原始存的数据格式不是set的,是string。
    vietor
        5
    vietor  
       2015-05-07 09:39:34 +08:00
    简单的说,是你的存储结构设计有问题,本来应该用StoredSet。现在的情况是,你先用笨方法。
    zts1993
        6
    zts1993  
       2015-05-07 09:47:37 +08:00 via Android
    这个确实应该用SortedSet,虽然有点浪费空间。
    fenzlie
        7
    fenzlie  
       2015-05-07 09:48:20 +08:00
    如果你不怕其它查询请求被堵塞的话,可以用LUA脚本实现一个简易的冒排。冒200次就可以了。
    mxm145
        8
    mxm145  
    OP
       2015-05-07 09:54:31 +08:00
    感谢各位,看来还是只能用笨办法全部取出来,然后转成SortedSet
    abscon
        9
    abscon  
       2015-05-07 10:43:06 +08:00
    value是整形的?韩国哪个组合?(逃
    cloud107202
        10
    cloud107202  
       2015-05-07 11:14:48 +08:00
    1. 数据一定到取出来。如果不想这样,从redis层面优化只能换redis的数据结构了,这里不太熟
    2. 在程序里有优化空间,使用一个size=200的最大堆,然后把所有取出的数据依次扔到这个堆里即可(比如Java中的PriorityQueue)。与朴素做法相比,避免掉对40w数据在内存中的占用与排序开销。
    wy315700
        11
    wy315700  
       2015-05-07 11:16:06 +08:00
    @vietor

    搭车问,StoreSet存40W数据的性能怎么样
    cloud107202
        12
    cloud107202  
       2015-05-07 11:29:25 +08:00
    @cloud107202 第二点说的有点问题。数据入堆前,要先与堆顶元素判断,如果小于则pass 大于则入堆。这里容量可变的PriorityQueue并不合适,应该使用一个固定容量的结构,搜了一下有guava的MinMaxPriorityQueue
    northisland
        13
    northisland  
       2015-05-07 12:14:58 +08:00
    "
    除了把所有的全部取出来比较之外有没有其他更好的办法
    "

    你不把所有数据遍历完,能做这件事儿。。。我想你肯定算命很准
    northisland
        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+ ... )

    我想的方法,求指点
    vietor
        15
    vietor  
       2015-05-07 13:22:30 +08:00
    StoredSet 一般用于游戏的排行榜,普普通通就几百万的,没什么不妥的。
    Magic347
        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)
    ETiV
        17
    ETiV  
       2015-05-07 15:56:03 +08:00 via iPhone
    为什么sorted被好几个人打成了stored……
    sagrada
        18
    sagrada  
       2015-05-07 16:48:28 +08:00
    用redis命令scan,每次取一些值(默认10个左右),插入列表,如果列表<20,继续;如果>20,插入并排序,只保留前20;当scan返回0时,全部遍历完毕。
    mxm145
        19
    mxm145  
    OP
       2015-05-08 14:40:46 +08:00
    @wy315700 我用朴素的办法存起来了,速度很不错
    mxm145
        20
    mxm145  
    OP
       2015-05-08 16:04:28 +08:00
    @sagrada 昨天很急就没来得及看所有的回复了,用了最笨的办法全部取出然后存sorted set,耗时300秒,估计数据量更大的时候就需要其他办法了
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   3369 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 10:29 · PVG 18:29 · LAX 02:29 · JFK 05:29
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.