Furthering my obsession with FastArrayList... Attached is a new List implementation inspired by but faster than FastArrayList. From the javadoc:
Optimized thread-safe array-backed dynamic java.util.List implementation. The list is backed by a dynamic array; the array will grow automatically as more elements are added. This is just like java.util.ArrayList; unlike ArrayList, however, the array can also *shrink* after a remove operation. The internal array is always the same size as the list, saving memory. Read access to this list is not synchronized, but write access is. To pull this trick off, the state of the list is cloned during a write, the changes are applied to the clone, and then the clone replaces the list's state. Read operations use a local reference to the old state, and are not adversely affected by a write. This is similar to org.apache.commons.collections.FastArrayList. However, since the list is backed by a dynamic array, *many of the algorithms that alter the list already require that the state be cloned*. For instance, to remove an element, a new array must be allocated, and the elements from the old array (minus the removed object) must be copied to the new array. FastArrayList essentially performed the cloning twice: It first clones the entire list, and then performs the costly remove() operation on the copy. This implementation is optimized such that a new array is only allocated once. Assuming no monitor contention, this class should perform similarly to java.util.ArrayList, except for the add(Object) and set(int, Object) methods, which now perform in linear time. Sublists produced by this class are also thread-safe, and they are also not synchronized during a read operation. The iterators produced by this class are *not* "fail-fast". Read operations on an iterator *never* fail. A ConcurrentModificationExcepiton will only be raised if the original list is modified in some way and somebody subsequently attempts to modify it via the iterator. -Paul ============================================ Paul Jack Database Administrator San Francisco AIDS Foundation [EMAIL PROTECTED] (415)487-3075 "As far as we can discern, the sole purpose of human existence is to kindle a light of meaning in the darkness of mere being." --Carl Jung ============================================
OptimizedFastArrayList.java
Description: Binary data
-- To unsubscribe, e-mail: <mailto:[EMAIL PROTECTED]> For additional commands, e-mail: <mailto:[EMAIL PROTECTED]>
