python - 使用基本库优化python代码

Question

我正在尝试在具有 170 万行和 4 个变量的表上使用基本 python 进行非等自连接。
数据如下所示:

product     position_min     position_max      count_pos
A.16        167804              167870              20
A.18        167804              167838              15
A.15        167896              167768              18
A.20        238359              238361              33
A.35        167835              167837              8

这里是我使用的代码:

import csv
from collections import defaultdict
import sys
import os

list_csv=[]
l=[]
with open(r'product.csv', 'r') as file1:
    my_reader1 = csv.reader(file1, delimiter=';')
    for row in my_reader1:
        list_csv.append(row)
with open(r'product.csv', 'r') as file2:
    my_reader2 = csv.reader(file2, delimiter=';') 
    with open('product_p.csv', "w") as csvfile_write:
        ecriture = csv.writer(csvfile_write, delimiter=';',
                                quotechar='"', quoting=csv.QUOTE_ALL)
        for row in my_reader2:
            res = defaultdict(list)
            for k in range(len(list_csv)):
                comp= list_csv[k]
                try:
                    if int(row[1]) >= int(comp[1]) and int(row[2]) <= int(comp[2]) and row[0] != comp[0]:
                        res[row[0]].append([comp[0],comp[3]]) 
                except:
                    pass
            


            if bool(res):    
                for key, value in res.items():
                    sublists = defaultdict(list)
                    for sublist in value:
                        l=[]
                        sublists[sublist[0]].append(int(sublist[1]))
                    l.append(str(key) + ";"+ str(min(sublists.keys(), key=(lambda k: sublists[k]))))
                        ecriture.writerow(l)

我应该在“product_p.csv”文件中得到这个:

'A.18'; 'A.16'
'A.15'; 'A.18'
'A.35'; 'A.18' 

代码的作用是读取同一个文件两次，第一次完全，并将其转换为列表，第二次逐行查找每个产品(第一个变量)所属的所有产品根据 position_min 和 position_max 上的条件，然后通过保留具有 count_pos 最小值的产品只选择一个。
我在原始数据的样本上尝试了它，它可以工作，但是有 170 万行，它运行了几个小时而没有给出任何结果。
有没有办法在没有循环或更少循环的情况下做到这一点？任何人都可以帮助使用基本的 python 库优化它吗？
先感谢您

Answer 1

我认为这里需要一种不同的方法，因为将每个产品相互比较总是会给出 O(n^2) 的时间复杂度。
我按升序对产品列表进行排序 position_min (并降序 position_max ，以防万一)并从上面的答案中反转检查:而不是查看是否 comp “包含”ref我做了相反的事情。通过这种方式，可以仅针对具有较高 position_min 的产品检查每个产品。 , 并尽快停止搜索 comp找到谁的 position_min高于 position_max的 ref .
为了测试这个解决方案，我生成了一个包含 100 个产品的随机列表，并运行了从上面的答案复制的一个函数和一个基于我的建议的函数。后者执行大约 1000 次比较而不是 10000 次，根据 timeit尽管由于初始排序而产生开销，但它的速度大约快了 4 倍。
代码如下:

##reference function
def f1(basedata):
    outd={}
    for ref in basedata:
        for comp in basedata:
            if ref == comp:
                continue
            elif ref[1] >= comp[1] and ref[2] <= comp[2]:
                if not outd.get(ref[0], False) or comp[3] < outd[ref[0]][1]:
                    outd[ref[0]] = (comp[0], comp[3])
    return outd

##optimized(?) function
def f2(basedata):
    outd={}
    sorteddata = sorted(basedata, key=lambda x:(x[1],-x[2]))
    runs = 0
    for i,ref in enumerate(sorteddata):
        toohigh=False
        j=i
        while j < len(sorteddata)-1 and not toohigh:
            j+=1
            runs+=1
            comp=sorteddata[j]
            if comp[1] > ref[2]:
                toohigh=True
            elif comp[2] <= ref[2]:
                if not outd.get(comp[0], False) or ref[3] < outd[comp[0]][1]:
                    outd[comp[0]] = (ref[0], ref[3])
    print(runs)
    return outd