在保持列表排序的同时将唯一整数附加到列表的最快方法是什么？

Question

我需要将值一一附加到现有列表中，同时始终保持以下两个条件：

\n

\n

• 列表中的每个值都是唯一的

  \n
\n

• 列表始终按升序排序

  \n
\n

\n

这些值都是整数，而且数量巨大（字面意思是数百万，毫不夸张），并且列表是动态构建的，根据变化的条件添加或删除值，我真的需要一种非常有效的方法来做到这一点这。

\n

sorted(set(lst))不符合解决方案的资格，因为首先列表不是预先存在的，之后我需要对其进行变异，解决方案本身效率不高，为了维持上述两个条件，我需要在之后重复低效的方法每个突变，这是不切实际的，并且需要花费难以想象的时间来处理数百万个数字。

\n

一种方法是维护一个与列表具有相同元素的集合，并使用该集合进行成员资格检查，并且仅在集合中没有元素时才将元素添加到列表中，然后将相同的元素添加到两个位置同一时间。这保持了独特性。

\n

为了保持顺序，请使用二分搜索来计算所需的插入索引并在索引处插入元素。

\n

我想出的示例实现：

\n

from bisect import bisect\n\nclass Sorting_List:\n    def __init__(self):\n        self.data = []\n        self.unique = set()\n\n    def add(self, n):\n        if n in self.unique:\n            return\n\n        self.unique.add(n)\n        if not self.data:\n            self.data.append(n)\n            return\n        if n > self.data[-1]:\n            self.data.append(n)\n        elif n < self.data[0]:\n            self.data.insert(0, n)\n        elif len(self.data) == 2:\n            self.data.insert(1, n)\n        else:\n            self.data.insert(bisect(self.data, n), n)\n

\n

我对这个解决方案不满意，因为我必须维护一个集合，这不是内存效率最高的解决方案，而且我认为这不是最节省时间的解决方案。

\n

我做了一些测试：

\n

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

\n

from bisect import bisect\n\nclass Sorting_List:\n    def __init__(self):\n        self.data = []\n        self.unique = set()\n\n    def add(self, n):\n        if n in self.unique:\n            return\n\n        self.unique.add(n)\n        if not self.data:\n            self.data.append(n)\n            return\n        if n > self.data[-1]:\n            self.data.append(n)\n        elif n < self.data[0]:\n            self.data.insert(0, n)\n        elif len(self.data) == 2:\n            self.data.insert(1, n)\n        else:\n            self.data.insert(bisect(self.data, n), n)\n

\n

因此，列表的成员资格检查是使用线性搜索完成的，通过逐一迭代列表并执行相等性检查，这效率很低，但对于少量元素（n <= 12）优于二分搜索，并且对于较大元素要慢得多金额。

\n

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

\n

并且set成员资格检查比二分搜索快，二分搜索比线性搜索快得多：

\n

In [182]: [test(i) for i in range(1, 24)]\nOut[182]:\n[(3.1215199967846275e-08, 9.411800000816583e-08),\n (4.0730200009420514e-08, 9.4089699909091e-08),\n (5.392530001699925e-08, 1.0571250005159527e-07),\n (5.4071999969892203e-08, 1.111615999834612e-07),\n (5.495569994673133e-08, 1.3055420003365725e-07),\n (7.999380002729595e-08, 1.2215890001971274e-07),\n (6.739119999110698e-08, 1.1633279989473522e-07),\n (1.1775600002147258e-07, 1.2142769992351532e-07),\n (9.138470003381372e-08, 1.1602859990671277e-07),\n (1.212503999704495e-07, 1.2919300002977253e-07),\n (1.4093979995232076e-07, 1.1543070001062005e-07),\n (1.3911779993213713e-07, 1.1900339997373521e-07),\n (1.641304000513628e-07, 1.2721199996303767e-07),\n (2.2550319996662438e-07, 1.3572790008038284e-07),\n (2.0048839994706214e-07, 1.2690539995674044e-07),\n (2.0169020001776515e-07, 1.3345349999144673e-07),\n (1.482249000109732e-07, 1.2819399998988957e-07),\n (1.777580000925809e-07, 1.2856919993646443e-07),\n (1.5940839995164425e-07, 1.2710969999898224e-07),\n (2.772621000185609e-07, 1.4048079994972795e-07),\n (2.014727999921888e-07, 1.4225799997802823e-07),\n (2.851358000189066e-07, 1.3718699989840387e-07),\n (2.607858000556007e-07, 1.4413580007385463e-07)]\n

\n

我们怎样才能设计出更快的方法呢？

\n

---

\n

