Files vs Arrays?

[Sam Bluesman]

Hi.

I have written a program which takes in data from text files that can be up to 5Mb. At the moment, the program is slow and i am getting the memory heap problem and I think its because im storing a lot of the data in arrays. I was wondering, would it be better to store data in files that can then be read rather than storing everything in arrays which meant they all have to be kept in memory at the same time?

Many thanks

[Michael Morris]

...would it be better to store data in files that can then be read rather than storing everything in arrays..

I doubt the arrays are what's causing the problem. My guess is you have an inefficient algorithm that is retrieving data from the arrays. File I/O for the most part is going to be much slower than anything stored on the heap and it seems somewhat strange to read the data in from a file, store it into another file and retrieve it again (if that's what you are implying).

How much heap are you using? Are the arrays multi-dimensional?

If your problem is an ineficient algorithm, you may want to consider using Maps instead of arrays, but make sure that the hashes for your keys are efficient.

[Sam Bluesman]

Yes the arrays become multidimensional. Using one of the input files, the arrays would be 20000 by 20000.

Having put System.out.println("Test") statements in my code I find that the program crashes when declaring a 2D array of that size...

How do I work out what heap I am using?
[ May 27, 2007: Message edited by: Sam Bluesman ]

[Jim Yingst]

Um, yes. A byte[][] of that size would take up 400 Mb or so, and other data types would take up more memory. So yes, that's likely to give you memory problems, and a file structure could well be better for you. Or maybe there's another way to handle you data, such as with sparse arrays (since there were only 5 Mb of data initially). What can you tell use about the data in the file? What does it represent?

[Sam Bluesman]

Hi there. Basically, the file has the following format:

Object1 Object2 Stat

and so would have contents similar to:

AAAA BAAA 0.1
AAAA CAAA 0.2
AAAA DAAA 0.3
BAAA CAAA 0.4
BAAA DAAA 0.5
CAAA DAAA 0.6

...except imagine thousands of text lines like this

This is then put into a 2d array as follows

      AAAA BAAA CAAA DAAA
AAAA  0    0.1  0.2  0.3
BAAA  0.1  0    0.4  0.5
CAAA  0.2  0.4  0    0.6
DAAA  0.3  0.5  0.6  0

..except this would be obvisouly bigger than the data given above

BTW, what are sparse arrays?

[Jim Yingst]

So, the file lines you're showing there look like they take about 14-15 bytes each, assuming 1 byte per character. More if the decimal values are longer. So a 5 Mb file would have a little under 40,000 lines, at most. A 20,000 x 20,000 grid has 400,000,000 positions in it. So about 99.99% of the grid is filled with zeroes, the default value. Is that right? A conventional 2-D array (or array of arrays, in Java) is taking up a large amount of memory that isn't really being used for anything.

This is exactly the sort of problem sparse arrays are designed for. Basically, they're alternate storage structures designed to handle arrays (or matrices) in which the majority of the elements are zero (or some other default value). However there is no one implementation strategy for these; there are several. You could spend some time googling "sparse arrays" or maybe "java sparse arrays" for more info and examples. You may also want to replace "arrays" with "matrices".

One relatively simple way to implement a sparse array in Java is to create a Map<Point,Double>. Each set of x-y coordinates with a nonzero value would get its own Point object, and then the value would be put in a Double object, and the pair would be put in the Map. That may sound inefficient, but it's way less inefficient than what you have now. At least in terms of memory. Whether or not it works well for you is another question, which may depend on what sort of processing you need to do. For some types of processing, you may benefit from having a TreeMap or NavigableMp rather than HashMap. But that's hard to say without a lot more analysis. I think a HashMap<Point, Double> would not be too difficult to make. You could try it an see how well it works, then analyze further if improvements are unnecessary.

