python - python中的计算时间非常长

Question

我正在运行我的代码，其中包括查找平均值。在大约 600 万行的 CSV (ssm_resnik.txt) 中，第一行是一个引用，第二行是另一个，第三个值是两个引用之间的“距离”。这种距离是由对这个问题不重要的生物学标准任意定义的。大多数参考将与...大多数参考相对，因此具有超过 600 万行的巨大 CSV。在另一个 CSV（all_spot_uniprot.txt）中，我有大约 3600 个点（第一列），每个点都有一个或多个参考（第三列）。这些值与巨大的 CSV 相同。我需要将第二个文件的点 ref 的每个 3600 与同一文件中的所有其他 3600-1 ref 进行比较。所有可能的组合（如果存在）都在第一个巨大的 CSV 文件 (ssm_resnik.txt) 中。

我的代码有什么问题？嗯...每次迭代 10 秒，3600 *3600 *10 = 129.600.000 秒 = 1500 天（几乎 5 年）。这发生在我的核心 i3 中，但在 mac 中很好。下面是我的代码和每个文件的一部分。请给我建议。有什么代码设计缺陷？有什么方法可以减少计算时间？提前致谢...

import csv

spot_to_uniprot=open('all_spot_uniprot.txt', 'rbU')
STU=csv.reader(spot_to_uniprot, delimiter='\t')

uniprot_vs_uniprot=open('ssm_resnik.txt', 'rbU')
allVSall= csv.reader(uniprot_vs_uniprot, delimiter='\t')

recorder=open('tabela_final.csv', 'wb')
fout=csv.writer(recorder, delimiter='\t', quotechar='"')

dict_STU={} #dicionário 'spot to uniprot'
dict_corresp={} #for each pair of uniprot ref as key and as value
#a list of lists with the first list as one spot and the second list is the spot+1
dict_corresp_media={}##average of one spot to other
total_correspondencias_x_y=[]
_lista_spot=[]
lista_spot=[]
lista_temp=[]
lista_CSV=[]

for a in STU:
    _lista_spot.append(int(a[0]))
    if a[0] not in dict_STU.keys():
        dict_STU[a[0]]=[]
        dict_STU[a[0]].append(a[2])
    else:        
        dict_STU[a[0]].append(a[2])
n_spot=max(_lista_spot)

spot_to_uniprot.close()

##for aa in _lista_spot:
##    lista_spot.append(int(aa))
##lista_spot.sort()

for i in allVSall:
    lista_CSV.append(i)
tuple_CSV=tuple(lista_CSV)

uniprot_vs_uniprot.close()

for h in range(1, n_spot):
    for _h in range(h+1, n_spot+1):
        #print h, 'h da lista_spot'
        del total_correspondencias_x_y[:]
        total_correspondencias_x_y.append(dict_STU[str(h)])
        #print h, 'h'
        #print _h, '_h'
        #print __h, '__h'
        total_correspondencias_x_y.append(dict_STU[str(_h)])
        print total_correspondencias_x_y, 'total_corresp_x_y'

        for c1 in total_correspondencias_x_y[0]:
            if c1=='No Data':
                pass
            else:
                for c2 in total_correspondencias_x_y[1]:
                    if c2=='No Data':
                        pass
                    else:
                        #print c1, c2, 'c1 e c2'
                        for c3 in lista_CSV:
                            if c1 in c3[0]:
                                if c2 in c3[1]:
                                    lista_temp.append(c3[2])
                                    print lista_temp, 'lista_temp'

        elements=len(lista_temp)
        if len(lista_temp)==0:
            dict_corresp_media[str(h)+'_'+str(_h)]=0
        else:
            temp_d=0
            for d in lista_temp:
                temp_d +=float(d)
            media_spots=temp_d/elements
            dict_corresp_media[str(h)+'_'+str(_h)]=media_spots

        print dict_corresp_media[str(h)+'_'+str(_h)]
        lista_temp=[]

recorder.close()

这是我文件的一部分：

all_spot_uniprot.txt

