Rekursion problem

[mit]

Hallo,
ich beschäftige mich Rekursion und wollte den folgen rekursiven Perl Code:

Code: Alles auswählen

#!/usr/bin/perl
use strict; 

my @structure;
my @bases;

sub evalRna {
    my ($l,  
	$r)  
	= @_;

    my %bonds = (GU=>1,UG=>1,AU=>2,UA=>2,CG=>3,GC=>3);

    my $energy = $bonds{$bases[$l].$bases[$r]};
	print "e: ", $energy, "\n";
    my $level=0;

    my $ii = $l;
    
    for (my $i=$l+1; $i<=$r; $i++) {
	$level-- if ($structure[$i] eq ")");
	if ($level==0) {
	    $energy += evalRna($ii,$i) if ($structure[$i] eq ")");
	    $ii = $i;
	}
	$level++ if ($structure[$i] eq "(");
    }
    return $energy;
}

sub evalRnaStructure {
    my ($basestring,$structurestring) = @_;
    @bases = split(//, 5 . $basestring . 3);
    @structure = split(//, "($structurestring)");
    return evalRna(0, $#structure);
}


my $basestring = "CUCUCGGUAGCCAAGUUGGUUUUAAGGCGCAAGACUGAAUUUACCACUACGAAACUUGAGAUCGGGCGUUCGACUCGCCCCCGGGAGACCA";

my $parenstring = ".((((((...))(((((((((((..(...))))))(((...).).))(...))))))))))(((((.(..((...)))))).)((...)))";

print evalRnaStructure($basestring,$parenstring), 
     " hydrogen bonds in this structure.\n";

in Python umschreiben. Der folgende Python Code liefert aber ein falschen Wert zurück.

Code: Alles auswählen

import sys
#sys.setrecursionlimit(333500)

def evalRNA(baseStr, structureStr, l, r):
  level = 0
  ii = l
  energy = 0
  bonds = {'GU': 1, 'UG': 1, 'AU': 2, 
           'UA': 2, 'CG': 3, 'GC': 3}
  
  if bonds.has_key(baseStr[l] + baseStr[r]):
    energy = bonds[baseStr[l] + baseStr[r]]
  else:
    print "error", baseStr[l], baseStr[r]
    
  print l,  baseStr[l], baseStr[r], "e ", energy, bonds["GC"]

  for i in range(l, r): 
    if structureStr[i] == ")":
      level -= 1
    if level == 0:
      if structureStr[i] == ")":
        energy += evalRNA(baseStr, structureStr, ii, i)
        ii=i
    if structureStr[i] == "(":
      level += 1
    #print i
  return energy
    
def evalRnaStructure(baseStr, structStr):
  baseStr = '5' + baseStr + '3'
  print(baseStr)
  print(len(baseStr))
  structStr = "(" + structStr + ")"
  print structStr
  print (len(structStr))
  
  return evalRNA(baseStr, structStr, 1, len(structStr)-1)


if __name__ == "__main__":
  baseStr = 'CUCUCGGUAGCCAAGUUGGUUUUAAGGCGCAAGACUGAAUUUACCACUACGAAACUUGAGAUCGGGCGUUCGACUCGCCCCCGGGAGACCA'
    
  structureStr = '.((((((...))(((((((((((..(...))))))(((...).).))(...))))))))))(((((.(..((...)))))).)((...)))'
  
  print(evalRnaStructure(baseStr, structureStr),  
     " hydrogen bonds in this structure.")

Das richtige Ergebnis lautet 81 aber der Python Code liefert nur 6 zurück. Was habe ich falsch gemacht?

Viele Grüße

[BlackJack]

@mit: Du hast auf jeden Fall schonmal den falschen Quelltext gezeigt, denn *der* gibt bei mir einen ``RuntimeError: maximum recursion depth exceeded in cmp``.

Ansonsten schau Dir mal die Indexe an. Die entsprechen bei Dir nicht immer denen im Perl-Quelltext.

[fhoech]

Vielleicht noch als Zusatz zu BlackJacks Hinweis mit den fehlerhaften Indexen im Python-Code: In den Zeilen 18 (die range) und 38.

Ausserdem ist in Zeile 24 eine Einrückung zuviel.

[mit]

Ops, ich habe jetzt den oberen Code aktualisiert. Ich habe den ganzen Tag versucht den Fehler zu finden und es mir leider nicht gelungen.

[fhoech]

Ok, dann bitte zu den von mir genannten Zeilen eine dazuaddieren, dann stimmen meine Zeilenangaben wieder

[mit]

Habe die Korrekturen im folgenden Code eingebaut aber troztdem bekomme ich nicht das richtige Ergebnis.

Code: Alles auswählen

import sys

def evalRNA(baseStr, structureStr, l, r):
  level = 0
  ii = l
  energy = 0
  bonds = {'GU': 1, 'UG': 1, 'AU': 2, 
           'UA': 2, 'CG': 3, 'GC': 3}
  
  if bonds.has_key(baseStr[l] + baseStr[r]):
    energy = bonds[baseStr[l] + baseStr[r]]
  else:
    print "error", baseStr[l], baseStr[r]
    
  print l,  baseStr[l], baseStr[r], "e ", energy, bonds["GC"]

  for i in range(l+1, r+1): 
    if structureStr[i] == ")":
      level -= 1
    if level == 0:
      if structureStr[i] == ")":
        energy += evalRNA(baseStr, structureStr, ii, i)
        ii=i
  if structureStr[i] == "(":
    level += 1
    #print i
  return energy
    
def evalRnaStructure(baseStr, structStr):
  baseStr = '5' + baseStr + '3'
  print(baseStr)
  print(len(baseStr))
  structStr = "(" + structStr + ")"
  print structStr
  print (len(structStr))
  
  return evalRNA(baseStr, structStr, 0, len(structStr)-1)


if __name__ == "__main__":
  baseStr = 'CUCUCGGUAGCCAAGUUGGUUUUAAGGCGCAAGACUGAAUUUACCACUACGAAACUUGAGAUCGGGCGUUCGACUCGCCCCCGGGAGACCA'
    
  structureStr = '.((((((...))(((((((((((..(...))))))(((...).).))(...))))))))))(((((.(..((...)))))).)((...)))'
  
  print(evalRnaStructure(baseStr, structureStr),  
     " hydrogen bonds in this structure.")

  

[fhoech]

Zeile 24 (die mit ii=i) eine Einrückung raus, dafür die zwei folgenden Zeilen wieder eins einrücken.

btw, mach statt dem hier:

Code: Alles auswählen

import sys

def evalRNA(baseStr, structureStr, l, r):
  level = 0
  ii = l
  energy = 0
  bonds = {'GU': 1, 'UG': 1, 'AU': 2,
         'UA': 2, 'CG': 3, 'GC': 3}
 
  if bonds.has_key(baseStr[l] + baseStr[r]):
    energy = bonds[baseStr[l] + baseStr[r]]
  else:
    print "error", baseStr[l], baseStr[r]

vielleicht lieber das hier:

Code: Alles auswählen

import sys

bonds = {'GU': 1, 'UG': 1, 'AU': 2,
           'UA': 2, 'CG': 3, 'GC': 3}

def evalRNA(baseStr, structureStr, l, r):
  level = 0
  ii = l
 
  key = baseStr[l] + baseStr[r]
  if key in bonds:
    energy = bonds[key]
  else:
    energy = 0

(so braucht bonds nicht jedesmal in der Funktion neu initialisiert werden, und es ist klarer, welcher Wert energy zugewiesen wird, wenn kein passender key in bonds existiert)

[mit]

Danke. Habe die Korrekturen im folgenden Code eingebaut aber trotzdem bekomme ich nicht das richtige Ergebnis.

Code: Alles auswählen

import sys

bonds = {'GU': 1, 'UG': 1, 'AU': 2,
           'UA': 2, 'CG': 3, 'GC': 3}

def evalRNA(baseStr, structureStr, l, r):
  level = 0
  ii = l
 
  key = baseStr[l] + baseStr[r]
  if key in bonds:
    energy = bonds[key]
  else:
    energy = 0
    
  print l,  baseStr[l], baseStr[r], "e ", energy, bonds["GC"]

  for i in range(l+1, r+1): 
    if structureStr[i] == ")":
      level -= 1
    if level == 0:
      if structureStr[i] == ")":
        energy += evalRNA(baseStr, structureStr, ii, i)
      ii=i
  if structureStr[i] == "(":
    level += 1
  return energy
    
def evalRnaStructure(baseStr, structStr):
  baseStr = '5' + baseStr + '3'
  print(baseStr)
  print(len(baseStr))
  structStr = "(" + structStr + ")"
  print structStr
  print (len(structStr))
  
  return evalRNA(baseStr, structStr, 0, len(structStr)-1)


if __name__ == "__main__":
  baseStr = 'CUCUCGGUAGCCAAGUUGGUUUUAAGGCGCAAGACUGAAUUUACCACUACGAAACUUGAGAUCGGGCGUUCGACUCGCCCCCGGGAGACCA'
    
  structureStr = '.((((((...))(((((((((((..(...))))))(((...).).))(...))))))))))(((((.(..((...)))))).)((...)))'
  
  print(evalRnaStructure(baseStr, structureStr),  
     " hydrogen bonds in this structure.")

[fhoech]

Ahem...

(...) dafür die zwei folgenden Zeilen wieder eins einrücken.

[mit]

Welche Zeilen meinst du?

[fhoech]

Diese:

Code: Alles auswählen

   if structureStr[i] == "(":
      level += 1

Wie ich bereits schrieb, siehe oben.

[mit]

Vielen Dank es funktioniert.

[sma]

Perl ist keine Sprache, die ich freiwillig benutzen würde. Mir ist dieses zählen der Klammern und suchen von Paaren nicht so ganz klar, aber irgendwie wirkt das Perl-Programm umständlicher als gedacht.

Hier ist meine Python-Version. Bonds und Strings kann ich aus der Funktion herausziehen. Experimente haben ergeben, dass Perl offenbar keinen Fehler liefert, wenn man auf unbekannte Schlüssel zugreift. Daher habe ich `get` benutzt. Auch liefert `$#` überraschender Weise nicht die Länge, sondern die Länge - 1. Statt C-`for` benutze ich lieber `range`. Und was die 5 und 3 vor und hinter dem String als Begrenzer sollen, weiß ich nicht. Hauptsache, es sind keine der 4 Basen.

Code: Alles auswählen

bonds = {
    "GU": 1,
    "UG": 1,
    "AU": 2,
    "UA": 2,
    "CG": 3,
    "GC": 3,
}

bases = "-CUCUCGGUAGCCAAGUUGGUUUUAAGGCGCAAGACUGAAUUUACCACUACGAAACUUGAGAUCGGGCGUUCGACUCGCCCCCGGGAGACCA-"
structure = "(.((((((...))(((((((((((..(...))))))(((...).).))(...))))))))))(((((.(..((...)))))).)((...))))"

def eval_rna(l, r):
    energy = bonds.get(bases[l] + bases[r], 0)
    
    level = 0; ii = l
    
    for i in range(l + 1, r + 1):
        if structure[i] == ")":
            level -= 1
        if level == 0:
            if structure[i] == ")":
                energy += eval_rna(ii, i)
            ii = i
        if structure[i] == "(":
            level += 1

    return energy
    
print eval_rna(0, len(structure) - 1), "hydrogen bonds in this structure"

Stefan

[BlackJack]

@sma: Wenn Du `bonds` und die Zeichenketten aus der Funktion herausziehst, dann hat man wieder globale Variablen. Bei `bonds` ist das noch okay, aber die anderen beiden würde ich nicht auf globaler Ebene haben wollen, weil das wohl eher Beispiele für Werte sein sollen, mit dem man das aufrufen kann. Ich habe das so gelöst (und heute morgen vergessen zu posten ):

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf-8
"""Ported from a piece of Perl code.

:TODO: It is inefficient because the structure is (re)parsed too many times
    in the recursive calls of `eval_rna()`.  Parsing it just once and note
    down matching parenthesis' indices would be much more efficient.
"""

BONDS = dict(GU=1, UG=1, AU=2, UA=2, CG=3, GC=3)


def eval_rna_structure(bases, structure):
    # 
    # TODO: Why '5' and '3'?  The values are ignored anyway. Seems
    #   to be just important that they can't be part of a BONDS key.
    #   
    bases = '5' + bases + '3'
    structure = '(' + structure + ')'
    
    def eval_rna(left_index, right_index):
        energy = BONDS.get(bases[left_index] + bases[right_index], 0)
        level = 0
        index = left_index
        for i in xrange(left_index + 1, right_index + 1):
            if structure[i] == ')':
                level -= 1
            if level == 0:
                if structure[i] == ')':
                    energy += eval_rna(index, i)
                index = i
            if structure[i] == '(':
                level += 1
        return energy

    return eval_rna(0, len(structure) - 2)


def main():
    bases = ('CUCUCGGUAGCCAAGUUGGUUUUAAGGCGCAAGACUGAAUUUACCACU'
             'ACGAAACUUGAGAUCGGGCGUUCGACUCGCCCCCGGGAGACCA')
    structure = ('.((((((...))(((((((((((..(...))))))(((...).).))(...'
                 '))))))))))(((((.(..((...)))))).)((...)))')
    result = eval_rna_structure(bases, structure)
    print result, 'hydrogen bonds in this structure.'


if __name__ == '__main__':
    main()

Es scheint mir auch viel zu kompliziert zu sein, weil bei jedem rekursiven Aufruf eigentlich schon bekannte Klammerstrukturen immer wieder "ausgezählt" werden.

[mit]

Vielen Dank.