How to efficiently get the mean of the elements in two list of lists in Python

Question

I have two lists as follows.

mylist1 = [["lemon", 0.1], ["egg", 0.1], ["muffin", 0.3], ["chocolate", 0.5]] mylist2 = [["chocolate", 0.5], ["milk", 0.2], ["carrot", 0.8], ["egg", 0.8]] 

I want to get the mean of the common elements in the two lists as follows.

myoutput = [["chocolate", 0.5], ["egg", 0.45]] 

My current code is as follows

for item1 in mylist1:     for item2 in mylist2:         if item1[0] == item2[0]:              print(np.mean([item1[1], item2[1]])) 

However, since there are two for loops (O(n^2) complexity) this is very inefficient for very long lists. I am wondering if there is more standard/efficient way of doing this in Python.

Answer 1

You can do it in O(n) (single pass over each list) by converting 1 to a dict, then per item in the 2nd list access that dict (in O(1)), like this:

mylist1 = [["lemon", 0.1], ["egg", 0.1], ["muffin", 0.3], ["chocolate", 0.5]] mylist2 = [["chocolate", 0.5], ["milk", 0.2], ["carrot", 0.8], ["egg", 0.8]]  l1_as_dict = dict(mylist1)  myoutput = [] for item,price2 in mylist2:     if item in l1_as_dict:         price1 = l1_as_dict[item]         myoutput.append([item, (price1+price2)/2])  print(myoutput) 

Output:

[['chocolate', 0.5], ['egg', 0.45]]