根据干预机会对两个坐标之间的旅行进行排名的最快方法？

Question

我有超过5000个带lat / lon坐标的数据帧，我有另一个数据帧，有超过23000次跳闸，原始lat / lon坐标和目标lat / lon坐标。

所有地方和旅行都在布拉格，CZE地区。

我想根据干预机会计算每次旅行的等级 - 在距离原点更近的所有其他地方的总和。机会的方向无关紧要。

我尝试了嵌套循环来创建地点之间所有距离的列表，但它的速度很慢。 （10小时内达到第80名）

for (row in 73:nrow(dataset_2015_POI_prg)) {
    print(row)
    id <- toString(dataset_2015_POI_prg[row, "venue_id"])
    lat <- dataset_2015_POI_prg[row, "venue_lat"]
    lon <- dataset_2015_POI_prg[row, "venue_lon"]

    for (innerrow in 1:nrow(dataset_2015_POI_prg)) {
        innerid <- toString(dataset_2015_POI_prg[innerrow, "venue_id"])
        if (id != innerid && length(which(dataset_2015_POI_mix$from_venue_id == innerid & dataset_2015_POI_mix$to_venue_id == id)) == 0) {
            print(innerrow)
            innerlat <- dataset_2015_POI_prg[innerrow, "venue_lat"]
            innerlon <- dataset_2015_POI_prg[innerrow, "venue_lon"]   
            dist <- distm(c(lon, lat), c(innerlon, innerlat), fun = distHaversine)
            dataset_2015_POI_mix[nrow(dataset_2015_POI_mix) + 1,] = list(id, lat, lon, innerid, innerlat, innerlon, as.numeric(dist))
        }
    }
}

旅行数据帧

user_id from_lat    from_lon    to_lat      to_lon      distance
159493  50.08017    14.50109    50.09171    14.54276    3241.884096
159493  50.09171    14.54276    50.09076    14.54271    106.390784
159493  50.09076    14.54271    50.11302    14.61078    5456.33700
...

放置数据框

venue_id    venue_lat   venue_lon
4adcda9     50.08096    14.42810
...

什么是正确和最快的方式？预期的结果是具有新列级别的旅行的新数据帧，其是与原始位置相比所有更接近的位置的总和。

非常感谢，我是R的新手:)

编辑：源文件对于pastebin来说太大了，所以这里是：trip：http://data.krysp.in/trips.txt把http://data.krysp.in/pois.txt

EDIT2：dput()的小数据示例：

structure(list(venue_lat = c(50.09171, 50.090755, 50.113024, 
50.113251, 50.103708, 50.080167, 50.108774, 50.113106, 50.081854, 
50.104832, 50.090597, 50.113026, 50.068476, 50.113124, 50.10815, 
50.060503), venue_lon = c(14.542765, 14.542707, 14.610781, 14.611714, 
14.490623, 14.501095, 14.577527, 14.611648, 14.500505, 14.476009, 
14.541811, 14.611271, 14.404627, 14.611779, 14.583479, 14.506008
)), row.names = c(NA, 16L), class = "data.frame")

旅行

