在C++和其他语言中,附加库实现了多索引容器,例如Boost.Multiindex.也就是说,一个集合存储一种类型的值,但在这些值上保持多个不同的索引.这些索引提供不同的访问方法和排序行为,例如map,multimap,set,multiset,array等.多索引容器的运行时复杂性通常是各个索引的复杂性的总和.
是否有Haskell的等价物或人们自己组成？具体来说,使用set-type索引(T是实例Ord)以及map类型的索引来实现类型T集合的最惯用方法是什么(假设类型K的键值可以是为每个T提供,明确地或通过功能T -> K)？
我今天早上刚刚将IxSet上传到hackage,
http://hackage.haskell.org/package/ixset
ixset提供具有多个索引的集合.
ixset作为happstack-ixset已经存在了很长时间.此版本删除了特定于happstack的任何依赖项,并且是IxSet的新官方版本.
另一种选择是kdtree:
darcs得到http://darcs.monoid.at/kdtree
kdtree旨在通过提供更高的类型安全性和更好的时间和空间使用来改进IxSet.当前版本似乎在所有这三个方面都做得很好 - 但它尚未准备好迎接黄金时段.其他贡献者将受到高度欢迎.
在简单的情况下,每个元素都有一个始终可用的唯一键,您可以使用a Map并提取键来查找元素.在每个值仅仅是几乎没有价值的情况下,有可用的一个关键,一个简单的解决方案,将是这样的Map K (Set T).直接查找元素将涉及首先提取密钥,索引Map以找到共享该密钥的元素集,然后查找所需的元素.
在大多数情况下,如果可以通过上述方式直接完成某些操作(简单的转换和嵌套),那么以这种方式执行它可能是有意义的.然而,由于显而易见的原因,这些都没有很好地概括为例如可能不可用的多个独立密钥或密钥.
除此之外,我不知道任何广泛使用的标准实现.确实存在一些例子,例如来自happstack的IxSet似乎大致符合该法案.我怀疑这里有一个大小适中的解决方案可能会有很差的收益/复杂性比例,因此人们倾向于自己动手以满足特定需求.
直观地说,这似乎是一个问题,可能更好地工作,而不是单个实现,而是一个原始集合,可以比Data.Map允许更灵活地组成,以创建特殊的专业结构.但这对短期需求并没有多大帮助.
| 归档时间： |
|
| 查看次数： |
1593 次 |
| 最近记录： |