방향성 인접 목록 빠른 구현

Question

import distance 
from collections import defaultdict 

my_list = ['ACAA', 'TCAA','TCAT','TGAT','TCGA','TGGA','GCGA','AAAA','GGGG','GGGC'] 
counts = {'ACAA':60, 'TCAA':3,'TCAT':30,'TGAT':8,'TCGA':1,'TGGA':1,'GCGA':8,'AAAA':5,'GGGG':8,'GGGC':1} 

adj_list = defaultdict(list) 
for strng1 in my_list: 
    for strng2 in my_list: 
     if distance.hamming(strng1, strng2) == 1 and counts[strng1] >= (counts[strng2]*2): 
      adj_list[strng1].append(strng2) 

방향성 인접 목록을 가져 오기위한이 구현 방법이 있습니다. 예상 결과 :

ACAA: TCAA 
TCAA: TCGA 
TCAT: TCAA, TGAT 
TGAT 
TCGA: TGGA 
TGGA: TCGA 
GCGA: TCGA 
AAAA 
GGGG: GGGC 
GGGC 

더 빠른 구현이 있습니까? 이는 대용량 데이터 세트로 인해 매우 느려집니다. cython에서 이것을 재 작성하면 속도가 빨라질까요? 그렇다면 누군가가 cython을 시작하는 데 도움이 될 수 있습니까?

Answer 1

나는 사이 썬에 대해 알고하지 않습니다,하지만 당신은 내부 루프에 DICT 항목에 접근 피할 수 :

adj_list = defaultdict(list) 
for strng1 in my_list: 
    a1 = adj_list[strng1] 
    c1 = counts[strng1] 
    for strng2 in my_list: 
     if distance.hamming(strng1, strng2) == 1 and c1 >= (counts[strng2]*2): 
      a1.append(strng2) 

당신도 후반에만 반복하여 더 많은을 절감하고 대칭 APPEND을 수행 할 수 있습니다. 그렇게하면 대칭이므로 거리 계산의 50 %를 절약 할 수 있습니다. 당신은 오직 위 행렬 삼각형 (대각선을 제외하고, 나는 그 자체와 한 문자열의 거리가 0이라고 가정)을 전체 행렬 대신에 수행합니다.

for i,strng1 in enumerate(my_list): 
    ... 
    for j in range(i+1,len(my_list)): 

내 시도, 잘 모르겠지만, 근접해야합니다 :

adj_list = defaultdict(list) 
for i,strng1 in enumerate(my_list): 
    a1 = adj_list[strng1] 
    c1 = counts[strng1] 
    for j in range(i+1,len(my_list)): 
     strng2 = my_list[j] 
     if distance.hamming(strng1, strng2) == 1: 
      c2 = counts[strng2] 
      if c1 >= (c2*2): 
       a1.append(strng2) 
      if c2 >= (c1*2): 
       adj_list[strng1].append(strng2) 

crysis405 편집 :

원본 :

def adj_lst(my_list, counts): 
    adj_list = defaultdict(list) 
    for strng1 in my_list: 
     a1 = adj_list[strng1] 
     c1 = counts[strng1] 
     for strng2 in my_list: 
      if distance.hamming(strng1, strng2) == 1 and c1 >= (counts[strng2]*2): 
       adj_list[strng1].append(strng2) 

하기 권장 개선 :

def adj_lst_fast(my_list, counts): 
    adj_list_fast = defaultdict(list) 
    for i,strng1 in enumerate(my_list): 
     a1 = adj_list_fast[strng1] 
     c1 = counts[strng1] 
     for j in range(i+1,len(my_list)): 
      strng2 = my_list[j] 
      if distnace.hamming(strng1, strng2: 
       c2 = counts[strng2] 
       if c1 >= (c2*2): 
        adj_list_fast[strng1].append(strng2) 
       elif c2 >= (c1*2): 
        adj_list_fast[strng2].append(strng1) 

성능 :

print(timeit.timeit('adj_lst(my_list, counts)', number = 10000, 
setup="from __main__ import adj_lst, my_list, counts")) 

1.2892486669989012

print(timeit.timeit('adj_lst_fast(my_list, counts)', number = 10000, 
setup="from __main__ import adj_lst_fast, my_list, counts")) 

0.6437049919986748