파이썬은 파일에서 1 백만 개의 문자열을 검색하고 각 문자열의 수를 계산합니다.

Question

더 빠른 방법을 찾으려합니다. 나는 약 1 백만 개의 문자열 (길이 6-40)을 별도의 줄에 포함하고있는 file1을 가지고있다. 나는 각각 80,000 개의 문자열을 포함하는 파일 2에서 각각을 찾고 싶다. 작은 문자열이 한 번 여러 번 발견되면이 문자열의 발생은 여전히 ​​1이다. 성능 비교에 관심이있는 사용자라면 file1 및 file2를 다운로드 할 수있는 링크가 있습니다. dropbox.com/sh/oj62918p83h8kus/sY2WejWmhu?m

내가 지금하고있는 일은 파일 2에 대한 사전을 구성하고 문자열 ID를 키로 사용하고 문자열을 값으로 사용하는 것입니다. 내 코드는

for line in file1: 
    substring=line[:-1].split("\t") 
    for ID in dictionary.keys(): 
     bigstring=dictionary[ID] 
     IDlist=[] 
     if bigstring.find(substring)!=-1: 
      IDlist.append(ID) 
    output.write("%s\t%s\n" % (substring,str(len(IDlist)))) 

내 코드가 완료 시간이 걸릴 것입니다 (파일 2에서 문자열 중복 값을 가지고 있기 때문에, 단지 문자열 ID는 고유). 누구든지 빠른 방법을 제안 할 수 있습니까? file1과 file2는 모두 약 50M이며, 내 PC는 8G 메모리를 가지고 있습니다. 더 빨리 만들 필요가있을만큼 많은 메모리를 사용할 수 있습니다. 1 시간 내에 완료 할 수있는 방법은 모두 허용 가능합니다.

아래의 설명에서 몇 가지 제안을 시도한 후 성능 비교를 확인한 후 코드가 실행 시간입니다. 마크 Amery 및 다른 사람

import sys 
from Bio import SeqIO 

#first I load strings in file2 to a dictionary called var_seq, 
var_seq={} 
handle=SeqIO.parse(file2,'fasta') 
for record in handle: 
    var_seq[record.id]=str(record.seq) 

print len(var_seq) #Here print out 76827, which is the right number. loading file2 to var_seq doesn't take long, about 1 second, you shall not focus here to improve performance 

output=open(outputfilename,'w') 
icount=0 
input1=open(file1,'r') 
for line in input1: 
    icount+=1 
    row=line[:-1].split("\t") 
    ensp=row[0] #ensp is just peptides iD 
    peptide=row[1] #peptides is the substrings i want to search in file2 
    num=0 
    for ID,bigstring in var_seq.iteritems(): 
     if peptide in bigstring: 
      num+=1 

    newline="%s\t%s\t%s\n" % (ensp,peptide,str(num)) 
    output.write(newline) 
    if icount%1000==0: 
     break 

input1.close() 
handle.close() 
output.close() 

에 의해 제안

일부 개선이 완료 1m4s를 취할 것입니다. 엔트로피

from collections import defaultdict 
var_seq=defaultdict(int) 
handle=SeqIO.parse(file2,'fasta') 
for record in handle: 
    var_seq[str(record.seq)]+=1 

print len(var_seq) # here print out 59502, duplicates are removed, but occurances of duplicates are stored as value 
handle.close() 

output=open(outputfilename,'w') 
icount=0 

with open(file1) as fd: 
    for line in fd: 
     icount+=1 
     row=line[:-1].split("\t") 
     ensp=row[0] 
     peptide=row[1] 
     num=0 
     for varseq,num_occurrences in var_seq.items(): 
      if peptide in varseq: 
       num+=num_occurrences 

    newline="%s\t%s\t%s\n" % (ensp,peptide,str(num)) 
    output.write(newline) 
    if icount%1000==0: 
     break 

output.close() 

이 하나의 제안 내 이전