Or you could make one big file, read with a RandomAccessFile. Or FileChannel could be faster if you're willing to do extra work to figure out how to use it effectively here. Again, it shouldn't be too difficult to try something like this with RAF, and see how fast it is. If it's not fast enough, you may well be able to improve performance by reading a chunk of the file into memory all at once, processing all that, and then moving on to the next chunk.

Can you tell us more about the type of processing you need to do with this data? What does the data represent? Can you consider each data element one at a time, or do the calculations involve several neighboring elements at once? Here is where there may be opportunities for clever tricks to avoid needing to have everything in memory at once. Maybe.
[ May 27, 2007: Message edited by: Jim Yingst ]

[Sam Bluesman]

Thanks for the advice. I've just learnt (from my superiors) that the format of the file will NOT be as said above!

It will be:

AAAA BAAA DataValue DataValue DataValue DataValue 0.1
AAAA CAAA DataValue DataValue DataValue DateValue 0.2
AAAA DAAA DataValue DataValue DataValue DateValue 0.3
BAAA CAAA DataValue DataValue DataValue DateValue 0.4
BAAA DAAA DataValue DataValue DataValue DateValue 0.5
CAAA DAAA DataValue DataValue DataValue DateValue 0.6

The above matrix that needs to be produced still stands.

As a general background and purpose of this program...

The file contains object identifiers and, as well as other data values, a correlation statistic between them.

Taking the file, the data should be represented as a matrix of correlations. It's almost like having a set of places (instead of objects) and the distances between them (instead of the correlation stats) and the idea is to put them into something similar to a SQUARE road distance chart. This MUST be placed in a text file so that it can be put into the statistical program R....or at worst an Excel worksheet, but I have absolutely no idea how to do this.

Thanks again
[ May 27, 2007: Message edited by: Sam Bluesman ]

[Jim Yingst]

hm. Well, so far I don't really have any idea what these values mean, or what the processing you're doing is like. You should probably just ignore my comments about sparse arrays unless you can determine that the vast majority of entries in the array are zero.

Is there a way that you can read the original file data into memory, and then generate the 20000x20000 array one row at a time? (Or even, one element at a time.) Is there any reason you need the whole thing in memory at once? If it's possible to calculate each value one at a time, I'd do that, and write the results to a file as you go.

[William Brogden]

Is there a way that you can read the original file data into memory,

That sounds like the right track to me. Your 5MB file will only take 10MB as a char[]. One pass through that will let you locate all the line starts as an int[] of pointers which will enable you to recover the contents of any line at memory speed. As Jim suggests you can then work on the problem in chunks of a reasonable size.

Bill

[Sam Bluesman]

Sorry guys...im not exactly sure you're trying to say...

[Charles Lyons]

What's being said is that perhaps there's a way to process the data in smaller chunks so you don't have to read in the entire set of data into an array at once; this is a bit like encoding/decoding an audio file: you do it block by block, not altogether. Could you elaborate more on the algorithm you're using to process the data? If you can be more specific (e.g. by giving an outline of the algorithm), it might help.

Alternatively, is there any reason why your file needs to be in text format? If it was a binary structure instead, you could use a RandomAccessFile to read/write and seek directly in the file, possibly also using a RAM buffer (array) to increase intermediate calculation performance. Also, a binary file would mean you don't have to parse the textual contents into primitive numbers (which is an expensive operation), and your file sizes would also be much reduced.
[ May 28, 2007: Message edited by: Charles Lyons ]

[Jim Yingst]

We are suggesting that it may be possible to solve this without ever creating a 20000 x 20000 array. Something like this:

read input file & store in memory
 
for (int i = 0; i < 20000; i++) {
    for (int j = 0; j < 20000; j++) {
        calculate the value that should be at position (i,j)
        write it to file
    }
}

I have no idea if this is possible for your problem, because I have no idea how you are supposed to calculate your results. But many problems are possible to solve in a manner similar to this. If you don't need to create the 20000 x 20000 array, then don't.

[Jim Yingst]

