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

大佬们,遇到个有意思的问题,看看有解吗

  •  
  •   rizon ·
    othorizon · 2019-04-26 16:44:26 +08:00 · 3001 次点击
    这是一个创建于 1798 天前的主题,其中的信息可能已经有所发展或是发生改变。

    表里存储的数据如下

    name | order
    -----|------
    A | 1
    B | 2
    C | 3

    然后比如我要改变 C 的顺序,放到 A 和 B 之间,那么最直接的方式是修改为

    name | order
    ------|------
    A | 1
    B | 3
    C | 2

    但是有没有办法可以做到,尽量只修改 C 的 order 值就可以来改变顺序呢?
    也就是说有没有一种可以表达顺序的方式,能够做的只修改自身的值就可以改变顺序

    为了表达更清晰我举个例子,比如这样
    name | order
    ------|------
    A | 1
    B | 2
    C | 1.5

    但是这种对半除的方式,会导致无限小数的问题,不够严谨,感觉也不太合适。
    ps. v2 的 markdown 不支持表格唉

    第 1 条附言  ·  2019-04-26 23:50:52 +08:00
    总结一下大家说的。
    预留空间是一种比较可行的方案,也是我之前的想的方案之一,空间不够就洗牌,重新分配。
    再有就是 2 分法,或者 2 分法的变形,其实也没必要真的对半分,只要在两个值之间找到一个值就可以了,所以这和预留空间其实我觉得是一样的。

    另外其实我还有个想法,就是用链表,这种的不满足我的前提,但是可以尽可能少的去修改数据,移动一个对象的位置只需要修改两个指针也就是更新两条数据就行了,也算是一个折中的方案吧。
    26 条回复    2019-04-27 08:15:48 +08:00
    Vegetable
        1
    Vegetable  
       2019-04-26 17:00:20 +08:00
    设置优先级.优先级不严格与顺序对应.
    A 1
    B 2
    C 3

    把 C 改成 1.1,自然就排在 AB 之间了.
    我们业务上某些展示页面的排序就是这么做的.有好处也有坏处.我个人是参考了 scrapy 的中间件优先级设置.
    geelaw
        2
    geelaw  
       2019-04-26 17:03:24 +08:00 via iPhone   ❤️ 1
    在有限的 domain 上不存在,在稠密的 domain 上可以(例如用字典序排序的不限长字符串)。

    如果你不需要快速的排序,你可以用链表,这样把元素删除和插入都只需要常数个修改。
    index90
        3
    index90  
       2019-04-26 17:07:05 +08:00
    C.order = (A.order+B.order)/2?
    rizon
        4
    rizon  
    OP
       2019-04-26 17:11:46 +08:00
    @Vegetable #1 你把 C 改成 1.1 之后那如果又把 B 移动到 A 和 C 之前怎么做呢? B 要改成什么呢
    rizon
        5
    rizon  
    OP
       2019-04-26 17:12:48 +08:00
    @index90 #3 就像我正文说的,这样会出现除不开的情况。你又不能四舍五入,那样会导致有可能出现重复的值
    index90
        6
    index90  
       2019-04-26 17:16:08 +08:00
    不管是不是四舍五入,即使除得开,也会出现重复值问题。
    index90
        7
    index90  
       2019-04-26 17:18:10 +08:00
    A 1
    B 3
    C 6
    D 7
    第一次,把 C 放到 A,B 之间
    第二次,把 D 放到 A,B 之间

    哦?难道你的题目是,把元素放到任意两个相邻的元素之间?
    Raymon111111
        8
    Raymon111111  
       2019-04-26 17:32:55 +08:00
    为什么一定要限的这么死 感觉这种方案把自己逼到一个没有特别好解决方案的境地

    直接顺序是定死的 1 2 3 4 5, 然后每个顺序对应谁可以变, 实现简单, 逻辑也合乎直觉
    HuasLeung
        9
    HuasLeung  
       2019-04-26 17:44:39 +08:00
    看看能不能换个思路来玩:
    要把 C 放在 A 和 B 的中间,不动 C,而是对 B 进行变大操作。
    HuasLeung
        10
    HuasLeung  
       2019-04-26 17:47:10 +08:00
    @HuasLeung 如 B=(C+D)/2 取整
    jmc891205
        11
    jmc891205  
       2019-04-26 17:47:38 +08:00
    用分数来表示 order 好了
    存两个 integer 一个是分子一个是分母
    ziding
        12
    ziding  
       2019-04-26 17:47:43 +08:00
    我这边是这么玩的,初始化的时候 100 为基数,调整顺序的时候( A+B )/2,如果找不到,对 B 的值进行增大处理,增大的时候,(大于 B 的+小于 B 的)/2+50,绝大部分情况不用调整很多的顺序就能找到空隙,一旦找不到,这次调整会比较慢,因为要调整较多的记录数,但是这次调整完了,后续的就会很快了。
    A 100
    B 200
    C 300
    HuasLeung
        13
    HuasLeung  
       2019-04-26 17:51:34 +08:00
    @HuasLeung 上面的"B=(C+D)/2 取整",当我没说过…… D 不一定存在,除非能定义一个比较合理的基数
    Vegetable
        14
    Vegetable  
       2019-04-26 17:53:35 +08:00
    @rizon 不存在的,这种设计在一开始就预留了足够的顺序,所以我们的排序是根据权重倒序排列,100 起步.而且这个是手动维护的,不存在一张纸能对折几次的问题.
    同样我也说了这个有缺点.
    pancl
        15
    pancl  
       2019-04-26 17:57:48 +08:00
    加多一列...
    zilaijuan
        16
    zilaijuan  
       2019-04-26 18:00:45 +08:00 via Android
    马一下。楼上说的都还是求和除以 2,楼主一开始就不考虑这个方法了
    aa6563679
        17
    aa6563679  
       2019-04-26 18:06:29 +08:00 via iPhone
    就是这样一路除下去,直到字段太长就进行一次重排
    tidyoux
        18
    tidyoux  
       2019-04-26 18:09:10 +08:00
    顺序信息放到内存中,在内存中更新顺序信息,定期持久化到数据库中。
    gamexg
        19
    gamexg  
       2019-04-26 18:19:16 +08:00
    100
    200
    300

    我见过很多都是这样做的,一般调整空间足够。
    不够时再重新生成顺序。
    jhdxr
        20
    jhdxr  
       2019-04-26 18:32:06 +08:00
    @zilaijuan 上面已经有人提到了,存分数,而不是小数
    zilaijuan
        21
    zilaijuan  
       2019-04-26 20:16:07 +08:00 via Android
    @jhdxr 个人感觉存分数会增加计算量,影响排序的效率
    ccpp132
        22
    ccpp132  
       2019-04-26 20:36:11 +08:00 via Android
    分数也要挂的,分母越来越大,除不了很多次就存不下了。学点信息论就知道这没什么方法,除 2 每次就减少一半可用来表示的内容。不管你存成什么形式
    saulshao
        23
    saulshao  
       2019-04-26 22:52:54 +08:00
    这个正如楼上的总结,根本就没什么一劳永逸的方法。完全取决于你面临的具体问题,然后设计具体的方案。
    opengps
        24
    opengps  
       2019-04-26 23:30:07 +08:00
    要不排序列就换成小数点吧,或者加大默认数值间隔
    xuanbg
        25
    xuanbg  
       2019-04-27 08:14:01 +08:00
    先预留空间,插到哪个后面就哪个的序号+1。空间内位置冲突则空间内重排,空间满则后面若干空间(可按实际情况设置 2-10 )全部重排。一般每个空间预留 10000 就足够了,很少重排。多空间重排基本只是摆设,从来用不到。
    xuanbg
        26
    xuanbg  
       2019-04-27 08:15:48 +08:00
    @xuanbg 插前面就序号-1
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   3305 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 13:49 · PVG 21:49 · LAX 06:49 · JFK 09:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.