Elemente einer Äquivalenzklasse bzgl einer Ordnung vereinen?

[0x7F800000]

Hey Leute!

Folgendes Problem:
-ich habe eine Collection mit irgendwelchen (teilweise "gleichartigen" d.h. x.equals(y)==true) Elementen
-Es gibt eine Operation die zwei elemente dieser Collection zu einem kombinieren (Summation)
-Es gibt eine Ordnung (durch Comparator gegeben)

Frage: wie bekomme ich eine sortierte Menge von zu jeweils einem element kombinierten Äquivalenzklassen?

Anschaulich: ich will sowas wie "2ab+7c+8ab" schnell zu "10ab+7c" zusammenrechnen können.

Meine bisherigen Ideen:
1) Alle elemente zu sortieren, und dann nochmal über die liste drübergehen, und dann nacheinanderfolgende gleichwertige elemente aufaddieren. Wäre ein aufwand von O(n log(n) + n) wobei mich das "+n" sehr nervt, weil's eigentlich umsonst ist, und der vergleich auch nicht grade atomar & primitiv ist.

2) TreeSet irgendwie so umfunktionieren, dass er mir zumindest mal die äquivalenzklassen rausspuckt.
Problem: das ist ein Set, der wird doppelt vorkommende Elemente aussortieren

3) Irgendsowas Tree-Set ähnliches schreiben, das für dieses Kombinieren zuständig ist. Sollte schneller als in O(nlog(n)) laufen, allerdings habe ich grad wenig Lust so ein Tree-Set zu implementieren.

Falls jemand bessere Vorschläge hat, bitte melden.
Da ich nicht daran glaube, dass jemals etwas passiert, was konkret mir alleine das Leben einfacher macht, fange ich schonmal mit der 3. Variante an :autsch: ^^

greetz, Andrey

 

[SlaterB]

O(n log(n) + n) ist doch von der Performance her O(n log(n))
das kleinere +n spielt keine Rolle

----

die Äquivalenzklassen in einer Hashmap sammeln
Klasse -> Summe

wenn die Klassen einen Hashcode/ Nummer 0-n haben, dann gar ein Array,
mit Aufwand O(n) hast du alle zusammengefasst,

das Sortieren ist danach vielleicht einfach, wenn wiederum 0-n gegeben ist,
sonst normal sortieren,

 

[0x7F800000]

O(n log(n) + n) ist doch von der Performance her O(n log(n))
das kleinere +n spielt keine Rolle

es spielt schon eine rolle. Es heißt ja auch "asymptotische" Laufzeit. Wenn ich hier Polynome in 50000 Variablen mit zehn millionen Termen hätte, wäre das "+n" wohl nicht messbar. Aber wenn ich hier sehr oft mit sehr kleinen Polynomen in drei variablen rechne, dann macht dieser sinnfreie +n vorgang evtl. schonmal die Hälfte der Zeit aus.

die Äquivalenzklassen in einer Hashmap sammeln
Klasse -> Summe

wie das? ich müsste dann doch irgendwie jeder "x²y³z²wvu³..."-Kombination irgendeinen eindeutigen Hashcode zuordnen? Und wie soll ich dann die einzelnen Buckets darausholen, die API stellt sowas nicht bereit. ???:L Oder meinst du irgendeine eigenbau-Hashmap?

wenn die Klassen einen Hashcode/ Nummer 0-n haben, dann gar ein Array,
mit Aufwand O(n) hast du alle zusammengefasst

öööhm... irgendwie sind solche Monome schon abzählbar. Aber bezüglich einer beliebigen Monomordnung eine explizite Bijektion von so einem schräg geordneten mehrdimensionalen Gitter zu [0...N] anzugeben ist imho Folterselbstmord. Also, theoretisch ist das natürlich alles "einfach gegeben", aber das ist in einem Programm nicht sinnvoll umzusetzen, ich hätte da nicht mal einen Ansatz. Und wenn ich da ganz schüchtern und bescheiden zehn Variablen nehme, mit dreistelligen Potenzen, dann reicht Long schon nicht mehr aus, um alle "kleinen" kombinationen abzuzählen.

Aber danke für den Vorschlag. :toll:

Hab das jetzt temporär wie folgt gelöst:

	public static <T extends FieldElement<T>> List<Term<T>> recombineTerms(Collection<Term<T>> terms,final Comparator<Term> order){
		
		class RecombinationTree{
			Term<T> term;
			RecombinationTree smaller,bigger;
			
			RecombinationTree(Term<T> t){
				term=t;
				smaller=null;
				bigger=null;
			}
			
			void add(Term<T> t){
				int relation=order.compare(term,t);
				if(relation<0){
					if(smaller==null)	smaller=new RecombinationTree(t);	else	smaller.add(t);
				}else if(relation>0){
					if(bigger==null) bigger=new RecombinationTree(t);	else	bigger.add(t);
				}else{
					term=term.add(t);
				}
			}
			
			List<Term<T>> toList(){
				List<Term<T>> result=new LinkedList<Term<T>>();
				toListRec(result);
				return result;
			}
			
			void toListRec(List<Term<T>> list){
				if(smaller!=null) smaller.toListRec(list);
				list.add(term);
				if(bigger!=null) bigger.toListRec(list);
			}
		}
		
		Iterator<Term<T>> i=terms.iterator();
		if(i.hasNext()){
			RecombinationTree tree=new RecombinationTree(i.next());
			for(;i.hasNext();){
				tree.add(i.next());
			}
			return tree.toList();
		}else{
			return new LinkedList<Term<T>>();
		}
	}

Also, in der "rekombinierungsmethode" habe ich mir da einfach einen eigenen auf meine Bedürfnisse zugeschnittenen binären "rekombinierungsBaum" erstellt, der das alles in O(n log(n)) bzw worst case O(n²) [im entarteten fall] sortiert und zusammenaddiert und als liste ausgibt. Worst case ist halb so wild, ich werde bei der multiplikation der polynome darauf achten, dass alles möglichst bunt gemischt wird. Zur addition werde ich das in O(n) per "reißverschlussverfahren" in O(n) zusammenaddieren, deswegen passt's schon, denke ich mal.

Ist solche Verwendung von zugeschnittenen lokalen Klassen überhaupt zulässig, oder schieß ich mir da grad selbst in den Fuß? :?: das sollte doch performancemäßig nicht viel ausmachen, oder? (zumindest nicht so viel wie der hohe Generics-overhead)

Optimieren kann ich eh später, will's erstmal allgemein zum Laufen bringen.
Ich hab schon einen sehr guten Grund, bereits die wenigen bisher erstellten 12 Klassen zu 7 zusammenzufassen, habe mir da irgendwie massig unnötige Factory-Klassen erstellt :autsch: imho ein blöder Design-fehler, eigentlich ist das jetzt schon alles zum wegwerfen :? . Aber nachher ist man immer schlauer, deswegen mach ich's ja

 

[0x7F800000]

Q(long)[X,Y,Z]DEGREVLEX
Y^7Z^3+X^4Y^3+3/7X^2Y^4Z+2/3Y^4Z^3+X^2Y^2+XYZ^2+Y^2Z^2+XZ^3+8YZ^3

Uiiii, der scheiß läuft sogar^^ Noch nicht viel, aber immerhin, ich kann die Dinger schon hinschreiben
So, jetzt kann ich aber beruhigt pennen gehen.

Weitere vorschläge bzgl des oben geposteten Problems sind stets willkommen, vielleicht fällt einem ja doch noch was ein.

greetz, Andrey

 

[SlaterB]

Aber wenn ich hier sehr oft mit sehr kleinen Polynomen in drei variablen rechne, dann macht dieser sinnfreie +n vorgang evtl. schonmal die Hälfte der Zeit aus.

umso besser, dann hast du in diesem Fall doch nur O(2n) = O(n)

wie das? ich müsste dann doch irgendwie jeder "x²y³z²wvu³..."-Kombination irgendeinen eindeutigen Hashcode zuordnen?

wie liegen denn diese Kombinationen vor, wie stellst du ihre Ähnlichkeit fest beim Vergleich zweier Elemente?
wenns z.B. Strings sind, dann gibts doch schon Hashcode

