Haskell getsizeof大整数

Question

考虑到引擎盖下有任意精度的数学运算，我正在尝试获取一个大整数的字节大小，并且我想知道结果实际使用了多少空间。

这是一个示例：

Prelude> import Data.Bits
Prelude> let fac1000 = product [1..1000] # big!
Prelude Data.Bits> finiteBitSize fac1000

<interactive>:37:1: error:
    • Ambiguous type variable ‘b0’ arising from a use of ‘finiteBitSize’
      prevents the constraint ‘(FiniteBits b0)’ from being solved.
      Probable fix: use a type annotation to specify what ‘b0’ should be.
      These potential instances exist:
        instance FiniteBits Bool -- Defined in ‘Data.Bits’
        instance FiniteBits Int -- Defined in ‘Data.Bits’
        instance FiniteBits Word -- Defined in ‘Data.Bits’
    • In the expression: finiteBitSize fac1000
      In an equation for ‘it’: it = finiteBitSize fac1000

<interactive>:37:15: error:
    • Ambiguous type variable ‘b0’ arising from a use of ‘fac1000’
      prevents the constraint ‘(Num b0)’ from being solved.
      Probable fix: use a type annotation to specify what ‘b0’ should be.
      These potential instances exist:
        instance Num Integer -- Defined in ‘GHC.Num’
        instance Num Double -- Defined in ‘GHC.Float’
        instance Num Float -- Defined in ‘GHC.Float’
        ...plus two others
        (use -fprint-potential-instances to see them all)
    • In the first argument of ‘finiteBitSize’, namely ‘fac1000’
      In the expression: finiteBitSize fac1000
      In an equation for ‘it’: it = finiteBitSize fac1000

例如，当我强制转换为整数时，他们建议的类型注释似乎并不合理：

Prelude Data.Bits> finiteBitSize (fac1000 :: Int)
64

好吧，这是一个很大的数字，我不相信。在python中，我得到：

>>> import sys, math
>>> sys.getsizeof(math.factorial(1000))
1164

对于天文较大的4.02e2568来说，这对我来说更可信。

Answer 1

您可以通过使用整数对数包要求以256为底的对数来估计字节数：

Math.NumberTheory.Logarithms> integerLogBase 256 (product [1..1000])
1066

这仅是一个近似值，因为它仅考虑了用于存储数字的字节。通常，任意精度整数还具有一些开销，用于存储有关数字长度的信息，并且可能会存储一些过度分配的信息，并且采用对数运算法则都无法解决这些问题。

如果您不介意以位而不是字节报告近似大小，integerLog2则速度会更快。

Math.NumberTheory.Logarithms> integerLog2 (product [1..1000])
8529

如果您想得到真正的答案，则必须接触一些真正的低级API，并依赖于的确切定义Integer：

{-# LANGUAGE MagicHash #-}
import Data.Bits
import GHC.Exts
import GHC.Integer.GMP.Internals
import GHC.Prim

sizeOfInteger :: Integer -> Int
sizeOfInteger n = constructorSize + case n of
    S# i -> finiteBitSize (I# i) `div` 8
    Jp# bn -> sizeOfBigNat bn
    Jn# bn -> sizeOfBigNat bn
    where
    constructorSize = finiteBitSize (0 :: Word) `div` 8
    sizeOfBigNat (BN# arr) = constructorSize + I# (sizeofByteArray# arr)

在ghci中尝试一下：

> sizeOfInteger (product [1..1000])
1088

谨防！我不知道这些内部API的所有前景。Integer以不同的方式计算equals可能会产生表示不同的值。当接触这些内部API时，有时会失去抽象外部API的保证。在这种情况下，您可能没有那个x == y隐含的含义sizeOfInteger x == sizeOfInteger y。如果您打算采用这种方法，请仔细阅读文档！