python - 提高python算法的速度

Question

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

代码:

从推文中获取单词:

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 倍的改进之外，您还可以通过推文中所有单词频率总和的因子来提高代码的性能。