Джулия: содержит ли массив определенный суб-массив

В julia мы можем проверить, содержит ли массив значение, например: 

> 6 in [4,6,5]
true

Однако это возвращает false, при попытке проверить под-массив в определенном порядке: 

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

Каков правильный синтаксис для проверки того, существует ли в массиве определенный суб-массив?

3 3
arrays julia-lang sub-array

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
3

Требуется немного кода, чтобы сделать функцию, которая хорошо работает, но это намного быстрее, чем версия 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)
5

Недавно я использовал это для поиска подпоследовательностей в массивах целых чисел. Это не так хорошо и не так быстро, как у @scott'S 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
1