Variablen Wie kann man ein Objekt austauschen?

[Miikku]

Hi!

Also beim Objekttausch geht es nicht um das simple

Object a = new Object();
Object b = new Object();
{Object tmp=a;a=b;b=tmp;}

Es geht vielmehr darum, dass ich versuche zwei Familien darzustellen und dass nun zwei Leute jeweils aus einer der Familien heiraten. Was mach ich dann? Folgende Definition:

class Family{
 public int ArrayList<Human> members;
 public Family(){this.members = new ArrayList();}
 public Family(Human[] members){
  this.members = new ArrayList( Arrays.asList( members ) );
 }
 public void connectWithFamily( Family family ){
  this = family; //Das geht natürlich nicht, aber darum geht es hier...
 }
}
class Human{
 public Human spouse;
 public Family family;
 public Human(Family family){
  this.family = family;
 }
 public void marry(Human spouse){
  this.spouse = spouse;
  if( spouse.spouse != this )
   spouse.marry( this );
  this.family.connectWith( spouse.family );
 }
}

Für folgendes Szenario:

Family petersFamily = new Family(), annasFamily = new Family();
Human peter = new Human(petersFamily);
Human petersMom = new Human(petersFamily);
Human anna = new Human(annasFamily);
Human annasMom = new Human(annasFamily);
peter.marry(anna);
if( petersMom.family == annasMom.family ) //Sollte zutreffen
 System.out.println("Annas Mutter ist in der gleichen Familie, wie Peters Mutter!");

Und sagt bitte nicht

 public void connectWithFamily( Family family ){
  for( Human member : members )
   member.family = family;
 }

Das Ergebnis wäre zwar das richtige, aber was, wenn Hans als Variable irgendwo die Familie seines besten Freundes Peter gespeichert hat? Dann könnte ich über Hans noch an die alte unvollständige Familie kommen und die sollte eig. gar nicht mehr existieren, damit der Garbage-Collector sie sich einverleiben kann!

Was ich machen möchte ist quasi ein Austausch aller Referenzen auf Peters Familie durch Annas Familie. Und am besten irgendwas performantes, ich kämpfe sowieso schon gegen Performance-Fresser in Form von Exceptions und dergleichen.
[OT]Apropos, hat jemand eine performante Idee, einen String auf ihren Zahlengehalt zu checken? Also zu prüfen, ob "73.57" eine Zahl ist und "te.st" keine, ohne eine Exception zu schmeißen?[/OT]

Es wäre echt cool, wenn jemand einen Vorschlag hätte, ich muss mein Projekt nämlich bis ich eine Idee habe auf Eis legen...

Mit freundlichen Grüßen,
Miikku

 

[Wildcard]

Wenn Anna eine Schwester hat, und sie in eine dritte Familie einheiratet, zu welcher Familie gehört Anna, zu welcher ihre Schwester, und zu welcher ihre Mutter?
Dein Beispiel ist nicht durchdacht, du bräuchtest mehr als eine Familie pro 'Human'.
Ausserdem hast du nicht erklärt welche Vorraussetzungen erfüllt sein müssen damit die jemand als einer Familie zugehörig betrachtest, also lässt sich dazu nicht viel sagen.

 

[Dekker]

Ist das hier ein reales Beispiel deines Projektes oder hast du hier ein übertragendes Beispiel onlinegestellt? Warum ist hier die Performance so drastisch? Echtzeitsystem?

Mal allgemein gesagt, desto mehr Referenzen du verwaltest, desto aufwendiger wird auch deren Verwaltung. Man kommt halt nicht drum herum die Referenzen alle zu ändern.

 

[Miikku]

Also ich hab wohl ein wichtiges Detail vergessen zu beschreiben.
Die Familien fusionieren sich automatisch, also wenn Peter in Annas Familie einheiratet, werden alle Mitglieder aus seiner Familie und die aus Annas Familie in eine neue Familie gepackt (oder um sich die Hälfte der Schieberei zu ersparen in eine der schon existierenden Familien).
Das könnte gecoded ungefähr so aussehen:

 public void connectWithFamily( Family family ){
  for( Human member : family.members ){
   member.family = this;
   this.members.add( member );
  }
 }

Also zur Frage

Wenn Anna eine Schwester hat, und sie in eine dritte Familie einheiratet, zu welcher Familie gehört Anna, zu welcher ihre Schwester, und zu welcher ihre Mutter?

