如果您在Haskell中编写生物信息学算法,则可能会使用代数数据类型来表示核苷酸:

data Nucleotide = A | T | C | G

我想您会在Standard ML或OCaml中做类似的事情(我从未真正使用过)。

可以将Nucleotide类型的值清楚地包含在两位中。但是,这样做将导致访问时间比每个Nucleotide值使用一个字节要慢,因为您需要使用二进制运算符选择感兴趣的两位。

因此,在决定如何表示代数数据类型时,编译器必须在内存效率和计算效率之间进行内在的权衡。此外,由于值可以具有可变大小,因此使内存中的代数数据类型表示更加复杂:
data Maybe a = Just a | Nothing

显然,形式Maybe aJust a值在逻辑上大于形式Nothing的值。在这样的极端示例中:
data Hulk a b c d e = Big a b c d e | Little

您绝对不需要将Little值中包含的五个值的空指针或零值存储在Big值中。我假设您只是使用可变大小的堆分配内存,并在开头使用构造函数ID(例如,0Big1Little)。但是,如果您想将Hulk值存储在堆栈中(一种更快的表示形式),则必须将空白内存与Little值一起存储,以便Hulk类型的所有值都具有相同的大小。另一个权衡。

西蒙·马洛(Simon Marlow)用previous StackOverflow question回答了我关于GHC的一般性问题。但是,我有三个相关的问题尚未解答:
  • 标准ML(SML / NJ和MLton)和OCaml是否使用相同的技术?
  • 如果是这样,这些语言(或其 sibling )的较不常见的编译器是否会尝试其他技术?
  • 在这些语言中,是否存在一种相当简单的方法(理想情况下是编译指示或选项标志)来使用内存效率更高的表示形式,例如Nucleotide的两位表示形式?对于许多生物信息学应用来说,这种存储效率是必不可少的。如果每个Nucleotide必须为一个字节,则高性能生物信息学算法将不得不求助于手动位加密。
  • 最佳答案

    没有一个单一的答案:数据类型是抽象结构,可以由实现者自行决定以多种方式实现。在实践中,诸如单独编译之类的考虑倾向于在某种程度上限制事物。

    对于将仅包含空构造函数的数据类型打包到尽可能少的位的特定情况下,可以通过定义从数据类型到小整数再返回的函数来进行。被抽象类型(或在Haskell中,newtype)隐藏的整数类型也是一个合理的选择。将小整数打包和解压缩为正在使用的任何聚合形式将是您的工作。

    顺便说一句,现实世界OCaml在OCaml值的表示形式上带有a very nice chapter(粗略的总结:就此问题而言,与GHC并没有太大不同)。

    09-10 09:30
    查看更多