在 Julia 中进行频率计数的最佳方法

Question

我有一个 binary file，我正在用 julia 进行频率计数。

using PyPlot
import StatsBase
const stb=StatsBase

function getall(fname)
    b=Mmap.mmap(fname,Vector{Int32})
    #a=open(fname)
    #b=reinterpret(Int32,readbytes(a))
    d=stb.countmap(b)
    x=collect(keys(d)) & 0x7ffffff
    y=collect(values(d))
    #plot(x,y,"r^")
    #xlim(0,3000)
    #ylim(0,3e5)
    #grid("on")
    return x,y
end

在 python 中，我使用 numpy.unique、numpy.memmap 并获得相似的性能（550 毫秒）。 Julia 代码可以更快吗？有没有其他方法可以代替使用 StatBases 来计数。

Answer 1

countmap操作是任何编程语言中的标准操作。此外，它也是"raw"，就像排序一样，这意味着它必须对输入数据进行基本的流行操作。这种操作很难优化，因为它们在大多数语言中的完成方式类似 - 如果它们在源语言中不够快，则会调用专门的例程（读 C/Cpp 写）。

茱莉亚也不例外。一些 "raw" 线性代数外包给高度优化的库。

为了使这个答案富有成效（并且 Julia 积极），有一些算法方法可以处理输入的特殊情况，这将产生比一般算法更快的速度（即使用基于哈希的计数器 Dict）。在 Julia 中编写这些特殊情况的能力代表了它的速度和解决所谓的 2 种语言问题的尝试。

具体来说，以下尝试通过绕过基于散列的通用 Dict 并使用更快的简单散列和 16 - 位查找 table.

在我的测试文件中，它比 OP 中的 countmap 实现实现了 10% 的加速。适度的改进 :)。

using DataStructures
function getall4(fname)
    b=Mmap.mmap(fname,Vector{UInt32})
    c = zeros(Int,2^16)
    v = Array(UInt16,2^16)
    l = length(b)
    for i=1:l
        d1 = b[i]&0xFFFF
        d2 = d1 $ (b[i]>>16)
        if d1==v[d2+1]
            c[d2+1] += 1
        else
            c[d2+1] -= 1
        end
        if (c[d2+1]<=0)
            c[d2+1] = 1
            v[d2+1] = d1
        end
    end
    cc = DataStructures.counter(UInt32)
    fill!(c,0)
    for i=1:l
        d1 = b[i]&0xFFFF
        d2 = d1 $ (b[i]>>16)
        if v[d2+1]==d1
            c[d2+1] += 1
        end
    end
    for i=1:l
        d1 = b[i]&0xFFFF
        d2 = d1 $ (b[i]>>16)
        if !(v[d2+1]==d1)
            push!(cc,b[(i+1)>>1])
        end
    end
    x = UInt32[]
    y = Int[]
    for i=1:(1<<16)
        if c[i]>0
            push!(x,(UInt32(i)<<16)+v[i])
            push!(y,c[i])
        end
    end
    append!(x,collect(keys(cc.map)))
    append!(y,collect(values(cc.map)))
    x,y
end

在 Julia 中进行频率计数的最佳方法

Best way to do frequency counting in Julia

binary

statistics

counter

julia