Alle gehören sie in die große Familie, die sich gebildet hat.

Ausserdem hast du nicht erklärt welche Vorraussetzungen erfüllt sein müssen damit die jemand als einer Familie zugehörig betrachtest, also lässt sich dazu nicht viel sagen.

Folgende Definitionen:
Alle Ehepaare gehören in eine Familie.
Alle Eltern gehören in die gleiche Familie wie alle ihre Kinder.

Genug definiert?

Also ich habe immer noch keine Lösung und bin weiterhin offen für Vorschläge.

[EDIT]

Ist das hier ein reales Beispiel deines Projektes oder hast du hier ein übertragendes Beispiel onlinegestellt? Warum ist hier die Performance so drastisch? Echtzeitsystem?

Ja das ist ein übertragendes Beispiel, ich habe es ehrlich gesagt nicht einmal getestet... aber in der Theorie ist es das gleiche.
Das mit der Performance liegt daran, dass es sich um eine Simulation handelt, die bestimmte statistische und repräsentative Daten über Menschenmengen bzw. Menschen sammeln soll und die wird natürlich immer genauer, je nach dem, wie viele Menschen man gleichzeitig simuliert. Wenn man alle 82kk Einwohner Deutschlands simulieren möchte, läuft die Simulation schon mal ein paar Minuten und das, obwohl ich noch am Anfang stehe und die Datenmengen vermutlich noch um ein vielfaches steigen. Mir ist natürlich klar, das man das professioneller entweder mit nur primitives oder in C schreibt, aber ich bin halt kein mehrköpfiges Team^^.
[OT]Jedenfalls muss ich beim überprüfen von Tabellenwerten öfters überprüfen ob es sich tatsächlich um Zahlenwerte handelt und das frisst im Moment schon eine Menge Zeit, vor allem wenn es eben keine Zahl ist. Aber sobald ich die Zeit dazu finde, werde ich da ein Caching-System für einbauen. Bis dahin und auch dann noch in geringem maße ist die Performance maßgeblich von der Zahlenüberprüfung beeinflusst.[/OT]

Mal allgemein gesagt, desto mehr Referenzen du verwaltest, desto aufwendiger wird auch deren Verwaltung. Man kommt halt nicht drum herum die Referenzen alle zu ändern.

Du meinst also eine allgemeine Methode gibt es nicht. Java bietet keine Möglichkeit mit dieser Situation seriös umzugehen?
Dann darf ich einfach niemals eine direkte Referenz auf eine Familie abspeichern, sondern entweder nur einen Menschen aus einer Familie, oder... ich hab eine Idee... ich glaube die ist gar nicht mal schlecht. Folgendes:

class Folk{ //Kann man ja noch umbenennen xD
 public Family family;
 public Folk(){
  this.family = new Family();
 }
 public Folk(Human[] members){
  this.family = new Family( members );
 }
 public Folk(Family family){
  this.family = family;
 }
}

Und dann speichert man immer nur das entsprechende Volk ab und greift darüber auf die Familie zu, sodass man nur noch die Familie des Volkes ändern muss. Ich find mich gut
Nur das das wiedermal der Performance nicht gut tut, aber ich glaube im Vergleich zu dem Exception-Problem ist das hier zu verkraften

Danke Dekker!
[/EDIT]

Mit freundlichen Grüßen,
Miikku

 

[0x7F800000]

1) Wenn generics, dann generics! Lass solche scherze wie "new ArrayList()"
2) das wovon du hier sprichst sieht aus wie Union-Find, die Struktur ist sehr schnell und ziemlich einfach, skizze kommt
3) Exceptions legen alles lahm, bastle dir ein regex um die strings zu prüfen. Wahrscheinlich gibt's die irgendwo schon eingebaut, muss mal guggen...

Mir ist natürlich klar, das man das professioneller entweder mit nur primitives oder in C schreibt, aber ich bin halt kein mehrköpfiges Team^^.

macht hier einer auf r341 pr0gr4mm3r oder was soll der Unsinn? Java läuft fast genauso schnell wie C, und wenn's dir nicht reicht, dann bringt's nix, auf assembler umzusteigen: versuche lieber
1) den code ohne groben Unfug zu schreiben (Exceptions zum zahlen-prüfen)
2) evtl zurechnungsfähigen mathematiker fragen, ob es für dein problem einen algo gibt, der um O(n^3) schneller läuft
3) evtl GPU mit an bord nehmen, sehr angenehm, wie ich gerade herausfinde
4) weitere Rechner hinzuziehen, mieten, grid organisieren, sonstwas...
NIX von alledem macht man in C (bis evtl. bissl GPU proggen)

