suche optimale Datenstruktur

[Hm...]

Hi Leute,

ich habe mal wieder ein problem mit meiner Datenstruktur.

Mein Algo. soll folgendes machen:

Input: A,B,... (sind Ereignisse, codiert als int)
Output: (A,B,w),(A,B,f),(A,f),(A,w), ... (sind DataNodes)

Derzeitige Datenstruktur ist:

  
package persistentGraph;  
  
import java.util.ArrayList;  
import java.util.LinkedList;  
import java.util.Set;  
import java.util.Stack;  
  
public class NodeData {  
  
	public int id;  
	//public LinkedList<NodeData> list;  
	public Stack stack;  
	public Set set;//LinkedList<Integer> list;  
	public Tripel tripel;  
	  
	public NodeData(int id, Tripel tripel)  
	{  
		this.id = id;  
		this.stack = new Stack();  
		//this.set = new Set();  
		//selbstabbildung  
		//this.list.add(id);  
		this.tripel = tripel;  
	}  
}  
  

Bei einem input von 10.000 Ereignissen erhalte ich 100.000.000 DataNodes. Der Datanode soll zudem speichern, welche anderen DataNodes er erreichen kann.

Bisher wollte ich das einfach über einen Root DataNode und entsprechende nachfolge DataNodes speichern. Hierbei habe ich u.a. ArrayList, linkedlist und Stack ausprobiert - kann es sein dass Stacks eine sehr lange laufzeit haben im vergleich zu arraylist? (beim einfügen)

Habt ihr einen Hinweis, wie ich diese Datenstruktur verbessern köbnnte? würde ich nur mit den 10.000 ereignissen arbeiten, anstatt die 100.000.000 datanodes aufzubauen, wäre das ein großer performenc gewinn, allerdings hat jeder datanode ein individuelles tripel, dass ich dann auf andere art speichern müsste. ich hab mir auch überlegt die datanodes als xml zu speichern, damit der arbeitsspeicher nicht zusehr belastet wird, aber das kostet wahrscheinlich wieder viel laufzeit.

[Hm...]

der laufzeit-problemcode bei derzeitiger datenstruktur:

  
public static Stack<NodeData> constructStations(ArrayList<String> categorien)  
	{  
		Stack<NodeData> stations=new Stack();  
		Tripel root = new Tripel();  
		root.n=true;  
		int id=0;  
		stations.push(new NodeData(id,root));//zustands nichts gekauft zu haben  
		for(int i=0;i<categorien.size();i++)  
		{  
			id++;  
			root = new Tripel();  
			root.a=Integer.valueOf(categorien.get(i));  
			stations.push(new NodeData(id,root));  
			  
			id++;  
			root.n=true;  
			stations.push(new NodeData(id,root));  
			  
			for(int j=0;j<categorien.size();j++)  
			{  
				if(i<j)  
				{  
					id++;  
					root.b=Integer.valueOf(categorien.get(j));  
					stations.push(new NodeData(id,root));  
					  
					id++;  
					root.n=false;  
					stations.push(new NodeData(id,root));  
				}  
			}  
		}  
		  
		return stations;  
	}  

[Hm...]

hm...... eventuell habe ich die lösung gefunden, bitte korrigiert mich, wenn es noch besser geht.

ich erstelle die nodeData einfach ohne die stacks und speichere alle nodedata in einem stack so, dass ich mit einem bestimmten iterator alle nachfolge nodes herausfinden kann :)

[dedlfix]

Tach!

Bisher wollte ich das einfach über einen Root DataNode und entsprechende nachfolge DataNodes speichern. Hierbei habe ich u.a. ArrayList, linkedlist und Stack ausprobiert - kann es sein dass Stacks eine sehr lange laufzeit haben im vergleich zu arraylist? (beim einfügen)

Es bringt nicht viel (außer Erfahrung, wie es nicht geht), wild alle angebotenen Datenstrukturen auszuprobieren. Diese sind nicht per se austauschbar. Jede hat ihre speziellen Eingenschaften und Anwendungsgebiete. Mach dich doch erst einmal damit bekannt. Ein Stack ist ein Last-in-first-out-Speicher. Er ist für das zwischenzeitliche Ablegen von Werten gedacht. Prominentes Beispiel ist ein Programm mit Unterfunktionsaufrufen. Der Prozessor muss sich die Rücksprungadressen merken. Je tiefer in Subroutines abgestiegen wird, desto mehr Adressen lagern sich auf dem Stack ab. Bei jedem Beenden und Rücksprung wird wieder eine Adresse vom Stack entfernt. Vielleicht kann man auch über eienn Stack iterieren, oder Tonnen von Daten darauf ablegen, aber das ist nicht seine Aufgabe.

Habt ihr einen Hinweis, wie ich diese Datenstruktur verbessern köbnnte?

Viellleicht hilft es dir, dir in der realen Welt vorzustellen, wie du das Problem der Verwaltung von Dingen lösen müsstest. Allerdings darfst du dabei nicht zu klein denken. Ein Raum von Zimmergröße zum Ablegen von Zeug ist sicher recht einfach zu überblicken. Der Computer hat aber quasi den Platz einer Großstadt (unbebaut, zunächst). Da brauchst du dann doch schon eine Verwaltung um die Dinge wiederzufinden oder was immer du mit ihnen machen willst. Das sind deine Strukturen. Wenn die Dinge klein sind, werden sie direkt in der Struktur verwaltet (per value). Sind sie zu groß, kann nur eine Referenz abgelegt werden. Dann braucht es auch noch ein Platz-Management für die eigentlichen Dinge. Einiges macht Java im Hintergrund, aber es muss es tun und braucht dafür Zeit und Platz. Ist zum Beispiel deine Verwaltungsstruktur (von vorn herein) zu klein (angelegt), muss sie (immer wieder) vergrößert werden. Dabei muss man mit ihr auch mal an einen freien Platz umziehen. Wobei die eigentlichen Dinge dort bleiben, wo sie sind, es werden ja nur die Referenzen zu ihnen umgezogen. Wie auch immer, deine Strukturen sind jedenfalls ziemliche Spezialisten. Man kann sie mit artfremden Aufgaben betrauen, aber damit sind sie nicht glücklich und auch ziemlich ineffizient.

tl;dr: Informier dich über die Eigenschaften der Verwaltungsstrukturen und wie (in)effizient deine geplanten Zugriffe damit realisiert werden können.

dedlfix.

[Hm...]

danke, ich habe das problem gelöst indem ich ein arraylist mit allen nodedata erstellt habe und dazu einen iterator der die nachbarn eines nodes in der liste in O(1) pro nachbarn findet.

[Whouzuo]

Hi Leute,

ich habe mal wieder ein problem mit meiner Datenstruktur.

Mein Algo. soll folgendes machen:

Input: A,B,... (sind Ereignisse, codiert als int)
Output: (A,B,w),(A,B,f),(A,f),(A,w), ... (sind DataNodes)

Bitte was soll der tun? Hab nix verstanden.