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

Question

我有一个二进制文件,我正在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操作是任何编程语言的标准操作.此外,它也是"原始的",就像排序一样,这意味着它必须对输入数据进行基本的流行操作.这种操作难以优化,因为它们在大多数语言中都是类似的 - 如果它们在源语言中不够快,则会调用专门的例程(读取C/Cpp编写).

朱莉娅也不例外.一些"原始"线性代数外包给高度优化的库.

为了对这个答案进行有效的(和朱莉亚正面)旋转,有一些算法方法可以处理输入的特殊情况,这种情况会产生一般算法的加速(即使用基于散列的计数器Dict).在Julia中编写这些特殊情况的能力代表了它的速度和尝试解决所谓的双语问题.

具体地说,下面尝试通过绕过一般的基于散列的Dict并使用更快的简单散列和16位查找表来优化具有32位字的不均匀分布的文件(例如文本文件).

在我的测试文件中,它比countmapOP中的实现速度提高了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