我正在尝试创建一个理论上可以处理的数组或列表，给定足够的硬件等，多达 100^100 个 BigInteger 条目。使用数组或标准列表的问题在于它们只能容纳 Integer.MAX_VALUE 数量的条目。您将如何解决此限制？一个全新的类/界面？列表的包装？完全是另一种数据类型？
问问题
195 次
7 回答
4
100^100 = 10^200。假设 BigInteger 的内存占用为 28 个字节（它有 7 个int字段），即 2.8 * 10^201 字节或 2.8 * 10^192 GB。没有足够的硬件，永远不会有:-)
于 2009-07-09T17:16:31.333 回答
4
理论上，一个 22 维的 java 数组将有足够的空间来保存数据。
但我们应该记住，整个宇宙中的原子数估计为 10^78（德语 ref）。
因此，在开始实施之前，您必须考虑如何在宇宙中的每个原子上存储 10^23 个字节......
编辑
一般来说，如果您需要支持 O(1) 访问的大型数据结构，您可以创建多维数组。
一个二维数组array[Integer.MAX_VALUE][Integer.MAX_VALUE]可以容纳大约4.6x10^18 个值。您可以通过array[ai mod Integer.MAX_VALUE][ai div Integer.MAX_VALUE]处理每个值ai。当然，这也适用于高维数组。
于 2009-07-09T17:27:39.173 回答
1
我将创建一个允许更大值的新接口类型。可能使用 long 作为最大大小和索引参数。
于 2009-07-09T17:27:59.187 回答
0
我首先想到的是创建一个支持索引并具有多个's数组的新ArrayList类型。然后您可以实现 get/set/etc 方法，以便当您访问大于 2^32 的索引时，访问数组中的下一个。要确定要使用哪个数组，请按 对索引进行散列。longArrayListArrayList(2^32 - 1) mod index
要处理大小约束问题，您必须将一些数组序列化到磁盘。不过，如果您使用 HPC，这不是什么大问题。我可以访问的共享内存系统每个节点有 256GB 可用内存。遍历该列表需要多长时间是另一个问题，但我认为天体物理学家所做的事情接近那个规模。
列表的大小看起来太大而无法使用（正如其他海报所说），因此您必须将其缩小到可行的大小。
于 2009-07-09T17:16:33.733 回答
0
你可以使用链表......但你会在list.get(list.size()-1)返回之前死掉:-)
顺便说一句，看看可以处理大量数据的Fastutil集合库。
于 2009-07-09T17:19:03.167 回答
0
您可以有效地从 2 个 32 位整数中获得 64 位整数，或者从 4 个 32 位整数中获得 128 位整数，或者实际上从足够多的整数中获得您需要的任何大小。
为了演示，考虑用 2 个 32 位整数表示 64 位整数的最简单情况。
一些伪代码：
int64 c = Get64BitInt(int32 a, int32 b)
{
c = 2^32*a + b
}
您可以定义一个新类来保存大整数，使用整数数组来存储数字。您必须编写自己的算术方法，但这不应该太费力。
于 2009-07-09T17:25:57.990 回答
0
我认为出于几个原因，您正在考虑制作自己的系列。首先，列表接口采用 int 长度。尽管理论上您可以强制列表实现不为 0，从而使您的潜在容量增加一倍，但这仍然是冒险的。
另一个原因是您可能正在查看未完全存储在内存中的内容，因此缓存、索引、迭代等将具有外部资源依赖性，您可能只需要按索引或迭代器获取，而不是两者。
这听起来像是一个大规模的分布式计算问题，而这并不是 Java 集合旨在解决的问题。
但是，如果您只需要这么大的索引（因为您要在很长的线上绘制少量点），那么由 Map 支持的自定义界面（包含 BigInteger 键和表示列表内容的值）可能会为您提供什么你要。如果您真的想要类似 List 的行为， Map 实现可能必须单独跟踪插入顺序。
于 2009-07-09T17:33:46.540 回答