प्रभावी खोज

Question

एक मैट्रिक्स प्रत्येक पंक्ति में एक दो आयामी क्षेत्र को निर्धारित कर, और एक अन्य मैट्रिक्स निर्दिष्ट बिंदु एक विमान में विचार करें:

xmin <- c(3, 14, 25, 61) 
xmax <- c(5, 18, 27, 65) 
ymin <- c(33, 12, 83, 2) 
ymax <- c(35, 16, 90, 6) 
regions <- cbind(xmin, xmax, ymin, ymax) 

x <- c(7, 26, 4, 16) 
y <- c(4, 85, 30, 13) 
points <- cbind(x, y) 

regions में अनुक्रमित प्राप्त करने की सबसे तेज़ तरीका क्या है कि points में प्रत्येक अंक शामिल है?

मैं क्या हासिल करना चाहते का एक उदाहरण है:

apply(points, 1, function(x){ 
    which(regions[,'xmin'] < x[1] & regions[,'xmax'] > x[1] & regions[,'ymin'] < x[2] & regions[,'ymax'] > x[2]) 
}) 

लेकिन दोनों regions और points दृष्टिकोण 1E5 में पंक्तियों की संख्या के रूप में इस बल्कि धीमी गति से हो जाता है और मैं एक उचित vectorized दृष्टिकोण के लिए देख रहा हूँ .. ।

अग्रिम धन्यवाद ...

सबसे अच्छा थॉमस

ई डीआईटी:

किसी भी दिलचस्पी के लिए मैंने आरसीपीपी का उपयोग करके सी ++ में एक फ़ंक्शन बनाया जो लगभग 50x प्रदर्शन सुधार प्रदान करता है। मैं सी में धाराप्रवाह ++ तो यह संभवतः बेहतर किया जा सकता है नहीं कर रहा हूँ ... इस समारोह के

