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

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

> 6 in [4,6,5]
true

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

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

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

Источник

7 ответов

Решение

Для третьего условия т.е. вектора [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
Источник

Я думаю, что стоит упомянуть, что в Julia 1.0 у вас есть функция issubset

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

Вы также можете довольно удобно назвать это, используя \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)
Источник

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

Обратите внимание, что теперь вы можете векторизовать in с точкой:

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

и цепочка с all чтобы получить ответ:

julia> all(in([4,6,5]).([4, 6]))
true
Источник

В библиотеке 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

Это молниеносно и почти не требует памяти - Джулияviewлегкий и эффективный. И, как всегда с Джулией, решение обычно состоит в том, чтобы просто определить больше функций.

Источник

Я использовал это недавно, чтобы найти подпоследовательности в массивах целых чисел. Это не так хорошо и не так быстро, как @ Скотт 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
Источник

Вот более современная реализация с использованием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
Источник
Другие вопросы по тегам