代码之家 › 专栏 › 技术社区 › Romain Linsolas

如何在计算过程中存储数百万个双精度?

data-structures performance java

Romain Linsolas · 技术社区 · 15 年前

我的引擎正在执行1000000个模拟 X 交易。在每个模拟过程中,对于每个交易,可以验证特定的条件。在这种情况下,我存储值(它是 double )形成一个数组。每个交易都有自己的价值列表(即,这些价值是从一个交易到另一个交易的独立价值)。

在所有模拟的最后,对于每个交易,我在他的 List<Double> 得到一些输出。不幸的是,这个算法需要这些值的完整列表,因此,我无法修改我的算法来“即时”计算输出,即在模拟过程中。

在“正常”条件下(即 X 如果是低值,并且验证条件的时间少于10%),则计算将正确结束,即使这可能会得到增强。

我的问题发生在我有很多交易的时候(例如 X = 30 )几乎所有的模拟都验证了我的特定条件(假设90%的模拟)。所以为了存储这些值,我需要 900,000 * 30 * 64bits 内存(约216MB)。我未来的一项要求是能够运行5000000次模拟…

所以我不能继续使用我当前的存储值的方法。目前,我使用的是 Map<String, List<Double>> ,其中键是元素的ID,并且 列表<double> 值列表。

所以我的问题是,如何增强应用程序的这个特定部分,以减少模拟过程中的内存使用?

另一个重要注意事项是,对于最终计算,我的 列表<double> (或我将使用的任何结构) 必须订购 . 因此,如果我前面问题的解决方案还提供了一个结构,用于排序新插入的元素(例如 SortedMap )这将是非常棒的!

我使用的是Java 1.6。

编辑1

我的引擎确实在执行一些财务计算,在我的例子中,所有交易都是相关的。这意味着我不能对第一笔交易运行我的计算,获取输出,清除 列表<double> ,然后转到第二个交易,依此类推。

当然,作为临时解决方案,我们将增加分配给引擎的内存,但这不是我期望的解决方案;)

编辑2

关于算法本身。我不能给出精确的算法,但这里有一些提示:

我们必须整理一下 列表<double> . 然后我将计算一个索引(根据给定参数和 List 本身)。然后,我终于把 index-th 此列表的值。

public static double algo(double input, List<Double> sortedList) {
    if (someSpecificCases) {
        return 0;
    }
    // Calculate the index value, using input and also size of the sortedList...
    double index = ...;
    // Specific case where I return the first item of my list.
    if (index == 1) {
        return sortedList.get(0);
    }
    // Specific case where I return the last item of my list.
    if (index == sortedList.size()) {
        return sortedList.get(sortedList.size() - 1);
    }
    // Here, I need the index-th value of my list...
    double val = sortedList.get((int) index);
    double finalValue = someBasicCalculations(val);
    return finalValue;
}

我希望现在能得到这样的信息…

编辑3