Und wenn ich da ganz schüchtern und bescheiden zehn Variablen nehme, mit dreistelligen Potenzen, dann reicht Long schon nicht mehr aus, um alle "kleinen" kombinationen abzuzählen.

eben war noch von sehr kleinen Polynomen die Rede, nun gehts du in's Unendliche, du musst dich schon entscheiden

wenn die Möglichkeiten des Zusammenfassens gering, die Anzahl der Äquivalenzklassen eh praktisch gleich n ist,
dann wird das Sortieren die Hauptaufgabe, dann dürfte es nichts schnelleres als O(n log(n)) geben

außer
http://de.wikipedia.org/wiki/Bucketsort
welches eher meinen Vorstellungen entspricht

aber der RecombinationTree scheint den zweiten Durchlauf unnötig zu machen, denke ich

 

[0x7F800000]

umso besser, dann hast du in diesem Fall doch nur O(2n) = O(n)

wie gesagt, ich will weder dass es asymtotisch lahm wird, noch dass sich bei kleinen Termen der unnötige overhead zu stark auswirkt.

wie das? ich müsste dann doch irgendwie jeder "x²y³z²wvu³..."-Kombination irgendeinen eindeutigen Hashcode zuordnen?

wie liegen denn diese Kombinationen vor, wie stellst du ihre Ähnlichkeit fest beim Vergleich zweier Elemente?
wenns z.B. Strings sind, dann gibts doch schon Hashcode

als integer arrays liegt das vor. x²y³z entspricht zB. einem tupel [2,3,1] bzw [0,0,...,0,2,3,1] je nach dem, ob da noch weitere variablen vorhanden sind, die mit der potenz 0 vorkommen.

Ich glaub aber ich weiß jetzt was du meintest. In einer HashMap einfach die Tupeln gegen die Koeffizienten mappen, und dann alle terme durchgehen, in der map nachschlagen, ob die entsprechende variablenkombination da drin schon vorkommt, und evtl den Koeffizienten draufaddieren, bzw. als neuen eintrag hinzufügen. Jo, hört sich eigentlich gar nicht schlecht an. Alles in die HashMap zu werfen würde mich im schnitt etwa O(n) kosten (auch wenn mit großen overhead). Aber ich müsste es anschließend trotzdem nochmal sortieren, nachdem ich alles zusammengefasst hab.

Und wenn ich da ganz schüchtern und bescheiden zehn Variablen nehme, mit dreistelligen Potenzen, dann reicht Long schon nicht mehr aus, um alle "kleinen" kombinationen abzuzählen.

eben war noch von sehr kleinen Polynomen die Rede, nun gehts du in's Unendliche, du musst dich schon entscheiden

Das Beispiel war schüchtern und bescheiden.
10 Variablen, 3Stellige potenzen => "klein"
1000 Variablen, 20Stellige potenzen => "groß"

außer
http://de.wikipedia.org/wiki/Bucketsort
welches eher meinen Vorstellungen entspricht

Zu speicherintensiv, nicht umsetzbar.

aber der RecombinationTree scheint den zweiten Durchlauf unnötig zu machen, denke ich

"zweiter durchlauf" ist was? Da tropfen einfach von oben die terme rein, werden entweder weitergereicht oder zusammengefasst. Am ende wird's als sortierte Liste ausgegeben.

Also, danke für die Anregung mit der HashMap schon mal, ich denk nochmal drüber nach. :toll:

 

[SlaterB]

> Aber ich müsste es anschließend trotzdem nochmal sortieren, nachdem ich alles zusammengefasst hab.

dass du die Äquivalenzklassen sortieren musst steht außer Frage, deshalb dominiert ja n log(n)

die Frage ist nur, wie man noch möglichst schmerzfrei die andere Aufgabe des Zusammenfassens ausführen kann und ob das vorher oder nachher passiert
mit dem RecombinationTree sortierst du alle n Elemente per n log(n) und fügst sie quasi danach (nach dem Sortieraufwand) nahezu kostenlos zusammen, zumindest ohne zusätzliche Vergleiche

mit der HashMap könntest du das Zusammführen mit Aufwand n durchführen, und hast danach normalen Sortieraufwand für die geringere Zahl x der übrigbleibdenden Äquivalenzklassen,
das lohnt sich immer mehr, je größer der Unterschied zwischen x und n ist

