在Python中将项目插入到排序列表中

Question

我正在创建一个类,其中一个方法将新项插入到排序列表中.该项目将插入已排序列表中的已更正(已排序)位置.我不能使用比其他任何内置列表函数或方法[],[:],+,和len虽然.这是让我感到困惑的部分.

解决这个问题的最佳方法是什么？

Answer 1

使用bisect模块的insort功能:

>> import bisect 
>> a = [1, 2, 4, 5] 
>> bisect.insort(a, 3) 
>> print(a) 
[1, 2, 3, 4, 5] 

Answer 2

提示1:您可能想要在bisect模块中学习Python代码.

提示2: 切片可用于列表插入:

>>> s = ['a', 'b', 'd', 'e']
>>> s[2:2] = ['c']
>>> s
['a', 'b', 'c', 'd', 'e']

Answer 3

您应该使用bisect模块.此外,在使用bisect.insort_left之前,需要对列表进行排序

这是一个非常大的差异.

>>> l = [0, 2, 4, 5, 9]
>>> bisect.insort_left(l,8)
>>> l
[0, 2, 4, 5, 8, 9]

timeit.timeit("l.append(8); l = sorted(l)",setup="l = [4,2,0,9,5]; import bisect; l = sorted(l)",number=10000)
    1.2235019207000732

timeit.timeit("bisect.insort_left(l,8)",setup="l = [4,2,0,9,5]; import bisect; l=sorted(l)",number=10000)
    0.041441917419433594

Answer 4

我现在正在学习算法，所以我想知道 bisect 模块是如何编写的。以下是 bisect 模块中有关将项目插入排序列表的代码，该代码使用二分法：

def insort_right(a, x, lo=0, hi=None):
    """Insert item x in list a, and keep it sorted assuming a is sorted.
    If x is already in a, insert it to the right of the rightmost x.
    Optional args lo (default 0) and hi (default len(a)) bound the
    slice of a to be searched.
    """

    if lo < 0:
        raise ValueError('lo must be non-negative')
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid]:
            hi = mid
        else:
            lo = mid+1
    a.insert(lo, x)

Answer 5

如果没有人为限制，应该按照 的描述bisect.insort()使用。然而，正如评论中提到的，大多数现实世界的问题不仅仅是对纯数字进行排序。stangaVelda

幸运的是，正如 所评论的drakenation，该解决方案适用于任何可比较的对象。例如，bisect.insort()还可以使用实现以下功能的自定义数据类__lt__()：

from bisect import insort

@dataclass
class Person:
    first_name: str
    last_name: str
    age: int

    def __lt__(self, other):
        return self.age < other.age

persons = []

insort(persons, Person('John', 'Doe', 30))
insort(persons, Person('Jane', 'Doe', 28))
insort(persons, Person('Santa', 'Claus', 1750))

# [Person(first_name='Jane', last_name='Doe', age=28), Person(first_name='John', last_name='Doe', age=30), Person(first_name='Santa', last_name='Claus', age=1750)]

然而，在元组的情况下，需要按任意键排序。默认情况下，元组按第一项（名字）排序，然后按下一项（姓氏）排序，依此类推。

作为解决方案，您可以管理附加的密钥列表：

from bisect import bisect

persons = []
ages = []

def insert_person(person):
    age = person[2]
    i = bisect(ages, age)
    persons.insert(i, person)
    ages.insert(i, age)
    
insert_person(('John', 'Doe', 30))
insert_person(('Jane', 'Doe', 28))
insert_person(('Santa', 'Claus', 1750))

官方解决方案：的文档bisect.insort()参考了一个如何使用该函数的菜谱，在自定义类SortedCollection中实现该功能，这样就可以使用如下：

>>> s = SortedCollection(key=itemgetter(2))
>>> for record in [
...         ('roger', 'young', 30),
...         ('angela', 'jones', 28),
...         ('bill', 'smith', 22),
...         ('david', 'thomas', 32)]:
...     s.insert(record)

>>> pprint(list(s))         # show records sorted by age
[('bill', 'smith', 22),
 ('angela', 'jones', 28),
 ('roger', 'young', 30),
 ('david', 'thomas', 32)]

以下是使示例工作所需的类的相关摘录。基本上，它管理与项目列表并行的SortedCollection 附加键列表，以找出在哪里插入新元组（及其键）。

from bisect import bisect_left

class SortedCollection(object):

    def __init__(self, iterable=(), key=None):
        self._given_key = key
        key = (lambda x: x) if key is None else key
        decorated = sorted((key(item), item) for item in iterable)
        self._keys = [k for k, item in decorated]
        self._items = [item for k, item in decorated]
        self._key = key
        
    def __getitem__(self, i):
        return self._items[i]

    def __iter__(self):
        return iter(self._items)
        
    def insert(self, item):
        'Insert a new item.  If equal keys are found, add to the left'
        k = self._key(item)
        i = bisect_left(self._keys, k)
        self._keys.insert(i, k)
        self._items.insert(i, item)

请注意，list.insert()以及 的复杂度bisect.insort()为O(n)。因此，正如 所评论的nz_21，手动迭代排序列表，寻找正确的位置，在复杂性方面也同样好。事实上，在插入新值后简单地对数组进行排序也可能没问题，因为 Python 的Timsort 的最坏情况复杂度为 O(n log(n))。但为了完整起见，请注意二叉搜索树 (BST) 允许在 O(log(n)) 时间内进行插入。