xom-interest AT lists.ibiblio.org
Subject: XOM API for Processing XML with Java
List archive
Re: [XOM-interest] XOMTestCase.assertEquals() too slow
- From: Wolfgang Hoschek <wolfgang.hoschek AT mac.com>
- To: xom-interest AT lists.ibiblio.org
- Subject: Re: [XOM-interest] XOMTestCase.assertEquals() too slow
- Date: Thu, 25 Jan 2007 21:44:57 -0800
It's not clear why XOMTestCase.assertEquals() should be orders of
magnitude slower than parsing or serialization. All of these should
clearly be O(N) overall.
Turns out the comparison is implemented with an O(N^2) algorithm. It stems from the (unnecessary) stateless nature of getNonTextNode (expected, i) as used from XOMTestCase.compareChildren():
// now compare everything that isn't text using the original
// element objects
for (int i = 0; i < nonTextNodes; i++) {
Node expectedChild = getNonTextNode(expected, i);
Node actualChild = getNonTextNode(actual, i);
assertEquals(message, expectedChild, actualChild);
}
Because the 8 MB test document is wide (database dump style), with some 50000 elements under the root node this leads to > 10^9 scan steps. And here, we're lucky, as in practise, 8 MB is considered small...
Wolfgang.
-
[XOM-interest] XOMTestCase.assertEquals() too slow,
Wolfgang Hoschek, 01/25/2007
-
Re: [XOM-interest] XOMTestCase.assertEquals() too slow,
Wolfgang Hoschek, 01/26/2007
- Re: [XOM-interest] XOMTestCase.assertEquals() too slow, Wolfgang Hoschek, 01/26/2007
- Re: [XOM-interest] XOMTestCase.assertEquals() too slow, Elliotte Harold, 01/26/2007
-
Re: [XOM-interest] XOMTestCase.assertEquals() too slow,
Wolfgang Hoschek, 01/26/2007
Archive powered by MHonArc 2.6.24.