実行時間がGCスキューに長すぎます

Question

現在、スキューの違いを分析するスクリプトを作成しています。残念ながら、私の問題は、文字列の長さが長くなるとランタイムが長くなり、私の答えを計算することができないということです。

def SkewGC(file): 
    countG = 0 
    countC = 0 
    diffGtoC = "" 
    # first, we need to find number of G's. 
    # the idea is, if G appears, we add it to the count. 
    # We'll just do the same to each one. 
    for pos in range(0,len(file)): 
     if file[pos] == "G": 
      countG = countG+1 
     if file[pos] == "C": 
      countC = countC+1 
     diffGtoC = diffGtoC + str(countG-countC) + "," 
    return diffGtoC.split(",") 

SkewGCArray = SkewGC(data) 
# This because I included extra "," at the end... 
SkewGCArray = [int(i) for i in SkewGCArray[:len(SkewGCArray)-1]] 

def min_locator(file): 
    min_indices = "" 
    for pos in range(0,len(file)): 
     if file[pos] == min(file): 
      min_indices = min_indices + str(pos) + " " 
    return min_indices 

print min_locator(SkewGCArray) 

本質的に、このスクリプトは、GおよびC（DNA中のヌクレオチドに対応する）の数を算出し、各位置での差を取得し、Iは、最小のインデックスを検索しようとしています。 （入力文字列ですが）長さが大きくなると、90000+のようにでもスクリプトは実行されますが、妥当な時間（約4-5分）で解答を解決することはできません。

誰でも私にできることを教えてくれますか？私は、差を取る方が良いかどうか（diffGtoC）、それを最小値として設定し、最小値を置き換えて何か違うものが見えるまでそれぞれの差を再計算するかどうかについて考えました。

しかし、私がこのアプローチで心配していたのは、最小の指標を見つけて保持することです。私が言えば、値を持つ配列を有していた：

を[-4、-2、-5、-6、-5、-6]

私は最小値（-4変更する方法を見ることができます - 5、次に-6）は、アルゴリズムのランタイムの点ではより速くなりますが、どのようにして-6の位置を維持することができますか？これが完全に理解できるかどうかはわかりません。あなたのコードのパフォーマンスを向上させる

Answer 1

いくつかの提案：

diffGtoC = diffGtoC + str(countG-countC) + "," 
    return diffGtoC.split(",") 

がに実際に等価です：

diffGtoC = list() 
diffGtoC.append(countG - countC) 

文字列Pythonで不変であるので、あなたはすべてのポジションのために新たな文字列を生成しています非常に効率的ではありません。リストを使用すると、実行中の変換strとintのコンバージョンとリストの切り捨ても保存されます。 pop()を使用して新しいリストを生成する代わりにリストの最後のアイテムを削除することもできます。

本当に簡単な方法は、最小値を検索し、最小値とその位置のみを保存することです。次に、最小位置から反復を開始し、最小値を再度見つけることができるかどうかを確認し、必要であれば最初の最小位置に追加します。少ないデータ操作で時間とメモリを節約します。