binary - 在 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并获得了相似的性能(550ms)。 Julia 代码可以更快吗？除了使用 StatBases 之外，还有其他计数方法吗？

Answer 1

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

Julia 也不异常(exception)。一些“原始”线性代数被外包给高度优化的库。

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

具体来说，以下尝试通过绕过一般的基于哈希的 Dict 并使用更快的简单哈希和 16 位来优化 32 位单词分布不均匀的文件(例如文本文件)查找表。

在我的测试文件中，它比 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