I am trying to find the similarity between the two movies using Pearson correlation coefficient. The programs is working well for small inputs but for large inputs (like 100000 lines) it takes forever. My professor said it would take few minutes, but my program is executing forever.
The input format:
If two or more users watch two movies, we will find similarity between them based on rating.
# -*- coding: utf-8 -*- """ Created on June 06, 2016 @author: Praveen Allam """ from mrjob.job import MRJob from mrjob.step import MRStep from itertools import combinations from itertools import izip from math import sqrt class PearsonCorrelation(MRJob): def steps(self): return [ MRStep(mapper=self.mapper1, reducer=self.reducer1), MRStep(mapper=self.mapper2, reducer=self.reducer2) ] def mapper1(self, _, line): ##yield each line to first mapper user,movie,rating=line.split('|') yield None,[user,movie,rating] def reducer1(self, _, value): ##yield all combinations to second mapper for item1,item2 in combinations(value,2): yield item1,item2 def mapper2(self,value1,value2): ##yield movie1,movie2 and corresponding ratings of user. if(value1==value2): yield [value1,value2],[float(value1),float(value2)] def reducer2(self,movies,ratings): rating= for item in ratings: rating.append(item) ##extract using izip only if there are more than one instance. if(len(rating)>1): v1,v2=izip(*rating) ##calculate the pearson coefficient corr=self.pearsonCoefficient(v1,v2) ##yield the result yield "The Similarity between "+movies+" and "+movies+" is: " , corr def pearsonCoefficient(self,a,b): n=len(b) value=range(n) #sums of individual lists sum_x=sum([float(a[i]) for i in value]) sum_y=sum([float(b[i]) for i in value]) #sum of the squares of each lists sum_xSq=sum([a[i]**2.0 for i in value]) sum_ySq=sum([b[i]**2.0 for i in value]) #sum of the products sumP=sum([a[i]*b[i] for i in value]) #Calculate Pearson coefficient numerator=sumP-(sum_x*sum_y/n) denominator=((sum_xSq-pow(sum_x,2)/n)*(sum_ySq-pow(sum_y,2)/n))**0.5 if denominator == 0: return 1 result=numerator/denominator return result if __name__ == '__main__': PearsonCorrelation.run()