####### 다음의 방법에 비해 개선 된 20 대 빠르지는 중복을 검색 피할 수 있기 때문에 예상대로 이유를 이해하지 않습니다 1m10s 걸립니다.

Mark Amery가 제안한 Haystack과 Needle 방법이 가장 빠름이 밝혀졌습니다.이 방법의 문제점은 모든 하위 문자열의 계산 결과가 0이라는 점입니다. 아직 이해할 수 없습니다.

다음은 그의 메소드를 구현 한 코드입니다.

class Node(object): 
    def __init__(self): 
     self.words = set() 
     self.links = {} 

base = Node() 

def search_haystack_tree(needle): 
    current_node = base 
    for char in needle: 
     try: 
      current_node = current_node.links[char] 
     except KeyError: 
      return 0 
    return len(current_node.words) 

input1=open(file1,'r') 
needles={} 
for line in input1: 
    row=line[:-1].split("\t") 
    needles[row[1]]=row[0] 

print len(needles) 

handle=SeqIO.parse(file2,'fasta') 
haystacks={} 
for record in handle: 
    haystacks[record.id]=str(record.seq) 

print len(haystacks) 

for haystack_id, haystack in haystacks.iteritems(): #should be the same as enumerate(list) 
    for i in xrange(len(haystack)): 
     current_node = base 
     for char in haystack[i:]: 
      current_node = current_node.links.setdefault(char, Node()) 
      current_node.words.add(haystack_id) 

icount=0 
output=open(outputfilename,'w') 
for needle in needles: 
    icount+=1 
    count = search_haystack_tree(needle) 
    newline="%s\t%s\t%s\n" % (needles[needle],needle,str(count)) 
    output.write(newline) 
    if icount%1000==0: 
     break 

input1.close() 
handle.close() 
output.close() 

완료하는 데 단지 0m11s 밖에 걸리지 않으며 다른 방법보다 훨씬 빠릅니다. 그러나 모든 계산 결과를 0으로 만드는 것이 내 실수인지 또는 Mark의 방법에 결함이 있는지는 알지 못합니다.

Answer 1

귀하의 코드가 작동처럼 (당신이 방금 대신 실제 코드를 붙여의 메모리에서 인용하지 않았다 확실?)하지 않는 것 같습니다 예를 들어

,이 라인 :

substring=line[:-1].split("\t") 

은 substring을 목록으로 만듭니다. 하지만 나중에 당신이 할 : 당신이 str.find(list)를 호출 할 경우 오류가 발생합니다

if bigstring.find(substring)!=-1: 

.

어쨌든 가장 안쪽 루프에 쓸모없는 목록을 작성하고 있습니다. 이 :

IDlist=[] 
if bigstring.find(substring)!=-1: 
    IDlist.append(ID) 

#later 
len(IDlist) 

쓸데없이 메모리를 할당하고 해제 스레 싱을 야기 목록뿐만 아니라이 쓸데없이 아래로 모든 것을 늦추지 것이다.

from collections import defaultdict 

dictionary = defaultdict(int) 
with open(file2) as fd: 
    for line in fd: 
     for s in line.split("\t"): 
      dictionary[s.strip()] += 1 

with open(file1) as fd: 
    for line in fd: 
     for substring in line.split('\t'): 
      count = 0 
      for bigstring,num_occurrences in dictionary.items(): 
       if substring in bigstring: 
        count += num_occurrences 
      print substring, count 

추신 : 난 당신이 몇 가지 line.split("\t")을하기 때문에 탭으로 분리되어 줄에 여러 단어를 가지고 있다고 가정하고

이

작동하고 계산을하는 것이 더 효율적 수단을 사용한다 코드 포인트. 이것이 틀린 경우, 코드를 수정하는 것이 쉬워야합니다.

PPS : 사용하기에 너무 느려지는 경우 (시도해보아야하지만 내 생각에 10 밀리미터에서 실행해야한다고 가정합니다). 제안 된 의견 중 하나로 접미어 트리를 사용해야합니다. 시간을 최대 공간을 무역 :

편집 : 부정적인 성능

