ШмякВопрос больше из области теории.
Необходимо хранить структуру данных в виде некого набора пар число-число
причем число ключ должно быть уникальным и число значение тоже уникально.

Какой диапазон чисел? byte/int/long/BigDecimal?
Какие основные операции? Какие наиболее частые?

ШмякВсякие там Map и List не предлагать.
Значений в массиве может быть достаточно много и необходимо минимизировать расход ресурсов на это дело.

Ой, да ладно. Экономия на спичках? Сколько "достаточно много"?


ШмякЕсть здравые предложения? :)
Есть opensource реализации коллекций для примитивов.
Сама структура особого смысла не имеет, если не знать какие операции нужны.
Пока только поняли что нужна проверка или замещение при вставке. Так как кажое должно быть уникальным, то, наверное, проверка, а не замещение?

ШмякЗапишите в Map подобную структуру хотя бы до Integer.MAX_VALUE/2 и посмотрите сколько оно отожрет?

Ты прикалываешься?
Integer.MAX_VALUE = 2,147,483,647
Integer.MAX_VALUE / 2 ~ 1G, 4 байта на int - 4Gb.
Тут даже без HashMap обосрешься массив на андроиде создавать.

ШмякА теперь подобную операцию проделайте на Андроиде, где ресурсы счет любят.
С этого стоило бы начать вопрос. А то любят тут спрашивать-спрашивать, а в конце темы написать, мол J2ME.

ШмякВот если бы все было так просто, я бы и не спрашивала.
Я спросил сколько ожидается пар. Получил ответ померять Integer.MAX_VALUE/2. Это не похоже на реалистичное значение, потому что даже простой массив такого размера придется размещать на долговременном хранилище, а не памяти.
Поэтому может обсудим реалистичную постановку задачи?

Так обязательно в памяти размещать? Или можно в файле? Тогда проще, так как ключи упорядочены, можно весь диапазон разбить по сегментам и быстро вычислять сегмент из значения, как в HashMap.

ШмякОпераций никаких нет, последовательное чтение элементов.
Т.е. это постоянный массив, который в процессе не модифицируется?

ШмякВы вот все хотите подогнать под существующие структуры, желание ясно.

А они достаточно оптимизированы. И все мои вопросы снова игнорируются. :(


ШмякДопустим необходимо случайным образом выбирать числа от 1 до Integer.MAX_VALUE.
При этом если генератор случайных чисел выдаст число(масло масляное), которое уже было необходимо остановить обработку.
Как бы вы эту задачу реализовали?
Шафл бы сделал вместо генератора. Опять задача выдрана из конктекста. Я могу кучу вариантов привести, но вы их отметёте, потому что у вас свой контекст и вы его знаете.
На сколько генератор нормально распределен? Можно пробовать выделять диапазоны и вводить для них уровень использованности.
Как долго длиться обработка? Если долго, то массив можно и в файловой системе разместить.
У меня тут куча вопросов, которые влияют на оптимальность решения. А на них нет ни одного ответа.

ШмякУчите мат часть, разница есть и большая.
Нет особой разницы
http://habrahabr.ru/post/159557/
Либо данные можно в памяти разместить, тогда 4-10-20 байт на элемент роли не сыграют.
Либо нельзя тогда размещаем в файловой системе или базе.

ШмякМассив определяется в начале работы и в процессе уже не меняется.
Наконце-то детали начали поступать.

ШмякТ.е. определяется его размер и заполняется данными. И в процессе работы бегаем по нему вперед и назад.
Размер может быть маленьким а может быть максимальным. Закладываемся на критическое значение.
Т.е. задача вообще не в том чтобы провалидировать, или наполнить. А исключительно оптимизировать хранение и перебор? Можно же было сразу объяснить?

ШмякДопустим необходимо случайным образом выбирать числа от 1 до Integer.MAX_VALUE.
При этом если генератор случайных чисел выдаст число(масло масляное), которое уже было необходимо остановить обработку.
Как бы вы эту задачу реализовали?
Как обычно никто не может нормально объяснить что нужно. Вот ещё раз перечитал.
"необходимо остановить обработку" - обработку чего? Где мы её в задаче начали? Вообще весь процесс остановить?

Йуный джавистЪИспользуйте фильтр блума.
О! Примерно то что я думал. Можно закрывать целые регионы и с высокой долей вероятности говорить что там нет свободных чистел.
Но вот и формализированое представление. Спасибо!

ШмякОбработка длится долго.
И если уж конкретней, то в массиве хранятся не сами данные а индексы элементов другого массива, в котором эти данные и есть, он вот и хранится в файле. Типа, индекс :)
Грубо говоря, в файле хранится много-много строк и необходимо эти строки случайным образом перемешать и последовательно обрабатывать вперед, назад... по желанию пользователя. Но в исходном файле данные перемешивать нельзя.
Вот так задача "сделать коллекцию" превратилась в задачу "реализовать шафл".

ШмякРебята, вы откуда взялись? Вы решаете задачу тупо в лоб!
Т.е. не решаете а просто подгоняете.
Как объяснил, так и решаем.

ШмякПо поводу студенческой задачи расскажу ответ.
Необходимо хранить не само число а признак того, что число уже встречалось.

ОК. Как это свяазано с задачами шафла и создания коллекции?

ШмякТ.е. надо не массив int хранить размера Integer.MAX_VALUE, а массив bit размера Integer.MAX_VALUE.

Логично. У нас уже есть 3 задачи. Одну решили. Осталось две.

Шмяки тогда вы израсходуете не 8.5 гигов, если решать задачу тупо в лоб, а примерно 8 мегов.
MAX_VALUE это 2G по одном биту на число это 2G/8~270Mb, а не 8.

ШмякЛаднушки, тему закрыла.
ОК.

ШмякНе хватает у меня араторских способностей объяснить вам задачу.
"арать" :)
Вы из более чем десяти моих вопросов ответили на два. Т.е. вам ваш же собственный вопрос не интересеню

ШмякИли вы ее понимать не хотите. :)
ЧСВ

BlazkowiczMAX_VALUE это 2G по одном биту на число это 2G/8~270Mb, а не 8.
Стоит так же отметить что до примерно 1млн итерций, битовый массив, возможно, будет не самой оптимальной структурой по потреблению памяти.