python - 用于在已排序数据中快速插入和随机访问的数据结构
问题描述
p = random_point(a,b)
#random_point() returns a tuple/named-tuple (x,y)
#0<x<a 0<y<b
if centers.validates(p):
centers.insert(p)
#centers is the data structure to store points
在centers
数据结构中,所有x
和y
坐标都存储在两个单独的排序(升序)列表中,一个是 for x
,另一个是 for y
。in 中的每个节点都x
指向对应的y
,反之亦然,这样它们就可以单独排序并且仍然保持 pair 属性:centers.get_x_of(y)
和centers.get_y_of(x)
我在数据结构中需要的属性:
- 快速插入,在已排序的数据中(最好是 log n)
- 随机访问
- 分别对 x 和 y 进行排序,而不会丢失对属性
最初我想使用 simple Lists
,并使用Binary search
来获取插入任何新元素的索引。但我发现,可以使用像 AVL 或 B-trees 这样的自平衡树来改进它。x
我可以为和分别制作两棵树y
,每个节点都有一个额外的指针,可以从 x-tree 节点指向 y-tree 节点。
但我不知道如何在这些树中构建随机访问功能。该函数centers.validate()
尝试插入x
& y
,并对相邻元素进行一些检查,这需要随机访问:
def validate(p):
indices = get_index(p)
#returns a named tuple of indices to insert x and y, Eg: (3,7)
condition1 = func(x_list[indices.x-1], p.x) and func(x_list[indices.x+1], p.x)
condition2 = func(y_list[indices.y-1], p.y) and func(y_list[indices.y+1], p.y)
#func is some mathematical condition on neighboring elements of x and y
return condition1 and condition2
在上面的函数中,我需要访问x
&y
数据结构的相邻元素。我认为在树中实现这一点会使它复杂化。是否有任何数据结构组合可以实现这一目标?我正在用 Python 写这个(如果有帮助的话)
解决方案
具有 2 个 dict 的类,其中的键是另一个 dict 的键,该 dict 包含与此 dict 中的值相关的值。它需要为每个字典维护一个列表,以便在调用它时调用该字典的元素(您当前的字典值)。您将需要二进制或其他有效排序来对每个 dict 进行操作以进行插入,尽管它实际上会使用该 dict 的顺序列表来查找每个中点键,然后检查该键中的值。
推荐阅读
- ios - 应用程序为模拟器而不是物理设备编译
- java - 如何使用 USACO 的文件测试输入输出
- python-3.x - 如何在python中添加一个字段以根据其他列返回值?
- mongodb - 如何将存储在 mongodb 中的颜色应用于 ejs 模板?
- javascript - 为什么我的模块函数的 Jest 间谍在另一个模块中使用,在测试后一个模块的函数时没有被调用?
- python - 如何在 postgreSQL 中构建表
- java - 如何在场景构建器中添加我的自定义布局管理器?
- visual-c++ - rust 编译时 1 字节的结构成员对齐 (rustflags)
- javascript - 使用 For 循环在数组中递归搜索
- mysql - 如何在父查询案例语句中使用子查询的结果