时间戳

首页 > 解决方案 > Haskell getsizeof 大整数

haskell - Haskell getsizeof 大整数

问题描述

我试图以字节为单位获取大整数的大小，因为幕后有任意精度的数学，我想知道结果实际使用了多少空间。

这是一个示例：

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 来说，这对我来说更可信。

标签： haskell

解决方案

您可以通过使用integer-logarithms包询问其日志基数 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的 s 可能会产生表示不同的值。接触这些内部 API 时，您有时会失去抽象外部 API 的保证；在这种情况下，你可能没有那个x == y暗示sizeOfInteger x == sizeOfInteger y。如果您打算走这条路，请仔细阅读文档！

推荐阅读