Есть ли способ разделить карту на основе узла FIRST для удовлетворения предиката?

Question

Существует функция с именем Map.partition, которая разбивает карту на 2 карты, причем одна содержит ВСЕ элементы, удовлетворяющие предикату. Предикат принимает ключ и значение в качестве аргументов и проверяет каждый элемент карты, чтобы определить, к какой карте результатов он принадлежит.

Мое требование - особый случай этого. У меня есть карта, и я хочу разделить ее на 2 карты в зависимости от того, больше или меньше ключ какого-либо значения. Это было бы гораздо эффективнее, поскольку вам нужно только искать в дереве, пока выходные данные предиката не изменятся. Текущая реализация будет O (n), и то, что я ищу, будет O (log (n)). Это должно быть прямолинейно для реализации пользовательского дерева, но я бы предпочел использовать встроенные коллекции, если смогу, перед тем как развернуть свою собственную.

Answer 1

Документацию для карт F # можно найти по следующей ссылке: https://msdn.microsoft.com/en-us/visualfsharpdocs/conceptual/collections.map-module-%5Bfsharp%5D Хотя операция, которую вы хотите реализовать, может быть реализована в O (log (n)), она не реализована в этом модуле. Наилучшим вариантом будет использование раздела (как вы сказали, O (n)) или реализация собственной версии Map. Вы также можете выполнить поиск кода в github, который реализует красно-черное дерево и включает в себя собственный метод для этой операции.

Краткий ответ: Нет, не существует метода разделения карты на основе первого узла для удовлетворения предиката.

РЕДАКТИРОВАТЬ: это ->