functional-programming - 计算纯函数式语言中字节的频率

Question

如果我们有一个任务：

给定一个二进制数据块，计算其中字节的频率。

而且您应该在 C 中执行此操作，即使对于较大的二进制块，答案也是微不足道且相当快的。一个人如何在没有副作用的情况下用一种纯粹的函数式语言来实现它？

例如，如果您编写了一个函数，该函数接受每个字节和其余字节列表的频率计数，并返回修改后的频率计数，那么它必须为 100M 字节的数据集做大量工作。

此外，如果您对数据进行排序，然后以某种方式计算后续相同值字节的数量，则排序本身将花费大量时间。

有没有合理的方法来实现这一点？

Answer 1

直接的方法确实是传入并返回将字节映射到计数的数据结构。这可能会被实现为某种树（据我所知，这就是您从标准库容器中得到的东西）。在纯函数式编程中，当您传入一棵树并且需要返回一棵仅在一个节点上有差异的新树时，返回的树最终会与原始树共享几乎所有的结构和数据。

遍历树以获取计数有一些开销，但由于您正在计算字节，因此树永远小于 256 个元素，因此开销是 log(255)，它是一个常数。对于大型数据集，它不会变得更大——它不会改变算法的复杂性。即使您使用最大可能的开销来复制完整的 256 项计数数组而没有共享，这实际上也是如此。

如果您想优化这一点，您可以利用“中间”频率计数永远不需要的事实，除非作为下一组计数的计算的一部分。这意味着您可以使用各种技术来让实现使用破坏性更新，即使您仍在语义上编写函数式代码。Haskell 中的 AnSTref基本上是让您手动执行此操作。

从理论上讲，编译器可能会注意到您正在用一个新值替换一个不再需要的值，因此它可以为您进行适当的更新。我不知道目前是否有任何实际的生产就绪编译器能够进行这种优化。