python - 更新嵌套列表在 python 中花费的时间太长

Question

我正在尝试在 python 中实现棕色聚类算法。

我有 cluster = List[List] 的数据结构

在任何给定时间，外部列表长度最大为 40 或 41。

但内部列表包含英文单词，例如'the'，'hello'等

所以我总共有 8000 个单词(词汇)，最初将前 40 个单词放入集群。

我将我的词汇量从 41 遍历到 8000 # 做一些计算这需要非常少的时间。 # 合并列表中的 2 项并从列表中删除一项 # 例如:如果 c1 和 c2 是簇中的项，则

for i in range(41, 8000):
    clusters.append(vocabulary[i])
    c1 = computation 1
    c2 = computation 2
    clusters[c1] = clusters[c1] + clusters[c2]
    del clusters[c2]

但是随着我遍历我的词汇表，行 clusters[c1] = clusters[c1] + clusters[c1] 所花费的时间逐渐增加。最初对于 41-50 是 1 秒，但对于每 20 个词汇项目，时间增加 1 秒。

在我的整个代码中仅评论 clusters[c1] = clusters[c1] + clusters[c1] 时，我观察到所有迭代都需要恒定的时间。我不确定如何才能加快这个过程。

for i in range(41, 8000):
    clusters.append(vocabulary[i])
    c1 = computation 1
    c2 = computation 2
    #clusters[c1] = clusters[c1] + clusters[c2]
    del clusters[c2]

我是stackoverflow的新手，如果这里的格式不正确，请原谅。

谢谢

Answer 1

您遇到的问题是列表连接是线性时间操作。因此，您的整个循环是 O(n^2)(对于远大于 1000 的 n 来说，这太慢了)。这忽略了复制如此大的列表如何不利于缓存性能等。

不相交集合数据结构

我推荐的解决方案是使用 disjoint set数据结构。这是一种基于树的数据结构，可在您执行查询时“ self 展平”，从而使“合并”集群的运行时间非常快。

基本思想是每个单词都以其自己的“单例”树开始，合并集群包括使一棵树的根成为另一棵树的子树。重复此过程(注意平衡)，直到您拥有所需数量的集群。

我写了一个example implementation (GitHub 链接)假设每个集合的元素都是数字。只要您有从词汇术语到整数的映射，它就可以很好地满足您的目的。 (注意:我已经完成了一些初步测试，但我现在只用了 5 分钟就写完了，所以我建议检查我的工作。;))

要在您的代码中使用，我会执行如下操作:

clusters = DisjointSet(8000)
# some code to merge the first 40 words into clusters
for i in range(41, 8000):
    c1 = some_computation() # assuming c1 is a number
    c2 = some_computation() # assuming c2 is a number
    clusters.join(c1, c2)

# Now, if you want to determine if some word with number k is 
# in the same cluster as a word with number j:
print("{} and {} are in the same cluster? {}".format(j, k, clusters.query(j, k))

关于集合与列表

虽然集合提供比列表更快的访问时间，但它们在复制时实际上有更差的运行时间。这在理论上是有道理的，因为 set 对象实际上必须分配和分配 比列表更多 的内存空间以获得适当的加载因子。此外，插入如此多的项目可能会导致整个哈希表的“重新散列”，这在最坏的情况下是二次时间操作。

但是，我们现在关心的是练习，因此我进行了一个快速实验，以确定偏移集比列表到底差到什么程度。

如果有人感兴趣，执行此测试的代码如下。我使用的是 Python 的 Intel 封装，所以我的性能可能比你的机器上稍微快一些。

import time
import random
import numpy as np
import matplotlib.pyplot as plt

data = []
for trial in range(5):
    trial_data = []

    for N in range(0, 20000, 50):
        l1 = random.sample(range(1000000), N)
        l2 = random.sample(range(1000000), N)
        s1 = set(l1)
        s2 = set(l2)

        # Time to concatenate two lists of length N
        start_lst = time.clock()
        l3 = l1+l2
        stop_lst = time.clock()

        # Time to union two sets of length N
        start_set = time.clock()
        s3 = s1|s2
        stop_set  = time.clock()

        trial_data.append([N, stop_lst - start_lst, stop_set - start_set])
    data.append(trial_data)

# average the trials and plot
data_array = np.array(data)
avg_data = np.average(data_array, 0)

fig = plt.figure()
ax = plt.gca()
ax.plot(avg_data[:,0], avg_data[:,1], label='Lists')
ax.plot(avg_data[:,0], avg_data[:,2], label='Sets')
ax.set_xlabel('Length of set or list (N)')
ax.set_ylabel('Seconds to union or concat (s)')
plt.legend(loc=2)
plt.show()