Efficiently find "duplicates" between two lists with dict-elements comparing just a subset of the dict-fields

user_4865723 0
Viewed 493

What makes my question different...

...from similar ones here on StackOverflow. In the MWE below, the dict has 4 fields; but only 2 of them are relevant for comparing.

The problem...

...is easy, and I always provide a solution in my MWE below, but I would like to know if there is a more efficient, pythonic way to handle that -- efficient in the meaning of CPU time.

Two list() with dict() elements need to be check for "duplicates." A duplicate is defined as if the fields title and date are equal. The content of the other fields (flag and misc) do not matter. To add another factor: the dict elements can have different number of fields, but title and date are always present.

My solution

I simply translate my human words into python words (dupli and data are the two lists):

for d in dupli[:]:
    for e in data:
        # compare by 'title' and 'date'
        if e['title'] == d['title'] and e['date'] == d['date']:
            print('Duplicate found: {}'.format(d))
            # remove duplicates
            dupli.remove(d)

My full MWE

This MWE generates the list data with 100 random elements. The second list dupli has 10 elements where 3 of them have "duplicates" (by title and date BUT NOT misc or flag) in the first list.

#!/usr/bin/env python3
import random
import string


# helper function
def random_string(n):
    return ''.join([random.choice(string.ascii_letters) for i in range(n)])


# Create persistent data
def create_data(n):
    container = []
    for idx in range(n):
        # create an element with title, date and some misc data
        element = {
           'title': random_string(random.randrange(35)),
           'date': [2020, 5, random.randint(1, 30)],
           'flag': (random.random() < 0.5),  # bool
           'misc': random_string(random.randrange(5)),
        }

        container.append(element)
    return container


# persistent data
data = create_data(100)

# new data elements with possible duplicates
dupli = create_data(10)

# generate 3 duplicates
for idx in [2, 5, 8]:
    dupli[idx]['title'] = data[idx*10]['title']
    dupli[idx]['date'] = data[idx*10]['date']

# MY APPROACH to check for duplicates
for d in dupli[:]:
    for e in data:
        # compare by 'title' and 'date'
        if e['title'] == d['title'] and e['date'] == d['date']:
            print('Duplicate found: {}'.format(d))
            # remove duplicates
            dupli.remove(d)

# add the rest to persistent data
data.extend(dupli)

Background information

This is only an MWE. The real world data is more complex. That is why efficiency is important for me. The following numbers depending on my users of course, but just to give you and idea:

  • A dict element has 4 to 12 fields.
  • A list have 200 to 20.000 elements.
  • There are 30 to 300 lists in my application.
  • On the other side for each list there is a list with new elements: 10 to 40 elements.
compare python-3.x list dictionary python
1 Answers

I hope I understood your question. You can first prepare a set() with tuples (<title>, <date>) and then just check if element from data list is in this set - this will be O(n).

For example:

elems = set((d['title'], tuple(d['date'])) for d in dupli)
for e in data:
    if (e['title'], tuple(e['date'])) in elems:
        print('Duplicate found: {}'.format(e))

Prints:

Duplicate found: {'title': 'ENhIdksxeNKqCgbbg', 'date': [2020, 5, 5], 'flag': True, 'misc': ''}
Duplicate found: {'title': 'MRyXAmfJjSNjrXYTNpPRQFP', 'date': [2020, 5, 3], 'flag': True, 'misc': 'oTmr'}
Duplicate found: {'title': 'IyeSazUnquqTwYXGnTjHelFGr', 'date': [2020, 5, 12], 'flag': True, 'misc': 'CdhG'}

EDIT:

In set((d['title'], tuple(d['date'])) for d in dupli) I must first create tuple from d['date'], because original type is list (unhashable) and I cannot add list to set.

Better will be storing d['date'] as tuple originally (to skip this converting step and speed-up things):

'date': (2020, 5, random.randint(1, 30)),  # <-- tuple, not list
user_100359850
Related