Results 1 to 9 of 9
 11182010, 04:54 AM #1Member
 Join Date
 Nov 2010
 Posts
 1
 Rep Power
 0
Picking a Collection and Design for querying 1G Point objects
Hi everyone, any chance I could get some design tips?
I have one million Point objects where the x and y values are floats with 2 decimal places. These points exist somewhere between a top left corner of (0,0) and a bottom right corner(400,200).
When the user specifies a top left and bottom right Point(for a rectangle) (no slanted diaganol lines), I have to return all of my Point objects that are inside of the Rectangle specified by the user  in less than a second.
I tried making 2 TreeSets  one ordered by X and one ordered by Y, where they both use the same Point objects, (I'm avoiding instantiating double the points). The 1st treeset is instantiated without problems, but when my application attempts instantiating the 2nd TreeSet, I get an outof Heap memory exception. If that were to have worked correctly instead, I was planning on using the "subset" method in TreeSet to get all the Point objects in the user's selected X range, .. and then viceversa on the "Y" treeset for the points matching the user's specified Y rectangle values,.. and then I could take the intersection of those two result lists to arrive at a list with the points inside the user's specified rectangle.
Tweaking the JVM memory is Not going to be an option.
Is there a different design I should be using?
Thanks so much
 11182010, 10:05 AM #2Moderator
 Join Date
 Apr 2009
 Posts
 13,368
 Rep Power
 24
 11182010, 10:50 AM #3Senior Member
 Join Date
 Jun 2008
 Posts
 2,571
 Rep Power
 11
Uhm, why not a list in a list (or a 2dimensional array rather than a 2 dimensional list) with "nonused" points having a null reference? Then simply pull out the indexes that correspond to the x and y coordinates involved?
 11182010, 11:01 AM #4Moderator
 Join Date
 Apr 2009
 Posts
 13,368
 Rep Power
 24
How would you convert the float coordinates to int indexes?
 11182010, 11:44 AM #5Senior Member
 Join Date
 Jun 2008
 Posts
 2,571
 Rep Power
 11
Sorry, didn't notice float, but he said, specifically "with two decimal points", so x 100.
 11182010, 11:50 AM #6Moderator
 Join Date
 Apr 2009
 Posts
 13,368
 Rep Power
 24
Good point.
I just took in the float aspect and missed the two decimal places bit.
:)
I do wonder how big a List that would make, though. If they're already suffering an OOM with two TreeSets containing only the Points that exist, then adding in (albeti null) references for 40000 x 20000...800 million references?
 11182010, 12:26 PM #7
 Join Date
 Sep 2008
 Location
 Voorschoten, the Netherlands
 Posts
 14,414
 Blog Entries
 7
 Rep Power
 25
Maybe the following will fit: for 20000x40000 points (== 8E8 points) a bitset (one bit per point) takes up 1E8 bytes (100 MB). The bit is zero when a point at that coordinate doesn't exist. If the space is (extremely?) sparse this probably won't be a suitable solution.
kind regards,
JosBuild a wall around Donald Trump; I'll pay for it.
 11182010, 12:38 PM #8Moderator
 Join Date
 Apr 2009
 Posts
 13,368
 Rep Power
 24
We don't know what the space restrictions are, only that they are sufficiently low to prevent two TreeSets containing the same million objects.
We know the million objects fit (since they can create one TreeSet), but an additional million references (plus whataver overhead there is for a TreeSet) kills it. So I suspect an additional 100Mb would also kill it.
 11222010, 11:09 AM #9Member
 Join Date
 Nov 2010
 Posts
 1
 Rep Power
 0
Using an array can be an efficient solution with memory and performance
See the code below which uses both Treeset and array.
import java.awt.Point;
import java.io.BufferedReader;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Date;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;
import java.util.SortedSet;
import java.util.StringTokenizer;
import java.util.TreeSet;
class ABC {
public static final int TT_EOL = 10;
}
class TestSwitch {
public static void main(String args[]) {
System.out.println("Treeset *************");
treeSetOper();
System.out.println("Arry *************");
arrayOper();
}
public static void treeSetOper(){
TreeSet<Point> parray1 = new TreeSet<Point>(new XComparator());
TreeSet<Point> parray2 = new TreeSet<Point>(new YComparator());
for(int i = 0 ; i < 1000000 ; i++){
Random r1 = new Random();
Point p = new Point(r1.nextInt(40000),r1.nextInt(20000));
parray1.add(p);
}
Iterator<Point> i = parray1.iterator();
while(i.hasNext()){
Point p = i.next();
parray2.add(p);
}
Point inputTop = new Point(19980,9980);
Point inputBottom = new Point(20020,10020);
long before = System.currentTimeMillis();
SortedSet<Point> subsetx = parray1.subSet(new Point(19980,0), new Point(20020,20000));
SortedSet<Point> subsety = parray2.subSet(new Point(0,9980), new Point(40000,10020));
Set<Point> intersection = new HashSet<Point>(subsetx);
intersection.retainAll(subsety);
long after = System.currentTimeMillis();
System.out.println("Size : " + intersection.size());
System.out.println("Time : " + (afterbefore));
}
public static void arrayOper(){
long before = System.currentTimeMillis();
Point[] parray1 = new Point[1000000];
//Point[] parray2 = new Point[1000000];
for(int i = 0 ; i < 1000000 ; i++){
Random r1 = new Random();
Point p = new Point(r1.nextInt(40000),r1.nextInt(20000));
//Point p = new Point(1,1);
parray1[i]=p;
//parray2[i]=p;
}
//Arrays.sort(parray1,new XComparator());
//Arrays.sort(parray2,new YComparator());
Point inputTop = new Point(19980,9980);
Point inputBottom = new Point(20020,10020);
ArrayList<Point> intersection = new ArrayList<Point>();
for(int i = 0 ; i < 1000000 ; i++){
Point p = parray1[i];
if((p.x >=19980 && p.x <= 20020) && (p.y >=9980 && p.y <= 10020)){
intersection.add(p);
}
}
long after = System.currentTimeMillis();
System.out.println("Size : " + intersection.size());
System.out.println("Time : " + (afterbefore));
}
}
class XComparator implements Comparator<Point>{
public int compare(Point o1, Point o2) {
int retval = 0;
int x = o1.xo2.x;
if(x < 0){
return 1;
}else if(x==0){
}else if(x>0){
return +1;
}
int y = o1.yo2.y;
if(y < 0){
return 1;
}else if(y==0){
}else if(y>0){
return +1;
}
return retval;
}
}
class YComparator implements Comparator<Point>{
public int compare(Point o1, Point o2) {
int retval = 0;
int y = o1.yo2.y;
if(y < 0){
return 1;
}else if(y==0){
}else if(y>0){
return +1;
}
int x = o1.xo2.x;
if(x < 0){
return 1;
}else if(x==0){
}else if(x>0){
return +1;
}
return retval;
}
}
Similar Threads

Picking randomly
By AbdulAziz Bader in forum New To JavaReplies: 17Last Post: 06022010, 12:39 PM 
Help needed with querying collections
By Jawaharlal in forum Advanced JavaReplies: 5Last Post: 04282010, 04:43 PM 
iterating through a collection of objects
By Scotty Boy in forum New To JavaReplies: 0Last Post: 04102008, 01:28 AM 
querying russian data from db problem
By mr_empty in forum JDBCReplies: 0Last Post: 03042008, 08:56 AM 
3D Duke picking his nose and contemplating on Ruby
By Mark in forum Reviews / AdvertisingReplies: 2Last Post: 12282007, 04:00 PM
Bookmarks