[R] Making a ranking algorithm more efficient

[Peter Wolf]

let's start by defining x and y matching the properties of the points in 
the picture
<<*>>=
x<-c(1,2,4,5,9,3,7,6); y<-c(10,8,5,3,2,9,4,7)
plot(x,y,pch=letters[1:8])

@
along each dimension we have to compare the coordinates of the points:
<<*>>=
outer(x,x,"<")

@
we get a logical matrix:
output-start
Wed Jun  2 10:36:52 2004
      [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]
[1,] FALSE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
[2,] FALSE FALSE  TRUE  TRUE  TRUE  TRUE  TRUE  TRUE
[3,] FALSE FALSE FALSE  TRUE  TRUE FALSE  TRUE  TRUE
[4,] FALSE FALSE FALSE FALSE  TRUE FALSE  TRUE  TRUE
[5,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[6,] FALSE FALSE  TRUE  TRUE  TRUE FALSE  TRUE  TRUE
[7,] FALSE FALSE FALSE FALSE  TRUE FALSE FALSE FALSE
[8,] FALSE FALSE FALSE FALSE  TRUE FALSE  TRUE FALSE
output-end

results of dimension x and of dimension y have to be aggregated by "&"
<<*>>=
outer(x,x,"<")&outer(y,y,"<")

@
and we get:
output-start
Wed Jun  2 10:44:56 2004
      [,1]  [,2]  [,3]  [,4]  [,5]  [,6]  [,7]  [,8]
[1,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[2,] FALSE FALSE FALSE FALSE FALSE  TRUE FALSE FALSE
[3,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE  TRUE
[4,] FALSE FALSE FALSE FALSE FALSE FALSE  TRUE  TRUE
[5,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[6,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[7,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
[8,] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE
output-end

TRUE in position (i,j) indicates that x- and y-coordinates of point i 
are smaller
than those of point j. The sum of row i shows the number of
points that dominate point i. The sum of col j shows the number of points
that are dominated by point j.
 
@
so we can compute the the number of dominated points by applying 
function sum on the cols:
<<*>>=
apply(outer(x,x,"<")&outer(y,y,"<"),2,sum)

@
at last some polishing
<<*>>=
result<-apply(outer(x,x,"<")&outer(y,y,"<"),2,sum)+1
names(result)<-letters[1:8]
result

@
output-start
Wed Jun  2 10:59:03 2004
a b c d e f g h
1 1 1 1 1 2 2 3
output-end

in the case of more than 2 dimensions you have to add further 
outer-operations

Peter Wolf




Waichler, Scott R wrote:

>I would like to make a ranking operation more efficient if possible.
>The goal is to rank a set of points representing objective 
>function values such that points which are "dominated" by no 
>others have rank 1, those which are dominated by one other point 
>have rank 2, etc.  In the example with two dimensions below, objective
>functions 1 and 2 are to be minimized.  Points a-e are non-dominated,
>rank 1 points.  Point f is rank 2 because point b is superior, and 
>point g is rank 2 because point d is superior.  Point h is rank 3 
>because points c and d are both superior.
>
>       | a 
>       |    f
>       |  b
>       |       h          (figure requires monospaced, plain-text
>display)
>Obj 1  |     c    
>       |         g 
>       |      d     
>       |            e
>       |____________________
>
>              Obj 2
> 
>
>I need to compute the ranks of the rows of a matrix, where each row
>represents a point in objective space and the columns
>contain the objective function values to be minimized.  
>Rank is defined as the number of points with objective function 
>values less than or equal to the current point (including the current 
>point).  I've written the following function with two loops:
>
>  PARETO.RANK <- function(obj.array) {
>    obj.array <- unique(obj.array)
>    
>    ind.row <- 1:nrow(obj.array)
>    ind.col <- 1:ncol(obj.array)
>
>    rank.vec <- rep(NA, length(ind.row)) # initialize
>
>    # Loop thru rows (points in objective function space)
>    for(i in ind.row) { 
>      set <- ind.row
>      for (j in ind.col) {  # Loop thru objective functions
>        set <- set[ obj.array[set,j] <= obj.array[i,j] ]
>      }
>      rank.vec[i] <- length(set)
>    }
>    return(rank.vec)
>  } # end PARETO.RANK3()
>
>Can anyone think of a way to do this more efficiently, for example by
>vectorizing further?  
>
>Thanks,
>Scott Waichler
>scott.waichler at pnl.gov
>
>______________________________________________
>R-help at stat.math.ethz.ch mailing list
>https://www.stat.math.ethz.ch/mailman/listinfo/r-help
>PLEASE do read the posting guide! http://www.R-project.org/posting-guide.html
>  
>