python - 更快地比较两个列表

问题描述

我试图对两个文件进行比较，这些文件大约有 70k 行，而我目前的算法需要大约 5 分钟才能完全比较所有文件。

本质上，我所做的是将两个文件的所有行都放入列表中，因此看起来像这样。

    compare_list_new=[['Albert','V4','25.000','45.000','1.3500'], 
     ['James','V4','22.000','43.000','1.4000'], ['James','V5','23.000','41.000','1.3000']]

    compare_list_old=[['Albert','V4','25.000','45.000','1.3900'], 
     ['James','V4','22.000','43.000','1.2000'], ['James','V5','23.000','41.000','1.2000']]

这个想法是两个文件具有相似的名称，因此要在旧条目中找到新条目，我们必须根据坐标进行搜索，所以如果我想从新到旧找到特定的 James，我必须使用 ' 22.000'，'43.000'。

找到条目后，我从新文件中取出 1.4000，从旧文件中取出 1.2000，然后减去它们以找到从旧文件到新文件的增量。

这是我使用的当前算法：

    # This is not important
    import time
    import timeit
    import bisect
    from operator import itemgetter
    import time


    compare=open("factor.output.new.txt","w")
    compare_list_new=[]
    compare_list_old=[]
    newlist=[]

    #File Count algorithm

    start = time.time() # Tracks execution time

    def list_create(fname):  #Makes the list in the appropriate format
         newlist=[]
         with open(fname) as file:
              for i, line in enumerate(file):
                  if i>6:
                     for line in file:
                         lines_list=line.split(" ")
                         del lines_list[0]
                         del lines_list[2:29]
                         del lines_list[5:12]
                         newlist.append(lines_list)
         return newlist



     #Creates lists and sorts them

     compare_list_new=list_create("par_iop.pwr.sfactor.output_new.ipf")
     compare_list_new=sorted(compare_list_new, key=itemgetter(2))
     compare_list_old=list_create("par_iop.pwr.sfactor.output_old.ipf")
     compare_list_old=sorted(compare_list_old, key=itemgetter(2))



    compare.write("Name Version Coordinate_x Coordinate_y Sfactordelta FLAG\n")
    compare_list_copy=compare_list_old #Makes a copy of the list


    for item in compare_list_new: # compares both lists
        end = time.time()
        print(end - start)
        for line in compare_list_old:
            if item[0:4] == line[0:4]:
               s1=float(item[4])
               s2 = float(line[4])
               delta=s1-s2
               delta=format(delta,'.4f')
               item[4]=str(delta)
               text = " ".join(item)
               compare.write(text +"  " +"\n")
               compare_list_copy.remove(line)
               match=1
               break
         if(match==1):
            compare_list_old=compare_list_copy
            match=0
         else:
            text=" ".join(item)
            compare.write(text + "  " + "ITEM NOT FOUND IN OLD FILE BUT IS IN NEW FILE""\n")
            try:
               compare_list_copy.remove(line)
            except ValueError:
                  pass
            compare_list_old = compare_list_copy
    compare.close()

本质上，比较两者的部分列出了它在对它们进行排序后所做的事情，如果它们匹配，那么它将执行获取增量并将其从副本中删除的操作，然后使旧的等于副本，这样它就不会删除项目而遍历列表。如果该项目不匹配，则表示不在旧文件中，但在新文件中。

我想要一些可能使这个过程更快的东西。

标签： pythonalgorithm

解决方案

这里有很多代码，而且缩进明显不正确，所以我什至不知道逻辑到底应该是什么，也没有迹象表明你认为哪个部分很慢（或者你怎么知道），但有一件事立马跳出来：

compare_list_copy.remove(line)

……还有一个remove稍后。

首先，无论何时调用lst.remove(val)，列表都必须进行线性搜索，将每个元素与val. 但是你已经知道了你想要的元素的索引（或者更确切地说，你可以通过使用知道它enumerate），所以整个搜索都是浪费的；只是del lst[idx]相反。

其次，无论是您remove还是del，您仍在从数组中间删除。这意味着将所有后续元素向上移动一个插槽。它有一个更快的常数（它只是一个大内存移动，而不是一堆对比较函数的调用），但它仍然是线性的。

而你在你的内部循环中这样做。所以，你在N已经是二次方的时间上增加了一个额外的因子。bisect如果您只是按照对数搜索对相同数据进行线性搜索，那么您在对数时间而不是线性时间中进行搜索的任何努力都将被浪费。

如果你需要一些东西，你可以在对数时间内搜索，也可以在对数时间内修改，你想要的是某种树（或树列表结构，如跳过列表）。PyPI 上有很好的库包含各种二叉树和 b 树变体，或者您可以在 Wikipedia 上查找算法。

或者，您可以直接获取诸如 Sorted Containers 库之类的东西，该库将事物包装在更高级别。例如， a 的sorteddict行为很像 a dict，但您可以搜索最近的键而不是精确匹配，或者搜索给定范围内的所有键等。在幕后，它可以与某种混合的 btree 绳索一起使用什么的，但你不需要关心那些细节；重要的是它保证了您在对数时间内所需的所有操作。

完成此操作后，您的两个外部循环中的至少一个也可以有利地变成对数搜索（使用树几乎可以免费获得）。

此时您的总时间是O(log**2 N * N)而不是O(N**3)，这是一个巨大的差异。

如果您不习惯用算法复杂性术语来处理性能，请考虑一下：只有 1000 个元素，立方时间1000*1000*1000= 10 亿步；对数平方线性时间需要10*10*1000= 100,000 步。这就是天和秒之间的区别。

python - 更快地比较两个列表

问题描述

解决方案

推荐阅读