[Programmiererstammtisch] "Zum ächzenden Compiler"

[Zulan]

Ich würde die nun gerne alle Möglichkeiten mit je einem Element aus jeden Vektor erstellen und die neuen Kombinationen in Vektoren speichern.

Ich glaube das ist nicht unbedingt das was du eigentlich willst. Du kommst vermtulich besser wenn du die Kombinationen immer dynamisch erzeugst.

[Strat]

Inwiefern hilft es mir die Kombinationen dymamisch zu erzeugen

[Zulan]

Inwiefern hilft es mir die Kombinationen dymamisch zu erzeugen

Was machst du mit den Kombinationen denn?

[Shakka]

Inwiefern hilft es mir die Kombinationen dymamisch zu erzeugen

Wenn Du sie nicht alle wirklich brauchst, sondern sie nur aufstellst um später wenige davon auszuwählen, hilft es sehr viel.
Dann geht plötzlich auch 1000x1000 statt 5x3.

Auch wenn diese Dinger nur aufgestellt werden um danach stück für stück "abgearbeitet" und verworfen werden, hilft es viel. Die Teile brauchen unter Umständen sehr viel Speicher. Wenn man sie erst alle aufbaut benötigt man eben viel Speicher.
Wenn man immer nur die im Speicher hat, die man aktuell wirklich benötigt, braucht man fast gar keinen Speicher mehr.

[Strat]

Dann erläutere ich mal genau wozu die Kombinationen sind.

Ich programmiere an einem Spiel in dem der Spieler die Position des Regierungschefs übernimmt. Ähnlich Democrazy
Es gibt verschiedene Strömungen in der Bevölkerung: Sozialisten, Kapitalisten, Patrioten etc.
Der Algorithmus erzeugt dann die Bevölkerungsgruppen aus Kombinationen aus denen: z.B. reiche patriotsche Sozialisten, arme liberale Umweltschützer. Da diese Merkmale per Editor festgelegt werden und gelöscht/neu erzeugt, soll zum Start das Programm alle Gruppen erzeugen bis auf sich gegenseitig auschließende z.B. sozialistische Kapitalisten. Jede erzeugt Gruppe hat dann durch die Kombination eine spezifische Meinung zur Regierung. Da die alle gleichzeitig aktiv sind, würde ich nicht sagen, dass es mir etwas bringt die dynamisch zu erzeugen.

[alpha civ]

Werden überhaupt alle diese Kombinationen gebraucht?

[Strat]

In der bisherigen Idee werden alle gebraucht. Die nicht benötigten sind schon vorher aussortiert worden durch die GruppenID.

[Zulan]

Dann erläutere ich mal genau wozu die Kombinationen sind.

Ich programmiere an einem Spiel in dem der Spieler die Position des Regierungschefs übernimmt. Ähnlich Democrazy
Es gibt verschiedene Strömungen in der Bevölkerung: Sozialisten, Kapitalisten, Patrioten etc.
Der Algorithmus erzeugt dann die Bevölkerungsgruppen aus Kombinationen aus denen: z.B. reiche patriotsche Sozialisten, arme liberale Umweltschützer. Da diese Merkmale per Editor festgelegt werden und gelöscht/neu erzeugt, soll zum Start das Programm alle Gruppen erzeugen bis auf sich gegenseitig auschließende z.B. sozialistische Kapitalisten. Jede erzeugt Gruppe hat dann durch die Kombination eine spezifische Meinung zur Regierung. Da die alle gleichzeitig aktiv sind, würde ich nicht sagen, dass es mir etwas bringt die dynamisch zu erzeugen.

Wie greifst du auf die Kombinationen zu?
Welche Daten zu den Gruppen werden gespeichert? Die Mitglieder? Sonst was?
Kann sich zur Lebzeit eines Buergers die Zugehoerigkeit aendern?
Enstehen dynamich neue Buerger?

Ich gehe davon aus eine Baumstruktur eignet sich wesentlich besser als der Vektor.

