Вы, кажется, хорошо понимаете компромисс здесь, поэтому я сомневаюсь, что кто-то может дать вам окончательный, принципиальный ответ. К счастью, это довольно просто проверить.
Я начал с создания простого Iterator<String>, которое бесконечно зацикливается на конечном списке случайно сгенерированных строк. (То есть: при инициализации он генерирует массив _strings из a случайных строк длиной b из пула c различных символов. Первый вызов next() возвращает _strings[0], следующий вызов возвращает _strings[1] & hellip; ( n + 1) -й вызов снова возвращает _strings[0].) Строки, возвращенные этим итератором, были тем, что я использовал во всех звонках SortedSet<String>.add(...) и SortedSet<String>remove(...).
Затем я написал тестовый метод, который принимает пустой SortedSet<String> и зацикливается d раз. На каждой итерации добавляется e элементов, затем удаляется f элементов, а затем выполняется итерация по всему набору. (В качестве проверки работоспособности он отслеживает размер набора, используя возвращаемые значения add() и remove(), и когда выполняет итерацию по всему набору, он удостоверяется, что находит ожидаемое количество элементов. В основном я сделал просто 1030 * что-то в теле цикла.)
Не думаю, что мне нужно объяснять, что делает мой метод main(...). : -)
Я пробовал различные значения для различных параметров, и я обнаружил, что иногда ConcurrentSkipListSet<String> работал лучше, а иногда TreeSet<String>, но разница была не более чем в два раза. В целом, ConcurrentSkipListSet<String> работает лучше, когда:
- a , b и / или c были относительно большими. (Я имею в виду, в диапазоне, который я тестировал. Мои a были в диапазоне от 1000 до 10000, мои b - от 3 до 10, мои c ' s от 10 до 80. В целом, размеры результирующих наборов варьировались от 450 до 10000, с режимами 666 и 6666, потому что я обычно использовал e = 2 & lrm; f .) Это говорит о том, что
ConcurrentSkipListSet<String> справляется несколько лучше, чем TreeSet<String> с большими наборами и / или с более дорогими сравнениями строк. Пробуя конкретные значения, разработанные для того, чтобы разделить эти два фактора, у меня сложилось впечатление, что ConcurrentSkipListSet<String> справляется заметно лучше, чем TreeSet<String> с большими наборами, и немного меньше , что хорошо при более дорогих сравнениях строк. (Это в основном то, что вы ожидаете; подход бинарного дерева TreeSet<String> направлен на то, чтобы сделать абсолютно минимальное возможное количество сравнений.)
- e и f были маленькими; то есть, когда я вызывал
add(...) s и remove(...) s только небольшое количество раз за итерацию. (Это именно то, что вы предсказали.) Точная точка оборота зависела от a , b и c , но в первом приближении ConcurrentSkipListSet<String> показали лучшие результаты, когда e + f было меньше, чем около 10, а TreeSet<String> показали лучшие результаты, когда e + f было больше около 20.
Конечно, это было на машине, которая может выглядеть совсем не так, как ваша, с использованием JDK, который может выглядеть совсем не так, как ваш, и с использованием очень искусственных данных, которые могут выглядеть совсем не так, как ваша. Я бы порекомендовал вам запустить свои собственные тесты. Так как Tree* и ConcurrentSkipList* оба реализуют Sorted*, у вас не должно возникнуть никаких проблем, пробуя свой код в обоих направлениях и видя то, что вы найдете.
Насколько я знаю, ConcurrentSkipList * в основном являются реализациями без блокировок, основанными на CAS, поэтому они не должны нести (много) накладных расходов, [& hellip;]
Насколько я понимаю, это будет зависеть от машины. В некоторых системах реализация без блокировок может быть невозможна, и в этом случае эти классы должны будут использовать блокировки. (Но поскольку вы на самом деле не многопоточность, даже блокировки не могут стоить все дорого. Конечно, синхронизация требует дополнительных затрат, но ее стоимость main является конфликтом блокировок и принудительной одиночной Это не проблема для вас. Опять же, я думаю, вам просто нужно протестировать и посмотреть, как работают две версии.)