7

整数を列挙し、オンになっている各ビットの指数を返す最も速い方法は何ですか? << を使用した例と、Math.Pow を使用した別の例を見てきました。本当に速いものが他にあるかどうか疑問に思います。

ありがとう。

4

8 に答える 8

30

最速の方法は？ほとんどの場合、ルックアップ テーブルが最速の方法です。必要な数値の配列を含む、int ごとに 1 つずつ、40 億のエントリを持つ int[][] 配列を作成します。もちろん、テーブルの初期化には時間がかかりますが、ルックアップは非常に高速です。

「最速」が何を意味するのか、誰もが実際に質問に答えるのに十分な精度で述べていないことに注意してください。それは、起動時間を含む最速の償却時間、または起動コストを無視できると仮定した場合の限界ルックアップ時間を意味しますか? 私のソリューション スケッチは後者を想定しています。

明らかに、20 億バイトのアドレス空間を持つ 32 ビット マシンには、300 億バイトの配列を格納するのに十分なアドレス空間がありません。64 ビット マシンを用意してください。高速にしたい場合は、少なくともそれだけの量の物理メモリをインストールする必要があります。そうしないと、ページングによってあなたが殺されます。

ルックアップごとに節約できる数ナノ秒が、余分なハードウェアをすべて購入する価値があることを願っています。それとも、実際には最速の方法を望んでいないのでしょうか?

:-)

于 2009-05-08T06:09:08.810 に答える
11

ビットシフトが最速だと思います。テストされていませんが、次は高速である必要があると思います (少なくとも IEnumerables と同じくらい高速です)。

IEnumerable<int> GetExponents(Int32 value)
{
    for(int i=0; i<32; i++)
    {
        if(value & 1)
            yield return i;
        value >>= 1;
    }
}

より速くしたい場合は、List<int>代わりに a を返すことを検討してください。

于 2009-05-08T03:34:10.570 に答える
6

はIEnumerable実行されません。このトピックのいくつかの例の最適化:

最初のもの (最速 - 10M 実行で 2.35 秒、範囲 1..10M):

static uint[] MulDeBruijnBitPos = new uint[32] 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};

static uint[] GetExponents(uint value)
{
    uint[] data = new uint[32];
    int enabledBitCounter = 0;

    while (value != 0)
    {
        uint m = (value & (0 - value));
        value ^= m;
        data[enabledBitCounter++] = MulDeBruijnBitPos[(m * (uint)0x077CB531U) >> 27];
    }

    Array.Resize<uint>(ref data, enabledBitCounter);
    return data;
}

別のバージョン (2 番目に速い - 10M 実行で 3 秒、範囲 1..10M):

static uint[] GetExponents(uint value)
{
    uint[] data = new uint[32];
    int enabledBitCounter = 0;

    for (uint i = 0; value > 0; ++i)
    {
        if ((value & 1) == 1)
            data[enabledBitCounter++] = i;
        value >>= 1;
    }

    Array.Resize<uint>(ref data, enabledBitCounter);
    return data;
}
于 2009-05-09T07:52:56.530 に答える
5

1バイト相当のビットのルックアップ配列は、安全なC＃コードで実行できる最速に近いはずです。4バイトのそれぞれを整数からシフトし（必要に応じてuintにキャストします）、配列にインデックスを付けます。

ルックアップ配列の要素は、指数の配列である場合もあれば、ビットで何をしているのかによっては、機能するデリゲートである場合もあります。

于 2009-05-08T03:48:31.923 に答える
3

楽しみのために、LINQ を使用したワンライナーを次に示します。

yieldそれは確かに最速の方法ではありませんが、使用およびイテレータブロックを使用する他の回答に大きく遅れをとっているわけではありません。

int test = 42;

// returns 1, 3, 5
//   2^1 + 2^3 + 2^5
// =   2 +   8 +  32
// = 42
var exponents = Enumerable.Range(0, 32).Where(x => ((test >> x) & 1) == 1);

より迅速な解決策として、イテレータ ブロックを使用するのではなく、単純なコレクションを返すことをお勧めします。このようなもの：

int test = 2458217;

// returns 0, 3, 5, 6, 9, 15, 16, 18, 21
//   2^0 + 2^3 + 2^5 + 2^6 + 2^9 +  2^15 +  2^16 +   2^18 +    2^21
// =   1 +   8 +  32 +  64 + 512 + 32768 + 65536 + 262144 + 2097152
// = 2458217
var exponents = GetExponents(test);

// ...

public static List<int> GetExponents(int source)
{
    List<int> result = new List<int>(32);

    for (int i = 0; i < 32; i++)
    {
        if (((source >> i) & 1) == 1)
        {
            result.Add(i);
        }
    }

    return result;
}
于 2009-05-08T10:21:52.697 に答える
2

入力の分布が与えられた場合の最速は? 通常、ビットが 1 つだけ設定されている場合は、設定されたビットを探してループするよりも高速になる可能性があります。

Bit Twiddling Hacksから取得した最下位ビットの位置を見つけるための受け入れられた回答から取得すると、このソリューションはループし、連続する各最下位ビットの位置を見つけてクリアし、返します。

   static int[] MulDeBruijnBitPos = new int[32] 
    {
      0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
      31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };

    static IEnumerable<int> GetExponents(UInt32 v)
    {
        UInt32 m;

        while( v != 0 ) {
          m = (v & (UInt32) (-v));
          yield return MulDeBruijnBitPos[((UInt32) (m * 0x077CB531U)) >> 27];
          v ^= m;
        }
    }

ビットが設定されている回数だけループします。

于 2009-05-08T04:14:51.720 に答える
1

ビットシフト（<<）が最速だと思います。

于 2009-05-08T03:29:58.520 に答える
0

少しの C++ で窒息しない場合:

 void func(int i, int& n, int a[]){
  n = 0;
  if (i < 0) a[n++] = 31;
  i <<= 1;
  if (i < 0) a[n++] = 30;
  i <<= 1;
  if (i < 0) a[n++] = 29;
  i <<= 1;

  ...

  if (i < 0) a[n++] = 0;
}
于 2009-05-10T21:48:27.030 に答える