質問は
基本的な 2log の他の (および/またはより高速な) 実装はありますか?
アプリケーション
log2(int) および log2(float) 操作は、さまざまなコンテキストで非常に役立ちます。たとえば、圧縮アルゴリズム、3D エンジン、機械学習などです。これらのコンテキストのほとんどすべてで、何十億回も呼び出される低レベルのコードで使用されます... 特に log2(int) 操作は非常に便利です。
私は常に log2 を使用していることに気付いたので、ここで作業している特定のアプリケーションを提供したくありません。同じことは、これが実際にパフォーマンスを低下させるという事実です (さまざまなアプリケーションのパフォーマンス テストで示されているように)。私にとっては、これをできるだけ早く取得することが重要です。
すべての実装をテストするための完全なソース コードが一番下に追加されているので、自分の目で確かめてください。
そしてもちろん... テストを少なくとも 3 回実行し、カウンターが数秒に達するのに十分な大きさであることを確認してください。また、「追加」操作を行って、ループ全体が JIT'ter によって魔法のように削除されないようにします。それでは、実際の作業を始めましょう。
些細な実装
C# での 2log の簡単な実装は次のとおりです。
(int)(Math.Log(x) / Math.Log(2))
この実装は簡単ですが、非常に遅くなります。2 つのログ操作が必要ですが、それ自体がすでに非常に遅いです。もちろん、1.0/Math.Log(2)定数を作成することでこれを最適化できます。
(浮動小数点エラーの結果として) 正しい結果を得るには、この定数を少し変更するか、正しい結果を得るために小さな数値を追加する必要があることに注意してください。私は後者を選択しましたが、それは問題ではありません。最終結果はすべての場合において遅くなります。
テーブル ルックアップ
これに対するより迅速な解決策は、ルックアップ テーブルを使用することです。任意の 2 の累乗のルックアップ テーブルを使用できますが、私は通常、256 または 64K エントリのテーブル サイズを使用します。
まず、ルックアップ テーブルを作成します。
lookup = new int[256];
for (int i = 1; i < 256; ++i)
{
lookup[i] = (int)(Math.Log(i) / Math.Log(2));
}
次に、次のように 2log を実装します。
private static int LogLookup(int i)
{
if (i >= 0x1000000) { return lookup[i >> 24] + 24; }
else if (i >= 0x10000) { return lookup[i >> 16] + 16; }
else if (i >= 0x100) { return lookup[i >> 8] + 8; }
else { return lookup[i]; }
}
ご覧のとおり、テーブル ルックアップははるかに高速な実装ですが、欠点として、計算には使用できませんlog2(float)。
枝の除去
ご存知のように、プロセッサは分岐が苦手なので、分岐を削除することでテーブル ルックアップを改善できると考えました。if の束の代わりに、値を含む 2 番目のテーブルを導入し、テーブル内のエントリを見つけるためにビットをシフトしました。
nobranch = new int[16] { 0, 0, 8, 8, 16, 16, 16, 16, 24, 24, 24, 24, 24, 24, 24, 24 };
private static int LogDoubleLookup(int i)
{
int n = (i | (i >> 4));
n = (n | (n >> 2));
n = (n | (n >> 1));
n = ((n & 0x1000000) >> 21) | ((n & 0x10000) >> 14) | ((n & 0x100) >> 7) | (n & 1);
int br = nobranch[n];
return lookup[i >> br] + br;
}
このテストを実行すると、実際には if-then-else ソリューションよりも遅いことがわかります。
そしてIntel 80386がありました
Intel はこれが重要な操作であることを何年も前に理解していたので、Bit-Scan-Forward (BSF) をプロセッサに実装しました。他のプロセッサにも同様の命令があります。これは、私が知っている 2log を実行する最速の方法ですが、残念ながら、C# からこれらの優れた関数を使用する方法を知っています... もう実行されない実装を持つという考えは好きではありません新しいタブレットや携帯電話が市場に出たとき - この機能を直接使用できるクロスプラットフォーム ソリューションを知りません。
その他の実装
l4V が指摘したように (ありがとう!) 他にもいくつかの実装があります。具体的には:
- 些細なループ。これは簡単なので省略しましたが、これは実際には高速ではありません。に実装されてい
TestTrivialます。 - 64ビットIEEE/int共用体が使用可能。で実装
TestFloat - DeBruijn ルックアップ テーブル。で実装
TestDeBruijn - 二分探索。で実装
TestBinary
名前が気に入っていることは別として、DeBruijn ルックアップ テーブルは通常のルックアップ テーブルと同じくらい高速であり、ここで最速のアルゴリズムの 1 つになっています... 私が試した他のすべてのアルゴリズムははるかに低速です。
完全なテスト コード
public class Log2Test
{
public static void TestNaive()
{
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += (int)(Math.Log(i) / Math.Log(2.0));
}
sw.Stop();
Console.WriteLine("Result: {0} - naive implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
public static int LogTrivialLoop(int v)
{
int r = 0;
while ((v >>= 1) > 0) // unroll for more speed...
{
r++;
}
return r;
}
public static void TestTrivialLoop()
{
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogTrivialLoop(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - loop implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
public static int LogFloat(int v)
{
Helper h = new Helper() { U1 = v, U2 = 0x43300000 };
h.D -= 4503599627370496.0;
return (h.U2 >> 20) - 0x3FF;
}
public static void TestFloat()
{
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogFloat(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - IEEE float implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
[StructLayout(LayoutKind.Explicit)]
private struct Helper
{
[FieldOffset(0)]
public int U1;
[FieldOffset(4)]
public int U2;
[FieldOffset(0)]
public double D;
}
public static void TestConstant()
{
double c = 1.0 / Math.Log(2.0);
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += (int)(0.00000000001 + Math.Log(i) * c);
}
sw.Stop();
Console.WriteLine("Result: {0} - naive 2 implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
private static int LogLookup(int i)
{
if (i >= 0x1000000) { return lookup[i >> 24] + 24; }
else if (i >= 0x10000) { return lookup[i >> 16] + 16; }
else if (i >= 0x100) { return lookup[i >> 8] + 8; }
else { return lookup[i]; }
}
public static void TestLookup()
{
lookup = new int[256];
for (int i = 1; i < 256; ++i)
{
lookup[i] = (int)(Math.Log(i) / Math.Log(2));
}
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogLookup(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - table lookup implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
private static int LogDoubleLookup(int i)
{
int n = (i | (i >> 4));
n = (n | (n >> 2));
n = (n | (n >> 1));
n = ((n & 0x1000000) >> 21) | ((n & 0x10000) >> 14) | ((n & 0x100) >> 7) | (n & 1);
int br = nobranch[n];
return lookup[i >> br] + br;
}
public static void TestDoubleLookup()
{
// Lookup table was already constructed earlier
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogDoubleLookup(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - double table lookup implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
private static int LogBinary(int v)
{
/* This is the worst implementation ever... - apparently C# is a slow-branching language
int[] b = { 0x2, 0xC, 0xF0, 0xFF00, 0x7FFF0000 };
int[] S = { 1, 2, 4, 8, 16 };
int r = 0; // result of log2(v) will go here
for (int i = 4; i >= 0; i--) // unroll for speed...
{
if ((v & b[i]) != 0)
{
v >>= S[i];
r |= S[i];
}
}
return r;
*/
int r = (((v > 0xFFFF)) ? 0x10 : 0);
v >>= r;
int shift = ((v > 0xFF) ? 0x8 : 0);
v >>= shift;
r |= shift;
shift = ((v > 0xF) ? 0x4 : 0);
v >>= shift;
r |= shift;
shift = ((v > 0x3) ? 0x2 : 0);
v >>= shift;
r |= shift;
r |= (v >> 1);
return r;
}
public static void TestBinary()
{
// Lookup table was already constructed earlier
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogBinary(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - binary search implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
private static readonly int[] MultiplyDeBruijnBitPosition = new int[32]
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
private static int LogDeBruijn(int v)
{
v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
return MultiplyDeBruijnBitPosition[(uint)(v * 0x07C4ACDDU) >> 27];
}
public static void TestDeBruijn()
{
// Lookup table was already constructed earlier
Stopwatch sw = new Stopwatch();
sw.Start();
int n = 0;
for (int i = 1; i < 100000000; ++i)
{
n += LogDeBruijn(i);
}
sw.Stop();
Console.WriteLine("Result: {0} - de Bruijn implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds);
}
private static int[] lookup;
private static readonly int[] nobranch = new int[16] { 0, 0, 8, 8, 16, 16, 16, 16, 24, 24, 24, 24, 24, 24, 24, 24 };
static void Main(string[] args)
{
TestConstant();
TestNaive();
TestDeBruijn();
TestBinary();
TestFloat();
TestTrivialLoop();
TestLookup();
TestDoubleLookup();
Console.ReadLine();
}
}