Набор целых чисел. Возможное увеличение производительности в случае увеличения новых записей

Question

Если вы были высококвалифицированным Java-разработчиком с низкой задержкой (я не являюсь), и вам было предложено реализовать набор int (примитив или нет), было бы возможно для вас получить дополнительный прирост производительности при гарантированном предварительном условии что каждая новая запись выше, чем любое другое значение, ранее сохраненное в наборе?

Насколько значительным может быть этот выигрыш для add, contains а также remove операции в лучших / худших сценариях?

С одной стороны, кажется естественным, что такое ограничение приведет к повышению производительности. С другой стороны, неубывающие записи - это очень распространенная ситуация (например, при создании уникального идентификатора), и если бы выигрыш стоил борьбы, то более или менее известная реализация была бы уже разработана.

Answer 1

Когда вы проверяете этот вопрос, вы обнаружите, что add а также contains уже O(1). Так что улучшать там особо нечего.

И я думаю, что эти двое могли бы только один раз извлечь выгоду из этого ограничения:

• "добавление" становится проще, потому что вы можете просто запомнить последнее добавленное значение; так что нужна только одна проверка, когда приходит новое значение
• аналогично, при запросе "содержаться"; у вас есть первая предварительная проверка, которая мгновенно сообщает вам, когда данное значение не может быть в наборе

Но это об этом.

И кроме того: если ваше ограничение действительно состоит в том, что каждая "новая" запись, которая должна быть добавлена, больше, чем последняя - тогда вам не нужен набор в первую очередь. Потому что ваше ограничение гарантирует, что все элементы будут уникальными. Так что в этом смысле вы тоже можете просматривать списки...

Что касается комментария, который задает вопрос между возможными дельтами между O (1) и O(1.5); мой ответ:

Разница между O (1) и O(n) носит теоретический характер, вы отвечаете, что используете ручку и лист бумаги. Разница между O(1.0) и O(1.005) ... там я бы начал с экспериментов и тестов.

Значение: эти "реальные" факторы зависят от различных элементов, которые "близки" к базовой реализации. Вы начнете с изучения того, как Набор, который вы используете в настоящее время, реализован для вашей платформы; и как JVM на вашей платформе выполняет компиляцию точно в срок. После этого вы можете сделать выводы о том, что можно улучшить, приняв во внимание это ограничение.

В заключение; относительно ограничения, ухудшающего существующие реализации. Я предполагаю, что это также могло случиться; как сказано выше: такие детали действительно зависят от конкретной реализации. И кроме того: вы назвали три разные операции; и фактические результаты могут быть очень разными; в зависимости от типа операции.

Если бы мне пришлось работать над этой проблемой; Я бы начал с создания достаточно больших файлов с "тестовыми данными" (случайные числа, числа только для увеличения и их вариации). И тогда я бы использовал настоящий профилировщик (или, по крайней мере, сложный сравнительный анализ) и начал измерять.