[OT]Jedenfalls muss ich beim überprüfen von Tabellenwerten öfters überprüfen ob es sich tatsächlich um Zahlenwerte handelt und das frisst im Moment schon eine Menge Zeit, vor allem wenn es eben keine Zahl ist. Aber sobald ich die Zeit dazu finde, werde ich da ein Caching-System für einbauen. Bis dahin und auch dann noch in geringem maße ist die Performance maßgeblich von der Zahlenüberprüfung beeinflusst.[/OT]

Das hört sich nach gröbsten Unfug an. Man rechnet nicht mit Textdateien: mit Abstand komplizierteste rechenoperation, die du mit einer zahl ausführen kannst, ist es, diese zu Schreiben oder zu parsen. Bringe also deine daten in einen vernünftigen Zustand, bevor du damit irgendetwas ausrechnest.

 

[0x7F800000]

Also, das sollte funzen, lag aber seit hundert jahren in einer ecke herum, hab's grad nicht getestet:

package datastructures;

import java.util.*;

public class UnionFind<T>{
        /** Gruselige Implementierungsdetails, gehen den user nichts an
           */
	private class TreeNode{
		T value;
		TreeNode parent;
		int numberOfDescendants;
		public TreeNode(T value) {
			this.value = value;
			this.parent = null;
			numberOfDescendants=0;
		}
		
		public T getValue(){
			return value;
		}
		
		public TreeNode getRootAndCompress(){
			if(this.parent==null){
				return this;
			}else{
				TreeNode root=this.parent.getRootAndCompress();
				this.parent=root;
				return root;
			}
		}
		
		public void union(TreeNode other){
			if(other.numberOfDescendants>this.numberOfDescendants){
				other.numberOfDescendants+=this.numberOfDescendants+1;
				this.parent=other;
			}else{
				this.numberOfDescendants+=other.numberOfDescendants+1;
				other.parent=this;
			}
		}
	}
	
	private HashMap<T,TreeNode> map;
	private int numberOfSubsets;
	
        /** leeres UnionFind bauen. Elemente hinzufügen geht mit makeSet()
           */
	public UnionFind(){
		this(new HashSet<T>());
	}
	
        /** neues UnionFind basteln, es mit elementen von set füllen. Alle elemente werden
          * als mengen für sich betrachtet, nichts ist vereint
          */ 
	public UnionFind(Set<T> set){
		map=new HashMap<T,TreeNode>(set.size());
		for(T t:set){
			map.put(t, new TreeNode(t));
		}
		numberOfSubsets=set.size();
	}
	
        /** leeres Union find bestimmter größe erzeugen. Die größe ist nur Hint für HashMap
           */
	public UnionFind(int initialSize){
		map=new HashMap<T,TreeNode>(initialSize);
		numberOfSubsets=0;
	}
	
        /** fügt ein neues element zu unionfind hinzu. Das neue element ist von allen anderen getrennt
          */
	public boolean makeSet(T t){
		if(!map.containsKey(t)){
			map.put(t,new TreeNode(t));
			numberOfSubsets++;
			return true;
		}else{
			return false;
		}
	}
	
        /** gibt den representanten der "familie" bzw. der partition zurück
          */
	public T find(T t){
		TreeNode node=map.get(t);
		if(node!=null){
			return node.getRootAndCompress().getValue();
		}
		return null;
	}
	
        /** vereinigt "familien" von a und b
           */
	public boolean union(T a, T b){
		TreeNode aRoot=map.get(a).getRootAndCompress();
		TreeNode bRoot=map.get(b).getRootAndCompress();
		if(aRoot!=null && bRoot!=null && aRoot!=bRoot){
			aRoot.union(bRoot);
			numberOfSubsets--;
			return true;
		}
		return false;
	}
	
        /** anzahl der familien
          */
	public int getNumberOfSubsets(){
		return numberOfSubsets;
	}
	
        /** alle familien zurückgeben
          */
	public Collection<Set<T>> getSubsets(){
		Map<T,Set<T>> representantsToSets=new HashMap<T,Set<T>>(numberOfSubsets);
		for(T t:map.keySet()){
			T representant=find(t);
			if(!representantsToSets.containsKey(representant)){
				representantsToSets.put(representant,new HashSet<T>());
			}
			representantsToSets.get(representant).add(t);
		}
		return representantsToSets.values();
	}
	
