優化呼叫昂貴功能的次數

Question

我有一個mainFun，它需要四個參數x,a,b和c，所有的矢量值和可能長度不等。此函數調用expensiveFun，這在計算上很昂貴，所以我想將呼叫數減少到expensiveFun。此功能需要被調用爲每個值在x[i]，a[i]，b[i]，c[i]如果a，b，或c是較短的長度的話，就需要進行「包裝」（它們的索引是在模a[i % a.size()]）。對於x（即所有整數0，...，max（x））的每個可能的不同值，預先計算expensiveFun將是最好的，然後通過out[i] = precomputedValues[x[i]]僅填充輸出out。如果a,b和c具有相同的長度（下面的例子），這可以很容易地實現，但如果它們不是很長，它會變得很難看。如果參數向量的長度不同，有什麼辦法可以提高效率嗎？

下面我提供了一個可重複的例子。這是一個簡化的代碼，只是爲了舉例。

std::vector<int> expensiveFun(int x, int a, int b, int c) { 
    std::vector<int> out(x+1); 
    out[0] = a+b*c; 
    for (int i = 1; i <= x; i++) 
    out[i] = out[i-1] * i + a * (b+c); 
    return out; 
} 

std::vector<int> mainFun(
    std::vector<int> x, 
    std::vector<int> a, 
    std::vector<int> b, 
    std::vector<int> c 
) { 

    int n = x.size(); 
    int a_size = a.size(); 
    int b_size = b.size(); 
    int c_size = c.size(); 

    std::vector<int> out(n); 

    // easy 
    if (a_size == b_size && b_size == a_size) { 

    int max_x = 0; 
    for (int j = 0; j < n; j++) 
     if (x[j] > max_x) 
     max_x = x[j]; 

    for (int i = 0; i < a_size; i++) { 
     int max_x = 0; 
     for (int j = 0; j < n; j += a_size) { 
     if (x[j] > max_x) 
      max_x = x[j]; 
     } 
     std::vector<int> precomputedValues = expensiveFun(max_x, a[i], b[i], c[i]); 
     for (int j = i; j < n; j += a_size) { 
     out[j] = precomputedValues[x[j]]; 
     } 
    } 

    // otherwise give up 
    } else { 

    for (int j = 0; j < n; j++) { 
     out[j] = expensiveFun(x[j], a[j % a_size], c[j % c_size], c[j % c_size]).back(); 
    } 

    } 

    return out; 
} 

例輸入：

x = {0, 1, 5, 3, 2, 1, 0, 4, 4, 2, 3, 4, 1} 
a = {1, 2, 3} 
b = {1, 2} 
c = {3, 4, 5, 6} 

的參數應該被摺疊，使它們變爲

x = {0, 1, 5, 3, 2, 1, 0, 4, 4, 2, 3, 4, 1} 
a = {1, 2, 3, 1, 2, 3, 1, 2, 3, 1, 2, 3, 1} 
b = {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1} 
c = {3, 4, 5, 6, 3, 4, 5, 6, 3, 4, 5, 6, 3} 

輸出是不是現在重要的，因爲在這裏的主要問題是關於有效處理不同大小的參數向量。

Answer 1

Memoize你的功能。

一旦計算出a，b和c組合的向量，就將其存儲在std::unordered_map中。下次您看到相同的組合時，您將檢索已經計算出的矢量 - 用計算機內存支付計算速度的經典方法。

std::map<std::tuple<int,int,int>,std::vector<int>> memo; 

int expensiveFunMemo(int x, int xMax, int a, int b, int c) { 
    assert(x <= xMax); 
    std::vector<int>& out = memo[std::make_tuple(a, b, c)]; 
    if (!out.size()) { 
    out.push_back(a+b*c); 
    for (int i = 1; i <= xMax; i++) 
     out.push_back(out[i-1] * i + a * (b+c)); 
    } 
    assert(out.size == xMax+1); 
    return out[x]; 
} 

這樣你永遠不會計算expensiveFunMemo爲{a, b, c}任意組合不止一次。

你mainFun變得更簡單，太：

std::vector<int> mainFun(
    const std::vector<int>& x, 
    const std::vector<int>& a, 
    const std::vector<int>& b, 
    const std::vector<int>& c 
) { 
    size_t n = x.size(); 
    size_t a_size = a.size(); 
    size_t b_size = b.size(); 
    size_t c_size = c.size(); 
    std::vector<int> out(n); 
    int xMax = *std::max_element(x.begin(), x.end()); 
    for (size_t j = 0 ; j < n ; j++) { 
    out[j] = expensiveFunMemo(x[j], xMax, a[j % a_size], c[j % c_size], c[j % c_size]); 
    } 
    return out; 
} 

注：該解決方案使用std::map<K,V>代替std::unordered_map<K,V>因爲std::tuple<...>缺少一個通用的散列函數。 This Q&A提供瞭解決此問題的解決方案。