Python 的 bisect 函数如何使用这个元组作为参数？

Question

这是我正在学习的 Coursera 基因组学课程中提出的问题。我们目前正在处理搜索方法，特别是如何检测（对齐）较长 DNA 序列（t）中较短 DNA 序列（p，字符串）的所有出现，也是一个字符串）。所讨论的方法涉及为 t 创建一个 散列 table，由长度为 k 的所有可能子串组成 及其位置（每个子串都是所谓的 kmer）。然后，我们使用从 p 派生的相同长度 (kmers) 的子字符串搜索散列 table。这涉及创建 Index class 和最终使用 Python 的 bisect_left 函数.这是代码：

import bisect
import sys

class Index(object):

    def __init__(self, t, k):
        ''' Create index from all substrings of size 'length' '''
        self.k = k  # k-mer length (k)
        self.index = []
        for i in range(len(t) - k + 1):  # for each k-mer
            self.index.append((t[i:i+k], i))  # append (k-mer, offset) pair (tuple)
        self.index.sort()  # alphabetize by k-mer
    
    def query(self, p):
        ''' Return index hits for first k-mer of P '''
        kmer = p[:self.k]  # query with first k-mer
        i = bisect.bisect_left(self.index, (kmer, -1))  # binary search
        hits = []
        while i < len(self.index):  # collect matching index entries
            if self.index[i][0] != kmer:
                break
            hits.append(self.index[i][1])
            i += 1
        return hits

我的问题涉及 bisect_left 函数 的格式。 Python 文档给出了这个函数的语法如下：
bisect.bisect_left(a, x, lo=0, hi=len(a), *, key=None)
我课程中使用的bisect_left函数是这样格式化的：
i = bisect.bisect_left(self.index, (kmer, -1))
我知道参数 a 已经传递给参数 self.index，这是从 [= 创建的散列 table 22=]t。但是后来我对后面的 tuple 感到困惑。我看不到以下任何参数如何接受元组。我可以想象散列 table 被组织为 (kmer, position) 形式的元组，但是这些条目的 none 将具有位置 -1。讲师声明他出于特定目的将值设置为 -1，如下所示：

“所以第一步就是找到 p 的第一个 k 基础，以便在 tables 中查找它们。所以，我要说 kmer 等于 p 到长度 k，并且我们需要做 self.k。现在我想 找到这个 kmer 出现的列表中的第一个位置 ，所以我要使用 bisect 快速完成。说 i = bisect.bisect_left。然后我传入我们正在搜索的列表，然后是我们正在搜索的对象。记住这是一个列表元组所以我要传入kmer，然后我要放-1。并且 因为列表中的所有索引都大于负数，这确保我们总是得到第一次出现 。”

我的意思是，我懂英语，但我不明白 bisect 如何 (a) 将元组作为参数，以及 (b) 假设它可以（显然可以），它如何使使用的位置 -1 在散列 table 中不存在？我有一种预感，我不知道排序方面发生了什么，但我不能把我的手指放在上面。

非常感谢，很抱歉我的问题陈述太长了。

Answer 1

在 Python 中，您可以按字典顺序比较元组（就像在字典中一样）。首先比较第一个元素，然后比较第二个元素，依此类推。

>>> (1, 2, 3) < (1, 2, 4)
True
>>> (1, 3, 3) < (1, 2, 4)
False
>>> ('a', 'p', 'p', 'l', 'e') > ('a', 'r', 't')
False
>>>

bisect.bisect_left 不限于整数或字符串，它适用于任何可以比较的对象。事实上，你可以在这里看到它是如何实现的：GitHub link

与 documentation on bisect_left says 一样，它会搜索要插入新元组的索引，以便列表仍然排序。

例如，这个列表排序：

[("a", 1), ("b", -42), ("c", 2), ("c", 3)]

这不是：

[("a", 1), ("c", 3),  ("b", -42), ("c", 3)]

将 bisect.bisect_left 与元组一起使用的示例：

from bisect import bisect_left

# The shopping list must be ordered by food type first, by
# quantity second.
shopping_list = [("apples", 100), ("bananas", 42), ("grapes", 250)]

# Say, we want to figure out where to put our cherries.
print(bisect_left(shopping_list, ("cherries", 666)))  # 2
# Our new list might look like this:
[("apples", 100), ("bananas", 42), ("cherries", 666), ("grapes", 250)]
# (just for illustration, bisect_left doesn't change the list)

# What if we want to find out where the bananas start?
print(bisect_left(shopping_list, ("bananas",)))  # 1

感谢 Kelly Bundy 的评论：(kmer,) 比 (kmer, -1) 更适合使用。 ("foo",)确实小于("foo", whatever)。如果您的要求发生变化并且现在 -1 是一个有效的第二个元素，这会更好。

P.S。 self.index 列表不是散列 table。它只是一个排序的元组列表。它没有任何特殊的搜索功能（除了允许二进制搜索，这就是您正在做的）。 hash tables.

的解释有a great talk by Brandon Rhodes and this SO question

Python 的 bisect 函数如何使用这个元组作为参数？

How does Python's bisect function use this tuple as an argument?

python

hashtable

dna-sequence

bisect