如何在计算过程中存储数百万的Double?

我的引擎正在对X交易执行1,000,000次模拟。 在每次模拟期间,对于每笔交易,可以validation特定条件。 在这种情况下,我将值(它是一个double )存储到一个数组中。 每笔交易都有自己的价值清单(即这些价值从一笔交易到另一笔交易都是独立的)。

在所有模拟结束时,对于每笔交易,我在他的List上运行一个算法来获得一些输出。 不幸的是,这个算法需要这些值的完整列表,因此,我无法修改我的算法来“即时”计算输出,即在模拟期间。

在“正常”条件下(即X为低,并且validation条件的时间少于10%),计算结束正确,即使可以增强。

当我有很多交易(例如X = 30 )并且我的几乎所有模拟都validation了我的特定条件(比如90%的模拟)时,我的问题就出现了。 所以只是为了存储值,我需要大约900,000 * 30 * 64bits 64位的内存(大约216Mb)。 我未来的要求之一是能够运行5,000,000次模拟……

所以我无法继续目前存储值的方式。 目前,我使用了Map<String, List>的“简单”结构,其中键是元素的ID, List是值列表。

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

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

我使用的是Java 1.6。


编辑1

我的引擎确实正在执行一些财务计算,在我的情况下,所有交易都是相关的。 这意味着我无法在第一笔交易中运行计算,获取输出,清理List ,然后转到第二笔交易,依此类推。

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


编辑2

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

我们必须处理已排序的List 。 然后我将计算一个索引(根据给定的参数和List本身的大小计算)。 然后,我最终返回此List的index-th值。

 public static double algo(double input, List 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

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

我在想一个使用临时文件的解决方案:在某个阈值(例如100,000)之前,我的List将新值存储在内存中。 当List的大小达到此阈值时,我将此列表附加到临时文件中(每个交易一个文件)。

像这样的东西:

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

在整个计算结束时,对于每笔交易,我将从内存中以及临时文件中重建完整的List 。 然后,我运行我的算法。 我清理了这笔交易的价值,并转到第二笔交易(我现在可以这样做,因为现在所有的模拟都已完成)。

你怎么看待这样的解决方案? 你认为这是可以接受的吗?

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

你能逃脱使用花车而不是双打吗? 这样可以节省100Mb。

你的问题是算法,你正在寻找“减少强度”优化。

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

我希望符合标准的数据信息含量低 ,因此可以进行大量压缩。

没有进一步的信息,我们真的无法帮助你。

  1. 您提到“引擎”未连接到数据库,但您是否考虑使用数据库来存储元素列表? 可能是一个嵌入式数据库,如SQLite?

  2. 如果你使用int或甚至short而不是string作为Map的关键字段,那可能会节省一些内存。

  3. 如果您需要一个保证订单的集合对象,请考虑使用QueueStack而不是您当前使用的List

  4. 正如Dommer和Alan已经建议的那样,可能会想到一种顺序运行交易的方法。

我希望有一些帮助!


编辑:

您对只有30个键的评论是一个好点。

  1. 在这种情况下,由于您必须同时计算所有交易,那么您是否考虑过将List序列化为磁盘(即XML)?

  2. 或者甚至只是为每个List写一个文本文件到磁盘,然后在计算交易后,一次加载一个文件/ List来validation条件List

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

只是为了澄清一下,您是否需要一次内存中的所有信息? 听起来你正在进行金融模拟(也许是信用风险?​​)。 假设您正在运行30笔交易,您是否需要将所有值存储在内存中? 或者你可以运行第一笔交易(约900,000 * 64位),然后丢弃双重列表(将其序列化为磁盘或其他东西),然后继续下一个? 我认为这可能没关系,因为你说这些交易是彼此独立的。

如果这听起来很光顾,请道歉; 我只是想弄清问题。

轻率的答案是获得更多的内存。 Sun JVM可以(几乎很开心)处理多GB的堆,如果它是一个批处理作业,那么更长的GC暂停可能不是一个大问题。

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

另一个级别是在堆中的nio Buffer中维护双精度列表。 这样做的好处是,在GC运行中实际上不考虑用于数据的空间,理论上可能会导致您在内存映射文件中管理数据结构。

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

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

如果您必须拥有所有交易的所有值,您唯一的选择是增加可用内存。 您对内存使用量的计算仅基于值的大小和值的数量。 如果没有办法减少所需的值数量,没有数据结构可以帮助您,您只需要增加可用内存。

从你告诉我们的情况来看,你需要10 ^ 6 x 30个处理器(即模拟次数乘以交易次数),每个处理器都有几个K RAM。 也许,你没有那么多的处理器 – 你有30个,每个处理器的模拟有足够的内存吗?

说真的:将您的程序并行化并购买一台配备32GB RAM(或16核64GB或……)的8核计算机。 你迟早要做这件事,不妨现在就去做。

有一种理论,我读了一段时间,你会把数据写入磁盘,只读/写你的大块。 当然这描述了虚拟内存,但不同之处在于程序员比操作系统控制流量和位置。 优点是操作系统只分配了很多虚拟内存,您可以访问整个HD。

或者更容易的选择只是增加你的交换/分页内存,我认为这将是愚蠢的,但在你的情况下会有所帮助。

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

您说您需要访问所有值,但您不可能同时对所有值进行操作? 您可以序列化数据,以便将其存储在单个文件中。 每个记录通过某些分隔符,键值或简单的字节计数分开设置。 保持字节计数器的方式。 让它成为一个由左文件组成的“循环文件”和一个像对立堆栈一样操作的右文件。 当数据从左侧文件中弹出(读取)时,它将被处理并推送(写入)到正确的文件中。 如果您的下一个操作需要先前处理的值,则反转文件传输的方向。 将您的算法视为驻留在硬盘驱动器的读/写头上。 您只需使用不同的方法并以极低的速度访问列表即可。 速度命中率很高但是如果您可以优化序列化序列,以便最有可能访问的数据按使用顺序位于文件顶部,并且可能将左右文件放在不同的物理驱动器和页面文件上第三个驱动器,由于顺序和同时读写,您将从增加的硬盘性能中受益。 当然它比听起来有点难。 每次更改方向都需要最终确定两个文件。 逻辑上类似if(当前数据流如果从左到右){将EOF发送到right_file; left_file = left_file – right_file;}实际上,您希望将所有数据保留在物理上驻留在驱动器上的位置,并且只需操作主文件表中文件的开始和结束地址。 字面操作就像一对硬盘堆栈。 与简单地添加更多内存相比,这将是一个更慢,更复杂的过程,但是比单独的文件更有效,并且每个记录1个文件的所有开销*数百万条记录。 或者只是将所有数据放入数据库中。 FWIW,这个想法刚刚来到我身边。 我从来没有真正做过,甚至没有听说过它。 但我想有人必须在我之前想到它。 如果没有,请告诉我。 我真的可以在我的简历上使用这笔款项。

一种解决方案是将双打格式化为字符串,然后将它们添加到按照设计排序的(快速)键值存储中。

然后你只需要从商店顺序阅读。

这是一个商店,在插入时自然地对条目进行排序。

并且他们吹嘘他们以每秒1亿条目的速度进行这项工作(搜索速度几乎是其两倍):

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

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

第四次通话将提供基于范围的搜索。