Efficient computation of bivariate empirical cdf in R/Fortran

Question

Given an n*2 data matrix X I'd like to calculate the bivariate empirical cdf for each observation, i.e. for each i in 1:n, return the percentage of observations with 1st element not greater than X[i,1] and 2nd element not greater than X[i,2].

Because of the nested search involved it gets terribly slow for n ~ 100k, even after porting it to Fortran. Does anyone know if there's a better way of handling sample sizes like this?

Edit: I believe this problem is similar (in terms of complexity) to finding Kendall's tau, which is of order O(n^2). In that case Knight (1966) has an algorithm to reduce it to O(n log(n)). Just wondering if there's any O(n*log(n)) algorithm for finding bivariate ecdf already out there.

Edit 2: This is the code I have in Fortran, as requested. This is called in R in the usual way, so the R code is omitted here. The code is meant for arbitrary dimensions, but for the specific thing I'm doing a bivariate one is good enough.

! Calculates multivariate empirical cdf for each point
! n: number of observations
! d: dimension (>=2)
! umat: data matrix
! outvec: vector of ecdf

subroutine mecdf(n,d,umat,outvec)
    implicit none

    integer :: n, d, i, j, k, tempsum
    double precision, dimension(n) :: outvec
    double precision, dimension(n,d) :: umat
    logical :: flag

    do i = 1,n
        tempsum = 0
        do j = 1,n
            flag = .true.
            do k = 1,d
                if (umat(i,k) < umat(j,k)) then
                    flag = .false.
                    exit
                end if
            end do
            if (flag) then
                tempsum = tempsum + 1
            end if
        end do
        outvec(i) = real(tempsum)/n
    end do
    return
end subroutine

Answer 1

I think my first effort was not really an ecdf, although it did map the points to the interval [0,1] The example, a 25 x 2 matrix generated with:

#M <- matrix(runif(100), ncol=2)
M <- 
structure(c(0.0468267474789172, 0.296053855214268, 0.205678076483309, 
0.467400068417192, 0.968577065737918, 0.435642971657217, 0.929023026255891, 
0.038406387437135, 0.304360694251955, 0.964778139721602, 0.534192910650745, 
0.741682186257094, 0.0848641532938927, 0.405901980120689, 0.957696850644425, 
0.384813814423978, 0.639882878866047, 0.231505588628352, 0.271994129288942, 
0.786155494628474, 0.349499785574153, 0.279077709652483, 0.206662984099239, 
0.777465222170576, 0.705439242534339, 0.643429880728945, 0.887209519045427, 
0.0794123203959316, 0.849177583120763, 0.704594585578889, 0.736909110797569, 
0.503158083418384, 0.49449566937983, 0.408533290959895, 0.236613316927105, 
0.297427259152755, 0.0677345870062709, 0.623845702270046, 0.139933609170839, 
0.740499466424808, 0.628097783308476, 0.678438259987161, 0.186680511338636, 
0.339367639739066, 0.373212536331266, 0.976724133593962, 0.94558056560345, 
0.610417427960783, 0.887977657606825, 0.663434249348938, 0.447939050383866, 
0.755168803501874, 0.478974275058135, 0.737040047068149, 0.429466919740662, 
0.0021107573993504, 0.697435079608113, 0.444197302218527, 0.108997165458277, 
0.856855363817886, 0.891898229718208, 0.93553287582472, 0.991948011796921, 
0.630414301762357, 0.0604106825776398, 0.908968194155023, 0.0398679254576564, 
0.251426834380254, 0.235532913124189, 0.392070295521989, 0.530511683085933, 
0.319339724024758, 0.534880011575297, 0.92030712752603, 0.138276003766805, 
0.213625695323572, 0.407931711757556, 0.605797187192366, 0.424798395251855, 
0.471233424032107, 0.0105366336647421, 0.625802840106189, 0.524665891425684, 
0.0375960320234299, 0.54812005511485, 0.0105806747451425, 0.438266788609326, 
0.791981092421338, 0.363821814302355, 0.157931488472968, 0.47945317090489, 
0.906797411618754, 0.762243523262441, 0.258681379957125, 0.308056800393388, 
0.91944490163587, 0.412255838746205, 0.347220918396488, 0.68236422073096, 
0.559149842709303), .Dim = c(50L, 2L))

So the task is to do a single summation of a two-part logical test on N items which I suspect is O(N*3). It might be marginally faster if implemented in Rcpp, but these are vectorized operations.

# Wrong: ecdf2d <- function(m,i,j) { ord <- rank(m[ , 1]^2+m[ , 2]^2)
#            ord[i]/nrow(m)}  # scales to [0,1] interval

ecdf2d.v2 <- function(obj, x, y) sum( obj[,1] < x & obj[,2] < y)/nrow(obj)