[Charles]: Alternatively, is there any reason why your file needs to be in text format? If it was a binary structure instead, you could use a RandomAccessFile to read/write and seek directly in the file, possibly also using a RAM buffer (array) to increase intermediate calculations.

Yes, when I talked about using RandomAccessFile in place of the 20000 x 20000 array earlier, I should have said you'd write and read the values using binary methods like writeDouble() and readDouble(), not printing the results as text. Even if you eventually need a text file, you could use a large binary file as an intermediate format.

Sam: it's very difficult to give good advice here without a better understanding of what the data in the input file means, and what the output file means. What do AAAA, BAAA refer to? What are the 0.1, 0.2, etc? And what in the world are the "DataValue" things?
[ May 28, 2007: Message edited by: Jim Yingst ]

[Sam Bluesman]

OK Guys. I can see that you're trying to help but don't have much to go on: So..... here goes:

Background:

Single Nucleotide Polymorphisms (SNPs) are single base variants within our DNA. For example, where some might have an 'A' at a particular location in their DNA, others may have a 'G'

The file I want to take in has a list of SNPs and the correlations between other SNPs in a region of DNA. It contains the locations of the SNPs, the population from which the data came from e.g. USA, and actual names of the SNPs and the correlation between the two SNPs in that row; it has the following format:

SNP1Location  SNP2Location  DataPopulationOrigin  SNP1Name  SNP2Name  AmountOfCrossover CORRELATIONStatistic

I have chosen to use the locations of the two snps as their identifiers purely randomly, of course I could have chosen the Names...but there we go.

As an example, here is an example of some REAL data, but VERY much condensed - there are actually thousands of differnt SNPs in each file.

Line1 about the file
Line2 gives column headings
21876767 21880326 CEU rs4352938 rs7865071 1 0.959 
21876767 21884299 CEU rs4352938 rs7389140 1 0.691 
21880326 21884299 CEU rs7865071 rs7389140 1 0.661 

I would like to be able to get this into the following form:

         21876767 21880326 21884299
21876767 0        0.041    0.309
21880326 0.041    0        0.339 
21884299 0.309    0.339    0

Note 1) The correlations have to be taken away from 1, so what would have been 0.959 would be 0.041
Note 2) The matrix above is represented neatly for your viewing. A space beween each SNP location, statistic etc. would be the aim.

Here is an outline of my program:

Class 1: Program.java
 
        1. Ask for SNP input file (shown above)
 
        2. Pass the file name to FileReader.java class
 
 
Class 2: FileReader.java
 
        1.  Open the the file using the file name given
 
        1.2 Count number of lines, then minus 2 to disregard first two lines. Store as noLines.
 
        1.3 Close file
 
 
        2.  Open the file again
 
        2.1 Create three arrays:
            String[] sNP1PosArray      = new String[noLines];
            String[] sNP2PosArray      = new String[noLines];
     Double[] initialSNPLDArray = new Double[noLines];
 
        2.2 Fill the arrays using the following algorithm:
 
            // skip the first two lines
            ldData = MyFile.readLine();
     ldData = MyFile.readLine();
 
            for (counter=0; counter<noLines; counter++){
       ldData = MyFile.readLine();
               String[] ldDataArray = ldData.split(" ");
       sNP1PosArray[counter] = ldDataArray[0];
       sNP2PosArray[counter] = ldDataArray[1];
       initialSNPLDArray[counter] = Double.parseDouble(ldDataArray[6]);
     } 
    
2.3 Close the file
 
        2.4 Create a new array:
            Double[] sNPLDArray = new Double[noLines];
            and from 1.000 take each of the values in initialSNPLDArray
 
        2.5 Pass noLDLines, sNP1PosArray, sNP2PosArray, sNPLDArray to   
            the MatrixCreator.java class
 
