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

对于有插入(范围插入)、 删除(范围删除)、 下标获取要求性能最好的数据结构是什么?

  •  
  •   wdc63 · 2022-06-30 16:38:55 +08:00 · 2085 次点击
    这是一个创建于 638 天前的主题,其中的信息可能已经有所发展或是发生改变。

    现在开发的项目对性能比较敏感,有一个列表结构频繁地会通过索引获取对象,通过下标或对象本身删除列表中的一个或多个对象,在列表中间某个位置、尾部插入一个或多个对象,请问能不能实现这种数据结构让每种方法都以 O(1)的方式进行。

    28 条回复    2022-07-01 23:40:46 +08:00
    THESDZ
        1
    THESDZ  
       2022-06-30 16:44:03 +08:00
    通过下标获取的,是数组吧?(这个问题应该是这么简单吧?)
    wdc63
        2
    wdc63  
    OP
       2022-06-30 16:46:13 +08:00
    @THESDZ 数组下标获取是 O1 ,但 InsertAt 、RemoveAt 、Remove(obj)都有 O(n)的时间开销,希望能后面几种方法也能以 O1 实现。
    MoYi123
        3
    MoYi123  
       2022-06-30 16:47:19 +08:00
    #include <ext/pb_ds/assoc_container.hpp>

    只能 O(logn),而且常数不小.
    xtreme1
        4
    xtreme1  
       2022-06-30 16:48:25 +08:00
    at() 和 removeAt() 应该没法同时 O(1)吧..
    cogear
        5
    cogear  
       2022-06-30 16:50:00 +08:00
    以我的见识来说,查询和插入都做到 O1 是不可能的。

    线性表(数组)查询可以 O1 。
    链表插入删除可以 O1 ,但是查询是 O(n)

    跳跃表?能在插入和查询之间做个平衡,O(logN),但是不能 O1 。
    wdc63
        6
    wdc63  
    OP
       2022-06-30 16:50:30 +08:00
    @MoYi123 能否解释一下这种算法,只会 C#、JAVA 和 Python ,C++看起来太费劲。
    wdc63
        7
    wdc63  
    OP
       2022-06-30 16:51:26 +08:00
    @cogear 能否做到查询 O1 ,插入 Ologn 。
    dcsuibian
        8
    dcsuibian  
       2022-06-30 16:54:12 +08:00
    哈希表,平均 O(1),最差 O(n)。。。
    wdc63
        9
    wdc63  
    OP
       2022-06-30 16:56:24 +08:00
    @dcsuibian hash 表没法用下标查询。
    Jooooooooo
        10
    Jooooooooo  
       2022-06-30 17:10:26 +08:00
    一个简单的思路出发点是用空间去换时间

    比如你维护多份相同的数据
    wdc63
        11
    wdc63  
    OP
       2022-06-30 17:11:22 +08:00
    @Jooooooooo 具体怎样能实现呢?
    Jooooooooo
        12
    Jooooooooo  
       2022-06-30 17:18:13 +08:00
    @wdc63 简单想了一下, 先用 linkedList, 这样范围的插入和删除就是 O(1) 的

    接下来问题是怎么找到 list 里对应的节点, 再用一个 map, 维护所有数据在上面 list 里的 index, 这样来了一个元素要查找能立马得知它在 list 哪个位置 (object -> index)

    接下来再有一个问题是, 怎么快速遍历到 list 对应的位置上, 再用一个 map, 记录所有 index 指向的节点, 比如第 0 个元素的指针, 第 1 个元素的指针

    这样有可能可以?? 不过细节得再想想. (在不考虑并发的前提下
    Jooooooooo
        13
    Jooooooooo  
       2022-06-30 17:19:19 +08:00
    @Jooooooooo 噢不行, index 没法维护...得再想想别的方案了.
    thinkershare
        14
    thinkershare  
       2022-06-30 17:19:23 +08:00
    @wdc63 没有这种数据结构, 不用找了
    cogear
        15
    cogear  
       2022-06-30 17:20:18 +08:00
    @wdc63 不能,查询做不到 O1 ,查询大约是二分查找的性能
    MoYi123
        16
    MoYi123  
       2022-06-30 17:21:58 +08:00
    @wdc63 有点问题, 这个不是很合适.
    jhdxr
        17
    jhdxr  
       2022-06-30 17:25:15 +08:00
    『通过索引获取对象,通过下标』
    如果你觉得索引和下标是不一样的。那你不是默认就只剩数组了,链表之类的哪来下标?
    seers
        18
    seers  
       2022-06-30 17:28:05 +08:00 via Android
    哈西链表
    MoYi123
        19
    MoYi123  
       2022-06-30 17:29:56 +08:00
    @wdc63


    看下这个库吧, from sortedcontainers import SortedList
    把注释删掉大约 600 行

    但是中间插入不好搞. 必须定期重新构建整个数据结构.

    from sortedcontainers import SortedList

    a = [0]


    def incr():
    a[0] += 1
    return a[0]


    s = SortedList()
    invert = {}
    # 向尾部插入单个
    idx = incr()
    s.add([idx, 'A'])
    invert['A'] = idx

    idx = incr()
    s.add([idx, 'B'])
    invert['B'] = idx

    # 用下标获取
    print(s[0]) # [1, 'A']
    print(s[1]) # [2, 'B']

    # 用下标删除
    s.pop(0)
    print(s)

    # 用对象本身删除
    idx = invert['B']
    idx = s.bisect_left([idx, 'B'])
    s.pop(idx)

    print(s)

    # 中间插入(先插入 2 个值)
    idx = incr()
    s.add([idx, 'A'])
    invert['A'] = idx

    idx = incr()
    s.add([idx, 'B'])
    invert['B'] = idx

    # 中间插入,在 A,B 间加一个 C
    # 这里比较尴尬, float 精度有限, 需要定期用 O(n)重新构建整个表
    left = s[0][0]
    right = s[1][0]
    s.add([(left + right) / 2, 'C'])
    print(s)
    sunny352787
        20
    sunny352787  
       2022-06-30 18:23:20 +08:00
    不是,等一下,不会又碰到了 AB 问题了吧?为啥一定要用下标呢?一般来说 hash 表就可以了啊,你这是个什么场景一定要用数组下标这种形式呢?
    aguesuka
        21
    aguesuka  
       2022-06-30 19:24:00 +08:00
    这段代码能 O(1) 地 [添加元素返回下标] , [通过下标获得元素], [通过下标删除元素].
    但是列表是无序的, 不能保证删除的幂等性.

    https://github.com/aguesuka/torrent-finder/blob/dev-nio2/src/main/java/cc/aguesuka/maguet/util/ArrayHeapSpace.java
    RicardoY
        22
    RicardoY  
       2022-06-30 20:53:05 +08:00
    块状链表这个场景应该蛮快的,如果数据量不是太大的话,复杂度比你要求的高一点
    hsfzxjy
        23
    hsfzxjy  
       2022-06-30 21:17:59 +08:00 via Android
    了解下跳表 skip list
    joetse
        24
    joetse  
       2022-06-30 23:15:19 +08:00 via Android
    只有完美哈希可以做到,前提是无限内存
    dqzcwxb
        25
    dqzcwxb  
       2022-06-30 23:32:55 +08:00
    世间安得双全法
    AllenHua
        26
    AllenHua  
       2022-07-01 09:43:18 +08:00 via iPhone
    优先保证插入和删除是 o(1) 应该就是链表为主的结构了,但又要保证查询是 o(1) 应该是做不到的,在查询上妥协一些应该是比较理想的方案
    qbqbqbqb
        27
    qbqbqbqb  
       2022-07-01 11:51:07 +08:00
    所有方法都 O(1)是不行的
    可以做到所有方法都是 O(log n)

    主要有两大类:
    * 跳跃表( skip list ),单次操作时间复杂度为期望 O(log n),实现较为简单
    * 带有 order statistics 的平衡二叉搜索树(包括 AVL, 红黑树, Splay 等多种实现),根据实现的不同,单次操作时间复杂度为期望、均摊或严格 O(log n),实现较为复杂
    wdc63
        28
    wdc63  
    OP
       2022-07-01 23:40:46 +08:00
    @qbqbqbqb
    @AllenHua
    @aguesuka
    @MoYi123
    感谢,已经放弃用下标取得对象的方法了,用下标的方法主要是为了方便前台用户交互部分获取数据的逻辑,现在就用 hashset ,改写了前台的逻辑,直接获取到对象而不是下标,再在逻辑部分进行处理。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2434 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 24ms · UTC 15:56 · PVG 23:56 · LAX 08:56 · JFK 11:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.