正の整数の桁数を求める最良の方法は何ですか?
私はこの3つの基本的な方法を見つけました：
文字列への変換
String s = new Integer(t).toString();
int len = s.length();
for ループ
for(long long int temp = number; temp >= 1;)
{
temp/=10;
decimalPlaces++;
}
対数計算
digits = floor( log10( number ) ) + 1;
ほとんどの言語で log10(x) = ln(x) / ln(10) を計算できます。
最初はストリングス方式が一番汚いと思っていたのですが、考えれば考えるほど一番手っ取り早い方法だと思います。またはそれは？
常にこの方法があります：
n = 1;
if ( i >= 100000000 ) { n += 8; i /= 100000000; }
if ( i >= 10000 ) { n += 4; i /= 10000; }
if ( i >= 100 ) { n += 2; i /= 100; }
if ( i >= 10 ) { n += 1; }
正しい答えはそれを測定することですが、文字列を変換してエンドマーカーを探すために必要なCPUステップの数を推測できるはずです
次に、プロセッサが 1 秒あたりに実行できる FPU 操作の数と、1 つのログを計算するのがいかに簡単かを考えてください。
編集：月曜日の朝にもう少し時間を無駄にします:-)
String s = new Integer(t).toString();
int len = s.length();
高水準言語の問題の 1 つは、システムが一見単純なステートメントの舞台裏でどれだけの作業を行っているかを推測することです。必須ジョエルリンク
このステートメントには、文字列のメモリの割り当てと、場合によっては文字列の一時的なコピーがいくつか含まれます。整数を解析し、その数字を文字列にコピーする必要があります。数値が大きい場合は、既存のメモリを再割り当てして移動する必要があります。あなたの国が「、」または「。」を使用しているかどうかを判断するために、多くのロケール設定をチェックする必要があるかもしれません。また、多くの Unicode 変換を行う必要があるかもしれません。
次に、長さを見つけるには、文字列全体をスキャンする必要があります。これも、ユニコードと、右から左への言語ですか? などのローカル固有の設定を考慮して行われます。
または:
digits = floor( log10( number ) ) + 1;
これを紙で行うのが難しいからといって、コンピューターで行うのが難しいというわけではありません。実際、ハイ パフォーマンス コンピューティングの良いルールは、人間にとって難しいもの (流体力学、3D レンダリング) はコンピューターにとって簡単であり、人間にとって簡単なもの (顔認識、声の検出) であったようです。うるさい部屋）パソコンはつらい！
一般に、組み込みの数学関数 log/sin/cos などは、50 年間コンピューター設計の重要な部分であったと想定できます。したがって、それらが FPU のハードウェア関数に直接マップされていなくても、代替の実装がかなり効率的であることに賭けることができます。
わかりません。答えは、個々の言語がどのように実装されているかによって異なる場合があります。
だから、それをストレステストしてください！3 つのソリューションをすべて実装します。1 から 1,000,000 (または、ソリューションが実行される数値を表すその他の巨大な数値セット) でそれらを実行し、それぞれにかかる時間を計ります。
あなたの解決策を互いに競い合い、彼らに戦わせてください。知的なグラディエーターのように。3つのアルゴリズムが入る！1 つのアルゴリズムが残されます。
試験条件
結果
数字: [1,10],
番号。実行数: 1,000,000
無作為抽出: 8777509,40442298,477894,329950,513,91751410,313,3159,131309,2
結果: 7,8,6,6,3,8,3,4,6,1
文字列への変換: 724ms
対数計算: 349ms
DIV 10 反復: 229ms
手動調整: 136ms
注: 著者は、10 桁を超える数について結論を出すことを控えています。
脚本
package {
import flash.display.MovieClip;
import flash.utils.getTimer;
/**
* @author Daniel
*/
public class Digits extends MovieClip {
private const NUMBERS : uint = 1000000;
private const DIGITS : uint = 10;
private var numbers : Array;
private var digits : Array;
public function Digits() {
// ************* NUMBERS *************
numbers = [];
for (var i : int = 0; i < NUMBERS; i++) {
var number : Number = Math.floor(Math.pow(10, Math.random()*DIGITS));
numbers.push(number);
}
trace('Max digits: ' + DIGITS + ', count of numbers: ' + NUMBERS);
trace('sample: ' + numbers.slice(0, 10));
// ************* CONVERSION TO STRING *************
digits = [];
var time : Number = getTimer();
for (var i : int = 0; i < numbers.length; i++) {
digits.push(String(numbers[i]).length);
}
trace('\nCONVERSION TO STRING - time: ' + (getTimer() - time));
trace('sample: ' + digits.slice(0, 10));
// ************* LOGARITMIC CALCULATION *************
digits = [];
time = getTimer();
for (var i : int = 0; i < numbers.length; i++) {
digits.push(Math.floor( Math.log( numbers[i] ) / Math.log(10) ) + 1);
}
trace('\nLOGARITMIC CALCULATION - time: ' + (getTimer() - time));
trace('sample: ' + digits.slice(0, 10));
// ************* DIV 10 ITERATION *************
digits = [];
time = getTimer();
var digit : uint = 0;
for (var i : int = 0; i < numbers.length; i++) {
digit = 0;
for(var temp : Number = numbers[i]; temp >= 1;)
{
temp/=10;
digit++;
}
digits.push(digit);
}
trace('\nDIV 10 ITERATION - time: ' + (getTimer() - time));
trace('sample: ' + digits.slice(0, 10));
// ************* MANUAL CONDITIONING *************
digits = [];
time = getTimer();
var digit : uint;
for (var i : int = 0; i < numbers.length; i++) {
var number : Number = numbers[i];
if (number < 10) digit = 1;
else if (number < 100) digit = 2;
else if (number < 1000) digit = 3;
else if (number < 10000) digit = 4;
else if (number < 100000) digit = 5;
else if (number < 1000000) digit = 6;
else if (number < 10000000) digit = 7;
else if (number < 100000000) digit = 8;
else if (number < 1000000000) digit = 9;
else if (number < 10000000000) digit = 10;
digits.push(digit);
}
trace('\nMANUAL CONDITIONING: ' + (getTimer() - time));
trace('sample: ' + digits.slice(0, 10));
}
}
}
このアルゴリズムは、次のことを前提としても良いかもしれません:
数の境界がわからない
var num = 123456789L;
var len = 0;
var tmp = 1L;
while(tmp < num)
{
len++;
tmp = (tmp << 3) + (tmp << 1);
}
このアルゴリズムは、for ループ (2) に匹敵する速度を提供する必要がありますが、(除算の代わりに 2 ビット シフト、加算と減算) により、少し高速になります。
Log10 アルゴリズムに関しては、Log 関数を計算するための解析式が無限ループを持ち、 Wikiで正確に計算できないため、おおよその答えしか得られません (これは実際に近いですが、それでもなおです) 。
使用しているプログラミング言語に関係なく、最も単純なソリューションを使用してください。整数の桁数を数えることが (便利な) プログラムのボトルネックになるケースは考えられません。
char buffer[32];
int length = sprintf(buffer, "%ld", (long)123456789);
len = (length . show) 123456789
length = String(123456789).length;
$length = strlen(123456789);
length = Len(str(123456789)) - 1
import math
def numdigits(n):
return ( int(math.floor(math.log10(n))) + 1 )
文字列への変換: これは、各数字を反復処理し、現在の数字にマップされる文字を見つけ、文字のコレクションに文字を追加する必要があります。次に、結果の String オブジェクトの長さを取得します。n=#桁の場合、O(n) で実行されます。
for-loop: 数値を 10 で割り、カウンターをインクリメントするという 2 つの数学演算を実行します。n=#桁の場合、O(n) で実行されます。
logarithmic: log10 と floor を呼び出し、1 を加算します。O(1) のように見えますが、log10 または floor 関数がどれほど速いかはよくわかりません。この種のことに関する私の知識は、使用されないことで萎縮してしまったので、これらの機能には複雑さが隠されている可能性があります。
だから私はそれが次のようになると思います:複数の数学演算またはで起こっていることよりも速く数字のマッピングを検索していlog10ますか? 答えはきっと変わる。文字マッピングが高速なプラットフォームもあれば、計算が高速なプラットフォームもあるでしょう。また、最初のメソッドは、長さを取得するためだけに存在する新しい String オブジェクトを作成することにも注意してください。これはおそらく他の 2 つの方法よりも多くのメモリを使用しますが、問題になる場合とそうでない場合があります。
メソッド 1 が使用する atoi/toString アルゴリズムはメソッド 2 と似ているため、競合からメソッド 1 を除外することは明らかです。
方法 3 の速度は、命令セットに log base 10 が含まれているシステム用にコードがコンパイルされているかどうかによって異なります。
非常に大きな整数の場合、log メソッドの方がはるかに高速です。たとえば、2491327 桁の数値 (11920928 番目のフィボナッチ数) の場合、Python は 10 で割るアルゴリズムを実行するのに数分、実行するのに数ミリ秒かかります1+floor(log(n,10))。
複雑にしないでおく：
long long int a = 223452355415634664;
int x;
for (x = 1; a >= 10; x++)
{
a = a / 10;
}
printf("%d", x);
ループの代わりに再帰的なソリューションを使用できますが、多少似ています。
@tailrec
def digits (i: Long, carry: Int=1) : Int = if (i < 10) carry else digits (i/10, carry+1)
digits (8345012978643L)
long を使用すると、状況が変わる可能性があります。さまざまなアルゴリズムに対して小さい数値と長い数値を個別に測定し、典型的な入力に応じて適切な数値を選択してください。:)
もちろん、スイッチに勝るものはありません。
switch (x) {
case 0: case 1: case 2: case 3: case 4: case 5: case 6: case 7: case 8: case 9: return 1;
case 10: case 11: // ...
case 99: return 2;
case 100: // you get the point :)
default: return 10; // switch only over int
}
普通の配列を除いて:
int [] size = {1,1,1,1,1,1,1,1,1,2,2,2,2,2,... };
int x = 234561798;
return size [x];
コードサイズを最適化するように言う人もいますが、時期尚早の最適化...
@daniel.sedlacek の結果を見て興味を持ったので、Swift を使用して 10 桁を超える数字をテストしました。プレイグラウンドで次のスクリプトを実行しました。
let base = [Double(100090000000), Double(100050000), Double(100050000), Double(100000200)]
var rar = [Double]()
for i in 1...10 {
for d in base {
let v = d*Double(arc4random_uniform(UInt32(1000000000)))
rar.append(v*Double(arc4random_uniform(UInt32(1000000000))))
rar.append(Double(1)*pow(1,Double(i)))
}
}
print(rar)
var timeInterval = NSDate().timeIntervalSince1970
for d in rar {
floor(log10(d))
}
var newTimeInterval = NSDate().timeIntervalSince1970
print(newTimeInterval-timeInterval)
timeInterval = NSDate().timeIntervalSince1970
for d in rar {
var c = d
while c > 10 {
c = c/10
}
}
newTimeInterval = NSDate().timeIntervalSince1970
print(newTimeInterval-timeInterval)
80要素の結果
0.105069875717163 for floor(log10(x))
0.867973804473877 for div 10 iterations
let numDigits num =
let num = abs(num)
let rec numDigitsInner num =
match num with
| num when num < 10 -> 1
| _ -> 1 + numDigitsInner (num / 10)
numDigitsInner num
文字列にキャストしない F# バージョン。