Мне нужно повторять и вперед, и назад в отсортированном наборе. Если я использую NavigableSet, я получаю строго-вперед итератор и строго-обратный итератор (iterator() и descendingIterator()), но никто не может двигаться вперед и назад.Java: SortedSet «cursor» -истовый итератор
Какова временная сложность NavigableSet.lower() и higher()? Я могу использовать их вместо этого, но я не хочу этого делать, если они неэффективны.
Есть только две реализации NavigableSet. Говоря, что вы выбрали TreeSet, в то время как у меня нет источника, Javadoc говорит, что он основан на TreeMap providing O(log(n)) for get/put/containsKey/remove. В худшем случае это приведет к тому, что вы найдете значение, которое мы находим для более низкого/более высокого, плюс дополнительный поиск, чтобы получить следующее/предыдущее значение, предоставляя O (2log (n)) = O (log (n)) ,
Деревья в наихудшем случае O (n) для поиска в случае, если это фактически список, но в целом O (высота).
Есть ли деревья, которые быстрее для итерации между соседними элементами? –
Это компромисс между операциями. Это зависит от размера 'n'. Для дерева get - 'O (log n)', а итерация - 'O (log n)'. Используя отсортированный массив/список, get - 'O (n)', а итерация - 'O (1)'. – Andy
ОК, спасибо. Я уверен, что SkipLists имеют O (log n) get и O (1) итерацию. –
В зависимости от ваших конкретных потребностей вы можете преобразовать отсортированный набор в список, скажем, список массивов, и использовать list iterator для обхода. Он может использоваться в обоих направлениях с помощью методов next() и previous(), которые могут свободно смешиваться.
Это справедливая точка, и лучшее описание использования поможет. Однако, по крайней мере, в тех случаях, когда они связаны с Java API, единственными параметрами SortedSet (TreeSet, ConcurrentSkipListSet) являются также NavigableSets. Таким образом, будет просто добавленное время преобразования в список, а затем процедура, указанная Энди в комментарии к моему ответу. – apiri
Испытывали ли вы (время) альтернативы с представительным набором данных? – matiasf
у вас есть точка - если вам нужно оптимизировать, вы должны быть готовы измерить, но именно поэтому я спросил здесь, чтобы получить мудрость от тех из вас, кто более опытен. (не говоря уже о том, что это должно быть в документации, но это не так. grrrr.) –