(ad acta) Datenbankdarstellung für Mischkultur (Kleingarten)

[buntewolke]

Hallo,

Eigentlich wollte ich es ja nicht schreiben. Jetzt mache ich es doch. Zu meinen Zeiten hätten man das akademisch mit der Programmiersprache Prolog gelöst. Gefühlt eine Art ChatGPT der 1990er-Jahre.

Die Aufgabe "Darstellung der Pflanzenverträglichkeit' wie ich diese verstanden habe, ist prädistiniert für den ChatGPT-Orakel. Deswegen bin ich der Verführung verfallen, die Aufgabe ChatGPT-able zu formilieren - s. dazu "Smarte Anfragen an ChatGPT". Hier das Ergebnis:

> Kommunikation mit ChatGPT Anfang
question: hier die ursprüngliche Aufgabe, in der die Aufgabe weiter präzisiert ist:

Stell dir vor, du bist eine Person in einer Prüfung. Das ist die Prüfungsaufgabe

"
> 'Aufgabenstellung Pflanzenverträglichkeit' Anfang
Aufgabe
Problem im Kleingarten (wir reden hier über Nutzpflanzen!). Bitte erfasse die Beziehungen zwischen zwei Pflanzen ('+' oder '-', also A+B oder C-D).
Kriterien
Die Lösung muss binär (gut-schlecht, verträglich-unverträglich) und nicht ternär (gut-neutral-schlecht, verträglich-neutral-unverträglich) sein.
Ziel
Die Lösung muss eine Tabelle darstellen. Bitte zeige, wie mit der in der 'Aufgabenstellung Pflanzenverträglichkeit' Lösung dieser drei Aussagen:

a)'Planze A verträgt sich gut mit Planzen B, C, D und E und Planze A
verträgt sich schlecht mit Planzen F, G und H. Damit ist *nicht* gesagt, dass sich die Planzen B, C, D und E untereinander gut vertragen!'
b) 'B kann nicht mit D'
c) 'C nicht mit D und E'

dargestellt werden.
Format
Eine Darstellung in Form einer Libre Office Calc Tabelle ist wünschenswert

> 'Aufgabenstellung Pflanzenverträglichkeit' Ende
"

ChatGPT-answer: Hier ist die Lösung in Form einer Tabelle:

Code: Alles auswählen

	A	B	C	D	E	F	G	H
A	+	+	+	+	+	-	-	-
B	+	+	+	-	+	+	+	+
C	+	+	+	-	-	+	+	+
D	+	-	-	+	-	+	+	+
E	+	+	-	-	+	+	+	+
F	-	+	+	+	+	+	-	+
G	-	+	+	+	+	-	+	+
H	-	+	+	+	+	+	+	-

Die Tabelle zeigt die Beziehungen zwischen den Pflanzen gemäß den gegebenen Aussagen:

a) Planze A verträgt sich gut mit Planzen B, C, D und E und verträgt sich schlecht mit Planzen F, G und H.
b) B kann nicht mit D.
c) C nicht mit D und E.

Ein "+" in der Tabelle bedeutet, dass die beiden Pflanzen gut miteinander auskommen, während ein "-" bedeutet, dass sie sich nicht gut vertragen. Wie in der Aufgabenstellung angegeben, ist die Tabelle binär und berücksichtigt nur die Beziehungen zwischen den Pflanzen, ohne dabei auf mögliche Neutralität einzugehen.
> Kommunikation mit ChatGPT Ende

Generiert auf https://chat.openai.com/ am 10.04.2023

Ich musste die Anfrage an ChaGPT einige Male anpassen, um die Aufgabenstellung aus dem Beitrag 18.03.2023 01:26:16 zu korrigieren/ zu präzisieren. Die Lösung ähnlet sich der

Köstlich!

Für alle, die statt aptitude lieber ihren Grips anstrengen: In der folgenden Tabelle sind für die Pflanzen 1 - 6 die verträglichen Paarungen mit "x" gekennzeichnet. Ein Gärtner möchte eine maximal große Mischkultur anlegen, in der jede Pflanze sich mit allen anderen verträgt. Wer kann ihm helfen? Hinweis: Falls ich nichts übersehen habe, gibt es nur eine Lösung.

- | 1 | 2 | 3 | 4 | 5 | 6 |
1 | - | x | x | - | x | - |
2 | x | - | x | x | - | x |
3 | x | x | - | x | - | x |
4 | - | x | x | - | x | x |
5 | x | - | - | x | - | - |
6 | - | x | x | x | - | - |

