在朱莉娅做频率计数的最佳方法

Question

我有一个binary file，我正在茱莉亚做频率计数。

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积极），我们有算法方法来处理输入的特殊情况，这会比一般算法产生加速（即使用基于散列的计数器Dict）。在Julia中编写这些特殊情况的能力代表了它的速度和解决所谓的2语言问题的尝试。

具体来说，下面试图优化32位字的不均匀分布的文件（例如文本文件），通过绕过一般的基于散列的Dict并使用更快的简单散列和16位散列，位查找表。

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