algorithm - アルゴリズムの最適化：計算またはルックアップテーブルによる対数

Question

すべてのステップで次のような2つのアルゴリズムを計算する必要があるオーディオアルゴリズムを最適化しようとしています。これで、多項式時間で実行される対数のアルゴリズムがないことを読みました。私の質問は、大量のメモリアクセスの欠点はありますが、すべての対数をルックアップテーブルで実行することが理にかなっている場合、それらは常に同じであるためです。

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

私はC++でプログラミングしています。

どうもありがとう！

score 6 · Accepted Answer

本当に必要なのは

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

次に、12個の値のみのテーブルを使用して機能する非常に単純なO（1）計算があります。

frexp（）を使用して、値を指数と仮数に分割します。（これはほんの少しの操作なので、数サイクルかかります。）
2.0の12番目の根（2で割った値）の累乗の事前計算されたリストで仮数を調べます。これは、最大4つの比較で実行できます。
結果は、12 *（指数-1）+最小ルートのインデックス>=仮数です。

追加するために編集：

2の12乗根の累乗が適度に均等に分散されるため、実際にはさらに優れた解決策があります。[0.5、1.0）（frexpによって返される仮数の範囲）を17の等間隔のサブ範囲に分割すると、各サブ範囲は2つの可能な戻り値のいずれかに分類されます。したがって、各サブ範囲をルートのベクトルへのインデックスに関連付ける場合は、ターゲット（その範囲内）を単一のルートと比較するだけで済みます。

私が首尾一貫した英語を書くには遅すぎるので、あなたはコードに落ち着く必要があります：

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 };

これを試してみたところ、OPのループを使用して、合計計算時間が約0.5秒（log2fの場合）から約0.15秒に短縮されました。参照テーブルの合計サイズは164バイトです。

score 2 · Accepted Answer

fkの代わりに簡潔さと明快さのためにzを書くと、内部ループはを計算しceil(12 * log2f((f - 0.5) / z))ます。今12 * log2f((f - 0.5) / z)= 12*log2f(f - 0.5) - 12*log2f(z)。事前に、999エントリの配列を計算して、10988001の代わりに、11998の対数計算のみですべての値を計算できるようにします。

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]);
  }
}

score 1 · Accepted Answer

私が見つけた：

11Kx1K = 11Mの組み合わせがありますが(f, fk)、
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が2バイトであるため、このテーブルをロードするために必要なのは11Kx1Kx2B=22MBのメモリのみです。それは何もありません。

score 0 · Accepted Answer

ループの順序を逆にすると、kの繰り返し値の数がはるかに多くなります。このセットでは、kが「1つの実行」を持つ12977のケースのみがあります。最長ランは618です。

これは、逆のアプローチがlog2f呼び出しの数を最小化することを示唆します-インデックスnを計算する必要があります。ここでk（z、f + n）！= k（z、f）（そしてn個のインスタンスをループします...）

とにかく、最終製品では、巨大なLUTの利点を疑っています。11000 + 1000サイズのテーブルを使用するアプローチでさえ、私には最適ではないようです。代わりに、11000 + 1000の整数だけで、8〜16個で構成されるlog2の線形または最大2次区分的多項式近似が存在すると推測します。

このようなアプローチが見つかった場合、多項式係数はNEONまたはXXMレジスタに適合し、メモリアクセスなしで並列実装が可能になります。

algorithm - アルゴリズムの最適化：計算またはルックアップテーブルによる対数

4 に答える 4

Related

Reference