4

我正在使用 java 程序从数据库中获取一些数据。然后我计算一些数字并开始将它们存储在一个数组中。我正在使用的机器有 4 GB 的 RAM。现在，我不知道会提前多少个数字，所以我使用 anArrayList<Double>.但我知道大概会有300 million numbers.

因此，由于一个 double 是 8 个字节，因此该数组将消耗的内存的粗略估计是 2.4 gigs（可能更多，因为 ArrayList 的开销）。在此之后，我想计算这个数组的中位数，并使用将数组org.apache.commons.math3.stat.descriptive.rank.Median作为输入的库double[]。所以，我需要ArrayList<Double>将double[].

我确实看到了很多提出这个问题的问题，他们都提到没有办法循环遍历整个数组。现在这很好，但由于它们还在内存中维护这两个对象，这使我的内存需求达到了 4.8 gigs。现在我们遇到了一个问题，因为我们可用的总 RAM 有 4 个演出。

首先，我是否怀疑该程序会在某些时候给我一个正确的内存错误（它当前正在运行）？如果是这样，我如何计算中位数而不必分配双倍的内存？我想避免对数组进行排序，因为计算中位数是 O(n)。

4

4 回答 4

6

您的问题比您意识到的还要糟糕，因为ArrayList<Double>它的效率远低于每个条目 8 个字节。每个条目实际上是一个对象，其中ArrayList保存着一个引用数组。一个Double对象大概有 12 个字节（4 个字节用于某种类型标识符，8 个字节用于double自身），并且对它的引用又增加了 4 个字节，使每个条目的总数达到 16 个字节，甚至不包括内存管理和这样的。

如果约束更宽一些，您可以实现自己的DoubleArray，由 a 支持double[]但知道如何调整自身大小。但是，调整大小意味着您必须同时在内存中保留旧数组和新数组的副本，这也超出了内存限制。

不过，这仍然留下了一些选择：

  • 循环输入两次；一次计算条目，一次将它们读入正确大小的double[]. 当然，这取决于您输入的性质是否可行。

  • 对最大输入大小（可能是用户可配置的）做出一些假设，并预先分配一个double[]这个固定大小。仅使用已填充的部分。

  • 使用float而不是double将内存需求减少一半，但会牺牲一些精度。

  • 重新考虑您的算法，以避免一次将所有内容都保存在内存中。

于 2013-11-10T10:40:23.737 回答
2

有许多为基元创建动态数组的开源库。其中之一： http ://trove.starlight-systems.com/

于 2013-11-10T11:20:38.883 回答
1

中值是排序列表中间的值。所以你不必使用第二个数组，你可以这样做：

Collections.sort(myArray);
final double median = myArray.get(myArray.size() / 2);

而且由于无论如何您都是从数据库中获取数据，因此您可以告诉数据库给您中间值，而不是在 Java 中进行，这也将节省传输数据的所有时间（和内存）。

于 2013-11-10T11:06:40.640 回答
1

我同意，使用 Trove4jTDoubleArrayList类（参见javadoc）存储双精度或TFloatArrayList浮点数。通过结合以前的答案，我们得到：

// guess initialcapacity to remove requirement for resizing
TDoubleArrayList data = new TDoubleArrayList(initialcapacity);
// fill data
data.sort();
double median = data.get(data.size()/2);
于 2013-11-10T12:09:20.837 回答