Class 3: MatrixCreator.java
 
        3.1 Set up two dimensional array that will contain the matrix
            String[][] correlationMatrix = new String[noLines+1][noLines+1];
            Note: 1 is added so that the snp identifers can go along the top and down the side
 
        3.2 Generate an array to store the list of unique SNP identifiers
        String[] uniqueSNPIdentifiers = new String[noLines];
 
        3.3 Find the unique identifiers by using the following algorithm
 
 // Look through sNP1Pos array first
 for (counter=0; counter<noLines; counter++)
 {
    currentID = sNP1PosArray[counter];
    foundFlag = 0;
    for (counter2 = 0;counter2<noLines;counter2++)
    {
       if (currentID.equals(uniqueSNPIdentifiers[counter2]))
       {
          foundFlag++;
       }
    }
    if (foundFlag == 0)
    {
       uniqueSNPIdentifiers[index] = currentID;
       index++;
    }
        }
 
 // Look through sNP2Pos array second
 for (counter=0; counter<noLines; counter++)
 {
    currentID = sNP2PosArray[counter];
    foundFlag = 0;
    for (counter2 = 0;counter2<noLines;counter2++)
    {
       if (currentID.equals(uniqueSNPIdentifiers[counter2]))
       {
          foundFlag++;
       }
    }
    if (foundFlag == 0)
    {
       uniqueSNPIdentifiers[index] = currentID;
       index++;
    }
        }
 
        // Unique SNP positions now found
 
        3.4 Now create a full list of all SNPs and their correlations with 
            other SNPs. This means that data will be repeated such that:
            
            21876767 21880326 0.041 AND 21880326 21876767 0.041 
 
            will be stated, unlike in the file above
 
    String[] completeSNPList1 = new String[noLines*noLines];
     String[] completeSNPList2 = new String[noLines*noLines];
     Double[] completeLDList   = new Double[noLines*noLines];
 
    // Set up first column of the three above
    index=0;
    for(counter=0; counter<noLines; counter++)
    {
       currentID = uniqueSNPIdentifiers[counter];
      for(counter2=0; counter2<noLines; counter2++)
      {
         completeSNPList1[counter2+index] = currentID;
      }
      index = index+noLines;
    }
 
           // Set up second column of the three above
    index = 0;
    for(counter=0; counter<noLines; counter++)
    {
      for(counter2=0; counter2<noLines; counter2++)
      {
  currentID = uniqueSNPIdentifiers[counter2];
 completeSNPList2[counter2+index] = currentID;
      }
      index=index+noLines;
    }
 
 
            //Now put the right number in the same index that corresponds  
 to the two snps sotored in completeSNPList1 and completeSNPList2
 
 
 for(counter=0; counter<completeSNPList1.length;counter++)
        {
    if(completeSNPList1[counter].equals(completeSNPList2[counter]))
           {
        completeLDList[counter] = 0.000;
    }else{
 
    for(counter2=0; counter2<noLDLines; counter2++)
           {
       if(sNP1NameArray[counter2].equals(completeSNPList1[counter])
  && sNP2NameArray[counter2].equals(completeSNPList2[counter])){
    
 completeLDList[counter]=sNPLDArray[counter2];
    
       }else if(sNP2NameArray[counter2].equals(completeSNPList1     
                       [counter]) && sNP1NameArray[counter2].equals
                       (completeSNPList2[counter])){
             
                    completeLDList[counter] = sNPLDArray[counter2];
       }
                }
     }
 }
 
 
        3.5 Now form the matrix using the String[][] correlationMatrix
 
//start with top right which should just be a space
correlationMatrix[0][0] = " ";

 //Input SNP identifiers along top row
 for(counter=1; counter<correlationMatrix.length; counter++)
        {
    correlationMatrix[counter][0]=uniqueSNPIdentifiers[counter-1];
 }
 
 //Input SNP identifiers down first column
 for(counter=1; counter<correlationMatrix.length; counter++)
        {
    correlationMatrix[0][counter]=uniqueSNPIdentifiers[counter-1];
 }   
 
        // Now input the values
 index = 0;
 for(counter=1; counter<correlationMatrix.length; counter++)
 {
    for(counter2=1; counter2<correlationMatrix.length; counter2++)
    {
       correlationMatrix[counter][counter2] = Double.toString(completeLDList[index]);
       index++;
     }
 }     
 
        3.6 Send the correlationMatrix to MatrixFileWriter class which will
            write the matrix to a text file - or not!
 
