Woran liegt es das dieser Code Probleme macht?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
gabba110
User
Beiträge: 16
Registriert: Donnerstag 28. September 2017, 20:13

Hallöchen, nach dem ich nun meinen Code fertig habe (denke ich) wollte ich ihn abgeben, nur leider kommt es bei dem Testprogramm zu Problemen bezüglich der Laufzeit, oder irgendeiner anderen Sache (wird nicht näher beschrieben). Hat vlt. einer von euch eine Idee wo das Problem liegen könnte?

Code: Alles auswählen

"""
Prüft ob eine Aequivalenzrelation vorliegt.

@input: n Element N mit n>0, Relationen 
@output: True oder False
"""
def aequiva(n,R):

# Prüfe ob n > len R
    if n > len(R):
        return False
    
# Reflexivität   
    for a in range(1,n+1):
        if(a,a) not in R:
            return False 
            
# Symmetrie
    for d in R[:]:
        if (d[1],d[0]) not in R:  
            return False
    
# Transitivität
    for i in R:
        for j in R:
            if i[1]==j[0] and ((i[0],j[1]) not in R):
                return False
    return True
    
#aequiva (2 , [(1 , 1), (2 ,2 ), (1 ,2 ), (2 ,1) , (1 , 1) , (2 , 2 )])  # ist nur eine Testinstanz...
Sirius3
User
Beiträge: 17712
Registriert: Sonntag 21. Oktober 2012, 17:20

@gabba110: der Doc-String ist nicht innerhalb der Funktion. »aquiva« ist eine blöde Abkürzung, die man nicht versteht, »check_aequivalence_relation« wäre tausendmal besser. »R« sollte dann auch «relations« heißen. Die Kommentare sind falsch eingerückt. Der zweite Test schließt den ersten Test schon mit ein, so dass man den weglassen könnte. Warum wird bei der zweiten for-Schleife eine Kopie von R erzeugt?

Ohne Aufgabenstellung kann man nicht sagen, ob das Richtig oder Falsch ist. Erzeug doch einfach selbst Testfälle und prüfe diese.
gabba110
User
Beiträge: 16
Registriert: Donnerstag 28. September 2017, 20:13

Danke für die schnelle Antwort.
Ja ich weiß, die sinnvollen Bezeichnungen in Englisch etc. wollte ich zum Schluss nochmal, obwohl es natürlich schlau wäre, es sofort zu machen.
Also die Aufgabenstellung ist: Schreiben Sie eine Funktion, die bei gegebenen n (mit n Element N und n>0) und R überprüft ob eine Äquivalenzrelation vorliegt.
Z.B

Code: Alles auswählen

True
>>> aequivalenzrelation (3 , [(2 , 2), (1 ,1 ), (3 ,3 ), (4 ,4) , (1 , 2) , (2 , 1), (2 ,3 ), (3 ,2 )])
False
>>> aequivalenzrelation (2 , [(1 , 1), (2 ,2 ), (1 ,2 ), (2 ,1) , (1 , 1) , (2 , 2 )]
True
Mein Code macht das, jedenfalls komme ich auf die selben Ergebnisse, dennoch wird mir angezeigt, dass er zu lange benötigt um die Testinstanz vollständig zu prüfen.

"Warum wird bei der zweiten for-Schleife eine Kopie von R erzeugt?"
Wie meist du dass? Bin leider noch Anfänger sry:)
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

R[:] erzeugt eine Kopie, ohne das du das brauchst.
gabba110
User
Beiträge: 16
Registriert: Donnerstag 28. September 2017, 20:13

