Как бы вы справились с созданием массива или списка, который имел бы больше записей, чем стандартная реализация позволила бы вам получить доступ?

Question

Я пытаюсь создать массив или список, который мог бы теоретически обрабатывать, учитывая адекватное аппаратное обеспечение и такое, как 100 ^ 100 записей BigInteger. Проблема с использованием массива или стандартного списка состоит в том, что они могут содержать только количество записей Integer.MAX_VALUE. Как бы вы обходили эти ограничения? Совершенно новый класс / интерфейс? Обертка для списка? совсем другой тип данных?

Answer 1

В 22-мерном Java-массиве будет достаточно места для хранения данных - теоретически.

Но мы должны помнить, что число атомов во всей вселенной оценивается в 10 ^ 78 ( ссылка на немецком языке ).

Итак, прежде чем приступить к реализации, вам нужно подумать, как хранить 10 ^ 23 байта на каждом атоме во вселенной ...

Редактировать

В общем, если вам нужны большие структуры данных, поддерживающие доступ в O (1), вы можете создавать многомерные массивы.

2-мерный массив массив [Integer.MAX_VALUE] [Integer.MAX_VALUE] может содержать около 4.6x10 ^ 18 значений. Вы можете адресовать каждое значение ai массивом [ai mod Integer.MAX_VALUE] [ai div Integer.MAX_VALUE] . И, конечно, это работает и для многомерных массивов.

Answer 2

100 ^ 100 = 10 ^ 200. Предполагая, что объем памяти BigInteger составляет 28 байт (у него 7 int полей), это 2,8 * 10 ^ 201 байт или 2,8 * 10 ^ 192 гигабайт. Там нет адекватного оборудования и никогда не будет: -)

Answer 3

Я бы создал новый тип интерфейса, который учитывал бы большие значения. Возможно использование long для максимального размера и параметров индекса.

Answer 4

Я думаю, что по нескольким причинам вы пытаетесь создать свою собственную коллекцию. Во-первых, интерфейс списка предполагает длину int. Хотя вы могли бы заставить реализацию списка не быть 0 на основе теории, что удвоило бы вашу потенциальную емкость, это все равно было бы рискованно.

Другая причина в том, что вы, вероятно, смотрите на что-то, не сохраненное в памяти полностью, поэтому кэширование, индексирование, итерации и т. Д. Будут зависеть от внешних ресурсов, и вам может потребоваться только получение по индексу или итератору, а не оба .

Это звучит как огромная проблема распределенных вычислений, и это не то, для чего были разработаны Java-коллекции.

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

Answer 5

Вы можете эффективно получить 64-битное целое число из 2-х 32-битных или 128-битное целое из 4-х 32-битных, или даже любой размер, который вам требуется из достаточного количества целых.

Чтобы продемонстрировать, рассмотрим простейший случай представления 64-битного типа int с 2 32-битными целыми числами.

Какой-то псевдокод:

int64 c = Get64BitInt(int32 a, int32 b)
{
   c = 2^32*a + b
}

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

Answer 6

Вы можете использовать связанный список ... но вы умрете до того, как list.get(list.size()-1) вернет: -)

Кстати, взгляните на Fastutil библиотеку коллекций, которая может работать с большим количеством данных.

Answer 7

Первое, что приходит мне в голову, - это создать новый тип ArrayList, который поддерживает индексы long и имеет массив из нескольких ArrayList. Затем вы можете реализовать методы get / set / etc, чтобы при доступе к индексу больше 2 ^ 32 доступ к следующему ArrayList в массиве. Чтобы определить, какой массив использовать, хэшируйте индекс по (2^32 - 1) mod index.

Чтобы справиться с проблемой ограничения размера, вам придется сериализовать некоторые массивы на диск. Однако если вы находитесь в HPC, это не такая большая проблема . система с общей памятью У меня есть доступ к 256 ГБ доступной памяти на узел. То, сколько времени вам потребуется, чтобы перебрать этот список, является еще одной проблемой, но я думаю, что астрофизики делают вещи, близкие к этому масштабу.

Размер списка выглядит слишком большим, чтобы с ним можно было работать (как говорили другие авторы), поэтому вам придется уменьшать масштаб до работоспособного размера.