Julia 函数返回数组的非唯一元素

Question

Julia base 具有 unique 函数，该函数返回一个仅包含数组(或任何可迭代对象)的唯一元素的向量。我正在寻找一个 nonunique 函数来返回一个数组，该数组包含在其输入中至少出现两次的所有元素。据我所知 Julia 没有这样的功能，这让我感到有些惊讶。

我的第一次尝试如下:

function nonunique(x::AbstractArray)
    uniqueindexes = indexin(unique(x),x)
    nonuniqueindexes = setdiff(1:length(x),uniqueindexes)
    unique(x[nonuniqueindexes])
end

但是受到 Bogumił Kamiński's 对 indices of unique elements of vector in Julia 的回答的启发，我写了第二个版本:

function nonunique(x::AbstractArray{T}) where T
    uniqueset = Set{T}()
    duplicatedset = Set{T}()
    duplicatedvector = Vector{T}()
    for i in x
        if(i in uniqueset)
            if !(i in duplicatedset)
                push!(duplicatedset, i)
                push!(duplicatedvector, i)
            end
        else
            push!(uniqueset, i)
        end
    end
    duplicatedvector
end

在我的测试中，这个版本快了大约 4 倍。它有一个很好的特性，即返回按每组等效元素的第二个(第一次重复)最初出现的顺序排序。我相信 in 在检查 Set 的成员资格时比 Array 更快，这说明了有两个变量 duplicatedset 和 duplicatedvector 。

我真的有必要“推出自己的” nonunique 函数，第二个版本可以改进吗？

Answer 1

您可以通过对列表进行排序然后搜索重复项来获得更高的性能:

function nonunique2(x::AbstractArray{T}) where T
    xs = sort(x)
    duplicatedvector = T[]
    for i=2:length(xs)
        if (isequal(xs[i],xs[i-1]) && (length(duplicatedvector)==0 || !isequal(duplicatedvector[end], xs[i])))
            push!(duplicatedvector,xs[i])
        end
    end
    duplicatedvector
end

以下是示例结果:

julia> x = rand(1:1000,1000);

julia> using BenchmarkTools

julia> nn = @btime nonunique($x);
  42.240 μs (39 allocations: 71.23 KiB)

julia> nn2s = @btime nonunique2($x);
  26.453 μs (10 allocations: 16.33 KiB)

julia> sort(nn) == sort(nn2s)
true

如果您可以进行就地排序，那就更好了:

function nonunique2!(x::AbstractArray{T}) where T
    sort!(x)
    duplicatedvector = T[]
    for i=2:length(x)
        if (isequal(x[i],x[i-1]) && (length(duplicatedvector)==0 || !isequal(duplicatedvector[end], x[i])))
            push!(duplicatedvector,x[i])
        end
    end
    duplicatedvector
end

这是结果(相同的数据)

julia> nn2 = @btime nonunique2!($x)
  9.813 μs (9 allocations: 8.39 KiB)

julia> sort(nn) == sort(nns)
true