2010-10-14 35 views
6

我的引擎正在執行1,000,000次模擬X交易。在每次模擬過程中,對於每筆交易,都可以驗證特定條件。在這種情況下,我將該值(它是一個double)存儲到一個數組中。每筆交易都會有自己的價值清單(即這些價值從一筆交易到另一筆交易都是相互依存的)。如何在計算過程中存儲數百萬的Double?

在所有模擬結束時,對於每筆交易,我在他的List<Double>上運行算法以獲得一些輸出。不幸的是,該算法需要這些值的完整列表,因此,我無法修改我的算法來「即時」計算輸出,即在模擬期間。

在「正常」條件下(即X較低,條件驗證時間少於10%),即使可以增強計算,計算也會正確結束。

當我有很多交易時(例如X = 30),我的問題發生,幾乎所有的模擬驗證我的具體情況(比如說模擬的90%)。所以只是爲了存儲這些值,我需要約900,000 * 30 * 64bits的內存(約216Mb)。我未來的要求之一是能夠運行5,000,000次模擬...

因此,我無法繼續使用當前存儲值的方式。目前,我使用了一個「簡單」的結構Map<String, List<Double>>,其中關鍵是元素的ID和List<Double>值的列表。

所以我的問題是如何增強我的應用程序的這一特定部分,以減少模擬期間的內存使用量?

也是另一個重要的一點是,對於最後的計算,我的List<Double>(或其他結構,我將使用)必須訂購。所以如果我以前的問題的解決方案也提供了一個訂購新插入元素的結構(例如SortedMap),那將非常棒!

我正在使用Java 1.6。


編輯1

我的引擎正在執行一些財務計算的確,在我的情況下,所有的交易都有關。這意味着我不能運行我的第一筆交易的計算,獲得輸出,清理List<Double>,然後移動到第二筆交易,依此類推。

當然,作爲一個臨時解決方案,我們將增加分配到發動機的內存,但它不是我期待的解決方案;)


編輯2

關於算法本身。我不能在這裏給出確切的算法,但這裏有一些提示:

我們必須在排序的List<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

