Java: memory efficient storing of arrays of integers

Question

Premise: This problem might be already known, and I might be using the wrong wording, please refer me elsewhere if this is the case.

Quick Problem Overview: I have to store a high number of arrays of integers in order to avoid duplication. I am doing the following:

LinkedList<int[]> ArraysAlreadyUsed;

Upon using an array, I add it to the list. Before using an array I see if it is in the list. Since I need to use many high dimensional arrays I run into memory issues.

Question: What is a good/the best way of doing this in order to minimize the amount of memory occupied? Is there a way to represent such arrays with a hash string? And would this be better?

LinkedList is a poor choice both in terms of memory overhead and iteration. Use ArrayList instead. However, an exhaustive linear search for an array seems like a bad idea to begin with. — Marko Topolnik
– Marko Topolnik, Commented Apr 1, 2015 at 13:03
I wasnt able to understand your problem clearly, but seems like you can solve your problem if you give your throughts on using hashmap to your situation — Ravikiran butti
– Ravikiran butti, Commented Apr 1, 2015 at 13:04
@rave763 How would I use hashmap in this case? what would I map my arrays of integer to? — k88074
– k88074, Commented Apr 1, 2015 at 13:08
Let me know if my understand of your situation is right , have a few arrays with various numbers ie [1,2,3] , [2,3,4] , [1,2,3]. You want a solution to whether at a given time you have already processed thaat array .. i.e in above scenario u have already used [1,2,3] so you wouldnt process it again — Ravikiran butti
– Ravikiran butti, Commented Apr 1, 2015 at 13:10
ok cool : I dnt knw whether it is the best solution in the world.. But here is how i would have done it. I would have first designed an algorithm to generate the key. Example myAlgorithm add the values in the array. so my hashmap entries will be (6,[1,2,3]) , (9, [2,3,4]) now when the third array is reached i will do a get(6). it will retrive me an array and then i will make a check if my array matches to the one in the hashmap. although is suggest ur key generation algorith should be very effiecent to avoid large key collosion... Happy coding — Ravikiran butti
– Ravikiran butti, Commented Apr 1, 2015 at 13:18

assylias · Accepted Answer · 2015-04-01 13:18:04Z

It may make sense to create a wrapper that implements equals and hashcode so that you can place the arrays in a Set for O(1) contains/add. Something like:

public class IntArray {
  private final int[] array;
  private final int hash;

  public IntArray(int[] array) {
    this.array = array;
    this.hash = Arrays.hashCode(this.array); //cache hashcode for better performance
  }

  @Override
  public int hashCode() {
    return hash;
  }

  @Override
  public boolean equals(Object obj) {
    if (obj == null) return false;
    if (getClass() != obj.getClass()) return false;
    final IntArray other = (IntArray) obj;
    return Arrays.equals(this.array, other.array);
  }
}

You can then simply use a set:

Set<IntArray> arrays = new HashSet<> ();

That will create a small overhead (guestimate less than 20 bytes per wrapper) but will perform much better than your LinkedList.

If memory is your only concern then you could go for an int[][] but that will be more painful...

Davide Lorenzo MARINO · Accepted Answer · 2015-04-01 13:09:02Z

0

If you need to check the presence of an element in a data structure the best solution is to use a Map. So use an HashMap.

Retrieve of elements happens in O(1). In a list (LinkedList or ArrayList) the search happens in O(n).

A linked list is also a poor choice in term of memory occupation. Infact for each element you have a reference to the previous element and a reference to the next element.

Just in term of memory occupations the best solution is using an array of int (not an ArrayList) with a reference to the last inserted id.

answered Apr 1, 2015 at 13:09

Davide Lorenzo MARINO

27k4 gold badges45 silver badges58 bronze badges

Comments

Shane Voisard · Accepted Answer · 2015-04-01 17:16:58Z

0

Using a BitSet in place of int[] might reduce the memory footprint.

edited Apr 1, 2015 at 17:16

answered Apr 1, 2015 at 13:12

Shane Voisard

1,1458 silver badges12 bronze badges

Collectives™ on Stack Overflow

Java: memory efficient storing of arrays of integers

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related