<分区>
我正在用 haskell 为翻译器实现一个符号表。我的问题是在从关联列表转换为 trie/map/hashmap 之前，表在平均用例上应该有多大，假设我的键是小字符串或字节串？我不想使用哈希表，因为从 io Monad 展开似乎在效率方面倒退了一步(在这里插入 haskell 效率笑话 :))
编辑:取消我对哈希表的评论。根据最新的实现，它们与其他选项一样好。
<分区>
我正在用 haskell 为翻译器实现一个符号表。我的问题是在从关联列表转换为 trie/map/hashmap 之前，表在平均用例上应该有多大，假设我的键是小字符串或字节串？我不想使用哈希表，因为从 io Monad 展开似乎在效率方面倒退了一步(在这里插入 haskell 效率笑话 :))
编辑:取消我对哈希表的评论。根据最新的实现，它们与其他选项一样好。
最佳答案
我认为您应该始终*将 (Hash)Map 用于任何事情，而不仅仅是一个快速脚本。
第一个参数，从设计角度使用最佳数据类型。 map 缩放到更大的尺寸。即使对于较小的关联列表，如果它实际上一样快，我也不会感到惊讶(并且几乎期望如此)。这种感觉背后的原因来自于关注1 ，关于为 nub 使用 Set，他们发现即使对于小列表也不会慢。此外，Maps 有很多与其相关的有用函数，可用于操作它们。对于不存在的列表，或者您必须自己编写它们(而且它们可能不会那么快)。
第二个参数，不需要就不要优化。正如 kqr 在他对您的回答的评论中指出的那样，在有证据证明您需要它(并且您确实需要优化此列表/ map )之前不要进行优化。为此要记住的一个问题是，这么小的字典多久会出现一次？那么它是否会为您的程序的总时间贡献很多时间。或者执行量已经很小以至于不会有明显的差异？
*:我现在能想到的一个异常(exception)是，如果您想创建一个无限关联列表。
附言有关列表(和公司政策)可能出错的好文章，请参阅 http://thedailywtf.com/Articles/Coding-Practices-MUST-Be-Followed.aspx
关于haskell - 转换为树之前的关联列表有多大，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/21503789/