	@Override
	public String toString(){
		return getSubsets().toString();
	}
	
	//hashCode, equals, clone make no sense, because this Structure is dynamic
	
        /** kleines demo mit ints
          */
	public static void main(String[] args){
		UnionFind<Integer> u=new UnionFind<Integer>(new HashSet<Integer>(Arrays.asList(1,2,3,4,5)));
		System.out.println(u+" "+u.numberOfSubsets); for(Integer i:u.map.keySet()) System.out.print(i+"->"+u.find(i)+"\t"); System.out.println();
		u.union(2,3);
		System.out.println(u+" "+u.numberOfSubsets); for(Integer i:u.map.keySet()) System.out.print(i+"->"+u.find(i)+"\t"); System.out.println();
		u.union(2,2);
		u.makeSet(7);
		System.out.println(u+" "+u.numberOfSubsets); for(Integer i:u.map.keySet()) System.out.print(i+"->"+u.find(i)+"\t"); System.out.println();
		u.union(1,7);
		System.out.println(u+" "+u.numberOfSubsets); for(Integer i:u.map.keySet()) System.out.print(i+"->"+u.find(i)+"\t"); System.out.println();
		u.union(1,4);
		System.out.println(u+" "+u.numberOfSubsets); for(Integer i:u.map.keySet()) System.out.print(i+"->"+u.find(i)+"\t"); System.out.println();
		u.union(3,4);
		System.out.println(u+" "+u.numberOfSubsets); for(Integer i:u.map.keySet()) System.out.print(i+"->"+u.find(i)+"\t"); System.out.println();
		u.union(1,5);
		System.out.println(u+" "+u.numberOfSubsets); for(Integer i:u.map.keySet()) System.out.print(i+"->"+u.find(i)+"\t"); System.out.println();
		u.union(2,4); 
		System.out.println(u+" "+u.numberOfSubsets); for(Integer i:u.map.keySet()) System.out.print(i+"->"+u.find(i)+"\t"); System.out.println();
	}
}

Du schmeißt all deine Humans in ein Set<Human>, übergibst es an den konstruktor der union find, und dann muss du nur noch union(mann, frau) aufrufen, um ihre familien zu vereinen.

THEORIE: Das funktioniert so: du vergisst dein "family"-konzept komplett, und speicherst für jeden Human nur noch den Kopf der Familie (bzw. die Human-Klasse geht das alles nichts mehr an, das wird alles automatisch von UnionFind erledigt). Bei der anfrage, zu welcher familie man denn gehöre, gibt man einfach rekursiv den Familienkopf zurück, und merkt sich den dabei, wer denn der Familienkopf ist (Pfadkompression, wird auch alles automatisch erledigt). Durch die permanente Pfadkompression wächst die Zugriffszeit asymptotisch etwa wie die inverse Ackermann funktion, und da kannst du beliebig große Zahlen einsetzen, da kommt immer fünf raus, d.h. alle operationen passieren praktisch in konstanter Zeit. Beim vereinen der familien muss man nur noch eine einzige referenz umbiegen: die familienköpfe müssen sich einfach darauf einigen, wer wen als familienkopf abspeichert, fertig. Das sollte einige umkopiererei ersparen.

 

[Wildcard]

Das ganze ist ein 4 Zeiler wenn du es mit EMF modellierst:

public void marry(Human spouse){
    setSpouse(partner);
    List<Human> formerFamily = new ArrayList(getFamily().getMembers());
    setFamily(spouse.getFamily());
    getFamily().addAll(formerFamily);
}

Family#members ist eine Containment Referenz mit EOpposite zu Human#family und Human#spouse ist ein EOpposite zu sich selbst.

 

[Miikku]

1) Wenn generics, dann generics! Lass solche scherze wie "new ArrayList()"

Hast recht, das war ein grober Fehler in dem Exempel. In meinem Code steht es natürlich richtig.

2) das wovon du hier sprichst sieht aus wie Union-Find, die Struktur ist sehr schnell und ziemlich einfach, skizze kommt

Klingt ganz hilfreich, aber anhand des Wortes "Union-Find" fällt es mir nicht direkt wie Schuppen von den Augen... was genau ist das?

