Das deutsche Python-Forum

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...

@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.

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:)

R[:] erzeugt eine Kopie, ohne das du das brauchst.

__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."

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.

__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?

Wo machst du denn Index-Operationen auf R? Sehe ich nicht eine. Aber diverse "xxx in R"-Ausdruecke.

__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 )])

@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.

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

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...)

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:)

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?

(4,4) ... ach Mist

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

So funktioniert es aber leider auch nicht:(

Das deutsche Python-Forum

Woran liegt es das dieser Code Probleme macht?

Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?

Re: Woran liegt es das dieser Code Probleme macht?