> zweiter durchlauf" ist was?

das +n aus n log(n) +n vom ersten Posting

 

[0x7F800000]

mit dem RecombinationTree sortierst du alle n Elemente per n log(n) und fügst sie quasi danach (nach dem Sortieraufwand) nahezu kostenlos zusammen, zumindest ohne zusätzliche Vergleiche

mit der HashMap könntest du das Zusammführen mit Aufwand n durchführen, und hast danach normalen Sortieraufwand für die geringere Zahl x der übrigbleibdenden Äquivalenzklassen,
das lohnt sich immer mehr, je größer der Unterschied zwischen x und n ist

Aaah ja, ich verstehe vorauf du hinaus willst. Eine sehr schöne überlegung, allerdings hast du nicht beachtet, dass ich beim RecombinationTree ja nicht alle n Terme sortiere: manche "versickern" ja unterwegs in bereits vorhandenen Knoten, ohne neue Leafs zu bilden. Aber schöne Überlegung, so hab ich das gar nicht betrachtet :toll:

Mir ist unterwegs übrigens aufgefallen, dass ich auch beim multiplizieren noch die ordnung beibehalten kann, wenn ich das nicht geradezu absichtlich durcheinandermische (was ich anfangs vorhatte: ist zwar etwas langsamer, dafür aber gemütlicher... ja,, bin halt faul :roll: )

Ich werde jetzt versuchen, alle rechenoperationen vorsichtig so umzuschreiben, dass nirgends ordnung verlorengeht.
Dann brauche ich am ende den "recombinationTree" ja nur noch beim Parsen.
Dann muss ja nur das was der unaufmerksame mensch falschrum eingetippt hat neusortiert werden. Alle anderen zwischenergebnisse werden ja aus Operationen auf bereits sortierten polynomen hervorgehen, wenn das an keiner stelle kaputtgeht, dann wird die einmal gewonnene ordnung mit einem geringen aufwand immer weitervererbt. Das ist wesentlich besser als die idee die ich gestern noch hatte.

ne, so ein forum ist vor allem cool zum lauten Nachdenken

 

[0x7F800000]

Notiz: bei der multiplikation von geordneten polynomen bleibt eigentlich recht viel ordnung erhalten. Wenn man das vorsichtig stück für stück abknabbert, dann braucht man im worst case ein einziges mal an einer einzigen stelle ein element in eine bereits sortierte liste mit (n-1) termen einfügen, statt n*m Terme in irgendwelche Rekombinierungsbäume einzusortieren. (n soll die anzahl der Terme des Kürzeren Polynoms sein)

Aber das ist imho ein wenig trickreich, da muss man schon gut aufpassen. Ich mach's mal später irgendwann, wenn ich mehr zeit hab...

 

[Marco13]

Der Thread lungerte noch so latent in meinem Hinterkopf rum, bin aber nicht sicher, ob ich da alles richtig verstanden habe. Ich gehe davon aus, dass du in irgendeiner Form sowas hast wie eine Klasse

class Monom
{
    float factor;
    String powers;
}

Und ein Polynom (d.h. eine Folge solche Monome) sollte sortiert und "optimiert" werden. Das müßte doch mit einer TreeMap gemacht werden können? Ich würde da jetzt im Pseudocode so rangehen:

Collection<Monom> optimize(Collection<Monom> polynom)
{
    Map<String, Monom> map = new TreeMap<String, Monom>(new PowersStringComparator());
    for (Monom monom : polynom)
    {
        Monom resultMonom = map.get(monom.powers);
        if (resultMonom == null)
        {
            resultMonom = new Monom();
            resultMonom.powers = monom.powers;
            map.put(monom.powers, resultMonom);
        }
        resultMonom.factor += monom.factor;
    }
    return map.values();
}

Das müßte das ganze dann doch in O(n log n) erledigen? ???:L Aber wahrscheinlich hab ich da nur wieder irgendwas falsch verstanden oder nicht berücksichtigt...

 

[0x7F800000]

