Блог

Ключевым моментом является то, что массив отсортирован и может содержать недостающие элементы. Я подозреваю, length(unique(arr)) что это не самый быстрый.

Мне интересно, существует ли предварительно созданная функция, которая может справиться с таким случаем?

Реализация unique(itr) Джулии довольно эффективна для произвольных коллекций — время масштабируется примерно линейно с размером входной коллекции. Однако, поскольку он создает два справочных словаря, чтобы помочь определить, какие элементы он видел раньше, объем выделяемой памяти масштабируется в соответствии с количеством уникальных элементов в коллекции. Если вы знаете, что входная коллекция уже отсортирована, вы можете воспользоваться этим, чтобы уменьшить распределение и значительно ускорить подсчет:

 function nunique(a)
    last = first(a)
    n = 1
    for x in a
        if isless(last, x)
            n  = 1
            last = x
        end
    end
    n
end

r = Array{Union{Missing,Int64}}(rand(1:10000, 100000))  # 100_000 elements, 10_000 unique
r[rand(1:length(r), 100)] .= missing                    # 100 missing elements
sort!(r)

@time length(unique(r))
# 0.002156 seconds (37 allocations: 503.781 KiB)
# 10001

@time nunique(r)
# 0.000464 seconds (1 allocation: 16 bytes)
# 10001
  

Насколько я могу судить, нет встроенной функции, которая оптимизирует для особого случая отсортированных входных массивов.

Эта функция по-прежнему будет масштабироваться во времени, как и размер входной коллекции, но она выполняет только одно (!) выделение, поэтому она сбрасывает все накладные расходы, связанные с созданием поисковых словарей.

Конечно, эта функция будет работать только в том случае, если массив уже отсортирован в соответствии с isless функцией. Вы можете добавить проверку во время итерации, чтобы прервать и переключиться на length(unique(itr)) версию, если необходимо:

 function nunique2(a)
    last = first(a)
    n = 1
    for x in a
        if isless(last, x)
            n  = 1
            last = x
        elseif !isequal(last, x)
            return length(unique(a))
        end
    end
    n
end

@time nunique2(r)
# 0.000256 seconds (1 allocation: 16 bytes)
# 10001

using Random
shuffle!(r)
@time nunique2(r)
# 0.002801 seconds (37 allocations: 503.781 KiB)
# 10001
  

Как и во всех микробенчмарках, YMMV.

У меня есть параллельное решение, но, к сожалению, оно всего на 30% быстрее в 6 потоках

 function nunique(v)
    @assert length(v) > 0
    cnt = 1
    lasta::eltype(v) = first(v)
    @inbounds for newa1 in v
        if !isequal(newa1, lasta)
            cnt  = 1
            lasta = newa1
        end
    end
    cnt
end

""" Parallelized version """
function pnunique(v)
    nt = Threads.nthreads()
    lo::Vector{Int} = collect(0:div(length(v), nt):length(v)-1)
    hi::Vector{Int} = lo[2:end]
    hi[end] = length(v)
    lo = lo .  1

    nu = Vector{Int}(undef, nt)

    Threads.@threads for i in 1:nt
        @inbounds nu[i] = nunique(@view v[lo[i]:hi[i]])
    end

    res = sum(nu)
    for j in 1:nt-1
        @inbounds res -= v[hi[j]] == v[lo[j 1]]
    end

    res
end