minchau 2003/06/25 12:40:26
Modified: java/src/org/apache/xml/utils Trie.java
Log:
Sped up the Trie.get(String) method by about a factor of 2.
This was done by:
1) Not using string.charAt(i) when looping through the characters,
but rather using string.getChars(0, len, array, 0) and looping over the array.
2) Special casing the lookup in get(String key) for 0,1,2 or more characters
3) Putting the objects into the Trie considering the key as case insensitive
at the
time of putting the objects in, rather than at the time of taking them out.
4) Not using a try/catch in the search loop to test if an
index is out of bounds, but testing if the character value is less than 128.
Thanks to Gordon Chiu for optimization 1) and Henry Zongaro for 3) and 4).
Submitted by: Brian Minchau
Revision Changes Path
1.4 +81 -21 xml-xalan/java/src/org/apache/xml/utils/Trie.java
Index: Trie.java
===================================================================
RCS file: /home/cvs/xml-xalan/java/src/org/apache/xml/utils/Trie.java,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- Trie.java 27 Jan 2003 18:45:15 -0000 1.3
+++ Trie.java 25 Jun 2003 19:40:26 -0000 1.4
@@ -71,6 +71,9 @@
/** The root node of the tree. */
Node m_Root;
+
+ /** helper buffer to convert Strings to char arrays */
+ private char[] m_charBuffer = new char[0];
/**
* Construct the trie.
@@ -92,6 +95,12 @@
{
final int len = key.length();
+ if (len > m_charBuffer.length)
+ {
+ // make the biggest buffer ever needed in get(String)
+ m_charBuffer = new char[len];
+ }
+
Node node = m_Root;
for (int i = 0; i < len; i++)
@@ -107,11 +116,11 @@
for (; i < len; i++)
{
Node newNode = new Node();
-
+ // put this value into the tree with a case insensitive key
node.m_nextChar[Character.toUpperCase(key.charAt(i))] = newNode;
+ node.m_nextChar[Character.toLowerCase(key.charAt(i))] = newNode;
node = newNode;
}
-
break;
}
}
@@ -130,31 +139,82 @@
*
* @return The object that matches the key, or null.
*/
- public Object get(String key)
- {
+public Object get(final String key)
+{
final int len = key.length();
- Node node = m_Root;
- for (int i = 0; i < len; i++)
- {
- try
- {
- node = node.m_nextChar[Character.toUpperCase(key.charAt(i))];
- }
- catch (ArrayIndexOutOfBoundsException e)
- {
+ /* If the name is too long, we won't find it, this also keeps us
+ * from overflowing m_charBuffer
+ */
+ if (m_charBuffer.length < len)
+ return null;
- // the key is not 7-bit ASCII so we won't find it here
- node = null;
- }
+ Node node = m_Root;
+ switch (len) // optimize the look up based on the number of chars
+ {
+ // case 0 looks silly, but the generated bytecode runs
+ // faster for lookup of elements of length 2 with this in
+ // and a fair bit faster. Don't know why.
+ case 0 :
+ {
+ return null;
+ }
+
+ case 1 :
+ {
+ final char ch = key.charAt(0);
+ if (ch < ALPHA_SIZE)
+ {
+ node = node.m_nextChar[ch];
+ if (node != null)
+ return node.m_Value;
+ }
+ return null;
+ }
+// comment out case 2 because the default is faster
+// case 2 :
+// {
+// final char ch0 = key.charAt(0);
+// final char ch1 = key.charAt(1);
+// if (ch0 < ALPHA_SIZE && ch1 < ALPHA_SIZE)
+// {
+// node = node.m_nextChar[ch0];
+// if (node != null)
+// {
+//
+// if (ch1 < ALPHA_SIZE)
+// {
+// node = node.m_nextChar[ch1];
+// if (node != null)
+// return node.m_Value;
+// }
+// }
+// }
+// return null;
+// }
+ default :
+ {
+ key.getChars(0, len, m_charBuffer, 0);
+ // copy string into array
+ for (int i = 0; i < len; i++)
+ {
+ final char ch = m_charBuffer[i];
+ if (ALPHA_SIZE <= ch)
+ {
+ // the key is not 7-bit ASCII so we won't find it
here
+ return null;
+ }
+
+ node = node.m_nextChar[ch];
+ if (node == null)
+ return null;
+ }
- if (node == null)
- return null;
+ return node.m_Value;
+ }
}
-
- return node.m_Value;
- }
+}
/**
* <meta name="usage" content="internal"/>
---------------------------------------------------------------------
To unsubscribe, e-mail: [EMAIL PROTECTED]
For additional commands, e-mail: [EMAIL PROTECTED]
