检查一行中所有值是否相同或缺失的最有效方法

5

我最初在 data.table 论坛上提出了这个问题,得到了一些好的答案,但我希望找到一个不到一秒钟的解决方案(实际数据大小为 3M x 303)。

这是我的 R 社区中的链接,以及在 Julia 中使用 DataFrames.jl 的 MWE(如果我使用了错误的软件包,请告诉我)

julia> using DataFrames

julia> df = DataFrame(v1 = [1.0,2.1,3.0], v2 = [1,3,3], v3 = [missing,2.1,3.0])
3×3 DataFrame
 Row │ v1       v2     v3
     │ Float64  Int64  Float64?
─────┼───────────────────────────
   11.0      1  missing
   22.1      3        2.1
   33.0      3        3.0

julia> desired = [true,false,true]
3-element Vector{Bool}:
 1
 0
 1
6个回答

9
在Julia中,使用矩阵进行这类操作与R类似,也很自然:
julia> using BenchmarkTools

julia> function helper(x)
           nonempty = false
           local fv
           for v in x
               if !ismissing(v)
                   if nonempty
                       v == fv || return false
                   else
                       fv = v
                       nonempty = true
                   end
               end
           end
           return true
       end
helper (generic function with 1 method)

julia> mat = rand([1, 2, missing], 3_000_000, 303);

julia> @benchmark helper.(eachrow($mat))
BenchmarkTools.Trial: 34 samples with 1 evaluation.
 Range (min … max):  139.440 ms … 154.628 ms  ┊ GC (min … max): 5.74% … 5.15%
 Time  (median):     147.890 ms               ┊ GC (median):    5.27%        
 Time  (mean ± σ):   147.876 ms ±   3.114 ms  ┊ GC (mean ± σ):  5.23% ± 0.95%

                    ▃    ▃   ▃  ▃  ██ ▃
  ▇▁▁▁▁▁▁▁▁▁▇▁▁▁▁▁▁▁█▁▁▁▁█▇▇▇█▁▁█▇▁██▇█▁▇▁▇▇▁▇▇▁▇▁▇▇▇▁▁▁▁▇▁▁▁▁▇ ▁
  139 ms           Histogram: frequency by time          155 ms <

 Memory estimate: 114.80 MiB, allocs estimate: 6.

操作也可以在DataFrames.jl中完成,这里是一个如何执行的示例:
julia> function helper2(x, i)
           nonempty = false
           local fv
           for v in x
               vv = v[i]
               if !ismissing(vv)
                   if nonempty
                       vv == fv || return false
                   else
                       fv = vv
                       nonempty = true
                   end
               end
           end
           return true
       end
helper2 (generic function with 1 method)

julia> df = DataFrame(mat, :auto, copycols=false); # copycols to avoid copying as data is large

julia> @benchmark helper2.(Ref(identity.(eachcol($df))), 1:nrow($df))
BenchmarkTools.Trial: 46 samples with 1 evaluation.
 Range (min … max):  105.265 ms … 123.345 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     110.682 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   110.581 ms ±   2.692 ms  ┊ GC (mean ± σ):  0.00% ± 0.00%

                ▄ ▂ ▄█▂
  ▄▁▁▄▄▁▁▆▄▁▁▁▆▆█▄█▆███▄▄▁█▄▁▁▁▁▁▁▁▁▁▁▁▄▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▄ ▁
  105 ms           Histogram: frequency by time          123 ms <

 Memory estimate: 385.28 KiB, allocs estimate: 15.

如果代码中有任何不清楚的地方,请告诉我,我可以解释。


编辑

如果你有一个小型的唯一eltypes集合,做如下操作:

helper2.(Ref(collect(Union{unique(typeof.(eachcol(df)))...}, eachcol(df))), 1:nrow(df))

如果Union{unique(typeof.(eachcol(df)))...}不是一个小集合,那么最好有另一种解决方案,请在评论中说明这是否足够好。

