r - 如何有效识别重复的有序对-6ren

r - 如何有效识别重复的有序对

转载作者：行者123 更新时间：2023-12-04 10:14:33

我正在处理在不同列中包含源 ID 和目标 ID 的源-目的地 (OD) 数据。有时，聚合相同的 OD 对很重要，只是起点和终点交换了。

OD 数据如下所示:

orign             dest      value
E02002361         E02002361 109
E02002361         E02002363  38
E02002361         E02002367  10
E02002361         E02002371  44
E02002363         E02002361  34

在上面的例子中，第一行和最后一行可以被认为是同一对，除了方向相反。挑战在于如何有效地识别它们是重复的。

我创建了一个包， stplanr ，这可以回答这个问题，如下面的可重现示例所示:

x = read.csv(stringsAsFactors = FALSE, text = "orign,dest,value
E02002361,E02002361,109
E02002361,E02002363,38
E02002361,E02002367,10
E02002361,E02002371,44
E02002363,E02002361,34")
duplicated(stplanr::od_id_order(x)[[3]])
#> Registered S3 method overwritten by 'R.oo':
#>   method        from       
#>   throw.default R.methodsS3
#> [1] FALSE FALSE FALSE FALSE  TRUE

创建于 2019-07-27 由 reprex package (v0.3.0)

这种方法的问题在于对于大型数据集来说速度很慢。

我看过 fastest way to get Min from every column in a matrix?这表明 pmin是在多列(不是 2)中获得最小值的最有效方法，我们已经在使用它。

不像 Removing duplicate combinations (irrespective of order)这个问题是关于只有 2 列的重复识别和效率。解决方法贴在 Removing duplicate combinations (irrespective of order)似乎比下面的时间中显示的最慢的解决方案慢。

比这更快的解决方案是 szudzik_pairing函数，由我的同事 Malcolm Morgan 创建并基于 method由 Matthew Szudzik 开发。

我们已经尝试了每种方法，Szudzik 方法确实看起来更快，但我想知道:有没有更有效的方法(在任何语言中，但最好在 R 中实现)？

这是我们所做工作的一个可快速重现的示例，包括一个显示时间的简单基准测试:

od_id_order_base <- function(x, id1 = names(x)[1], id2 = names(x)[2]) {
  data.frame(
    stringsAsFactors = FALSE,
    stplanr.id1 = x[[id1]],
    stplanr.id1 = x[[id2]],
    stplanr.key = paste(
      pmin(x[[id1]], x[[id2]]),
      pmax(x[[id1]], x[[id2]])
    )
  )
}

od_id_order_rfast <- function(x, id1 = names(x)[1], id2 = names(x)[2]) {
  data.frame(
    stringsAsFactors = FALSE,
    stplanr.id1 = x[[id1]],
    stplanr.id1 = x[[id2]],
    stplanr.key = paste(
      Rfast::colPmin(as.numeric(as.factor(x[[id1]])), as.numeric(as.factor(x[[id1]]))),
      pmax(x[[id1]], x[[id2]])
    )
  )
}

od_id_order_dplyr <- function(x, id1 = names(x)[1], id2 = names(x)[2]) {
  dplyr::transmute_(x,
    stplanr.id1 = as.name(id1),
    stplanr.id2 = as.name(id2),
    stplanr.key = ~paste(pmin(stplanr.id1, stplanr.id2), pmax(stplanr.id1, stplanr.id2))
  )
}

szudzik_pairing <- function(val1, val2, ordermatters = FALSE) {
  if(length(val1) != length(val2)){
    stop("val1 and val2 are not of equal length")
  }

  if(class(val1) == "factor"){
    val1 <- as.character(val1)
  }
  if(class(val2) == "factor"){
    val2 <- as.character(val2)
  }
  lvls <- unique(c(val1, val2))
  val1 <- as.integer(factor(val1, levels = lvls))
  val2 <- as.integer(factor(val2, levels = lvls))
  if(ordermatters){
    ismax <- val1 > val2
    stplanr.key <- (ismax * 1) * (val1^2 + val1 + val2) + ((!ismax) * 1) * (val2^2 + val1)
  }else{
    a <- ifelse(val1 > val2, val2, val1)
    b <- ifelse(val1 > val2, val1, val2)
    stplanr.key <- b^2 + a
  }
  return(stplanr.key)
}


n = 1000
ids <- as.character(runif(n, 1e4, 1e7 - 1))

x <- data.frame(id1 = rep(ids, times = n),
                id2 = rep(ids, each = n),
                val = 1,
                stringsAsFactors = FALSE)



head(od_id_order_base(x))
#>        stplanr.id1    stplanr.id1.1                       stplanr.key
#> 1 8515501.50763425 8515501.50763425 8515501.50763425 8515501.50763425
#> 2 2454738.52108038 8515501.50763425 2454738.52108038 8515501.50763425
#> 3  223811.25236322 8515501.50763425  223811.25236322 8515501.50763425
#> 4 4882305.41496906 8515501.50763425 4882305.41496906 8515501.50763425
#> 5  4663684.5752892 8515501.50763425  4663684.5752892 8515501.50763425
#> 6 725621.968830239 8515501.50763425 725621.968830239 8515501.50763425
head(od_id_order_rfast(x))
#>        stplanr.id1    stplanr.id1.1          stplanr.key
#> 1 8515501.50763425 8515501.50763425 830 8515501.50763425
#> 2 2454738.52108038 8515501.50763425 163 8515501.50763425
#> 3  223811.25236322 8515501.50763425 135 8515501.50763425
#> 4 4882305.41496906 8515501.50763425 435 8515501.50763425
#> 5  4663684.5752892 8515501.50763425 408 8515501.50763425
#> 6 725621.968830239 8515501.50763425 689 8515501.50763425
head(od_id_order_dplyr(x))
#> Warning: transmute_() is deprecated. 
#> Please use transmute() instead
#> 
#> The 'programming' vignette or the tidyeval book can help you
#> to program with transmute() : https://tidyeval.tidyverse.org
#> This warning is displayed once per session.
#>        stplanr.id1      stplanr.id2                       stplanr.key
#> 1 8515501.50763425 8515501.50763425 8515501.50763425 8515501.50763425
#> 2 2454738.52108038 8515501.50763425 2454738.52108038 8515501.50763425
#> 3  223811.25236322 8515501.50763425  223811.25236322 8515501.50763425
#> 4 4882305.41496906 8515501.50763425 4882305.41496906 8515501.50763425
#> 5  4663684.5752892 8515501.50763425  4663684.5752892 8515501.50763425
#> 6 725621.968830239 8515501.50763425 725621.968830239 8515501.50763425
head(szudzik_pairing(x$id1, x$id2))
#> [1]  2  5 10 17 26 37


system.time(od_id_order_base(x))
#>    user  system elapsed 
#>   0.467   0.000   0.467
system.time(od_id_order_rfast(x))
#>    user  system elapsed 
#>   1.063   0.001   1.064
system.time(od_id_order_dplyr(x))
#>    user  system elapsed 
#>   0.493   0.000   0.493
system.time(szudzik_pairing(x$id1, x$id2))
#>    user  system elapsed 
#>   0.100   0.000   0.101

创建于 2019-07-27 由 reprex package (v0.3.0)

devtools::session_info()
#> ─ Session info ──────────────────────────────────────────────────────────
#>  setting  value                       
#>  version  R version 3.6.0 (2019-04-26)
#>  os       Debian GNU/Linux 9 (stretch)
#>  system   x86_64, linux-gnu           
#>  ui       X11                         
#>  language (EN)                        
#>  collate  en_US.UTF-8                 
#>  ctype    en_US.UTF-8                 
#>  tz       Etc/UTC                     
#>  date     2019-07-27                  
#> 
#> ─ Packages ──────────────────────────────────────────────────────────────
#>  package      * version date       lib source        
#>  assertthat     0.2.1   2019-03-21 [1] CRAN (R 3.6.0)
#>  backports      1.1.4   2019-04-10 [1] CRAN (R 3.6.0)
#>  callr          3.3.0   2019-07-04 [1] CRAN (R 3.6.0)
#>  cli            1.1.0   2019-03-19 [1] CRAN (R 3.6.0)
#>  crayon         1.3.4   2017-09-16 [1] CRAN (R 3.6.0)
#>  desc           1.2.0   2018-05-01 [1] CRAN (R 3.6.0)
#>  devtools       2.1.0   2019-07-06 [1] CRAN (R 3.6.0)
#>  digest         0.6.20  2019-07-04 [1] CRAN (R 3.6.0)
#>  dplyr          0.8.3   2019-07-04 [1] CRAN (R 3.6.0)
#>  evaluate       0.14    2019-05-28 [1] CRAN (R 3.6.0)
#>  fs             1.3.1   2019-05-06 [1] CRAN (R 3.6.0)
#>  glue           1.3.1   2019-03-12 [1] CRAN (R 3.6.0)
#>  highr          0.8     2019-03-20 [1] CRAN (R 3.6.0)
#>  htmltools      0.3.6   2017-04-28 [1] CRAN (R 3.6.0)
#>  knitr          1.23    2019-05-18 [1] CRAN (R 3.6.0)
#>  magrittr       1.5     2014-11-22 [1] CRAN (R 3.6.0)
#>  memoise        1.1.0   2017-04-21 [1] CRAN (R 3.6.0)
#>  pillar         1.4.2   2019-06-29 [1] CRAN (R 3.6.0)
#>  pkgbuild       1.0.3   2019-03-20 [1] CRAN (R 3.6.0)
#>  pkgconfig      2.0.2   2018-08-16 [1] CRAN (R 3.6.0)
#>  pkgload        1.0.2   2018-10-29 [1] CRAN (R 3.6.0)
#>  prettyunits    1.0.2   2015-07-13 [1] CRAN (R 3.6.0)
#>  processx       3.4.0   2019-07-03 [1] CRAN (R 3.6.0)
#>  ps             1.3.0   2018-12-21 [1] CRAN (R 3.6.0)
#>  purrr          0.3.2   2019-03-15 [1] CRAN (R 3.6.0)
#>  R6             2.4.0   2019-02-14 [1] CRAN (R 3.6.0)
#>  Rcpp           1.0.1   2019-03-17 [1] CRAN (R 3.6.0)
#>  RcppZiggurat   0.1.5   2018-06-10 [1] CRAN (R 3.6.0)
#>  remotes        2.1.0   2019-06-24 [1] CRAN (R 3.6.0)
#>  Rfast          1.9.4   2019-05-25 [1] CRAN (R 3.6.0)
#>  rlang          0.4.0   2019-06-25 [1] CRAN (R 3.6.0)
#>  rmarkdown      1.13    2019-05-22 [1] CRAN (R 3.6.0)
#>  rprojroot      1.3-2   2018-01-03 [1] CRAN (R 3.6.0)
#>  sessioninfo    1.1.1   2018-11-05 [1] CRAN (R 3.6.0)
#>  stringi        1.4.3   2019-03-12 [1] CRAN (R 3.6.0)
#>  stringr        1.4.0   2019-02-10 [1] CRAN (R 3.6.0)
#>  testthat       2.1.1   2019-04-23 [1] CRAN (R 3.6.0)
#>  tibble         2.1.3   2019-06-06 [1] CRAN (R 3.6.0)
#>  tidyselect     0.2.5   2018-10-11 [1] CRAN (R 3.6.0)
#>  usethis        1.5.1   2019-07-04 [1] CRAN (R 3.6.0)
#>  withr          2.1.2   2018-03-15 [1] CRAN (R 3.6.0)
#>  xfun           0.8     2019-06-25 [1] CRAN (R 3.6.0)
#>  yaml           2.2.0   2018-07-25 [1] CRAN (R 3.6.0)
#> 
#> [1] /usr/local/lib/R/site-library
#> [2] /usr/local/lib/R/library

最佳答案

以下是从元组 (x, y) 生成唯一键的四种可能方法，其中顺序无关紧要:od_id_order_base和 szudzik_pairing ，根据 OP 的问题；一种改进的 Szudzik 方法 szudzik_pairing_alt ;和方法 max_min使用此 answer 中所示的公式.

convert_to_numeric <- function(x, y) {
  if (length(x) != length(y)) stop("x and y are not of equal length")
  if (class(x) == "factor") x <- as.character(x)
  if (class(y) == "factor") y <- as.character(y)
  lvls <- unique(c(x, y))
  x <- as.integer(factor(x, levels = lvls))
  y <- as.integer(factor(y, levels = lvls))
  list(x = x, y = y)  
}

od_id_order_base <- function(x, y) {
  d <- convert_to_numeric(x, y)
  x <- d$x
  y <- d$y
  paste(pmin(x, y), pmax(x, y))
}

szudzik_pairing <- function(x, y) {
  d <- convert_to_numeric(x, y)
  x <- d$x
  y <- d$y
  a <- ifelse(x > y, y, x)
  b <- ifelse(x > y, x, y)
  b^2 + a
}

szudzik_pairing_alt <- function(x, y) {
  d <- convert_to_numeric(x, y)
  x <- d$x
  y <- d$y
  z <- y^2 + x
  ifelse(y < x, x^2 + y, z)
}

max_min <- function(x, y) {
  d <- convert_to_numeric(x, y)
  x <- d$x
  y <- d$y
  a <- pmax(x, y)
  b <- pmin(x, y)
  a * (a + 1) / 2 + b
}

从一些示例数据生成 key 并验证我们得到相同的结果:

check_dupe <- function(f, x, y) duplicated(f(x, y))

set.seed(123)
n <- 1000^2
x <- ceiling(runif(n) * 1000)
y <- ceiling(runif(n) * 1000)

p <- lapply(list(od_id_order_base, szudzik_pairing, szudzik_pairing_alt, 
  max_min), check_dupe, x, y)
all(sapply(p[-1], function(x) identical(p[[1]], as.vector(x))))
# [1] TRUE

基准测试:

bmk <- microbenchmark::microbenchmark(
  p1 = check_dupe(od_id_order_base, x, y),
  p2 = check_dupe(szudzik_pairing, x, y),
  p3 = check_dupe(szudzik_pairing_alt, x, y),
  p4 = check_dupe(max_min, x, y),
  times = 100
)
# Unit: seconds
#  expr      min       lq     mean   median       uq      max neval cld
#    p1 2.958512 3.089615 3.336621 3.336915 3.474973 4.721378   100   b
#    p2 1.934742 2.058185 2.191331 2.190588 2.306203 2.983729   100  a 
#    p3 1.889201 1.990306 2.173845 2.138995 2.259218 5.186751   100  a 
#    p4 1.870261 1.980756 2.143026 2.145458 2.234580 3.111324   100  a

关于r - 如何有效识别重复的有序对，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/57235601/

文章推荐： graphql - 在 Graphql 突变中传递多行字符串

文章推荐： r - 如何在R中获得abline的梯度

文章推荐： r - 根据两个相似的df之间的对比创建一个新的数据框

文章推荐： r - 修改 S3 对象而不返回它？

mongodb 元组比较(有序)
就类似于这个问题:mongodb query multiple pairs using $in 我想用 (first, last) >= ('John', 'Smith') 找到前 10 个全名。使用
cocoa - 有序 NSDictionary
如何保留向 NSDictionary 添加对象的方式？我意识到 NSDictionary 中的值没有特定的顺序，但就我而言，我需要保留使用 setValue:forKey: 添加的顺序，例如一个数组
assembly - 有序/无序比较是什么意思？
看看上证所运营商 CMPORDPS - ordered compare packed singles CMPUNORDPS - unordered compare packed singles 有序和
java - powermock 有序
我使用 PowerMock 来模拟静态方法。我需要验证静态和非静态方法调用的顺序。可以使用 PowerMock 来做吗？ UPD 我使用 powermockito 扩展来模拟静态方法，因此使用 pow
scala - 合并两个流(有序)以获得最终排序的流
例如，如何合并两个已排序的整数流？我认为这是非常基本的，但只是发现它根本不是微不足道的。下面的不是尾递归的，当流很大时它会堆栈溢出。 def merge(as: Stream[Int], bs: St
c - 用于在二叉树中查找(有序)节点后继的代码中的段错误
我试图在二叉树中查找/打印每个节点的中序后继，但编译器给我的结果是段错误。这是结构:- struct node { int x; struct node *left; str
sql - 使整个 block 有序
我有一个查询看起来像 SELECT a, b, c, d FROM tab ORDER BY a ASC, b ASC 我的结果集看起来像 +-----------------
php - 有序 SQL 时间戳提取
首先，我试过搜索这个主题但一无所获(似乎找不到合适的关键词)，所以如果这是重复的，请告知。我一直在尝试从我的数据库中获取一些 time_stamp 并将它们按时间间隔排序。例如，我运行一个查询，如
c++ - 有序 QVector 中的二进制搜索
这个问题在这里已经有了答案: How do I get the index of an iterator of an std::vector? (9 个回答) 关闭 6 年前。我已经订购了 QVe
java - 有序 Hibernate 列表违反唯一约束
我有以下实体，如果我尝试通过 removeTask 方法从 TaskList 中删除 Task，则会出现异常。 @Entity public class TaskList extends Generi
c - 将字符串中的每个字母(有序)合并为一个新字符串
所以，我对 C 编程还是很陌生。有3个长度相同的字符串。 str1="abc", str2="def", str3="ghi". 新字符串中的输出将类似于“adgbehcfi”。 #include
MySQL:分组/有序/左连接查询非常慢
我的查询有一个问题，它花费的时间太长(仅仅这个简单的查询就超过了两秒)。乍一看，这似乎是一个索引问题，所有连接的字段都已编入索引，但我找不到其他我可能需要编入索引以加快速度的内容。一旦我将我需要的字
java - 有序 map 实现
我正在寻找一个 Map 实现，它按照键值对的添加顺序迭代它们。例如 Map orderedMap = // instantiation omitted for obvious reasons :) o
database - 分层、有序、键值存储？
我正在寻找具有以下功能的数据库系统: 分层(多维)键每个维度的键排序因此，如果我的 key 类似于 App > User > Item，我可以运行如下查询:“该用户的下一项是什么？”或者“这个应用
c++ - 使无序初始化 statc 有序
以下类使用 CRTP 尝试将类型添加到具有 Schwarz 计数器以确保初始化顺序的 std::vector。根据 3.6.2/2 成员 h_ 具有无序初始化。我将如何更改它以确保它已订购初始化？我希
C++有序(稳定)优先级队列
我正在实现一个玩具调度程序，它读取进程规范(例如到达时间、总运行时间)的输入文件，然后根据随机 io/cpu 突发调度进程。文件格式 Arrival time, total CPU time, CP
Python - 有序 header HTTP 请求
我目前正在使用 python 2.7 requests 库，并且不支持有序 header 。我可以为 post 和 get 放置有序数据(如有序字典)，但根本不支持标题。甚至在 python 3 中也
java - java中是否有并发&自过期&有序 HashMap
我正在使用来自 google guava 的 ConcurrentHashMap(通过 MapMaker)，但该实现未排序。google guava 中有 ConcurrentSkipListMap，
java - 有序(自然插入顺序)和线程安全的 Java Map
我有一个旧应用程序，其中使用 ConcurrentHashMap。现在我们知道并发HasMap 是无序的，但是需要读取最初插入的对象。我已经在生产中使用了一段时间的代码，因此我正在寻找快速替代方案来替
c# - 保持 .NET 依赖注入(inject)有序
最近我开始使用 .NET Core 2.1 开发一个新项目，我决定使用 SOLID 原则并创建一个漂亮的项目结构。这是一个 Web API 项目。一切正常我使用了很多依赖注入(inject)，大部分

行者123

个人简介

我是一名优秀的程序员,十分优秀！

作者热门文章

滴滴打车优惠券免费领取

全站热门文章

首页

博学

6Ren·AI

商城

r - 如何有效识别重复的有序对