Group unique users with two changing IDs

The idea is very simple:

• for each entry

  • scan all existing users,

    • if any dimension of the entry matches previous user, extend his attribute set, and add him to the merge list

  • if was not matched to anyone existing create a new user,

  • otherwise group distinct users together

This should be pretty fast, as it scans the list only once and does not require recursion.

ID1 = [7, 7, 8, 9]
ID2 = ["a", "b", "b", "c"]
user = {}
new_user_idx = 0
for i in range(len(ID1)):
    merge = []   # this is a list of users that should be merged
    for k in user:
        # find if any feature is already found in previous user  
        if ID1[i] in user[k][0]:
            user[k][1].add(ID2[i])
            merge.append(k)
        if ID2[i] in user[k][1]:
            user[k][0].add(ID1[i])
            merge.append(k)
    if not merge:
        # we have to create a new user
        user[new_user_idx] = (set([ID1[i]]), set([ID2[i]]))
        new_user_idx += 1
    elif len(merge)>1:
        # merging existing users
        for el in set(merge[1:]):
            if el==merge[0]: continue  # skip unnecessary merge
            user[merge[0]][0].update(user[el][0]) # copy attributes
            user[merge[0]][1].update(user[el][1])
            user.pop(el) # delete merged user
print(user)   


{0: ({7, 8}, {'a', 'b'}), 1: ({9}, {'c'})}
 

Trying it with sets:

%%timeit
ID1 = [7, 7, 8, 9]
ID2 = ["a", "b", "b", "c"]

users = {0: {'phone': set([ID1[0]]), 'email': set([ID2[0]])}}

for index, id1 in enumerate(ID1):
    id2 = ID2[index]
    
    # iterate over found list of users
    i = 0
    n_users = max(users.keys()) 
    while i <= n_users:
        if any([(id1 in users[i]['phone']), (id2 in users[i]['email'])]):
            users[i]['phone'].add(id1)
            users[i]['email'].add(id2)
            break
        i += 1

    # add new user if not found
    if i > n_users:
        users[i] = {'phone': set([id1]), 'email': set([id2])}

Don't run timeit with a 5-element list. This is not a valid method to evaluate the contenders. Use bigger lists (1000+) to test performance, or you will not actually end up with the fast program you want.

I'll throw my hat in the ring, with an O(N) worst-case algorithm (doesn't depend on the number of users).

I'll point out the performance of the other algorithms depends a lot on the number of IDs a typical user has. This one is specialized to work well for a large number of IDs per user.

ID1 = [7, 7, 8, 9]
ID2 = ["a", "b", "b", "c"]

from collections import defaultdict

id1_to_id2 = defaultdict(set)
id2_to_id1 = defaultdict(set)
for id1, id2 in zip(ID1, ID2):
    id1_to_id2[id1].add(id2)
    id2_to_id1[id2].add(id1)

id1_to_user = {}
users = {}
for id1 in id1_to_id2:
    if id1 in id1_to_user:
        continue # Already processed

    # Find all id1 and id2 for this user, using 'floodfill'
    id1s = {id1}
    id2s = set()
    id1_queue = [id1]
    while len(id1_queue) > 0:
        old_id2s = id2s.copy()
        for id1 in id1_queue:
            id2s.update(id1_to_id2[id1]) # try using id2_queue = set().union(id1_to_id2[id1] for id1 in id1_queue)-id2s; id2s |= id2_queue as well in case it's faster
        id2_queue = id2s - old_id2s
        id1_queue = []
        old_id1s = id1s.copy()
        for id2 in id2_queue:
            id1s.update(id2_to_id1[id2])
        id2_queue = []
        id1_queue = id1s - old_id1s
    user = len(users)
    users[user] = [id1s, id2s]
    for id1 in id1s:
        id1_to_user[id1] = user

print(users)