14

明らかな解決策の1つは次のとおりです。

int n = 2134;
while(n > 9)
    n /= 10;

これには線形時間がかかります。もっと速くできるでしょうか？

これは線形時間よりも速いですか:

char s[100];
sprintf(s, "%d", n);
n = s[0]-'0';

他の方法はどれですか (効率が主な関心事です)? 最初の桁だけを見つける必要があることを除いて、これ
を見てきました。（また、答えがわかりません）。

4

13 に答える 13

22

一部のプロセッサには、数値の「大きさ」を非常に迅速に計算する命令があります ( http://en.wikipedia.org/wiki/Leading_zero_countを参照)。これは、繰り返し 10 で除算する代わりに、10 のべき乗をすばやく選択し、それで除算するために使用できます。

clz数値の 2 進数表現 (0...32) の先行ゼロ ビットの数を計算する関数が与えられたとします。次に、先頭のゼロの数ごとに適切な 10 の累乗を与えるルックアップ テーブルを使用できます。

uint32_t powers_of_10[33] = {
    1000000000, 1000000000,
    100000000, 100000000, 100000000,
    10000000, 10000000, 10000000,
    1000000, 1000000, 1000000, 1000000,
    100000, 100000, 100000,
    10000, 10000, 10000,
    1000, 1000, 1000, 1000,
    100, 100, 100,
    10, 10, 10,
    1, 1, 1, 1, 1
};

int CalcFirstDecimalDigit(uint32_t x)
{
    int leading_zeros = clz(x);
    x /= powers_of_10[leading_zeros];
    if (x >= 10)
        return 1;
    else
        return x;
}
于 2013-06-30T19:46:27.117 に答える
14

たとえば、32 ビット符号なしの場合:

ステップ 1:値が次のどの区間にあるかを (二分探索によって) 決定します。

0 .. 9
10 .. 99
100 .. 999
1000 .. 9999
10000 .. 99999
100000 .. 999999
1000000 .. 9999999
10000000 .. 99999999
100000000 .. 999999999
1000000000 .. 4294967295

最大 4 つの比較を行います

ステップ2：

先頭の桁を 1 除算して計算します。

于 2013-06-30T19:47:51.733 に答える
6

sprintf(私が想定しているように)大幅に遅くなると確信しています。除算操作の数を減らすために最適化を行うことができます (これは、ほぼすべてのプロセッサで最も遅い命令の 1 つです)。

したがって、次のようなことができます。

 while(n > 10000)
   n /= 1000;

 while(n >= 9)
   n /= 10;

もちろん、速度が本当に重要な場合はそうです。

于 2013-06-30T19:00:38.403 に答える
5

Your second example should use sprintf. Anyway, it cannot be faster since the entire number is printed, thus all digits are searched.

The linked question/answer uses a property of logarithm: for a number of x digits, it's base 10 logarithm is between x and x+1. But, due to floating point errors this method doesn't really work properly in some cases. Also, take into consideration the fact that doing floating point is slower than doing integer arithmetic.

Thus, the simplest solution is also the faster.

于 2013-06-30T18:59:08.240 に答える
4

O(1) 一定時間で実行できますが、非常に大きなメモリ使用量が犠牲になります。それは同じ古い時間/メモリのトレードオフです。

2^31 エントリ (signed int)、エントリあたり 4 ビットのルックアップ テーブルを作成できます (4 ビットを使用すると、数値の最初の桁 1 ～ 9 を 10 進表現でエンコードできます)。

次に、int を使用してルックアップ テーブルにアクセスし、O(1) の最初の桁を取得できます。ルックアップ テーブルは 2^31 * 4 ビット -> 1024 M バイト

私が考える最速の方法です...

于 2013-06-30T19:41:35.820 に答える
4

これは、二分探索の一種のバリエーションです。二分探索のように O(log n) です。速いかどうかは、整数除算をどれだけ速くできるかによって異なります。

if (n >= 100000000)
    n /= 100000000
if (n >= 10000)
    n /= 10000
if (n >= 100)
    n /= 100
if (n >= 10)
    n /= 10

このメソッドは、より大きな範囲の整数に対して簡単に拡張できます。

于 2014-09-29T04:16:58.897 に答える
3

あなたはこれを簡単に行うことができます：

//Shashank Jain
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
    int num,fdigit;
    cin>>num;
    if(num<0)
        num*=-1;
    int l=log10(num); // l = (length of number -1)

    fdigit=num/pow(10,l);

    cout<<fdigit<<endl;
    return 0;
}
于 2013-07-01T08:00:46.757 に答える
1 
int FirstDigit ( int Number ) {

    // to obtain the <number of digits -1> use this math formula:

    int DigitsInNumber = (int) lg(Number);           

    long TenExpon = pow(10, DigitsInNumber);

    return (Number / TenExpon);                //first digit
}

また：lg(n) = ln(n) / ln(10);

于 2015-07-09T18:15:25.400 に答える
0

最初の解決策 (n が >= 0 であることがわかっていると仮定) はほぼ最適であり、インライン アセンブリ言語を使用することによってのみ大幅に改善できると思います。しかし、それは何百万ものそのような数値を処理している場合にのみ価値があります.

あなたの2番目の解決策は、どうすればうまく言えますか? -- より Java 的なアプローチ: パフォーマンス? 気になるラディダ…

于 2013-06-30T19:00:09.593 に答える
-2

数値が x9x8x7x6x5x4x3x2x1 の場合、10 ^ 8 で割るだけなので、次のものが必要です。バイナリ検索を使用できます/

于 2013-06-30T19:49:23.623 に答える