Python 升序、查找高效的集合方案？

需要一个集合，要求：
1. 遍历时是升序
2. in 查找很高效

特点：
1. 初始化后，没遍历和 in 之外的其它操作，即初始化后不会更新
2. 初始化就是升序的
3. 大量的遍历和 in 操作
4. 集合内元素是唯一的

最早用的是 list ，缺点：in 低效
现在用 set ，缺点：遍历出来不是升序。刚刚发现非升序，在一些地方会有问题

希望方案很简单，最好是用标准库解决

一个可能的解决方案：bisect 。但用起来有点小麻烦
一个可能的解决方案，自己 new 一个类型，包装 list 和 set ，遍历用 list ，in 用 set

9 条回复 • 2024-09-17 15:42:41 +08:00

fox0001

3 天前 via Android

pandas

ho121

3 天前 via Android

OrderedDict

nagisaushio

3 天前 via Android

OrderedDict

NoOneNoBody

3 天前

in 低效的话，应该元素很多，那还是 pandas+1 ，遍历操作可以转为向量化

sagaxu

3 天前

from sortedcontainers import SortedSet

Sawyerhou

3 天前 via Android

如果 push, pop 等其他功能不特别复杂，自定义 list+set 很高效。

vituralfuture

2 天前 via Android

用内置的 dict ，cpython 的 dict 实现保证遍历出的键是升序的，in 也很高效。把你的数据做完键存进去，值随意选，不使用

Projection

2 天前

创建一个类并自定义 __contains__ 魔术方法，实现则使用 bisect 二分查找。根据这个思路找 GPT 生成了代码：

import bisect

class OrderedList:
def __init__(self, items):
# 确保列表有序
self.items = sorted(items)

# 自定义 in 操作，使用二分查找
def __contains__(self, item):
# 使用 bisect 模块进行二分查找
index = bisect.bisect_left(self.items, item)
# 检查查找到的索引是否在范围内，且对应元素是否与目标相等
return index < len(self.items) and self.items[index] == item

# 支持遍历
def __iter__(self):
return iter(self.items)

# 使用示例
ordered_list = OrderedList([10, 1, 7, 3, 5])

# 遍历
for item in ordered_list:
print(item) # 输出: 1 3 5 7 10 (有序)

# 使用自定义的 in 操作（使用二分查找）
print(7 in ordered_list) # 输出: True
print(6 in ordered_list) # 输出: False

johnsona

1 天前 via iPhone

sorted 不就好了吗 3.7 以上的 dict 便利顺序同插入顺序