提高 python 算法的速度

Question

我已经使用 Twitter 的 Sentiment140 数据集进行情绪分析

代码：

从推文中获取单词：

tweet_tokens = []
[tweet_tokens.append(dev.get_tweet_tokens(idx)) for idx, item in enumerate(dev)]

从令牌中获取未知单词

words_without_embs = []
[[words_without_embs.append(w) for w in tweet if w not in word2vec] for tweet in tweet_tokens]
len(words_without_embs)

代码的最后一部分，将向量计算为左右单词（上下文）的平均值

vectors = {} # alg
for word in words_without_embs:
  mean_vectors = []
  for tweet in tweet_tokens:
    if word in tweet:
      idx = tweet.index(word)
      try:
        mean_vector = np.mean([word2vec.get_vector(tweet[idx-1]), word2vec.get_vector(tweet[idx+1])], axis=0)
        mean_vectors.append(mean_vector)
      except:
        pass

    if tweet == tweet_tokens[-1]: # last iteration
      mean_vector_all_tweets = np.mean(mean_vectors, axis=0)
      vectors[word] = mean_vector_all_tweets

有 1058532 个单词，此代码的最后部分运行速度非常慢，每分钟大约 250 个单词。

如何提高该算法的速度？

Answer 1

您的代码缓慢的主要原因之一是检查 tweet_tokens 中每条推文的所有单词（近 100 万个单词）是否存在。因此，您实施的时间复杂度为 1e6 * |tweet_tokens|.

1) 第一次改进（减少搜索和比较）

但是，您可以先标记每个 tweet，然后找到该词的索引，这样可以做得更好。如果你在现有的单词上建立一个字典，你可以从单词字典中找到最多 log(1e6) ~ 25 个比较的单词标记的索引。因此，在这种情况下，时间复杂度最多为25 * |tweet_tokens|。因此，您可以将代码的性能提高 1e6/25 = 40000 倍！

2) 第二次改进（减少 Word2Vec 计算）

此外，你总是在计算不同推文中同一个词的向量。因此，每个词的向量将被计算 f 倍 f 是该词在推文中的频率。一个合理的解决方案是一次计算 words_without_embs 中所有单词的向量（它可以是一个离线过程）。然后，例如，根据单词字典中的单词索引存储所有这些向量（以某种方式根据单词查询快速找到它们）。最终，只需从准备好的数据结构中读取它进行平均计算。那样的话，除了40000倍的提升之外，你还可以通过推文中所有词频的总和来提升你的代码的性能。

Answer 2

这看起来可以与一些小的编辑很好地并行化。

你能否将最后一个 if tweet == tweet_tokens[-1]: 块移动到一个级别并删除它的“if”语句？这本身只会略微提高速度，但有了它，您可以更有效地并行化代码。
考虑将内部 for 循环设为自己的函数并通过多线程设置调用它。（有关描述和示例，请参阅 this site 处的 ThreadPoolExecutor 和 thread_function()。）然后您可以为单个机器上的每个处理器或分布式环境中的每个 VM 设置一个单独的线程。这应该允许更有效的缩放。
在@DarrylG 的上述评论的基础上，重构那些列表理解以避免将 .append() 与现有列表一起使用。 .append() 比等效的列表理解要慢。例如，将 [tweet_tokens.append(dev.get_tweet_tokens(idx)) for idx, item in enumerate(dev)] 更改为 tweet_tokens = [dev.get_tweet_tokens(idx) for idx, item in enumerate(dev)]。

Answer 3

处理未知词的更常见（并且可能更好）的策略包括：

training/using 一个模型，如 FastText，可以为词汇外 (OOV) 词提供猜测向量
获得更多的训练数据，所以可以从实际用法中学习到更多未知词的向量
完全忽略生词

您似乎决定通过对所有直接相邻词取平均值来为 OOV 词合成新向量。我认为这不会特别有效。在词向量的多种下游使用中，它只是倾向于加重词的上下文相邻词——这也可以通过完全忽略未知词来实现simply/cheaply。

但是考虑到您想要做的事情，最好的方法是在标识 words_without_embs.

的同一遍中收集相邻的单词

例如，将 words_without_embs 设为 dict（或者 DefaultDict），其中每个键是一个需要向量的单词，每个值是一个 list 你目前找到的所有相邻词。

然后，tweet_tokens 上的一个循环会用 keys 填充 words_without_embs，这些词需要向量，同时填充那些 values 以及目前看到的所有相邻词。

然后，words_without_embs 键的最后一个循环将简单地获取现有的相邻词列表以进行平均。（不再多次通过 tweet_tokens。）

但同样：所有这些工作可能不会优于简单地删除未知单词的基准做法。

提高 python 算法的速度

Improve speed of python algorithm

python

algorithm

machine-learning

nlp

word2vec

1) 第一次改进（减少搜索和比较）

2) 第二次改进（减少 Word2Vec 计算）