up vote 0 down vote favorite

So I'm working on project for my algorithms class that I'm currently taking. I'm doing some research online and see that some people are using an ArrayList<Integer> and some people are using an int array[]. My question is, what's better to use for a min heap and why. The project requires me to keep the top 10000 largest numbers in the list from a very large list of numbers

share|improve this question
up vote 2 down vote accepted

If you know the array size at compile time, using a bare int[] array is faster. Of course, the performance difference is probably negligible -- but the idea is that ArrayList is internally implemented as an Object[] array, so you're saving yourself that overhead, plus the overhead of dealing with Integer vs int.

share|improve this answer
    
Thanks for that. That's what I thought, since I know the size of the array needed it would be better to use a bare array. I was noticing that the array list was used for increasing the number of elements – kevorski Jul 30 '14 at 22:21
    
Yeah, I think the primary benefit is the add method that gives you a dynamically-resizing array (which you could do yourself, but which is a lot of boilerplate to write). If you know your max size, and you don't need any of the other ArrayList convenience methods, I don't think there is a compelling reason to use one. Also, please accept this answer if it solved your problem. – Patrick Collins Jul 30 '14 at 22:24
1  
I'm not sure *at all that an ArrayList<Integer> wraps an int[]. It most like wraps an Object[] in which ints are autoboxed. Which implies 1) more memory consuptions (you'll have the ints AND the pointer to them), and 2) an autoboxing performance penalty. Granted, both may be negligeable at small sizes. – GPI Jul 30 '14 at 22:24
    
@GPI Yes, I believe that's correct, my mistake. I'll edit. – Patrick Collins Jul 30 '14 at 22:25
    
@PatrickCollins, not to be pedantic, but it's no Integer[] either ! It could not work with Generics if that was the case... It will create an Object[] which contains Integer instances, which is not the same as Integer[] (although memory wise, it is, it is practically different) – GPI Jul 30 '14 at 22:29
up vote 1 down vote

An int[] will consume less memory than an ArrayList<Integer>. Part of that is simply the overhead which is added from an Integer which adds ~16 bytes per instance. This video goes through memory impact of various objects and collections in 32bit and 64bit jvms. At about the 9:30 mark it talks about memory associated with each object. At about the 11:15 mark it talks about how much memory various types (including Object references) take. For an int[], you have 1 Object (the int[]) and it will actually contain all of the individual int values as contiguous memory. For an ArrayList<Integer>, you have the ArrayList object, the Object[] object and all of the Integer objects. Additionally, the Object[] doesn't actually contain the Integer objects in contiguous memory, rather it contains object references in contiguous memory. The Integer objects themselves are elsewhere on the heap.

So the end result is that an ArrayList<Integer> requires ~6x the amount of memory as an int[]. The backing Object[] and the int[] take the same amount of memory (~40,000 bytes). The 10k Integer objects take ~20 bytes each for a total of 200,000 bytes. So the ArrayList will be a minimum of 240,000 bytes compared to the int[] at approximately 40,000 bytes.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.