Head-Map debuggen

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
Benutzeravatar
Marceline
User
Beiträge: 20
Registriert: Freitag 2. November 2018, 16:35

Augabe: Folgender Code ist gegebeen und soll auf jegliche Fehler (Synax, Logik, Style-Guide nach PEP 8) untersucht werden. Hinweis: Wenn das Programm am Ende nicht komplett lauffähig ist, gibt es auf die gesamte Aufgabe 0 Punkte, unabhängig davon wie viele Fehler bereits korrigiert wurden

Code: Alles auswählen

from math import *
import random

class SortTree:
    #constructor
    def init(self, unsorted_list):
    self.list = unsorted_list

    #exchange operation
    def ExchangeNode(self, i, j):
        self.list[i], self.list[j] = self.list[i], self.list[j]

    #iterativ nach Robert Sedgewick
    def SinkNode(self, index):
    max_index = len(self.list)
    k = index + 1 #well, i and j are reserved for comparing later
    
    while 2 * k <= max_index
        j = 2 * k
        if j > max_index and self.list[j - 1] < self.list[j]:
            j += 1
        if (self.list[k - 1] >= self.list[j - 1]):
            break
        self.ExchangeNode(k - 1, j - 1)
        k=j

    def get_highest_node(self):
        a = self.list[0]
        self.ExchangeNode(0; -1)
        del self.list[-1]
        self.SinkNode(0)
        return "a"

    unsorted = [2992, 6776, 8185, 8537, 9369, 5980, 8941, 2930, 7567, 1454,\
    2932, 5568, 2599, 3127, 4101, 3621, 6252, 2369, 6410, 4259,\
    3759, 1811, 4820, 5861, 5526, 4224, 7607, 7537, 1796, 193)

    #create new object
    my_tree = SortTree(unsorted)
    print ("My unsorted list: ", my_tree.list)

    #build a heap, let sink new nodes
    for i in range(len(my_tree.list) - 1, -1, -1):
        my_tree.SinkNode(i)

    # create the new sorted list
    output = [my_tree.get_highest_node() for i in range(len(my_tree.list))]
    output.reverse() #yes, that’s right so
    
    print ("\nMy sorted list: " + output)
Problem/Lösungsansatz: Der Interpreter erkennt "k" in Zeile 16 nicht und weiß nicht, wie er das definiert soll. Ich vermute das k die Heaps modellieren soll und das man es umbennen soll. (Sinnvolle Variablennamen). Heaps sind ja Listen,bzw. Bäume indem man das 0. Listenelement als Wurzel seht, das 1. Listenelement als linkes Kind der Wurzel, das 2. Listenelement als rechtes Kind der Wurzel, das 3. Listenelement als
linkes Kind des linken Kinds der Wurzel, In dieser Baumdarstellung ist das (2*x + 1)-te Listenelement das linke Kind von dem (x+1)-ten Listenelement und das (2*x + 2)-te Listenelement ist das rechte Kind von dem (x+1)-ten Listenelement.
Bei einem Max-Heap (das ist die Form von Heap die wir hier betrachten) sind die Kinder immer kleiner als der Elternknoten, wenn der Heap sich in repariertem Zustand befindet. D.h. dass die Wurzel der größte Knoten ist. Es gibt hierfür eine delete_max Operation. Die delete_max Operation entfernt das 0.te Element der Liste, also die Wurzel im Baum und fügt an den 0.ten Listenplatz dafür das letzte Listenelement. Die Funktion get_highest_node() soll also nicht den größten Knoten suchen, sondern einfach nur das 0.te Element der Liste entfernen. Das 0.te Element der Liste ist aber das größte Element sofern der Heap repariert ist.

Wie kann ich "k" hier einfügen, ohne dass der Code abschmiert. Ich habe versucht k in die def SinkNode (self, index, k) zu schreiben und self.k = k zu definieren, aber es funktioniert nicht.

Meine Korrektor soweit:

Code: Alles auswählen

"""This programm models the heap representation after Robert Sedgewick"""

import random
 # Line 1: The wrong import has been removed.


