Skip to Content.
Sympa Menu

xom-interest - Re: [XOM-interest] Reducing indexOf() to constant time

xom-interest AT lists.ibiblio.org

Subject: XOM API for Processing XML with Java

List archive

Chronological Thread  
  • From: Wolfgang Hoschek <whoschek AT lbl.gov>
  • To: Wolfgang Hoschek <whoschek AT lbl.gov>
  • Cc: xom-interest AT lists.ibiblio.org
  • Subject: Re: [XOM-interest] Reducing indexOf() to constant time
  • Date: Tue, 25 Jan 2005 11:42:13 -0800

For completeness:

Time complexity would remain the same even when needing to update the index of other siblings on insert/remove, because insert/remove itself have the same time complexity. But still, it's probably not worth trying a variant of this patch.

Wolfgang.

Turns out I hit the SEND button too fast :-)

I was thinking on terms of a read-only XPath model. But the patch doesn't work for subsequent tree insertions/removals because the positions of all other siblings would need to updated as well, which is way too expensive. Intuitively, a HashMap{Node,int} would be too expensive as well :-(

Anyway, please ignore the patch...
Wolfgang.

On Jan 25, 2005, at 11:19 AM, Wolfgang Hoschek wrote:

To be considered when you get round to think about "building XOM for speed":

Here is a patch reducing ParentNode.indexOf(Node child) from linear to constant time.
Among other things, this can be used to speed up XPath operations such as sibling related axis navigations, document order checking and sorting (when using an effective compareOrder(A,B) algorithm that simulataneously walks towards the root from both nodes A and B to be compared for document order).

Memory consumption is increased by adding a "parentPosition" integer to each Node.
(In practise it would be sufficient to have the integer variable only stored in Element nodes, but for simplicity i'm omitting this variation).

The way it works is by updating the variable on insertion and reading it on indexOf. (There's actually no need to update it on removal because indexOf checks whether the child to be found has the right parent.)

Node.java:

private ParentNode parent = null;
int parentPosition = -1; // WH

ParentNode.java:

final void fastInsertChild(Node child, int position) {
if (children == null) children = new ArrayList(1);
if (position == children.size())
children.add(child);
else
children.add(position, child);
// children.add(position, child);
child.setParent(this);
child.parentPosition = position; // WH
}

public int indexOf(Node child) {

if (children == null) return -1;
if (child.getParent() != this) return -1;
// if (child.isNamespace()) return -1; // ??? Not sure
return child.parentPosition; // WH
// return children.indexOf(child);
}

Saxon/Nux have equivalent sibling position functionality in the NodeWrapper class but if such functionality would be available directly from the underlying XOM tree it would be even better.

[I have some more patches for XOMHandler and NonVerifyingXOMHandler that simultaneously improve memory consumption and performance when used in conjuntion with the stringified Text patch, but that's a story for later.]


---------------------------------------------------------------------- -
Wolfgang Hoschek | email: whoschek AT lbl.gov
Distributed Systems Department | phone: (415)-533-7610
Berkeley Laboratory | http://dsd.lbl.gov/~hoschek/
---------------------------------------------------------------------- -

_______________________________________________
XOM-interest mailing list
XOM-interest AT lists.ibiblio.org
http://lists.ibiblio.org/mailman/listinfo/xom-interest





Archive powered by MHonArc 2.6.24.

Top of Page