CODEWITHSUNDEEP
java
user1311286
user1311286

Reputation:

Linked list of Linked List of Integers, Java.

I first ran into my problem trying to create a int[][] of very large size (7k by 30k) for a dictionary gap list postings program. But alas I run out of space trying to allocate the array. How might I create a 2-d array of integers?

What I want is a list of list in which each list in the list is a list of integers. Here is a sample of my code.

Code: 

 static final int numberOfTerms = 6782;
 static final int numberOfLines = 30383;
 byte[][] countMatrix = new byte[numberOfLines][numberOfTerms];
 int[][] gapsMatrix = new int[numberOfLines][numberOfTerms]; // To big!!

This list of lists is going to be filled with integers that represent the gaps between two occurrences of the same word in a specific text. So in count matrix I hold a byte indicating whether a word is specified for a specified index. Then in the function I am creating right now I am going through the countMatrix and if I find a byte there, I take the current index minus the last found index and save that number in my 2D-array of integers which gives me the just the gaps between each of the same word in the text.

So how might I create a data structure I need to accomplish this?

Upvotes: 2

Views: 4098

Answers (4)

Lauri
Lauri

Reputation: 1899

So how might I create a data structure I need to accomplish this?

If is understand correctly, then you want to record gaps between same terms. Let us say, you have array of terms you need to analyze, then:

    String[] terms = ...;
    Map<String, List<Integer>> map = new TreeMap<String, <Integer>>();
    for (int i = 0; i < terms.length; i++) {
      String term = terms[i];
      List<Integer> positions = map.get(term);
      if (gaps == null) {
        positions = new ArrayList<Integer>();
      }
      positions.add(i);
      map.set(term, positions);
    }

Later you just look at the positions of each term and may calculate gaps between those. (You may integrate that gaps calculation into this code, but I leave it as exercise for you).

Upvotes: 0

HJW
HJW

Reputation: 23443

You simply have insufficient memory to do that.

http://www.javamex.com/tutorials/memory/array_memory_usage.shtml

Sorry I didn't make it clear but, it is unlikely that using another DS is going to change this.

Upvotes: 0

Peter Lawrey
Peter Lawrey

Reputation: 533492

To create an array you need to have enough memory to create it.

An int uses 4-bytes per values and an array uses at least N * M times that.

e.g. 4 * 30383 * 6782 is about 820 MB you need to have free to create this.

This is about $8 worth of memory so this should be a big problem unless you don't have this much or you set your maximum memory too low.

I would increase your maximum memory by 1 GB at least and it should work.

Alternatives include

  • use a smaller size e.g. char or short or byte which is 2-4 x smaller.
  • use off heap memory such as a memory mapped file. This doesn't use much heap but does use disk space which is usually cheaper.
  • increase your maximum memory size.

Upvotes: 1

Amit Deshpande
Amit Deshpande

Reputation: 19185

I don't know whether this will work for you but you can try Sparse Matrix as option if you want to stick to Array. There are several other options.Map, List ,Weak reference Collections etc

Upvotes: 1

Related Questions