优化此代码：python list iter 用于比较 2 个列表

Question

def cross(listMaster, listSlave, criteria="email"):

    if criteria == "email":

        emailListSlave = []

        returnUnique = []

        for item in listSlave: 

            emailListSlave.append(item[2]) #appends emails

        for no,item in enumerate(listMaster):

            if no % 10000 == 0: 

                print("Status: {percent:.2f} %".format(percent=(no/len(listMaster))))

            if item[2] not in emailListSlave:

                returnUnique.append(item)

        return returnUnique

我有 2 个列表：listMaster 和 listSlave。这两个列表都有大约 2,000,000 个项目，其中包含大约 24 个项目。我的目标是按列表中的第三个元素（恰好是电子邮件）对列表进行“排序”。然后我想在主从列表之间找到唯一的电子邮件。因此，如果从列表在主列表中存在电子邮件，则丢弃该项目并继续。

我的算法：

1) 将 Slave 列表 (email) 中每一项的第 3 个元素加载到新列表 (emailListSlave) 中

2）遍历MasterList，检查MasterList中每一项的第三个元素是否在emailListSlave中

3) 如果 2 为 True，则继续，如果为 false，则附加 returnUnique 列表，其中包含仅在 listMaster 中找到的唯一电子邮件

运行这个非常慢。我设法在大约 20 分钟内完成了 10%。我可以用 iter 加速这个过程吗？迭代工具？请帮我优化这段代码。

Answer 1

这是您的解决方案......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 lookuploop 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()])...一旦生成了这些（注意每个文件有 20k，因为生成 200 万的时间太长了），我构建了以下测试套件来比较不同的方法......import csvimport unittestemail = 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 秒。那快了几个数量级。

Answer 2

它如此缓慢的原因是搜索是在线性时间内进行的。使用关键字作为搜索字符串的字典。应该有很大的不同。