你有一个由3_000_000个元素组成的向量,其中每个元素都是一个由303个元素组成的向量吗?还是一个由303个元素组成的向量,其中每个元素都是一个由3_000_000个元素组成的向量?如果是第一种情况,请使用第一种解决方案。如果是第二种情况,则使用第二种解决方案(语法可能需要进行最小限度的更改,但通常应使用相同的模式)。如果您更新了您使用的具体数据结构的问题,我将能够更新我的答案。 - Bogumił Kamiński
3
这表明您的源列 eltype 存在显着的异质性。这是您原来提问中没有出现过的。由于您要求“最有效”的代码,数据的确切特征非常重要 - 我针对您分享的数据优化了代码。我建议您使用想要获得最优代码的数据更新您的问题。然后我可以更新我的答案。 - Bogumił Kamiński
identity.()eltype 进行了约简 - 这是这个问题中至关重要的问题。第二段代码按行工作 - 请注意我用 i 进行索引。 - Bogumił Kamiński
1
我已经更新了小联合混合浮点数和整数的情况的答案。在我的电脑上,它运行大约116.094毫秒。 - Bogumił Kamiński
1
@BogumiłKamiński,根据我与OP的讨论,数据集中有30-70%的行具有相同的值。我猜这是瓶颈所在。更快的解决方案可能需要并行处理。 - ekoam
显示剩余8条评论

3

你是否有大约350MB的可用内存?如果是,你可以尝试使用这个函数。

rowequal <- function(x) {
  undetermined <- function(x, can_del) {
    if (length(can_del) < 1L)
      return(x)
    x[-can_del]
  }
  if (ncol(x) < 1L)
    return(logical())
  out <- logical(nrow(x))
  if (ncol(x) < 2L)
    return(!out)
  x1 <- x[[1L]]
  need_compare <- undetermined(seq_len(nrow(x)), which(x1 != x[[2L]]))
  x1[nas] <- x[[2L]][nas <- which(is.na(x1))]
  if (ncol(x) > 2L) {
    for (j in 3:ncol(x)) {
      need_compare <- undetermined(
        need_compare, which(x1[need_compare] != x[[j]][need_compare])
      )
      x1[nas] <- x[[j]][nas <- which(is.na(x1))]
      if (length(need_compare) < 1L)
        return(out)
    }
  }
  `[<-`(out, need_compare, TRUE)
}

以下是基准测试结果

> dim(d)
[1] 3000000     300
> bench::mark(f(d), rowequal(d), iterations = 10)
# A tibble: 2 x 13
  expression       min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result memory time  gc   
  <bch:expr>  <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list> <list> <lis> <lis>
1 f(d)           2.97s    2.98s     0.335    34.4MB        0    10     0      29.8s <lgl ~ <Rpro~ <ben~ <tib~
2 rowequal(d)  88.52ms  93.34ms    10.7     352.2MB        0    10     0    932.5ms <lgl ~ <Rpro~ <ben~ <tib~

在这里,f(我从这篇文章中获取)和d是:

f <- function(x) {
  v1 = do.call(pmin, c(x, na.rm = TRUE))
  v2 = do.call(pmax, c(x, na.rm = TRUE))
  v1 == v2
}

mkDT <- function(rows, cols, type = as.integer) {
  data.table::setDT(
    replicate(cols, sample(type(c(1:10, NA)), rows, replace = TRUE), simplify = FALSE)
  )
}

d <- mkDT(3e6, 300)

一个Rcpp版本的代码。如果你可以确保数据帧中所有列都是numeric类型,那么它可以实现最佳性能(在内存使用和速度方面)。我猜这是你问题的最有效解决方案(在R中)。

rowequalcpp <- function(x) {
  if (ncol(x) < 1L)
    return(logical())
  out <- logical(nrow(x))
  if (ncol(x) < 2L)
    return(!out)
  mark_equal(out, x)
  out
}