1   spr0001 Q8DRQ4
1   SP0001  O08397
1   SPN01072    B5E568
2   spr0002 P59651
2   SP0002  O06672
2   SPN01074    B5E569
3   spr0005 Q8DRQ2
3   SP0005  Q97TD1
3   SPN01078    B5E572
4   spr0006 Q8DRQ1
4   SP0006  Q97TD0
4   SPN01079    B5E573
5   spr0009 Q8DRQ0
5   SP0009  Q97TC7
6   spr0010 Q8DRP9
6   SP0011  Q97TC5
6   SPN01085    B5E578
7   spr0012 P59652
7   SP0013  O69076
7   SPN01087    B5E580
8   spr0017 Q8DRP6
8   SP0017  No Data
8   SPN01090    B5E5G4
9   spr0020 Q8CZD0
9   SP0018  Q97TC2
9   SPN01093    B5E5G7
10  spr0021 P65888
10  SP0019  P65887
..  ......  ......  ......
..  ......  ......  ......
3617    spr2016 Q8DMY7
3617    spr0324 Q8DR62
3617    SP2211  No Data
3617    SP1311  No Data
3617    SP1441  No Data
3617    SPN11022    No Data
3617    SPN01038    No Data
3617    SPN08246    No Data
3618    spr2018 Q8DMY5
3618    SP0812  No Data
3618    SP2213  No Data
3618    SPN04196    B5E3J0
3618    SPN01040    B5E3V9
3619    spr2040 Q8DMW6
3619    SP2234  Q97N38
3619    SPN01065    B5E462
3620    spr2043 P60243

ssm_resnik.txt

Q8DRQ4  O08397  1.0
Q8DRQ4  B5E568  1.0
Q8DRQ4  P59651  0.12077157944440875
Q8DRQ4  O06672  0.12077157944440875
Q8DRQ4  B5E569  0.12077157944440875
Q8DRQ4  Q8DRQ1  0.12077157944440875
Q8DRQ4  Q97TD0  0.12077157944440875
Q8DRQ4  B5E573  0.12077157944440875
Q8DRQ4  Q8DRP9  0.07139907404780385
Q8DRQ4  Q97TC5  0.07139907404780385
Q8DRQ4  B5E578  0.07139907404780385
Q8DRQ4  P59652  0.04789965413510797
Q8DRQ4  O69076  0.04789965413510797
Q8DRQ4  B5E580  0.04698170092888175
Q8DRQ4  Q8DRP6  0.12077157944440875
Q8DRQ4  P65888  0.05619465373456477
Q8DRQ4  P65887  0.05619465373456477
Q8DRQ4  B5E5G8  0.05619465373456477
Q8DRQ4  Q8DRP3  0.0115283466875553
Q8DRQ4  Q97TC0  0.0115283466875553
Q8DRQ4  B5E5G9  0.0115283466875553
Q8DRQ4  Q8DRP2  0.05619465373456477
Q8DRQ4  Q97TB9  0.05619465373456477
Q8DRQ4  B5E5H1  0.05619465373456477
Q8DRQ4  Q8DRP0  0.12077157944440875
Q8DRQ4  B5E5H3  0.12077157944440875
Q8DRQ4  Q8DNI4  0.12077157944440875
Q8DRQ4  Q8CWP0  0.12077157944440875
Q8DRQ4  Q97CV3  0.12077157944440875
Q8DRQ4  Q97P52  0.12077157944440875
O08397  Q97PH8  0.12077157944440875
O08397  P59200  0.10979991157849654
O08397  P59199  0.10979991157849654
O08397  B5E5I1  0.12077157944440875
O08397  Q8DRN5  0.047725405544042546
O08397  Q97TA8  0.047725405544042546
O08397  B5E5I4  0.047725405544042546
O08397  Q8DRN4  0.1555714706579846
O08397  Q97TA7  0.1555714706579846
O08397  B5E5I5  0.1555714706579846
O08397  Q97TA6  0.02938784938305615
O08397  Q8DRN2  0.02938784938305615
O08397  Q9F7T4  0.02938784938305615
O08397  P59653  0.04191624792292713
O08397  Q03727  0.04191624792292713
O08397  B5E5J1  0.045754049904644475
O08397  P59654  0.01167129073292015
O08397  P36498  0.01167129073292015
O08397  B5E5J2  0.0
O08397  Q8DRM7  0.05619465373456477
O08397  Q07296  0.05619465373456477
O08397  B5E5J3  0.05619465373456477
O08397  Q97TA3  0.05619465373456477
O08397  B5E5J5  0.05619465373456477
O08397  Q97T99  0.05619465373456477
O08397  Q8DRL9  0.05619465373456477
O08397  Q97T96  0.05619465373456477
O08397  B5E5K1  0.05619465373456477
O08397  Q97T95  0.05619465373456477
O08397  Q8DRL7  0.05619465373456477

Answer 1

600 万行可以保存在内存或 SQLite 数据库中。把它放在那里并利用提供的查找优化：

with open('ssm_resnik.txt', 'rbU') as uniprot_vs_uniprot:
    reader = csv.reader(uniprot_vs_uniprot, delimiter='\t')
    allVSall = { tuple(r[:2]): float(r[2]) for r in reader }

现在allVSall是一个提供 O(1) 查找的映射；这使您不必为生成的每个组合循环遍历整个 600 万行。那是节省了很多循环。

