检查Julia数组中的所有元素是否相等

Question

检查Julia数组中的所有元素是否相等

26

我能想到的最简短的测试数组 arr 中所有元素是否相等的方法是 all(arr[1] .== arr)。虽然这样做很短，但似乎有点不够优雅。是否有内置函数可以完成此操作？

我猜想应该有类似于 ==(arr...) 的函数，但这样做行不通，因为 == 运算符只能接受两个参数。我不确定 Julia 如何解析诸如 arr[1] == arr[2] == arr[3] 的表达式，但是否有一种方法可以将其适配到具有任意数量元素的数组上呢？

- tparker

1

此函数自Julia Base库v1.8版本起已实现为allequal; 参见https://docs.julialang.org/en/v1/base/collections/#Base.allequal - Jeff

4个回答

18

很棒的问题@tparker和很好的答案@ColinTBowers。在尝试思考它们两个时，我想到了尝试直截了当的老派Julian方式-for-loop。结果在一长串相同元素的重要输入上更快，因此我添加了这个注释。另外，函数名称allequal似乎足够恰当，值得一提。所以这里是不同的变体:

allequal_1(x) = all(y->y==x[1],x)

# allequal_2(x) used to be erroneously defined as foldl(==,x)   

@inline function allequal_3(x)
    length(x) < 2 && return true
    e1 = x[1]
    i = 2
    @inbounds for i=2:length(x)
        x[i] == e1 || return false
    end
    return true
end

还有基准测试：

julia> using BenchmarkTools

julia> v = fill(1,10_000_000);  # long vector of 1s

julia> allequal_1(v)
true

julia> allequal_3(v)
true

julia> @btime allequal_1($v);
  9.573 ms (1 allocation: 16 bytes)

julia> @btime allequal_3($v);
  6.853 ms (0 allocations: 0 bytes)

更新：另一个重要的基准测试案例是当存在短路机会时。因此（如评论中请求）：

julia> v[100] = 2
2

julia> allequal_1(v),allequal_2(v),allequal_3(v)
(false, false, false)

julia> @btime allequal_1($v);
  108.946 ns (1 allocation: 16 bytes)

julia> @btime allequal_3($v);
  68.221 ns (0 allocations: 0 bytes)

所有事情都一样的情况下，for版本应该在基础版本中变为allequal。

- Dan Getz

我非常喜欢Julia Base的构建方式，它通过组合和构建通用函数来使许多实现变得高级和抽象。例如，看看reduce.jl。我希望allequal(虽然它实际上不应该在Base中)能够像这样，基于一些通用结构（如all）构建，而不是制作一些超优化的自定义循环。这样，改进all的性能将改进依赖它的每个函数的性能。 - DNF

@DNF 你说得对，它不会短路（与我的回忆不符 - 已修正答案）。但是也许（并且符合您评论中的基本哲学），应该定义一个短路的 foldl（和其他缩减操作），基于 op 的 零元素。使用另一种带有零元素定义的 foldl 签名，或者只是针对常见二进制操作的专用签名。 - Dan Getz

1

也许值得添加一个基准测试，使用同一台机器进行长向量测试，其中早期元素之一不同，以查看缺乏短路的影响有多大。 - tparker

2

请注意，allequal_2的最优性并不重要，因为它是不正确的！例如，allequal_2([0,0,0])的计算结果为false。 - banbh

1

@banbh 感谢您注意到这个问题。我会编辑答案。可能是因为 true == 1 和 false == 0 的C语言起源有些可疑，所以我混淆了。 - Dan Getz

显示剩余4条评论

15

仅有轻微的改进：allsame(x) = all(y -> y == first(x), x) 比 allsame(x) = all(y -> y == x[1], x) 更通用，即使当x不是一个AbstractArray时仍然有效，例如生成器。

- Pablo San-Jose

2

特别是，它适用于具有非标准索引（例如基于零的）的数组。顺便说一句，如果我没记错的话，你可以写==(first(x))而不是y -> y == first(x)。这个是新的。 - DNF

生成器是什么？ - tparker

2

这是一个Julia对象，可以迭代生成值，而无需为它们分配容器或将它们写入内存。例如，像c = [x^2 for x in 1:100]这样的推导式会分配一个包含前100个整数平方的向量。相比之下，生成器g = (x^2 for x in 1:100)会按顺序生成相同的值，而不会分配向量。您可以执行类似for s in g; $show s; end的操作来打印它们。生成器被证明是非常强大的性能工具。 - Pablo San-Jose

0

从Julia 1.8版本开始，你可以使用以下任一方式：

allequal(arr)

或者在1.8之前，你可以简单地检查一下：

length(unique(arr)) == 1

- mossr

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Colin T Bowers · Accepted Answer

all 是正确的解决方案，但如果你想要针对谓词 p 和可迭代对象 itr 使用方法 all(p, itr)，因为它将使用短路行为（一旦发现一个 false 就停止）。所以：

all(y->y==x[1], x)

要看到差别，您可以运行以下小速度测试：

for n = 100000:250000:1100000
    x = rand(1:2, n);
    @time all(x .== x[1]);
    @time all(y->y==x[1], x);
    println("------------------------")
end

忽略第一次迭代，因为它是编译时间。

  0.000177 seconds (22 allocations: 17.266 KiB)
  0.006155 seconds (976 allocations: 55.062 KiB)
------------------------
  0.000531 seconds (23 allocations: 47.719 KiB)
  0.000003 seconds (1 allocation: 16 bytes)
------------------------
  0.000872 seconds (23 allocations: 78.219 KiB)
  0.000001 seconds (1 allocation: 16 bytes)
------------------------
  0.001210 seconds (23 allocations: 108.781 KiB)
  0.000001 seconds (1 allocation: 16 bytes)
------------------------
  0.001538 seconds (23 allocations: 139.281 KiB)
  0.000002 seconds (1 allocation: 16 bytes)

第一个解决方案明显是O(n)，而第二个方案最好是O(1)，最坏情况下是O(n)(取决于itr的数据生成过程)。