class SortTree:

    name = " "
    # Line 5: The name attribute was. added. 
    # Line 5: The unnecessary commentary has been removed.
    def _init_(self, unsorted_list):
        # Line 6: The format of the __init__- order was corrected.
        self.list = unsorted_list
        # Line 7: The line was intended.

    # The Operation is exchanged.
    # Line 9: The sentence has ben completeted. 
    def ExchangeNode(self, i, j, k):
        self.list[i], self.list[j] = self.list[i], self.list[j]
        self.list[k] = self.list[k]

    # The Iterative Method of Robert Sergewick is used.
    # Line 13: The commentary has been translated to English.
    def SinkNode(self, k, index):
        self.index = index
        self.k = k
        # Line 14: Index has been defined.
        max_index = len(self.list)
        # Line 15: The line was inteded.
        k = index + 1
    # Line 16: The commentary was collequial and unnecessary.
        self.k = k
    while 2 * k <= max_index:
        # Line 18:: A colon at the end is added.
        j = 2 * k
        if j > max_index and self.list[j - 1] < self.list[j]:
            j += 1
        if (self.list[k - 1] >= self.list[j - 1]):
            break
        self.ExchangeNode(k - 1, j - 1)
        k=j

    def get_highest_node(self):
        a = self.list[0]
        # Line 28: The line was intended.
        self.ExchangeNode(0, -1)
    # Line 29: The semicolon was replaced with a collar ,.
        del self.list[-1]
        self.SinkNode(0)
        return "a"

    unsorted = [2992, 6776, 8185, 8537, 9369, 5980, 8941, 2930, 7567, 1454,\
    2932, 5568, 2599, 3127, 4101, 3621, 6252, 2369, 6410, 4259,\
    3759, 1811, 4820, 5861, 5526, 4224, 7607, 7537, 1796, 193]
    # Line 36: The round bracket was replaced with a square bracket.

    # A new object is created
    # Line 38: The sentence was completed and a space tab added.
    my_tree = sort_tree(unsorted)
    # Line 39: Camel Cases were replaced with underline.
    print ("My unsorted list: ", my_tree.list)

    #build a heap, let sink new nodes
    for i in range(len(my_tree.list) - 1, -1, -1):
        my_tree.SinkNode(i)

    # create the new sorted list
    output = [my_tree.get_highest_node() for i in range(len(my_tree.list))]
    output.reverse() #yes, that’s right so
    
    print ("\nMy sorted list: " + output)

def main():
    """This programm models the heap representation after Robobert Sedgewick."""    

if __name__ == '__main__':
    main()
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

Und, läuft Dein Code? Das ist leicht zu testen. Bei Syntax und Style-Guide (PEP 8 ) kann pylint hilfreich sein. Die Logik hingegen bleibt Dir überlassen, schließlich geht es bei Deiner Aufgabe auch um das Verständnis dessen, was da wie passieren soll.
Benutzeravatar
Marceline
User
Beiträge: 20
Registriert: Freitag 2. November 2018, 16:35

Er läuft nicht, eben weil Python die Variable "k" in Zeile 15 (im Original-Aufgabencode) nicht akzeptiert. Auch das Umbennen oder die Definition "k"s als Attribut helfen nicht weiter.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@Marceline: was meinst Du mit »Python akzeptiert `k` nicht«? Wenn es eine Fehlermeldung gibt, dann sagt die ziemlich deutlich, was genau falsch ist.

Warum wurde da ein unbenutztes Klassenattribut `name` hinzugefügt?
Der Kommentar zu Zeile 6 passt zwar, ist aber nicht im Code zu finden.
Warum hat `ExchangeNode` ein `k` bekommen? Was soll die Methode machen und warum macht sie das bisher noch nicht?
Die Einrückungen von `SinkNode` passt immer noch nicht. Es macht keinen Sinn, lokale Variablen an Attribute zu binden, die nicht benutzt werden (und auch nicht sollten).
Was soll `get_highest_node` zurückliefern?
Deine `main`-Funktion ist leer, wo steht der Code, der da eigentlich hineingehört?

Zum Style-Guide: es sind noch ein paar Klammernpaare zu viel, und 100% der \ sind überflüssig. Die Schreibweise von Methoden ist nicht immer korrekt. Doc-Strings wären bei solch einer Aufgabe auch angebracht.
Semantisch würde ich sagen, dass die Klasse hier komplett falsch ist und in einfache Funktionen umwandeln sollte.
Benutzeravatar
Marceline
User
Beiträge: 20
Registriert: Freitag 2. November 2018, 16:35

Die Fehlermeldung lautet:
line 16, in <module>
class SortTree:

line 43, in SortTree
while 2 * k <= max_index:
NameError: name 'k' is not defined

Dabei definiere ich ja self.k = k. Warum akzeptiert Python das nicht endlich?
Warum passt die Einrückung von SinkNode nicht? Weil ExchangeNode ist genau auf derselben Stelle eingerückt.
Benutzeravatar
kbr
User
Beiträge: 1487
Registriert: Mittwoch 15. Oktober 2008, 09:27

Marceline hat geschrieben: Samstag 19. Januar 2019, 14:00 Warum passt die Einrückung von SinkNode nicht? Weil ExchangeNode ist genau auf derselben Stelle eingerückt.
while ist auf der gleichen Ebene wie SinkNode und gehört damit nicht zu SinkNode sondern ist Code auf Klassen-Ebene.
Benutzeravatar
__blackjack__
User
Beiträge: 13004
Registriert: Samstag 2. Juni 2018, 10:21
Wohnort: 127.0.0.1
Kontaktdaten:

Bei Zeile 5 würde ich übrigens schreiben, dass der *falsche* Kommentar entfernt wurde, denn `__init__()` ist kein Konstruktor. Das wäre in Python die `__new__()`-Methode.
“Most people find the concept of programming obvious, but the doing impossible.” — Alan J. Perlis
Antworten