Exceptions legen alles lahm, bastle dir ein regex um die strings zu prüfen. Wahrscheinlich gibt's die irgendwo schon eingebaut, muss mal guggen...

Regex's sind also nicht lahm? ???:L Ich dachte die währen so ungefähr das Beispiel für Langsamkeit schlechthin. Aber ehrlich gesagt hab ich auch keine bessere Idee :bahnhof:

macht hier einer auf r341 pr0gr4mm3r oder was soll der Unsinn? Java läuft fast genauso schnell wie C, und wenn's dir nicht reicht, dann bringt's nix, auf assembler umzusteigen

Nicht so voreilig bitte, denn 1. meine ich bloß, dass man das ganze mit Sicherheit auch ohne Objekte und mit optimierten Routinen angehen kann (im übrigen kannst du die Geschwindigkeit von C und Java nicht vergleichen, weil sich objektorientierter Code auf C, objektlos wie es ist, kaum übertragen lässt) und 2. war das natürlich eine Übertreibung, mit der ich nur darauf hinweisen wollte, dass ich natürlich als einzelner Mensch keinen wirklich performanten Code schreiben kann und einfach keine Zeit habe, z.B. ArrayList's durch echte Arrays zu ersetzen.

den code ohne groben Unfug zu schreiben (Exceptions zum zahlen-prüfen)

Sag ich ja die ganze Zeit xD
Im übrigen scheint sich aber über Zahlenprüfungsgeschwindigkeiten in Java außer mir keiner Sorgen zu machen. Kein ganz durchschnittliches Ergebnis, wenn man "java isnumeric" googlet hat eine Methode ohne Exceptions oder Schleifen.

evtl zurechnungsfähigen mathematiker fragen, ob es für dein problem einen algo gibt, der um O(n^3) schneller läuft

Also erstens halte ich mich selber für so einen Mathematiker (achtung, zweckmäßige Übertreibung ) und zweitens handelt es sich auch um, wie ich sie oben schon nannte, "representative" Berechnungen. Das bedeutet ich schnappe mir einen Menschen aus der Menge und schaue mir seine Daten an. Das ist nötig, weil die Daten eines Menschen miteinander verzahnt sind und Durchschnittswerte da nicht mithalten können und einfach, weil es einem diesen Menschen näher bringt .

evtl GPU mit an bord nehmen, sehr angenehm, wie ich gerade herausfinde

Danke für den Vorschlag, aber das ist wohl eher ein Zusatz, der sich auch im Nachhinein noch installieren lässt, oder?

Das hört sich nach gröbsten Unfug an. Man rechnet nicht mit Textdateien: mit Abstand komplizierteste rechenoperation, die du mit einer zahl ausführen kannst, ist es, diese zu Schreiben oder zu parsen. Bringe also deine daten in einen vernünftigen Zustand, bevor du damit irgendetwas ausrechnest.

In die Berechnungen fießen statistische Daten ein, die sich mit der Zeit ändern. Außerdem müssen sie editierbar sein, für den Fall, dass man ein anderes als das voreingestellte Land simulieren möchte. Deshalb lese ich zum Programmstart ein paar CSV-Tabellen aus und cache sie. Nur das ich momentan noch bei jedem Zugriff auf Tabellendaten überprüfe, ob es sich um einen Text oder eine Zahl handelt ist nicht direkt verantwortbar aber weiter oben steht schon geschrieben, dass ich das langfristig gar nicht vor habe.

@Wildcard:

Das ganze ist ein 4 Zeiler wenn du es mit EMF modellierst

Wth ist EMF? ???:L

Und was du da schreibst ist ja nett und funktioniert und so... aber was hat das mit dem Problem zu tun?

 

[Wildcard]

@Wildcard:

Wth ist EMF? ???:L

Und was du da schreibst ist ja nett und funktioniert und so... aber was hat das mit dem Problem zu tun?

EMF ist ein Modellierungswerkzeug für strukturierte Datenmodelle (wie deine Familien).
Eclipse Modeling - EMF - Home
Was es mit dem Problem zu tun hat? Na es tut genau das was du angestrebt hast.
Family#members und Human#family sind gegensätzliche Beziehungen, genauer gesagt ein Spezialfall davon, Container/Containment beziehung.
EMF generiert dir aus einer solchen Abstrakten Modelldefinition Java Klassen die solche Beziehungen automatisiert und hochperformt umsetzen.
Konkret bedeutet das, wenn du einem Human eine Family setzt, dann wird er automatisch der Family als Member gesetzt. Setzt du eine neue Familie, werden die alte und die neue Familie automatisch aktualisiert.
Diese explizit modellierten Beziehungen erlauben dann auch viele Performance Optimierungen.
So lässt sich in deinem Beispiel die Frage

