在 Python 中使用排序列表：“bisect”模块的魔力

使用排序列表有时可能有点棘手。您需要在每次插入后维护列表的顺序并有效地搜索其中的元素。二分搜索是一种用于在排序列表中搜索的强大算法。虽然从头开始实施并不太困难，但可能很耗时。幸运的是，Python 提供了 bisect 模块，这使得处理排序列表变得更加容易。

什么是二分查找？

二分搜索是一种在排序数组中查找目标值位置的算法。想象一下您正在电话簿中搜索一个名字。您可能不是从第一页开始，而是从书的中间开始，并根据名称按字母顺序是大于还是小于中间的名称来决定是在前半部分还是后半部分继续搜索。二分查找以类似的方式进行操作：它以两个指针开始，一个位于列表的开头，另一个位于列表的末尾。然后计算中间元素并与目标进行比较。

bisect 模块：简化排序列表操作

虽然二分搜索很有效，但每次都写出实现可能很乏味。但是，如果您只需一行代码即可执行相同的操作呢？这就是 Python 的 bisect 模块的用武之地。bisect 是 Python 标准库的一部分，可帮助您维护排序列表，而无需在每次插入后对其进行排序。它使用简单的二分算法来实现这一点。

bisect 模块提供了两个关键函数：bisect 和 insort。 bisect 函数查找应插入元素以保持列表排序的索引，而 insort 函数将元素插入列表中同时保持其排序顺序。

使用二等分模块：一个实际示例

让我们从导入模块开始：

import bisect

示例 1：将数字插入排序列表

假设我们有一个排序的数字列表：

data = [1, 3, 5, 6, 8]

要在保持列表排序的同时插入新号码，只需使用：

bisect.insort(data, 7)

运行此代码后，数据将如下所示：

[1, 3, 5, 6, 7, 8]

示例 2：查找插入点

如果您只想找出数字将插入的位置而不实际插入怎么办？您可以使用 bisect_left 或 bisect_right 函数：

index = bisect.bisect_left(data, 4)
print(index)  # Output: 2

这告诉我们应该将数字 4 插入到索引 2 处以保持列表有序。

示例 3：维护动态列表中的排序顺序

假设您正在管理一个动态增长的列表，并且需要插入元素，同时确保其保持排序：

dynamic_data = []
for number in [10, 3, 7, 5, 8, 2]:
    bisect.insort(dynamic_data, number)
    print(dynamic_data)

这将在插入元素时输出每一步的列表：

[10]
[3, 10]
[3, 7, 10]
[3, 5, 7, 10]
[3, 5, 7, 8, 10]
[2, 3, 5, 7, 8, 10]

示例 4：将 bisect 与自定义对象结合使用

假设您有一个自定义对象列表，例如元组，并且您想根据特定条件插入它们：

items = [(1, 'apple'), (3, 'cherry'), (5, 'date')]
bisect.insort(items, (2, 'banana'))
print(items)  # Output: [(1, 'apple'), (2, 'banana'), (3, 'cherry'), (5, 'date')]

或者您可能想根据每个元组的第二个元素插入：

items = [('a', 10), ('b', 20), ('c', 30)]
bisect.insort(items, ('d', 25), key=lambda x: x[1])
print(items)  # Output: [('a', 10), ('b', 20), ('d', 25), ('c', 30)]

行动中的二分法：搜索单词

二等分模块不限于数字；它对于搜索字符串、元组、字符等列表也很有用。
例如，要在排序列表中查找单词：

def searchWord(dictionary, target):
    return bisect.bisect_left(dictionary, target)


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'guitar', 'happiness', 'ice', 'joke']
target = 'guitar'

或者查找具有特定前缀的单词组中的第一个单词：

def searchPrefix(dictionary, prefix):
    return bisect.bisect_left(dictionary, prefix), bisect.bisect_right(dictionary, prefix + 'z') # adding 'z' to the prefix to get the last word starting with the prefix
# bisect_rigth function will be discussed in a moment


dictionary = ['alphabet', 'bear', 'car', 'density', 'epic', 'fear', 'generator', 'genetic', 'genius', 'gentlemen', 'guitar', 'happiness', 'ice', 'joke']
prefix = 'gen'

但是，请记住 bisect_left 返回应插入目标的索引，而不是目标是否存在于列表中。

bisect 和 insort 的变体

该模块还包括右侧变体：bisect_right 和 insort_right。如果元素已在列表中，这些函数将返回插入元素的最右侧索引。例如，如果目标在列表中，bisect_right 将返回大于目标的第一个元素的索引，而 insort_right 将在该位置插入元素。

引擎盖下平分

bisect 模块的强大之处在于它有效地实现了二分搜索算法。例如，当您调用 bisect.bisect_left 时，该函数本质上对列表执行二分搜索以确定新元素的正确插入点。

以下是它的工作原理：

1. 初始化：函数以两个指针lo和hi开始，它们代表列表内搜索范围的下限和上限。最初，lo 设置为列表的开头（索引 0），hi 设置为列表的末尾（索引等于列表的长度）。但您也可以指定自定义 lo 和 hi 值以在列表的特定范围内进行搜索。

2. Bisection: Within a loop, the function calculates the midpoint (mid) between lo and hi. It then compares the value at mid with the target value you’re looking to insert.

3. Comparison:

* If the target is less than or equal to the value at `mid`, the upper bound (`hi`) is moved to `mid`.
* If the target is greater, the lower bound (`lo`) is moved to `mid + 1`.

1. Termination: This process continues, halving the search range each time, until lo equals hi. At this point, lo (or hi) represents the correct index where the target should be inserted to maintain the list's sorted order.

2. Insertion: For the insort function, once the correct index is found using bisect_left, the target is inserted into the list at that position.

This approach ensures that the insertion process is efficient, with a time complexity of O(log n) for the search and O(n) for the insertion due to the list shifting operation. This is significantly more efficient than sorting the list after each insertion, especially for large datasets.

bisect_left code example:

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

insort_left code example:

def insort_left(a, x, lo=0, hi=None, *, key=None):

    if key is None:
        lo = bisect_left(a, x, lo, hi)
    else:
        lo = bisect_left(a, key(x), lo, hi, key=key)
    a.insert(lo, x)

Conclusion

The bisect module makes working with sorted lists straightforward and efficient. The next time you need to perform binary search or insert elements into a sorted list, remember the bisect module and save yourself time and effort.

以上是在 Python 中使用排序列表：“bisect”模块的魔力的详细内容。更多信息请关注PHP中文网其他相关文章！