Проверьте, равны ли все элементы массива Julia

Самый короткий способ, с помощью которого я могу проверить, равно ли все элементы в массиве arr равны all(arr[1] .== arr). Хотя это, конечно, коротко, кажется немного неэлегантным. Есть ли встроенная функция, которая делает это?

Я подозреваю, что есть что-то в строках ==(arr...), но это не работает, потому что оператор == может принимать только два аргумента. Я не уверен, как Джулия разбирает выражения типа arr[1] == arr[2] == arr[3], но есть ли способ адаптировать это к массиву с произвольным количеством элементов?

Ответы

Ответ 1

Отличный вопрос @tparker и отличный ответ @ColinTBowers. Пытаясь задуматься о них обоих, мне пришло в голову попробовать прямолинейную старую школу Джулианского пути-the-the-t20. Результат был быстрее на важном вводе длинного вектора одинаковых элементов, поэтому я добавляю эту заметку. Кроме того, имя функции allequal кажется достаточно подходящим для упоминания. Итак, вот варианты:

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

allequal_2(x) = foldl(==,x)   # another way but doesn't short-circuit :(

@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_2(v)
true

julia> allequal_3(v)
true

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

julia> @btime allequal_2($v);
  10.585 ms (0 allocations: 0 bytes)

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

ОБНОВЛЕНИЕ: Еще один важный момент для тестирования - когда есть возможность короткого замыкания. Таким образом (по запросу в commment):

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_2($v);
  10.325 ms (0 allocations: 0 bytes)

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

Вторая версия allequal_2 плохо работает, так как она не замыкается.

При прочих равных условиях версия for должна быть allequal в базе.

Ответ 2

all - правильное решение, но вы хотите использовать метод all(p, itr) для предиката 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).

Ответ 3

Просто небольшое улучшение: allsame(x) = all(y → y == first(x), x) является более общим, чем allsame(x) = all(y → y == x[1], x), и работает, даже если x является чем-то отличным от AbstractArray, например, генератором.

Ответ 4

У меня недостаточно высокая репутация, чтобы комментировать ответ, предложивший foldl(==, x), но я не думаю, что он работает:

julia> foldl(==, [3,3,3])
false

julia> (3 == 3) == 3
false

julia> 3 == 3 == 3
true

julia> foldl(==, [3,3,1])
true

В приведенном выше примере, foldl(==, [3,3,3]) по существу (3 == 3) == 3, что упрощается до true == 3.