Эффективное удаление элементов из диапазона юнита (Джулия) - PullRequest
Новая
       6

Эффективное удаление элементов из диапазона юнита (Джулия)

3 голосов
/ 18 июня 2020

Я пытаюсь эффективно удалить вектор элементов x из диапазона единиц 1:m, а затем вернуть вектор оставшихся элементов.

Для length(x) намного меньше, чем m .

Вот различные методы, которые я придумал: 

using Distributions

function func1(m, x)
    for i in 1:1000
        collect(setdiff(1:m, x))
    end
end

function func2(m, x)
    for i in 1:1000
        filter(n -> !(n in x), 1:m)
    end
end

function func3(m, x)
    dict = Dict(zip(1:m, 1:m))
    for i in 1:1000
        d = copy(dict)
        for n in x
            delete!(d, n)
        end
        collect(keys(d))
    end
end

m = 10000
x = sample(1:m, 100)

@time func1(m, x)
@time func2(m, x)
@time func3(m, x)

Функция 3 примерно в два раза быстрее, чем функции 1 и 2, однако результат не сортируется, что не является Для меня это нарушает правила, но я бы предпочел, чтобы результат был отсортирован.

Поскольку я удаляю элементы из диапазона единиц, моя интуиция подсказывает мне, что поиск элемента (и удаление) можно выполнить O (1), и, следовательно, должен быть алгоритм, который масштабирует O (len (x)), а не то, что я, кажется, получаю, а это сложность O (m).

1 Ответ

3 голосов
/ 18 июня 2020

Если m намного больше, чем длина x (т.е. вы оставляете большинство элементов), вы можете рассмотреть это: 

function func4(m, x)
    res = Vector{Vector{Int}}(undef, 1000)
    for i in 1:1000
        ind = trues(m)
        ind[x] .= false
        res[i] = findall(ind)
    end
    return res
end

, так как это должно быть быстрее.

(вы могли бы быть быстрее, если бы, например, знали, что x отсортирован и уникален - и, возможно, в вашей исходной задаче вы знаете, что это или снова x достаточно мал, чтобы его сортировка и создание уникального почти не требовалось затрат по сравнению с созданием результата)

Я специально добавил res - и рекомендую вам также добавить его в свои методы. Причина в том, что вы рискуете, что компилятор заметит, что ваша функция не имеет побочных эффектов, и оптимизирует весь l oop как неработающий. Вот пример этого: 

julia> function f()
           for i in 1:1_000_000_000
               s = i
           end
       end
f (generic function with 1 method)

julia> @code_native f()
    .text
; ┌ @ REPL[163]:2 within `f'
    retq
    nopw    %cs:(%rax,%rax)
    nopl    (%rax,%rax)
; └
...