편집 2에 영향을주지 않고 file2에서 동일한 문자열을 여러 번 처리하도록 코드를 개정.

다음은 상당한 메모리를 소비하고 사전을 작성하는 데 걸리는 코드입니다. 그러나 검색이 끝나면 백만개의 문자열 중에서 검색 할 각 검색은 단일 해시 테이블 조회 (즉, O(1))에 소요되는 시간 내에 완료되어야합니다.

참고 : 프로세스의 각 단계에 소요되는 시간을 기록하기 위해 몇 가지 명령문을 추가했습니다. 검색 할 때 어느 부분을 취했는지 알 수 있도록 보관해야합니다. 1000 개의 문자열로 테스트하기 때문에 이것은 중요합니다. 왜냐하면 90 %의 비용이 검색 시간이 아닌 빌드 시간 일 경우, 1M 문자열로 테스트 할 때 여전히 한 번만 수행하므로, 그렇게하지 않을 것입니다.

from Bio import SeqIO 
from collections import defaultdict 
from datetime import datetime 

def all_substrings(s): 
    result = set() 
    for length in range(1,len(s)+1): 
     for offset in range(len(s)-length+1): 
      result.add(s[offset:offset+length]) 
    return result 

print "Building dictionary...." 
build_start = datetime.now() 

dictionary = defaultdict(int) 
handle = SeqIO.parse(file2, 'fasta') 
for record in handle: 
    for sub in all_substrings(str(record.seq).strip()): 
     dictionary[sub] += 1 
build_end = datetime.now() 
print "Dictionary built in: %gs" % (build-end-build_start).total_seconds() 

print "Searching...\n" 
search_start = datetime.now() 

with open(file1) as fd: 
    for line in fd: 
     substring = line.strip().split("\t")[1] 
     count = dictionary[substring] 
     print substring, count 

search_end = datetime.now() 
print "Search done in: %gs" % (search_end-search_start).total_seconds() 

Answer 2

을 내가 알고리즘 재능이 아니에요 : 문제

또한 나는 당신이 당신이 단지에서 이것을 연결하고 테스트 할 수 있어야하므로, 파일 1과 파일 2 구문 분석을 내 코드를 수정 한 점에 유의 그러나 나는 이것이 당신에게 건강한 성능 향상을 가져다 줄 것이라고 생각한다. 'haystacks'를보고 싶은 큰 단어의 목록으로 설정하고 찾고있는 부분 문자열의 목록을 '바늘'로 지정해야합니다 (사본을 포함 할 수 있음). 끝까지 구현하십시오. 제안 된 솔루션의 성능을 쉽게 비교할 수 있도록 바늘 목록과 건초 더미 목록을 게시 할 수 있다면 좋을 것입니다.

haystacks = <some list of words> 
needles = <some list of words> 

class Node(object): 
    def __init__(self): 
     self.words = set() 
     self.links = {} 

base = Node() 

for haystack_id, haystack in enumerate(haystacks): 
    for i in xrange(len(haystack)): 
     current_node = base 
     for char in haystack[i:]: 
      current_node = current_node.links.setdefault(char, Node()) 
      current_node.words.add(haystack_id) 

def search_haystack_tree(needle): 
    current_node = base 
    for char in needle: 
     try: 
      current_node = current_node.links[char] 
     except KeyError: 
      return 0 
    return len(current_node.words) 

for needle in needles: 
    count = search_haystack_tree(needle) 
    print "Count for %s: %i" % (needle, count) 

당신은 아마 코드를보고 일어나고, 그러나 다만 단어에 넣어 알아낼 수 있습니다 : 나는 건초 더미 단어의 문자열의 거대한 트리를 구성하는 모든 바늘 주어, 당신은 탐색 할 수 있도록 트리 문자를 문자 단위로 처리하고 그 하위 문자열이 포함 된 haystack의 모든 haystack ID 집합을 노드에 연결 한 노드로 끝납니다. 다음 각 바늘을 위해 우리는 다만 나무를 통해서 가고 끝에 세트의 크기를 센다.