在Python中遍历列表

Question

我有一个序列列表l（数千个序列）：l = [ABCD，AABA，...]。我还有一个文件f，其中包含许多4个字母的序列（大约一百万个）。我想为f中的每个序列选择l中最接近的字符串，最多可以在汉明距离为2的情况下，并更新计数器good_count。我为此编写了以下代码，但速度非常慢。我想知道是否可以更快地完成。

def hamming(s1, s2):
    if len(s1) != len(s2):
            raise ValueError("Undefined for sequences of unequal length")  
    return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))

f = open("input.txt","r")

l = [ABCD,AABA,...]

good_count = 0
for s in f:
     x = f.readline()
     dist_array = []
     for ll in l:
        dist = hamming(x,ll)
        dist_array.append(dist)
     min_dist = min(dist_array)
     if min_dist <= 2:
        good_count += 1
print good_count

如果 l 和 f 很小，它可以快速运行，但对于较大的 l 和 f 来说，时间会很长。请建议一个更快的解决方案。

- Ssank

---

我建议您先解析该文件并将元素保存在列表中，然后应用“filter”，然后返回列表的大小。 - Tony

一点建议，您可在迭代过程中计算最小值，不需要另外一个循环来计算min(dist_array)。 - ᴀʀᴍᴀɴ

只有大约457k个可能的四字母序列。在检查每个序列之前，您可能还需要考虑消除重复项。(假设我们仅限于26个英文字母) - MrAlexBailey

如果您确实需要某个最接近的匹配项（未在上述代码中显示），则可以尝试创建一个包含所有精确模式、所有距离为一的模式和所有距离为二的模式的集合。这仍然只需要检查11个项目，但是在某些情况下，集合开始占用可观的内存。 - Peter DeGlopper

@AdamSmith - 请随意。 - Peter DeGlopper

Answer 1

使用现有的库，例如jellyfish：

from jellyfish import hamming_distance

这将为您提供汉明距离的C实现。

- Zeugma

Answer 2

哦，你只是在统计与汉明距离小于2的匹配项数量吗？这可以更快地完成。

total_count = 0

for line in f:
    # skip the s = f.readline() since that's what `line` is in this
    line = line.strip()  # just in case
    for ll in l:
        if hamming(line, ll) <= 2:
            total_count += 1
            break  # skip the rest of the ll in l loop
    # and then you don't need any processing afterwards either.

请注意，你的大部分代码时间将花费在这行上：

        if hamming(line, ll) <= 2:

任何优化该算法的方式都将极大地提高您的整体脚本速度。 Boud的答案赞扬了jellyfish的hamming_distance函数的优点，但由于没有个人经验，我不能自己推荐它。 但是他建议使用更快的hamming距离实现是正确的！

Peter DeGlopper建议将l列表分成六组不同的“两个或更少的汉明距离”匹配集。也就是说，一组包含所有可能具有两个或更少汉明距离的对的集合。 这可能看起来像：

# hamming_sets is [ {AB??}, {A?C?}, {A??D}, {?BC?}, {?B?D}, {??CD} ]
hamming_sets = [ set(), set(), set(), set(), set(), set() ]

for ll in l:
    # this should take the lion's share of time in your program
    hamming_sets[0].add(l[0] + l[1])
    hamming_sets[0].add(l[0] + l[2])
    hamming_sets[0].add(l[0] + l[3])
    hamming_sets[0].add(l[1] + l[2])
    hamming_sets[0].add(l[1] + l[3])
    hamming_sets[0].add(l[2] + l[3])

total_count = 0

for line in f:
    # and this should be fast, even if `f` is large
    line = line.strip()
    if line[0]+line[1] in hamming_sets[0] or \
       line[0]+line[2] in hamming_sets[1] or \
       line[0]+line[3] in hamming_sets[2] or \
       line[1]+line[2] in hamming_sets[3] or \
       line[1]+line[3] in hamming_sets[4] or \
       line[2]+line[3] in hamming_sets[5]:
        total_count += 1

你可以通过将hamming_sets作为一个字典，使用transform_function: set_of_results的键值对来提高可读性。

hamming_sets = {lambda s: s[0]+s[1]: set(),
                lambda s: s[0]+s[2]: set(),
                lambda s: s[0]+s[3]: set(),
                lambda s: s[1]+s[2]: set(),
                lambda s: s[1]+s[3]: set(),
                lambda s: s[2]+s[3]: set()}

for func, set_ in hamming_sets.items():
    for ll in l:
        set_.add(func(ll))

total_count = 0

for line in f:
    line = line.strip()
    if any(func(line) in set_ for func, set_ in hamming_sets.items()):
        total_count += 1

- Adam Smith

---

请注意，@Ssank，您的代码最终并不关心找到最接近的匹配项，它只关心是否找到距离<=2的匹配项。您将继续遍历整个“l”列表，直到找到最接近的匹配项，但结果并不依赖于它。如果您的预期结果在所有情况下都取决于找到最接近的匹配项，则应修改示例代码以匹配。否则，这种早期退出将平均提供更快的运行时间。 - Adam Smith

我认为实现hamming_sets的示例代码需要使用占位符（例如示例中的?）维护间距 - 仅记录模式ABCD的AB将意味着行CDAB看起来像是匹配。 - Peter DeGlopper

@PeterDeGlopper 不应该，因为我们从测试行中提取相同的字符。最后一次编辑可能会使这更清晰。 - Adam Smith

@PeterDeGlopper 可能不会，因为这是Python。在低级语言中，一个两个字符的数组比一个四个字符的数组要小，但我相信Python会将它们抽象成占用相同的内存，这才是你真正节省的！ - Adam Smith

我的实现显示sys.getsizeof("AB")为39，sys.getsizeof("AB??")为41。因此，对象开销显然占主导地位，但额外的字符会产生微小的差异。在这种情况下可能不重要，而不同的实现可能行为有所不同。 - Peter DeGlopper