structure(list(user_id = c(159493, 159493, 159493, 159493, 159493, 
159493, 159493, 159493, 159493, 159493, 159493, 159493, 159493, 
159493, 159493, 159493, 159493, 159493, 159493, 159493, 159493, 
159493, 159493, 159493, 159493, 159493, 159493, 159493, 159493, 
159493), from_lat = c(50.080167, 50.09171, 50.090755, 50.113024, 
50.113251, 50.113024, 50.103708, 50.080167, 50.108774, 50.113024, 
50.113106, 50.09171, 50.080167, 50.081854, 50.113106, 50.113024, 
50.104832, 50.09171, 50.090597, 50.113024, 50.09171, 50.113026, 
50.113024, 50.068476, 50.113124, 50.113024, 50.09171, 50.113024, 
50.10815, 50.09171), from_lon = c(14.501095, 14.542765, 14.542707, 
14.610781, 14.611714, 14.610781, 14.490623, 14.501095, 14.577527, 
14.610781, 14.611648, 14.542765, 14.501095, 14.500505, 14.611648, 
14.610781, 14.476009, 14.542765, 14.541811, 14.610781, 14.542765, 
14.611271, 14.610781, 14.404627, 14.611779, 14.610781, 14.542765, 
14.610781, 14.583479, 14.542765), from_timestamp = c(10284, 58919, 
58960, 82576, 197020, 1520404, 1539221, 1581079, 1585186, 1586688, 
1586730, 1615656, 1637753, 1640134, 1643362, 1643399, 1659750, 
1756952, 1765592, 1870541, 2000993, 2008701, 2008728, 2541997, 
2653448, 2659355, 2682234, 2727528, 2822921, 2852025), to_lat = c(50.09171, 
50.090755, 50.113024, 50.113251, 50.113024, 50.103708, 50.080167, 
50.108774, 50.113024, 50.113106, 50.09171, 50.080167, 50.081854, 
50.113106, 50.113024, 50.104832, 50.09171, 50.090597, 50.113024, 
50.09171, 50.113026, 50.113024, 50.068476, 50.113124, 50.113024, 
50.09171, 50.113024, 50.10815, 50.09171, 50.060503), to_lon = c(14.542765, 
14.542707, 14.610781, 14.611714, 14.610781, 14.490623, 14.501095, 
14.577527, 14.610781, 14.611648, 14.542765, 14.501095, 14.500505, 
14.611648, 14.610781, 14.476009, 14.542765, 14.541811, 14.610781, 
14.542765, 14.611271, 14.610781, 14.404627, 14.611779, 14.610781, 
14.542765, 14.610781, 14.583479, 14.542765, 14.506008), to_timestamp = c(58919, 
58960, 82576, 197020, 1520404, 1539221, 1581079, 1585186, 1586688, 
1586730, 1615656, 1637753, 1640134, 1643362, 1643399, 1659750, 
1756952, 1765592, 1870541, 2000993, 2008701, 2008728, 2541997, 
2653448, 2659355, 2682234, 2727528, 2822921, 2852025, 3185844
), distance = c(3241.88409599252, 106.39078390924, 5456.33700758756, 
71.2359425785903, 71.2359425785903, 8640.94151730882, 2725.20357275113, 
6319.36823149692, 2420.67310365364, 62.5615027825454, 5464.76021027322, 
3241.88409599252, 192.467213137768, 8665.6776299234, 62.5615027825454, 
9664.83271725758, 4985.72628636199, 141.396853243087, 5521.3444368517, 
5405.101536154, 5436.65634829112, 34.9800594737613, 15536.1468890647, 
15607.2384436169, 72.1080346201786, 5405.101536154, 5405.101536154, 
2023.20076623555, 3435.28409601096, 4354.77279195115)), row.names = c("2", 
"3", "4", "5", "6", "7", "8", "9", "10", "11", "12", "13", "14", 
"15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", 
"26", "27", "28", "29", "30", "31"), class = "data.frame")

Answer 1

我不太确定我是否理解了“基于干预机会对命运进行排名”的意思。这当然意味着同一目的地可以根据用户的不同来源而具有不同的等级。此外，我不确定“介入”是否应该暗示起源和目的地之间的方向。

无论如何这就是我所拥有的：

建议1（考虑方向）

准备trips df

library(sf)

buffers <- list()

for(i in 1:nrow(trips)) {
buffers[[i]] <- st_buffer(st_linestring(matrix(as.numeric(trips[i, c(3,2,6,5)]), ncol = 2, byrow = T)), dist = 0.01)
}

buffer_sfc <- st_sfc(buffers, crs = 4326)

sf_trips <- st_sf(trips, geometry = buffer_sfc)

准备dest df

sf_dest <- st_as_sf(x = dest, coords = c("venue_lon", "venue_lat"), crs = 4326)

创建排名

res <- st_contains(sf_trips, sf_dest)

trips$rank <- sapply(res, length)

这就是它的作用：用直线连接原点和目的地并在其周围创建一个多边形。然后位于该多边形中的所有其他目的地点都是“干预”。您可以通过dist =中的st_buffer参数调整多边形的大小，具体取决于与直接连接的偏差仍然可以称为“干预”。

我相信这会比你的代码运行得更快。如果通过“干预”，你的意思是任何靠近原点的地方，无论你做什么方向：

建议2

library(RANN)


intv_ops <- list()

for(i in 1:nrow(trips)) {
  intv_ops[[i]] <- nn2(dest, trips[i, 2:3], searchtype = "radius", radius = (trips$distance[i]/1.11) * 0.00001)$nn.idx
}

trips$rank <- sapply(intv_ops, function(x) sum(x != 0))

qazxsw pois是用C ++编写的knn算法的包装器，所以它非常快。