Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

How to make the following code more efficient?

"""
Calculate the posterior distribution of p(pos|word) using Baye's rule:
p(pos|word) \propto p(word|pos)p(pos).
"""    
word_pos_dict = defaultdict(float)  # Example, word|pos -> 0.0012
pos_dict = defaultdict(float)       # pos -> 0.005
pos_word_dict = defaultdict(float)  # pos|word -> 0.017

for word_pos, word_pos_prob in word_pos_dict.items():
    word, pos = word_pos.split('|')
    marginal_prob = 0        
    for pos_prob in pos_dict.values():
        marginal_prob += word_pos_prob * pos_prob    # Marginal prob of p(word)
    pos_word_prob = word_pos_prob * pos_dict[pos]
    pos_word = pos + '|' + word
    pos_word_dict[pos_word] = pos_word_prob / marginal_prob

In practice, the length of word_pos_dict is 57,602, and pos_dict has 984 elements, which make this calculation much slower. Is there something wrong with the implementation, design or algorithm?

share|improve this question

2 Answers 2

up vote 3 down vote accepted

One obvious improvement:

for word_pos, word_pos_prob in word_pos_dict.items():
    marginal_prob = 0        
    for pos_prob in pos_dict.values():
        marginal_prob += word_pos_prob * pos_prob 

Simplifies to:

multiplier = 0
for pos_prob in pos_dict.values():
    multiplier += pos_prob
# or just 'multiplier = sum(pos_dict.values())'

for word_pos, word_pos_prob in word_pos_dict.items():
    marginal_prob = word_pos_prob * multiplier        

Now the inner loop only runs once.

share|improve this answer

which make this calculation much slower.

An immediate question is much slower than what?

Few optimisations are obvious, but they are just nitpicking. Asymptotics remains same no matter what.

First, I'd make word_pos_dict indices tuples instead of string. That would save you string splitting and concatenation.

Second, swapping inner/outer loops in your case would be beneficial: as coded, you initialize inner loop 57602 times; when swapped, the initialization would happen only 984 times.

share|improve this answer
    
Sorry for the vague expression. I thought that it would be executed in minutes but hours. –  fishiwhj Jun 18 at 10:21
    
+1 for two-tuple keys –  jonrsharpe Jun 18 at 12:22
    
I have to say that using tuples instead of string is a beautiful solution but it will cost more time. –  fishiwhj Jun 19 at 6:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.