performance - 什么时候应该使用 Haskell 的 Data.Map 来代替元组列表？

Question

最近需要比较两组历史数据。由于有时其中会缺少一两天，并且我想要精确，因此我决定创建一个所有可能日期的列表以及两个包含日期和属于这两个集合的相应值的元组列表。然后我将后面的列表更改为Map以改进日期查找。

这个想法是尝试从 Mapped 列表中的完整日期列表中查找每个日期，并创建 (date, value1, value2) 的“三元组”列表 仅包含两个数据集都有日期和值的日期。然后我可以将它们写入文件并正确比较它们。

不要介意代码，包含它只是为了好的措施

这是代码(它根本不是最佳的，但对于这个小任务，它很好地完成了工作):

import qualified Data.Map as M
import Data.List (transpose)
import Data.Maybe (fromJust)

main = do
    dts     <- readFile "dates.txt"
    cts1    <- readFile "eu.txt"
    cts2    <- readFile "usa.txt"
    let
        dates  = lines dts
        cols1  = transpose $ map words $ lines cts1
        cols2  = transpose $ map words $ lines cts2
        prs1   = zip (head cols1) (last cols1)
        prs2   = zip (head cols2) (last cols2)
        map1   = M.fromList prs1
        map2   = M.fromList prs2
        trips  = map fromJust (filter (/=Nothing) (map (\date -> getTrips date map1 map2) dates))
        cols3  = map (\(a,b,c) -> [a,b,c]) trips
        result = unlines $ map unwords $ cols3
    writeFile "trips.txt" result

getTrips :: String -> M.Map String String -> M.Map String String -> Maybe (String, String, String)
getTrips date map1 map2
    | is1 /= Nothing && is2 /= Nothing    = Just (date, fromJust is1, fromJust is2)
    | otherwise                           = Nothing
    where
        is1 = M.lookup date map1
        is2 = M.lookup date map2

TL;DR:代码有效(尽管我很乐意听到一些意见/建议)，但我有一些问题:

• 只有大约 2000 个日期，因此我不太关心性能(你可以看到我到处都在使用 String)；那么使用 Data.Map 是否有点过头了？ 什么时候应该优先使用Data.Map而不是元组列表？
• Map 是从 String 的元组创建的 - 可以吗？键应该始终为数字，以便平衡和查找正常工作？

Answer 1

there were only around 2000 dates, therefore I didn't care much about performance (you can see that I was using Strings everywhere); was using Data.Map an overkill then? When should Data.Map be preferred over lists of tuples?

您应该使用适合您的问题和性能/编程时间限制的数据结构，因此使用Map可能是一个好主意。也许在你的情况下，如果你的数据已经订购，你可以这样做

union [] _ = []
union _ [] = []
union xss@((dx,vx):xs) yss@((dy,vy):ys) = 
    case compare dx dy of
         EQ -> (dx, vx, vy) : union xs ys
         GT -> union xss ys
         LT -> union xs yss

the Map was created from tuples of Strings - is it fine or should the key always be numeric in order for the balancing and lookups to work properly?

不，如果您的代码类型检查您的Map将正常工作(w/r/t您定义Ord实例的方式)。但正如 C. A. McCann 所建议的，a trie如果您的键是列表，则可能更合适，特别是如果键前缀之间有很多重叠(查看列表上的 Ord 实例是如何实现的，并想象必须进行的操作数量将键“abcdx”、“abcdy”和“abcdz”插入 Map 与 trie 结构中以说服自己)。