Re: Can arrays be parameters to generics
On Sun, 3 Aug 2008, Christian wrote:
Tom Anderson schrieb:
On Sat, 2 Aug 2008, Christian wrote:
Daniel Pitts schrieb:
puzzlecracker wrote:
Item 25 of Effective Java 2nd Edition (Bloch): Prefer lists to arrays.
Lists are a higher level abstraction, and therefor "easier" to work
with.
and slower to work with...
Premature optimization is the root of all evil.
Lists are marginally slower to work with than arrays, but who cares if
your program is fast when it doesn't work correctly?
Until now the only reason to optimize collections away for arrays was
never the speed but allways the RAM usage for me.
And how exactly do you search or insert into this array?
Searching with binary search ... as implemented in Arrays class..
inserting creating a new array using data of the binarys search shifting all
entrys afterwards..
Yikes. That sounds reasonable for lookup - it's O(log N), rather than a
hashset's O(1), but still not too bad. But insertion will be very slow
indeed.
Yes it is slower. Bit if the arrays/sets come en masse and are rather
small , may be less than 500 entrys one won't notice it that much.
As Lew keeps pointing out, if we're talking about small tables, then space
efficiency doesn't matter too much.
This example I made is really only important to show that even if
Collections are superior usually. My experience till now was that the
reason to choose arrays over Collection (no matter if set or list or
map) were always due to storage. There has never ever been a problem
with speed for me due to collections.
I would agree that the space overhead in a HashSet is excessive. It would
be good to have a leaner one that doesn't just wrap a HashMap, and so
saves a word per entry. It would also be good to have a very
space-efficient SortedArraySet, like the way you manage arrays, for when
you have a huge structure that is infrequently updated.
Or perhaps a HashMap/HashSet that uses linear probing rather than
collision lists, which would save even more memory. It is even possible to
do away with the Entry objects altogether in that case, although only by
giving up cacheing of the hashcode (which is actually not such a big deal
if your keys cache the hashcode anyway, as strings do).
tom
--
unstable orbits in the space of lies