Hallo zusammen,
ich schreibe das an diese Gruppe, weil sie mir den nächstliegenden bzw. persönlichsten Kontakt zu versprechen scheint und weil die Frage hier vielleicht am wenigsten "OT" ist (weil das "T" ja auch nicht ganz so spezifisch eingeschränkt ist). Es ist aber ganz klar, dass ich nur in die Runde frage, ob jemand *Interesse* an der Sache hat, ich erhebe keinerlei *Anspruch* auf Unterstützung. Und zwar Interesse daran, ein paar Python-Dateien anzusehen und (helfend) zu diskutieren.
Ich mache gerade eine Serie von Online-Kursen bei Coursera zum Thema Algorithmen und Datenstrukturen (ein Versuch, etwas gegen meine langgehegte Frustration über fehlende Grundlagen zu tun). Insgesamt läuft es sehr gut und ich bin froh, es angefangen zu haben, aber in einigen Fällen komme ich doch nicht weiter. Das heißt letztlich, dass meine Programmieraufgaben vom System zurückgewiesen werden, weil irgendein Testfall ein falsches Ergebnis provoziert oder weil die Lösung für einen Fall zu lange rechnet. Das Interessante, aber auch Frustrierende an den Kursen ist, dass man außer bei den ersten Aufgaben jeder Einheit nur diese Information erhält, aber weiter nichts über die Fälle oder falschen Ergebnisse.
Was ich also gerne hätte, wäre, dass sich jemand Python-Dateien ansieht, die z.B. eine Lösung für die Frage haben "Ist die Eingabe ein korrekter BInärer Suchbaum?" oder "Gibt es in dem gegebenen gerichteten Graphen negative Zyklen?" und Ähnliches. Ich will auf keinen Fall, dass mir jemand die Lösungen anbietet bzw. schreibt. Vielmehr wäre ich dankbar für konkrete Hinweise auf (versteckte) Fehler oder Optimierungsmöglichkeiten meiner Algorithmen bzw. Implementierungen.
HG Urs
Hallo Urs,
Hast du die Python-Programme lokal getestet? Kann man die Lernumgebung auf der Webseite lokal nachbauen, um dann mehr Rückmeldungen zu bekommen? Es macht nicht wirklich Spaß, stundenlang in einer Umgebung zu testen, wo man keine sinnvollen Rückmeldungen bekommt. Gerade bei Programmen für Anfänger und Einsteiger geht es doch nicht um Laufzeitoptimierung sondern um klare, einfache Struktur.
Viele Grüße, Stefan Ziegler.
Gesendet: Donnerstag, 27. Juli 2017 um 19:58 Uhr Von: "Urs Liska" ul@openlilylib.org An: flug@lug-freiburg.de Betreff: [Flug] (OT?) Algorithmen und Datenstrukturen
Hallo zusammen,
ich schreibe das an diese Gruppe, weil sie mir den nächstliegenden bzw. persönlichsten Kontakt zu versprechen scheint und weil die Frage hier vielleicht am wenigsten "OT" ist (weil das "T" ja auch nicht ganz so spezifisch eingeschränkt ist). Es ist aber ganz klar, dass ich nur in die Runde frage, ob jemand *Interesse* an der Sache hat, ich erhebe keinerlei *Anspruch* auf Unterstützung. Und zwar Interesse daran, ein paar Python-Dateien anzusehen und (helfend) zu diskutieren.
Ich mache gerade eine Serie von Online-Kursen bei Coursera zum Thema Algorithmen und Datenstrukturen (ein Versuch, etwas gegen meine langgehegte Frustration über fehlende Grundlagen zu tun). Insgesamt läuft es sehr gut und ich bin froh, es angefangen zu haben, aber in einigen Fällen komme ich doch nicht weiter. Das heißt letztlich, dass meine Programmieraufgaben vom System zurückgewiesen werden, weil irgendein Testfall ein falsches Ergebnis provoziert oder weil die Lösung für einen Fall zu lange rechnet. Das Interessante, aber auch Frustrierende an den Kursen ist, dass man außer bei den ersten Aufgaben jeder Einheit nur diese Information erhält, aber weiter nichts über die Fälle oder falschen Ergebnisse.
Was ich also gerne hätte, wäre, dass sich jemand Python-Dateien ansieht, die z.B. eine Lösung für die Frage haben "Ist die Eingabe ein korrekter BInärer Suchbaum?" oder "Gibt es in dem gegebenen gerichteten Graphen negative Zyklen?" und Ähnliches. Ich will auf keinen Fall, dass mir jemand die Lösungen anbietet bzw. schreibt. Vielmehr wäre ich dankbar für konkrete Hinweise auf (versteckte) Fehler oder Optimierungsmöglichkeiten meiner Algorithmen bzw. Implementierungen.
HG Urs
-- ul@openlilylib.org https://openlilylib.org http://lilypondblog.org
Freiburger Linux User Group Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen): https://lug-freiburg.de/mailman/listinfo/flug
Am Donnerstag, 27. Juli 2017 23:26 CEST, "Stefan Ziegler" stefan.ziegler_zst@gmx.de schrieb:
Hallo Urs,
Hast du die Python-Programme lokal getestet? Kann man die Lernumgebung auf der Webseite lokal nachbauen, um dann mehr Rückmeldungen zu bekommen?
Bei solchen Online-Kursen geht das offt nicht. Die Test die verwendet werden um die Korrektheit der Antworten zu prüfen werden bewusst und aus gutem Grund nicht zur Verfügung gestellt. Sonst ist die Versuchung zu gross, das einzureichende Programm auf die erwarteten Ergebnisse hin zu "optimieren". Ich habe da nette Geschichten gehört von Programmen eingereichten Programmen die einfach das erwartete Ergebnis harcoded im Qellcode hatten und das zurückgaben. Andererseits scheint Optimierung auf erwartete Ergebnisse ja durchaus eine Tugend macher Programme zu sein - besonders in der Automobilindustrie ;-)
Es macht nicht wirklich Spaß, stundenlang in einer Umgebung zu testen, wo man keine sinnvollen Rückmeldungen bekommt. Gerade bei Programmen für Anfänger und Einsteiger geht es doch nicht um Laufzeitoptimierung sondern um klare, einfache Struktur.
Nun ja, das ist wahrscheinlich weniger ein Problem der Effizenz sondern wahrscheinlich eher ein rekursiver Algorythmus der nicht terminiert. Natürlich sollte ein hinreichend guter Python-Programm-Begutachter fähig sein ein Programm zu schreiben das feststellt ob eine gegebene Lösung terminiert .... ;-)
@urs: nur her mit dem Code - ich kann ihn mir gerne mal ansehen.
Gruss RalfD
Hallo Ralf,
Am 27.07.2017 um 23:38 schrieb Ralf Mattes:
Am Donnerstag, 27. Juli 2017 23:26 CEST, "Stefan Ziegler" stefan.ziegler_zst@gmx.de schrieb:
Hallo Urs,
Hast du die Python-Programme lokal getestet? Kann man die Lernumgebung auf der Webseite lokal nachbauen, um dann mehr Rückmeldungen zu bekommen?
Bei solchen Online-Kursen geht das offt nicht. Die Test die verwendet werden um die Korrektheit der Antworten zu prüfen werden bewusst und aus gutem Grund nicht zur Verfügung gestellt. Sonst ist die Versuchung zu gross, das einzureichende Programm auf die erwarteten Ergebnisse hin zu "optimieren". Ich habe da nette Geschichten gehört von Programmen eingereichten Programmen die einfach das erwartete Ergebnis harcoded im Qellcode hatten und das zurückgaben.
LOL!
Andererseits scheint Optimierung auf erwartete Ergebnisse ja durchaus eine Tugend macher Programme zu sein - besonders in der Automobilindustrie ;-)
Stimmt ;-) Ich muss sagen, die Einschränkung, dass man weder die Eingabe noch die Ausgabe kennt, erscheint mir nicht ganz realistisch. In der Regel wird man ja beim Testen/Debuggen mindestens eins von beidem steuern oder beobachten können. (Was man weiß, sind die Rahmenbedingungen, also etwa: minimale/maximale Anzahl der Werte, Wertebereiche, garantierte Korrektheit u.Ä.)
Es macht nicht wirklich Spaß, stundenlang in einer Umgebung zu testen, wo man keine sinnvollen Rückmeldungen bekommt. Gerade bei Programmen für Anfänger und Einsteiger geht es doch nicht um Laufzeitoptimierung sondern um klare, einfache Struktur.
Nun ja, das ist wahrscheinlich weniger ein Problem der Effizenz sondern wahrscheinlich eher ein rekursiver Algorythmus der nicht terminiert.
Möglich. Mir scheint es aber ebensogut möglich, dass der Algorithmus einfach an bestimmten Randfällen oder Datenmengen scheitert, weil sich da erst das nicht optimale Laufzeitverhalten bemerkbar macht (siehe Beispiel aus der anderen Mail).
Natürlich sollte ein hinreichend guter Python-Programm-Begutachter fähig sein ein Programm zu schreiben das feststellt ob eine gegebene Lösung terminiert .... ;-)
@urs: nur her mit dem Code - ich kann ihn mir gerne mal ansehen.
Ich habe ein Repo und werde dir (und Tomas, der auch privat geantwortet hat) einen Account auf meinem privaten Gitlab-Server einrichten. Die derzeit offenen (also nicht erfolgreich eingereichten) Dateien und Fragen sind im Issue-Tracker verlinkt und erläutert. Jeweils ein Verzeichnis oberhalb der Python-Dateien befindet sich ein PDF mit den Aufgabenbeschreibungen.
Herzlichen Dank schon mal! Urs
Gruss RalfD
Hallo Stefan,
Am 27.07.2017 um 23:26 schrieb Stefan Ziegler:
Hallo Urs,
Hast du die Python-Programme lokal getestet?
Ja, natürlich, soweit mir das möglich war. In den ersten Kursen gab es auch noch einfach die Gelegenheit zum Stress-Testing, weil die Vorgabedateien einen naiven Algorithmus implementiert hatten. Damit konnte man für kleinere Datenmengen Vergleiche anstellen und zumindest die Korrektheit der Ergebnisse überprüfen.
Wenn das fehlt, ist man allerdings auf sich alleine gestellt und muss versuchen, die gefährlichen Fälle mit großen Datenmengen herauszufinden und gezielt zu testen. Dabei komme ich allerdings an meine Grenzen.
Kann man die Lernumgebung auf der Webseite lokal nachbauen, um dann mehr Rückmeldungen zu bekommen?
Nein. Wie gesagt bekommt man bei den jeweils ersten Aufgaben eines Kurses sowohl die Eingabedaten als auch die (falschen) Antworten geliefert, später wird man aber bewusst im Dunkeln gelassen.
Es macht nicht wirklich Spaß, stundenlang in einer Umgebung zu testen, wo man keine sinnvollen Rückmeldungen bekommt.
Das stimmt allerdings. *Sinn* macht es aber bis zu einem gewissen Grad schon.
Gerade bei Programmen für Anfänger und Einsteiger geht es doch nicht um Laufzeitoptimierung sondern um klare, einfache Struktur.
Doch, darum geht es hier durchaus. Das Programmieren ist ja nicht Gegenstand des Kurses (wird vorausgesetzt), sondern die Algorithmen. Und es geht darum, die Erfahrung zu machen, welche spektakulären Laufzeitunterschiede Details des Algorithmus und der Implementierungen machen können. Wenn man (nicht-professionell) vor sich hin programmiert, probiert man ja i.d.R. mit ein paar Fällen herum und verarbeitet dann ein paar Dutzend, Hundert oder auch Tausend Datensätze - und das geht mit heutigen Computern eben doch auch mit dem schlechtesten Algorithmus. Wenn man dann aber einen Baum mit bis zu 10^5 Knoten verarbeiten soll, macht es doch einen signifikanten Unterschied. Während ich die Beispiele für diese Anfrage vorbereitet habe, konnte ich eine Aufgabe doch selber lösen, indem ich beim Durchlaufen eines Baums die Zeile
return left + [index] + right in return left[0::-1] + [index] + right[0::-1]
umwandelte. Auf einmal brach der Grader nicht mehr bei 20 Sekunden ab (er bricht immer nach dem Doppelten der erlaubten Zeit ab, so dass man nicht weiß, ob der Algorithmus nicht terminiert oder doch einfach nur zu lange braucht), sondern gab eine maximale Zeit von 1.05 Sekunden an.
Diese Art von Engpässen selbst zu finden, ist die Vorgabe der Kurse. Und grundsätzlich finde ich das auch gut. Allerdings kann man u.U. in einer Sackgasse landen, wenn man einfach nicht weiter weiß. Es gibt natürlich die Diskussionsforen, wo auch Mentoren und gelegentlich die Dozenten antworten. Es ist aber (natürlich) ausdrücklich verboten, dort konkreten Code zu teilen.
Herzliche Grüße Urs
Viele Grüße, Stefan Ziegler.
Gesendet: Donnerstag, 27. Juli 2017 um 19:58 Uhr Von: "Urs Liska" ul@openlilylib.org An: flug@lug-freiburg.de Betreff: [Flug] (OT?) Algorithmen und Datenstrukturen
Hallo zusammen,
ich schreibe das an diese Gruppe, weil sie mir den nächstliegenden bzw. persönlichsten Kontakt zu versprechen scheint und weil die Frage hier vielleicht am wenigsten "OT" ist (weil das "T" ja auch nicht ganz so spezifisch eingeschränkt ist). Es ist aber ganz klar, dass ich nur in die Runde frage, ob jemand *Interesse* an der Sache hat, ich erhebe keinerlei *Anspruch* auf Unterstützung. Und zwar Interesse daran, ein paar Python-Dateien anzusehen und (helfend) zu diskutieren.
Ich mache gerade eine Serie von Online-Kursen bei Coursera zum Thema Algorithmen und Datenstrukturen (ein Versuch, etwas gegen meine langgehegte Frustration über fehlende Grundlagen zu tun). Insgesamt läuft es sehr gut und ich bin froh, es angefangen zu haben, aber in einigen Fällen komme ich doch nicht weiter. Das heißt letztlich, dass meine Programmieraufgaben vom System zurückgewiesen werden, weil irgendein Testfall ein falsches Ergebnis provoziert oder weil die Lösung für einen Fall zu lange rechnet. Das Interessante, aber auch Frustrierende an den Kursen ist, dass man außer bei den ersten Aufgaben jeder Einheit nur diese Information erhält, aber weiter nichts über die Fälle oder falschen Ergebnisse.
Was ich also gerne hätte, wäre, dass sich jemand Python-Dateien ansieht, die z.B. eine Lösung für die Frage haben "Ist die Eingabe ein korrekter BInärer Suchbaum?" oder "Gibt es in dem gegebenen gerichteten Graphen negative Zyklen?" und Ähnliches. Ich will auf keinen Fall, dass mir jemand die Lösungen anbietet bzw. schreibt. Vielmehr wäre ich dankbar für konkrete Hinweise auf (versteckte) Fehler oder Optimierungsmöglichkeiten meiner Algorithmen bzw. Implementierungen.
HG Urs
-- ul@openlilylib.org https://openlilylib.org http://lilypondblog.org
Freiburger Linux User Group Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen): https://lug-freiburg.de/mailman/listinfo/flug
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Thu, Jul 27, 2017 at 07:58:25PM +0200, Urs Liska wrote:
Hallo zusammen,
[...]
Was ich also gerne hätte, wäre, dass sich jemand Python-Dateien ansieht, die z.B. eine Lösung für die Frage haben "Ist die Eingabe ein korrekter BInärer Suchbaum?"
[...]
Ich habe mir die mal angeschaut. Ich nehme mal an, die ist:
02-data-structures/06-binary-search-trees/is_bst/is_bst.py
Bei der Methode is_bst(self, indeex=0) stehe ich noch auf der Leitung: was soll die Methode als Rückgabewert liefern? Ich meine: was für eine Art Objekt?
Wenn ich nicht ganz auf der Leitung stehe, dann vermute ich hier den Knoten :-)
(mehr morgen).
lg - -- t
Am 28.07.2017 um 23:31 schrieb tomas@tuxteam.de:
On Thu, Jul 27, 2017 at 07:58:25PM +0200, Urs Liska wrote:
Hallo zusammen,
[...]
Was ich also gerne hätte, wäre, dass sich jemand Python-Dateien ansieht, die z.B. eine Lösung für die Frage haben "Ist die Eingabe ein korrekter BInärer Suchbaum?"
[...]
Ich habe mir die mal angeschaut. Ich nehme mal an, die ist:
02-data-structures/06-binary-search-trees/is_bst/is_bst.py
Ja. Allerdings ist die bereits im master-Branch, was bedeutet, dass die Aufgabe schon erfolgreich absolviert wurde (inzwischen, d.h. seit meinem ersten Post).
Bei der Methode is_bst(self, indeex=0) stehe ich noch auf der Leitung: was soll die Methode als Rückgabewert liefern? Ich meine: was für eine Art Objekt?
Wenn ich nicht ganz auf der Leitung stehe, dann vermute ich hier den Knoten :-)
Das ist in der Tat recht kryptisch und hätte wohl eine bessere Kommentierung verdient. Dann hätte ich auch den (allerdings konsequenzlosen) Fehler bemerkt ... Der Rückgabewert der rekursiven Funktion ist eine Liste mit den Randwerten der linken und rechten Kinder und dem aktuellen Knoten in der Mitte. "Natürlicher" wäre die Rückgabe von "left + [index] + right", wodurch rekursiv eine Liste mit dem gesamten Inhalt des Baums in natürlicher Ordnung entsteht. Diese Liste kann allerdings recht lang werden und kostet offensichtlich zu viel Rechenzeit.
Falsch ist, dass das mittlere Element nicht "[index]" sein dürfte, sondern der tatsächliche Schlüsselwert, nämlich "[self.value(index)]". Da dieser mittlere Wert aber überhaupt nicht gebraucht wird, ist der Fehler nicht aufgefallen. DIESE Aufgabe ist also inzwischen erfolgreich gelöst.
Herzliche Grüße Urs
(mehr morgen).
lg -- t _______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen):
https://lug-freiburg.de/mailman/listinfo/flug
Am 29. Juli 2017 00:28:26 MESZ schrieb Urs Liska ul@openlilylib.org:
Am 28.07.2017 um 23:31 schrieb tomas@tuxteam.de:
On Thu, Jul 27, 2017 at 07:58:25PM +0200, Urs Liska wrote:
Hallo zusammen,
[...]
Was ich also gerne hätte, wäre, dass sich jemand Python-Dateien
ansieht,
die z.B. eine Lösung für die Frage haben "Ist die Eingabe ein
korrekter
BInärer Suchbaum?"
[...]
Ich habe mir die mal angeschaut. Ich nehme mal an, die ist:
02-data-structures/06-binary-search-trees/is_bst/is_bst.py
Ja. Allerdings ist die bereits im master-Branch, was bedeutet, dass die Aufgabe schon erfolgreich absolviert wurde (inzwischen, d.h. seit meinem ersten Post).
Was ich damit eigentlich sagen wollte, ist, dass nur die Fragen relevant sind, die tatsächlich im Issue-Tracker offen sind.
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Sat, Jul 29, 2017 at 12:28:26AM +0200, Urs Liska wrote:
Am 28.07.2017 um 23:31 schrieb tomas@tuxteam.de:
[...]
Ich habe mir die mal angeschaut. Ich nehme mal an, die ist:
02-data-structures/06-binary-search-trees/is_bst/is_bst.py
Ja. Allerdings ist die bereits im master-Branch, was bedeutet, dass die Aufgabe schon erfolgreich absolviert wurde (inzwischen, d.h. seit meinem ersten Post).
Congrats :)
Bei der Methode is_bst(self, indeex=0) stehe ich noch auf der Leitung: was soll die Methode als Rückgabewert liefern? Ich meine: was für eine Art Objekt?
Wenn ich nicht ganz auf der Leitung stehe, dann vermute ich hier den Knoten :-)
Das ist in der Tat recht kryptisch und hätte wohl eine bessere Kommentierung verdient. Dann hätte ich auch den (allerdings konsequenzlosen) Fehler bemerkt ...
+1
Der Rückgabewert der rekursiven Funktion ist eine Liste mit den Randwerten der linken und rechten Kinder und dem aktuellen Knoten in der Mitte. "Natürlicher" wäre die Rückgabe von "left + [index] + right",
OK. Darauf wäre ich allerdings nicht gekommen, zumal is_bst einem das Hirn schon auf ein boolean "polt" (is this thing a binary search tree?). Das verführt einem dazu, sich diese "Frage" rekursiv vorzustellen
is_bst(tree): return tree.left.val < tree.val \ and tree.val < tree.right.var \ and is_bst(tree.left) \ and is_bst(tree.right)
(das ist natürlich salopp formuliert, bei Deiner Darstellung des Baums müssen eher solche Dinge stehen wie
self.value(self.left(index)) < self.value(index) ...
bzw.
is_bst(self.left(index))...
... you get the idea. Man muss natürlich damit klarkommen, dass diese Methoden manchmal None liefern, was den Ausdruck etwas unübersichtlich macht (bei den Vergleichen).
Anders als bei Deinem Ansatz muss man also nicht "mittendrin" herausspringen (d.h. fail()), sondern das Ergebnis entsteht rekursiv. Im Fehlerfall ist das "Herausspringen" schneller, natürlich.
wodurch rekursiv eine Liste mit dem gesamten Inhalt des Baums in natürlicher Ordnung entsteht. Diese Liste kann allerdings recht lang werden und kostet offensichtlich zu viel Rechenzeit.
Falsch ist, dass das mittlere Element nicht "[index]" sein dürfte, sondern der tatsächliche Schlüsselwert, nämlich "[self.value(index)]". Da dieser mittlere Wert aber überhaupt nicht gebraucht wird, ist der
Das verstehe ich nicht: der mittlere Wert muss doch zwischen den linken und den rechten liegen, damit der Baum sortiert ist? Muss man das nicht auch prüfen?
Fehler nicht aufgefallen. DIESE Aufgabe ist also inzwischen erfolgreich gelöst.
Bestens. Hängst Du noch irgendwo?
lg - -- t
Am 29.07.2017 um 09:15 schrieb tomas@tuxteam.de:
On Sat, Jul 29, 2017 at 12:28:26AM +0200, Urs Liska wrote:
Am 28.07.2017 um 23:31 schrieb tomas@tuxteam.de:
[...]
Ich habe mir die mal angeschaut. Ich nehme mal an, die ist:
02-data-structures/06-binary-search-trees/is_bst/is_bst.py
Ja. Allerdings ist die bereits im master-Branch, was bedeutet, dass die Aufgabe schon erfolgreich absolviert wurde (inzwischen, d.h. seit meinem ersten Post).
Congrats :)
Bei der Methode is_bst(self, indeex=0) stehe ich noch auf der Leitung: was soll die Methode als Rückgabewert liefern? Ich meine: was für eine Art Objekt?
Wenn ich nicht ganz auf der Leitung stehe, dann vermute ich hier den Knoten :-)
Das ist in der Tat recht kryptisch und hätte wohl eine bessere Kommentierung verdient. Dann hätte ich auch den (allerdings konsequenzlosen) Fehler bemerkt ...
+1
Der Rückgabewert der rekursiven Funktion ist eine Liste mit den Randwerten der linken und rechten Kinder und dem aktuellen Knoten in der Mitte. "Natürlicher" wäre die Rückgabe von "left + [index] + right",
OK. Darauf wäre ich allerdings nicht gekommen, zumal is_bst einem das Hirn schon auf ein boolean "polt" (is this thing a binary search tree?).
Grrr, das muss ich zugeben. Die Funktion sollte anders heißen. Im Wesentlichen ist es so, dass der Baum in seiner natürlichen Ordnung durchlaufen wird. Sofern eine Fehlerbedingung festgestellt wird, bricht sie ab, andernfalls läuft sie durch und gibt "irgendwas" zurück - dann ist der Baum korrekt.
Semantisch richtig wäre wohl
def main(): tree = TreeOrders() if len(tree.nodes) == 0: print("CORRECT") tree.traverse() print("CORRECT")
Das verführt einem dazu, sich diese "Frage" rekursiv vorzustellen
is_bst(tree): return tree.left.val < tree.val \ and tree.val < tree.right.var \ and is_bst(tree.left) \ and is_bst(tree.right)
(das ist natürlich salopp formuliert, bei Deiner Darstellung des Baums müssen eher solche Dinge stehen wie
self.value(self.left(index)) < self.value(index) ...bzw.
is_bst(self.left(index))...... you get the idea. Man muss natürlich damit klarkommen, dass diese Methoden manchmal None liefern, was den Ausdruck etwas unübersichtlich macht (bei den Vergleichen).
Ich glaube nicht, dass das funktionierten würde. Wenn ich an einem gegebenen Knoten für links und rechts nur einen Boolean-Wert zurückbekomme, kann ich nicht mit dem aktuellen Knoten vergleichen (wie du unten auch schreibst). Daher muss die rekursive Funktion schon die Knoten-Werte des Subtrees zurückgeben.
Anders als bei Deinem Ansatz muss man also nicht "mittendrin" herausspringen (d.h. fail()), sondern das Ergebnis entsteht rekursiv. Im Fehlerfall ist das "Herausspringen" schneller, natürlich.
wodurch rekursiv eine Liste mit dem gesamten Inhalt des Baums in natürlicher Ordnung entsteht. Diese Liste kann allerdings recht lang werden und kostet offensichtlich zu viel Rechenzeit.
Falsch ist, dass das mittlere Element nicht "[index]" sein dürfte, sondern der tatsächliche Schlüsselwert, nämlich "[self.value(index)]". Da dieser mittlere Wert aber überhaupt nicht gebraucht wird, ist der
Das verstehe ich nicht: der mittlere Wert muss doch zwischen den linken und den rechten liegen, damit der Baum sortiert ist? Muss man das nicht auch prüfen?
Ja, natürlich. Am gegebenen Knoten muss ich prüfen, ob der höchste Wert des linken Teilbaums kleiner als und der niedrigste Wert des rechten Teilbaums größer als der aktuelle Wert ist. Nach oben weitergeben muss ich aber nur den niedrigsten und größten Wert des sich ergebenden Teilbaums, damit der nächsthöhere Knoten ebendiesen Vergleich anstellen kann. Der Wert des aktuellen Knotens wird überhaupt nicht weiter verwendet, und deswegen ist es auch nicht aufgefallen, dass ich hier den Index statt des Werts weitergegeben habe. Ich glaube, ich probiere das nochmal zu korrigieren (auch wenn die Aufgabe ja schon offiziell akzeptiert wurde.
Fehler nicht aufgefallen. DIESE Aufgabe ist also inzwischen erfolgreich gelöst.
Bestens. Hängst Du noch irgendwo?
Ja, wie gesagt habe ich offene Fragen auf dem Issue-Tracker abgelegt (ich habe das Repository jetzt doch auch öffentlich sichtbar gemacht): https://git.openlilylib.org/uliska/algorithms-and-datastructures/issues
Im Moment sind es zwei unterschiedlich geartete Fragen: 1) Bei der Aufgabe, Substrings zu hashen, komme ich einfach nicht über einen Testfall hinweg, bei dem der Algorithmus zu lange braucht. Hier muss es entweder eine Optimierung geben, die ich nicht gefunden habe (z.B. dass unnötig String-Kopien erzeugt werden oder es eine unnötige Schleife gibt) oder einen Sonderfall, der meinen Algorithmus in die Ecke (bzw. in einen Kreis) treibt): https://git.openlilylib.org/uliska/algorithms-and-datastructures/issues/3
2) Bei der Frage, ob ein Graph bipartit ist, scheitere ich an einer "falschen Antwort". Hier muss ich sagen, dass mir die Implikationen der Aufgabe noch etwas schwammit sind und mein Ansatz daher vielleicht zu naiv ist. Ich suche per Breitensuche nach erreichbaren Knoten und färbe alle Nachbarn eines Knotens mit der "anderen" Farbe ein. Wenn ich auf einen Knoten stoße, der bereits entdeckt wurde, aber dieselbe Farbe wie ein aktueller Knoten hat, erkenne ich den Graphen als nicht bipartit. Bei allen angegebenen Beispiel-Eingaben funktioniert das auch, aber der Grader weist einen (mir unbekannten) Test-Fall ab.
Es gibt noch ein paar weitere Aufgaben, die ich noch nicht gelöst habe, aber die sind noch in dem Stadium, in dem ich versuche, alleine klarzukommen (wie schon gesagt: Es geht mir ja nicht darum, die Aufgaben zu bestehen und das Zertifikat zu bekommen, sondern darum, die Sachen zu verstehen).
HG Urs
lg -- t _______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen):
https://lug-freiburg.de/mailman/listinfo/flug
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Sat, Jul 29, 2017 at 09:49:21AM +0200, Urs Liska wrote:
Am 29.07.2017 um 09:15 schrieb tomas@tuxteam.de:
On Sat, Jul 29, 2017 at 12:28:26AM +0200, Urs Liska wrote:
Am 28.07.2017 um 23:31 schrieb tomas@tuxteam.de:
[...]
Der Rückgabewert der rekursiven Funktion ist eine Liste mit den Randwerten der linken und rechten Kinder und dem aktuellen Knoten in der Mitte. "Natürlicher" wäre die Rückgabe von "left + [index] + right",
OK. Darauf wäre ich allerdings nicht gekommen, zumal is_bst einem das Hirn schon auf ein boolean "polt" (is this thing a binary search tree?).
Grrr, das muss ich zugeben. Die Funktion sollte anders heißen. Im Wesentlichen ist es so, dass der Baum in seiner natürlichen Ordnung durchlaufen wird. Sofern eine Fehlerbedingung festgestellt wird, bricht sie ab, andernfalls läuft sie durch und gibt "irgendwas" zurück - dann ist der Baum korrekt.
Semantisch richtig wäre wohl
def main(): tree = TreeOrders() if len(tree.nodes) == 0: print("CORRECT") tree.traverse() print("CORRECT")
Das verführt einem dazu, sich diese "Frage" rekursiv vorzustellen
is_bst(tree): return tree.left.val < tree.val \ and tree.val < tree.right.var \ and is_bst(tree.left) \ and is_bst(tree.right)
(das ist natürlich salopp formuliert, bei Deiner Darstellung des Baums müssen eher solche Dinge stehen wie
self.value(self.left(index)) < self.value(index) ...bzw.
is_bst(self.left(index))...... you get the idea. Man muss natürlich damit klarkommen, dass diese Methoden manchmal None liefern, was den Ausdruck etwas unübersichtlich macht (bei den Vergleichen).
Ich glaube nicht, dass das funktionierten würde. Wenn ich an einem gegebenen Knoten für links und rechts nur einen Boolean-Wert zurückbekomme, kann ich nicht mit dem aktuellen Knoten vergleichen (wie du unten auch schreibst). Daher muss die rekursive Funktion schon die Knoten-Werte des Subtrees zurückgeben.
Ich glaube, ich verstehe, was Du meinst... mein Ansatz würde (vorsicht, ASCII-Grafik):
4 / \ 3 5 / \ 1 6
durchgehen lassen, weil der Teilbaum an 3 "OK" sagen würde, der an 5 auch und 3-4-5 auch ganz manierlich aussieht. Hast recht :)
Ja, natürlich. Am gegebenen Knoten muss ich prüfen, ob der höchste Wert des linken Teilbaums kleiner als und der niedrigste Wert des rechten Teilbaums größer als der aktuelle Wert ist [...]
Sehr richtig. Dann kann Deine Funktion/Methode z.B. "range" heissen, und sie liefert (lo, hi) die gesamte Spannweite des Baums -- das ist ja im wesentlichen, was Du gemacht hast.
Im Moment sind es zwei unterschiedlich geartete Fragen:
Na, was für den Abend. Jetzt habe ich bald Kochdienst :-)
lg - -- tomás
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Hi, Flug
wenn unsere Algorithmenschieberei Euch auf die Nerven geht... bitte schreien, dann ziehen wir uns diskret zurück :-)
lg - -- t
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Sat, Jul 29, 2017 at 09:49:21AM +0200, Urs Liska wrote:
[...]
Im Moment sind es zwei unterschiedlich geartete Fragen:
Bei der Aufgabe, Substrings zu hashen, komme ich einfach nicht über einen Testfall hinweg, bei dem der Algorithmus zu lange braucht. Hier muss es entweder eine Optimierung geben, die ich nicht gefunden habe (z.B. dass unnötig String-Kopien erzeugt werden oder es eine unnötige Schleife gibt) oder einen Sonderfall, der meinen Algorithmus in die Ecke (bzw. in einen Kreis) treibt): https://git.openlilylib.org/uliska/algorithms-and-datastructures/issues/3
Ich vermisse einige Moduli (%) in precompute_hashes. Z.B. muss
y = self._rn_dx ** p_len
eine ziemlich grosse Zahl sein, bei einem mässig (~100) langem Pattern (im Assignment faseln die von bis 10^5), selbst wenn _rn_dx so klein ist wie bei Dir (2) (was ich ein wenig bedrohlich finde, ich weiss nicht, wie sich das auf das Kollissionsverhalten des Hashes auswirkt).
Python kommt mit grossen Zahlen zwar klar, aber sie sind teuer (auf meiner Gurke kippt die Zeit bei mir von 0.8 auf über 4 (Sekunden):
for i in range(60, 100, 1):
... def f(): ... return 2**i ... timeit.timeit(f) ... print(i) ... 0.8464090824127197 60 0.8901400566101074 61 0.8901631832122803 62 4.829195976257324 63 3.9598159790039062 64 4.131256103515625 65
Da sieht man auch, wieviele Bits sich Python bei einem 64 bit-System als tag bits reserviert, nämlich 3. Ab 2^62 muss Python die Maschinenintegers verlassen und "lange Integers" nehmen. Schick aber langsam.
Vielleicht ist eine Exponentiation in der Schleife, mit Modulo dazwischen richtig. Ganz luxuriös wäre "modular exponentiation" [1], aber ich glaube, die Fussgängermethode wird ausreichen (ein erster Test bei mir liefert: eher nicht -- uh, oh):
def mexp(x, y):
... e = x ... for i in range(1, y, 1): ... e = (e*x) % 1000000009 ... return e ...
mexp(2, 6)
64
def f():
... return mexp(17, 100) ...
timeit.timeit(f)
27.922509908676147
Entweder übersehe ich etwas, oder es braucht tatsächlich [1].
Ganz fies wird, wenn Du das "unmodulierte" y weiter unten für jedes Character in der Schleife nimmst: dann muss Python jedes einfache Integer in ein "fettes" verwandeln...
So viel kriege ich noch heute Abend zusammen.
Fazit: teste Dein Programm mit richtig langen Strings (pattern length 100 oder so).
lg - -- t
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Sat, Jul 29, 2017 at 11:45:49PM +0200, tomas wrote:
[...]
Vielleicht ist eine Exponentiation in der Schleife, mit Modulo dazwischen richtig. Ganz luxuriös wäre "modular exponentiation" [1] [...]
Referenz fehlte:
[1] https://en.wikipedia.org/wiki/Modular_exponentiation
- -- t
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Stellt sich heraus, dass Python von Haus aus modular exponentiation hat:
pow(17, 100, 1000000009)
901726059
def f():
... return pow(17, 100, 1000000009) ...
timeit.timeit(f)
1.7400319576263428
(ausserdem muss ich nachschauen, was die timeit-Defaults sind. Der macht bestimmt mehrere Runden, das kann nicht 1.7 Sek... eher Millis sein. Whatever.
lg - -- t
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Sat, Jul 29, 2017 at 11:55:09PM +0200, tomas@tuxteam.de wrote:
[...]
(ausserdem muss ich nachschauen, was die timeit-Defaults sind. Der
Aha. Lesen hilft. Default bei timeit ist 10^6 Runden. Zeiten also in μS/Runde. Python ist nicht gerade schnell, aber sooo langsam dann auch nicht ;-)
lg - -- t
Am 29.07.2017 um 23:55 schrieb tomas@tuxteam.de:
Stellt sich heraus, dass Python von Haus aus modular exponentiation hat:
pow(17, 100, 1000000009)
901726059
def f():
... return pow(17, 100, 1000000009) ...
timeit.timeit(f)
1.7400319576263428
(ausserdem muss ich nachschauen, was die timeit-Defaults sind. Der macht bestimmt mehrere Runden, das kann nicht 1.7 Sek... eher Millis sein. Whatever.
Das war es tatsächlich, brachte den Timeout nach 10 Sekunden herunter auf 1,6 Sekunden für den längsten Testfall.
Tja, jetzt habe ich dieses Assignment auch vervollständigt - ohne aber so wirklich verstanden zu haben, was ich mache :-( Offensichtlich fällt es mir recht leicht, so Dinge wie etwa das Durchqueren von Graphen zu verstehen, aber die konkret mathematischen Sachen bilden doch noch eine natürliche Grenze. Ich hab zwar mal freiwillig Mathe-LK gemacht und auch ziemlich gut durchgezogen - aber das ist doch auch schon 25 Jahre her ...
HG Urs
lg -- t _______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen):
https://lug-freiburg.de/mailman/listinfo/flug
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Tue, Aug 01, 2017 at 10:00:24PM +0200, Urs Liska wrote:
[...]
(ausserdem muss ich nachschauen, was die timeit-Defaults sind. Der macht bestimmt mehrere Runden, das kann nicht 1.7 Sek... eher Millis sein. Whatever.
Das war es tatsächlich, brachte den Timeout nach 10 Sekunden herunter auf 1,6 Sekunden für den längsten Testfall.
Tja, jetzt habe ich dieses Assignment auch vervollständigt - ohne aber so wirklich verstanden zu haben, was ich mache :-(
Das liegt möglicherweise daran, dass an diesem Rabin-Karp mehrere Akteure beteiligt sind (das ist auch bei den Graphen so, die anderen treten aber mehr in den Hintergrund und sind sozusagen Teil des Chors :)
Ich nenne mal welche, ohne Anspruch auf Vollständigkeit zu erheben. Wenn Du bei einem Punkt sagst "kann ich", dann kansst Du den streichen, sonst... reingucken (wenn Du Hilfe dabei brauchst, melde Dich. Die Liste ist sicher auch hilfreich darin)
- (Abstrakte) Daten und ihre Darstellungen Buchstaben, Strings, Zahlen; Binäre darstellung. Maschinenwort.
- Arithmetik (abstrakt und in Maschinendarstellung). Grundrechenarten und Modulo. Primzahlen
- Hashing
Die wirken alle ein wenig gleichberechtigt hier zusammen, es lohnt sich aber, sie jeweils als eigenständige Persönlichkeiten kennenzulernen.
Offensichtlich fällt es mir recht leicht, so Dinge wie etwa das Durchqueren von Graphen zu verstehen, aber die konkret mathematischen Sachen bilden doch noch eine natürliche Grenze. Ich hab zwar mal freiwillig Mathe-LK gemacht und auch ziemlich gut durchgezogen - aber das ist doch auch schon 25 Jahre her ...
Ich habe da oben mal eine (diffuse) Theorie aufgestellt. Ich denke, das Grundwerkzeug hast Du, die nötige Vertrautheit, gleichzeitig drei davon auf der Werkbank liegen zu haben ohne den Überblick zu verlieren braucht etwas Übung.
lg - -- t
Am 2017-08-02 11:19, schrieb tomas@tuxteam.de:
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Tue, Aug 01, 2017 at 10:00:24PM +0200, Urs Liska wrote:
[...]
Tja, jetzt habe ich dieses Assignment auch vervollständigt - ohne aber so wirklich verstanden zu haben, was ich mache :-(
Das liegt möglicherweise daran, dass an diesem Rabin-Karp mehrere Akteure beteiligt sind (das ist auch bei den Graphen so, die anderen treten aber mehr in den Hintergrund und sind sozusagen Teil des Chors :)
Ich nenne mal welche, ohne Anspruch auf Vollständigkeit zu erheben. Wenn Du bei einem Punkt sagst "kann ich", dann kansst Du den streichen, sonst... reingucken (wenn Du Hilfe dabei brauchst, melde Dich. Die Liste ist sicher auch hilfreich darin)
- (Abstrakte) Daten und ihre Darstellungen Buchstaben, Strings, Zahlen; Binäre darstellung. Maschinenwort.
Mit "Maschinenwort" meinst du das Problem, dass es haklig wird, wenn ein Datentyp (v.a Integer) die Größe eines (systemabhängigen) Maschinenworts überschreitet? Sprachen wie C produzieren dann einen stummen Überlauf (falsche Zahlen ohne Fehlermeldung), Python regelt das für dich, wird aber dramatisch langsamer. Wenn es das ist: "kann ich", der Rest ist mir auch klar.
- Arithmetik (abstrakt und in Maschinendarstellung).
Arithmetik in Maschinendarstellung? Weiß ich jetzt nicht genau, was du meinst. Manche Sachen sind mir klar wie z.B. Diverses was mit Bit-Shifting zu tun hat, vieles Andere nicht. Keine Ahnung, wie die Maschine Multiplikationen regelt (und keine Ahnung, ab wann ich dieses Wissen brauche).
Grundrechenarten und Modulo. Primzahlen
Bei Modulo und Primzahlen sind mir Grundlagen durchaus bekannt, höhere Dinge aber überhaupt nicht. Dieser Artikel über das Fermatsche Theorem (bestimmte Eigenschaften von Zahlen hoch eine Primzahl) fallen mir sehr schwer. Auch weitergehende Modulo-Regeln (was passiert, wenn ich in welcher Reihenfolge Modulo-Operationen durchführe, und v.a., wie kann ich davon profitieren?) - ziemlich blank ...
- Hashing
Das Konzept von Hash-Funktionen und Hash-Chains ist mir im Kurs klar geworden. Die Mathematik von guten Hash-Funktionen dagegen nicht. Und auch wenn ich verstanden habe wie diese polynomische String-Hash-Funktion funktioniert, ist mir überhaupt nicht klar, wie die Dozenten auf die Idee gekommen sind, sie in die entsprechende Python-Funktion zu übertragen. Gleiches gilt für die Idee der vorberechneten Hashes. Ich kann leicht nachvollziehen, dass man einmal einen ganzen String (zeichenweise) hasht und dann für jede weitere Stelle praktisch nur eine Funktion berechnen muss. Nachzuvollziehen, wie das mit den Summenfunktionen tatsächlich funktioniert, ist schon schwieriger. Und das in eine funktionierende Python-Routine zu übertragen, hätte ich nicht alleine gewusst.
Die wirken alle ein wenig gleichberechtigt hier zusammen, es lohnt sich aber, sie jeweils als eigenständige Persönlichkeiten kennenzulernen.
Offensichtlich fällt es mir recht leicht, so Dinge wie etwa das Durchqueren von Graphen zu verstehen, aber die konkret mathematischen Sachen bilden doch noch eine natürliche Grenze. Ich hab zwar mal freiwillig Mathe-LK gemacht und auch ziemlich gut durchgezogen - aber das ist doch auch schon 25 Jahre her ...
Ich habe da oben mal eine (diffuse) Theorie aufgestellt. Ich denke, das Grundwerkzeug hast Du, die nötige Vertrautheit, gleichzeitig drei davon auf der Werkbank liegen zu haben ohne den Überblick zu verlieren braucht etwas Übung.
Diese Theorie kenne ich auch, ich nehme immer das Bild eines Gleichungssystems, das zu viele Unbekannte hat und in dem man erst dann eine Lösung findet, wenn alle gleichzeitig (zufällig) den richtigen Wert haben. Aber das trifft hier glaube ich nur bedingt zu. Ich habe sicher das Grundwerkzeug, Algorithmen zu verstehen und bin mit einigen der relevanten Parameter vertraut (z.B. inzwischen den Implikationen der verwendeten Datenstruktur). Bei den komplexeren mathematischen Bestandteilen fehlt mir aber teilweise tatsächlich ein Grundverständnis (entweder vergessen oder teilweise noch nie wirklich damit beschäftigt).
Ich bin mal gespannt, wie sich das im nächsten Kurs (String-Algorithmen) und im optionalen letzten Modul des Graphen-Kurses (erweiterte Aufgaben und anscheinend 1000x so schnelle Navigations-Algorithmen mit echten Kartendaten) entwickelt.
HG und herzlichen Dank Urs
lg
- -- t
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux)
iEYEARECAAYFAlmBmR4ACgkQBcgs9XrR2kZ2JwCdHKNqK8mXlhEq0KfdgpJrXFAW cDgAnjOau58gPpRXVUAb1BkUwvBOM+OS =UnJE -----END PGP SIGNATURE----- _______________________________________________ Freiburger Linux User Group Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen): https://lug-freiburg.de/mailman/listinfo/flug
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Thu, Aug 03, 2017 at 11:57:43AM +0200, ul@openlilylib.org wrote:
Am 2017-08-02 11:19, schrieb tomas@tuxteam.de:
[...]
- (Abstrakte) Daten und ihre Darstellungen Buchstaben, Strings, Zahlen; Binäre darstellung. Maschinenwort.
Mit "Maschinenwort" meinst du das Problem, dass es haklig wird, wenn ein Datentyp (v.a Integer) die Größe eines (systemabhängigen) Maschinenworts überschreitet? Sprachen wie C produzieren dann einen stummen Überlauf (falsche Zahlen ohne Fehlermeldung), Python regelt das für dich, wird aber dramatisch langsamer. Wenn es das ist: "kann ich", der Rest ist mir auch klar.
Klingt so, ja :-)
- Arithmetik (abstrakt und in Maschinendarstellung).
Arithmetik in Maschinendarstellung? Weiß ich jetzt nicht genau, was du meinst. Manche Sachen sind mir klar wie z.B. Diverses was mit Bit-Shifting zu tun hat, vieles Andere nicht. Keine Ahnung, wie die Maschine Multiplikationen regelt (und keine Ahnung, ab wann ich dieses Wissen brauche).
Im wesentlichen ja. Es gibt einerseits die Arithmetik (natürliche, ganze, rationale und reele Zahlen, Grundrechenarten) und die Kompromisse, die ein Computer so machen muss, um "so zu tun, als ob"). Aus Deinen Bemerkungen schliesse ich, dass Du ein brauchbares "working model" davon hast, das Du bei Bedarf verfeinern kannst.
Grundrechenarten und Modulo. Primzahlen
Bei Modulo und Primzahlen sind mir Grundlagen durchaus bekannt, höhere Dinge aber überhaupt nicht. Dieser Artikel über das Fermatsche Theorem (bestimmte Eigenschaften von Zahlen hoch eine Primzahl) fallen mir sehr schwer. Auch weitergehende Modulo-Regeln (was passiert, wenn ich in welcher Reihenfolge Modulo-Operationen durchführe, und v.a., wie kann ich davon profitieren?) - ziemlich blank ...
Naja, das ist nach oben offen und heisst Zahlentheorie. Die zeichnet sich durch böse Überraschungen aus. Dinge, die sehr leicht zu formulieren sind stellen sich als äusserst schwierig zu beweisen heraus (oder zu widerlegen, whatever). Die Goldbachsche Vermutung[1] ist das eine Paradebeispiel. Wenn sich bei Dir die Grenzen "ausgefranst" anfühlen, dann ist das ein gutes Zeichen :)
Zu Modulo musst Du hier lediglich wissen: das ist der Rest der Division einer Zahl durch eine andere. Meistens (die Konventionen variieren aber!) nimmt man den *positiven* Rest:
5 mod 7 == 5 21 mod 7 == 0 -1 mod 7 == 6 (*)
(*) immer die Doku konsultieren :-)
Die Rechenarten ergeben sich daraus:
(a + b) mod c == (a mod c + b mod c) mod c (a*b) mod c == ( (a mod c) * (b mod c) ) mod c
Es loht sich vielleicht (Verständnis ist oft Vertrautwerden), wenn Du Dir die Exponentiation mal genauer anguckst.
- Hashing
Das Konzept von Hash-Funktionen und Hash-Chains ist mir im Kurs klar geworden. Die Mathematik von guten Hash-Funktionen dagegen nicht.
Das liegt daran, dass nicht genau definiert ist, was eine gute Hashfunktion ist. Im wesentlichen ist eine Hashfunktion eine Funktion, die "grosse Datenklumpen" auf "kleine Datenklumpen" abbildet, meistens, weil letztere leichter zu handhaben sind. Abgesehen davon will man meist, dass zwei unterschiedliche Datenklumpen unterschiedliche Hashwerte besitzen (wenn nicht, nennt sich das eine Kollision: die iist natürlich nicht immer zu vermeiden: gehen wir von z.B. Datenklumpen von 10MB aus und hashen wir sie auf 100 Bit "runter", dann müssen sich im Schnitt 10^5 grosse Klumpen auf einem Hash treffen. Doof.
D.h. wir wollen das "typische", "praktisch vorkommende" Datenklumpen "nicht zu oft" kollidieren. Und da fängt die schwarze Magie an :-)
Abgesehen davon gibt es noch spezialisierte Hashfunktionen, die bestimmte Eigenschaften haben:
- perfect hashing: nie eine Kollision (wie geht das denn?). Das geht dann, wenn die Ausgangsmenge der grossen Klumpen im Voraus bekannt ist. Man knetet die Hashfunktion so lange, bis man eine bekommt, die (für diese Menge) nicht kollidiert. Anwendung findet das z.B. in der Menge der Schlüsselworte einer Sprache. Mach mal "man gperf" :-)
- similarity hashing Man will, dass die Hashes von ähnlichen Klumpen auch ähnlich sind (was auch immer ähnlich sei: z.B. Dokumente mit vielen ähnlichen Wörtern sollen auf Bitwürste abgebildet werden, die sich in wenigen Bits unterscheiden). Gut für Dokumenten- und Bildersuche
- kryptographische Hashes Es soll möglichst schwer sein, aus dem Hash Rückschlüsse auf den Originalklumpen zu ziehen. Nach dem heutigen Stand der Technik. Und wenn man nicht NSA heisst. Weites Thema :)
Und auch wenn ich verstanden habe wie diese polynomische String-Hash-Funktion funktioniert, ist mir überhaupt nicht klar, wie die Dozenten auf die Idee gekommen sind, sie in die entsprechende Python-Funktion zu übertragen. Gleiches gilt für die Idee der vorberechneten Hashes. Ich kann leicht nachvollziehen, dass man einmal einen ganzen String (zeichenweise) hasht und dann für jede weitere Stelle praktisch nur eine Funktion berechnen muss.
OK. Das ist was für ein eigenes Posting. Dass man das stellenweise machen kann liegt an der speziellen Konstruktion des Hashes (ein "rolling hash"[2]. Das wird ausgiebig in Tools wie rsync (und ich glaube auch diff) genutzt. Vermutlich macht diese Eigenschaft einen Hash auch besonders unbrauchbar für einen kryptographischen Hash -- Bauchgefühl, ich habe keinen Beweis für sowas ;-)
Nachzuvollziehen, wie das mit den Summenfunktionen tatsächlich funktioniert, ist schon schwieriger. Und das in eine funktionierende Python-Routine zu übertragen, hätte ich nicht alleine gewusst.
Klar. Musst wahrscheinlich kleiner anfangen und den Turm langsam aufbauen.
Diese Theorie kenne ich auch, ich nehme immer das Bild eines Gleichungssystems, das zu viele Unbekannte hat und in dem man erst dann eine Lösung findet, wenn alle gleichzeitig (zufällig) den richtigen Wert haben.
:-)
Aber das trifft hier glaube ich nur bedingt zu. Ich habe sicher das Grundwerkzeug, Algorithmen zu verstehen und bin mit einigen der relevanten Parameter vertraut (z.B. inzwischen den Implikationen der verwendeten Datenstruktur). Bei den komplexeren mathematischen Bestandteilen fehlt mir aber teilweise tatsächlich ein Grundverständnis (entweder vergessen oder teilweise noch nie wirklich damit beschäftigt).
Da gibt es nicht so komplexe Zusammenhänge, die verkleiden sich nur als solche :)
Ich bin mal gespannt, wie sich das im nächsten Kurs (String-Algorithmen) und im optionalen letzten Modul des Graphen-Kurses (erweiterte Aufgaben und anscheinend 1000x so schnelle Navigations-Algorithmen mit echten Kartendaten) entwickelt.
Klingt ja sehr vergnüglich
[1] https://en.wikipedia.org/wiki/Goldbach_conjecture [2] https://en.wikipedia.org/wiki/Rolling_hash
lg - -- t
Am 03.08.2017 um 13:53 schrieb tomas@tuxteam.de:
On Thu, Aug 03, 2017 at 11:57:43AM +0200, ul@openlilylib.org wrote:
Am 2017-08-02 11:19, schrieb tomas@tuxteam.de:
[...]
Zu Modulo musst Du hier lediglich wissen: das ist der Rest der Division einer Zahl durch eine andere. Meistens (die Konventionen variieren aber!) nimmt man den *positiven* Rest:
5 mod 7 == 5 21 mod 7 == 0 -1 mod 7 == 6 (*)
(*) immer die Doku konsultieren :-)
Die Rechenarten ergeben sich daraus:
(a + b) mod c == (a mod c + b mod c) mod c (a*b) mod c == ( (a mod c) * (b mod c) ) mod c
Es loht sich vielleicht (Verständnis ist oft Vertrautwerden), wenn Du Dir die Exponentiation mal genauer anguckst.
Danke, jetzt hat es klick gemacht. Ich hatte nie so recht verstanden, wieso man bei einzelnen Operanden Modulo machen kann, ohne das Ergebnis zu verfälschen. Natürlich ist es sonnenklar (nur ich stand auf dem Schlauch), dass man das nur dann machen kann, wenn man für das Ergebnis auch den Modulo berechnet.
Jetzt ist mir auch klar, warum (a^b) mod c = ((a mod c)^b) mod c ist, und dass man damit immense große Zahlen vermeiden kann, wenn man hinterher sowieso wieder nur am Modulo interessiert ist.
- Hashing
Das Konzept von Hash-Funktionen und Hash-Chains ist mir im Kurs klar geworden. Die Mathematik von guten Hash-Funktionen dagegen nicht.
Das liegt daran, dass nicht genau definiert ist, was eine gute Hashfunktion ist.
Ich habe mich wahrscheinlich nicht klar genug ausgedrückt. Dass ich zum jetzigen Zeitpunkt nicht erwarten kann, mir selber für gegebene Datenstrukturen geeignete Hashfunktionen auszudenken, ist mir schon klar. Aber ich hatte auch noch große Schwierigkeiten, den Ausführungen über die im Kurs vorgegebenen Funktionen zu folgen.
Im wesentlichen ist eine Hashfunktion eine Funktion, die "grosse Datenklumpen" auf "kleine Datenklumpen" abbildet, meistens, weil letztere leichter zu handhaben sind. Abgesehen davon will man meist, dass zwei unterschiedliche Datenklumpen unterschiedliche Hashwerte besitzen (wenn nicht, nennt sich das eine Kollision: die iist natürlich nicht immer zu vermeiden: gehen wir von z.B. Datenklumpen von 10MB aus und hashen wir sie auf 100 Bit "runter", dann müssen sich im Schnitt 10^5 grosse Klumpen auf einem Hash treffen. Doof.
D.h. wir wollen das "typische", "praktisch vorkommende" Datenklumpen "nicht zu oft" kollidieren. Und da fängt die schwarze Magie an :-)
Abgesehen davon gibt es noch spezialisierte Hashfunktionen, die bestimmte Eigenschaften haben:
- perfect hashing: nie eine Kollision (wie geht das denn?). Das geht dann, wenn die Ausgangsmenge der grossen Klumpen im Voraus bekannt ist. Man knetet die Hashfunktion so lange, bis man eine bekommt, die (für diese Menge) nicht kollidiert. Anwendung findet das z.B. in der Menge der Schlüsselworte einer Sprache. Mach mal "man gperf" :-)
(kleiner Scherz. Natürlich weiß ich, wie ich im Internet Manpages für nicht installierte Programme finde. Sehr interessant!)
- similarity hashing Man will, dass die Hashes von ähnlichen Klumpen auch ähnlich sind (was auch immer ähnlich sei: z.B. Dokumente mit vielen ähnlichen Wörtern sollen auf Bitwürste abgebildet werden, die sich in wenigen Bits unterscheiden). Gut für Dokumenten- und Bildersuche
Interessant. Im Kurs lag der Schwerpunkt eher darauf, diesen Fall möglichst zu vermeiden, um das Risiko von Kollisionen zu minimieren. Also: kleine Unterschiede in den Eingangsdaten sollten möglichst große und statistisch möglichst gleichmäßig verteilte Ergebnisse produzieren.
Eine weitere Kategorie, über die im Kurs gesprochen wurde, waren "Universelle Familien von Hash-Funktionen", die nicht perfekt sind, aber für zwei unterschiedliche Eingabewerte eine Kollisionswahrscheinlichkeit von höchstens 1/m (m = Größe der Hash-Tabelle) haben. https://en.wikipedia.org/wiki/Universal_hashing
[...]
Herzliche Grüße Urs
_______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen):
https://lug-freiburg.de/mailman/listinfo/flug
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Mon, Aug 07, 2017 at 07:30:45AM +0200, Urs Liska wrote:
Am 03.08.2017 um 13:53 schrieb tomas@tuxteam.de:
[...]
5 mod 7 == 5
[...]
Danke, jetzt hat es klick gemacht.
Na, wenn's sooo einfach geht ;-D
Ich fand diesen Modularkram immer ein wenig schwer zu lesen/schreiben:
(foo mod bar ...) mod bar
Habe ich jetzt ein mod vergessen? Es fühlt sich wie Distributivgesetz an, man muss aber "draussen" noch ein mod liegen lassen.
Jetzt ist mir auch klar, warum (a^b) mod c = ((a mod c)^b) mod c ist, und dass man damit immense große Zahlen vermeiden kann, wenn man hinterher sowieso wieder nur am Modulo interessiert ist.
Jaja. Der obskure Hinweis in der Aufgabe "immer schön modulo machen" oder so ähnlich.
[...]
Ich habe mich wahrscheinlich nicht klar genug ausgedrückt. Dass ich zum jetzigen Zeitpunkt nicht erwarten kann, mir selber für gegebene Datenstrukturen geeignete Hashfunktionen auszudenken, ist mir schon klar. Aber ich hatte auch noch große Schwierigkeiten, den Ausführungen über die im Kurs vorgegebenen Funktionen zu folgen.
Das mag daran liegen, dass oft Konzept und Implementierungsdetails in der Präsentation wild durcheinandergemischt werden. Am Ende behält man den Eindruck, Hashing hätte "irgendwie mit Primzahlen zu tun" (was nur ganz bedingt stimmt), und "Primzahlen sind schwierig" (was schon eher stimmt, aber eine andere Geschichte ist).
Ja, Primzahlen nimmt man gerne zur Implementierung, aber nur, um sich aus der Affäre zu ziehen -- oder um den Geist im Computer zu verwirren. Aber mit der Grundidee des Hashings haben sie wenig zu tun.
Die Sache mit Modulo ist ja naheliegend (man hat M Kandidaten und N Plätze, also nimmt man erst M mod N und "wickelt" sozusagen M um N "herum" -- so könnte man vorgehen, wenn man eine (vorher nicht bekannte) Zahl M an Leuten auf N Tische verteilt. Wenn die Leute auch noch je mit einer Nummer ankommen (Perso), dann ist es noch besser: die Tischnummer N ist einfach die Endnummer des Persos. Dann weisst Du, welchen Tisch Du ansteuern musst, wenn Du jemanden suchst.
Das hat man auch für Variablennamen gerne benutzt, bis wir dummen Programmierer/innen kamen und unsere Variablen gerne ORT1, GESCHW1 BLUB1 nannten und dann alle an einem (überfüllten) Tisch landeten.
Das viel zu naive Modulo (meist eine Zweierpotenz) neigte dazu, die letzten Bytes "unversehrt" in den Hashwert "durchzureichen" und die (verdeckte) Struktur der Daten machten Interferenzen (man könnte sagen, ein Moiré-Effekt [1]). Dann kamen die Primzahlen.
Wenn jemand uns böse will, dann müssen wir evtl. würfeln (z.B. mit universal hashing, wie Du erwähnt hast). Eine feste Hashfunktion könnte unsere/r Gegner/in schnell rausbekommen.
lg
[1] https://en.wikipedia.org/wiki/Moir%C3%A9 - -- t
Am 07.08.2017 um 11:15 schrieb tomas@tuxteam.de:
On Mon, Aug 07, 2017 at 07:30:45AM +0200, Urs Liska wrote:
Am 03.08.2017 um 13:53 schrieb tomas@tuxteam.de:
[...]
5 mod 7 == 5
[...]
Danke, jetzt hat es klick gemacht.
Na, wenn's sooo einfach geht ;-D
Ich fand diesen Modularkram immer ein wenig schwer zu lesen/schreiben:
(foo mod bar ...) mod bar
Habe ich jetzt ein mod vergessen? Es fühlt sich wie Distributivgesetz an, man muss aber "draussen" noch ein mod liegen lassen.
:-)
[...]
Ich habe mich wahrscheinlich nicht klar genug ausgedrückt. Dass ich zum jetzigen Zeitpunkt nicht erwarten kann, mir selber für gegebene Datenstrukturen geeignete Hashfunktionen auszudenken, ist mir schon klar. Aber ich hatte auch noch große Schwierigkeiten, den Ausführungen über die im Kurs vorgegebenen Funktionen zu folgen.
Das mag daran liegen, dass oft Konzept und Implementierungsdetails in der Präsentation wild durcheinandergemischt werden. Am Ende behält man den Eindruck, Hashing hätte "irgendwie mit Primzahlen zu tun" (was nur ganz bedingt stimmt), und "Primzahlen sind schwierig" (was schon eher stimmt, aber eine andere Geschichte ist).
Tja, die Sache mit der didaktischen Aufbereitung. Die ist durchaus unterschiedlich gut bei den verschiedenen Dozenten (auch) dieser Kurse. Hier hatten sie m.E. das Problem, dass sie nicht wirklich auf das Entwickeln von Hash-Funktionen eingehen wollten (ich denke auch, dass das den Rahmen wirklich sprengen würde), deshalb haben sie die beiden verwendeten Funktionen doch relativ willkürlich vorgesetzt (dann aber wieder recht ausführlich mathematisch bewiesen). Dass Hashfunktionen schwierig sind und wir jetzt halt einfach mit den uns vorgesetzten und für den Zweck gut geeigneten Funktionen zu arbeiten haben, wurde dadurch nicht so klar wie es hätte sein sollen.
Interessant ist auch, dass der anscheinend ranghöchste der Dozenten didaktisch mit Abstand der Schlechteste ist ;-)
Ja, Primzahlen nimmt man gerne zur Implementierung, aber nur, um sich aus der Affäre zu ziehen -- oder um den Geist im Computer zu verwirren. Aber mit der Grundidee des Hashings haben sie wenig zu tun.
Die Sache mit Modulo ist ja naheliegend (man hat M Kandidaten und N Plätze, also nimmt man erst M mod N und "wickelt" sozusagen M um N "herum" -- so könnte man vorgehen, wenn man eine (vorher nicht bekannte) Zahl M an Leuten auf N Tische verteilt. Wenn die Leute auch noch je mit einer Nummer ankommen (Perso), dann ist es noch besser: die Tischnummer N ist einfach die Endnummer des Persos. Dann weisst Du, welchen Tisch Du ansteuern musst, wenn Du jemanden suchst.
Das hat man auch für Variablennamen gerne benutzt, bis wir dummen Programmierer/innen kamen und unsere Variablen gerne ORT1, GESCHW1 BLUB1 nannten und dann alle an einem (überfüllten) Tisch landeten.
Das viel zu naive Modulo (meist eine Zweierpotenz) neigte dazu, die letzten Bytes "unversehrt" in den Hashwert "durchzureichen" und die (verdeckte) Struktur der Daten machten Interferenzen (man könnte sagen, ein Moiré-Effekt [1]).
Wenn man dagegen fortlaufende Daten hat (z.B. weil ein Schlüssel automatisch hochgezählt wird oder weil man Array-Indizes nutzen kann, dann würde ein einfaches Modulo die ideale Verteilung bringen.
Dann kamen die Primzahlen.
Wenn jemand uns böse will, dann müssen wir evtl. würfeln (z.B. mit universal hashing, wie Du erwähnt hast). Eine feste Hashfunktion könnte unsere/r Gegner/in schnell rausbekommen.
Interessante Fragestellung, wie man bei einem Adressbuch die Daten böswillig zurechtrücken wollte (nur das wurde als Beispiel verwendet). Vielleicht wäre das mal ein lohnendes Thema für die amerikanische Wahlbetrug-Kommission. Drei bis fünf Millionen schlecht gehashte Wählereinträge, weil die Schwarzen und Hispanics im Durchschnitt andere Namen haben als stramm-rechte Amerikaner :-/
HG Urs
lg
[1] https://en.wikipedia.org/wiki/Moir%C3%A9 -- t _______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen):
https://lug-freiburg.de/mailman/listinfo/flug
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Wed, Aug 09, 2017 at 12:25:17AM +0200, Urs Liska wrote:
[...]
Interessant ist auch, dass der anscheinend ranghöchste der Dozenten didaktisch mit Abstand der Schlechteste ist ;-)
Die Güte von Didaktik ist oft, wie das Hashing, sehr kontextabhängig :)
Oder: "all generalizations suck".
[...]
Interessante Fragestellung, wie man bei einem Adressbuch die Daten böswillig zurechtrücken wollte (nur das wurde als Beispiel verwendet). Vielleicht wäre das mal ein lohnendes Thema für die amerikanische Wahlbetrug-Kommission. Drei bis fünf Millionen schlecht gehashte Wählereinträge, weil die Schwarzen und Hispanics im Durchschnitt andere Namen haben als stramm-rechte Amerikaner :-/
Naja. Eine "korrekte" Hashtable würde nur langsam werden, aber trotzdem richtige Ergebnisse liefern. Wie das in der Praxis aussieht: [1], da haben irgendwelche Webprogrammierer Pythons Hashfunktion allzu naiv für etwas verwendet, an dessen andere Seite das böse, böse Internet hing. Nur ein denial of service attack, aber immerhin ;-)
(Soweit ich weiss haben sich die anderen zwei P's auch damit herumschlagen müssen).
lg
[1] https://mail.python.org/pipermail/python-dev/2011-December/115116.html - -- t
Hallo Tomás,
Am 29.07.2017 um 23:45 schrieb tomas@tuxteam.de:
On Sat, Jul 29, 2017 at 09:49:21AM +0200, Urs Liska wrote:
[...]
Im Moment sind es zwei unterschiedlich geartete Fragen:
Bei der Aufgabe, Substrings zu hashen, komme ich einfach nicht über einen Testfall hinweg, bei dem der Algorithmus zu lange braucht. Hier muss es entweder eine Optimierung geben, die ich nicht gefunden habe (z.B. dass unnötig String-Kopien erzeugt werden oder es eine unnötige Schleife gibt) oder einen Sonderfall, der meinen Algorithmus in die Ecke (bzw. in einen Kreis) treibt):
https://git.openlilylib.org/uliska/algorithms-and-datastructures/issues/3
Ich vermisse einige Moduli (%) in precompute_hashes. Z.B. muss
y = self._rn_dx ** p_len
eine ziemlich grosse Zahl sein,
stimmt. Ich glaube, hier sieht man, wie ich schwimme. Ich war eigentlich von Varianten mit deutlich mehr %-Operationen ausgegangen und hatte dann gedacht, dass diese vielleicht unnötig Zeit kosten. Wahrscheinlich habe ich da dann in die falsche Richtung "verbessert" - eben, weil ich die Sache nicht völlig durchschaue.
Vielen Dank für deine Überlegungen und Ausführungen, die mich hoffentlich in eine bessere Richtung lenken - allerdings nicht mehr heute Abend, da ist mir das doch zu kompliziert. Ein Mentor hat im Forum übrigens geschrieben, dass sich alle, die Probleme mit der Laufzeit haben, sich mal "Schnelleres Modulo" (https://en.wikipedia.org/wiki/Fermat%27s_little_theorem) anschauen sollten.
Ich melde mich, falls es weitere Erkenntnisse gibt. HG Urs
bei einem mässig (~100) langem Pattern (im Assignment faseln die von bis 10^5), selbst wenn _rn_dx so klein ist wie bei Dir (2) (was ich ein wenig bedrohlich finde, ich weiss nicht, wie sich das auf das Kollissionsverhalten des Hashes auswirkt).
Python kommt mit grossen Zahlen zwar klar, aber sie sind teuer (auf meiner Gurke kippt die Zeit bei mir von 0.8 auf über 4 (Sekunden):
for i in range(60, 100, 1):
... def f(): ... return 2**i ... timeit.timeit(f) ... print(i) ... 0.8464090824127197 60 0.8901400566101074 61 0.8901631832122803 62 4.829195976257324 63 3.9598159790039062 64 4.131256103515625 65
Da sieht man auch, wieviele Bits sich Python bei einem 64 bit-System als tag bits reserviert, nämlich 3. Ab 2^62 muss Python die Maschinenintegers verlassen und "lange Integers" nehmen. Schick aber langsam.
Vielleicht ist eine Exponentiation in der Schleife, mit Modulo dazwischen richtig. Ganz luxuriös wäre "modular exponentiation" [1], aber ich glaube, die Fussgängermethode wird ausreichen (ein erster Test bei mir liefert: eher nicht -- uh, oh):
def mexp(x, y):
... e = x ... for i in range(1, y, 1): ... e = (e*x) % 1000000009 ... return e ...
mexp(2, 6)
64
def f():
... return mexp(17, 100) ...
timeit.timeit(f)
27.922509908676147
Entweder übersehe ich etwas, oder es braucht tatsächlich [1].
Ganz fies wird, wenn Du das "unmodulierte" y weiter unten für jedes Character in der Schleife nimmst: dann muss Python jedes einfache Integer in ein "fettes" verwandeln...
So viel kriege ich noch heute Abend zusammen.
Fazit: teste Dein Programm mit richtig langen Strings (pattern length 100 oder so).
lg -- t _______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen):
https://lug-freiburg.de/mailman/listinfo/flug
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Sat, Jul 29, 2017 at 09:49:21AM +0200, Urs Liska wrote:
Bei der Frage, ob ein Graph bipartit ist, scheitere ich an einer "falschen Antwort". Hier muss ich sagen, dass mir die Implikationen der Aufgabe noch etwas schwammit sind und mein Ansatz daher vielleicht zu naiv ist.
?
Ich suche per Breitensuche nach erreichbaren Knoten und färbe alle Nachbarn eines Knotens mit der "anderen" Farbe ein. Wenn ich auf einen Knoten stoße, der bereits entdeckt wurde, aber dieselbe Farbe wie ein aktueller Knoten hat, erkenne ich den Graphen als nicht bipartit.
Sieht korrekt aus, auch lesbar. Daher mein Fragezeichen da oben. Dem Code nach zu urteilen hast Du verstanden, worum es geht.
Bei allen angegebenen Beispiel-Eingaben funktioniert das auch, aber der Grader weist einen (mir unbekannten) Test-Fall ab.
Probier mal das:
5 5 1 2 3 4 4 5 5 3
Ist nicht bipartit. Dein Code wird aber (ich riskiere eine Blamage: ich habe es nicht getestet!) behaupten, es sei bipartit. Was fehlt noch?
Entweder blamiere ich mich jetzt, oder Du findest einen Bug :^)
lg - -- t
Am 31.07.2017 um 09:10 schrieb tomas@tuxteam.de:
On Sat, Jul 29, 2017 at 09:49:21AM +0200, Urs Liska wrote:
Bei der Frage, ob ein Graph bipartit ist, scheitere ich an einer "falschen Antwort". Hier muss ich sagen, dass mir die Implikationen der Aufgabe noch etwas schwammit sind und mein Ansatz daher vielleicht zu naiv ist.
?
Ich suche per Breitensuche nach erreichbaren Knoten und färbe alle Nachbarn eines Knotens mit der "anderen" Farbe ein. Wenn ich auf einen Knoten stoße, der bereits entdeckt wurde, aber dieselbe Farbe wie ein aktueller Knoten hat, erkenne ich den Graphen als nicht bipartit.
Sieht korrekt aus, auch lesbar. Daher mein Fragezeichen da oben. Dem Code nach zu urteilen hast Du verstanden, worum es geht.
Bei allen angegebenen Beispiel-Eingaben funktioniert das auch, aber der Grader weist einen (mir unbekannten) Test-Fall ab.
Probier mal das:
5 5 1 2 3 4 4 5 5 3
Ist nicht bipartit. Dein Code wird aber (ich riskiere eine Blamage: ich habe es nicht getestet!) behaupten, es sei bipartit. Was fehlt noch?
Erstmal herzlichen Dank dafür - das ist genau das, was ich brauche (nicht fertige Lösungen). Aber Deine Eingabe passt irgendwie nicht. Nach den Vorgaben sagt dieser: 5 Knoten und 5 Verbindungen, es folgen aber nur vier Verbindungen. Wenn ich die fünf Knoten mit vier Verbindungen zeichne, kommt das heraus:
1-2 3---5 \ / 4
also ein Graph mit zwei nicht verbundenen Teilen. Ist es das, was du meinst?
Wenn solche geteilten Graphen als Eingabe erlaubt sind, dann scheitert mein Code daran, dass er beim ersten Knoten anfängt und daher nur einen Teilgraphen absucht. Das wäre möglich, aber normalerweise finden sich in den Instruktionen doch irgendwelche Hinweise auf solche zu beachtenden Details. Ich werde mal im Forum nachfragen und sehen, ob ein Mentor etwas dazu sagt.
Ah doch. Die "Constraints" sagen: 1 <= n <= 10^3 Knoten und 0 <= m <= 10^4 Verbindungen. Das heißt, Graphen mit Knoten und *keinen* Verbindungen sind erlaubt.
Knoten *ohne* Verbindungen sind bipartit, denn es geht nicht darum, dass "zweifarbige" Verbindungen da sein müssen, sondern darum, dass *vorhandene* Verbindungen zweifarbig sein müssen.
Der Bug müsste demnach sein, dass ich sicherstellen muss, dass alle Knoten besucht worden sind. Darüber hinaus könnte ich direkt abbrechen, wenn der Graph keine Verbindungen hat, was bei den Sonderfällen viel Zeit sparen kann.
Entweder blamiere ich mich jetzt, oder Du findest einen Bug :^)
Ich werde der Sache nachgehen ;-)
lg -- t _______________________________________________ > Freiburger Linux User Group > Mail an die Liste: flug@lug-freiburg.de Mailingliste verwalten (u.a. abbestellen):
https://lug-freiburg.de/mailman/listinfo/flug
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Mon, Jul 31, 2017 at 10:28:42AM +0200, Urs Liska wrote:
Am 31.07.2017 um 09:10 schrieb tomas@tuxteam.de:
On Sat, Jul 29, 2017 at 09:49:21AM +0200, Urs Liska wrote:
Bei der Frage, ob ein Graph bipartit ist, scheitere ich an einer "falschen Antwort". Hier muss ich sagen, dass mir die Implikationen der Aufgabe noch etwas schwammit sind und mein Ansatz daher vielleicht zu naiv ist.
?
Ich suche per Breitensuche nach erreichbaren Knoten und färbe alle Nachbarn eines Knotens mit der "anderen" Farbe ein. Wenn ich auf einen Knoten stoße, der bereits entdeckt wurde, aber dieselbe Farbe wie ein aktueller Knoten hat, erkenne ich den Graphen als nicht bipartit.
Sieht korrekt aus, auch lesbar. Daher mein Fragezeichen da oben. Dem Code nach zu urteilen hast Du verstanden, worum es geht.
Bei allen angegebenen Beispiel-Eingaben funktioniert das auch, aber der Grader weist einen (mir unbekannten) Test-Fall ab.
Probier mal das:
5 5 1 2 3 4 4 5 5 3
Ist nicht bipartit. Dein Code wird aber (ich riskiere eine Blamage: ich habe es nicht getestet!) behaupten, es sei bipartit. Was fehlt noch?
Erstmal herzlichen Dank dafür - das ist genau das, was ich brauche (nicht fertige Lösungen). Aber Deine Eingabe passt irgendwie nicht. Nach den Vorgaben sagt dieser: 5 Knoten und 5 Verbindungen, es folgen aber nur vier Verbindungen.
Öh -- ja. Ups. Pfui. Schlamperei.
Wenn ich die fünf Knoten mit vier Verbindungen zeichne, kommt das heraus:
1-2 3---5 \ / 4
also ein Graph mit zwei nicht verbundenen Teilen. Ist es das, was du meinst?
Genau.
Wenn solche geteilten Graphen als Eingabe erlaubt sind, dann scheitert mein Code daran, dass er beim ersten Knoten anfängt und daher nur einen Teilgraphen absucht.
Exakt. Der Graph muss nicht zusammenhängend ("connected") sein. Zumindest steht in der Aufgabenstellung nichts darüber.
Das wäre möglich, aber normalerweise finden sich inden Instruktionen doch irgendwelche Hinweise auf solche zu beachtenden Details. Ich werde mal im Forum nachfragen und sehen, ob ein Mentor etwas dazu sagt.
Hm. Das ist eine interessante Feststellung: jedes Gebiet hat so etwas wie "implizites Wissen", Dinge, "über die man nicht sprechen muss", und ein Teil der Mühen, sich das zu erarbeiten ist, dieses zu lernen.
Ist ein Graph immer zusammenhängend, es sei denn, man wird extra darauf hingewiesen? Wie ich die Graph-Fuzzis so kenne: nein.
Ah doch. Die "Constraints" sagen: 1 <= n <= 10^3 Knoten und 0 <= m <= 10^4 Verbindungen. Das heißt, Graphen mit Knoten und *keinen* Verbindungen sind erlaubt.
Das o.a. Beispiel hat aber auch noch Knoten & Verbindungen, ist nur "nicht zusammenhängend".
Knoten *ohne* Verbindungen sind bipartit, denn es geht nicht darum, dass "zweifarbige" Verbindungen da sein müssen, sondern darum, dass *vorhandene* Verbindungen zweifarbig sein müssen.
Der Bug müsste demnach sein, dass ich sicherstellen muss, dass alle Knoten besucht worden sind. Darüber hinaus könnte ich direkt abbrechen, wenn der Graph keine Verbindungen hat, was bei den Sonderfällen viel Zeit sparen kann.
Zum einen, ja. Aber auch:
1 -- 2 3 -- 4
ist bipartit. Dein Code würde auch "ja" sagen, aber in der Hälfte der Zeit, die er eigentlich dazu bräuchte :-)
Entweder blamiere ich mich jetzt, oder Du findest einen Bug :^)
Oder beides, s.o.
Ich werde der Sache nachgehen ;-)
Enjoy - -- t
Am 31.07.2017 um 10:58 schrieb tomas@tuxteam.de:
On Mon, Jul 31, 2017 at 10:28:42AM +0200, Urs Liska wrote:
Probier mal das:
5 5 1 2 3 4 4 5 5 3
Ist nicht bipartit. Dein Code wird aber (ich riskiere eine Blamage: ich habe es nicht getestet!) behaupten, es sei bipartit. Was fehlt noch?
Erstmal herzlichen Dank dafür - das ist genau das, was ich brauche (nicht fertige Lösungen). Aber Deine Eingabe passt irgendwie nicht. Nach den Vorgaben sagt dieser: 5 Knoten und 5 Verbindungen, es folgen aber nur vier Verbindungen.
Öh -- ja. Ups. Pfui. Schlamperei.
Wenn ich die fünf Knoten mit vier Verbindungen zeichne, kommt das
heraus:
1-2 3---5 \ / 4
also ein Graph mit zwei nicht verbundenen Teilen. Ist es das, was du
meinst?
Genau.
Na, dann war deine unvollständige Eingabe immerhin vollständig genug, um das Problem zu verdeutlichen.
Wenn solche geteilten Graphen als Eingabe erlaubt sind, dann scheitert mein Code daran, dass er beim ersten Knoten anfängt und daher nur einen Teilgraphen absucht.
Exakt. Der Graph muss nicht zusammenhängend ("connected") sein. Zumindest steht in der Aufgabenstellung nichts darüber.
Das wäre möglich, aber normalerweise finden sich inden Instruktionen doch irgendwelche Hinweise auf solche zu beachtenden Details. Ich werde mal im Forum nachfragen und sehen, ob ein Mentor etwas dazu sagt.
Hm. Das ist eine interessante Feststellung: jedes Gebiet hat so etwas wie "implizites Wissen", Dinge, "über die man nicht sprechen muss", und ein Teil der Mühen, sich das zu erarbeiten ist, dieses zu lernen.
Ist ein Graph immer zusammenhängend, es sei denn, man wird extra darauf hingewiesen? Wie ich die Graph-Fuzzis so kenne: nein.
Ja, das ist das Eine. Das Andere ist, wie man so etwas in einem Kurs handhabt. Das Konzept des bipartiten Graphen war vorher nicht in den Lektionen drangekommen, sondern in dieser Aufgabe zum ersten Mal beschrieben. Insofern ist die Erwartung, dass man selbst drauf kommt, relativ hoch gesteckt. Immerhin ist dieser (mein) Denkfehler sogar auf Wikipedia zu finden: https://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness beschreibt genau, was ich gemacht hatte. Ich denke, das könnte eine kleine Ergänzung vertragen ...
Ah doch. Die "Constraints" sagen: 1 <= n <= 10^3 Knoten und 0 <= m <= 10^4 Verbindungen. Das heißt, Graphen mit Knoten und *keinen* Verbindungen sind erlaubt.
Das o.a. Beispiel hat aber auch noch Knoten & Verbindungen, ist nur "nicht zusammenhängend".
Knoten *ohne* Verbindungen sind bipartit, denn es geht nicht darum, dass "zweifarbige" Verbindungen da sein müssen, sondern darum, dass *vorhandene* Verbindungen zweifarbig sein müssen.
Der Bug müsste demnach sein, dass ich sicherstellen muss, dass alle Knoten besucht worden sind. Darüber hinaus könnte ich direkt abbrechen, wenn der Graph keine Verbindungen hat, was bei den Sonderfällen viel Zeit sparen kann.
Zum einen, ja. Aber auch:
1 -- 2 3 -- 4
ist bipartit. Dein Code würde auch "ja" sagen, aber in der Hälfte der Zeit, die er eigentlich dazu bräuchte :-)
Entweder blamiere ich mich jetzt, oder Du findest einen Bug :^)
Oder beides, s.o.
Ich werde der Sache nachgehen ;-)
Enjoy
Das war's übrigens - jetzt wurde die Lösung akzeptiert. Also auf zu neuen Problemen ...
Herzlichen Dank nochmal Urs
-- t
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Mon, Jul 31, 2017 at 02:02:11PM +0200, Urs Liska wrote:
Am 31.07.2017 um 10:58 schrieb tomas@tuxteam.de:
[...]
Ist ein Graph immer zusammenhängend, es sei denn, man wird extra darauf hingewiesen? Wie ich die Graph-Fuzzis so kenne: nein.
Ja, das ist das Eine. Das Andere ist, wie man so etwas in einem Kurs handhabt. Das Konzept des bipartiten Graphen war vorher nicht in den Lektionen drangekommen, sondern in dieser Aufgabe zum ersten Mal beschrieben. Insofern ist die Erwartung, dass man selbst drauf kommt, relativ hoch gesteckt. Immerhin ist dieser (mein) Denkfehler sogar auf Wikipedia zu finden: https://en.wikipedia.org/wiki/Bipartite_graph#Testing_bipartiteness beschreibt genau, was ich gemacht hatte. Ich denke, das könnte eine kleine Ergänzung vertragen ...
In der Tat: die Seite ist auch ein wenig schizophren (ich habe sie nicht ganz durchgelesen, sondern nach "connected" durchsucht, und dann findet man durchaus die Einschätzung, dass ein Bipartite nicht unbedingt connected sein muss (und dass es dann mehrere mögliche Partitions gibt). Die Beschreibung des Algorithmus, die Du oben erwähnst tut dann so, als sei das Ding immer zusammenhängend.
[...]
Das war's übrigens - jetzt wurde die Lösung akzeptiert. Also auf zu neuen Problemen ...
\o/
Herzlichen Dank nochmal
Naja -- ich hatte auch meine Freude daran :-)
lg - -- t
-
Ralf Mattes -
Stefan Ziegler -
tomas＠tuxteam.de -
ul＠openlilylib.org -
Urs Liska