Class 4: MatrixFileWriter.java
 
// Enable file writing
FileWriter file = new FileWriter("LDMatrix.txt");
PrintWriter OutputFile = new PrintWriter(file);
 
for(counter=0; counter<correlationMatrix.length; counter++)
{
   for(counter2=0; counter2<correlationMatrix.length; counter2++)
   {
      OutputFile.print(correlationMatrix[counter][counter2]+" ");
   }
   OutputFile.println("");
}
OutputFile.close();

[ May 28, 2007: Message edited by: Sam Bluesman ]
[ May 28, 2007: Message edited by: Sam Bluesman ]

[Charles Lyons]

Can I just clarify a couple of things?

(1) Only columns 1, 2 and 7 (the last) are important in this data:

Line1 about the file
Line2 gives column headings
21876767 21880326 CEU rs4352938 rs7865071 1 0.959 
21876767 21884299 CEU rs4352938 rs7389140 1 0.691 
21880326 21884299 CEU rs7865071 rs7389140 1 0.661 

(2) In this required output:

         21876767 21880326 21884299
21876767 0        0.041    0.309
21880326 0.041    0        0.339 
21884299 0.309    0.339    0

The produced matrix is symmetric with 0s on the diagonal? This will be a massive optimisation because you'll only need n(n-1)/2 pieces of data to create the matrix, whereas before you required n^2 - that's a huge saving for large n!

(3) Finally, how many lines are there in the file?
[ May 28, 2007: Message edited by: Charles Lyons ]

[Sam Bluesman]

Hi Charles.

1) Correct. 1,2 and 7 are the ONLY columns I need.

2) "The produced matrix is symmetric with 0s on the diagonal?"
Absolutly!

3) The number of lines will vary from anything of 10000 to 80000. This will depend on the nunber of SNPs that are being examined.

Many thanks

[William Brogden]

Here is what I was trying to suggest -

1. now that we know you are dealing with plain ascii we can use a byte[] and not loose any data
2. using the File object, get the length of the file and create a maching byte[]
3. read the entire file into the byte[] buffer
4. scan for line ends, recording the matching line starts as an ArrayList of Integer objects
5. convert the ArrayList data to an int[]

Now instead of reading the file repeatedly you can grab any arbitrary line as a String, making repeated passes through the data simple. You can now calculate and format your table one line at a time.

Bill

[Charles Lyons]

Presumably also the columns and rows in the output will need to be sorted so the headings are in ascending numerical order?

[Sam Bluesman]

Well they come in numerical order in the file already. I don't think it would matter too much if they were not in the output matrix.

[Charles Lyons]

2. using the File object, get the length of the file and create a maching byte[]
3. read the entire file into the byte[] buffer

But most of the data is redundant, so why store it at all?

4. scan for line ends, recording the matching line starts as an ArrayList of Integer objects

More efficient to scan with BufferedReader's readLine() - it calculates line terminating characters correctly, and obtains a String we'll want to parse anyway.

[Charles Lyons]

Well I was intrigued by this problem, so for a bit of fun, here's my draft solution:

import java.io.*;
import java.util.*;
 
public class MyProgram {
 
private static class DataPoint {
    /* snp1 <= snp2 by setData() */
    private int snp1;
    private int snp2;
 
    public void setData(int snp1, int snp2) {
        /* Set so that snp1 <= snp2 */
        this.snp1 = snp1 < snp2 ? snp1 : snp2;
        this.snp2 = snp1 < snp2 ? snp2 : snp1;
    }
 
    public int getSNP1() {
        return snp1;
    }
 