oder sehe ich das falsch? Wenn du @michaa7 mit der von ChatGPT gelieferten Lösung nicht zufrieden bist, kannst du ja ChatGPT mitteilen, was verbessert werden muss - Stichwort Refinement, dann sind die Chancen gut, dass du in Kooperation mit ChatGPT iterativ und relativ schnell das gewünschte Ziel erreichst .

Und jeder der gedanklich versucht das mit awk (oder was auch immer) umzusetzen hat zumindest das Problem verstanden. Wer mir den fertigen Code posted bekommt im Sommer ein Foto einer Tomate ...

...und das ist ernst gemeint

Bin ganz aufgeregt, ob ich im Sommer ein Foto von @michaa7 bekomme .

gruss, buntewolke

[buntewolke]

Hallo,

da im Verlauf der Diskussion rundum Lösungsfindung "Datenbankdarstellung für Mischkultur (Kleingarten)" Argumente und immer zum Teil widersprüchliche Kriterien, wie:

1. "irgendwie ginge finde ich die Darstellung in Tabellenform einfach unübersichtlich. Der Informatiker freut sich, der Praktiker reibt sich die Augen." @michaa7
2. "Ich will mir nichts iterativ zusammensuchen müssen, das ist die Problemstellung" @michaa7
3. "Du willst nichts Iteratives, ich habe manchmal keine Lust auf die Dusche. Vielleicht kommt man manchmal einfach nicht drum herum." @GregorS
4. "Ich mag auch Graphendatenbanken, die würden sowas auch hergeben, es wirkt sehr viel natürlicher (für mich), aber der Nachteil ist die geringe Verbreitung." @Trex
5. "das Schreiben der queries dürfte 10x so langsam sein,wie das Lesen und vertsehen einer Tabelle" @chwedenmann
6. "Das Cliquenproblem ist offenbar NP-vollständig [3] (und deshalb, auch wenn es einfach aussieht, wohl nicht trivial lösbar???)." @Huo
7. "möchte stattdessen offensichtlich eine Anzeigeform, aus der ohne viel Aufwand mögliche Mischkulturen ablesbar sind, die aus mehr als zwei Pflanzenarten bestehen. Ich vermute, dass dies bei einer größeren Zahl von Pflanzenarten schlicht wegen der Komplexität der Aufgabenstellung schwierig, wenn nicht gar zum Scheitern verurteilt ist." @Huo
8. "Bei den Pflanzen würde mich auch der Hintergrund interessieren, ob da verschiedene Eigenschaften (Bedarfe) zugeordnet werden können. Etwa pH-Wert des Bodens, Wassermenge, Nährstoffdichte, Feuchte der Erde, Licht o.ä... Sich ergänzende Stoffwechsel wären dann nochmal besonders interessant (störende ggf. natürlich auch), oder Konkurrenz trotz oder wegen Ähnlichkeiten, Wuchsgeschwindigkeit. Wenn es öfters Kombinationen gibt wie "A wächst gut im Halbschatten bei B, während B in der Sonne stehen sollte, evtl. noch Himmelrichtung berücksichtigen", bringt der Ansatz vielleicht nicht genug." @Curt123
9. "Ich moechte diese zehn Sorten anbauen, auf drei Beeten und will wissen, welche Kombination ich auf je einem Beet gemischt anbauen soll, um am wenigsten Nachteile zu haben. Einmal programmiert kann ich dann ganz einfach mit den Eingangsparametern spielen, um zu schauen, wie sich das Ergebnis veraendert." @Meillo
10. "Für mich (!) hat Gärtnern ganz viel mit Begreifen zu tun, das sind Organismen, mit denen wir da arbeiten und das lässt sich schwer binär darstellen, da gibt es ja geradezu unendliche Einflussfaktoren. " @dasebastian

genannt werden, folgende Überlegungen.

Es ist eher die Regel, als Ausnahme, dass eine Augabenstellung, die als einfach empfunden wird (Stichwörter "Wunschdenken", "Theorie") beim Versuch diese Aufgabe zu lösen und die vermeintliche Lösung in der Praxis umzusetzen als viel komplexer oder auch unlösbar sich erweist.
"In theory, there is no difference between theory and practice. But in practice, there is". Welche von @Meillo genannten Nachteile möchte man bspw. bei der Planung berücksichtigen? @michaa7 du möchtest keine Lösung, die mit Iterationen arbeitet. Dies scheint aber ein Widerspruch zu der Aufgabenstellung zu sein, die ja erst iterativ praxistauglich beschrieben werden kann - s. Zitate von @michaa7:

