算法優化：通過計算或查找表對數

我想優化一個音頻算法，它必須在每一步中計算兩個算法，如下所示。現在我已經讀過，沒有針對多項式運算的對數算法。我的問題是，如果通過查找表進行所有對數是有意義的，因爲它們總是相同的，儘管大量內存訪問的缺點是？算法優化：通過計算或查找表對數

for(int f=1;f<11000;f++){ 
    for(int fk=1;fk<1000;fk++){ 
     int k = ceil(12 * log2f((f - 0.5)/fk)); 
    } 
}

我用C++編程。

非常感謝！

來源

2012-10-25 Oliver

你在用k做什麼？您發佈的代碼沒有副作用或輸出。 – BCoates

注意在你開始做複雜的東西之前：log（（f-0.5）/ fk）= log（f-0.5）-log（fk），這樣你就可以分別計算這些問題，從而將問題減少到1000 + 11000日誌計算。這可以將日誌計算的數量減少約1000倍。 – Bitwise

@同時，我剛纔發佈了一個答案。（比您的評論輕鬆13秒。） –

如果你真正需要的是

ceil(12 * log2(/* something */))

再有是一個非常簡單的O（1）計算，它將使用一個只有12個值的表格。

使用frexp（）將值分成指數和尾數。（這只是位操作，所以它只需要幾個週期。）
查看尾數在預先計算的2.0根據第12根（除以2）的權力列表中，你可以用最多四次比較。
結果是12 *（指數-1）+最小根的指數> =尾數。

編輯補充：

有實際上是一個更好的解決方案，因爲兩個十二根的權力得到合理均勻分佈。如果將[0.5,1.0）（由frexp返回的尾數範圍）劃分爲17個均勻間隔的子範圍，則每個子範圍將落入兩個可能的返回值之一。因此，如果將每個子範圍與索引關聯到根矢量中，則只需將目標（在該範圍內）與單個根進行比較。

這是爲時已晚，我寫連貫的英語，所以你必須解決下面的代碼：

int Ceil12TimesLog2(double x) { 
    int exp; 
    double mantissa = std::frexp(x, &exp) * 2; 
    int idx = indexes[int((mantissa - 1.0) * 17)]; 
    return 12 * (exp - 1) + (mantissa <= roots[idx] ? idx : idx + 1); 
} 

// Here are the reference tables. 

double roots[12] = { 
    0x1.0000000000000p+0, 
    0x1.0f38f92d97963p+0, 
    0x1.1f59ac3c7d6c0p+0, 
    0x1.306fe0a31b715p+0, 
    0x1.428a2f98d728bp+0, 
    0x1.55b8108f0ec5ep+0, 
    0x1.6a09e667f3bccp+0, 
    0x1.7f910d768cfb0p+0, 
    0x1.965fea53d6e3dp+0, 
    0x1.ae89f995ad3adp+0, 
    0x1.c823e074ec129p+0, 
    0x1.e3437e7101344p+0 
}; 
int indexes[17] = { 0, 1, 2, 3, 4, 5, 5, 6, 7, 8, 8, 9, 9, 10, 10, 11, 11 };

我想這一點，並從約0.5秒帶來的總計算時間減少（對於log2f ）到約0.15秒，使用OP中的環路。參考表的總大小是164字節。

來源

2012-10-25 23:42:54 rici

哇！真棒！你真的幫我出去了。這將在測試時爲我節省一些時間:-)非常感謝！ – Oliver

我發現：

雖然你具有的(f, fk) 11Kx1K = 11M組合，
k的不同值的數目僅是294（你只需要9個比特來表示它）。

所以你肯定可以構造一個2d數組來存儲映射並將其加載到內存中。它看起來像

LOOKUP[f][fk] = v, f in 1..11000, fk in 1..1000 
-------------------- 
v1,1 v1,2 v1,3 ... v1,1000 
v2,1 v2,2 v2,3 ... v2,1000 
... ... ... ... 
v11000,1 , ...  v11000,1000

由於每個v是兩個字節，你只需要11Kx1Kx2B = 22MB內存來加載此表。沒什麼。

來源

2012-10-25 23:16:57 greeness

爲了簡潔明瞭而不是fk，你的內部循環計算ceil(12 * log2f((f - 0.5)/z))。現在12 * log2f((f - 0.5)/z) = 12*log2f(f - 0.5) - 12*log2f(z)。在此之前，計算一個陣列999項，讓您計算只有11998對數計算的所有值，而不是他們的10988001：

for (int z=1; z<1000; ++z) 
    z12[z] = 12 * log2f(z); 

for (int f=1; f<11000; ++f) { 
    w = 12 * log2f(f - 0.5); 
    for (int z=1; z<1000; ++z) { 
    int k = ceil(w - z12[z]); 
    } 
}

來源

2012-10-25 23:36:15

如果循環順序顛倒了，那麼k的重複值的數量要高得多。然後在這個集合中只有12977個案例，其中k有一個「跑一個」;最長的運行是618.

這將暗示反向方法會使log2f調用的數量最小 - 必須計算索引n，其中k（z，f + n）！= k（z， f）（並循環n個實例...）

無論如何，在最終產品中，我懷疑巨大的LUT的好處。即使使用11000 + 1000大小的桌子的方法對我來說也不是最理想的。相反，我猜測只有11000 + 1000個整數存在線性或最大2度分段多項式近似log2，其由8到16個片段組成。

如果找到了這種方法，那麼多項式係數會適合NEON或XXM寄存器，並允許並行實現而無需內存訪問。

來源

2012-10-26 07:21:39

算法優化：通過計算或查找表對數

回答

相關問題