朱莉娅:基本功能比同类功能快10,000倍

Question

我正在玩朱莉娅的十进制到二进制转换器'bin()',希望提高性能.我需要使用BigInts来解决这个问题,并在我的文件中使用bigInt调用bin()输出正确的二进制表示; 但是,调用类似于bin()函数的函数会花费一分钟的时间,而bin()则需要大约0.003秒.为什么会有这么大的差异？

function binBase(x::Unsigned, pad::Int, neg::Bool)
    i = neg + max(pad,sizeof(x)<<3-leading_zeros(x))
    a = Array(Uint8,i)
    while i > neg
        a[i] = '0'+(x&0x1)
        x >>= 1
        i -= 1
    end
    if neg; a[1]='-'; end
    ASCIIString(a)
end



function bin1(x::BigInt, pad::Int)
    y = bin(x)
end



function bin2(x::BigInt, pad::Int,a::Array{Uint8,1}, neg::Bool)
    while pad > neg
        a[pad] = '0'+(x&0x1)
        x >>= 1
        pad -= 1
    end
    if neg; a[1]='-'; end
    ASCIIString(a)
end




function test()
    a = Array(Uint8,1000001)
    x::BigInt= 2
    x = (x^1000000)


    @time bin1(x,1000001)
    @time bin2(x,1000001,a,true)

end

test()

Answer 1

正如Felipe Lema所指出的,Base将BigInt打印到GMP,它可以打印BigInts而不用它们进行任何中间计算 - 用BigInts进行大量计算以找出它们的数字非常慢并最终分配大量内存.底线:x >>= 1对于像Int64 这样的东西来说,做法非常有效,但对BigInts这样的东西来说并不是那么有效.