Laufzeit zu lang für GC Skew

Question

Ich arbeite derzeit an einem Skript, das Skew Unterschiede analysiert. Leider ist mein Problem, dass wenn die Länge der Zeichenfolge zunimmt, die Laufzeit zu lang wird und ich meine Antwort nicht berechnen kann.

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) 

Im Wesentlichen dieses Skript die Anzahl von G und C berechnet (entspricht den Nukleotiden in DNA), erhält bei jeder Positionsdifferenzen, und dann versuche ich die Indizes der Mindest zu finden. Es funktioniert gut für niedrige Länge der Datei (das ist die Eingabe-Zeichenfolge), aber wenn die Länge wird groß - sogar wie 90000+, dann läuft mein Skript, kann aber nicht zu einer Antwort in angemessener Zeit (~ 4-5 min) auflösen.

Kann mir jemand zeigen, was ich tun könnte, um es schneller zu machen? Ich habe darüber nachgedacht, ob es besser ist zu sagen, erhalte die Differenz (diffGtoC), setze das Minimum und berechne dann jede Differenz neu, bis sie etwas anderes sieht, währenddessen ich auch den Mindestwert ersetze.

Aber die Sorge, die ich mit diesem Ansatz hatte, war auf das Finden und Beibehalten der Indizes des Minimums. Wenn ich sage, ein Array mit Werten hatte:

[-4, -2, -5, -6, -5, -6]

kann ich sehen, wie der Minimalwert ändert (-4 bis - 5 und dann bis -6) wird in Bezug auf die Laufzeit des Algorithmus schneller sein, aber wie kann ich die Position von -6 beibehalten? Nicht sicher, ob das völlig Sinn macht.

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

ist eigentlich äquivalent zu:

Answer 1

Mehrere Vorschläge, um die Leistung Ihres Codes zu verbessern

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

Strings sind unveränderlich in Python, so dass Sie eine neue Zeichenfolge für jede Position zu erzeugen, die ist nicht sehr effizient. Durch die Verwendung einer Liste werden auch die von Ihnen ausgeführten Conversions str und int und die Kürzung Ihrer Liste gespeichert. Sie können auch pop() verwenden, um das letzte Element Ihrer Liste zu entfernen, anstatt ein neues zu erstellen.

Eine wirklich einfache Alternative wäre, nach dem Minimum zu suchen und nur den Minimalwert und seine Position zu speichern. Beginnen Sie dann mit der Iteration von der minimalen Position und prüfen Sie, ob Sie das Minimum wieder finden können und wenn ja, fügen Sie es an die erste minimale Position an. Weniger Datenmanipulation, die Zeit und Speicher spart.