这是一个创建于 910 天前的主题，其中的信息可能已经有所发展或是发生改变。
现在开发的项目对性能比较敏感，有一个列表结构频繁地会通过索引获取对象，通过下标或对象本身删除列表中的一个或多个对象，在列表中间某个位置、尾部插入一个或多个对象，请问能不能实现这种数据结构让每种方法都以 O(1)的方式进行。
 |
1
THESDZ 2022-06-30 16:44:03 +08:00
通过下标获取的，是数组吧？（这个问题应该是这么简单吧？）
|
 |
2
wdc63 OP @THESDZ 数组下标获取是 O1 ，但 InsertAt 、RemoveAt 、Remove(obj)都有 O(n)的时间开销，希望能后面几种方法也能以 O1 实现。
|
 |
3
MoYi123 2022-06-30 16:47:19 +08:00
#include <ext/pb_ds/assoc_container.hpp>
只能 O(logn),而且常数不小. |
 |
4
xtreme1 2022-06-30 16:48:25 +08:00
at() 和 removeAt() 应该没法同时 O(1)吧..
|
 |
5
cogear 2022-06-30 16:50:00 +08:00
以我的见识来说，查询和插入都做到 O1 是不可能的。
线性表（数组）查询可以 O1 。 链表插入删除可以 O1 ，但是查询是 O(n) 跳跃表？能在插入和查询之间做个平衡，O(logN)，但是不能 O1 。 |
 |
8
dcsuibian 2022-06-30 16:54:12 +08:00
哈希表，平均 O(1)，最差 O(n)。。。
|
 |
10
Jooooooooo 2022-06-30 17:10:26 +08:00
一个简单的思路出发点是用空间去换时间
比如你维护多份相同的数据 |
|
11
wdc63 OP @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 个元素的指针 这样有可能可以?? 不过细节得再想想. (在不考虑并发的前提下 |
|
13
Jooooooooo 2022-06-30 17:19:19 +08:00
@Jooooooooo 噢不行, index 没法维护...得再想想别的方案了.
|
 |
14
thinkershare 2022-06-30 17:19:23 +08:00
@wdc63 没有这种数据结构, 不用找了
|
 |
17
jhdxr 2022-06-30 17:25:15 +08:00
『通过索引获取对象，通过下标』
如果你觉得索引和下标是不一样的。那你不是默认就只剩数组了，链表之类的哪来下标？ |
 |
18
seers 2022-06-30 17:28:05 +08:00 via Android
哈西链表
|
|
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) |
 |
20
sunny352787 2022-06-30 18:23:20 +08:00
不是，等一下，不会又碰到了 AB 问题了吧？为啥一定要用下标呢？一般来说 hash 表就可以了啊，你这是个什么场景一定要用数组下标这种形式呢？
|
 |
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 |
 |
22
RicardoY 2022-06-30 20:53:05 +08:00
块状链表这个场景应该蛮快的，如果数据量不是太大的话，复杂度比你要求的高一点
|
 |
23
hsfzxjy 2022-06-30 21:17:59 +08:00 via Android
了解下跳表 skip list
|
 |
24
joetse 2022-06-30 23:15:19 +08:00 via Android
只有完美哈希可以做到，前提是无限内存
|
 |
25
dqzcwxb 2022-06-30 23:32:55 +08:00
世间安得双全法
|
 |
26
AllenHua 2022-07-01 09:43:18 +08:00 via iPhone
优先保证插入和删除是 o(1) 应该就是链表为主的结构了，但又要保证查询是 o(1) 应该是做不到的，在查询上妥协一些应该是比较理想的方案
|
 |
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)，实现较为复杂 |
|
28
wdc63 OP |
Select Language