Map
在哈斯克尔:
-
从列表中使用
fromList
-
fromAscList
-
利用这个事实
地图
Monoid
(或
Semigroup
)和concat
singletons
.
我知道
摊销
α1的复杂度为O(n*log(n)),其中α2为O(n)。
我想3应该大致相当于1,可能需要融合。
这个
重要的是,因为Haskell在默认情况下是懒惰的,即使来自映射的查找是O(log(n)),实际上它可以与映射本身的构造交错,即O(n*log(n)),这可以在实践中使查找成为O(n*log(n))(特别是当您每次需要构建映射时)。如果使用硬编码映射,也可能会附加此项
例如,我认为
lookup 'b' (fromList [('a', 1), ('b', 2)])
实际上相当于只在列表中查找d而不使用中间映射?
那么,1和3之间有什么区别吗,或者是排序列表和调用
?
另外,如果我需要一个映射只计算一次,我需要确保GHC不内联它,所以它是在函数之间共享的吗?
我意识到这个问题可能有点模糊,事实上与我最近遇到的不同用例相对应。
第一个对应于“静态连接”。我有一个管理项目的应用程序,每个项目代码可以按样式和变化进行拆分(例如“T恤-红色”=>(“T恤”,“红色”)。分割是基于规则(和regexp)的,而且非常慢。要不总是重新计算规则,只需执行一次并存储在db表中。我有几个纯函数,需要能够分割项目代码,所以我给他们传递一个函数
Text -> (Text, Text)
. 该函数实际上是部分应用于地图的查找。代码与此类似
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
(实际上比
从列表
第二种情况是在两个表之间执行手动连接,我通常会执行以下操作
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。
第三种情况是获取与不同表中类别项相关的杂项信息。
例如,我希望能够按类别比较sales(sales表)和purchase(purchases表)。
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和join中完成。为此,我将分别加载每个表(在sql中对所能做的进行分组),并返回
Map Style SalesInfo
Map Style PurchaseInfo
等。。。合并他们。这张桌子很大,我意识到我最终会把所有东西都加载到内存中,而手动“压缩”东西可能会更有效,但我不知道怎么做。
