gpt4 book ai didi

Haskell 集合保证每个操作的最坏情况界限?

转载 作者:行者123 更新时间:2023-12-04 02:08:00 25 4
gpt4 key购买 nike

这种结构对于实时应用程序是必要的——例如用户界面。 (用户不关心单击按钮需要 0.1 秒还是 0.2 秒,但他们确实关心第 100 次单击是否会强制执行出色的惰性计算并需要 10 秒才能继续。)

我在看冈崎的论文Purely functional data structures他描述了一种有趣的通用方法,用于将具有摊销边界的惰性数据结构转换为具有相同 的结构。每个操作的最坏情况界限 .这个想法是分配计算,以便在每次更新时强制执行一些未评估的 thunk。

我想知道,Haskell 中是否有任何标准集合( MapSet 等)的实现?

containers包说

The declared cost of each operation is either worst-case or amortized, but remains valid even if structures are shared.



因此不能保证单个操作的最坏情况界限。有严格的变体,如 Data.Map.Strict ,但它们的键和值很严格:

Key and value arguments are evaluated to WHNF; Keys and values are evaluated to WHNF before they are stored in the map.



它的结构没有(可能的)严格性。

最佳答案

there is nothing about (possible) strictness of its structure.



去寻找来源,例如对于 Data.Map.Map
-- See Note: Order of constructors
data Map k a = Bin {-# UNPACK #-} !Size !k a !(Map k a) !(Map k a)
| Tip

您会看到 Map 完全是脊椎严格的(并且在键中是严格的,即使使用 Data.Map.Lazy 也是如此),如果您将其评估为 WHNF,则强制使用完整的脊椎。这同样适用于 IntMap s、 Set s 和 IntSet s。

因此,您可以通过在每次操作之前将容器强制为 WHNF 来轻松地防止构建大型 thunk(映射到/包含的值除外)。对于 Data.XYZ.Strict 变体,防止包含值的大 thunk [时间(和空间)泄漏的常见原因] 是自动的(警告:这些值仅评估为 WHNF,如果您需要更多,您必须自己做例如 deepseq 在操作后立即更改任何值),您需要使用 Data.XYZ.Lazy 变体自行处理。

因此

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.



是这些容器很容易避免的问题。

但是,第 100 次点击的处理时间仍然可能比平均时间长得多,这不是由于出色的惰性计算,而是由于算法(考虑具有两个列表的经典队列实现,前面,您将元素从 dequeue (Q (x:xs) ys) = (x, Q xs ys) 出列在 O(1) 中,在 O(1) 中 enqueue y (Q xs ys) = Q xs (y:ys) 的后面,好吧,除了当前面列表为空并且后面需要先反转时,出队需要 O(size),但它是 O(1) 摊销的仍然)不改变摊余成本。

我不知道 containers 中使用的算法是否有这种情况,但这是需要注意的。

关于Haskell 集合保证每个操作的最坏情况界限?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12393104/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com