本文介绍了Haskell集合，保证每个操作的最坏情况的边界？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 这种结构对于实时应用是必需的，例如用户界面。 （用户不关心是否点击按钮需要0.1s或0.2s，但他们确实关心，如果第100次点击强制一个悬而未决的延迟计算，需要10秒继续。） 我正在阅读Okasaki的论文纯功能数据结构，他描述了一个有趣的通用方法将延迟数据结构与摊销边界转换成具有每个操作的相同最坏情况边界的结构。这个想法是分配计算，以便在每次更新时，一些部分的未评估thunk被强制。 我想知道，有没有任何这样的标准集合的实现（ Map href =http://hackage.haskell.org/package/containers-0.5.0.0> container 包说，因此无法保证单个操作的最坏情况。有诸如 Data.Map.Strict 的严格变体，但它们的键和值是严格的：它的结构没有什么可能的严格性。 解决方案 去寻找源，例如适用于 数据.Map.Map - 请参阅注意：构造函数的顺序数据Map ka = Bin { - ＃UNPACK＃ - }！Size！ka！（Map ka）！（Map ka） |提示 您会看到 Map spine-strict（并且在键中严格，即使使用 Data.Map.Lazy ），如果将它评估为WHNF，则强制执行完整的脊椎。这同样适用于 IntMap s，设置 s和 IntSet s。 所以你可以通过在每次操作之前强制容器到WHNF来防止大thunk（除了映射到/包含的值）的构造。对于 Data.XYZ.Strict 变体，自动为包含的值（时间（和空间）泄漏的常见原因）防止大的thunk：（值得注意的是，只评估WHNF，如果你需要更多，你必须自己做，例如 deepseq 操作后任何更改的值immediatley），你需要处理自己与 Data.XYZ.Lazy 变体。 因此 用户不在乎是否单击按钮需要0.1s或0.2s，但他们确实关心，如果第100次点击强制一个悬而未决的延迟计算，需要10秒。 $ b $ 但是，它仍然可以是第100次点击需要花费多长时间来处理比平均值，而不是由于出色的延迟计算，而是由于算法（考虑经典队列实现与两个列表，前面，你出队元素 dequeue（Q（x：xs）ys）=（x，Q xs ys），并且后面你 enqueue y（Q xs ys ）= Q xs（y：ys）在O（1）中，除了当前面列表为空并且后面需要首先反转时，出列队列需要O（size） （1）摊还价）而不改变摊销成本。 我不知道容器有这样的情况，但它是需要注意的。 Such structures are necessary for real-time applications - for example user interfaces. (Users don't care if clicking a button takes 0.1s or 0.2s, but they do care if the 100th click forces an outstanding lazy computation and takes 10s to proceed.)I was reading Okasaki's thesis Purely functional data structures and he describes an interesting general method for converting lazy data structures with amortized bounds into structures with the same worst-case bounds for every operation. The idea is to distribute computations so that at each update some portion of unevaluated thunks is forced.I wonder, is there any such implementation of standard collections (Map, Set, etc.) in Haskell?The containers package saysso there is no guarantee for the worst-case bounds for a single operation. There are strict variants like Data.Map.Strict, but they're strict in their keys and values:there is nothing about (possible) strictness of its structure. 解决方案 Go looking for the source, e.g. for Data.Map.Map-- See Note: Order of constructorsdata Map k a = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a) | TipYou see that a Map is totally spine-strict (and strict in the keys, even with Data.Map.Lazy), if you evaluate it to WHNF, the complete spine is forced. The same holds for IntMaps, Sets and IntSets.So you can prevent the construction of large thunks (except for the mapped-to/contained values) easily by forcing the container to WHNF before every operation. The prevention of large thunks for the contained values [a common cause for time (and space) leaks] is automatic for the Data.XYZ.Strict variants (caveat: the values are only evaluated to WHNF, if you need more, you have to do it yourself by e.g. deepseqing any changed values immediatley after the operation), something you need to handle yourself with the Data.XYZ.Lazy variants.Thusis an easily avoided problem with these containers.However, it could still be that the 100th click takes much longer to process than the average, not due to outstanding lazy computations, but due to the algorithm (consider the classic queue implementation with two lists, the front, where you dequeue elements by dequeue (Q (x:xs) ys) = (x, Q xs ys) in O(1), and the back where you enqueue y (Q xs ys) = Q xs (y:ys) in O(1), well, except that dequeuing takes O(size) when the front list is empty and the back needs to be reversed first, but it's O(1) amortized still) without changing the amortized cost.I don't know if the algorithms used in containers have any such cases, but it's something to be aware of. 这篇关于Haskell集合，保证每个操作的最坏情况的边界？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！
