高效地从单位范围（Julia）中删除元素

Question

我想要高效地从单元范围 1:m 中删除一个元素向量x，然后返回其余元素的向量。

针对 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)

第三个函数的运行速度大约是第一个和第二个函数的两倍，但结果并没有排序，这对我来说不是致命问题，但如果结果能排序我会更喜欢。

因为我正在从一个单位范围内删除元素，我的直觉告诉我查找（和删除）元素可以实现O(1)，因此应该有一个算法可以按比例扩展O(len(x)), 而我似乎得到的是O(m)复杂度。

- Set

---

循环1到1000的目的是什么？它似乎没有实现任何功能。如果它是为了基准测试，请将其删除并改用BenchmarkTools。最好编写代码以确切地执行所需的操作，然后确保基准测试处理重复评估和统计数据，这正是BenchmarkTools为您完成的工作。 - DNF

@DNF 是的，那是为了进行基准测试，很高兴知道有 BenchmarkTools 这个工具，我将来一定会使用它！ - Set

Answer 1

如果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，建议您在自己的方法中也添加它。原因是您有风险让编译器注意到您的函数没有副作用，并将整个循环优化为无操作。以下是这种情况发生的示例：

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)
; └

- Bogumił Kamiński

---

这真是太棒了。正是我在寻找的东西，谢谢！ - Set