Rcpp::sourceCpp(code = '
#include <Rcpp.h>

// [[Rcpp::export]]
void mark_equal(Rcpp::LogicalVector& res, const Rcpp::DataFrame& df) {
  Rcpp::NumericVector x1 = df[0];
  int n = df.nrows();
  int need_compare[n];
  for (int i = 0; i < n; ++i)
    need_compare[i] = i;
  for (int j = 1; j < df.length(); ++j) {
    Rcpp::NumericVector dfj = df[j];
    for (int i = 0; i < n; ) {
      int itmp = need_compare[i];
      if (Rcpp::NumericVector::is_na(x1[itmp]))
        x1[itmp] = dfj[itmp];
      if (!Rcpp::NumericVector::is_na(dfj[itmp]) && x1[itmp] != dfj[itmp]) {
        need_compare[i] = need_compare[n - 1];
        need_compare[n-- - 1] = itmp;
      } else
        ++i;
    }
    if (n < 1)
      return;
  }
  for (int i = 0; i < n; ++i)
    res[need_compare[i]] = TRUE;
}
')

基准测试(列的类型对性能至关重要):

> d <- mkDT(3000000, 300, as.integer)
> bench::mark(rowequal(d), rowequalcpp(d), iterations = 10)
# A tibble: 2 x 13
  expression        min  median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result memory time  gc   
  <bch:expr>     <bch:> <bch:t>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list> <list> <lis> <lis>
1 rowequal(d)     100ms   147ms      7.07     398MB     3.03     7     3      991ms <lgl ~ <Rpro~ <ben~ <tib~
2 rowequalcpp(d)  101ms   102ms      9.35     309MB     2.34     8     2      855ms <lgl ~ <Rpro~ <ben~ <tib~
> d <- mkDT(3000000, 300, as.numeric)
> bench::mark(rowequal(d), rowequalcpp(d), iterations = 10)
# A tibble: 2 x 13
  expression          min   median `itr/sec` mem_alloc `gc/sec` n_itr  n_gc total_time result  memory   time 
  <bch:expr>     <bch:tm> <bch:tm>     <dbl> <bch:byt>    <dbl> <int> <dbl>   <bch:tm> <list>  <list>   <lis>
1 rowequal(d)     103.7ms  110.8ms      8.05   349.3MB    0.895     9     1      1.12s <lgl [~ <Rprofm~ <ben~
2 rowequalcpp(d)   26.3ms   27.3ms     36.3     11.4MB    0        10     0    275.2ms <lgl [~ <Rprofm~ <ben~
# ... with 1 more variable: gc <list>

rowequal 大约需要 18 秒,而 rowequalcpp 在我的真实数据中只需要 1.9 秒。虽然 rowequalcpp 对于第一行运行良好,但对于其他行返回 false。 - هنروقتان
@هنروقتان 你好,代码有一个bug。我已经修复了它。请尝试更新后的代码。 - ekoam
谢谢您的更新,它产生了正确的答案,但新版本需要10.4秒。这是预期的吗? - هنروقتان
有趣的基准测试结果,点赞! - ThomasIsCoding
有多少行具有相同的值?我用1百万行相同的值再次检查了这个算法。由于需要访问这些行中的所有条目,它的速度确实变慢了很多。@هنروقتان - ekoam
显示剩余7条评论

2

结构很重要。这里介绍一种使用R语言的矩阵方法,使用matrixStats包(源代码),该包提供了用C语言实现的优化矩阵函数。

x = sample.int(3, size = 303*3e6, replace = T)            
m = matrix(x, ncol = 303, byrow = T)
bench::mark(
  var = matrixStats::rowVars(m, na.rm = T) == 0
)

在我的(肯定不是高性能的)计算机上,对于一个300万行的矩阵,大约需要3.5秒的时间。

但是我的数据结构并不是一个矩阵,将其转换为矩阵也不是很高效。 - هنروقتان
在原帖中,一些答案使用了 as.matrix,然而这并不是成本效益高的选择。请记住,as.matrix 需要额外复制数据框。 - هنروقتان

1

关于这个问题的另一个更新,现在我能够使用InMemoryDatasets将时间缩短到不到一秒钟(实际上不到0.5秒),感谢Julia lang讨论中的讨论

julia> using InMemoryDatasets
julia> df = Dataset(df)
julia> f(x,y) = ismissing(x) || ismissing(y) ? true : x == y
julia> byrow(df, isless, [:v1, :v2, :v3], with = byrow(df, coalesce, :), lt = f)

更新

根据来自讨论区的最新更新,我几乎能够将之前疯狂的记录减少一半:D,即0.27(Julia社区真的非常注重速度

julia> byrow(df, issorted, [:v1, :v2, :v3], lt = !f)

0
关于这个问题的快速更新, 我使用以下函数将时间缩短到约2秒(内存使用不到3 MiB!),尚未使用并行处理:(魔法在于使用@.
julia> f(x,y) = ismissing(x) || ismissing(y) ? true : x == y

julia> function rowequal(df, cols)
           res=ones(Bool, nrow(df))
           for i in 2:length(cols)
               @. res &= ifelse(f(df[!, cols[i-1]], df[!,cols[i]]), true, false)
           end
           res
       end

-3

我建议您使用 python,它有两个很棒的工具适合这种情况,pandas是最受欢迎的数据框架库,polars是世界上最快的数据框架库! (db-benchmark)。

import time
t1=time.time();df.max(axis=1)==df.min(axis=1);t2=time.time()

谢谢您的建议。我知道pandaspolars,它们都是很好的产品,毫无疑问。但是,您在帖子中提到的确切网站建议,如果性能是高优先级,则不应使用pandas,如果效率是高优先级,则不应使用polars,而且,如果我正在寻找速度和效率,则应使用data.table!顺便说一句,您的答案大约花了6秒钟,但我不确定pandas在其余的工作流程中是否像这样好。polars花费了28秒钟。 - هنروقتان

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接