我很清楚Pythonset是无序的，对sets进行排序会得到lists。但也许有一些外部库提供有序集，如果有的话我不知道它们并且我没有使用它们。

\n

只要它们具有高性能，使用此类有序集的解决方案就受到欢迎，但我并不是在寻求建议，因此请不要因此而关闭问题。

\n

然而，有序集仅满足第一个标准，仅保持唯一性，并且我还需要保持有序性。

\n

list这里只是术语，在普通的 Python 中list是唯一有序的可变序列。欢迎其他数据类型。

\n

关于SQLite，我还没有测试过内存瞬态数据库，但是对于基于本地HDD的数据库，I/O延迟是很多毫秒，这是不可接受的。

\n

---

\n

我刚刚进行了另一项测试：

\n

In [183]: test(256)\nOut[183]: (2.5505281999940053e-06, 1.7594210000243037e-07)\n

\n

看来我的自定义实现至少与SortedSet合理数量的数据一样高效，我需要更有效的方法。

\n

对于一百万个元素，我的方法确实变得非常低效，而SortedSet和SortedList两者都保持能力。

\n

现在看来，成员资格检查的SortedList加号set是最省时的方法，但显然内存效率不高，就像我的自定义实现一样。但我的自定义实现似乎优于SortedSet内存效率较高的实现。

\n

---

\n

SortedList通过一一添加 2^20 个元素进行测试，同时通过使用容器本身进行成员资格检查来保持元素的唯一性：

\n

In [188]: lst = list(range(256))\n\nIn [189]: s = set(lst)\n\nIn [190]: %timeit 199 in s\n42.5 ns \xc2\xb1 0.946 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 10,000,000 loops each)\n\nIn [191]: %timeit bisect(lst, 199)\n159 ns \xc2\xb1 1.38 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 10,000,000 loops each)\n\nIn [192]: %timeit 199 in lst\n2.53 \xc2\xb5s \xc2\xb1 31.7 ns per loop (mean \xc2\xb1 std. dev. of 7 runs, 100,000 loops each)\n

\n

（numbers定义如上）

\n

测试清楚地表明SortedList成员资格检查很慢，正如怀疑的那样，它使用线性搜索。

\n

Answer 1

我喜欢数据而不是猜测，所以我介绍了@Kelly Bundy 建议的方法

from bisect import bisect
from sortedcontainers import SortedList, SortedSet


class Sorting_List:
    # The Original
    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)


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

    def add(self, n):
        if n in self.unique:
            return
        self.unique.add(n)
        self.data[bisect(self.data, n) : 0] = (n,)


class SortedListWrapper:
    def __init__(self):
        self.data = SortedList()
        self.unique = set()

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

import random

from performance_measurement import run_performance_comparison


def original(values):
    x = Sorting_List()
    for value in values:
        x.add(value)
    return x.data


def kelly(values):
    x = Sorting_List_Kelly()
    for value in values:
        x.add(value)
    return x.data


def sortedset(values):
    x = SortedSet()
    for value in values:
        x.add(value)
    return x


def sortedlist(values):
    x = SortedListWrapper()
    for value in values:
        x.add(value)
    return x


def generate_lists(N):
    return [random.sample(range(N), N)]


data_size = [1000, 2000, 3000, 4000, 5000, 10000, 20000, 30000, 40000, 50000]

approaches = [original, kelly, sortedset, sortedlist]

run_performance_comparison(approaches, data_size, setup=generate_lists)

特别是对于小问题实例，@Kelly Bundy 的改进方法优于SortedList包装器SortedSet和sortedcontainers.

分析代码：

import timeit
import matplotlib.pyplot as plt
from typing import List, Dict, Callable

from contextlib import contextmanager


@contextmanager
def data_provider(data_size, setup=lambda N: N, teardown=lambda: None):
    data = setup(data_size)
    yield data
    teardown()


def run_performance_comparison(approaches: List[Callable],
                               data_size: List[int],
                               setup=lambda N: N,
                               teardown=lambda: None,
                               number_of_repetitions=5, title='N'):
    approach_times: Dict[Callable, List[float]] = {approach: [] for approach in approaches}

    for N in data_size:
        with data_provider(N, setup, teardown) as data:
            for approach in approaches:
                approach_time = timeit.timeit(lambda: approach(*data), number=number_of_repetitions)
                approach_times[approach].append(approach_time)

    for approach in approaches:
        plt.plot(data_size, approach_times[approach], label=approach.__name__)

    plt.xlabel(title)
    plt.ylabel('Execution Time (seconds)')
    plt.title('Performance Comparison')
    plt.legend()
    plt.show()