Ne, doch, alles eigentlich richtig. Nur du suchst und fügst wieder ein. Einmal get einmal put. Da gehst du denselben weg zweimal. Das könnte man umgehen, indem man die Monome mutabel macht, sodass sie direkt durch .add und .multiply usw. verändert werden können, statt ein neues Monom auszugeben. Aber das wäre für mich ungewohnt, und gegen die BigInteger-konvention.

Und Strings verwende ich natürlich nicht für zwischenrechnungen, alle Potenzen werden in int[] gespeichert.
Es läuft auch schon irgendwie. Wen es interessiert, kann mal hier einen Blick drauf werfen. Verbesserungsvorschläge erwarte ich da nicht zu viele, das ist ein dreckiger Prototyp der 50x soviel rechnet wie nötig. Aber für die aktuelle Hausaufgabe reicht's :autsch:

 

[Marco13]

Hab' mir das Applet mal angesehen - gut, was genau das macht, brauch' ich ja nicht zu verstehen :wink:

Ob Strings oder int[]s ist ja egal - irgendwas um die Potenzen zu erkennen - dass es ... "ungünstig" wäre, den Angedeuteten "PowersStringComparator" zu verwenden, der bei jedem Vergleich erstmal die Strings parsen und die Exponenten rausfinden müßte, ist klar - für eine Lexikographische Sortierung ist int[] (oder eine eigene Klasse) natürlich die richtige Wahl.

Nur du suchst und fügst wieder ein. Einmal get einmal put.

