julia - 检查两组是否有非空交集

Question

我写了一个函数intersects有效地检查两个集合是否有一个非空的交集(至少，比检查它们的交集的大小更有效)。

它运行良好，但现在我想将此函数专门用于 DataStructures.IntSet 类型来自 DataStructures 库。我写了下面的函数，它可以工作，但有点乱。

如您所见，当属性 inverse是 true ，我必须否定当前 block 。为了简化代码，我编写了函数 intersects2它做同样的工作，但不需要多个 if/else。

但是这段代码似乎比第一个代码效率低。我不确定，但我认为问题在于每次调用 op_u或 op_v复制参数，如下面的输出所示。

我怎样才能重写这个函数，使它不做任何复制(即不分配)并且没有几个重叠的 if/else？完整的代码、基准和结果可以在下面找到。

using Random
using DataStructures
using BenchmarkTools

elems = [randstring(8) for i in 1:10000]
ii = rand(1:10000, 3000)
jj = rand(1:10000, 3000)


x1 = Set(elems[ii])
y1 = Set(elems[jj])

x2 = Set(ii)
y2 = Set(jj)

x3 = DataStructures.IntSet(ii)
y3 = DataStructures.IntSet(jj)

function intersects(u, v)
    for x in u
        if x in v
            return true
        end
    end
    false
end

function intersects(u::DataStructures.IntSet, v::DataStructures.IntSet)
    ch_u, ch_v = u.bits.chunks, v.bits.chunks
    for i in 1:length(ch_u)
        if u.inverse
            if v.inverse
                if ~ch_u[i] & ~ch_v[i] > 0
                    return true
                end
            else
                if ~ch_u[i] & ch_v[i] > 0
                    return true
                end
            end
        else
            if v.inverse
                if ch_u[i] & ~ch_v[i] > 0
                    return true
                end
            else
                if ch_u[i] & ch_v[i] > 0
                    return true
                end
            end
        end
    end
    false
end

function intersects2(u::DataStructures.IntSet, v::DataStructures.IntSet)
    op_u = if u.inverse x->~x else x->x end
    op_v = if v.inverse x->~x else x->x end

    ch_u, ch_v = u.bits.chunks, v.bits.chunks
    for i in 1:length(ch_u)
        if op_u(ch_u[i]) & op_v(ch_v[i]) > 0
            return true
        end
    end
    false
end


println("Set{String}")
@btime intersects($x1, $y1)

println("Set{Int}")
@btime intersects($x2, $y2)

println("IntSet")
@btime intersects($x3, $y3)
@btime intersects2($x3, $y3)

Set{String}
  190.163 ns (0 allocations: 0 bytes)
Set{Int}
  17.935 ns (0 allocations: 0 bytes)
IntSet
  7.099 ns (0 allocations: 0 bytes)
  90.000 ns (5 allocations: 80 bytes)

Answer 1

您看到的开销可能是由于函数调用开销:op_u没有被内联。

此版本内联正确，性能与 intersects 相同:

julia> function intersects2(u::DataStructures.IntSet, v::DataStructures.IntSet)
           op_u(x) = u.inverse ? ~x : x
           op_v(x) = v.inverse ? ~x : x

           ch_u, ch_v = u.bits.chunks, v.bits.chunks
           for i in 1:length(ch_u)
               if op_u(ch_u[i]) & op_v(ch_v[i]) > 0
                   return true
               end
           end
           false
       end