Оптимизация математических операций с разреженными массивами

У меня есть разреженный массив: term_doc

  • его размер 622256x715 Float64. Это очень скудно:

    • Of its ~444,913,040 cells, only about 22,215 of them normally are nonempty.
    • Из 622256 рядов занято только 4699.
    • хотя из 715 столбцов все заняты.

Оператор, который я хотел бы выполнить, можно описать как возврат нормализованной строки и нормализованной версии этой матрицы.

Я написал наивную неразреженную версию:

function doUnsparseWay()
    gc() #Force Garbage collect before I start (and periodically during). This uses alot of memory
    term_doc

    N = term_doc./sum(term_doc,1)
    println("N done")  

    gc()
    P = term_doc./sum(term_doc,2)    
    println("P done")
    gc()

    N[isnan(N)] = 0.0
    P[isnan(P)] = 0.0

    N,P,term_doc
end

Выполнение этого:

> @time N,P,term_doc= doUnsparseWay()
outputs:
N done
P done
elapsed time: 30.97332475 seconds (14466 MB allocated, 5.15% gc time in 13 pauses with 3 full sweep)

Это довольно просто. Жрет память, и вылетает, если сборка мусора не происходит в нужное время (таким образом я вызываю это вручную). Но это достаточно быстро

Я хотел заставить его работать на разреженной матрице. Чтобы не пережевывать мою память, и потому что логически это более быстрая операция - нужно оперировать меньше клеток.

Я следовал предложениям из этот пост и из страница документации.

function doSparseWay()
    term_doc::SparseMatrixCSC{Float64,Int64}

    N= spzeros(size(term_doc)...)
    N::SparseMatrixCSC{Float64,Int64}

    for (doc,total_terms::Float64) in enumerate(sum(term_doc,1))
        if total_terms == 0
            continue
        end
        @fastmath @inbounds N[:,doc] = term_doc[:,doc]./total_terms
    end
    println("N done")  

    P = spzeros(size(term_doc)...)'
    P::SparseMatrixCSC{Float64,Int64}

    gfs = sum(term_doc,2)[:]
    gfs::Array{Float64,1} 


    nterms = size(term_doc,1)
    nterms::Int64 
    term_doc = term_doc'

    @inbounds @simd for term in 1:nterms
        @fastmath @inbounds P[:,term] = term_doc[:,term]/gfs[term]
    end
    println("P done")
    P=P'


    N[isnan(N)] = 0.0
    P[isnan(P)] = 0.0

    N,P,term_doc
end

Это никогда не завершается. Он доходит до вывода «N Done», но никогда не выводит «P Done». Я оставил его включенным на несколько часов.

  • Как оптимизировать его, чтобы он мог завершиться в разумные сроки?
  • Или, если это невозможно, объясните, почему.

optimization julia sparse-matrix sparse-array
person Lyndon White    schedule 23.02.2015    source источник
comment
К вашему сведению. В коде, который я видел, разреженные матрицы вызывают функцию хеширования (не встроенную) для преобразования виртуальных координат в абсолютные. Разница в скорости доступа к элементам в разреженных и нормальных матрицах достаточно велика. Если вам нужна скорость, найдите способ избежать использования разреженных матриц.   -  person BitBank    schedule 23.02.2015

Ответы (1)


arrow_upward
1
arrow_downward

Во-первых, вы делаете term_doc глобальной переменной, что является большой проблемой для производительности. Передайте это как аргумент, doSparseWay(term_doc::SparseMatrixCSC). (Аннотация типа в начале вашей функции не делает ничего полезного.)

Вы хотите использовать подход, аналогичный ответу walnuss:

function doSparseWay(term_doc::SparseMatrixCSC)
    I, J, V = findnz(term_doc)
    normI = sum(term_doc, 1)
    normJ = sum(term_doc, 2)
    NV = similar(V)
    PV = similar(V)
    for idx = 1:length(V)
        NV[idx] = V[idx]/normI[J[idx]]
        PV[idx] = V[idx]/normJ[I[idx]]
    end
    m, n = size(term_doc)
    sparse(I, J, NV, m, n), sparse(I, J, PV, m, n), term_doc
end

Это общий шаблон: когда вы хотите что-то оптимизировать для разреженных матриц, извлеките I, J, V и выполните все свои вычисления на V.

person tholy    schedule 24.02.2015