family.getMembers().contains(human)

in O(1) anstatt O(n) bei einer normalen Liste, oder O(log(n)) bei einer Map beantworten.

 

[Miikku]

@0x7F800000:
Wow!

Das nenne ich mal einen Stammbaum
Echt cooles Teil! Aber sag, wo hast du das her? Ist dieses "UnionFind" etwas, dass man kennen sollte?
Und was genau daran hast du selber geschrieben? Nur die Kommentare oder auch was an dem Quellcode?
In der StandardLibrary kann ich nichts derartiges entdecken...
Jedenfalls vielen Dank, so werd ichs machen!
Mal sehen, ob es deine Performance-Versprechen hält

 

[0x7F800000]

Klingt ganz hilfreich, aber anhand des Wortes "Union-Find" fällt es mir nicht direkt wie Schuppen von den Augen... was genau ist das?

Es ist die Datenstruktur, mit der man partitionen einer menge verwaltet. Deine Menge ist die Menge aller Humans. Partitioniert sind sie in Familien, d.h. jeder Mensch gehört zu exakt einer Familie. Du willst ab und zu Familien vereinen: das geht mit union find in (praktisch) konstanter zeit, im krassen kontrast zu der O(familySize)-Umkopiererei der familien-Mitglieder. Das Aufzählen aller Familien-Mitglieder würde auch in O(familySize) funktionieren, wenn man ein paar zusätzliche kanten abspeichert, geht also auch in optimaler Zeit.

Regex's sind also nicht lahm? ???:L Ich dachte die währen so ungefähr das Beispiel für Langsamkeit schlechthin. Aber ehrlich gesagt hab ich auch keine bessere Idee :bahnhof:

Okay, sorry. Ich hab' dazu nie performance-benchmarks gebastelt, ich könnte es mir vorstellen, dass sie wirklich lahm sind. Dann könntest du dir aber immer noch per Hand einen kleinen "elementaren automaten" mit eins bis zwei for-schleifen und paar if-abfragen zusammenbauen, die eine fließkommazahl erkennt, aber jeglichen overhead der regex-machinerie vermeidet. Dazu musst du aber wissen, ob's das wirklich wert ist. Ich würd's mal mit regex versuchen, schaden kann's nicht.

Nicht so voreilig bitte, denn 1. meine ich bloß, dass man das ganze mit Sicherheit auch ohne Objekte und mit optimierten Routinen angehen kann (im übrigen kannst du die Geschwindigkeit von C und Java nicht vergleichen, weil sich objektorientierter Code auf C, objektlos wie es ist, kaum übertragen lässt)

man kann immer alles besser machen, nur muss man sich fragen, ob die 5% an performance-gewinn 10 Jahre deines Lebens wert sind

2. war das natürlich eine Übertreibung, mit der ich nur darauf hinweisen wollte, dass ich natürlich als einzelner Mensch keinen wirklich performanten Code schreiben kann und einfach keine Zeit habe, z.B. ArrayList's durch echte Arrays zu ersetzen.

zeig mir doch mal bitte, wie sehr das die Perfomance erhöht. Ich schätze mal ungefähr um 0%. falls nicht: installier dir die Server-version der JVM, die optimiert dir garantiert alles so brutalst weg, dass du niemals den overhead eines solchen methodenaufrufs messen kannst. Ich bin mir sehr sicher, dass es keinen vernünftigen Grund gibt, ArrayLists durch Arrays zu ersetzen: es kostet nur furchtbar viel Zeit und Nerven, und liefert am ende völlig unwartbaren Code, auf kosten von ein paar Prozent performance-Gewinn. Mit einem Umstieg von einem O(n) auf ein O(1) Algorithmus erreicht man erfahrungsgemäß tausendfach mehr zu einem viel kleineren Preis.

Also erstens halte ich mich selber für so einen Mathematiker (achtung, zweckmäßige Übertreibung )

Okay! Sieht man in Java Foren nicht so oft. Ich hab hier jedenfalls noch keinen gesehen (und ich zähle selbst auch nicht dazu). Zumindest kam mir das Abstraktionsniveau im ersten Beitrag (also: Menschen, Familien) in keiner Weise verdächtig vor, als dass ich gleich einen Mathematiker dahinter vermutet hätte

