Улучшение времени выполнения для дедупликации списков на основе только определенных столбцов в Python

Question

У меня есть CSV два файла. Я пытаюсь удалить все строки, где определенные столбцы совпадают. Я думал, что я буду использовать списки в Python, чтобы сделать это. Я думал, что это будет быстро, но слишком медленно.

Я только хочу сравнить первые 3 столбца, так как последние 2 ненадежны. Тем не менее, я хочу экспортировать последние 2 столбца.

Пример:

A = [
(Jack, Smith, New York, USA, 100),
(Jim, Doe, Cleveland, UK, 200),
(Frank, Johnson, Chicago, USA, 300)
]

B = [
(Jack, Smith, New York, United States, blank),
(Jerry, Smith, Cleveland, USA, blank),
(Frank, Johnson, Chicago, America, blank)
]

Matched List = [
(Jack, Smith, New York, USA, 100)
(Frank, Johnson, Chicago, USA, 300)
]

Desired List = [
(Jim, Doe, Cleveland, UK, 200)
]

Поэтому я написал два вложенных For Loops, чтобы сравнить два списка и удалить соответствующие элементы. Тем не менее, мой список A составляет ~50 000, а список B - 600 000 строк. Это займет 3,5 часа. Мне нужно запустить его на наборе 300 000 и 4 000 000 строк; но, увидев, сколько времени это займет, он будет работать несколько дней.

Вот два For Loops (я сравниваю столбцы 0, 7, 9 и 10.)

for Acquisition_row in Acquisition_list[:]:
    for Leads_row in Leads_list:
        if (Acquisition_row[0] == Leads_row[0]) and (Acquisition_row[7] == Leads_row[7]) and (Acquisition_row[9] == Leads_row[9]) and (Acquisition_row[10] == Leads_row[10]):
            try:
                Acquisition_list.remove(Acquisition_row)
                Leads_list.append(Acquisition_row)
            except:
                print("Error!")

Есть ли способ ускорить это? Есть ли лучший подход? Должен ли я использовать другой язык программирования? Может быть, загрузить их во временную таблицу в БД SQL и использовать SQL?

Спасибо!

Answer 1

@kindall правильно предлагает set() или же dict чтобы отслеживать то, что вы видели до сих пор.

def getKey(row):
    return (row[0], row[7], row[9], row[10])

# create a set of all the keys you care about
lead_keys = {getKey(r) for r in Leads_rows}

# save this off due to reverse indexing gyration
len_ac_list = len(Acquisition_list)

for i, ac_row in enumerate(Acquisition_list[::-1]):
    ac_key = getKey(ac_row)
    if ac_key in lead_keys:   ## this look up is O(1)
        index = len_ac_list - i - 1
        Acquisition_list.pop(index)
        Leads_list.append(ac_row)
        ## maybe: lead_keys.add(ac_key)

Преимущества заключаются в следующем: при создании набора ключей вы перебираете Leads_list только один раз (для этого я выбрал Leads_list, потому что он больше, поэтому сэкономит вам больше времени); и ваш поиск по Acquisition_list занимает постоянное время, O(1), а не O(n), где n - это len(Leads_list).

В вашей первоначальной настройке вы выполняли, в худшем случае, (n*m) или (300000*4000000) операций, что составляет... тонну. С sets, вы будете делать только (n+m) или (30000+4000000), что... намного меньше. Как в 300 000 раз меньше. В этом разница между 1,2 триллиона вещей и 0,000004 триллиона (4 миллиона) вещей.