如何高效向列表添加唯一整数并维持其升序有序状态？

需求 #

需要实现一个动态构建的列表，逐个添加值时必须满足以下两个条件：

• 列表内所有元素唯一
• 列表始终保持升序排序

处理的数据规模为百万级整数，列表需要支持动态增删操作，要求实现方案具备极高的效率。

排除的低效方案 #

sorted(set(lst))完全不符合需求，原因如下：

1. 列表并非预先生成，后续需要频繁进行增删修改
2. 该方案本身效率极低，每次修改后重复执行排序和去重会消耗大量时间，无法处理百万级数据

尝试过的自定义实现及问题 #

我尝试过一种实现思路：同时维护一个与列表元素一致的set，通过set快速检查元素是否存在，仅当元素不存在时才添加到列表，同时更新两者以保证唯一性；通过二分查找计算插入索引来维持列表的有序性。

自定义实现代码如下：

from bisect import bisect

class Sorting_List:
    def __init__(self):
        self.data = []
        self.unique = set()

    def add(self, n):
        if n in self.unique:
            return

        self.unique.add(n)
        if not self.data:
            self.data.append(n)
            return
        if n > self.data[-1]:
            self.data.append(n)
        elif n < self.data[0]:
            self.data.insert(0, n)
        elif len(self.data) == 2:
            self.data.insert(1, n)
        else:
            self.data.insert(bisect(self.data, n), n)

但该方案存在明显缺陷：需要同时维护set和列表，内存利用率低，且时间效率并非最优。

性能测试结果 #

我针对不同实现方案做了多组性能测试：

成员检查性能对比 #

测试线性查找、二分查找与set成员检查的性能差异，测试代码：

from timeit import timeit

def test(n):
    setup = f'''from bisect import bisect
from random import choice
c = choice(range({n//2}, {n}))
numbers = list(range({n}))'''
    linear = timeit('c in numbers', setup) / 1e6
    binary = timeit('bisect(numbers, c) - 1 == c ', setup) / 1e6
    return linear, binary

测试结论：

• 列表的成员检查是线性查找，当元素数量≤12时速度优于二分查找，但元素数量增多后，性能远低于二分查找
• set的成员检查速度远快于二分查找，线性查找的速度最慢

具体测试数据：

In [188]: lst = list(range(256))

In [189]: s = set(lst)

In [190]: %timeit 199 in s
42.5 ns ± 0.946 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [191]: %timeit bisect(lst, 199)
159 ns ± 1.38 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)

In [192]: %timeit 199 in lst
2.53 µs ± 31.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

第三方有序集合库测试 #

测试对象为SortedSet和SortedList，测试数据为1048576个随机整数：

In [243]: numbers = random.choices(range(4294967295), k=1048576)

In [244]: sl = Sorting_List()

In [245]: ss = SortedSet()

In [246]: %timeit for i in numbers: ss.add(i)
306 ms ± 8.55 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [247]: %timeit for i in numbers: sl.add(i)
---------------------------------------------------------------------------
KeyboardInterrupt                         Traceback (most recent call last)
...

In [248]: sls = SortedList()

In [249]: s = set()

In [250]: %%timeit
     ...: for i in numbers:
     ...:     if i not in s:
     ...:         sls.add(i)
     ...:         s.add(i)
145 ms ± 3.24 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [251]: len(numbers)
Out[251]: 1048576

测试结论：

• 百万级元素场景下，自定义实现效率极低，甚至无法完成测试
• SortedSet和SortedList可正常处理百万级数据
• SortedList搭配set做成员检查是目前时间效率最高的方案，但内存利用率较低
• 单独使用SortedList做成员检查（内部为线性查找）效率极低：

In [252]: sls = SortedList()

In [253]: %%timeit
     ...: for i in numbers:
     ...:     if i not in sls:
     ...:         sls.add(i)
1.93 s ± 16.5 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

寻求更优方案 #

目前需要找到更高效的实现方案，可以使用第三方库的有序集合类，但必须保证在百万级数据场景下的性能。

内容的提问来源于stack exchange，提问作者Ξένη Γήινος