預計算值大表格

我在我的程序中有一個數學公式，它包含0和1之間的兩個值，並且做了很多工作來找到答案。預計算值大表格

我也希望能夠做到相反，即我想知道什麼樣的輸入值會產生一定的輸出。我無法通過分析來做到這一點，因爲無數人都會從衆多的輸入中產生相同的答案，而且公式太複雜。

我的問題是，我目前在做這樣的事情，這需要相當長的計算

for(double i = 0; i <= 1 ; i += 0.0001) 
     for(double j = 0; j <= 1; j+= 0.0001) 
      answer = formula(i,j); //do the math 
      if(Math.abs(answer - answerWanted) < 0.001) 
       //close match found

看到的公式是靜態的，我肯定可以預先計算這些值。我認爲查找一個值比執行許多計算要快得多。

我從來沒有做過這樣的事情。有誰知道使用什麼數據結構/如何索引/如何存儲結果？目前我唯一的想法是，我可以以某種方式排序答案，以減少搜索空間，或者只是在運行時初始化一個巨大的數組。如果重要，答案只能在0到2000之間。

來源

2011-04-05 Roger

可能的輸出值的範圍是什麼？什麼類型？ – EboMike 2011-04-05 00:58:41

您的輸入是否總是0.0001的倍數？ – usul 2011-04-05 03:11:06

基本上，您有一個10,000乘10,000的double數組值。如果將它保存在內存中，那將佔用大約800Mb的Java堆內存。

這裏有一些策略，可以幫助：

保持數據庫中的數據表。您可能可以實現亞毫秒的訪問時間（取決於數據庫產品，調優，訪問模式等），並且內存緩存可以改進。假設您存儲了{i, j, value}三元組，您需要對{i, j}進行正向查找，對於反函數則需要{value}。
如果公式是連續且相對平滑的，則可以減少存儲的數據點的數量（例如1000到1000），並使用插值爲您提供中間數據點的近似值。
如果公式沒有局部最小值和最大值，可以使用爬山變量來計算反函數。

在所有這一切，你需要考慮的是，反函數不可能是一個1：1的功能。可能有多個值出現在多個點上，並且可能有其他值未定義該函數。

來源

2011-04-05 01:11:53

爲什麼不將值存儲在數據庫中並使用搜索來匹配它。數據庫使用使搜索速度更快的索引。

假設有具有式和值作爲列的表，可以使用的範圍內選擇，例如

select formula, value from pre_computed_values 
    where value >= givenvalue - Epsilon and value <= givenvalue - Epsilon

其中小量是一個非常小的值（其範圍由你很高興與例如0.001英寸你的情況）

來源

2011-04-05 00:55:17 Rasika

你需要在那個where子句中使用「+ Epsilon」嗎？ – 2011-04-05 01:18:28

另一種方法是使用更智能的搜索算法。最好的選擇將取決於你的函數，而是一個良好的開端可能會是內爾德 - 米德（單純形）算法：

http://en.wikipedia.org/wiki/Nelder–Mead_method

這將大大減少計算量。局部最小值對於某些搜索算法可能是一個問題，但是Nelder-Mead可以脫離許多/大部分搜索算法。

如果您發現重複搜索相同的值，則可以添加簡單的緩存機制。

來源

2011-04-05 01:09:13 winwaed

該公式有多複雜？如果它不會交替增加和減少，可以將增量值更改爲大於.0001的值，然後一旦知道兩個值，就可以使用連續較小的增量來限定答案。您需要的答案在

之間

如果您在編譯與相應輸入的可能結果列表時設置，我可以建議一個散列表。訪問時間爲O（1），因此您只需擔心空間要求和創建表格所需的時間。

來源

2011-04-05 01:11:53 Duncan

空間要求是〜10Gb。參見上面的計算。 – 2011-04-05 01:44:01

除非公式足夠流暢，否則可以將所需數據減少到可管理的大小，然後如上所述捕獲答案。10GB聽起來有點大，除非你有空間來殺人。 – Duncan 2011-04-05 02:26:03

嘗試使用哈希表從雙到Set<Pair<Double, Double>>

HashMap<Double, Set<Pair<Double, Double>> Answers;

// fill in answers 
for(double i = 0; i <= 1 ; i += 0.0001) 
    for(double j = 0; j <= 1; j+= 0.0001) { 
     answer = formula(i,j); 
    Set<Double> existing; 
     if (Answers.hasKey(answer)) { 
      existing = Answers.get(answer); 
     } 
     else { 
      existing = new Set<Pair<Double, Double>>; 
     } 
     existing.add(new Pair(i, j)); 
     Answers.set(answer, existing); 
    } 
}

// look up all the possible inputs for an answer

Set<Pair<Double, Double>> inputs = Answers.get(output);

我還沒有考慮逆但就是簡單的......

來源

2011-04-05 01:16:54

這可能不會按原樣工作。考慮到當表示爲矩陣時前向函數需要〜800Mb，表示爲哈希表的反函數可能需要〜10Gb。（如果包含對象標題，每個鍵需要16個字節，每個值需要16個字節，Map.Entry每個需要28個字節，散列陣將有5千萬到1百萬個條目......） – 2011-04-05 01:42:39

I '我想嘗試這個，也許如果我想降低分辨率，它可能是合理的。但是，我似乎無法獲得'現有的=新的集<對<雙，雙>>;'工作。我如何分配內存我不知道 – Roger 2011-04-05 02:37:39

@Stephen C：硬件問題:-) – 2011-04-05 02:44:27

另一種可能性取決於方程的性質 - 如果輸出值與輸入值的圖不包含不連續性或其他這樣的醜陋，則可以預先計算一個更粗糙的數組（避免存儲數組的400多MB）正在看），然後試圖收斂於答案。

預先計算一個比您所看到的粗糙的網格，然後嘗試通過採用半個網格大小的步進間隔並檢查（您將必須計算它們）八個相鄰點來優化您的答案。選擇最好的，把你的網格切成兩半，然後重複，直到你具有所需的精度。這導致每步8個計算（您始終擁有上一步的中心值），從100x100到您的分辨率只需要7步，總計56次調用您的計算函數。

粗網格只需要足夠精細，以至於不能從目標上被困在鞍座的錯誤一側。

即使在一個1000x1000的網格中，網格的最大值也是8兆字節，要計算的最大值是32兆。

來源

2011-04-05 01:21:24

您還可以使用Genetic algorithm來查找給定輸出的函數輸入值。

hth

來源

2011-04-05 17:21:52

只有兩個參數，這將是一個非常糟糕的做事方式。 – winwaed 2011-04-05 21:05:13

不過，這個解決方案比現在的蠻力方式更快...... – 2011-04-06 08:00:25

預計算值大表格

回答

相關問題