3

提供された数値がパンデジタルかどうかを確認するための非常に高速なアルゴリズムが必要なプロジェクトに取り組んでいます。ロジックは正しいように見えますが、以下で説明するメソッドのパフォーマンスには特に満足していません。

それぞれ約 520ms、600ms、1600ms で最大 100 万個の 9 桁の数字をチェックできます。私は低遅延アプリケーションに取り組んでおり、本番環境では、確認する必要がある 7 ～ 9 桁の数字のデータセットが約 90 億または 95 億あります。

現在、次のロジックを使用する候補者が 3 人 (実際には 2 人) います。

方法 1:入力を取得し、Nその構成数字のバイト配列に分割し、関数を使用して並べ替え、要素とカウンターの一貫性をチェックArray.Sortするループを使用して配列を反復処理します。for

 byte[] Digits = SplitDigits(N);
 int len = NumberLength(N);
 Array.Sort(Digits);
 for (int i = 0; i <= len - 1; i++)
 {
     if (i + 1 != Digits[i])
          return false;
 }

方法 2:この方法は少し疑わしいロジックに基づいていますが、入力Nを構成数字のバイト配列に分割し、次のテストを行います。

 if (N * (N + 1) * 0.5 == DigitSum(N) && Factorial(len) == DigitProduct(N))
      return true;

方法 3:私はこの方法が嫌いなので、本当の候補ではありませんが、int を文字列にキャストしてからString.Contains、必要な文字列が pandigital かどうかを判断するために使用します。

2 番目と 3 番目の方法の実行時間はかなり安定していますが、最初の方法は頻繁に跳ね返ります。

したがって、理想的には、100 万 9 桁のマークの実行時間を 10 ミリ秒未満に短縮したいと考えています。何かご意見は？

これを Pentium 6100 ラップトップで 2GHz で実行しています。

PS - 2 番目の方法の数学的論理は適切ですか?

4

2 に答える 2

1

方法 1

362880 個の 9 桁のパンデジタル数のソート済みリストを事前に計算します。これには数ミリ秒しかかかりません。次に、リクエストごとに、まず数値が 9 で割り切れるかどうかを確認します。そうである場合は、バイナリ検索を使用して、事前に計算されたリストにあるかどうかを確認します。

方法 2

再度、数値が 9 で割り切れるかどうかを確認します。次に、ビット ベクトルを使用して数字の存在を追跡します。また、剰余乗算を使用して、除算を乗算に置き換えます。

static bool IsPandigital(int n)
{
    if (n != 9 * (int)((0x1c71c71dL * n) >> 32))
        return false;

    int flags = 0;
    while (n > 0) {
        int q = (int)((0x1999999aL * n) >> 32);
        flags |= 1 << (n - q * 10);
        n = q;
    }
    return flags == 0x3fe;
}

方法 1 は 15ms/1M で入ります。方法 2 は、私のマシンでは5.5ms/1Mです。これは、i7 950 で x64 にコンパイルされた C# です。

于 2013-03-03T20:43:58.467 に答える
0

考えただけ:(ウィキペディアからのパンデジタルの定義後)

int n = 1234567890;
int Flags = 0;
int Base = 10;
while(n != 0)
{
    Flags |= 1<<(n % Base); n /= Base;
}
bool bPanDigital = Flags == ((1 << Base) - 1);
于 2013-03-03T18:45:16.877 に答える