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

如何设计一个 arraylike 数据结构,支持 O(1) 的按索引访问和 O(1) 的按索引删除.

  •  
  •   littleMaple · 2021-01-07 21:25:05 +08:00 · 2131 次点击
    这是一个创建于 1416 天前的主题,其中的信息可能已经有所发展或是发生改变。

    用代码来作为例子,假设我们的数据结构名为 MagicArray:

    magic_array = MagicArray("How are you", "I am find", "Thank you", "And you")
    
    print(magic_array[2])  # 这一行应该打印 "Thank you",且该行的运行时间应该与 magic_array 的长度无关,或者至少“摊还地”无关.
    
    magic_array.remove(1)  # 这一行的运行时间应该与 magic_array 的长度无关,或者至少“摊还地”无关.
    
    print(magic_array[2])  # 这一行应该打印 "And you",且该行的运行时间应该与 magic_array 的长度无关,或者至少“摊还地”无关.
    

    如果我们无法设计出这样的数据结构,我们如何形式证明它不可能存在?如果确实不可能存在,我们可以设计出的最接近它的最快的数据结构能够有多快?

    22 条回复    2021-01-08 03:17:53 +08:00
    xupefei
        1
    xupefei  
       2021-01-07 21:28:06 +08:00 via iPhone
    链表+位置到节点的哈希表。
    这题算是 leetcode 中等难度。
    php8
        2
    php8  
       2021-01-07 21:28:42 +08:00 via Android
    咱 php 数组插入和删除都是 O(1)滴,还能当 map 用,难怪被公认是最好的语言
    xupefei
        3
    xupefei  
       2021-01-07 21:33:10 +08:00 via iPhone
    @xupefei 不过我这个办法删除比 O1 复杂,最坏情况下是 On 。
    用 jumplist 可能会更好
    littleMaple
        4
    littleMaple  
    OP
       2021-01-07 21:33:51 +08:00
    @xupefei #1 删除操作的时候维护「位置映射到节点的哈希表」就需要 O(n) 的复杂度吧?例如 magic_array.remove(1) 操作运行的时候,2->"Thank you" 和 3->"And you" 这两个映射就需要更新成 1->"Thank you" 和 2->"And you"。
    xupefei
        5
    xupefei  
       2021-01-07 21:36:17 +08:00 via iPhone   ❤️ 1
    最好的办法应该是用 rope,能做到 logn 复杂度
    sunkai0609
        6
    sunkai0609  
       2021-01-07 22:06:26 +08:00
    php 的数组
    sunkai0609
        7
    sunkai0609  
       2021-01-07 22:07:54 +08:00
    @sunkai0609 请无视我
    hanxiV2EX
        8
    hanxiV2EX  
       2021-01-07 22:10:50 +08:00 via Android   ❤️ 1
    跳跃表,redis 的 zset

    只能做到 lgn
    love
        9
    love  
       2021-01-07 23:18:15 +08:00 via Android
    这和 map 用整数做 key 有什么区别?
    mxT52CRuqR6o5
        10
    mxT52CRuqR6o5  
       2021-01-07 23:41:16 +08:00 via Android
    @php8 我 google 了一下 php 的 array_splice 可并不是 O(1)而是 O(offset+length)啊
    mxT52CRuqR6o5
        11
    mxT52CRuqR6o5  
       2021-01-07 23:42:31 +08:00 via Android   ❤️ 1
    这个问题一两句应该证明不了,书上也许会有答案
    raaaaaar
        12
    raaaaaar  
       2021-01-07 23:55:06 +08:00 via Android   ❤️ 1
    结合链表的增删和数组的查改优点就是跳表,所以不可能存在你说得这种上界都是 O(1) 的。
    查找操作最好的就是利用内存的随机存取特点,但是要实现删除操作就必然和随机存取冲突,因为删除节点内存就变了,地址也变了,要不影响随机存取,内存肯定要移动的。
    littleMaple
        13
    littleMaple  
    OP
       2021-01-08 00:05:26 +08:00
    @love #9 因为要求是 arraylike,例如如果删除了第三个元素,第四个元素至最后一个元素对应的索引都要相应的减一.
    littleMaple
        14
    littleMaple  
    OP
       2021-01-08 00:10:04 +08:00
    @raaaaaar #12 确实如此,直观上来说 O(1) access 和 O(1) remove 不可能同时满足,但是若是 amortized O(1) access 和 amortized O(1) remove 呢?放宽一点要求之后不知道能不能同时满足.
    php8
        15
    php8  
       2021-01-08 00:50:39 +08:00 via Android
    @mxT52CRuqR6o5 是我理解有误,没有考虑到删除之后下标要依次挪一格
    wangxiyu191
        16
    wangxiyu191  
       2021-01-08 01:51:39 +08:00   ❤️ 2
    没要求插入的时间和空间复杂度,钻个空子。可以在初始化 /插入时就生成好一次或多次删除后可能达到的所有的状态。这样插入和删除就都能做 O(1) 了。
    wangxiyu191
        17
    wangxiyu191  
       2021-01-08 01:53:12 +08:00
    @wangxiyu191 上面最后一句打错。“这样插入和删除就都能做 O(1) 了” -》 “这样查询和删除就都能做 O(1) 了”
    sunnybird
        18
    sunnybird  
       2021-01-08 02:14:16 +08:00 via Android
    算法核心思想,空间换时间
    shiji
        19
    shiji  
       2021-01-08 02:42:37 +08:00 via iPhone
    @littleMaple Hashmap 的核心不就是 array 么。 又没有必要说 array 不能留空,必须一字排开
    littleMaple
        20
    littleMaple  
    OP
       2021-01-08 03:02:04 +08:00
    @wangxiyu191 #16 你居然能想到这样暴力的方案 XD 而且居然是对的.
    littleMaple
        21
    littleMaple  
    OP
       2021-01-08 03:03:43 +08:00
    @shiji #19 我说的 arraylike 不是这个意思,你可以看我写在标题里的那一段代码,这个数据结构应该要能够满足那里描述的行为.
    ericls
        22
    ericls  
       2021-01-08 03:17:53 +08:00 via iPhone
    那就让插入贵一点嘛
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2828 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 07:26 · PVG 15:26 · LAX 23:26 · JFK 02:26
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.