cppFunction(' 
    IntegerVector findInRegion(NumericVector x, NumericVector y, NumericVector xmin, NumericVector xmax, NumericVector ymin, NumericVector ymax){ 
     int pointSize = x.size(); 
     int regionSize = xmin.size(); 
     IntegerVector ans(pointSize); 
     for(int i = 0; i < pointSize; i++){ 
      ans[i] = NA_INTEGER; 
     } 

     for(int i = 0; i < pointSize; i++){ 
      for(int j = 0; j < regionSize; j++){ 
       if(x[i] > xmin[j]){ 
        if(x[i] < xmax[j]){ 
         if(y[i] > ymin[j]){ 
          if(y[i] < ymax[j]){ 
           ans[i] = j+1; 
          }; 
         }; 
        }; 
       }; 
      }; 
     }; 
     return ans; 
    } 
') 

findRegion <- function(points, regions){ 
    if(!all(c('x', 'y') %in% colnames(points))){ 
     stop('points must contain columns named \'x\' and \'y\'') 
    } 
    if(!all(c('xmin', 'xmax', 'ymin', 'ymax') %in% colnames(regions))){ 
     stop('regions must contain columns named \'xmin\', \'xmax\', \'ymin\' and \'ymax\'') 
    } 
    findInRegion(points[, 'x'], points[,'y'], regions[, 'xmin'], regions[, 'xmax'], regions[, 'ymin'], regions[, 'ymax']) 
} 

एक दोष यह है कि यह मान लिया गया एक बिंदु केवल एक ही क्षेत्र से संबंधित हो सकता है ...

Answer 1

SQLite के साथ R-tree अनुक्रमणिका (बाध्यकारी बक्से को स्टोर करने के लिए डिज़ाइन किए गए डेटाबेस इंडेक्स का एक प्रकार) का उपयोग करके एक और समाधान है। यह साइमन के (7 सेकंड) की तुलना में थोड़ा धीमा हो गया है, संभवतः क्योंकि डेटा डिस्क पर कॉपी किया गया है।क्षेत्रों तो एक कुशल डेटा संरचना (एक [आर-वृक्ष] (में संग्रहीत किया जाएगा:

# Sample data: data.frames, rather than matrices 
regions <- data.frame(id=1:length(xmin), xmin, xmax, ymin, ymax) 
points <- data.frame(x, y) 

library(RSQLite) 
con <- dbConnect("SQLite", dbname = "/tmp/a.sqlite") 
dbGetQuery(con, "CREATE VIRTUAL TABLE regions USING rtree (id, xmin, xmax, ymin, ymax)") 
dbWriteTable(con, "regions", regions, row.names = FALSE, append = TRUE) 
dbWriteTable(con, "points", points, row.names = TRUE) 
res <- dbGetQuery(con, " 
    SELECT points.row_names, regions.id 
    FROM points, regions 
    WHERE xmin <= x AND x <= xmax 
    AND ymin <= y AND y <= ymax 
") 

Answer 2

यह वह जगह है वास्तव में एक दिलचस्प समस्या है। मैंने कुछ प्रारंभिक परीक्षण किया और यह लगता है जैसे यह तेज़ हो सकता है, लेकिन मुझे वास्तव में यह नहीं पता कि यह कितना अच्छा है।

# Are X coords greater than xmin 
lx <- outer(points[,1] , regions[,1] , ">") 

# Are X coords less than xmax 
hx <- outer(points[,1] , regions[,2] , "<") 

# Ditto for Y coords 
ly <- outer(points[,2] , regions[,3] , ">") 
hy <- outer(points[,2] , regions[,4] , "<") 

# These matrices for X and Y points have 1 if coords is in range, 0 otherwise 
inx <- lx * hx 
iny <- ly * hy 

# The final result matrix has 1 if both X and Y coords are in range and 0 if not 
# Rows are points, columns are regions 
res <- inx * iny 

100000 अंक और 100000 क्षेत्रों के डेटा पर इस दृष्टिकोण जब तक आप रैम बहुत है काम नहीं करेगा: मैं अगर आप अपने वास्तविक आंकड़ों पर परीक्षण करने और कुछ समय रिपोर्ट सकता है रुचि होगी। हालांकि मुझे लगता है कि यदि आप लगभग 1000 प्रत्येक के भाग में क्षेत्रों की संख्या को विभाजित करते हैं तो यह बहुत उपयोगी है। मेरे डेस्कटॉप पर 100,000 अंक और 1000 क्षेत्रों 5 सेकंड ले लिया:

Unit: seconds 
     expr  min  lq median  uq  max neval 
eval(simon) 4.528942 4.55258 4.59848 4.607572 4.671511  5 

समय मैं अपने apply विधि और यह एक, 10,000 अंक और 1000 क्षेत्रों के साथ के बीच में अंतर देखा की भयावहता को एक मोटा गाइड के रूप में (के आधार पर 5 रन):

Unit: milliseconds 
     expr  min  lq median  uq  max neval 
eval(simon) 394.7165 402.0919 403.0491 404.6943 428.7077  5 
    eval(OP) 1359.5889 1364.6308 1372.4980 1383.1327 1491.4628  5 

और 100,000 अंक और 1000 क्षेत्रों (एक रन के आधार पर) के साथ:

Unit: seconds 
     expr  min  lq median  uq  max neval 
eval(simon) 4.352857 4.352857 4.352857 4.352857 4.352857  1 
    eval(OP) 14.027390 14.027390 14.027390 14.027390 14.027390  1 

इस कोड मैं नमूना डेटा एक उत्पन्न करने के लिए प्रयोग किया जाता है डी बेंचमार्क चलाने के लिए:

set.seed(4862) 
xmin <- sample(25,1000,repl=T) 
xmax <- xmin + sample(15,100,repl=T) 
ymin <- sample(25,1000,repl=T) 
ymax <- ymin + sample(15,1000,repl=T) 
regions <- cbind(xmin, xmax, ymin, ymax) 

x <- sample(25,100000,repl=T) 
y <- sample(25,100000,repl=T) 
points <- cbind(x, y) 


OP <- quote({ res <- apply(points, 1, function(x){ 
    which(regions[,'xmin'] < x[1] & regions[,'xmax'] > x[1] & regions[,'ymin'] < x[2] & regions[,'ymax'] > x[2]) 
}) }) 


simon <- quote({ 
lx <- outer(points[,1] , regions[,1] , ">") 
hx <- outer(points[,1] , regions[,2] , "<") 
ly <- outer(points[,2] , regions[,3] , ">") 
hy <- outer(points[,2] , regions[,4] , "<") 
inx <- lx * hx 
iny <- ly * hy 
res <- inx * iny }) 

require(microbenchmark) 
microbenchmark(eval(simon) , eval(OP) , times = 1L) 

मैं इसे भाग में करने की अनुशंसा करता हूं। HTH।