在Python编程中如何减少forloops的数量以缩短运行时间？

Question

我正在研究Python编程。 问题是我的代码太慢，几天内无法获取数据。在

我的代码如下。dic字典数据是这样的；dic[0]=['happy'，100，[1234，1245，1515，1785。。。最多100]]也就是说，dic[0][1]表示dic[0][2]的长度。我要做的是计算骰子系数（单词相似度）（dic[I][0]代表一个单词（在上面的例子中，'happy'），dic[I][1]代表dic[I][2]的长度（仅len（dic[I][2]），dic[I][2]表示单词（dic[I][0]）出现的行号列表。这里的line表示语料库中的行号）

骰子系数的计算方法是：两个单词（单词1，单词2）在一个句子中出现的次数/（单词1的总出现次数+单词2的总出现次数）。在

总数据太大了。我的程序已经运行了两天了。。但还没有结果。。我必须尽快使用结果，因为这项工作的最后期限是下周。。在

有没有其他（更好的）算法可以马上实现？ 谢谢。在

for j in range(len(dic)):
            for k in range(len(dic)):

                score_temp = 0

                for r in range(len(dic[j][2])):
                    if(dic[j][2][r] in dic[k][2]):
                        score_temp += 1
                score_final = float(score_temp) / (dic[j][1] + dic[k][1])
                dice_cursor.execute('insert into dices values(?,?,?)', (dic[j][0], dic[k][0], score_final))

Answer 1

你的代码有很多问题：

由于您使用range()从0开始迭代dict的键，因此似乎最好使用一个list，这实际上是从整数到值的映射，其中整数是连续的，从0开始。另外，键在代码中似乎没有其他作用，只是用来处理dict中的条目，这意味着您根本不必遍历range()。相反，您应该这样迭代（假设您使用列表而不是dict）：

for a in the_list:
    for b in the_list:
        ...
        for value in a[2]:
            if value in b[2]:
                ...

不过，这只是稍微好一点。如果您可以使用集合而不是列表作为数据中的第三个条目，那会更好。列表上的in运算符的时间复杂度为O（n）。在集合上它的平均值只有0（1）。此外，您还可以使用标准库中的适当函数。然后你就会得出这样的结论：

^{pr2}$

Answer 2

问题不在于你的算法，而是你的数据结构。在

如果我理解您的问题，您必须迭代所有j, k组合；根本没有办法绕过它。所以最好的算法可能是dic长度的二次型。在

但是，对于每一对，您都在重复地执行一系列线性搜索，dic[j][2][r] in dic[k][2]。那部分是不必要的。如果您只需将这些dic[*][2]列表中的每一个都更改为集合，那么相同的查找就会变得即时。在

因此，代替O(N^2 * M^2)，其中N是dic的长度，M是（平均值？）dic[*][2]的长度是O(N^2 * M)。仍然很慢，但快得多。在

您没有向我们展示您在哪里构建这个巨大的列表，所以我不能向您展示如何以不同的方式构建它……但是通常这只是一个从set()开始并调用.add而不是从[]开始并调用.append。在

或者，如果你不能改变它的建造方式，你可以在事后改变它：

dic = [[a, b, set(c)] for a, b, c in dic]

---

我假设你没有重复计算两次。如果你不想重复的话。但是无论如何，您可以通过使用“multiset”类型来解决这个问题；通常collections.Counter是实现此目的的最简单方法。在

---

通过使用集合交集而不是迭代一个集合来检查另一个集合，也可以使它更简单（尽管速度稍快）。而不是这样：

^{pr2}$

…这样做：

temp_score += len(dic[j][2] & dic[k][2])

---

当我们在做的时候，你可以使用for x in dic和x来代替for j in range(len(dic))然后到处使用dic[j]。像这样：

for x in dic:
    for y in dic:
        score_temp = len(x[2] & y[2])
        score_final = float(score_temp) / (x[1] + y[1])
        dice_cursor.execute('insert into dices values(?,?,?)', 
                            (x[0], y[0], score_final))

或者，更简洁地说：

for x, y in itertools.product(dic, dic):