优化此代码：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 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()])

...

一旦生成了这些（注意每个文件有 20k，因为生成 200 万的时间太长了），我构建了以下测试套件来比较不同的方法......

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 秒。那快了几个数量级。

Answer 2

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