Julia：一个数组是否包含特定的子数组

Question

在Julia语言中，我们可以检查一个数组是否包含某个值，方法如下：

> 6 in [4,6,5]
true

然而，当尝试按特定顺序检查子数组时，这将返回false：

> [4,6] in [4,6,5]
false

如何正确使用语法来验证是否存在特定的子数组？

- Nicky Feller

---

问题的第二个结果与其描述不符。它是一个由 4 和第一个结果组成的元组。 - Dan Getz

包Iterators.jl还提供了一个有用的函数subsets，您可以编写[4,6] in subsets([4,5,6])。 - Gnimuc

那样无法得到正确的结果，即使得到了，其扩展性也很差（我使用不同长度的带有 Int64 的向量对所有这些进行了基准测试）。 - Scott Jones

我误解了问题，对于那些想要检查数组A的每个元素（不考虑A作为一个整体序列）是否包含在另一个数组B中的人来说，setdiff(A, B) |> isempty就足以完成这项工作。 - Gnimuc

Answer 1

我认为值得一提的是，在Julia 1.0中你有一个名为issubset的函数。

> issubset([4,6], [4,6,5])
true

您也可以使用 latex 的符号\subseteq来方便地调用它。

> [4,6] ⊆ [4,6,5]
true

这看起来对我来说很优化：

> using Random

> x, y = randperm(10^3)[1:10^2], randperm(10^3);

> @btime issubset(x, y);
16.153 μs (12 allocations: 45.96 KiB)

- rodrigolece

---

哇，非常好，这应该是被选中的答案。在 Julia 1.2.0 中仍然有效。 - Allan Karlson

请注意，子集和子数组是不同的概念。[6,4]不是 [4,6,5] 的子数组。 - Cameron Bieganek

Answer 2

写出一个性能良好的函数需要一些代码，但这比上面的 issubvec 版本要快得多：

function subset2(x,y)
    lenx = length(x)
    first = x[1]
    if lenx == 1
        return findnext(y, first, 1) != 0
    end
    leny = length(y)
    lim = length(y) - length(x) + 1
    cur = 1
    while (cur = findnext(y, first, cur)) != 0
        cur > lim && break
        beg = cur
        @inbounds for i = 2:lenx
            y[beg += 1] != x[i] && (beg = 0 ; break)
        end
        beg != 0 && return true
        cur += 1
    end
    false
end

注意：如果该函数实际返回子数组开始的位置（如果找到），或者如果没有找到则返回0，那么它将更加有用，类似于findfirst/findnext函数。

时间信息（第二个是使用我的subset2函数）：

  0.005273 seconds (65.70 k allocations: 4.073 MB)
  0.000086 seconds (4 allocations: 160 bytes)

- Scott Jones

---

第一个 @time 的结果（对于 issubvec）看起来可能包含了编译 - 对于如此简单的调用来说，它是一个过于异常的值。你能重新检查一下（在计时之前进行一次编译运行）吗？ - Dan Getz

不是异常值 - 当然在运行之前我已经编译过了（没有使用@time宏）。我还测试了各种长度，我展示的那个是使用长度为64K的向量进行测试，搜索一个长度为4的序列（向量中的最后4个值）。issubvec似乎具有O(n)的分配，其中n是y的长度。 - Scott Jones

也许最好将其发布为gist，并在此处放置链接？ - Scott Jones

就让它保持现状吧。实际上，subset2 更加优化（如果想要推进，还有更多的优化选项），但这可能会是另一个讨论的议题。 - Dan Getz

是的，至少对于需要快速解决问题的人来说，这是一个起点。我认为你的 issubvec 函数说明了标准库中数组函数可以做些什么。 - Scott Jones

Answer 3

针对第三个条件，即向量[4,6]作为子向量出现在4,6,5中，建议使用以下函数：

issubvec(v,big) = 
  any([v == slice(big,i:(i+length(v)-1)) for i=1:(length(big)-length(v)+1)])

针对第二个条件，即为els向量中的每个元素给出一个布尔值，指示其是否出现在set向量中，建议采用以下方法：

function vecin(els,set)
  res = zeros(Bool,size(els))
  res[findin(els,set)]=true
  res
end

使用OP中的向量，结果如下：

julia> vecin([4,6],[4,6,5])
2-element Array{Bool,1}:
 true
 true

