TL; DR: вот ваше решение ...
def cross(listMaster, listSlave, criteria="email"):
if criteria == "email":
returnUnique = listMaster[:] # create a copy of the master list
emails_in_master = set()
for item in listMaster:
emails_in_master.add(item[2]) # add the master emails to the set
for item in listSlave:
if item[2] in emails_in_master:
returnUnique.append(item)
return returnUnique
Ваш алгоритм O (n ^ 2), потому что вы перебираете список, затем ищите другой список за итерацию выше.Это приводит к экспоненциальному времени выполнения, которое в принципе является худшим, которое вы можете получить.Вам нужно попытаться довести алгоритм до линейной сложности, чтобы иметь достойное время выполнения.
Ваш алгоритм в основном следующий:
loop for n: # this costs n
loop for n: # this costs n for each of the n's above
add an item or continue # so total, this is O(n * n)
Вам нужно следующее:
loop for n: # this costs n
build a lookup
loop for n: # this costs n
add item if in lookup or continue # so total, this is O(n)
Я сгенерировал тестовые данные в CSV на моей локальной машине.Вот как я создал CSV-файлы ...
>>> import csv
>>> from faker import Faker
>>> fake = Faker()
>>> with open('masters.csv', 'wb') as csvfile:
... writer = csv.writer(csvfile, delimiter=',', quotechar='"')
... for i in range(20000):
... writer.writerow([fake.name(), fake.address(), fake.email(), fake.job(), fake.ssn()])
...
>>> with open('slaves.csv', 'wb') as csvfile:
... writer = csv.writer(csvfile, delimiter=',', quotechar='"')
... for i in range(20000):
... writer.writerow([fake.name(), fake.address(), fake.email(), fake.job(), fake.ssn()])
...
После того, как они были сгенерированы (обратите внимание, что на файл приходилось 20 КБ, так как 2 миллиона потребовалось бы слишком много времени для генерации), я создал следующий набор тестов длясравните различные подходы ...
import csv
import unittest
email = lambda l: l[2]
class TestListComparison(unittest.TestCase):
@classmethod
def setUpClass(cls):
cls.masters = []
cls.slaves = []
with open('masters.csv', 'rb') as master_csv:
reader = csv.reader(master_csv, delimiter=',', quotechar='"')
cls.masters = list(reader)
with open('slaves.csv', 'rb') as slave_csv:
reader = csv.reader(slave_csv, delimiter=',', quotechar='"')
cls.slaves = list(reader)
def test_make_sure_lists_are_well_formed(self):
self.assertEqual(len(self.masters), len(self.slaves))
self.assertEqual(len(self.masters), 20000)
def test_list_combination_original(self):
emailListSlave = []
returnUnique = []
for item in self.slaves:
emailListSlave.append(email(item))
for no, item in enumerate(self.masters): # O(n)
if email(item) not in self.slaves: # O(n)
returnUnique.append(item) # O(1)
# Total complexity: O(n * n * 1) => O(n^2)
def test_list_combination_using_lookup(self):
lookup = set()
returnUnique = self.masters[:] # create a copy of masters list
for master in self.masters: # loop over the master list O(n)
lookup.add(email(master)) # add the email to the set O(1)
for slave in self.slaves: # loop over the list again O(n)
if email(slave) in lookup: # check the lookup O(1)
returnUnique.append(slave) # add the item to the list O(1)
# Total complexity: O(n + n) => O(2n) => O(n)
Вот результаты выполнения:
Обратите внимание, что проверка поиска заняла около15 мс, в то время как оригинальный алгоритм занял около 14 с.Это на несколько порядков быстрее.