[R] truly object oriented programming in R
Jason Liao
jg_liao at yahoo.com
Thu Aug 12 19:20:14 CEST 2004
Dear Thomas,
Thank you very much again for taking time to answer my questions. I am
sorry that my knoweldge of R is limited as I have only learned what is
necessary to do my work. In the KD tree, we have this recursive data
structure in that each knod has two children knods and this process
continues until the data points are divided. Does R's list support this
recursive data structure? If yes, can you give a sample program?
Regards,
Jason
--- Thomas Lumley <tlumley at u.washington.edu> wrote:
> On Thu, 12 Aug 2004, Jason Liao wrote:
>
> > Good morning! I recently implemented a KD tree in JAVA for faster
> > kernel density estimation (part of the code follows). It went well.
> To
> > hook it with R, however, has proved more difficult. My question is:
> is
> > it possible to implement the algorithm in R? My impression seems to
> > indicate no as the code requires a complete class-object framework
> that
> > R does not support. But is there an R package or something that may
> > make it possible? Thanks in advance for your help.
>
>
> This code doesn't seem to have any requirement for a class-object
> framework. The methods can all be written as functions, there isn't
> any
> use of inheritance or polymorphism. The data structure can then be a
> list.
>
> Now, you might want to make this list an object, to improve printing
> or to
> make it easier to check that the functions don't get called with
> arguments
> that aren't really k-d trees. This is well within the facilities of
> even
> the S3 method system.
>
> AFAICS the only class/object facility that Java provides and the
> "methods" package doesn't is enforcement of "private" methods and
> data,
> which has absolutely no impact on the complexity of programs (it can
> affect how easy code *maintenance* is, because it forces you to
> decide
> what is and isn't in your API, but that's a separate issue).
>
> The old S3 class system is weaker, since it doesn't support function
> polymorphism based on more than one of the arguments and doesn't have
> reliable reflectance facilities.
>
>
> -thomas
>
>
> >
> > Java implementation of KD tree:
> >
> > public class Kdnode {
> >
> > private double[] center; //center of the bounding box
> > private double diameter; //maximum distance from center to
> > anywhere within the bounding box
> > private int numOfPoints; //number of source data points in
> the
> > bounding box
> >
> > private Kdnode left, right;
> >
> >
> > public Kdnode(double[][] points, int split_dim, int [][]
> > sortedIndices, double[][] bBox) {
> > //bBox: the bounding box, 1st row the lower bound, 2nd
> row
> > the upper bound
> > numOfPoints = points.length;
> > int d = points[0].length;
> >
> > center = new double[d];
> > for(int j=0; j<d; j++) center[j] =
> > (bBox[0][j]+bBox[1][j])/2.;
> > diameter = get_diameter(bBox);
> >
> > if(numOfPoints==1) {
> > diameter = 0.;
> > for(int j=0; j<d; j++) center[j] = points[0][j];
> > left = null;
> > right = null;
> > }
> > else {
> > int middlePoint =
> > sortedIndices[split_dim][numOfPoints/2];
> > double splitValue = points[middlePoint][split_dim];
> >
> > middlePoint =
> > sortedIndices[split_dim][numOfPoints/2-1];
> > double splitValue_small =
> > points[middlePoint][split_dim];
> >
> > int left_size = numOfPoints/2;
> > int right_size = numOfPoints - left_size;
> >
> > double[][] leftPoints = new double[left_size][d];
> > double[][] rightPoints = new
> double[right_size][d];
> >
> >
> > int[][] leftSortedIndices = new int[d][left_size];
> > int[][] rightSortedIndices = new int[d][right_size];
> >
> > int left_counter = 0, right_counter = 0;
> > int[] splitInfo = new int [numOfPoints];
> >
> > for(int i = 0; i < numOfPoints; i++) {
> > if(points[i][split_dim] < splitValue) {
> > for(int j=0; j<d; j++) leftPoints[left_counter][j] =
> points[i][j];
> > splitInfo[i] = right_counter;
> > left_counter++;
> > }
> >
> > else {
> > for(int j=0; j<d; j++) rightPoints[right_counter][j] =
> points[i][j];
> > splitInfo[i] = left_counter;
> > right_counter++;
> > }
> > }
> > // modify appropriately the indices to correspond to the new
> lists
> > for(int i = 0; i < d; i++) {
> > int left_index = 0, right_index = 0;
> > for(int j = 0; j < numOfPoints; j++) {
> > if(points[sortedIndices[i][j]][split_dim] < splitValue)
> > leftSortedIndices[i][left_index++] = sortedIndices[i][j] -
> > splitInfo[sortedIndices[i][j]];
> > else rightSortedIndices[i][right_index++] =
> sortedIndices[i][j]
> > - splitInfo[sortedIndices[i][j]];
> > }
> > }
> >
> > // Recursively compute the kdnodes for the points in the two
> > splitted spaces
> > double[][] leftBBox = new double[2][];
> > double[][] rightBBox = new double[2][];
> >
> > for(int i=0; i<2; i++) {
> > leftBBox[i] =
> > (double[])bBox[i].clone();
> > rightBBox[i] =
> > (double[])bBox[i].clone();
> > }
> >
> > leftBBox[1][split_dim] = splitValue_small;
> > rightBBox[0][split_dim] = splitValue;
> >
> > int next_dim = (split_dim + 1) % (d);
> > left = new Kdnode(leftPoints, next_dim, leftSortedIndices,
> > leftBBox);
> > right = new Kdnode(rightPoints, next_dim, rightSortedIndices,
> > rightBBox);
> > }
> > }
> >
> >
> > public double evaluate(double[] target, double delta,
> double
> > bandwidth) throws Exception
> > {
> >
> > double dis_2_center = Common.distance(target,
> > center)/bandwidth;
> > double dm = diameter/bandwidth;
> >
> > if(dis_2_center >= 1+dm) return 0.;
> > if(numOfPoints==1) return Common.K(dis_2_center);
> >
> > /*if(dis_2_center<1)
> > {
> > double temp2 = dm*Common.KDeriv(dis_2_center);
> > if(temp2<delta) return
> > Common.K(dis_2_center)*numOfPoints;
> > } */
> >
> > return left.evaluate(target,delta, bandwidth) +
> > right.evaluate(target,delta, bandwidth);
> > }
> >
> >
> > public double get_diameter(double[][] bBox)
> > {
> > double value = 0., diff;
> > for (int i=0; i<bBox[0].length;i++)
> > {
> > diff = (bBox[1][i] - bBox[0][i])/2.;
> > value += diff*diff;
> > }
> > return Math.sqrt(value);
> > }
> > }
> >
> > =====
> > Jason Liao, http://www.geocities.com/jg_liao
> > Dept. of Biostatistics, http://www2.umdnj.edu/bmtrxweb
> > University of Medicine and Dentistry of New Jersey
> > phone 732-235-5429, School of Public Health office
> > phone 732-235-8611, Cancer Institute of New Jersey office
> > moble phone 908-720-4205
> >
> > ______________________________________________
> > R-help at stat.math.ethz.ch mailing list
>
=== message truncated ===
=====
Jason Liao, http://www.geocities.com/jg_liao
Dept. of Biostatistics, http://www2.umdnj.edu/bmtrxweb
University of Medicine and Dentistry of New Jersey
phone 732-235-5429, School of Public Health office
phone 732-235-8611, Cancer Institute of New Jersey office
moble phone 908-720-4205
More information about the R-help
mailing list