Geek Answers Handbook

Find the minimum value between two sets of vectors (fastest way)

I have a data frame, which is the start and end time for a series of vectors. So, we have a bunch of vectors x and y vectors, and I want to compare the minimum distance between two vectors. If two vectors have any overlapping parts, then the minimum distance is 0 (in this application you cannot have a negative distance).

Here is the data structure (below is an easy way to capture it):

  x.start x.end y.start y.end
1       3     6       7     8
2      10    14      19    22
3      19    25      45    45
4      33    33      66    68
5     100   101      90   101
6     130   150     134   153

So, I want to go through the line along the vectors x and for each x-vector compare it with all y vectors and find the minimum distance between them.

Below I do this with a nested loop for, but I need to repeat this many times with a lot of vectors so that the speed counts. It is slow. What is the most efficient way to accomplish this task?

Desired conclusion:

## > out
## [1]  1  2  0 11  0  0

I would prefer to keep this in the R database, but if you have a faster way, independent of the OS, I am open.

Data:

dat <- data.frame(
    x.start = c(3, 10, 19, 33, 100, 130),
    x.end = c(6, 14, 25, 33, 101, 150), 
    y.start = c(7, 19, 45, 66, 90, 134),
    y.end = c(8, 22, 45, 68, 101, 153)
)

Please note that looking at my answer below may help to better understand the problem. I will compare the results after several competitors increase.

Here is the desired output as a data frame to simplify comparison and understanding:

  min_dist x.start x.end y.start y.end
1        1       3     6       7     8
2        2      10    14      19    22
3        0      19    25      45    45
4       11      33    33      66    68
5        0     100   101      90   101
6        0     130   150     134   153

Visualization of two sets of vectors:

enter image description here

, y ( ); x- 33:33, y- 45:45 , , .

: Tally

Unit: microseconds
                 expr      min       lq   median       uq        max neval
         GEEKTRADER() 5386.186 5553.659 5603.341 5678.214  68297.171  5000
            TRINKER() 1421.887 1480.198 1496.992 1517.985  63619.596  5000
       RICARDO_OPT1() 4748.483 4892.631 4974.968 5110.952 156400.446  5000
       RICARDO_OPT2() 7387.463 7583.859 7694.418 7845.564  70200.949  5000
          FOTNELTON()  437.576  462.767  473.963  486.091   6109.724  5000
     FOTNELTON_EDIT()  356.871  379.730  390.460  402.122   3576.174  5000
 RICARDO_SIMPLE_ANS()  801.444  842.496  855.091  870.952   3923.715  5000
             ALEXIS()  343.343  385.328  397.923  408.652   4169.093  5000
+4
6

, , , :

apply(dat, 1, function(d) {
  overlap <- (dat$y.end >= d[1] & dat$y.end <= d[2]) |
             (dat$y.start >= d[1] & dat$y.start <= d[2])
  if (any(overlap)) 0
  else min(abs(c(d[1] - dat$y.end[!overlap], dat$y.start[!overlap] - d[2])))
})

EDIT: overlap :

apply(dat, 1, function(d) {
  overlap <- dat$y.end >= d[1] & dat$y.start <= d[2]
  if (any(overlap)) 0
  else min(abs(c(d[1] - dat$y.end[!overlap], dat$y.start[!overlap] - d[2])))
})
+5

, . .

apply(dat[,1:2], MARGIN=1, FUN=function(x) {
  min(apply(dat[,3:4], MARGIN = 1, FUN = function(y){
    X <- c(t(x))
    Y <- c(t(y))
    #Check if the two line segments overlap else find minimum distance between the 2 edges of each line segments
    if (diff(range(c(X,Y))) <=  diff(X) + diff(Y)){
      return(0)
    } else {
      return(min(abs(outer(Y, X, "-"))))
    }
  }))
})
## [1]  1  2  0 11  0  0
+1

. . (№ 2), , . .

by=. , , x.start x.end. , x.end by. , , .

  library(data.table)
  DT <- data.table(dummykey = "A", dat, key="dummykey")
  A <- DT[ , !c("y.start", "y.end"), with=FALSE][DT[, !c("x.start", "x.end"), with=FALSE], allow.cartesian=TRUE]

1

  A[, max(0, min(ifelse(x.start > y.start, x.start-y.end, y.start-x.end))), by=x.start]
                                                 # or by=list(x.start, y.end)

2

  A[, xstartGTystart := x.start > y.start]
  A[(xstartGTystart), candidates := x.start - y.end]
  A[!(xstartGTystart), candidates := y.start-x.end]

  A[, list(minDisance=max(0, min(candidates))), by=x.start]
                             # or by=list(x.start, y.end)
+1

( ), , :

current <- c("x.start", "x.end")
comparedto <- c("y.start", "y.end")

apply(dat[, current], 1, function(r) {
  max(0, min(ifelse(r[[1]] > dat[, comparedto[[1]]], r[[1]]-dat[, comparedto[[2]]], dat[, comparedto[[1]]]-r[[2]])))
})
# [1]  1  2  0 11  0  0
+1

( , ):

alexis3 <- function()
{                   
 fun <- function(x1, x2, yvec1 = dat$y.start, yvec2 = dat$y.end) 
 { 
  if(any(c(yvec1, yvec2) %in% seq(x1, x2))) return(0)
  else min(abs(outer(c(x1, x2), c(yvec1, yvec2), `-`))) 
 } 

 mapply(fun, x1 = dat$x.start, x2 = dat$x.end)
}

#> alexis3()
#[1]  1  2  0 11  0  0
+1

:

## Convert start and end times to two lists of vectors
xvects <- mapply(":", dat[, 1], dat[, 2])
yvects <- mapply(":", dat[, 3], dat[, 4])

## Function to take vector x[i] and compare to all vector y    
FUN <- function(a, b) {
    vals <- abs(outer(a, b, "-"))
    if ((sum(vals) == 0) > 0) {
        return(0)
    }
    min(vals)
}

## Pre alot
out <- rep(NA, nrow(dat))

## Nested for loop
for (i in seq_along(xvects)) {

    outj <- rep(NA, nrow(dat))

    for (j in seq_along(yvects)) {

        outj[j] <- FUN(xvects[[i]], yvects[[j]])
    }

    out[i] <- min(outj)

}
0

More articles:


All Articles