android.util.SparseArray space time complexity properties

Showing 1-4 of 4 messages
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*:
http://developer.android.com/reference/android/util/SparseArray.html

However i think the documentation is not entirely correct and needs
more info:
When reviewing the sourcecode of SparseArray and comparing it with the
HashMap i come to the following conclusion

Source code of Sparse Array:
http://android.git.kernel.org/?p=platform/frameworks/base.git;a=blob_plain;f=core/java/android/util/SparseArray.java;hb=HEAD

For SpareArray:
Time complexity for reads and writes on a map of size N is log2(N) +
1,

However the time complexity for a HashMap of size N is C*N (where C is
a constant)
(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
valuable :)
--
Romain Guy
Android framework engineer
roma...@android.com

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. :)--
Dianne Hackborn
Android framework engineer
hac...@android.com

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