    public int getSNP2() {
        return snp2;
    }
 
    public boolean equals(Object o) {
        if(!(o instanceof DataPoint)) {
            return false;
        }
        DataPoint odp = (DataPoint) o;
        return (odp.snp1 == snp1 && odp.snp2 == snp2);
    }
 
    public int hashCode() {
        /* Return the least value for hash buckets */
        return snp1;
    }
}
 
public static void main(String[] args) throws Exception {
    /* The TreeMap + Comparator here makes sure we can sort at the same time as adding, so we get a nice ordered output */
    TreeMap<DataPoint, Double> data = new TreeMap<DataPoint, Double>(new Comparator<DataPoint>() {
        public int compare(DataPoint dp1, DataPoint dp2) {
            /* Sort by the value of snp1 (i.e. the least SNP value, then by the higher SNP2 value) */
            return dp1.getSNP1() == dp2.getSNP1() ? (dp1.getSNP2() - dp2.getSNP2()) : (dp1.getSNP1() - dp2.getSNP1());
        }
    });
 
    File f = new File(args[0]);
    BufferedReader br = new BufferedReader(new FileReader(f));
    /* Skip first two lines */
    br.readLine();
    br.readLine();
 
    /* Read each line at a time and extract the coordinate and data */
    String line = null;
    while((line = br.readLine()) != null) {
        /* Split the data by spaces */
        String[] lineData = line.split("\\s+");
        /* Get the SNPLocations and the coorelation */
        DataPoint dp = new DataPoint();
        dp.setData(Integer.parseInt(lineData[0]), Integer.parseInt(lineData[1]));
        data.put(dp, new Double(1.0 - Double.parseDouble(lineData[6])));
    }
    br.close();
 
    /* We have all the data we need in the 'data' Map - this set will have keys ordered so all SNP1 keys are the same, 
     * then all SNP2 keys the same
     */
    Set<DataPoint> snpLocations = data.keySet();
    
    // TODO: Output the results (hint: do it row at a time and use two loops: one for the rows, one for the columns).
}
 
}

It may well be full of compilation errors and I deliberately haven't finished it to give you something to work with. In particular, I think it will only output the upper (or lower) triangle of the matrix, so you'll need to think about how to get the diagonals and other triangle out. However, I think (after bug fixing) it should handle reading and sorting entries to provide a convenient way to obtain that data. You'll have to write the output code yourself! The only storage here is a TreeMap containing (n(n-1)/2) DataPoint and Double objects.

If you don't understand something or I've done something stupid, please post back your questions/comments...
[ May 28, 2007: Message edited by: Charles Lyons ]

[Jim Yingst]

OK, from what you've said, the largest file you have is 80,000 lines, which would create nonzero entries at 160,000 positions in the matrix, which has 400,000,000 positions total. That's a very sparse matrix. Because of the symmetry it could be done as a triangular matrix, but that only saves about half the space. It's still huge. You can use much less.

I would use my earlier HashMap suggestion. Whenever you you have a new line from the input file, take the two SNP locations and store them as a Pair:

class Pair {
    private final int x, y;
 
    public Pair(int a, int b) {
        if (a > b) {
            this.x = b;
            this.y = a;
        } else {
            this.x = a;
            this.y = b;
        }   
    }
 
    public int x() { return x; }
 
    public int y() { return y; }
 
    public boolean equals(Object obj) {
        if (!obj instanceof Pair) 
            return false;
        Pair other = (Pair) obj;
        return x == other.x && y == other.y;
    }
 
    public int hashCode() {
        return (x + 17) * 37 + y;
    }
}

Note the constructor makes sure that whatever order a and b are in, x is the lower number, and y is the higher number. Since the line for "21876767 21880326" also represents the correlation for "21880926 21876767", there's no need to store the latter one as well. This way we use one object to represent both.

Then just take each Pair and put it in a HashMap with the value:

for each line of input
    map.put(new Pair(SNP1Location, SNP2Location), 1 - correlation)
