c# - バイナリパターン比較のショートカット / C# での最速の実装

Question

次のように、特定のバイトまたは一連のバイトをチェックして、特定のビットシーケンスを確認する必要があります。

0 個以上ので開始できます0s。
0 個以上ので開始できます1s。
0末尾に少なくとも 1 つ含まれている必要があります。

つまり、bytes の値がでない場合、連続した値の後に少なくとも 1 つが最後に続く0値のみに関心があります。1s0

それを行うために次のコードを書きましたが、高度に最適化されていることを確認したかったのです。if ブランチ内の複数のチェックを最適化できると思いますが、その方法はわかりません。お知らせ下さい。

// The parameter [number] will NEVER be negative.
public static bool ConformsToPattern (System.Numerics.BigInteger number)
{
    byte [] bytes = null;
    bool moreOnesPossible = true;

    if (number == 0) // 00000000
    {
        return (true); // All bits are zero.
    }
    else
    {
        bytes = number.ToByteArray();

        if ((bytes [bytes.Length - 1] & 1) == 1)
        {
            return (false);
        }
        else
        {
            for (byte b=0; b < bytes.Length; b++)
            {
                if (moreOnesPossible)
                {
                    if
                    (
                        (bytes [b] == 1) // 00000001
                        || (bytes [b] == 3) // 00000011
                        || (bytes [b] == 7) // 00000111
                        || (bytes [b] == 15) // 00001111
                        || (bytes [b] == 31) // 00011111
                        || (bytes [b] == 63) // 00111111
                        || (bytes [b] == 127) // 01111111
                        || (bytes [b] == 255) // 11111111
                    )
                    {
                        // So far so good. Continue to the next byte with
                        // a possibility of more consecutive 1s.
                    }
                    else if
                    (
                        (bytes [b] == 128) // 10000000
                        || (bytes [b] == 192) // 11000000
                        || (bytes [b] == 224) // 11100000
                        || (bytes [b] == 240) // 11110000
                        || (bytes [b] == 248) // 11111000
                        || (bytes [b] == 252) // 11111100
                        || (bytes [b] == 254) // 11111110
                    )
                    {
                        moreOnesPossible = false;
                    }
                    else
                    {
                        return (false);
                    }
                }
                else
                {
                    if (bytes [b] > 0)
                    {
                        return (false);
                    }
                }
            }
        }
    }

    return (true);
}

重要:関数に送信される引数 [数値] が負になることは決してないため、符号ビットをチェックする必要はありません。

score 1 · Accepted Answer

このようなものはどうですか？1 が見つかった場合、その後は 0 が見つかるまで 1 のみになります。その後、0のみ。これは、不要な条件を実行しないため、トリックを少し速く実行するように見えます。

// The parameter [number] will NEVER be negative.
public static bool ConformsToPattern (System.Numerics.BigInteger number)
{
    byte [] bytes = null;
    bool moreOnesPossible = true;
    bool foundFirstOne = false;

    if (number == 0) // 00000000
    {
        return (true); // All bits are zero.
    }
    else
    {
        bytes = number.ToByteArray();

        if ((bytes [bytes.Length - 1] & 1) == 1)
        {
            return (false);
        }
        else
        {
            for (byte b=0; b < bytes.Length; b++)
            {
                if (moreOnesPossible)
                {
                    if(!foundFirstOne)
                    {
                        if
                        (
                            (bytes [b] == 1) // 00000001
                            || (bytes [b] == 3) // 00000011
                            || (bytes [b] == 7) // 00000111
                            || (bytes [b] == 15) // 00001111
                            || (bytes [b] == 31) // 00011111
                            || (bytes [b] == 63) // 00111111
                            || (bytes [b] == 127) // 01111111
                            || (bytes [b] == 255) // 11111111
                        )
                        {
                            foundFirstOne = true;
                            // So far so good. Continue to the next byte with
                            // a possibility of more consecutive 1s.
                        }
                        else if
                        (
                            (bytes [b] == 128) // 10000000
                            || (bytes [b] == 192) // 11000000
                            || (bytes [b] == 224) // 11100000
                            || (bytes [b] == 240) // 11110000
                            || (bytes [b] == 248) // 11111000
                            || (bytes [b] == 252) // 11111100
                            || (bytes [b] == 254) // 11111110
                        )
                        {
                            moreOnesPossible = false;
                        }
                        else
                        {
                            return (false);
                        }
                    }
                    else
                    {
                        if(bytes [b] != 255) // 11111111
                        {
                            if
                            (
                                (bytes [b] == 128) // 10000000
                                || (bytes [b] == 192) // 11000000
                                    || (bytes [b] == 224) // 11100000
                                || (bytes [b] == 240) // 11110000
                                || (bytes [b] == 248) // 11111000
                                || (bytes [b] == 252) // 11111100
                                || (bytes [b] == 254) // 11111110
                            )
                            {
                                moreOnesPossible = false;
                            }
                        }                            
                    }
                }
                else
                {
                    if (bytes [b] > 0)
                    {
                        return (false);
                    }
                }
            }
        }
    }

    return (true);
}

score 1 · Accepted Answer

これが私が自分で書いた方法です。あまりエレガントではありませんが、かなり高速です。