Hmja - dass das "put" nur für die gemacht wird, die noch nicht bekannt sind, hast du ja vermutlich gesehen. Wenn am Ende was sortiertes rauskommen soll, kommt man um das einmalige sortierte Einfügen ja nicht drumrum. Wenn es darum geht, dass bei einer Eingabe wie
x x x x x x x x x x
eben EINmal get+put (mit Laufzeit jeweils O(log n), und dann noch 9 mal get (jeweils WIEDER mit Laufzeit log(n)) gemacht wird: Das könnte man (da Sepeicher vermutlich die untergeordnete Rolle spielt) mit einer zweiten (Hash)map lösen:

Collection<Monom> optimize(Collection<Monom> polynom)
{
    Map<String, Monom> map = new TreeMap<String, Monom>(new PowersStringComparator());
    Map<String, Monom> helpMap = new HashMap<String, Monom>();
    for (Monom monom : polynom)
    {
        Monom resultMonom = helpMap.get(monom.powers);
        if (resultMonom == null)
        {
            resultMonom = new Monom();
            resultMonom.powers = monom.powers;
            map.put(monom.powers, resultMonom);
            helpMap.put(monom.powers, resultMonom);
        }
        resultMonom.factor += monom.factor;
    }
    return map.values();
}

Damit würde bei
x x x x x x x x x x
einmal get mit O(1), dann put mit O(log n), und dann nurnoch 9 mal get mit O(1) gemacht - effizienter geht's IMHO eigentlich nicht, außer, wenn man sich was überlegt, wie man direkt aus den Exponenten die Einfügeposition bestimmt - also im Prinzip mit dem angesprochenen BucketSort.

 

[0x7F800000]

hmm, wieso du da jetzt 2 maps draus gemacht hast ist mir jetzt ein rätsel, denn dein letzter vorschlag würde ja auch schon in O(n log(n)) ohne unnötige wiederholungen laufen, wenn man stillschweigend annimmt, dass so eine konstruktion:

resultMonom.factor += monom.factor;

vorhanden ist. D.h. wenn man "resultMonom.factor=irgendwas" nachträglich setzen kann. Das ist aber nicht gegeben, weil ich alle diese objekte immutabel gemacht hab. Das wäre ansonsten auch viel zu stressig, weil man nach 3 rechenschritten selbst nicht mehr weiß, ob man ein Term noch verändern darf, ohne in irgendeinem unbeteiligten Polynom irgendwas kaputtzumachen. Deswegen ist alles immutabel. Deswegen wird von termA.add(termB) ein neuer term zurückgegeben, der wohl oder übel in die menge neu einsortiert werden muss, es sei denn die Menge selber bewerkstelligt auch die addition.

 

[Marco13]

Äh ja - die zweite Map: Wenn man eine Eingabe mit n Monomen hat, die in k Äquivialenzklassen fallen, dann hätte die ursprüngliche Implementierung eine Laufzeit von

O(k * 2 * log(k) + (n-k) * log(k))

k unbekannte Elemente einfügen braucht k*get und k*put, also k*2*log(k)
(n-k) bekannte Elemente einfügen braucht (n-k) * log(k)

Bei der neuen wäre das nurnoch
O(k * 2 * log(k) + (n-k))

k unbekannte Elemente einfügen braucht k*get und k*put, also k*2*log(k)
(n-k) bekannte Elemente einfügen braucht (n-k) * 1

Was bei SEHR großen n von Vorteil sein könnte.

Aber ich hatte zumindest dahingehend recht dass ich etwas nicht berücksichtigt hatte: Nämlich die Immutabilität.

Jetzt die Softwarearchitekten-Lösung zu nennen wäre ggf. auch nicht das, was du willst... (d.h. von der Klasse "Monom" eine "MutableMonom" abzuleiten, und in der "optimize"-Methode nur mit den MutableMonoms rumzuhantieren, und sie dann als Collection von (immutable) Monomen zurückzugeben)

Vielleicht könnte man noch was dengeln, wenn man sich noch eine Map "powerString->index" speichert oder so, aber da müßt' ich erst noch drüber nachdenken.

 

[0x7F800000]

aaja... statt die elemente also lediglich zu sortieren, hashst du nochmal die äquivalenzklassen... Da bin ich mit meinem Term natürlich wesentlich schneller bei der richtigen Äquivalenzklasse, als wenn ich mich da jedes mal durch irgendeinen bescheuerten baum durchkämpfe. Hey, das ist geil! Echt ein guter vorschlag, auf so eine sortierende-&-hashende hybridlösung wäre ich in einem halben jahr nicht gekommen :toll: Danke, werde das beim neuschreiben unbedingt berücksichtigen :###

 

[Marco13]

Aber irgendwie kann ich mir kaum vorstellen, dass diese asymptotischen Laufzeitbetrachtungen wirklich gerechtfertigt sind - du hattest zwar gesagt, dass du "sehr oft mit sehr kleinen Polynomen in drei variablen" rechnest, aber ... um welche n's und k's geht's denn so?

(In dem Applet hatte ich die Standard-Vorgabe mal ausgerechnet, und gedacht: "Ja und, ging doch flott" - und weil er aus diesen 3 Zeilen eine ziemlich lange Ausgabe erzeugt hatte, hab ich mir gedacht: "Hähähä, jetzt bring' ich ihn mal ins Schwitzen" und die Ausgabe mit Copy&Paste wieder als neue Eingabe verwendet ... ... :roll: (Jaja, nicht lachen, das konnt' ich ja nicht ahnen... zumindest hab' ich damit eine Kleinigkeit über Gröbnerbasen gelernt :lol: )

 

[0x7F800000]

Aber irgendwie kann ich mir kaum vorstellen, dass diese asymptotischen Laufzeitbetrachtungen wirklich gerechtfertigt sind - du hattest zwar gesagt, dass du "sehr oft mit sehr kleinen Polynomen in drei variablen" rechnest, aber ... um welche n's und k's geht's denn so?

Wenn ich's wüsste^^
Ehrlichgesagt: Ich habe keine Ahnung! KA wie in etwa das Gleichungssystem für zB.

so ein Viech aussieht. Aber ich will so ein teil in meinem Garten hinstellen^^

Ich habe jedenfalls gehört, dass es manchmal problematisch ist, aus großen Gleichungssystemen zB irgendwelche Variablen herauszueliminieren. Da machen sich die Leute schon sorgen um Performance, das ist nicht alles auf "klick" sofort da... Deswegen will ich mir schonmal überlegen, wie ich zumindest die oft verwendeten Kleinigkeiten schnell hinbekomme. Wenn im Detail alles stimmt, wird es später auch im großen irgendwie passen

(In dem Applet hatte ich die Standard-Vorgabe mal ausgerechnet, und gedacht: "Ja und, ging doch flott"

Ja, "flott", dieses Beispiel war ja auch als Hausaufgabe gedacht, die per Hand durchzurechnen ist :autsch:
Keine wirklich gute Benchmark
(per hand ging's übrigens wesentlich schneller, weil man zwischendurch durch "scharfes hinguggen" alles wegwerfen konnte, aber das weiß der [bisher] stur rechnende Computer ja nicht, produziert deswegen tonnen von Output... :roll: )

... - und weil er aus diesen 3 Zeilen eine ziemlich lange Ausgabe erzeugt hatte, hab ich mir gedacht: "Hähähä, jetzt bring' ich ihn mal ins Schwitzen" und die Ausgabe mit Copy&Paste wieder als neue Eingabe verwendet ... ... :roll: (Jaja, nicht lachen, das konnt' ich ja nicht ahnen... zumindest hab' ich damit eine Kleinigkeit über Gröbnerbasen gelernt :lol: )

Beim zweiten Durchlauf ist nicht viel neues Hinzugekommen, hoffe ich doch??? :lol: :toll:

 

[Marco13]

Wenn ich's wüsste^^
Ehrlichgesagt: Ich habe keine Ahnung! KA wie in etwa das Gleichungssystem für zB.

so ein Viech aussieht. Aber ich will so ein teil in meinem Garten hinstellen^^

OK, der Zusammenhang zwischen diesem Bild und irgendwelchen Polynomgleichungen erschließt sich mir nicht unmittelbar (gehe aber davon aus, dass das die geplotteten "Nullstellen" sind).

Jetzt die Leier von "Premature Optimization" zu bringen wäre wohl nicht zielführend - wenn man (nicht durch irgendwelche Hacks die "Anzahl der ausgeführten Instruktionen" (bei gleicher Asymptotischer Laufzeit) zu verringern versucht, sondern) schon früh erkennt, dass man die Asymptotische Laufzeit "deutlich" reduzieren kann, macht man das natürlich - ob dann irgendwo anders Rechenzeit verbraten wird (z.B. weil man wegen einer Immutable-Klasse irgendwelche Workarounds basteln muss :wink: ) sieht man dann im Profiler...

Beim zweiten Durchlauf ist nicht viel neues Hinzugekommen, hoffe ich doch??? :lol: :toll:

*grummel* :x :wink:

 

[0x7F800000]

OK, der Zusammenhang zwischen diesem Bild und irgendwelchen Polynomgleichungen erschließt sich mir nicht unmittelbar (gehe aber davon aus, dass das die geplotteten "Nullstellen" sind).

was es jetzt genau ist weiß ich auch nicht... aber es sieht, genau wie du gesagt hast, nach einer Form aus, die entsteht, wenn man nach einer verschwindungsmenge mehrerer polynome sucht.

Jetzt die Leier von "Premature Optimization"

nnaja, das passt(e) vor drei tagen noch nicht wirklich. Da hatte ich ja ein sehr kleines sehr klares sehr atomares Ziel: einfach schnell mit polynomen rumhantieren zu können.
Bezogen auf "das ganze" (wie etwa den applet da) hast du natürlich vollkommen recht, ich mach mir hier sorgen um irgendwelche performance-krümmel, während an anderen stellen rechenzeit übelst verschleudert wird. Mittlerweile (in 3 tagen ) haben sich die prioritäten ja auch deutlich verlagert, das passiert halt schnell, wenn man anfängt einfach so drauflos zu programmieren, obwohl man erst vor kurzem von dem thema überhaupt erfahren hat, und nicht wirklich den überblick hat, was man da eigentlich macht und was das alles soll :roll:

Also, jetzt scheint's ja
1) fast immer zu funktionieren
2) wenn, dann richtig zu funktionieren.
Jetzt rechne ich ein paar tage auf dem papier herum, hol mir noch ein wenig inspiration in den theoretischen übungen, schaue es mir nochmal aus der distanz an, schmeiß unnötig komplizierte konstrukte raus, und schreibe das größtenteils einfach neu, zum zweiten mal aber ordentlich und dokumentiert usw.... :toll: Diese 0-te vesion habe ich irgendwie gleich beim ersten anlauf komplett eigetippt, und habe dabei in ~1200 höchstens 5 Zeilen kommentar verwendet^^ :autsch: Wundert mich sehr, warum da überhaupt irgendwas läuft, und auch noch korrekt :shock: