質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.52%

  • C

    3670questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    3442questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • アルゴリズム

    408questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

C/C++で整数の桁数を求める場合、1番処理が速いのはどの方法でしょうか?

解決済

回答 6

投稿 編集

  • 評価
  • クリップ 3
  • VIEW 2,820

yama_da

score 65

タイトル通りですが、C/C++で整数の桁数を最短で求めるにはどうすればよいでしょうか?
実験として、以下のようなプログラムを書いて、①10で割っていく、②常用対数を使う、の2通りを試してみました。

#include <stdio.h>
#include <math.h>
#include <time.h>


void countDigit(int n)
{
  int digit = 1;
  clock_t start,end;

  start = clock();

  while((n /= 10) != 0)
    digit++;

  end = clock();

  printf("countDigit()          digit::%d  time::%dms\n",digit,(int)(end - start));
}

void countDigitUsingLog(int n)
{
  clock_t start,end;
  int digit;

  start = clock();

  digit = log10(n) + 1;

  end = clock();
  printf("countDigitUsingLog()  digit::%d  time::%dms\n",digit,(int)(end - start));
}

int main(void)
{
  int n = 0;
  int i;

  for(i = 1;i < 10;i++) {
    n = n * 10 + i;
    printf("N = %d\n",n);
    countDigit(n);
    countDigitUsingLog(n);
    printf("\n");
  }

  return 0;
}

実行結果::

N = 1
countDigit()          digit::1  time::3ms
countDigitUsingLog()  digit::1  time::47ms

N = 12
countDigit()          digit::2  time::1ms
countDigitUsingLog()  digit::2  time::12ms

N = 123
countDigit()          digit::3  time::2ms
countDigitUsingLog()  digit::3  time::2ms

N = 1234
countDigit()          digit::4  time::1ms
countDigitUsingLog()  digit::4  time::2ms

N = 12345
countDigit()          digit::5  time::1ms
countDigitUsingLog()  digit::5  time::2ms

N = 123456
countDigit()          digit::6  time::2ms
countDigitUsingLog()  digit::6  time::2ms

N = 1234567
countDigit()          digit::7  time::1ms
countDigitUsingLog()  digit::7  time::2ms

N = 12345678
countDigit()          digit::8  time::2ms
countDigitUsingLog()  digit::8  time::2ms

N = 123456789
countDigit()          digit::9  time::2ms
countDigitUsingLog()  digit::9  time::3ms

僕の実行環境では、①は桁数に関わらず一定の速さ、②は3桁目あたりから①の速さに追いつく、といった結果になりました。この結果だけみると①のほうが良いのではないかの思ったのですが、C/C++は初心者に毛が生えた程度の知識しかないので、検証方法にあまり自信がありません。この結果を信じてもよいのでしょか?また、他にもっと良い方法があれば教えてください。

<実行環境>
Ubuntu 16.04 LTS
CPU : AMD A4-5000 APU with Radeon(TM) HD Graphics
gcc version 5.4.1 20160904 (Ubuntu 5.4.1-2ubuntu1~16.04)

<2017/1/23 追記>
皆さん回答ありがとうございました!ikedasさんのものとほとんど変わりませんが、皆さんが回答してくださったものを一通り僕の環境でも試してみました。与えられる整数値の桁数の範囲が分かっているなら、2分探索が一番良さそうです。とても勉強になりました、みなさん本当にありがとうございました!以下修正版と結果です。

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <limits.h>
#include <assert.h>

#define LOOP 10000000


void countDigit(int n)
{
  int digit = 1;
  clock_t start,end;

  start = clock();

  for(size_t i = 0;i < LOOP; ++i) {
    while((n /= 10) != 0)
      digit++;
  }

  end = clock();

  printf("%-25s\tdigit::%d\ttime::%fs\n",
     "countDigit()",digit,((double)end - start)/CLOCKS_PER_SEC);
}

void countDigitUsingLog(int n)
{
  clock_t start,end;
  int digit;

  start = clock();

  for(size_t i = 0;i < LOOP; ++i)
  digit = log10(n) + 1;

  end = clock();

  printf("%-25s\tdigit::%d\ttime::%fs\n",
     "countDigitUsingLog()",digit,((double)end - start)/CLOCKS_PER_SEC);
}

void countDigitBinary(int n)
{
      int digit;
  clock_t start,end;

  start = clock();

  for(size_t i = 0;i < LOOP; ++i) {

    if (n < 100000) {
      if (n < 1000) {
        if (n < 10)
          digit = 1;
        else if (n < 100)
          digit = 2;
        else
          digit = 3;
      } else {
        if (n < 10000)
          digit = 4;
        else
          digit = 5;
      }
    } else {
      if (n < 10000000) {
        if (n < 1000000)
          digit = 6;
        else
          digit = 7;
      } else {
        if (n < 100000000)
          digit = 8;
        else if (n < 1000000000)
          digit = 9;
        else
          digit = 10;
      }
    }
  }


  end = clock();

  printf("%-25s\tdigit::%d\ttime::%fs\n",
     "countDigitBinary()",digit,((double)end - start)/CLOCKS_PER_SEC);
}

int digitPoor(int n)
{
    assert(INT_MAX == 2147483647);
    assert(n >= 0);

    if (n < 10)         return 1;
    if (n < 100)        return 2;
    if (n < 1000)       return 3;
    if (n < 10000)      return 4;
    if (n < 100000)     return 5;
    if (n < 1000000)    return 6;
    if (n < 10000000)   return 7;
    if (n < 100000000)  return 8;
    if (n < 1000000000) return 9;
    return 10;
}

void countDigitPoor(int n)
{
    clock_t start,end;
    int digit;

    start = clock();
    for (size_t i=0; i < 10000000; ++i) {
        digit = digitPoor(n);
    }
    end = clock();
    printf("%-25s\tdigit::%d\ttime::%fs\n",
       "countDigitPoor()",digit,((double)end - start)/CLOCKS_PER_SEC);
}

void countDigitUsingSprintf(int n)
{
  clock_t start,end;
  int digit;
  char dummy[10];

  start = clock();

  for(size_t i = 0;i < LOOP; ++i)
  digit = sprintf(dummy, "%d", n);

  end = clock();
  printf("%-25s\tdigit::%d\ttime::%fs\n",
     "countDigitUsingSprintf()",digit,((double)end - start)/CLOCKS_PER_SEC);
}

void countForLoop()
{
  clock_t start,end;
  volatile int x=1;

  start = clock();

  for (size_t i = 0; i < LOOP; ++i)
    {
      x=i;
    }

  end = clock();

  printf("%-25s\t--------\ttime::%fs\n",
     "countForLoop()",((double)end - start)/CLOCKS_PER_SEC);  
}

int main(void)
{
  int n = 0;
  int i;

  for(i = 1;i < 10;i++) {
    n = n * 10 + i;
    printf("N = %d\n",n);
    countForLoop();
    countDigit(n);
    countDigitUsingLog(n);
    countDigitBinary(n);
    countDigitPoor(n);
    countDigitUsingSprintf(n);
    printf("\n");
  }

  return 0;
}
N = 1
countForLoop()               --------    time::0.045770s
countDigit()                 digit::1    time::0.100439s
countDigitUsingLog()         digit::1    time::0.378452s
countDigitBinary()           digit::1    time::0.053568s
countDigitPoor()             digit::1    time::0.079120s
countDigitUsingSprintf()     digit::1    time::2.265236s

N = 12
countForLoop()               --------    time::0.043182s
countDigit()                 digit::2    time::0.100408s
countDigitUsingLog()         digit::2    time::1.012793s
countDigitBinary()           digit::2    time::0.060286s
countDigitPoor()             digit::2    time::0.092724s
countDigitUsingSprintf()     digit::2    time::2.341804s

N = 123
countForLoop()               --------    time::0.042746s
countDigit()                 digit::3    time::0.100416s
countDigitUsingLog()         digit::3    time::1.004158s
countDigitBinary()           digit::3    time::0.060143s
countDigitPoor()             digit::3    time::0.108729s
countDigitUsingSprintf()     digit::3    time::2.442325s

N = 1234
countForLoop()               --------    time::0.045008s
countDigit()                 digit::4    time::0.100400s
countDigitUsingLog()         digit::4    time::1.004526s
countDigitBinary()           digit::4    time::0.048930s
countDigitPoor()             digit::4    time::0.132441s
countDigitUsingSprintf()     digit::4    time::2.530141s

N = 12345
countForLoop()               --------    time::0.042238s
countDigit()                 digit::5    time::0.100400s
countDigitUsingLog()         digit::5    time::1.008050s
countDigitBinary()           digit::5    time::0.060654s
countDigitPoor()             digit::5    time::0.144062s
countDigitUsingSprintf()     digit::5    time::2.624742s

N = 123456
countForLoop()               --------    time::0.042451s
countDigit()                 digit::6    time::0.100724s
countDigitUsingLog()         digit::6    time::1.008027s
countDigitBinary()           digit::6    time::0.058717s
countDigitPoor()             digit::6    time::0.177779s
countDigitUsingSprintf()     digit::6    time::2.751899s

N = 1234567
countForLoop()               --------    time::0.041235s
countDigit()                 digit::7    time::0.100376s
countDigitUsingLog()         digit::7    time::1.004352s
countDigitBinary()           digit::7    time::0.069315s
countDigitPoor()             digit::7    time::0.193293s
countDigitUsingSprintf()     digit::7    time::2.825540s

N = 12345678
countForLoop()               --------    time::0.041624s
countDigit()                 digit::8    time::0.100474s
countDigitUsingLog()         digit::8    time::1.004698s
countDigitBinary()           digit::8    time::0.075757s
countDigitPoor()             digit::8    time::0.215140s
countDigitUsingSprintf()     digit::8    time::2.937961s

N = 123456789
countForLoop()               --------    time::0.043923s
countDigit()                 digit::9    time::0.100387s
countDigitUsingLog()         digit::9    time::1.004096s
countDigitBinary()           digit::9    time::0.094569s
countDigitPoor()             digit::9    time::0.254226s
countDigitUsingSprintf()     digit::9    time::3.033319s
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

質問への追記・修正、ベストアンサー選択の依頼

  • ikedas

    2017/01/22 23:45

    実行時間を正確にだすには、繰り返し実行 (1000回とか) して平均を取った方がいいですよ。

    キャンセル

回答 6

+6

頭の悪そうなコードが良いパフォーマンスを出すことがあります。
ベンチマークはChironianさんのコードをベースにさせていただきました。

#include <limits.h>
#include <assert.h>

...

int digitPoor(int n)
{
    assert(INT_MAX == 2147483647);
    assert(n >= 0);

    if (n < 10)         return 1;
    if (n < 100)        return 2;
    if (n < 1000)       return 3;
    if (n < 10000)      return 4;
    if (n < 100000)     return 5;
    if (n < 1000000)    return 6;
    if (n < 10000000)   return 7;
    if (n < 100000000)  return 8;
    if (n < 1000000000) return 9;
    return 10;
}

void countDigitPoor(int n)
{
    clock_t start,end;
    int digit;

    start = clock();
    for (size_t i=0; i < 10000000; ++i) {
        digit = digitPoor(n);
    }
    end = clock();
    printf("countDigitPoor()      digit::%d  time::%fsec\n",digit,((double)end - start)/CLOCKS_PER_SEC);
}
$ gcc --version
gcc (GCC) 6.3.1 20170109
...
$ gcc -O1 -DNDEBUG ./bench.c -lm
$ ./a.out
N = 1
countForLoop()                  time::0.003087sec
countDigit()          digit::1  time::0.005684sec
countDigitUsingLog()  digit::1  time::0.138261sec
countDigitPoor()      digit::1  time::0.003104sec

N = 12
countForLoop()                  time::0.003059sec
countDigit()          digit::2  time::0.010454sec
countDigitUsingLog()  digit::2  time::0.447394sec
countDigitPoor()      digit::2  time::0.003249sec

N = 123
countForLoop()                  time::0.003394sec
countDigit()          digit::3  time::0.019453sec
countDigitUsingLog()  digit::3  time::0.444180sec
countDigitPoor()      digit::3  time::0.003249sec

N = 1234
countForLoop()                  time::0.003439sec
countDigit()          digit::4  time::0.027927sec
countDigitUsingLog()  digit::4  time::0.436616sec
countDigitPoor()      digit::4  time::0.003247sec

N = 12345
countForLoop()                  time::0.003234sec
countDigit()          digit::5  time::0.034176sec
countDigitUsingLog()  digit::5  time::0.448515sec
countDigitPoor()      digit::5  time::0.003319sec

N = 123456
countForLoop()                  time::0.003215sec
countDigit()          digit::6  time::0.043226sec
countDigitUsingLog()  digit::6  time::0.446970sec
countDigitPoor()      digit::6  time::0.003536sec

N = 1234567
countForLoop()                  time::0.003203sec
countDigit()          digit::7  time::0.053820sec
countDigitUsingLog()  digit::7  time::0.439272sec
countDigitPoor()      digit::7  time::0.003598sec

N = 12345678
countForLoop()                  time::0.003272sec
countDigit()          digit::8  time::0.065535sec
countDigitUsingLog()  digit::8  time::0.446334sec
countDigitPoor()      digit::8  time::0.003244sec

N = 123456789
countForLoop()                  time::0.003499sec
countDigit()          digit::9  time::0.079410sec
countDigitUsingLog()  digit::9  time::0.444234sec
countDigitPoor()      digit::9  time::0.003261sec

でも移植性を考えると割り算が無難だと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+5

こんにちは。

数回くらいの除算や1回のlog10計算にかかる時間は短すぎてclock()関数ではとても測れません。10,000,000回ほど繰り返して計測してみました。(utunbu 16.04 LTS on VirtualBox)

圧倒的に10で割る方が早いです。
32ビットであれば、このまま10で割る方が勝つと思います。
64ビットならば、どこかで逆転すると思います。

#include <stdio.h>
#include <math.h>
#include <time.h>

void countForLoop()
{
  clock_t start,end;
  volatile int x=1;

  start = clock();

  for (size_t i=0; i < 10000000; ++i)
  {
    x=i;
  }

  end = clock();

  printf("countForLoop()                  time::%fsec\n",((double)end - start)/CLOCKS_PER_SEC);
}

void countDigit(int n)
{
  int digit = 1;
  clock_t start,end;

  start = clock();

  for (size_t i=0; i < 10000000; ++i)
  {
    digit=1;
    int x=n;
    while((x /= 10) != 0)
      digit++;
  }

  end = clock();

  printf("countDigit()          digit::%d  time::%fsec\n",digit,((double)end - start)/CLOCKS_PER_SEC);
}

void countDigitUsingLog(int n)
{
  clock_t start,end;
  int digit;

  start = clock();

  for (size_t i=0; i < 10000000; ++i)
    digit = log10(n) + 1;

  end = clock();
  printf("countDigitUsingLog()  digit::%d  time::%fsec\n",digit,((double)end - start)/CLOCKS_PER_SEC);
}

int main(void)
{
  int n = 0;
  int i;

  for(i = 1;i < 10;i++) {
    n = n * 10 + i;
    printf("N = %d\n",n);
    countForLoop();
    countDigit(n);
    countDigitUsingLog(n);
    printf("\n");
  }

  return 0;
}
N = 1
countForLoop()                  time::0.003324sec
countDigit()          digit::1  time::0.005868sec
countDigitUsingLog()  digit::1  time::0.592562sec

N = 12
countForLoop()                  time::0.003532sec
countDigit()          digit::2  time::0.015215sec
countDigitUsingLog()  digit::2  time::0.880503sec

N = 123
countForLoop()                  time::0.002862sec
countDigit()          digit::3  time::0.027572sec
countDigitUsingLog()  digit::3  time::0.875855sec

N = 1234
countForLoop()                  time::0.002556sec
countDigit()          digit::4  time::0.041923sec
countDigitUsingLog()  digit::4  time::0.857530sec

N = 12345
countForLoop()                  time::0.003236sec
countDigit()          digit::5  time::0.057147sec
countDigitUsingLog()  digit::5  time::0.872361sec

N = 123456
countForLoop()                  time::0.002726sec
countDigit()          digit::6  time::0.074915sec
countDigitUsingLog()  digit::6  time::0.875790sec

N = 1234567
countForLoop()                  time::0.002834sec
countDigit()          digit::7  time::0.089634sec
countDigitUsingLog()  digit::7  time::0.862718sec

N = 12345678
countForLoop()                  time::0.002489sec
countDigit()          digit::8  time::0.110157sec
countDigitUsingLog()  digit::8  time::0.879816sec

N = 123456789
countForLoop()                  time::0.003085sec
countDigit()          digit::9  time::0.125394sec
countDigitUsingLog()  digit::9  time::0.876311sec

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

checkベストアンサー

+4

sharowさんの「貧者のアルゴリズム」では最悪計算量がO(log n)ですが、二分探索にするとO(log log n)に減らせます!

int
digitBinary(int n)
{
    if (n < 100000) {
        if (n < 1000) {
            if (n < 10)
                return 1;
            else if (n < 100)
                return 2;
            else
                return 3;
        } else {
            if (n < 10000)
                return 4;
            else
                return 5;
        }
    } else {
        if (n < 10000000) {
            if (n < 1000000)
                return 6;
            else
                return 7;
        } else {
            if (n < 100000000)
                return 8;
            else if (n < 1000000000)
                return 9;
            else
                return 10;
        }
    }
}

void
countDigitBinary(int n)
{   
    clock_t start,end;
    int digit;

    start = clock(); 
    for (size_t i=0; i < 10000000; ++i) {
        digit = digitBinary(n);
    }
    end = clock();
    printf("countDigitBinary()    digit::%d  time::%fsec\n",digit,((double)end - start)/CLOCKS_PER_SEC);
}

〈実行環境〉
macOS Sierra 10.12.2
CPU Core i5 1.7 GHz 

clang --version
Apple LLVM version 8.0.0 (clang-800.0.42.1)
Target: x86_64-apple-darwin16.3.0
Thread model: posix

clang -O0

N = 1
countForLoop()                  time::0.023104sec
countDigit()          digit::1  time::0.047660sec
countDigitUsingLog()  digit::1  time::0.246963sec
countDigitPoor()      digit::1  time::0.037537sec
countDigitBinary()    digit::1  time::0.039012sec

N = 12
countForLoop()                  time::0.023421sec
countDigit()          digit::2  time::0.084005sec
countDigitUsingLog()  digit::2  time::0.233920sec
countDigitPoor()      digit::2  time::0.051066sec
countDigitBinary()    digit::2  time::0.043674sec

N = 123
countForLoop()                  time::0.025515sec
countDigit()          digit::3  time::0.117607sec
countDigitUsingLog()  digit::3  time::0.236735sec
countDigitPoor()      digit::3  time::0.053296sec
countDigitBinary()    digit::3  time::0.051939sec

N = 1234
countForLoop()                  time::0.025521sec
countDigit()          digit::4  time::0.173296sec
countDigitUsingLog()  digit::4  time::0.234089sec
countDigitPoor()      digit::4  time::0.060343sec
countDigitBinary()    digit::4  time::0.045750sec

N = 12345
countForLoop()                  time::0.025067sec
countDigit()          digit::5  time::0.224774sec
countDigitUsingLog()  digit::5  time::0.236502sec
countDigitPoor()      digit::5  time::0.070013sec
countDigitBinary()    digit::5  time::0.051067sec

N = 123456
countForLoop()                  time::0.024541sec
countDigit()          digit::6  time::0.300018sec
countDigitUsingLog()  digit::6  time::0.236935sec
countDigitPoor()      digit::6  time::0.084706sec
countDigitBinary()    digit::6  time::0.043754sec

N = 1234567
countForLoop()                  time::0.026226sec
countDigit()          digit::7  time::0.365955sec
countDigitUsingLog()  digit::7  time::0.241753sec
countDigitPoor()      digit::7  time::0.082430sec
countDigitBinary()    digit::7  time::0.049685sec

N = 12345678
countForLoop()                  time::0.025289sec
countDigit()          digit::8  time::0.430325sec
countDigitUsingLog()  digit::8  time::0.236876sec
countDigitPoor()      digit::8  time::0.094294sec
countDigitBinary()    digit::8  time::0.050104sec

N = 123456789
countForLoop()                  time::0.026642sec
countDigit()          digit::9  time::0.513616sec
countDigitUsingLog()  digit::9  time::0.237418sec
countDigitPoor()      digit::9  time::0.097828sec
countDigitBinary()    digit::9  time::0.061868sec


clang -Ofast

N = 1
countForLoop()                  time::0.004516sec
countDigit()          digit::1  time::0.000000sec
countDigitUsingLog()  digit::1  time::0.000039sec
countDigitPoor()      digit::1  time::0.000000sec
countDigitBinary()    digit::1  time::0.000000sec

N = 12
countForLoop()                  time::0.003351sec
countDigit()          digit::2  time::0.011395sec
countDigitUsingLog()  digit::2  time::0.000001sec
countDigitPoor()      digit::2  time::0.000000sec
countDigitBinary()    digit::2  time::0.000000sec

N = 123
countForLoop()                  time::0.003504sec
countDigit()          digit::3  time::0.020016sec
countDigitUsingLog()  digit::3  time::0.000002sec
countDigitPoor()      digit::3  time::0.000001sec
countDigitBinary()    digit::3  time::0.000000sec

N = 1234
countForLoop()                  time::0.005942sec
countDigit()          digit::4  time::0.033859sec
countDigitUsingLog()  digit::4  time::0.000002sec
countDigitPoor()      digit::4  time::0.000001sec
countDigitBinary()    digit::4  time::0.000000sec

N = 12345
countForLoop()                  time::0.003354sec
countDigit()          digit::5  time::0.050976sec
countDigitUsingLog()  digit::5  time::0.000001sec
countDigitPoor()      digit::5  time::0.000001sec
countDigitBinary()    digit::5  time::0.000002sec

N = 123456
countForLoop()                  time::0.003368sec
countDigit()          digit::6  time::0.066714sec
countDigitUsingLog()  digit::6  time::0.000001sec
countDigitPoor()      digit::6  time::0.000001sec
countDigitBinary()    digit::6  time::0.000000sec

N = 1234567
countForLoop()                  time::0.003355sec
countDigit()          digit::7  time::0.071519sec
countDigitUsingLog()  digit::7  time::0.000001sec
countDigitPoor()      digit::7  time::0.000001sec
countDigitBinary()    digit::7  time::0.000000sec

N = 12345678
countForLoop()                  time::0.005837sec
countDigit()          digit::8  time::0.093607sec
countDigitUsingLog()  digit::8  time::0.000001sec
countDigitPoor()      digit::8  time::0.000000sec
countDigitBinary()    digit::8  time::0.000000sec

