haskell - 在 Haskell 中构建(惰性)映射的有效方法

Question

我知道在 Haskell 中构建 Map 的几种不同方法:

1. 使用 fromList 从列表构建它
2. 使用 fromAscList 从排序列表构建它
3. 利用 Map 是一个 Monoid(或 Semigroup)和 concat singletons 的事实。<

据我了解，#1 的摊销复杂度为 O(n*log(n))，而 #2 的复杂度为 O(n)。我猜#3 应该大致相当于#1，并且可能会发生融合。

摊销很重要，因为 Haskell 默认情况下是懒惰的，即使从 Map 进行查找的时间复杂度为 O(log(n))，但实际上它可以与 Map 的构造交错它本身的时间复杂度为 O(n * log(n))，这在实践中可以使查找时间为 O(n * log(n)) (特别是如果您每次需要时都构建 map )。如果您使用硬编码 map ，这也可能会附加

例如，我是否认为 lookup 'b' (fromList [('a', 1), ('b', 2)]) 实际上相当于 d在列表中查找而不使用中间映射？

那么 #1 和 #3 之间有区别吗？或者对列表进行排序和调用 fromList 之间有区别吗？

更新

另外，如果我需要一个映射仅计算一次，我是否需要确保 GHC 不会内联它，以便它在函数之间共享？

用例

我意识到这个问题可能有点模糊，实际上对应于我最近遇到的不同用例。

第一个对应于“静态连接”。我有一个管理项目的应用程序，每个项目代码都可以按样式和变体进行拆分(例如 'T-Shirt-Red' => ('T-Shirt', 'Red')。拆分基于规则(和regexp) 并且非常慢。为了不总是重新计算规则，只需执行一次并存储在数据库表中。我有一些纯函数需要能够拆分项目代码，所以我向它们传递了一个函数 Text -> (Text, Text)，该函数实际上是部分应用于Map的查找，代码类似这样

getSplitter :: Handler (Text -> (Text, Text))
getSplitter = do
      sku'style'vars <- runDB $ rawSQL "SELECT sku, style, var FROM style_cache " [] -- load the split table
      let sku'map = fromList [ (sku, (style,var)) 
                             | (sku, style, var) <- sku'style'vars
                             ]
      return $ flip lookup sku'map

通过按 sku 对项目进行排序并使用 fromDistinctAscList(实际上比 fromAscList 更快)，可以轻松加快此速度。但是，我仍然有一些关于如何在不同请求之间缓存它的问题。

第二种情况是在两个表之间进行手动联接，我通常会同时执行一些操作

do
   sku'infos <- selectList [] [] -- load item info
   let skuInfo = fromList sku'infos

   orderLines <- selectList [] [] -- load orders
   -- find infos corresponding to order items
   mapM (\o -> (o, lookup (orderSku o) skuInfo) orderLines

我可以再次在 SQL 中对 sku'infos 进行排序并使用 fromDistinctAscList。

第三种情况是获取与不同表中的类别项相关的杂项信息时。

例如，我希望能够按类别比较销售(销售表)和购买(购买表)。

在纯 SQL 中我会做一些事情

SELECT style, sum(sales.amount), sum(purchase.amount)
FROM style_cache
LEFT JOIN sales USING(sku)
LEFT JOIN purchases USING(sku)
GROUP by style

但是，这是一个简化的示例，实际上，聚合要复杂得多，并且必须在 Haskell 中完成以及连接。为此，我分别加载每个表(对 sql 中的内容进行分组)并返回Map Style SalesInfo、Map Style PurchaseInfo等...并将它们合并。该表相当大，我意识到我最终将所有内容加载到内存中，而我可能可以通过手动“压缩”内容来提高效率，但我不确定如何实现。

Answer 1

我不确定我是否理解这个问题背后的全部动机，但我会发表一些评论:

1. Map是脊柱严格的——这意味着 Map 的树结构并且 key 本身在每个 Map 上都被强制(至少足够远以进行所有必要的比较)手术。所以我期望 Data.Map.lookup k (fromList xs)进行 O(n*log(n)) 比较(n xs 的长度)，而我期望 Prelude.lookup k xs进行 O(n) 比较(实际上只是相等检查，但通常这与比较的复杂性几乎相同)。
2. 如果fromAscList . sort确实比 fromList 更快，这是 Data.Map 中的性能错误并且库应该更改为定义 fromList = fromAscList . sort 。如果是这样的话，我会感到非常惊讶。人们花了相当多的时间来优化 containers ，所以我不希望看到任何水果挂得那么低。
3. 是的，内联会破坏共享。