目前,我不會考慮任何硬件修改(太漫長而複雜在這裏:()。增加了內存的解決方案將完成,但它只是一個權宜之計。

我在想一個解決方案的那使用臨時文件:在某個閾值(例如100,000)之前,我的List<Double>將新值存儲在內存中。當List<Double>的大小達到此閾值時,我在臨時文件中追加此列表(每筆交易一個文件)。

類似的東西:

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

在整個計算結束時,每筆交易,我將重建從我有記憶,並在臨時文件的完整List<Double>。然後,我運行我的算法。我清理這筆交易的價值,並轉向第二筆交易(我現在可以這樣做,因爲現在所有的模擬都已完成)。

您對這樣的解決方案有什麼看法?你認爲這是可以接受的嗎?

當然,我會失去一些時間來閱讀和在外部文件中寫我的價值觀,但我認爲這是可以接受的,不是嗎?

+0

僅供參考:引擎是**不連接到任何數據庫。 – romaintaz 2010-10-14 15:15:14

+0

你說當X很小時,計算正確結束。當你增加X並且計算不能正確結束時?你有任何輸出錯誤? – Mark 2010-10-14 15:21:39

+0

當強力失敗時,多想一想。我看起來像你可能使用蒙特卡羅模擬方法,並且有關這個主題的大量文獻。 – msw 2010-10-14 15:33:08

回答

2

你能使用浮點數來代替雙打脫身?這將爲您節省100Mb。

+0

浮點運算不準確,會影響計算。 – Mark 2010-10-14 15:51:42

+0

你是對的馬克。然而,根據我的經驗,花車有時可以用於信用風險計算,但肯定不適用於前臺辦公系統。 – 2010-10-14 15:55:12

+2

@馬克羅賓遜:您的聲明適用於雙打和浮游物。這是一個問題,在這個特定情況下精度的損失是否重要。只有提問者才能回答這個問題。 – JeremyP 2010-10-14 15:57:06

1

從你的描述,似乎你將無法輕鬆地提高你的內存使用情況。雙精度的大小是固定的,如果您需要保留所有結果直到最終處理結束,您將無法減小該數據的大小。

如果您需要減少內存使用量,但可以接受更長的運行時間,則可以用List<Double>代替Map<String, List<Double>>,並且每次只處理一筆交易。

如果你必須有來自所有交易的所有值,你唯一的選擇是增加可用內存。您對內存使用情況的計算僅基於值的大小和值的數量。沒有辦法減少你需要的數值,沒有數據結構能夠幫助你,你只需要增加你的可用內存。

+0

看起來我們正在同時編寫類似的東西! – 2010-10-14 15:21:15

+0

確實。我應該表明,我必須同時運行所有交易。看我的編輯。 – romaintaz 2010-10-14 15:29:01

+0

如果你需要所有的交易,你將無法減少你的內存使用量。數據結構並不佔用你的內存,它是你需要的值。我更新了我的答案以包含此內容。 – 2010-10-14 15:32:44

2

只是爲了澄清,你需要的所有信息在內存中一次?這聽起來像你在做金融模擬(可能是信用風險?​​)。假設您正在運行30個交易,您是否需要將所有值存儲在內存中?或者你可以運行第一筆交易(約900,000 * 64位),然後放棄雙列表(將其序列化到磁盤或其他東西),然後繼續下一步?我認爲這可能是好的,因爲你說交易是相互獨立的。

道歉,如果這聽起來光顧;我只是想弄清楚這個問題。

+0

你是對的,這是用於財務計算。看我的編輯。 – romaintaz 2010-10-14 15:28:25

2

輕浮的答案是獲得更多的記憶。 Sun的JVM可以(幾乎高興地)處理幾千兆字節的堆,如果它是一個批處理作業,那麼較長的GC暫停可能不是一個大問題。

您可以決定,這不是一個明智的解決方案,嘗試的第一件事是寫像收集的自定義列表,但有它存儲原始雙打,而不是對象包裝雙對象。這將有助於節省您爲每個Double對象包裝器支付的每個對象開銷。我認爲Apache公共集合項目具有原始的集合實現,這可能是一個起點。

另一個層次是維護一個nio緩衝區堆中的雙打列表。這樣做的好處是,用於數據的空間實際上不在GC運行中考慮,理論上可能會導致您在管理內存映射文件中的數據結構的道路上走下坡路。

5

你的問題是算法,你正在尋找「減少力量」的優化。

不幸的是,你在問題描述中太過co and,並且說「不幸的是,這個算法需要這些值的完整列表......」這是可疑的。仿真運行已經通過了一個謂詞,它本身告訴你一些關於通過篩子的集合。

我希望符合標準的數據有low information content,因此可以大幅壓縮。

沒有進一步的信息,我們真的幫不了你。

+0

你說得對。我編輯了我的問題來添加我使用的僞算法。 – romaintaz 2010-10-14 15:43:44

0

有一個理論,我讀了一段時間,你會寫數據到磁盤,只讀/寫一塊你的。當然這描述了虛擬內存,但這裏的區別在於程序員控制的流程和位置比操作系統更棘手。這樣做的好處是操作系統只能分配很多虛擬內存才能使用,可以訪問整個HD。

或者更簡單的選擇只是增加交換/分頁內存,我認爲這會很愚蠢,但會對你的情況有所幫助。

快速此前谷歌好像這個功能可以幫助你,如果你在Windows上運行: http://msdn.microsoft.com/en-us/library/aa366537(VS.85).aspx

1

從您所告訴我們,您聽起來像需要10^6 x 30個處理器(即模擬次數乘以交易次數),每個處理器都有幾K K RAM。但是,也許你沒有那麼多的處理器 - 你有30個每個都有足夠的內存來進行一次交易的模擬嗎?

嚴重:將您的程序並行化,然後購買帶有32GB RAM(或16核w 64GB或...)的8覈計算機。你遲早不得不這樣做,現在就做吧。

3
  1. 你提到的「發動機」未連接到數據庫,但你有沒有考慮過使用一個數據庫來存儲元素的列表?可能是一個嵌入式數據庫,如SQLite?

  2. 如果您使用int甚至short,而不是stringMap的關鍵領域,可能會節省一些內存。

  3. 如果您需要,保證訂單的集合對象,再考慮QueueStack,而不是你List,你正在使用。

  4. 可能考慮按照Dommer和Alan已經建議的順序進行交易。

我希望這有些幫助!


編輯:

你只左右具有30個按鍵的評論是一個很好的點。

  1. 在這種情況下,因爲你必須在同一時間來計算所有的交易,那麼你認爲你的序列化List s到磁盤(即XML)?

  2. 甚至只是寫一個文本文件到磁盤的每個List,計算這些交易在此之後,加載一個文件/ List以時間來驗證的條件List

當然,缺點是文件IO速度很慢,但是,這會減少服務器的內存需求。

+0

該地圖將只包含30個密鑰(每筆交易一個)。所以我不會使用其他類型的類來保存任何內容...... – romaintaz 2010-10-14 15:47:26

+0

您建議使用數據庫。所以我創建了另一個關於這個特定想法的主題:http://stackoverflow.com/questions/3936044/how-efficient-will-be-to-use-a-in-memory-database-to-store-millions-of-暫時的 – romaintaz 2010-10-14 17:55:20

+0

你的第二個想法與我在第三次編輯中提出的完全相同。也許我會嘗試這個解決方案,但是每10萬次寫入一個文件,而不是爲了減少磁盤I/O的數量。 – romaintaz 2010-10-14 17:57:38

0

你說你需要訪問所有的值,但是你不可能一次操作所有的值?你可以序列化數據,以便可以將它存儲在單個文件中。每個記錄都由一些分隔符,鍵值或簡單字節計數分開。保持一個字節計數器的方式。讓它成爲一個由左側文件和右側文件組成的「循環文件」,其操作方式與反向堆棧相同。當數據從左側文件彈出(讀取)時,它將被處理並推送(寫入)到正確的文件中。如果您的下一個操作需要先前處理的值,則會反轉文件傳輸的方向。把你的算法看作是駐留在硬盤驅動器的讀/寫頭上。您可以像訪問列表一樣使用不同的方法,速度大大降低。速度將會很快,但如果您可以優化序列化順序,以便最有可能訪問的數據按使用順序位於文件的頂部,並且可能會將左右文件放在不同的物理驅動器上,並將頁面文件置於由於連續讀取和同時讀取和寫入,您將受益於更高硬盤性能的第三個驅動器。當然它比聽起來有點難。每次改變方向都需要最終確定兩個文件。邏輯上類似於, if(當前數據流如果從左到右){將EOF發送到right_file; left_file = left_file - right_file;}實際上,您希望將所有數據保留在物理上駐留在驅動器上的位置,並且僅處理主文件表中文件的開始和結束地址。字面上像一對硬盤堆棧一樣操作。與簡單地添加更多內存相比,這將是一個慢得多,更復雜的過程,但是比單獨的文件更有效率,以及每個記錄1個文件的開銷*數百萬條記錄。或者將所有數據放入數據庫。 FWIW,這個想法剛剛來到我身上。我從來沒有做過,甚至沒有聽說過。但是我想象一個人在我之前必須想到它。如果沒有,請讓我知道。我真的可以在我的簡歷上使用這個功勞。

0

一種解決方案是將雙打格式化爲字符串,然後將它們添加到按設計排序的(快速)鍵值存儲中。

然後,你只需要從商店順序閱讀。

這是一個'自然'插入條目的商店。

他們吹牛說他們是在每秒100萬個條目(搜索幾乎快一倍)的速度做:

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

只有3調用的API,它應該是容易測試。

第四個電話將提供基於範圍的搜索。