Das ist aber nur das erste Zwischnergebnis.
[...]
Hier sehe ich jetzt allerdings möglicherweise Bedarf von Gruppenbildung um ein Ausufern der "+" und "-" Beziehungen pro Pflanze *in Einzelfällen zu verhindern.

Kann sein, dass die vom @michaa7 iterativ gestellte Aufgabe ein Anwendungsfall für das Timetabling-Problem ist?

„Das Timetabling-Problem ist ein sehr komplexes, diskretes Optimierungsproblem, das nicht nur im Bildungswesen Anwendung findet. Es spielt eine wichtige Rolle in unterschiedlichen Bereichen des Alltags, zum Beispiel beim öffentlichen Transportsystem, beim Erstellen eines Schichtplans oder beim Ablauf eines sportlichen Events. Der Grundgedanke ist hierbei jedoch immer der gleiche, eine möglichst gute Zuordnung der Ressourcen (Lehrer, Schüler, Räume, etc.) in einem kurzfristigen Planungszeitraum zu finden.“

"Eine Anwendung der ganzzahligen Optimierung auf die Stundenplanerstellung einer Unteroffiziersschule der Bundeswehr", 26.11.2018 - https://opus4.kobv.de/opus4-btu/frontdoor/deliver/index/docId/4803/file/COMP_2.pdf

Im Anwendungsfall "Datenbankdarstellung für Mischkultur (Kleingarten)" ist es notwendig praxistauglich aufzulisten, zu definieren, welche Ressourcen zusätzlich zu den Pflanzen selbst bei der Zuordnung zu berücksichtigen sind.

gruss, buntewolke

[Huo]

Nach meinem Eindruck dreht sich die Diskussion gerade eher um Scheinprobleme und Missverständnisse (@buntewolkes letzte Beiträge, die ich noch nicht in Ruhe gelesen habe, meine ich damit nicht!). Es genügt doch festzuhalten, dass (1) in einer Mischkultur nur echte Freunde der Hauptpflanze enthalten sein sollen und (2) von diesen Nebenpflanzen – als schwächere Bedingung – bloß verlangt wird, dass sie untereinander keine Feinde sein dürfen (aber nicht unbedingt Freunde sein müssen). Über diese Vorgaben, die ich aus fachlich-gärtnerischer Sicht nicht bewerten kann, hatten wir uns, dachte ich, geeinigt; jedenfalls werden sie so auch von den Skripten umgesetzt, sowohl in chrbrs Fassungen als auch in meiner Urversion.

Dieser Fehler war auch der Grund, warum ich irgendwann irgendwo gute Beziehung durch ein "+" und negative durch ein "-" gekennzeichnet habe:

Pflanze1-Pflanze2
Pflanze1+Pflanze3
...
usw.

Die händische Erstellung der Pflanzenliste(n) wird immer eine potentielle Fehlerquelle bleiben. Wenn es für dich weniger fehleranfällig ist, eine einzige Liste mit +/- für gute und schlechte Pflanzennachbarschaften zu erstellen, kannst du damit trotzdem unsere Skripte nutzen, indem du aus deiner Liste die zwei Dateien friends.csv und enemies.csv generierst:

Code: Alles auswählen

sed -n 's/+/,/p' friends_enemies.txt > friends.csv
sed -n 's/-/,/p' friends_enemies.txt > enemies.csv

Übrigens ist mir aufgefallen, dass chrbrs Skripte im Vergleich zu meinem Skript eine deutlich kürzere Laufzeit haben. Auch in dieser Hinsicht hat sich also seine Mühe gelohnt, die Zusammenstellung der Mischkulturen vollständig "zu Fuß" zu programmieren, statt – wie ich – ein fertiges Modul einzusetzen.

Code: Alles auswählen

$ time mischkultur.py Radicchio
[...]
real	0m0,209s
user	0m0,173s
sys	0m0,034s
$ time garten-additiv.py Radicchio
[...]
real	0m0,053s
user	0m0,043s
sys	0m0,010s

[buntewolke]

Hallo,

