2

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?

Improve this question
2
  • Hey Dog I heard you like List of List so I answer with a List of Lists for your List needs! :P Commented Sep 18, 2012 at 13:56
  • Why are you mentioning linked lists in the title, while your question is really about arrays? Commented Sep 18, 2012 at 14:11

4 Answers 4

Reset to default
1

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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

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.
Improve this answer

Comments

0

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.

Improve this answer

1 Comment

I stated that in my question. But thanks for the reiteration. Why do you think that link made it better?
0

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).

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.