Re: 'ArrayList' allowing more than 2G entries.
On 19.06.2009 18:57, markspace wrote:
Robert Klemme wrote:
Do you really need to fill the array to that size or do you need the
largish array in order to allow for long indexes? In the latter case
with sparse filling you might simply use a Map<Long,YourType>.
Interesting idea! Untested:
public class LongList<T> {
private static final int BUF_SIZE = 2048;
private HashMap<Long,T[]> store = new HashMap<Long,T[]>();
public T get( long index ) {
T[] buf = store.get(index/BUF_SIZE);
if( buf == null ) {
return null;
}
return buf[ (int)(index % BUF_SIZE) ];
}
public void put( long index, T value ) {
T[] buf = store.get(index/BUF_SIZE);
if( buf == null ) {
buf = (T[]) new Object[BUF_SIZE];
store.put( index/BUF_SIZE, buf);
}
buf[(int)(index%BUF_SIZE)] = value;
}
}
I rather meant to use the map directly. This is likely only feasible if
the total number of elements is less than maxint, i.e. a sparse collection.
Your approach is similar to some deque implementations I have seen in
C++ world. It can also be implemented with an ArrayList as first level
collection instead of a map. I would use the ArrayList as first level
because it is more memory efficient (the array in a HashMap is usually
larger than the number of elements because of the way hash maps are
built) while having similar performance characteristics.
Btw, I'd make the chunk size configurable (i.e. via a constructor
argument) because that makes your class more flexible.
But when reading your other posting it seems that for the file case
(i.e. non streaming) you should consider memory mapped IO.
http://java.sun.com/javase/6/docs/api/java/nio/MappedByteBuffer.html
We should probably learn more about your usage patterns. Are those
elements read in order of appearance? Do you frequently have to jump
back and forth? How often is each entry accessed? Is there a
particular locality to accesses etc.?
Also, I am wondering what you do in the streaming case: your huge array
is accessed by index. But for real streaming processing you can only
access elements sequentially or at most keep n elements in memory. If
you need full indexed access in the streaming case you will have to read
the whole stream anyway and store it somewhere so you could cover this
eventually by memory mapped IO as well.
Kind regards
robert
--
remember.guy do |as, often| as.you_can - without end
http://blog.rubybestpractices.com/