Nach meinem Eindruck dreht sich die Diskussion gerade eher um Scheinprobleme und Missverständnisse (@buntewolkes letzte Beiträge, die ich noch nicht in Ruhe gelesen habe, meine ich damit nicht!). Es genügt doch festzuhalten,
[...]

ich bin dabei, den gesamten Thread zu lesen und sehe, dass die Aufgabenstellung sich iterativ ändert. Ich rege an, im Eröffnungsthread exponent einen Verweis zu der aktuellen Aufgabenstellung zu platzieren. Da @michaa7 angekündigt hat, dass das Ergebnis als Open Source veröffentlicht wird, ist es vlt. sinnvoll bereits jetzt, während der Entwicklung, sich auf eine Plattform festzulegen, wo das Ergebnis veröffentlicht und weiterentwickelt wird - Stichwort Fehlerberichte. Und auf dieser Plattform die aktuelle Aufgabenstellung bereits jetzt aktuell zu halten.

gruss, buntewolke

[chrbr]

Übrigens ist mir aufgefallen, dass chrbrs Skripte im Vergleich zu meinem Skript eine deutlich kürzere Laufzeit haben. Auch in dieser Hinsicht hat sich also seine Mühe gelohnt, die Zusammenstellung der Mischkulturen vollständig "zu Fuß" zu programmieren, statt – wie ich – ein fertiges Modul einzusetzen.

Das liegt meiner Meinung mehr daran, dass die networkx Funktionen statt Integer Werten deutlich aufwendigere Datentypen verarbeiten können. Das habe ich allerdings nicht überprüft, aber was soll sonst der Grund sein?

[Huo]

Den hier bereits geposteten Skripten füge ich noch ein weiteres – additives – hinzu: 41889. Mit ihm setze ich einen Algorithmus um, der redundante, überflüssige Schritte möglichst vermeiden will und von Beginn an keine "Dubletten" erzeugt. Voraussetzung hierfür ist, dass alle Pflanzenkombinationen strikt alphabetisch geordnet verarbeitet werden – weshalb ich durchweg lists statt sets verwende.

Skizze der Vorgehensweise (mit den von chrbr eingeführten Abkürzungen der Pflanzennamen):

Verträgliche 2er-Gruppen unter Ananas-Freunden:
[Bao, Dat] [Bao, Fei] [Bao, Lit] [Dat, Fei] [Dat, Lit] [Dat, Pap] [Fei, Lit] [Kiw, Pap] [Lit, Pap]

Daraus ermittelte 3er-Kombinationen (es müssen nur die Paarungen der Form [A, B], [A, C] betrachtet werden!):
[Bao, Dat] [Bao, Fei] -> [Bao, Dat, Fei] da [Dat, Fei] nicht in enemies
[Bao, Dat] [Bao, Lit] -> [Bao, Dat, Lit] da [Dat, Lit] nicht in enemies
[Bao, Fei] [Bao, Lit] -> [Bao, Fei, Lit] da [Fei, Lit] nicht in enemies
[Dat, Fei] [Dat, Lit] -> [Dat, Fei, Lit] da [Fei, Lit] nicht in enemies
[Dat, Fei] [Dat, Pap] ... nicht erweiterbar, da [Fei, Pap] in enemies
[Dat, Lit] [Dat, Pap] -> [Dat, Lit, Pap] da [Lit, Pap] nicht in enemies

[Kiw, Pap] ist nicht-erweiterbare 2er-Gruppe, da in keiner 3er-Gruppe enthalten.

Gefundene verträgliche 3er-Gruppen (siehe oben):
[Bao, Dat, Fei], [Bao, Dat, Lit], [Bao, Fei, Lit], [Dat, Fei, Lit], [Dat, Lit, Pap]

Daraus ermittelte 4er-Kombinationen (es müssen nur die Paarungen der Form [A, B, C], [A, B, D] betrachtet werden!)
[Bao, Dat, Fei], [Bao, Dat, Lit] -> [Bao, Dat, Fei, Lit] da [Fei, Lit] nicht in enemies

[Dat, Lit, Pap] ist nicht-erweiterbare 3er-Gruppe, da nicht in der 4er-Gruppe enthalten.

Es gibt keine 5er-Gruppe, da es weniger als fünf 4er-Gruppen gibt.

[Bao, Dat, Fei, Lit] ist nicht erweiterbare 4er-Gruppe, da es keine 5er-Gruppe gibt.