__deets__ hat geschrieben:R[:] erzeugt eine Kopie, ohne das du das brauchst.
Stimmt, habe ich voll vergessen rauszunehmen. Danke
Aber dennoch ist dieser Code anscheinend viel zu langsam;(

Fehlermeldung:
"Dein Programm hatte entweder einen Fehler beim Durchlaufen oder gibt falsche Ergebnisse zurück oder hat zu lange gebraucht."
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

Also ein relativ simpler Schritt zur Verbesserung koennte sein R in ein set zu ueberfuehren. Denn damit sollte der Test auf element-von von O(n) auf O(1) schrumpfen. Vielleicht reicht das schon.
gabba110
User
Beiträge: 16
Registriert: Donnerstag 28. September 2017, 20:13

__deets__ hat geschrieben:Also ein relativ simpler Schritt zur Verbesserung koennte sein R in ein set zu ueberfuehren. Denn damit sollte der Test auf element-von von O(n) auf O(1) schrumpfen. Vielleicht reicht das schon.
Also setze ich am Anfang relation = set(R) und fertig ? Funktionieren dann überhaupt noch die Indexoperationen bei der Symmetrie etc?
__deets__
User
Beiträge: 14494
Registriert: Mittwoch 14. Oktober 2015, 14:29

Wo machst du denn Index-Operationen auf R? Sehe ich nicht eine. Aber diverse "xxx in R"-Ausdruecke.
gabba110
User
Beiträge: 16
Registriert: Donnerstag 28. September 2017, 20:13

__deets__ hat geschrieben:Wo machst du denn Index-Operationen auf R? Sehe ich nicht eine. Aber diverse "xxx in R"-Ausdruecke.
Ja, stimmt auch wieder, ich denke immer es wäre das selbe, habe es nun nochmals abgegeben und es ergab wieder die gleiche Fehlermeldung.
Hier noch einmal mein Code:

Code: Alles auswählen

def aequivalenzrelation(n,R):
    """
    Prüft ob eine Aequivalenzrelation vorliegt.
 
    @input: n Element N mit n>0, Relationen
    @output: True oder False
    """
    relation=set(R)
    # Reflexivität   
    for a in range(1,n+1):
        if(a,a) not in relation:
            return False 
            
    # Symmetrie
    for d in relation:
        if (d[1],d[0]) not in relation:  
            return False
    
    # Transitivität
    for i in relation:
        for j in relation:
            if i[1]==j[0] and ((i[0],j[1]) not in relation):
                return False
    return True
    
#aequivalenzrelation (2 , [(1 , 1), (2 ,2 ), (1 ,2 ), (2 ,1) , (1 , 1) , (2 , 2 )])
Sirius3
User
Beiträge: 17712
Registriert: Sonntag 21. Oktober 2012, 17:20

@gabba110: Funktionen werden nach Tätigkeiten benannt, weil sie ja was tun. `aequivalenzrelation` sagt nur, dass es irgendwas mit einer Relation zu tun hat, aber nicht, das darauf geprüft wird.

Das Problem mit der Geschwindigkeit sind nicht die O(len(R))-Überprüfungen, sondern die O(len(R)^3), die Du mit dem Set in ein O(len(R)^2) umgewandelt hast.
gabba110
User
Beiträge: 16
Registriert: Donnerstag 28. September 2017, 20:13

Sirius3 hat geschrieben:@gabba110: Funktionen werden nach Tätigkeiten benannt, weil sie ja was tun. `aequivalenzrelation` sagt nur, dass es irgendwas mit einer Relation zu tun hat, aber nicht, das darauf geprüft wird.

Das Problem mit der Geschwindigkeit sind nicht die O(len(R))-Überprüfungen, sondern die O(len(R)^3), die Du mit dem Set in ein O(len(R)^2) umgewandelt hast.
Mir ist bewusst, dass man die Funktion anders benennen sollte, aber das darf ich nicht, sonst wird es von dem Prüfprogramm nicht erkannt;)Dieses ruft ja die Funktion unter dem Namen auf, vorhin habe ich bloß schnell einen anderen gewählt, denn es war nur eine Art Testprogramm.(ist ja auch egal:=))

Ok, dann ist die Funktion nun schon etwas schneller geworden, nun wäre die Frage, ist das denn überhaupt das Problem?
Oder übersehe ich einen Spezialfall, denn mein Programm nicht beachtet? R[] ist es nicht
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

gabba110 hat geschrieben:Danke für die schnelle Antwort.
Also die Aufgabenstellung ist: Schreiben Sie eine Funktion, die bei gegebenen n (mit n Element N und n>0) und R überprüft ob eine Äquivalenzrelation vorliegt.
Z.B

Code: Alles auswählen

True
>>> aequivalenzrelation (3 , [(2 , 2), (1 ,1 ), (3 ,3 ), (4 ,4) , (1 , 2) , (2 , 1), (2 ,3 ), (3 ,2 )])
False
>>> aequivalenzrelation (2 , [(1 , 1), (2 ,2 ), (1 ,2 ), (2 ,1) , (1 , 1) , (2 , 2 )]
True
Mein Code macht das, jedenfalls komme ich auf die selben Ergebnisse, dennoch wird mir angezeigt, dass er zu lange benötigt um die Testinstanz vollständig zu prüfen.
Wie müsstest du das erste dieser Beispiele ändern, um das Ergebnis in True zu ändern? Hast du das alles überprüft? (Hint: nein...)
gabba110
User
Beiträge: 16
Registriert: Donnerstag 28. September 2017, 20:13

Ok ich verstehe erlich gesagt nicht was du mir damit sagen möchtest.
Das erste Musterbeispiel ist falsch, da die Trasitivität nicht erfüllt ist, es fehlt (1,3), (3,1). Also False...

Ws habe ich denn nicht überprüft? Das ist ja mein Problem, ich habe irgendwie Scheuklappen vor den Augen:)
bords0
User
Beiträge: 234
Registriert: Mittwoch 4. Juli 2007, 20:40

Dann füge eben alles hinzu, was du meinst, dass es nötig sei. Und dann kommt bei dir True heraus. Es sollte aber immer noch False herauskommen. Welches Tupel überprüfst du nämlich überhaupt nicht?
gabba110
User
Beiträge: 16
Registriert: Donnerstag 28. September 2017, 20:13

(4,4) ... ach Mist
gabba110
User
Beiträge: 16
Registriert: Donnerstag 28. September 2017, 20:13

Guten morgen,
ich hab nun diesen Code hier geschrieben, der überprüft ob etwas in der Relation ist, was aber nicht in der Menge n enthalten ist.
Würde dies aber nicht noch mehr Rechenaufwand bedeuten?

Code: Alles auswählen

    liste = []
    for i in R:
        liste.extend(i)
    
    set_of_liste = set(liste)  
    set_of_n = set(range(1,n+1))  
    if set_of_liste != set_of_n:
        return False
gabba110
User
Beiträge: 16
Registriert: Donnerstag 28. September 2017, 20:13

So funktioniert es aber leider auch nicht:(
Antworten