目前,我不会考虑任何硬件修改(这里太长和复杂:()。增加内存的解决方案将完成,但这只是一个快速修复。

我在想一个使用临时文件的解决方案:直到某个阈值(例如100000),我的 列表<double> 在内存中存储新值。当尺寸 列表<double> 达到这个阈值后,我将这个列表附加到临时文件中(每个交易一个文件)。

像这样:

public void addNewValue(double v) {
    if (list.size() == 100000) {
        appendListInFile();
        list.clear();
    }
    list.add(v);
}

在整个计算结束时,对于每个交易,我将重新构造完整的 列表<double> 从我的记忆和临时文件中。然后,我运行我的算法。我清理这个交易的值,然后转到第二个交易(我现在可以这样做,因为所有的模拟现在都完成了)。

你觉得这样的解决方案怎么样?你认为可以接受吗?

当然,我会浪费一些时间在外部文件中读写我的值,但我认为这是可以接受的,不是吗?

10 回复 | 直到 15 年前

JeremyP 15 年前

你能不能用彩车而不是双打?这样可以节省100MB。

msw 15 年前

你的问题是算法,你正在寻找一个“强度降低”的优化。

不幸的是,您在问题描述中过于腼腆,并说“不幸的是,这个算法需要这些值的完整列表…”,这是可疑的。模拟运行已经传递了一个谓词,它本身告诉您一些关于通过筛选的集的信息。

我希望符合标准的数据具有 low information content 因此可以承受很大的压缩。

没有进一步的信息,我们真的帮不了你更多。

JohnB 15 年前

您提到“引擎”没有连接到数据库,但是您是否考虑使用数据库来存储元素列表?可能是嵌入式数据库,比如sqlite?
如果你用过 int 甚至 short 而不是 string 你的关键领域 Map ,这可能会节省一些内存。
如果您需要一个保证顺序的集合对象,那么考虑 Queue 或A Stack 代替你 List 您当前正在使用的。
可能想一个按顺序处理交易的方法,正如Dommer和Alan已经建议的那样。

希望能有所帮助!

编辑:

你对只有30把钥匙的评论是一个很好的观点。

在这种情况下,既然您必须同时计算所有交易,那么您是否考虑将您的 表 S到磁盘(即XML)?
或者甚至只为每个人在磁盘上写一个文本文件 表 ,然后在计算交易后,加载一个文件/ 表 一次验证 表 条件?

当然缺点是文件IO速度慢,但是这样会降低服务器的内存需求。

Tom Chantler 15 年前

只是为了澄清一下,您是否需要同时将所有信息存储在内存中?听起来你在做金融模拟(可能是信用风险?)。假设您正在处理30个交易,是否需要将所有值存储在内存中?或者可以运行第一个交易(~900000*64位),然后丢弃double列表(将其序列化到磁盘或其他东西),然后继续下一个交易吗?我想这也许可以,就像你说的,交易是相互独立的。

如果这听起来有点屈尊俯就道歉,我只是想对这个问题有个正确的认识。

Gareth Davis 15 年前

轻率的答案是获得更多的记忆。Sun JVM可以(几乎很高兴)处理多个千兆字节的堆,如果它是一个批处理作业,那么更长的GC暂停时间可能不是一个大问题。

您可能会认为这不是一个明智的解决方案,首先尝试编写一个自定义列表(如集合),但让它存储基元双精度值而不是对象包装双精度值对象。这将有助于节省为每个双对象包装器支付的每个对象开销。我认为Apache公共集合项目有原始集合实现,这些可能是一个起点。

另一个级别是在堆外的NIO缓冲区中维护double列表。这有一个优点,即用于数据的空间实际上在GC运行中没有考虑到,理论上可能会引导您在内存映射文件中管理数据结构。

Alan Geleynse buhbang 15 年前

从您的描述来看,您似乎无法轻松地提高内存使用率。double的大小是固定的,如果需要将所有结果保留到最终处理之前,则无法减小该数据的大小。

如果需要减少内存使用,但可以接受更长的运行时间,则可以替换 Map<String, List<Double>> 用一个 List<Double> 一次只处理一个交易。

如果您必须拥有所有交易的所有价值,那么您唯一的选择就是增加可用内存。内存使用率的计算只基于值的大小和值的数量。如果没有减少所需值数量的方法,任何数据结构都无法帮助您,只需增加可用内存即可。

High Performance Mark 15 年前

根据你告诉我们的,听起来你需要10^6 x 30个处理器(即模拟数量乘以交易数量),每个处理器都有几个k RAM。不过,也许您没有那么多处理器——您是否有30个处理器,每个处理器都有足够的内存用于一次交易的模拟?

认真地说:把你的程序并行化,买一台32GB内存的8核计算机(或者16核W64GB或…)。你迟早会这样做的,不妨现在就这么做。

Natalie Adams 15 年前

有一种理论,我之前读过,在那里你将把数据写到磁盘上,只读/写你所读的一大块。当然,这描述的是虚拟内存,但这里的区别在于程序员控制流和位置的速度比操作系统的速度快。这样做的好处是,操作系统只分配了这么多的虚拟内存,您可以访问整个硬盘。

或者更简单的选择就是增加交换/分页内存,我认为这很愚蠢,但对您的情况有帮助。

在快速搜索之后,如果您在Windows上运行,此功能似乎可以帮助您: http://msdn.microsoft.com/en-us/library/aa366537(VS.85).aspx

slomobile 15 年前

你说你需要访问所有的价值观,但你不可能同时操作所有的价值观?您是否可以序列化数据以便将其存储在单个文件中?每个记录都由一些分隔符、键值或简单的字节计数分隔开。无论哪种方法,都要保留一个字节计数器。让它成为一个由左文件和右文件组成的“循环文件”,它们的操作类似于相反的堆栈。当数据从左文件中弹出(读取)时,它被处理并推(写)到右文件中。如果您的下一个操作需要以前处理过的值,请反转文件传输的方向。将您的算法视为驻留在硬盘的读/写头上。您可以使用不同的方法以大大降低的速度访问列表。速度会有很大影响,但如果您可以优化序列化顺序,使最可能访问的数据按使用顺序位于文件的顶部,并可能将左右文件放在不同的物理驱动器上,而页面文件放在第三个驱动器上,则由于顺序和同时读写。当然要比听起来难一点。每次更改方向都需要完成两个文件。逻辑上是这样的, 如果(从左到右的当前数据流)将EOF发送到右_文件;左_文件=左_文件-右_文件;实际上,您希望将所有数据保留在其物理驻留在驱动器上的位置,只需操作主文件表中文件的开始和结束地址。字面上的操作就像一对硬盘堆栈。这将是一个比简单地添加更多内存慢得多、更复杂的过程,但比单独的文件效率高得多,而且每个记录一个文件的所有开销*数百万条记录。或者将所有数据放入数据库。我刚想到这个主意。我从来没有做过,甚至没有听说过。但我想肯定有人在我之前就想到了。如果没有,请告诉我。我真的可以用我简历上的学分。

Marit 15 年前

一种解决方案是将double格式化为字符串,然后将其添加到(快速)键值存储中,该存储按设计顺序排序。

然后您只需要从存储中按顺序读取。

这是一个“自然”排序的商店,当它们被插入时。

他们夸口说他们是以每秒1亿条的速度进行搜索的(搜索速度几乎是搜索速度的两倍):

http://forum.gwan.com/index.php?p=/discussion/comment/897/#Comment_897

对于只有3个调用的API,应该很容易测试。

第四个调用将提供基于范围的搜索。