2017-11-30 49 views
7

arr dizisindeki tüm öğelerin eşit olup olmadığını test etmenin en kısa yolu all(arr[1] .== arr). Bu kesinlikle kısa olsa da, biraz yetersiz görünüyor. Bunu yapan yerleşik bir işlev var mı?Bir Julia dizisinin tüm öğelerinin eşit olup olmadığını kontrol edin

==(arr...) satırlarında bir şey olduğundan şüpheleniyorum, ancak bu işe yaramaz çünkü == işleci yalnızca iki bağımsız değişken alabilir. Julia'nın arr[1] == arr[2] == arr[3] gibi ifadeleri nasıl ayrıştırdığından emin değilim, fakat bunu keyfi sayıda eleman içeren bir diziye uyarlamanın bir yolu var mı?

cevap

7

Harika bir soru @tparker ve mükemmel cevap @ColinTBowers. İkisini de düşünmeye çalışırken, düz-ileri eski-okul Julian-of-the-for -loop'u denememi sağladı. Sonuç, aynı elemanların uzun bir vektörünün önemli girdilerinde daha hızlıydı, bu yüzden bu notu ekliyorum. Ayrıca, allequal işlev adı, belirtilmesi için yeterli görünüyor.

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 

Ve kriter: Yani burada varyantlardır

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) 

GÜNCELLEME: Bir kısa devre fırsat varken kriter için bir diğer önemli durumdur. Yani (aynı COMMMENT istenilen):

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) 

ikinci versiyonu allequal_2 ücretleri kötü değil kısa devre yaptığı gibi.

Her şey eşittir, for sürümü Base'de allequal olmalıdır.

+0

Teşekkürler, 'foldl' tam aradığım işlevdir.Üçüncü uygulamanın neden daha hızlı olduğu için 'inbounds'un ötesinde bir sebep olduğunu düşünüyor musunuz? – tparker

+0

Julia Base'in, genel işlevlerin bir araya getirilmesi ve üzerine inşa edilmesiyle nasıl inşa edildiğini gerçekten çok seviyorum. Örneğin, 'reduction.jl' dosyasına bakın. Bir “allequal” ın (aslında Base'de olmamasına rağmen) bazı hiper-optimize özel döngü yapmak yerine, “all” gibi bazı jenerik yapıların üzerine inşa edilmesini tercih ederim. Bu şekilde, "herkesin" performansının iyileştirilmesi, ona bağlı olan her işlevi geliştirecektir. – DNF

+0

BTW. 'foldl' _not_ kısa devre yapıyor, bu yüzden burada kesinlikle uygun değil. – DNF

9

all doğru çözümdür, ama kısa devre davranışı (bulunduğunda bir false en kısa sürede kırmak) istihdam sağlayacak beri, yüklem p ve iterable itr yöntemi all(p, itr) istiyorum. Yani: derleme süresi zamanlama olarak

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

ilk yineleme Ignore:

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

farkı görmek için aşağıdaki küçük hız testi çalıştırabilirsiniz.

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) 

birinci solüsyonu, ikinci O ise, tabii ki oldukça O (n) 'nin (1) en iyi ve O (n) en kötü (itr için veri üreten sürece bağlı olarak) en.

+0

Vay, harika cevap! Her ne kadar el ile ilk elden karşılaştırmadan daha kompakt bir sözdizimi olmadığına şaşıyorum. – tparker

+2

@tparker 'allsame (x) = tümü (y-> y == x [1], x)'. Dil ile ilgili güzel şeylerden biri, bu kısayolları kendiniz yazmak ve kendi çekirdek paketinizde oturtmaktır. Daha genel olarak, Julia topluluğunda 'Base'i mümkün olduğu kadar trim tutmak için güçlü bir itme vardır. Her tür işlem için güzel, basit, işlev isimleri paketler halinde olabilir ve eğer yeterli kişi varsa, paket popüler hale gelir ve böyle devam eder ... ama 'Base' yalın ve hızlı kalır. –

+0

Bu boş dizide bile işe yaradığı güzel: 'allsame ([]) == true', olması gerektiği gibi boş bir dizinin içinde farklı elemanlar olmadığından. – mschauer

İlgili konular