end

Then you can just print out your table directly, without ever putting everything in a big, mostly-empty array:

for SNP1Location from 1 to 20000
    for SNP2Location from 1 to 20000
        correlation = map.get(new Pair(SNP1Location, NSNP2Location))
        write correlation, space
    end
    write newline
end

Note that we don't need anything at all in memory except for the HashMap and its contents, plus a few local variables. And the HashMap is just a little bigger than your three arrays were (which we no longer need), and much, much smaller than a 20000 x 20000 matrix.
[ May 28, 2007: Message edited by: Jim Yingst ]

[Jim Yingst]

Well, same basic idea. I don't see a purpose to using TreeMap rather than HashMap, since the ordering we need in the output is achieved by the loops. HashMap ought to be faster. But I might be missing something.

[Charles Lyons]

I don't see a purpose to using TreeMap rather than HashMap, since the ordering we need in the output is achieved by the loops. HashMap ought to be faster. But I might be missing something.

I don't know how the SNPLocation headings are being derived: numbers like 21876767 followed by 21880326 and 21884299 may not necessarily be in the appropriate order in the input file - and I'm not sure how you loop those from 1 to 20000 without knowing what they are in advance (there is no common difference between those three for instance)? Unless there's a pattern/formula I'm missing which determines them, it seemed sensible to order on the values of the input SNPLocations, rather than trust the file to be in the correct order already. If there is a pattern to exploit, HashMap is probably faster, though I would think TreeMap only has a performance overhead when adding the data (not retrieving it). Otherwise I think we have basically identical approaches!

[Jim Yingst]

[Charles]: The only storage here is a TreeMap containing (n(n-1)/2) DataPoint and Double objects.

Doesn't your map have only n entries? Same as mine?
[ May 28, 2007: Message edited by: Jim Yingst ]

[Charles Lyons]

Doesn't your map have only n entries? Same as mine?

I was interpreting n as the size of the resulting matrix (i.e. n x n matrix), while in fact if N is the number of lines in the input file (ignoring the first two), then we should have:

N = n(n-1)/2

So we're both correct, for different definitions of n or N! The map itself shouldn't contain any more than N (number of input data lines) entries.

[Sam Bluesman]

Hi Guys.

Thank you very much for trying to work this out. But there is a lot of code there I don't understand and so it's going to take me a while to work through it as I have not ever used any types of '-Map' before. I'll let you know of any questions I am sure to have about this.

Thanks again
[ May 28, 2007: Message edited by: Sam Bluesman ]

[Jim Yingst]

[Charles]: I don't know how the SNPLocation headings are being derived: numbers like 21876767 followed by 21880326 and 21884299 may not necessarily be in the appropriate order in the input file - and I'm not sure how you loop those from 1 to 20000 without knowing what they are in advance (there is no common difference between those three for instance)?

I missed that the numbers were larger than his stated range of 20000, implying that the list of SNP locations has many gaps in it. OK, so just take the lists of SNP locations he built in the first place, and sort them. Well, better to combine them and eliminate any duplicates, I guess, so put them all in a single TreeSet and do a toArray() on the result:

locationSet = new HashSet()
map = new HashSet()
for each line of input
    locationSet.add(SNP1Location)
    locationSet.add(SNP2Location)
    map.put(new Pair(SNP1Location, SNP2Location), 1 - correlation)
end
locationArray = locationSet.toArray()

Now you've got a complete list of SNP locations, in order. The final loops become:

for each x in locationArray 
    for each y in locationArray
        correlation = map.get(new Pair(x, y))
        if correlation is null
            correlation = 0
        write correlation + space
    end
    write newline
end

I added a comment about null map values, which should be extremely common since the size of the input file is so small compared to the output table.

[Charles]: I would think TreeMap only has a performance overhead when adding the data (not retrieving it).

It's O(log(n)) for get() as well as put(). Unless you're iterating the entrySet(), but I don't see how that would work here.