Das ist nötig, weil die Daten eines Menschen miteinander verzahnt sind und Durchschnittswerte da nicht mithalten können und einfach, weil es einem diesen Menschen näher bringt .

soll mir alles recht sein, solang die datenschützer das ganze für bedenkenlos halten.

Danke für den Vorschlag, aber das ist wohl eher ein Zusatz, der sich auch im Nachhinein noch installieren lässt, oder?

Öhm... Nö. Da müsste man das gesamte Projekt vom Fundament auf etwas anders aufrollen, einfach weil die Programmierung auf der GPU sich von der üblichen Programmiererei doch recht erheblich unterscheidet (vom gefühl her, vom Code her erst recht)

In die Berechnungen fießen statistische Daten ein, die sich mit der Zeit ändern. Außerdem müssen sie editierbar sein, für den Fall, dass man ein anderes als das voreingestellte Land simulieren möchte. Deshalb lese ich zum Programmstart ein paar CSV-Tabellen aus und cache sie.

Wenn du die daten beim Laden in vernünftiges Format bringst, ist alles ok. Wenn selbst das laden schon zu lange dauert, könntest du evtl die textdaten einlesen, und wieder binär abspeichern: dann würde man zumindest beim neuladen etwas Zeit sparen.

Nur das ich momentan noch bei jedem Zugriff auf Tabellendaten überprüfe, ob es sich um einen Text oder eine Zahl handelt ist nicht direkt verantwortbar aber weiter oben steht schon geschrieben, dass ich das langfristig gar nicht vor habe.

Okay. Dann kann ich ja ruhig schlafen^^

 

[0x7F800000]

Echt cooles Teil! Aber sag, wo hast du das her? [...]
Und was genau daran hast du selber geschrieben? Nur die Kommentare oder auch was an dem Quellcode?

Kommentare habe ich erst beim umkopieren ins Forum in eile hinzugefügt. Eigentlich habe ich daran jeden einzelnen Buchstaben geschrieben, kannst ja gerne sowas wie

/**
* Basic implementation of a UnionFind structure
*
* @author: 0x7F800000
*/

statt der unnützen Anweisung [c]package datastructures;[/c] vorne in der Datei einfügen^^ meinen echten namen würd ich heute aber nicht mehr drunterschreiben: Dokumentation ist auf deutsch und geht gegen alle konventionen, das ding extended keinerlei nützliche interfaces usw... Und ich weiß nicht mal, ob's überhaupt läuft^^ Ich hab's in den letzten drei jahren nicht gesehn, läuft das Ding überhaupt?

Ist dieses "UnionFind" etwas, dass man kennen sollte?

Nunja, ist schon einigermaßen bekannt, siehe da: Union-Find-Struktur ? Wikipedia. Das kommt in dem MST-Algo von Kruskal vor, deswegen werden die Informatiker-Drittsemestler damit öfters gequält.

In der StandardLibrary kann ich nichts derartiges entdecken...

Das ist noch nicht mal das schmerzvollste, ordentliche PriorityQueues mit decrease-Operation fehlen da auch, und das ist bei Dijkstra-Algo echt voll ätzend, vor allem weil Dijkstra-Algo so weit verbreitet ist.

Mal sehen, ob es deine Performance-Versprechen hält

Hey, erzähl du es mir^^ Ich hab in dem Buch gelesen, dass es schnell laufen sollte, ob's das wirklich tut: keine Ahnung! Hab's nur aus rein akademischen Interesse imlementiert, ich glaub sogar das war eine hausaufgabe... getestet habe ich es aber nie wirklich. Bin also genauso gespannt wie du Aber es hat wirklich eine asymptotisch viel bessere Laufzeit, es muss einfach schneller laufen.

 

[0x7F800000]

Ach übrigens: UnionFind heißt Union, weil da Scheidungen und unglückliche Todesfälle, die Familien wieder trennen, eigentlich nicht eingeplant sind. Man könnte sich evtl was überlegen, aber darauf ist das ding einfach nicht ausgelegt. Wollt' ich nur mal so beschied sagen, nicht dass du alles erstmal auf UnionFind umstellst, und dann doch noch Scheidungen reinbauen willst... Es würde mit union-find-ähnlicher struktur immer noch funktionieren, man müsste aber an der Pfadkompression schon ordentlich was abändern.