[R] Making a ranking algorithm more efficient
Peter Wolf
s-plus at wiwi.uni-bielefeld.de
Wed Jun 2 11:09:13 CEST 2004
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
>
>
More information about the R-help
mailing list