用于删除重复项的python脚本,需要24小时+循环遍历10 ^ 7条记录

Question

输入t1
P95P,71655,LINC-JP,致病性
P95P,71655,LINC-JP,致病性
P71P,71655,LINC-JP,致病性
P71P,71655,LINC-JP,致病性

输出op
P95P,71655,LINC-JP,致病性
P71P,71655,LINC-JP,致病性

mycode的

def dup():
    fi=open("op","a")
    l=[];final="";
    q=[];dic={};
    for i in open("t1"):
        k=i.split(",")
        q.append(k[1])
        q.append(k[0])
        if q in l:
            pass
        else:
            final= final + i.strip() + "\n"
            fi.write(str(i.strip()))
            fi.write("\n")
        l.append(q)
        q=[]
        #print i.strip()
    fi.close()
    return final.strip()    
d=dup()

在上面的输入行1,2和行3,4是重复的.因此,在输出中删除了这些重复项,输入文件中的条目大约为10 ^ 7.

为什么我的代码自24小时后运行以输入76Mb文件.它还没有完成整个输入文件的一次迭代.它适用于小文件.
任何人都可以指出这么长时间的原因.我如何优化我的程序？
日Thnx

Answer 1

您正在使用O(n ²)算法,该算法对较大的文件进行缩放:

for i in open("t1"):  # linear pass of file takes O(n) time
    ...
    if q in l:  # linear pass of list l takes O(n) time
        ...
    ...

你应该考虑使用一个集合(即make la set),或者itertools.groupby重复是否总是彼此相邻.这些方法将是O(n).

Answer 2

如果您可以访问Unix系统,那么这uniq是一个很好的实用程序,可以解决您的问题.

uniq input.txt output.txt

请参阅https://www.cs.duke.edu/csl/docs/unix_course/intro-89.html

我知道这是一个Python问题,但有时Python不是任务的工具.并且您始终可以在python脚本中嵌入系统调用.