Andrew Welch <andrew.j.we...@gmail.com> wrote on 06/09/2011 08:19:18 AM:
> Please respond to j-users > > >> Imagine a List class with a "length()" method. The first time the > >> length() method is called it walks the list and then stores the size > >> internally to a variable so that future calls to length() return this > >> size. > >> The data model hasn't changed, but the actual implementation state data > >> has. > >> This could possibly be not thread-safe. > >> XML trees are much more complex than this. > > > > ... and that's exactly what the NodeLists do in Xerces' DOM implementation > > for length(). Also, each time you call item() it stores the index and last > > Node returned, so that when you access n+1, it only needs to walk to the > > next sibling to return the result. Without that optimization the time spent > > iterating over the NodeList would be O(n^2) instead of linear. > > Ah ok, so there is some saved state going on. Next question, what > makes iterating over the list n-squared? It's a linked list which the user is indexing into. Without the cache you have to either start from the beginning or the end of the list every time to find the Node and over a for loop that ends up being n-squared. > thanks > -- > Andrew Welch > http://andrewjwelch.com > > --------------------------------------------------------------------- > To unsubscribe, e-mail: j-users-unsubscr...@xerces.apache.org > For additional commands, e-mail: j-users-h...@xerces.apache.org Thanks. Michael Glavassevich XML Parser Development IBM Toronto Lab E-mail: mrgla...@ca.ibm.com E-mail: mrgla...@apache.org
