Axa*_*dax 1 functional-programming
如果我们有一个任务:
给定一块二进制数据,计算其中的字节频率.
并且你应该在C中做到这一点,即使对于较大的二进制块,答案也是微不足道的并且相当快.如何用纯函数语言实现这一点,没有副作用？
例如,如果您编写了一个函数,该函数接受每个字节的频率计数和字节列表的其余部分,并返回修改后的频率计数,则必须为100M字节的数据集执行大量工作.
此外,如果您对数据进行排序,然后以某种方式计算后续相同值字节的数量,则排序本身将花费大量时间.
有没有合理的方法来实现这个？
直接的方法是传入并返回将字节映射到计数的数据结构.这很可能会实现某种树的(因为这是你走出标准库容器是什么,据我所知).在纯函数式编程中,当您在树中传递并且需要返回仅在一个节点上有差异的新树时,返回的树最终会与原始树共享几乎所有的结构和数据.
遍历树以获取计数有一些开销,但由于您计算字节数,树只会小于256个元素,因此开销是log(255),这是一个常量.对于大型数据集来说,它并没有变得更大 - 它不会改变算法的复杂性.即使您使用最大可能的开销来复制完整的256条计数数组而没有共享也是如此.
如果要优化它,可以利用"中间"频率计数这一事实,除非作为计算下一组计数的一部分.这意味着即使您仍然在语义上编写功能代码,您也可以使用各种技术来使实现使用破坏性更新.一个STref在Haskell基本上是让你手动完成.
从理论上讲,编译器可能会注意到您正在用新的值替换永不需要的值,因此它可以为您进行更新.我不知道任何实际的生产就绪编译器目前是否能够进行这种优化.