需要帮助加速这个函数

Question

输入: 一个包含各种位置的列表嵌套列表。

[['61097', '12204947'],
 ['61097', '239293'],
 ['61794', '37020977'],
 ['61794', '63243'],
 ['63243', '5380636']]

输出：一个排序的列表，其中包含列表中唯一数字的计数。

[4, 3, 3, 3, 3]

这个想法非常简单，我有一个包含变量数量位置的列表（在我们的示例中，每个列表只包含2个位置，但最多可存在10个位置）。我想循环遍历每个列表，如果存在任何其他包含相同数量位置的列表，则将该列表添加到原始列表中。

例子：使用上面的输入数据并使用以下代码：

def gen_haplotype_blocks(df):
    counts = []
    for i in range(len(df)):
        my_list = [item for item in df if any(x in item for x in df[i])]
        my_list = list(itertools.chain.from_iterable(my_list))
        uniq_counts = len(set(my_list))
        counts.append(uniq_counts)
        clear_output()
        display('Currently Running ' +str(i))
    return sorted(counts, reverse=True)

我得到了期望的输出。在这种情况下，当我循环遍历第一个列表['61097', '12204947']时，我发现我的第二个列表['61097', '239293']都包含'61097'，因此这些列表被连接在一起形成['61097', '12204947', '61097', '239293']。这对于每个单独的列表都会执行，输出如下：

['61097', '12204947', '61097', '239293']
['61097', '12204947', '61097', '239293']
['61794', '37020977', '61794', '63243']
['61794', '37020977', '61794', '63243', '63243', '5380636']
['61794', '63243', '63243', '5380636']

一旦完成此列表，我会计算每个列表中唯一值的数量，将其附加到另一个列表中，然后对最终列表进行排序并返回该列表。

因此，在['61097'，'12204947'，'61097'，'239293']的情况下，我们有两个“61097”，一个“12204947”和一个“239293”，共3个唯一数字。

虽然我的代码可以运行，但速度非常慢。运行时间接近两个小时，仍然只在第44k行左右。

我正在寻找一种显着加快此函数速度的方法。最好不要更改原始数据结构。我非常新手Python。

提前感谢！

- dddxxx

---

只是一句话：在Python中，你通常不需要执行 for i in range(len(thing))。大多数的 things 支持迭代协议，所以你可以直接使用 for i in thing。 - jjj

你确定 [4, 3, 3, 3, 3] 是正确的吗？我没有看到任何数字出现了4次。 - Nathan

对于第一行['61097'，'12204947']，我们遍历所有其他行，并发现只有第二行['61097'，'239293']包含至少一个数字彼此相同（61097）。我们将这两个列表连接在一起得到['61097'，'12204947'，'61097'，'239293']，当您计算其中唯一数字的数量时为3。我们对第二行执行相同的操作，唯一数字也是3。对于第三行，我们的连接列表是['61794'，'37020977'，'61794'，'63243']，因为第3行和第4行至少有一个数字在两个列表中都出现了。 - dddxxx

@Nathan 当你执行第4行时，你会将列表4、3和5连接起来（因为4包含在列表3中的61794和在列表5中的63243），得到['61794'，'37020977'，'61794'，'63243'，'63243'，'5380636']。唯一的数字是61794、370...、63243和5380636。这是4个数字。 - dddxxx

@jjj 很好知道，谢谢！ - dddxxx

Answer 1

不确定您说的“相当多”是多少，但从一开始就将内部的list转换为set可以加快速度。 在我的测试中，以下代码大约快了2.5倍：

def gen_haplotype_blocks_improved(df):
    df_set = [set(d) for d in df]
    counts = []
    for d1 in df_set:
        row = d1
        for d2 in df_set:
            if d1.intersection(d2) and d1 != d2:
                row = row.union(d2)
        counts.append(len(row))
    return sorted(counts, reverse=True)  

- Selcuk

Answer 2

为了提高程序速度，特别是在处理大数据集时，关键是使用哈希表或Python中的字典来存储不同的数字作为键，每个唯一数字存在的行作为值。然后在第二次遍历时，根据字典合并每行的列表，并计算唯一元素的数量。

def gen_haplotype_blocks(input):
    unique_numbers = {}

    for i, numbers in enumerate(input):
        for number in numbers:
            if number in unique_numbers:
                unique_numbers[number].append(i)
            else:
                unique_numbers[number] = [i]

    output = [[] for _ in range(len(input))]

    for i, numbers in enumerate(input):
        for number in numbers:
            for line in unique_numbers[number]:
                output[i] += input[line]

    counts = [len(set(x)) for x in output]
    return sorted(counts, reverse=True)

理论上，您的算法的时间复杂度为O(N*N)，其中N是输入列表的大小。因为您需要将每个列表与所有其他列表进行比较。但是在此方法中，复杂度为O(N)，对于更大的数据集来说应该会更快。这种折衷方案是额外的空间复杂度。

- Haojin

---

这实际上比OP和我的方法都快，但由于某些原因结果不正确。它在问题中的示例列表中产生相同的结果，但在其他情况下失败（例如尝试复制其中一个元组）。 - Selcuk

@Selcuk，很好的发现！我之前试图避免合并列表，但没有成功。我已经更新了代码，现在它对我来说能够正常工作了。 - Haojin