[Strat]

Die Gruppen der Bürger enthalten als Attribute dieGröße der Gruppe(entweder als Anteil oder in absoluten Zahlen) und der Anteil der Gruppe, welcher die Regierung wählt. Eventuell auch noch die Beliebtheit mit der anderen Partein. Im Moment aber noch nicht weiter von Belang.
Diese Werte werden geändert. Es entstehen keine neuen Kombinationen, nur kann es bei manchen Kombinationen sein, dass sie zu Start 0 Menschen sind.
Die Zugehörigkeit eines Bürgers kann sich darausfolgend auch ändern.
Zugriff geschieht über die Merkmale. Da werden dann alle Gruppen nach dem Merkmal abgesucht und dann die Ergebnisse geändert.

Und jede Gruppe erhält natürlich eine ID.

[alpha civ]

Also kann man das als Schlüssel-Wert-Paare auffassen? Die Merkmale einer Gruppe bildet einen Schlüssel, die Anzahl der Leute sowie der Anteil der Wähler den Wert.
Da wäre wohl ein Binärbaum geeignet. Die Schlüssel könnte man durch nicht-negative Zahlen repräsentieren. Wenn man z.B. die 3 Merkmale Sozialisten, Kapitalisten, Patrioten hat, dann könnte man den einzelnen Kombinationen von Merkmalen Binärzahlen mit 3 Bits zu ordnen: Sozialist das 3. Bit, Kapalist das 2. und Patriot das 1. Der Schlüssel zur Kombination [Sozialist, Patriot] wäre dann 101.
Die Menge aller dieser Kombinationen kann durch einen Binärbaum (hier mit Tiefe 3) dargestellt werden. Die Kanten sind mit 0 oder 1 beschriftet, die Blätter enthalten die Werte.

[Strat]

Schlüssel-Wert Paar klingt interessant.

Ein Binärbaum reicht nach meiner kurzen Recherche nicht aus, da es an mindestens 1 Stelle 3 Varianten gibt. Und So Sachen wie Sozialist und Kapitalist müssen sich ausschließn. Man könnte natürlich sagen, dass auf einen Wert ungleich Null, immer eine Null folgen muss Nur dann ist auch die 2 Nullstellensache noch etwas zum ausarbeiten

[alpha civ]

Das Speichern der Kombinationen und die Auschließungslogik sind zwei verschiedene Sachen. Was immer auch du für einen Container zum Speichern nimmst, diesen Container kann es egal sein, welche Kombinationen nicht möglich sind. Der Code, der diesen Container verwendet, ist dafür verantwortlich, dass keine ungültigen Kombinationen gespeichert werden.

[Zulan]

Die Gruppen der Bürger enthalten als Attribute dieGröße der Gruppe(entweder als Anteil oder in absoluten Zahlen) und der Anteil der Gruppe, welcher die Regierung wählt. Eventuell auch noch die Beliebtheit mit der anderen Partein. Im Moment aber noch nicht weiter von Belang.
Diese Werte werden geändert. Es entstehen keine neuen Kombinationen, nur kann es bei manchen Kombinationen sein, dass sie zu Start 0 Menschen sind.
Die Zugehörigkeit eines Bürgers kann sich darausfolgend auch ändern.
Zugriff geschieht über die Merkmale. Da werden dann alle Gruppen nach dem Merkmal abgesucht und dann die Ergebnisse geändert.

Und jede Gruppe erhält natürlich eine ID.

Es gibt damit ein paar Probleme. Die Kombinationsgruppen werden durch die Eigenenschaften (Gruppenzugehoerigkeit) der Buerger-Objekte definiert. Diese definieren auch die Gruppengroessen und deren Mitglieder. Wenn du jetzt diese Daten zusaetzlich nochmal speicherst, erzeugst du Redundanzen. Einerseits macht es das von der Entwicklung schwierig, weil sich dabei boese Bugs (Inkosnistenzen) einschleichen koennen. Andererseits bei einem solchne "Cache" auch die Frage wie das update/read-Verhaeltnis ist. Je nach Wahl der Datenstruktur kann so ein update durchaus sehr ineffizient sein.

