Improve speed of python algorithm

Question

I have used Sentiment140 dataset for twitter for sentiment analysis

Code:

getting words from tweets:

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

getting unknown words from tokens

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)

last part of code, calculate vector as the mean of left and right words (context)

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

There are 1058532 words and the last part of this code works very slow, about 250 words per minute.

How can you improve the speed of this algorithm?

Answer 1

One of the main reasons for your slow code is checking the existence of all words (near 1 million words) for each tweet in tweet_tokens. Hence, the time complexity of your implementation is 1e6 * |tweet_tokens|.

1) First Improvement (Reducing Search and Comparisons)

However, you can do it much better by tokenizing each tweet first, then finding the index of the word. If you built one dictionary over existing words, you can find the index of the word token with at most log(1e6) ~ 25 comparison from the word dictionary. Hence, in that case, the time complexity will be at most 25 * |tweet_tokens|. Therefore, you can improve the performance of your code 1e6/25 = 40000 times faster!

2) Second Improvment (Reducing Word2Vec Computations)

Moreover, you are always computing the vector of the same word in different tweets. Hence, the vector of each word will be computed f-times that f is the frequency of the word in tweets. A rational solution is computing the vector of all words in words_without_embs one time (it can be an offline process). Then, store all of these vectors based on the index of words in the word dictionary, for example (somehow to find them fast based on the word query). Eventually, merely read it from the prepared data structure for averaging computation. In that case, in addition to 40000 times improvement, you can improve the performance of your code by the factor of the sum of all words' frequencies in tweets.

Answer 2

This looks like it would parallelize well with some minor edits.

• Can you move that last if tweet == tweet_tokens[-1]: block up a level and remove the "if" statement for it? That by itself would only give a minor speed increase, but with it in place, you could parallelize the code more effectively.
• Consider making the inner for loop its own function and calling it via a multithreaded setup. (See ThreadPoolExecutor and thread_function() at this site for description and examples.) You could then have a separate thread for each processor on a single machine - or for each VM in a distributed environment. This should allow more effective scaling.
• Building on @DarrylG 's comment above, restructure those list-comprehensions to avoid using .append() with an existing list. The .append() is slower than an equivalent list comprehension would be. For example, change [tweet_tokens.append(dev.get_tweet_tokens(idx)) for idx, item in enumerate(dev)] to tweet_tokens = [dev.get_tweet_tokens(idx) for idx, item in enumerate(dev)].