float, double, BigDecimal

[miasma]

Hallo,

ich will in einer Baumstruktur mit Pointern zu den Nachbarknoten, zum Vaterknoten und ersten Kindknoten einfach rausfinden können welcher Kindknoten wenn man diese vergleicht jetzt in einem levelorder durchlauf vor dem anderen Knoten kommt.

Dazu dachte ich mir kann ich ja anfänglich ganz einfach numerisch durchnummerieren von 0 bis n. Werden dann Subbäume irgendwo eingefügt, bspw. als erstes Kind vom Vaterknoten so kann ich ja einfach erster Kindknoten falls vorhanden -1 machen, falls nicht 0 zuweisen. Wenn ich ganz rechts einen Kindknoten einfügen will (als letztes Kind) einfach die Zahl vom linken Nachbarknoten nehmen + 1. Wenn ich Kindknoten dazwischen einfügen will dann kann ich ja einfach die Ordnungszahl vom linken nachbarn + rechter Nachbar und durch 2 teilen.

Jetzt zu meiner Frage. Prinzipiell würde es doch reichen dazu eine Variable vom Typ double zu verwenden, aber wahrscheinlich hab ich dann schon Rundungsfehler. Wahrscheinlich wäre deshalb BigDecimal am besten geeignet?

Zudem eine dumme Frage, wie kriege ich eine Byte-Array represäntation von einer BigDecimal Instanz um diese zu serialisieren? Ich nehme mal an irgendwie aufteilen in vor-komma und nach-komma Stellen.

BTW: Nochmal zur eigentlichen Idee, ich will damit einfach bestimmen können welcher Kindknoten wenn man diese vergleicht in der Ordnung oder in einem Levelorder Durchlauf vorher kommt. Momentan nutze ich dazu noch:

	public int getSiblingPosition() {
		int index = 0;
		while (mNodeReadTrx.hasLeftSibling()) {
			mNodeReadTrx.moveToLeftSibling();
			index++;
		}
		return index;
	}

was natürlich sehr ineffizient ist, weil es sich um eine persistente (also auf Festplatte/Flash-disc gespeicherte) Baumstruktur handelt und somit die Knoten möglicherweise erst in den Hauptspeicher geladen werden müssen. Bei sehr vielen Vergleichen macht das wahrscheinlich einen deutlichen Unterschied, ob ich dann eine relative positionsangabe in den Knoten selbst speichere oder nicht. D.h. der Rückgabewert muss kein int sein. Im Prinzip will ich nur in der Lage sein beim Vergleich dann -1 oder 1 zurückzugeben je nachdem welcher der beiden verglichenen Knoten in der Kindordnung vorher kommt.

Letztendlich habe ich da bisher halt: return p1.getSiblingPosition() - p2.getSiblingPosition();

Viele Grüße,
Johannes

 

[Ark]

Was genau willst du denn mit dieser Baumstruktur bezwecken? Also wo und wie soll sie eingesetzt werden? Warum sollte sie genau so sein, wie du sie dir vorstellst?

double und float sind da vollkommen ungeeignet, je nach Ebene kann da ganz schnell z.B. schon nach dem zehnten eingefügten Knoten Schluss sein. Und BigDecimal geht da auch an der Problematik vorbei: Wahrscheinlicher wirst du alle Geschwister eingelesen haben, bevor die BigDecimal-Berechnungen durchgeführt wurden. Und weniger Speicher würde das Einlesen der Geschwister vermutlich auch benötigen.

Ark

 

[miasma]

Naja, um die document order Bestimmung für XQuery/XPath-Anfragen zu beschleuningen. In den allermeißten Fällen handelt es sich wohl um Knoten mit dem selben Parent-knoten die verglichen werden müssen (d.h. welcher Knoten in einem preorder-Durchlauf vorher kommen würde). Die meißten XML-Datenbanksysteme weißen deshalb entweder Dewey-/ORDPATH-IDs zu oder verwenden eine pre/post bzw. davon abgeleitete Kodierungsverfahren.

Ich weise die Knoten-IDs zunächst in einem preorder-Durchlauf zu, d.h. die meißten Knoten können mit Hilfe der IDs direkt verglichen werden. Später eingefügte Knoten (es wird einfach immer max-nodeID + 1 als nächstes zugewießen) brechen aber die preorder Nummerierung auf bzw. für genau diese Knoten kann man die nodeIDs dann nicht mehr direkt vergleichen. Prinzipiell suche ich da dann wie in Saxon den lowest common ancestor und muss dann noch schauen welcher der beiden Knoten mit übereinstimmendem Parent-Knoten zuerst kommt.

 

[miasma]

BTW: In Saxon hat man bspw. aber die sibling-Position direkt zum Abfragen weil parent-Knoten ein Array mit allen Kindknoten beinhalten.

 

[miasma]

Wahrscheinlich könnte man auch eine Art Dewey-/ORDPATH-ID verwenden aber die parent/child Beziehung weglassen, also nur die Kindordnung mit der gleichen Idee abspeichern, hmm (ich will auch moves- und inserts zwischen vater- und kind-Knoten effizient ohne jegliches relabeling unterstützen, deshalb darf in den labels keine parent/child Beziehung drin sein).

 

[Bernd Hohmann]

Zudem eine dumme Frage, wie kriege ich eine Byte-Array represäntation von einer BigDecimal Instanz um diese zu serialisieren?

BigDecimal ist direkt serialisierbar (bzw. hat seinen eigenen Wrapper eingebaut).

Wenn Du es als byte-Array haben möchtest, dann über diesen Umweg:

		ByteArrayOutputStream baos = new ByteArrayOutputStream();
		ObjectOutputStream oos = new ObjectOutputStream(baos);
		oos.writeObject(OBJECT);
		byte buffer[] = baos.toByteArray();
		oos.close();
		baos.close();

Bernd