Проверьте, имеют ли два набора непустое пересечение - PullRequest
Новая
       5

Проверьте, имеют ли два набора непустое пересечение

6 голосов
/ 16 февраля 2020

Я написал функцию intersects, которая эффективно проверяет, имеют ли два набора непустое пересечение (по крайней мере, более эффективно, чем проверка размера их пересечения).

Работает хорошо, но теперь я хотел бы специализировать эту функцию для типа DataStructures.IntSet из библиотеки DataStructures. Ниже я написал функцию, которая работает, но немного запутанно.

Как видите, когда атрибут inverse равен true, я должен отрицать текущий фрагмент. В попытке упростить код, я написал функцию intersects2, которая выполняет ту же работу, но без необходимости в умножении, если / else.

Но этот код выглядит менее эффективным, чем первый. Я не уверен, но я думаю, что проблема в том, что каждый вызов op_u или op_v копирует параметр, как показано в выходных данных ниже.

Как я могу переписать эту функцию так, чтобы она выполнялась не делать никаких копий (ie. без выделения) и без нескольких замаскированных если / еще? Полный код, тесты и результаты приведены ниже. 

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)

Ответы [ 2 ]

3 голосов
/ 16 февраля 2020

Переполнение, которое вы видите, вероятно, связано с издержками при вызове функции: 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
1 голос
/ 16 февраля 2020

Вы могли бы избежать вложенности также с помощью чего-то подобного, это также немного быстрее, чем ваш intersects(u::DataStructures.IntSet, v::DataStructures.IntSet) метод, из-за @inbounds: 

function intersects4(u::DataStructures.IntSet, v::DataStructures.IntSet)
    ch_u, ch_v = u.bits.chunks, v.bits.chunks
    for i in eachindex(length(ch_u) > length(ch_v) ? ch_u : ch_v)
        @inbounds if (u.inverse && v.inverse && ~ch_u[i] & ~ch_v[i] > 0) ||
           (u.inverse && ~ch_u[i] & ch_v[i] > 0) ||
           (v.inverse && ch_u[i] & ~ch_v[i] > 0) ||
           (ch_u[i] & ch_v[i] > 0) 
            return true
        end
    end
    return false
end

Вы уверены, что есть не может быть BoundsError, если длина ch_u больше, чем ch_v, а функция запускает весь l oop? Я сделал for i in eachindex(length(ch_u) > length(ch_v) ? ch_u : ch_v) на всякий случай, потому что я не проверил вашу функцию полностью.

Отличный ответ @ Дэвид Варела (я назову его функцию intersects3 ), вы можете получить даже немного быстрее, чем intersect4 выше, если убедитесь, что не будет BoundsError и использовать @inbounds, например: 

function intersects5(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 eachindex(length(ch_u) > length(ch_v) ? ch_u : ch_v)
        @inbounds if op_u(ch_u[i]) & op_v(ch_v[i]) > 0
            return true
        end
    end
    return false
end

julia> begin
           @btime intersects($x3, $y3)   # nested ifs and bound checks
           @btime intersects2($x3, $y3)  # with non inline-able ops
           @btime intersects3($x3, $y3)  # David's improvement
           @btime intersects4($x3, $y3)  # without ifs and with @inbounds
           @btime intersects5($x3, $y3)  # David's improvement with @inbounds
       end
7.184 ns (0 allocations: 0 bytes)
87.633 ns (5 allocations: 80 bytes)
6.500 ns (0 allocations: 0 bytes)
3.763 ns (0 allocations: 0 bytes)
3.079 ns (0 allocations: 0 bytes)

Также в вашем коде: 

op_u = if u.inverse x -> ~x else x -> x end

Вы могли бы также сделать: 

op_u = u.inverse ? (~) : identity

Поскольку оператор ~ является просто функцией, а функция identity уже существует, в любом случае, ответ Дэвида лучше (потому что это тоже не будет встроенным), и intersects5 - самый быстрый и краткий из всех, просто хотел упомянуть об этом.

...