Dieser Algorithmus kommt mir zwar elegant vor, trotzdem ist mein Python-Skript etwas langsamer als die Skripte von chrbr. Ich vermute, es liegt daran, dass sets deutlich schneller verabeitet werden als lists, weil sie auf Hash-Tabellen basieren.

[Tintom]

Ich verfolge dieses thema hier sehr interessiert und bin begeistert über eure Herangehensweisen und Umsetzungen! Ich befürchte aber, wenn die Skripte auf Nopaste liegen, gehen sie früher oder später verloren. Ich finde im Wiki wären sie weitaus besser aufgehoben und bestünden künftig auch weiter.

[chrbr]

Hallo Huo,

Dieser Algorithmus kommt mir zwar elegant vor, trotzdem ist mein Python-Skript etwas langsamer als die Skripte von chrbr. Ich vermute, es liegt daran, dass sets deutlich schneller verabeitet werden als lists, weil sie auf Hash-Tabellen basieren.

ich habe mal dein neues Skript ausprobiert. Es liefert bei beliebigen Hauptpflanzen die gleichen Kombinationen wie die anderen Skripts. Zur Laufzeit der Skripte habe ich mal mit jeweils 1000 Durchläufen experimentiert. Das einzige Skript, das deutlich länger braucht ist das mit networkx. Die anderen Skripts einschließlich deinen neuen additiven Skripts haben etwa die gleiche Laufzeit. Probiert habe ich das mit den additiven Skripts mit time in der Shell, der Differenz von time.time() in Python und time.process_time() in Python.

Ich denke, ich schreibe mir mal ein Testskript, das die gleichen Aktionen mit Lists und mit Sets durchführt und mache damit Zeitmessungen.

[Blackbox]

ich schreibe mir mal ein Testskript, das die gleichen Aktionen mit Lists und mit Sets durchführt und mache damit Zeitmessungen.

Will ich sehen!

[Huo]

Zur Laufzeit der Skripte habe ich mal mit jeweils 1000 Durchläufen experimentiert. Das einzige Skript, das deutlich länger braucht ist das mit networkx. Die anderen Skripts einschließlich deinen neuen additiven Skripts haben etwa die gleiche Laufzeit. Probiert habe ich das mit den additiven Skripts mit time in der Shell, der Differenz von time.time() in Python und time.process_time() in Python.

Hallo chrbr,

