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

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

  •  
  •   wdc63 · 40 天前 · 1417 次点击
    这是一个创建于 40 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

    只能 O(logn),而且常数不小.
    xtreme1
        4
    xtreme1  
       40 天前
    at() 和 removeAt() 应该没法同时 O(1)吧..
    cogear
        5
    cogear  
       40 天前
    以我的见识来说,查询和插入都做到 O1 是不可能的。

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

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

    比如你维护多份相同的数据
    wdc63
        11
    wdc63  
    OP
       40 天前
    @Jooooooooo 具体怎样能实现呢?
    Jooooooooo
        12
    Jooooooooo  
       40 天前
    @wdc63 简单想了一下, 先用 linkedList, 这样范围的插入和删除就是 O(1) 的

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

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

    这样有可能可以?? 不过细节得再想想. (在不考虑并发的前提下
    Jooooooooo
        13
    Jooooooooo  
       40 天前
    @Jooooooooo 噢不行, index 没法维护...得再想想别的方案了.
    thinkershare
        14
    thinkershare  
       40 天前
    @wdc63 没有这种数据结构, 不用找了
    cogear
        15
    cogear  
       40 天前
    @wdc63 不能,查询做不到 O1 ,查询大约是二分查找的性能
    MoYi123
        16
    MoYi123  
       40 天前
    @wdc63 有点问题, 这个不是很合适.
    jhdxr
        17
    jhdxr  
       40 天前
    『通过索引获取对象,通过下标』
    如果你觉得索引和下标是不一样的。那你不是默认就只剩数组了,链表之类的哪来下标?
    seers
        18
    seers  
       40 天前 via Android
    哈西链表
    MoYi123
        19
    MoYi123  
       40 天前
    @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  
       40 天前
    不是,等一下,不会又碰到了 AB 问题了吧?为啥一定要用下标呢?一般来说 hash 表就可以了啊,你这是个什么场景一定要用数组下标这种形式呢?
    aguesuka
        21
    aguesuka  
       40 天前
    这段代码能 O(1) 地 [添加元素返回下标] , [通过下标获得元素], [通过下标删除元素].
    但是列表是无序的, 不能保证删除的幂等性.

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

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