[Charles]: I was interpreting n as the size of the resulting matrix (i.e. n x n matrix),

Ah, makes sense.
[ May 28, 2007: Message edited by: Jim Yingst ]

[Sam Bluesman]

Hi Guys.

Im trying to implment a TreeMap as shown by charles but when I compile i get the folling error:

type TreeMap does not take parameters

Any ideas?

Cheers

[Sam Bluesman]

Sorry. I've just figured that i forgot an import statement - after hours of reading!!!

[Sam Bluesman]

Right. I've been doing my reading and examining the code used by Charles. I am printing to the screen the values held in the TreeMap. But I am a bit lost as to where the values of the SNP locations have gone?

Could you please clear this up for me?

MANY thanks

[Charles Lyons]

Using either of the solutions given previously, the keys for the map hold both the snp1 and snp2 values... You can obtain the pairs using the entrySet() method of TreeMap and iterating through that (possibly marginally more efficient than iterating through the keys and using get() on TreeMap to retrieve the value).

By the way, how's the running time? If it's a problem, Jim's solution is quite possibly slightly faster, though requires separate sorting code.

[Sam Bluesman]

Hello there.

OK. I've tried that using the following code:

Set<Map.Entry<DataPoint, Double>> set = data.entrySet();
 
    for (int counter=0; counter<data.size(); counter++) {
      System.out.print(set);
    }

However, I get the following in my XP console:

[FileInProgram$DataPoint@457=0.5, FileInProgram$DataPoint@457=0.7, FileInProgram$DataPoint@8ae=0.9][FileInProgram$DataPoint@457=0.5, Fi
leInProgram$DataPoint@457=0.7, FileInProgram$DataPoint@8ae=0.9][FileInProgram$DataPoint@457=0.5, FileInProgram$DataPoint@457=0.7, FileI
nProgram$DataPoint@8ae=0.9]

...having used the following small input file:

Line1
Line2
1111 2222 3 4 5 6 0.5
1111 3333 3 4 5 6 0.3
2222 3333 3 4 5 6 0.1
 

I think i'm not doing something right as I can't see the SNP locations listed.
[ May 30, 2007: Message edited by: Sam Bluesman ]

[Sam Bluesman]

BTW. Performace is excellent.

[Charles Lyons]

References like "FileInProgram$DataPoint@457" are the default implementation of toString() - which is invoked to output the DataPoint as a String.

Since you don't actually want toString() anyway, try the following (uses Java 5 syntax for the iterating):

Set<Map.Entry<DataPoint, Double>> set = data.entrySet();
for(Map.Entry<DataPoint, Double> entry : set) {
    System.out.println(entry.getKey().getSNP1() + "," + entry.getKey().getSNP2() + "=" + entry.getValue());
}

The keys should be in ascending order of SNP1. Now you've got the data in the map and an output set, you'll need to figure out how to output a matrix grid of the required values.

[Jim Yingst]

You're printing the entire entrySet() three times. And by using print() rather than println(), it's more confusing because there's no line separator between entries. Try something like this:

for (Map.Entry<DataPoint, Double> e : data.entrySet()) {
    System.out.println(e.getKey() + " = " + e.getValue());
}

The real problem though is that the DataPoint class doesn't have a toString() method that prints the point in a helpful manner. Neither did my Pair. Oops. However, you can add one, overriding the toString() method in DataPoint so that instead of "FileInProgram$DataPoint@457" you get something like "[1111,2222]"

Note that with a good toString() in place, you'd have gotten readable output just by writing

System.out.println(data);

[ May 30, 2007: Message edited by: Jim Yingst ]

[Jim Yingst]

[Charles]: Since you don't actually want toString() anyway

Well, not for the final result, in this case. But it's useful for being able to print something out to see what data is there. In my response I'm assuming there will be more work to format the output later. The toString() is just for debugging.

[Sam Bluesman]

Ah. That seemed to work guys.

Thank you very much.