f# - 有没有一种方法可以根据 FIRST 节点拆分 Map 以满足谓词？

Question

有一个名为的函数Map.partition将映射拆分为 2 个映射，其中一个包含满足谓词的所有元素。谓词将键和值作为参数，并检查映射的每个元素以确定它属于哪个结果映射。

我的要求是一个特例。我有一张地图，我想根据键是否大于或小于某个值来拆分为 2 个地图。这会更有效率，因为您只需要搜索树，直到谓词的输出发生变化。当前的实现将是 O(n)，而我正在寻找的是 O(log(n))。对于自定义树实现来说，这应该是直截了当的，但如果可以的话，我更愿意使用内置的集合，然后再推出自己的集合。

标签： f#binary-search-tree

Answer 1

F# Maps 的文档可以在以下链接中找到：https: //msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/collections.map-module-%5Bfsharp%5D 尽管您想要实现的操作可以在 O(log(n)) 中实现，在这个模块中没有实现。最好的选择是使用分区（如您所说，将是 O(n)）或实现您自己的 Map 版本。您还可以在 github 中搜索一些实现红黑树的代码，并为此操作包含您自己的自定义方法。

简短回答：不，没有一种方法可以根据第一个节点拆分 Map 以满足谓词。

编辑：这个->