N = 123456789
countForLoop()                  time::0.003542sec
countDigit()          digit::9  time::0.107566sec
countDigitUsingLog()  digit::9  time::0.000002sec
countDigitPoor()      digit::9  time::0.000002sec
countDigitBinary()    digit::9  time::0.000001sec


……速くなった……でも、桁数の小さいときも速くなってるように見えるのはなんでだろう?

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2017/01/23 22:19

    誰かやらないかと待っていたら本当にやってくれたので+1

    キャンセル

  • 2017/01/24 00:04

    BAうれしいです。が、平均計算量では「貧者」とタメのはずなので、Cの整数型くらいの桁数ならそちらでいいかな、と。

    あと、書いてから気づきましたが、二分探索のアイディアはmajiponiさんがすでに書いておられました。あと2進対数 (要はビット数ですね) を使うやり方というのはどんなものなのか、興味があります。

    キャンセル

+1

atoi関数定義で文字列にして、strlenで文字列の長さを求める。

あっ!コーディングか早いだけです、、、

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

+1

sprintfを使う方法もあります。

void countDigitUsingSprintf(int n)
{
  clock_t start,end;
  int digit;
  char dummy[10];

  start = clock();

  digit = sprintf(dummy, "%d", n);

  end = clock();
  printf("countDigitUsingSptintf()  digit::%d  time::%dms\n",digit,(int)(end - start));
}

速い遅いは環境や入力データに依存してしまうのかな。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

0

最適なアルゴリズムは時と場合により変わります。例えば、小さな数の入力がほとんどであれば、割り算の繰り返しのほうが圧倒的に速いです。が、入力が完全なランダムであれば、桁数が大きい入力が増えるので、常用対数のほうが有利になることもあります。なので、どちらが速いかという質問の答えは、使い方次第となります。

ちなみに私が最初に思いついたのは、2進対数(切り捨て)を出して10進だとどうなるか調べる方法、それから二分探索です。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.52%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

  • 解決済

    コンパイルエラーが直せません。

    選択ソートの実行時間を計測するためのプログラムを書いているのですが、コンパイルエラーが直すことができません。 以下がソースコードです。 #include <stdio.

  • 解決済

    警告やコンパイルエラーを直すことができません。

    クイックソートのソースを書いているのですがうまくコンパイルすることができません。 #include <stdio.h> #include <stdlib.h> #includ

  • 解決済

    C言語 Linux メモリの確保 状況把握

    以下のプログラムを修正して 5秒間で何回の入れ替えを行えるかを計測できるようにしてもらいたいです #include <stdio.h> #include <stdlib.h

  • 解決済

    linux 処理時間の表示

    C言語でLinuxを使っています。メモリを確保したりするプログラムなのですが、以下のプログラムを修正して 、5秒間で何回の入れ替えを行えるかを計測できるようにしてもらいたいです。初

  • 受付中

    c言語

    1から100までの重複のない乱数を作成して、そこから10個の三の倍数を抜き出すプログラミングを教えてください。

  • 解決済

    タイピングゲームの作成、乱数について

    前提・実現したいこと Cでタイピングゲームのような物を作っているのですが、今のコードのままだとランダムに表示させた問題を正解したときに再度同じ問題が出てしまいます 既に使用した

  • 受付中

    2分木のデータの追加

    前提・実現したいこと ■概要 0~n-1のn個のデータを、ツリー構造としてリスト化 (リスト化の方法) 操作: 0<=r<=1として、①②の場合分けによって右の子を見

  • 解決済

    文字列から、ある文字と文字の間にある文字列をすべて抜き出したい

    前提・実現したいこと C言語で、文字列からある文字と文字の間にあるものをすべて抜き出したい。 例えば下のように<a>と<b>のタグがあり、その間の文字をすべて出力をしたいで

同じタグがついた質問を見る

  • C

    3670questions

    C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

  • C++

    3442questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

  • アルゴリズム

    408questions

    アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。