/// <summary>
/// Checks to see if this cell lies on a major diagonal of a power of 2.
/// ^[0]*[1]*[0]+$ denotes the regular expression of the binary pattern we are looking for.
/// </summary>
public bool IsDiagonalMajorToPowerOfTwo ()
{
    byte [] bytes = null;
    bool moreOnesPossible = true;
    System.Numerics.BigInteger number = 0;

    number = System.Numerics.BigInteger.Abs(this.X - this.Y);

    if ((number == 0) || (number == 1)) // 00000000
    {
        return (true); // All bits are zero.
    }
    else
    {
        // The last bit should always be 0.
        if (number.IsEven)
        {
            bytes = number.ToByteArray();

            for (byte b=0; b < bytes.Length; b++)
            {
                if (moreOnesPossible)
                {
                    switch (bytes [b])
                    {
                        case 001: // 00000001
                        case 003: // 00000011
                        case 007: // 00000111
                        case 015: // 00001111
                        case 031: // 00011111
                        case 063: // 00111111
                        case 127: // 01111111
                        case 255: // 11111111
                        {
                            // So far so good.
                            // Carry on testing subsequent bytes.

                            break;
                        }
                        case 128: // 10000000
                        case 064: // 01000000
                        case 032: // 00100000
                        case 016: // 00010000
                        case 008: // 00001000
                        case 004: // 00000100
                        case 002: // 00000010

                        case 192: // 11000000
                        case 096: // 01100000
                        case 048: // 00110000
                        case 024: // 00011000
                        case 012: // 00001100
                        case 006: // 00000110

                        case 224: // 11100000
                        case 112: // 01110000
                        case 056: // 00111000
                        case 028: // 00011100
                        case 014: // 00001110

                        case 240: // 11110000
                        case 120: // 01111000
                        case 060: // 00111100
                        case 030: // 00011110

                        case 248: // 11111000
                        case 124: // 01111100
                        case 062: // 00111110

                        case 252: // 11111100
                        case 126: // 01111110

                        case 254: // 11111110
                        {
                            moreOnesPossible = false;

                            break;
                        }
                        default:
                        {
                            return (false);
                        }
                    }
                }
                else
                {
                    if (bytes [b] > 0)
                    {
                        return (false);
                    }
                }
            }
        }
        else
        {
            return (false);
        }
    }

    return (true);
}

score 0 · Accepted Answer

これがあなたがすでに持っているものよりも速いか遅いかはわかりませんが、試してみる必要があります（ロジックを台無しにしないことを願っています）...

public bool ConformsToPattern(System.Numerics.BigInteger number) {
    bool moreOnesPossible = true;
    if (number == 0) {
        return true;
    }
    else {
        byte[] bytes = number.ToByteArray();
        if ((bytes[bytes.Length - 1] & 1) == 1) {
            return false;
        }
        else {
            for (byte b = 0; b < bytes.Length; b++) {
                if (moreOnesPossible) {
                    switch (bytes[b]) {
                        case 1:
                        case 3:
                        case 7:
                        case 15:
                        case 31:
                        case 63:
                        case 127:
                        case 255:
                            continue;
                        default:
                            switch (bytes[b]) {
                                case 128:
                                case 192:
                                case 224:
                                case 240:
                                case 248:
                                case 252:
                                case 254:
                                    moreOnesPossible = false;
                                    continue;
                                default:
                                    return false;
                            }
                    }
                }
                else {
                    if (bytes[b] > 0) { return (false); }
                }
            }
        }
    }
    return true;
}

score 0 · Accepted Answer

私は正規表現の大ファンなので、単にバイトを文字列に変換し、正規表現に対してテストすることを考えました。ただし、パターンを慎重に定義することが重要です。あなたの質問を読んで、私はこれを思いつきました：

^(?:1*)(?:0+)$

チェックアウトしてください：

    public static bool ConformsToPattern(System.Numerics.BigInteger number)
    {
        byte[] ByteArray = number.ToByteArray();

        Regex BinaryRegex = new Regex("^(?:1*)(?:0+)$", RegexOptions.Compiled);

        return ByteArray.Where<byte>(x => !BinaryRegex.IsMatch(Convert.ToString(x, 2))).Count() > 0;
    }

score 0 · Accepted Answer

私の理解が正しければ、連続する 1 の連続が 1 つだけで、その後に連続する 0 が続く必要があります。

したがって、ゼロで終わる必要がある場合は、偶数でなければなりません。中間のすべてのバイトはすべて 1 でなければならず、最初と最後のバイトは唯一の特殊なケースです。

         if (number.IsZero)
            return true;

         if (!number.IsEven)
            return false;


         var bytes = number.ToByteArray();

         for (int i = 0; i < bytes.Length; i++)
         {
            if (i == 0)  //first byte case
            {
               if (!(
                     (bytes[i] == 1) // 00000001 
                     || (bytes[i] == 3) // 00000011 
                     || (bytes[i] == 7) // 00000111 
                     || (bytes[i] == 15) // 00001111 
                     || (bytes[i] == 31) // 00011111 
                     || (bytes[i] == 63) // 00111111 
                     || (bytes[i] == 127) // 01111111 
                     || (bytes[i] == 255) // 11111111 
                    ))
               {
                  return false; 
               }
            }
            else if (i == bytes.Length) //last byte case
            {
               if (!(
                  (bytes[i] == 128) // 10000000 
                        || (bytes[i] == 192) // 11000000 
                        || (bytes[i] == 224) // 11100000 
                        || (bytes[i] == 240) // 11110000 
                        || (bytes[i] == 248) // 11111000 
                        || (bytes[i] == 252) // 11111100 
                        || (bytes[i] == 254) // 11111110 
                    ))
               {
                  return false;
               }
            }
            else //all bytes in the middle
            {
               if (bytes[i] != 255)
                  return false;
            }

         }

c# - バイナリ パターン比較のショートカット / C# での最速の実装

6 に答える 6

Related

Reference

c# - バイナリパターン比較のショートカット / C# での最速の実装