3

数値に数字の「0」が含まれているかどうかを確認する最も速い方法は何ですか?

$20$ 秒以内に $10^9$ 近くの数値をチェックする必要があるため、高速な方法を開発する必要があります。

文字列に変換した後にゼロを検索することはできますか?

4

5 に答える 5

14

$2$ の累乗以外の数で割ると、数に関係なく同じ数の操作が必要になります。したがって、$x$ を $10$ で繰り返し割り、それぞれの剰余を $0$ に対してテストする代わりに、$x$ を $10^6$ (たとえば) で繰り返し割り、$[0, 10^6) のルックアップ テーブルに対して各剰余をテストすることを検討してください。 $. ルックアップ テーブルは、剰余に内部ゼロが含まれている場合は「はい」、ゼロが含まれていない場合は「いいえ」、剰余に最初のゼロしかない場合は「おそらく」と言う必要があります (この場合、$x$ が現在ゼロでないかどうかを確認して、それに応じて「はい」または「いいえ」）。

于 2012-04-05T17:00:35.633 に答える
1

アセンブリを記述したり、コンパイラに整数除算を強制したりできる場合は、剰余が $0$ になるか、被除数が $0$ になるまで、整数除算を $10$ で繰り返し実行します。余りだったら「$0$」の桁があります。配当だった場合、「$0$」の桁はありません。

于 2012-04-05T15:33:50.137 に答える
1

バイナリ ゼロ: (~x) ビットがゼロの場合、非ゼロになります。私の推測では、あなたは 2 進数には関心がありません。

データが文字列で始まる場合は、そのままにしておきます。そうでない場合は、文字列に変換してからチェックしないでください。文字列への変換は、ゼロの数字を検出するために必要以上の作業を行います。これは言語固有の可能性があります。Cまたはアセンブリでは、変換は独自の検出アルゴリズムよりも遅くなります。

たとえば、基数 10 の数値を整数として格納した場合 (c のように)、1000 エントリのルックアップ テーブルを作成できます。Lookup[100] = 1、Lookup[123] = 0 など。その後、入力数値を 10 ではなく 1000 で除算する必要があります。剰余はルックアップ インデックスです。これは、10 で割るよりも 3 倍速くなる可能性があります。小さなルックアップ テーブルはキャッシュに収まります。テーブルが大きすぎると、RAM が非常に遅いためにパフォーマンスが低下します。c では、符号なし int の方が符号付き int よりも速く除算される可能性があります。

最後に、これには複数のスレッドを検討してください。

于 2012-04-05T22:43:05.623 に答える
0

これらのチェックを 20 秒以内に 109 近くの数字に対して実行する必要があるため、高速な方法を開発する必要があります。

あ、プログラミングの質問です。

文字列に変換した後にゼロを検索することはできますか?

入力に渡すすべてが、先頭または末尾のゼロがない独自の行の数値である場合、 /0/ がそのトリックを実行します。しかし、はい、文字列が最も高速です。混合物にゼロまたは非数値を含むより複雑な表現を行うには、整数に対して次の正規表現を使用します。

/^[1-9]+0[0-9]*$|^0$/

これには、先​​頭にゼロがない数値、または数値ゼロである数値が必要です。また、整数を想定しています。

$ cat numbers
    375
    391
    940
    493
    566
    804
    800
    453
    726
    527
    428
    77
    984
    510
    795
    077
    0

    $ egrep '^[1-9]+0[0-9]*$|^0$' numbers
940
804
800
510
0

固定幅の場合、10 進数は少し難しくなる可能性があります。そうでない場合は、小数が「.nnn」ではなく「0.nnn」で始まっていない限り、2 つの括弧のそれぞれにピリオドを追加するだけで十分です。番号を教えてください。適切な修正を行います。

于 2012-04-05T20:40:52.987 に答える
0

以下は、数値の桁ごとに 1 つの除算を行う Mathematica コードです。

n = 34560116; d = IntegerLength[n]; m = 0; x = 1;  
While[d >= x, If[m == (k = Mod[n, 10^(x++)]), Break[], m = k]];
If[d >= x, Print["First zero found at: ", 10^(x - 2)]];

First zero found at: 1000
于 2012-04-10T23:15:46.697 に答える