|android.util.SparseArray space time complexity properties||TjerkW||5/19/09 3:04 PM|
I need a map from int to certain objects. I wanted to use the HashMap,
but in the documentation of SparseArray
it says that SparseArray is intented to be *more efficient*:
However i think the documentation is not entirely correct and needs
When reviewing the sourcecode of SparseArray and comparing it with the
HashMap i come to the following conclusion
Source code of Sparse Array:
Time complexity for reads and writes on a map of size N is log2(N) +
However the time complexity for a HashMap of size N is C*N (where C is
(according to the javadoc http://java.sun.com/j2se/1.4.2/docs/api/java/util/HashMap.html)
So maybe SparseArray is more efficient with respect to space
complexity it is not for time complexity.
So for programs that need high performance a HashMap may be better.
At least thats what i think. Am i right? Am i wrong?
I need a very fast implementation for my game :-)
|Re: [android-developers] android.util.SparseArray space time complexity properties||Romain Guy||5/19/09 4:47 PM|
HashMap can indeed be faster than SparseArray. However, and this is
very important, SparseArray does not require boxing/unboxing of
primitive types which prevents allocations and thus prevents the GC to
stop your games for hundreds of milliseconds. That is much more
Android framework engineer
Note: please don't send private questions to me, as I don't have time
to provide private support. All such questions should be posted on
public forums, where I and others can see and answer them
|Re: [android-developers] Re: android.util.SparseArray space time complexity properties||Dianne Hackborn||5/19/09 5:13 PM|
Also for most reasonable data structures, especially on a mobile phone, the difference between O(N) and O(log(N)) is just not that much. In fact, I would argue that for most typical uses it will be far made up for by the much less complicated code and internal data structure (another advantage of SparseArray -- it doesn't need to allocate an extra entry object for every mapping it contains, nor resize a hash table as the amount of items changes).
Then again, I've always been very partial to ordered arrays over hash maps. :)--
Android framework engineer
Note: please don't send private questions to me, as I don't have time to provide private support, and so won't reply to such e-mails. All such questions should be posted on public forums, where I and others can see and answer them.
|Re: [android-developers] Re: android.util.SparseArray space time complexity properties||TjerkW||5/20/09 12:35 AM|
I will write some test to check wich one is faster,
i understand that the unboxing/boxing is not really fast.
Thanks for the info!
2009/5/20 Romain Guy <roma...@google.com>
Tjerk Wolterink @ GMail