julia> issubvec([4,6],[4,6,5])
true

- Dan Getz

---

issubvec确实会返回正确的结果，但它也不是非常高效，因为它会进行许多分配。使用@time来查看性能是否因过度分配而受到影响是一个好主意。 - Scott Jones

issubvec 显然没有经过优化，@ScottJones，但它的逻辑非常清晰 - 这是我的意图。你编写的函数更好（甚至存在更优化的搜索子字符串/子向量算法）。我认为这样的通用子向量函数可能适合于 Base（与字符串函数类似的名称）。 - Dan Getz

实际上，我曾经为issubvec的逻辑而苦苦挣扎，结合了数组推导和使用slice和any函数。这并不是批评，我喜欢看到Julia的数组函数可以做出强大的事情，但是从C/C++/Java等语言转换过来，我必须扭曲我的大脑才能理解它。此外，我发现像那样简短而甜美的代码通常无法扩展，并且我是一个性能专家。 - Scott Jones

Answer 4

请注意，现在您可以使用点号对in进行向量化处理：

julia> in([4,6,5]).([4, 6])
2-element BitArray{1}:
 true
 true

并使用all链来获取您的答案：

julia> all(in([4,6,5]).([4, 6]))
true

- Adrien

---

不错。如果你想避免重复的项怎么办？例如，all(in([4,6,5]).([4, 6, 6])) 应该返回 false，而不是 true。 - Timothée HENRY

Answer 5

目前Julia库中没有标准的函数来确定一个特定的序列是否出现为另一个序列的子序列。可能是因为这实际上是一个相当棘手的问题（也称为字符串搜索算法），如何解决取决于您是否会重复搜索、是否要进行多个匹配、有多个模式、想要模糊匹配等。

这里提供的其他答案都是合理的，但有些过时了，而Julia已经得到了改进，我想提供一个稍微更加惯用的解决方案。

function issubarray(needle, haystack)
    getView(vec, i, len) = view(vec, i:i+len-1)
    ithview(i) = getView(haystack, i, length(needle))
    return any(i -> ithview(i) == needle, 1:length(haystack)-length(needle)+1)
end

这是闪电般的快速，并且几乎不需要内存 - Julia的view轻巧高效。而且，与Julia一贯的做法一样，解决方案通常只需定义更多的函数。

- Harry Ray

Answer 6

我最近使用了这个方法来查找整数数组中的子序列。它不如@scott的subset2(x,y)好，也不够快，但它会返回索引。

function findsequence(arr::Array{Int64}, seq::Array{Int64})
    indices = Int64[]
    i = 1
    n = length(seq)
    if n == 1
        while true
            occurrence = findnext(arr, seq[1], i)
            if occurrence == 0
                break
            else
                push!(indices, occurrence)
                i = occurrence +1
            end
        end
    else
        while true
            occurrence = Base._searchindex(arr, seq, i)
            if occurrence == 0
                break
            else
                push!(indices, occurrence)
                i = occurrence +1
            end
        end
    end
    return indices
end

julia> @time findsequence(rand(1:9, 1000), [2,3])
    0.000036 seconds (29 allocations: 8.766 KB)
    16-element Array{Int64,1}:
   80
  118
  138
  158
  234
  243
  409
  470
  539
  589
  619
  629
  645
  666
  762
  856

- daycaster

---

是的，那非常有用。我之前也不知道 Base._searchindex，我得进行基准测试！我认为使用迭代器也很好，这样就不会创建一个潜在很大（可能达到 seq 的长度）的向量。 - Scott Jones

Answer 7

这里是一个更现代化的实现，使用findall

function issubsequence(A, B)
    B1inA = findall(isequal(B[1]), A) # indices of the first element of b occuring in a
    matchFirstIndex = [] # Saves the first index in A of the occurances
    for i in B1inA
        if length(A[i:end]) < length(B) continue end
        if A[i:i + length(B) - 1] == B
            push!(matchFirstIndex, i)
        end
    end
    return matchFirstIndex
end

我得到了与 @daycaster 相似的运行时

@time issubsequence(rand(1:9, 1000), [2,3])
  0.000038 seconds (111 allocations: 20.844 KiB)
7-element Vector{Any}:
  57
 427
 616
 644
 771
 855
 982

- b-fg