collections.defaultdict阅读all_spot_uniprot列表时使用 a更容易：

from collections import defaultdict

dict_STU = defaultdict(list)
with open('all_spot_uniprot.txt', 'rbU') as spot_to_uniprot:
    reader = csv.reader(spot_to_uniprot, delimiter='\t')
    for row in reader:
        dict_STU[int(row[0])].append(row[2])

无需在max此处查找值，只需列出键并将它们传递给itertools.permutationsanditertools.product函数以生成组合。

以下代码以更紧凑的形式复制了您的代码，列表更少，字典查找 O(1)，因此循环更少：

from itertools import permutations, product, ifilter

no_no_data = lambda v: v != 'No Data'
dict_corresp_media = {}

for a, b in permutations(dict_STU.iterkeys(), r=2):
    # retrieve the a and b lists of possible keys, for which we need to loop over their products
    # we filter each for the `No Data` keys
    aval, bval = ifilter(no_no_data, dict_STU[a]), ifilter(no_no_data, dict_STU[b])

    matches = [allVSall[c1, c2] for c1, c2 in product(aval, bval) if (c1, c2) in allVSall]
    dict_corresp_media['{}_{}'.format(a, b)] = sum(matches) / len(matches) if matches else 0

对于您的输入样本，它会在几分之一秒内吐出：

>>> pprint.pprint(dict_corresp_media)
{'10_1': 0,
 '10_2': 0,
 '10_3': 0,
 '10_4': 0,
 '10_5': 0,
 '10_6': 0,
 '10_7': 0,
 '10_8': 0,
 '10_9': 0,
 '1_10': 0.05619465373456477,
 '1_2': 0.12077157944440875,
 '1_3': 0,
 '1_4': 0.12077157944440875,
 '1_5': 0,
 '1_6': 0.07139907404780385,
 '1_7': 0.04759366973303256,
 '1_8': 0.12077157944440875,
 '1_9': 0,
 '2_1': 0,
 '2_10': 0,
 '2_3': 0,
 '2_4': 0,
 '2_5': 0,
 '2_6': 0,
 '2_7': 0,
 '2_8': 0,
 '2_9': 0,
 '3_1': 0,
 '3_10': 0,
 '3_2': 0,
 '3_4': 0,
 '3_5': 0,
 '3_6': 0,
 '3_7': 0,
 '3_8': 0,
 '3_9': 0,
 '4_1': 0,
 '4_10': 0,
 '4_2': 0,
 '4_3': 0,
 '4_5': 0,
 '4_6': 0,
 '4_7': 0,
 '4_8': 0,
 '4_9': 0,
 '5_1': 0,
 '5_10': 0,
 '5_2': 0,
 '5_3': 0,
 '5_4': 0,
 '5_6': 0,
 '5_7': 0,
 '5_8': 0,
 '5_9': 0,
 '6_1': 0,
 '6_10': 0,
 '6_2': 0,
 '6_3': 0,
 '6_4': 0,
 '6_5': 0,
 '6_7': 0,
 '6_8': 0,
 '6_9': 0,
 '7_1': 0,
 '7_10': 0,
 '7_2': 0,
 '7_3': 0,
 '7_4': 0,
 '7_5': 0,
 '7_6': 0,
 '7_8': 0,
 '7_9': 0,
 '8_1': 0,
 '8_10': 0,
 '8_2': 0,
 '8_3': 0,
 '8_4': 0,
 '8_5': 0,
 '8_6': 0,
 '8_7': 0,
 '8_9': 0,
 '9_1': 0,
 '9_10': 0,
 '9_2': 0,
 '9_3': 0,
 '9_4': 0,
 '9_5': 0,
 '9_6': 0,
 '9_7': 0,
 '9_8': 0}

Answer 2

当脚本需要很长时间时，我会：

python -m cProfile myscript.py

我在一段时间后停止脚本。并且输出总结了在任何功能和模块中花费的时间。数字越大，问题就出在哪里。

在那里寻找其他分析方法：如何分析 python 脚本？

此外，就像评论建议的那样，您也可以考虑使用专用数据库。

Answer 3

您的程序的复杂性似乎远高于问题的复杂性。使用 cProfile 或 PyPy 之类的东西（或者甚至在 C 中重新实现，就此而言）将帮助您加快程序的某些部分，但不会解决基本问题 - 嵌套for循环。

看看你是否可以用更扁平的方式重写算法。请记住，这是 Python 和flat is better than nested.

Answer 4

如果您的代码具有较差的渐近复杂性，那么优化将无济于事。想想你是否可以简化你的问题。例如，您真的需要检查所有 N*N 对吗？也许你可以提前丢弃一些对？