Bezueglich der Schluessel-Werte-Map wuerde ich mir keine Gedanken um die Low-Level Implementierung im sinne von Bits machen. Entweder du nimmst eine map, dann brauchst du less, oder du nimmst eine unordered_map, dann brauchst du operator== und hash, jeweils auf das Tupel der Gruppenzugehoerigkeiten.

Das bloede ist, dass du bei Aenderungen der einzelnen Gruppenzugehoerigkeit eines Buergers alle Kombinationsgruppen aktualisieren muesstes. Ich glaube aber, dass du das mit einer klugen Baumstruktur optimieren kannst, so dass sowohl das update als auch das lesen nur linear/n log(n) mit der Anzahl der Gruppen (nicht Kombinationsgruppen) skaliert. Dabei kannst du dir entsprechend die Reglen zur Berechnung der Groesse von Teilmengen zu nutze machen. Ich bin aber nicht ganz sicher und kann es gerade nicht ausformulieren. Ansonsten hilft dir vielleicht auch der Begriff der Formalen Begriffsanalyse.

[Flati]

Ich würde dir raten nicht auf Vektoren oder ähnlich Datentypen zurück zu greifen, sondern auf Objekte. Sonst wirst du das Programm nur ganz schwer erweitern/warten können. Das heißt du hast dann ganz viele Objekte "Gruppe", wo die verschiedenen Ausrichtungen codiert sind. Etwas weiter gesponnen könntest du dann diesen Ausrichtungen auch gezielt "wichtige" Personen zuordnen, bzw. wieder entfernen und einer anderen Gruppe zuordnen. Dass Objekt "Gruppe" hat dann ein Feld "Reichtum", Anzahl Mitglieder, usw. was dann z.B. auf einer Skala von 1 - 5 das als int codiert sein kann.
Um diese Objekte zu erzeugen brauchst du wie schon beschrieben einen rekursiven Ansatz(vorallem wenn alle Kombination, mit wenigen Ausnahmen gewünscht sind), insbesondere dann wenn noch nicht ganz klar ist wieviele es endgültig gibt oder man das irgendwann noch erweitern will.
Wenn du dann schnell auf die Objekte zugreifen musst brauchst du so eine Art hashMap(wo ein direkter Link anhand der gewünschten Eigenschaft) auf das Objekt zugreifen kann, oder alternativ einen Baum wo man sich durchhangelt.
Bei so einen Ansatz hat man auch die Möglichkeit dynamische neue Gruppen hinzuzufügen, falls einen die möglichen Kombination irgendwann zu viel werden.

Edit: Der Reichtum, Durchschnittsalter usw. kann sich dann auch implizit durch die Eigenschaften der zugeordneten Personen ergeben, bzw. dynamisch verändern wenn man eine Person entfernt und dann einer anderen Gruppe hinzufügt.

[Gullix]

...also, irgendwie klingt das für mich, als würdest du dir unnötig das Leben schwer machen.

Ich vermute mal, du hast nicht eine Million Gruppen, sondern vielleicht zwanzig oder wenns hoch kommt auch mal hundert, nicht mehr. Da kann man Performance doch ignorieren und einfach das nehmen, was einfach zu programmieren ist. Liste oder Vector oder Array oder sowas. Dann machste dir ne Klasse oder struct "Gruppe", das kriegt ein paar Bits (Sozialist ja/nein, Kapitalist ja/nein, ...) und ein paar andere Felder (int mitgliederzahl und so), und die kannst du abfragen. Dann gehste halt an der Liste entlang und hast im dümmsten Fall mal 100 if-Abfragen, die kosten bei modernen CPUs ja nix mehr.

Oder ich übersehe etwas...