3
\$\begingroup\$

I have two lists with ca. 4000 elements where each each element have two columns. These are being fed into a function. Besides the function they are being fed into, is it possible to speed it up somehow? At this rate, it will take ca. 6-7 days to complete.

results=rep(0, length(as.numeric(unlist(coors))))
for(i in names(coors)){
  print(i)
  for( j in names(pols)){
    results[i]=point.in.polygon(coors[[i]][,1], coors[[i]][,2], pols[[j]][,1], pols[[j]][,2]) 
}}

EDIT: further description, I have the polygons for each ind in year 1 and the coordinates for year 2. I want to see how many of the locations from year 2 that falls within the polygon from year 1 for each individual.

EDIT 2: the structure of coors

 str(coors)  
 List of 4052  
  $ 2225 :'data.frame': 48 obs. of  2 variables:  
   ..$ cor.x: num [1:48] 635184 635215 635394 635431 635430 ...  
   ..$ cor.y: num [1:48] 7151002 7151201 7151175 7151110 7151118 ...  
  $ 2226 :'data.frame': 56 obs. of  2 variables:  
   ..$ cor.x: num [1:56] 635945 635936 635944 635969 635947 ...  
   ..$ cor.y: num [1:56] 7152813 7152847 7152834 7152785 7152810 ...  
  $ 2227 :'data.frame': 56 obs. of  2 variables:  
   ..$ cor.x: num [1:56] 636244 636245 636317 636450 636386 ...  
   ..$ cor.y: num [1:56] 7151503 7151505 7151628 7151693 7151799 ...  
  $ 2228 :'data.frame': 56 obs. of  2 variables:  
   ..$ cor.x: num [1:56] 636451 636418 636408 636467 636495 ...  
  ..$ cor.y: num [1:56] 7152610 7152605 7152634 7152572 7152537 ...  

There are always either 48 or 56 obs per element level. Pols have similar structure, but more variable lengths as the number of observations depends on the shape of the polygon.

\$\endgroup\$

migrated from stackoverflow.com Oct 2 '12 at 19:17

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ I suggest you describe the task that you are trying to accomplish so that we can help you rethink the design. \$\endgroup\$ – dan1111 Oct 1 '12 at 8:07
  • \$\begingroup\$ Are these polygons mutually distinct? If so, you might save time by not checking further after a match is found. Any other constraints might help as well. \$\endgroup\$ – DWin Oct 1 '12 at 8:07
  • \$\begingroup\$ I have updated with some more description that I hope might help. @DWin they are not necessarily distinct and they don't need to be. \$\endgroup\$ – Endre Grüner Ofstad Oct 1 '12 at 9:30
3
\$\begingroup\$

I assume you are using point.in.polygon from the sp package. The function can take any number of points, so you should rewrite your algorithm as a single loop: for each polygon in pols, make a single call to point.in.polygon to check if all the points in coords are inside or not. This should save you a lot of time. Then you'll only have to do a little work reformatting the output. I can help with the code if you can please clarify what coors looks like.

Edit: Here is now an example of how you could code this into a single loop. It is possible you will have to work it a bit as you have not really shown us how you want to store your output.

First, some sample data:

coors <- replicate(5, {n <- sample(5:10, 1);
                       data.frame(x = runif(n), y = runif(n))},
                   simplify = FALSE)

pols <- replicate(3, {n <- sample(5:10, 1)
                      data.frame(x = runif(n), y = runif(n))},
                  simplify = FALSE)

Here, we concatenate all the points in coors together, but keep a vector of group indices which we will use later for splitting by group:

all.coors  <- do.call(rbind, coors)
num.points <- sapply(coors, nrow)
group.idx  <- rep(seq_along(coors), num.points)

Now the single loop:

results <- vector("list", length(pols)) 
for (j in seq_along(pols)) {
   print(j)
   results[[j]] <- split(point.in.polygon(all.coors[,1], all.coors[,2],
                                          pols[[j]][,1], pols[[j]][,2]),
                         group.idx)
}

I am confident this will significantly speed up your computations. However, if this is still too slow, I agree you'll have to consider parallelization. Good luck.

\$\endgroup\$
  • \$\begingroup\$ I have now added more description :) \$\endgroup\$ – Endre Grüner Ofstad Oct 1 '12 at 12:57
  • \$\begingroup\$ Wow! Thank you for the time and effort! :) I have the coors also as a dataframe, so I was thinking about storing it as a new column there and then just use ave() to count number of 1's for each id. \$\endgroup\$ – Endre Grüner Ofstad Oct 2 '12 at 6:48
2
\$\begingroup\$

What you have here is a nested loop. Since the inner loop is executed 4000 times for each iteration of the outer loop, the total number of calls to point.in.polygon is 4000^2 so 16 million times.

The problem lies in how often the method is called and there is usually no direct way of speeding this up. Loop execution is only the tiniest fraction of the runtime spend here, the major amount of time will most likely be lost inside point.in.polygon. You can prove this by removing the function call to point.in.polygon and calling a dummy method instead.

Your best bet is finding a better algorithmic solution to your problem instead of trying to improve the brute force version you have here. As I understand it, you also overwrite the results[i] array for each inner call to point.in.polygon which basically means that only the last j-value's result will be saved anyway.

If you can not come up with a better algorithm, an alternative would be to execute the code in a multithreaded way. Maybe https://stackoverflow.com/questions/1395309/how-to-make-r-use-all-processors is a good starting point for that.

\$\endgroup\$
  • \$\begingroup\$ Thank you, I have tried to look at multiprocessing. I thought I was adding the results of the function to the results-vector. The function results is simply a vector with 1s and 0s (are the coordinate inside or outside the polygon) as long as the vector for coordinates. \$\endgroup\$ – Endre Grüner Ofstad Oct 1 '12 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy