how can I match all the key value pair in python which running too long

Question

User-item affinity and recommendations :
I am creating a table which suggests "customers who bought this item also bought algorithm "
Input dataset

productId   userId
Prod1        a
Prod1        b
Prod1        c
Prod1        d
prod2        b
prod2        c
prod2        a
prod2        b
prod3        c
prod3        a
prod3        d
prod3        c
prod4        a
prod4        b
prod4        d
prod4        a
prod5        d
prod5        a

Output required

Product1    Product2    score
Prod1       prod3
Prod1       prod4
Prod1       prod5
prod2       Prod1
prod2       prod3
prod2       prod4
prod2       prod5
prod3       Prod1
prod3       prod2

Using code : 
#Get list of unique items
itemList=list(set(main["productId"].tolist()))

#Get count of users
userCount=len(set(main["productId"].tolist()))

#Create an empty data frame to store item affinity scores for items.
itemAffinity= pd.DataFrame(columns=('item1', 'item2', 'score'))
rowCount=0

#For each item in the list, compare with other items.
for ind1 in range(len(itemList)):

    #Get list of users who bought this item 1.
    item1Users = main[main.productId==itemList[ind1]]["userId"].tolist()
    #print("Item 1 ", item1Users)

    #Get item 2 - items that are not item 1 or those that are not analyzed already.
    for ind2 in range(ind1, len(itemList)):

        if ( ind1 == ind2):
            continue

        #Get list of users who bought item 2
        item2Users=main[main.productId==itemList[ind2]]["userId"].tolist()
        #print("Item 2",item2Users)

        #Find score. Find the common list of users and divide it by the total users.
        commonUsers= len(set(item1Users).intersection(set(item2Users)))
        score=commonUsers / userCount

        #Add a score for item 1, item 2
        itemAffinity.loc[rowCount] = [itemList[ind1],itemList[ind2],score]
        rowCount +=1
        #Add a score for item2, item 1. The same score would apply irrespective of the sequence.
        itemAffinity.loc[rowCount] = [itemList[ind2],itemList[ind1],score]
        rowCount +=1

#Check final result
itemAffinity

the code is running perfectly fine on a sample dataset but
The code is taking too long to run in dataset containing 100,000 rows. Please help me optimize the code.

Answer 1

Yes, algorithm could be improved. You are recalculating user list for items in inside loop multiple times. You can just get a dictionary of item and their users outside loops.

# get unique items
items = set(main.productId)

n_users = len(set(main.userId))

# make a dictionary of item and users who bought that item
item_users = main.groupby('productId')['userId'].apply(set).to_dict()

# iterate over combinations of item1 and item2 and store scores
result = []
for item1, item2 in itertools.combinations(items, 2):

  score = len(item_users[item1] & item_users[item2]) / n_users
  item_tuples = [(item1, item2), (item2, item1)]
  result.append((item1, item2, score))
  result.append((item2, item1, score)) # store score for reverse order as well

# convert results to a dataframe
result = pd.DataFrame(result, columns=["item1", "item2", "score"])

Timing differences:

Original implementation from question

# 3 loops, best of 3: 41.8 ms per loop

Mark's Method 2

# 3 loops, best of 3: 19.9 ms per loop

Implementation in this answer

# 3 loops, best of 3: 3.01 ms per loop