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

Question

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

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

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

Answer 1

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

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

• «добавление» становится легче, потому что вы могли бы просто вспомнить последнее значение, которое было добавлено; поэтому нужна только одна проверка, когда новое значение приходит в
• Аналогично, при запросе «содержится»; у вас есть первый предварительный чек, который говорит вам мгновенно, когда заданное значение может не быть в наборе

Но это о нем.

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

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

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

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

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

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