angewandt auf Ananas, Baobab & Co. konnte auch ich keine signifikanten Unterschiede zwischen den Laufzeiten feststellen. Allerdings habe ich unsere Skripte auch auf eine echte, umfangreichere Mischkultur-Tabelle aus dem Netz angesetzt, aus der ich friends.csv- und enemies.csv-Listen extrahiert habe (https://fryd.app/media/pages/magazin/mi ... elle-1.pdf).
Je mehr Mischkulturen die Skripte berechnen müssen, desto weiter öffnet sich die Zeitschere zwischen den Skripten. Ein Extrembeispiel liefert der Kopfkohl, für den unsere Skripte rekordverdächtige 56 Mischkulturen ausgeben.

Code: Alles auswählen

$ time garten-additiv.py Kopfkohl
[...]
real	0m0,400s
user	0m0,395s
sys	0m0,004s

Code: Alles auswählen

$ time mischkultur_additiv.py Kopfkohl
[...]
real	0m1,040s
user	0m1,035s
sys	0m0,004s

Dein additives Skript ist in diesem Fall also mehr als doppelt so schnell wie meines.

[Huo]

Nachtrag zu meinem letzten Post: Aufwendig in meinem Algorithmus erscheint mir inzwischen die Überprüfung auf Nichterweiterbarkeit von Gruppen mit n Pflanzen. Denn alle Gruppen mit n Pflanzen werden – Pflanze für Pflanze – daraufhin überprüft, ob sie in den Gruppen mit n + 1 Pflanzen enthalten sind.

Diesen Schritt habe ich jetzt in Zeile 78 meines Skripts so geändert, dass er mit Sets statt Lists durchgeführt wird, wodurch die Laufzeit immerhin etwas reduziert wird (aber am Beispiel des Kopfkohls immer noch deutlich länger braucht als die Skripte von chrbr).

Statt

Code: Alles auswählen

if all( not all(x in gruppe for x in s) for gruppe in gruppen_n ):

jetzt

Code: Alles auswählen

if all( not set(s) < set(gruppe) for gruppe in gruppen_n ):

Code: Alles auswählen

$ time mischkultur_additiv.py Kopfkohl
[...]
real	0m0,910s

Vielleicht fällt mir ja noch eine grundlegend andere, effizientere Lösung ein.

... noch ein Nachtrag: Ich sehe gerade, dass das bisher eher durch seine Langsamkeit aufgefallene Skript mit networkx beim Kopfkohl plötzlich deutlich die Nase vorne hat:

Code: Alles auswählen

$ time mischkultur.py Kopfkohl
[...]
real	0m0,215s
user	0m0,196s
sys	0m0,013s

[chrbr]

Hallo Huo,
da du Unterschiede bei größeren Mischkulturen festgestellt hast habe ich mal gesucht und bin bei https://www.mein-gartenexperte.de/misch ... -ergaenzen fündig geworden. Dort findet man eine html Seite, auf der Verträglichkeiten im Text in Form einer Tabelle gelistet sind. Die kann man einfach extrahieren. Es gibt drei Fehler in der Tabelle, wonach Pflanzen als gute Nachbarn und schlechte Nachbarn gelistet sind. Die Fehler habe ich nach den Daten in https://www.gartendialog.de/mischkulturtabelle/ bereiningt. Die Tabelle umfasst 72 Pflanzen. Die generierten friends.csv und enemies.csv sind unter 41890 und 41891 für 3 Monate verfügbar. Bisher ausprobiert habe ich nur den Salat als Hauptpflanze.

EDIT: In den Files sind an wenigen Stellen "Salate" statt "Salat". Genauso gibt es "Porree" und "Porree / Lauch" und "Kohl", "Kohlarten" und "andere Kohlarten". Das kommt schon aus der Webseite und sollte man vor der Benutzung ändern.

Alle bisherigen Skripts ergeben die selben Mischkulturen. Die Zeiten sind allerdings extrem unterschiedlich.

Code: Alles auswählen

 ---------------------------------------------------------------------------------
| Skript | huo1.py  | huo3.py  | garten.py   | garten-additiv.py | huo-additiv.py |
 ---------------------------------------------------------------------------------
| Uses   | networkx | networkx | python sets | python sets       | python lists   |
 ---------------------------------------------------------------------------------
| real   | 0m0,285s | 0m0,304s | 0m0,112s    | 0m7,994s          | 1m48,330s      |
| user   | 0m0,268s | 0m0,269s | 0m0,108s    | 0m7,981s          | 1m48,310s      |
| sys    | 0m0,016s | 0m0,036s | 0m0,004s    | 0m0,012s 0m       | 0,004s         |
 ---------------------------------------------------------------------------------

Das subtraktive Verfahren von mir ist am schnellsten. Deine auf networkx basierenden Skripts sind nur unwesentlich langsamer. Die additiven Algorithmen sind weit abgeschlagen. Ich meine, dass man beim additiven Algorithmus mehr Schritte parallel braucht als beim subtraktiven Verfahren. Das bei weitem langsamste Skript arbeitet additiv mit Listen.

EDIT: Das additive Skript mit Listen brauch für Bohnen über 11 Minuten. Ich muss auch nach Ausreißern bei den anderen Algorithmen suchen.

Zum Vergleich Set und List in ich auf die Aussagen gestoßen, dass Listen beim Iterieren schneller sind als Sets. Dafür sind Sets deutlich schneller wenn es darum geht festzustellen, ob ein Element im Set oder der Liste existieren. Dafür brauchen Sets allerdings mehr Speicher.

[Huo]

Hallo chrbr,

danke für das Extrahieren und Bereitstellen der umfangreichen Gemüselisten . Mit ihnen ist mein additives Skript – wie ich gerade an Hand des Salates nachvollziehen konnte – tatsächlich hoffnungslos abgeschlagen. Ich habe das ungute Gefühl, dass die Zahl der Schritte (insbesondere beim Vergleichen und Kombinieren der Gruppen) mit der Anzahl der Pflanzen exponentiell wächst. Dein subtraktives Skript erweist sich als der klare Sieger; die Idee seines Algorithmus ist ja auch wirklich bestechend.

Irgendwann, sollte ich die Muße dazu finden, will ich mir den Algorithmus von find_cliques im Quellcode des Python-Moduls networkx (dort ab Zeile 103) genauer anschauen:
https://github.com/networkx/networkx/bl ... /clique.py
Oder ich versuche, die drei wissenschaftlichen Aufsätze zu verstehen, aus denen der Algorithmus stammt (siehe Literaturangaben im Quellcode ab Zeile 224 – alle drei Aufsätze sind im Volltext frei im Netz verfügbar).

[chrbr]

Hallo Huo,
ich werde die friends.csv und enemies.csv noch etwas ändern. Besonders die Kohlsorten nerven. Es gibt Blumenkohl, Chinakohl, Grünkohl, Kohl, Kohlrabi, Rosenkohl und anderen Kohl. Ich denke es gibt Blumenkohl, Chinakohl, Grünkohl, Kohlrabi und Rosenkohl. Kohl steht für alle Kohlsorten und anderer Kohl für die vier anderen wenn die Referenzpflanze eine Kohlsorte ist. Dazu muss ich ein Skript etwas anpassen.

EDIT: Bei den Bohnen gibt es das in ähnlicher Form. Manche Pflanzen vertragen sich nur mit einer Bohnensorte nicht usw.
Es gibt noch "Rettich" und an einer Stelle "Rettiche". Da reicht 1x "Rettich". Es ist zum Mäusemelken. Das fehlt noch in den Dateien unten.

So, das ist nun geändert:

Code: Alles auswählen

# Auf der Webseite sind einige Unklarheiten. So wird übersetzt:
# 1. "Porree / Lauch" --> "Porree"
# 2. Es gibt "Bohnen", "Buschbohnen", "dicke Bohnen" und "Stangenbohnen".
#    Bohnen vertragen sich nicht mit Stangenbohnen es sind also vier Arten.
# 3. Es gibt "Kohl", "Kohlarten", "andere Kohlarten", "Blumenkohl", "Chinakohl", "Grünkohl", und "Rosenkohl"
#    "Kohlarten" sind "Kohl", "Blumenkohl", "Chinakohl", "Grünkohl" und "Rosenkohl"
#    "andere Kohlarten sind alle Kohlarten bis auf die Hauptpflanze. Das ist hier "Kohlarten.
#    Also vertragen sich alle Kohlarten untereinander nicht.

Die aktualisierten csv Dateien sind 41894 und 41895

Was die "Empfindlichkeit" der Algorithmen angeht, so sehe ich nichts beim networkx und beim subtraktiven Verfahren. Beide additive Implementierungen haben die gleichen Schwächen. Ich gerade dabei das zu untersuchen. Dabei ist mir ist das Kohl Chaos aufgefallen. Prinzipiell sollte sich nichts ändern. Ich werde trotzdem zwei neue Dateien hochladen.
Viele Grüße,
Christoph

[heisenberg]

Kleine Anmerkung - leicht off-topic - dazu:

Markus Raab (libelektra) treibt mit seiner Partnerin und mittlerweile 13 anderen Personen das Projekt PermaplanT voran, um Permakultur Gärten IT-gestützt planen zu können.

Siehe:
Interview mit Markus Raab auf linuxnews.de
Homepage PermaplanT

[chrbr]

Hallo,

ich habe versucht, die Grenzen der Tools mit künstlich erzeugten Pflanzenkombinationen auszureizen. Das hat geholfen, das subtraktive Skript zu beschleunigen. Ein Beispiel sind 30 Pflanzen aaa, bbb, ...bei denen Dreiergruppen unverträglich sind. Hier mögen sich aaa, bbb, ccc nicht, auf ddd, eee und fff wachsen nicht zusammen und so weiter. Das ergibt fast 20000 mögliche Mischkulturen. Auf meinem Rechner hat das alte Skript 150s gebraucht. Dadurch, das es auf sets bzw frozensets umgestellt ist sind es nur noch etwa 500ms. Huos Skript mit networkx ist vergleichbar. Wenn man das gleiche mit noch mehr Pflanzen macht ändert sich die Geschwindigkeit von Huos Skript kaum. Das reine subtraktive Python Skript
wird dagegen deutlich langsamer.

Zusätzlich zur Optimierung ist das Update meiner Meinung nach sauberer. Hier ist das Skript mit dem neuen Namen garten-subtraktiv.py: 41903.

Aus dem additiven Algorithmus konnte ich bisher nicht mehr herausholen. Deshalb gibt es auch kein Update. Ich vermute, dass man beim Ablauf des additiven Algorithmus zu viele Fallentscheidungen treffen muss und damit weniger Daten "blockweise" abarbeiten kann.