↑ for(tmp=num;tmp>0;tmp /= 10) *p++;
itoa高速にするなら
for(tmp=num;tmp>0;tmp /= 10) *p++;
の処理は
*p += log( num ) + 1;
log(1) = 0
log(5) = 0.69897
log(10) = 1
log(50) = 1.69897
log(100) = 2
log(500) = 2.69897
log(1000) = 3
log(5000) = 3.69897
log(10000) = 4
log(50000) = 4.69897
log(100000) = 5
という感じです。
高速化するならこの辺りを物理演算ボードにまかすw
もっと速いのは stdlib.h に定義されてる itoaですが。
Rのべんきょー
行列 89, 93, 87, 88, 91, 87, 85, 90, 92, 91, 88, 90をプロツトする
x <- c(89, 93, 87, 88, 91, 87, 85, 90, 92, 91, 88, 90) y <- c(1:NROW(x)) z <- call('plot', x, y) eval(z)
plagger入れるにはfreebsd(freebsd6以降)が必須です
ほかのosじゃはまります。
かいせつ('A`) 投下用作成中
ソースコードでの回答ありがとうございます。
http://q.hatena.ne.jp/1207585413
できれば説明がほしかったのですが、自分への試練と思い勉強します。
がーん('A`)手段が目的にナッテタヨ
3のつく数字を判定する方法は関数 itoa(num,buf,10) (既に用意されている関数)用意されていないらしいで
10進数であると仮定して文字列に変換した後
strchr (こちらも用意されている関数)で文字 '3' をサーチすればいいと思います('A`)
#include <stdio.h> #include <stdlib.h> #include <string.h> char buf[99]; int ahoninarukazu = 3337; itoa(ahoninarukazu ,buf,10); // buf に "3337" が入る if( strchr(buf,'3') != NULL ) printf("あほになるー"); // '3' を含む
以下は投下したコードのコメント?つき
/* -------------------------------------------------------------------- gcc で itoaを呼んでもまともにコール出来ない 実際にないらしい。MSCがおまけでつけてるだけだったらしい */ /* -------------------------------------------------------------------- ↓返値 変換された文字へのポインタ char* buf そのもの char * itoa( ↓変換する数値 const int num , ↓変換された文字を格納するメモリへのポインタ char* buf, ↓無視します(stdlibにあるものは8,10,16などを指定しほげほげ進数に変換できます) const int ignore ) */ char *itoa( const int num ,char* buf, const int ignore ) { /* -------------------------------------------------------------------- 文字のテーブルです。 ここから字引みたいなことやります。 簡単化のためこんな文字列の感じで書かれていますが、 これは // [要素] ------------- 0 1 2 3 4 5 6 7 8 9 10 ---- const char table[] = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '\0' }; のことです。 数値 0など を 文字 '0'など に変換するときに使います。 */ const char table[] = "0123456789"; /* -------------------------------------------------------------------- ポインタ *p はバッファ buf の先頭 まずは自分のいる位置をポインタさんに教えます「buf の先頭」 e.g.: num = 12345 buf p ZZZZZZZZZZZZXXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZZ.... */ char *p = buf; /* -------------------------------------------------------------------- num を持っておきたいためtmpを用意 */ int tmp; /* -------------------------------------------------------------------- 数値の尻から判定していくので書き込みポインタを 数値の桁数分すすめます e.g.: num = 12345 buf >>>>>p ZZZZZZZZZZZZXXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXXXXXXXXXXXXXXZZZZZZZZZZZZZZZZZ.... */ for(tmp=num;tmp>0;tmp /= 10) *p++; /* -------------------------------------------------------------------- 文字の終端は\0 である これがないと表示するときにバッファオーバ e.g.: num = 12345 >>>>>p buf | ZZZZZZZZZZZZXXXXX0XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXXX" 注意: \0 を 0として表示してます */ *p='\0'; /* -------------------------------------------------------------------- 数値の尻(一桁目)から数値を判定していく 1. tmp%10: tmp%10 で一番下桁めの数 がわかる 0 1 2 3 4 5 6 7 8 9 2. table[tmp%10]: table から文字を得る tmp%10 が0 のとき table[0] = '0' tmp%10 が1 のとき table[1] = '1' tmp%10 が2 のとき table[2] = '2' tmp%10 が3 のとき table[3] = '3' tmp%10 が4 のとき table[4] = '4' tmp%10 が5 のとき table[5] = '5' tmp%10 が6 のとき table[6] = '6' tmp%10 が7 のとき table[7] = '7' tmp%10 が8 のとき table[8] = '8' tmp%10 が9 のとき table[9] = '9' 3. *--p= pを一つ前にもってく ポインタ*p に ↑で得た文字を突っ込んで 4. tmp /= 10 で次の桁を処理する というのを 最後の桁 tmp>0になるまで繰り返す e.g.: num = 12345 >>>>>p buf ZZZZZZZZZZZZXXXXX0XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXXX" (--p) num = 12345 >>>>p b | ZZZZZZZZZZZZXXXXX0XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXXX" (*p = table[tmp%10]) num = 12345 tmp = 12345 tmp % 10= 5 table[5]= '5' >>>>p b | ZZZZZZZZZZZZXXXX50XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXX5" (--p) num = 12345 >>>p b | ZZZZZZZZZZZZXXXX50XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXXX5" (*p = table[tmp%10]) num = 12345 tmp = 1234 tmp % 10= 4 table[4]= '4' >>>p b | ZZZZZZZZZZZZXXX450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXX45" (--p) num = 12345 >>p b | ZZZZZZZZZZZZXXX450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XXX45" (*p = table[tmp%10]) num = 12345 tmp = 123 tmp % 10= 3 table[3]= '3' >>p b | ZZZZZZZZZZZZXX3450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XX345" (--p) num = 12345 >p b| ZZZZZZZZZZZZXX3450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "XX345" (*p = table[tmp%10]) num = 12345 tmp = 12 tmp % 10= 2 table[2]= '2' >p b| ZZZZZZZZZZZZX23450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "X2345" (--p) num = 12345 p | ZZZZZZZZZZZZX23450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "X2345" (*p = table[tmp%10]) num = 12345 tmp = 1 tmp % 10= 1 table[3]= '1' p | ZZZZZZZZZZZZ123450XXXXXXXXXXZZZZZZZZZZZZZZZZZ buff = "12345" */ for(tmp=num;tmp>0;tmp /= 10) *--p=table[tmp%10]; /* -------------------------------------------------------------------- バッファ buf を返して 数値から文字列変換したものを返す */ return buf; } /* -------------------------------------------------------------------- ここからのコメントはネタです。 */ int main() { /* -------------------------------------------------------------------- buf が 99 なのは、 99桁もある数値で実行しないであろうという 希望からこのような実装にした。 本音はキーボードを打つ回数が少なく それなりに数値としては大きい値のため採用した e.g.: 1 文字 - 9 2 文字 - 99 3 文字 - 0xF (16) 3 文字 - 999 4 文字 - 0xFF (255) 4 文字 - 9999 */ char buf[99]; /* -------------------------------------------------------------------- 要求のある数値の要件は 整数であることのみであるため int を採用した */ int aho; /* -------------------------------------------------------------------- 1 から 50未満 までを変数 aho にいれて 繰り返す */ for(aho=1; aho<50; aho++){ /* -------------------------------------------------------------------- 3 の倍数 か 5の倍数 か 3がつく数 とき 数値を表示 || (論理or) により どれか一つが 0以外なら if(){ .... の中身を実行する e.g.: 1 || 0 || 0 => 1 0==0 は正しいので => 0以外の数値が返る 1==0 は違うので => 0が返る aho%3 は 3で割ったときの余り (0か3の倍数のとき答えは 0) aho%3==0 (3の倍数のとき) 0以外が返る itoa(aho,buf,10) は aho に入っている数値を文字列に変換する関数 buf は おまじない 場所 住み家 10 は 10進数を表す (がここでは無視してるのでなんでもいい itoa から返ってくるのはaho に入っている数値を文字列にしたもの(bufのポインタ)返る strchr は 文字列から 1文字を捜す strchr( 文字列, '3' ) == NULL 以外のとき 文字列に'3'が含まれている ( '3' が含まれている文字列の位置をポインタとして返す) ないとき != 0 としている (正しくは==NULL しないといけない 通例的に NULL == 0 だと仮定してしまっていたが危険であった) */ if( aho%3==0 || aho%5==0 || strchr(itoa(aho,buf,10),'3')) printf("%d\n",aho); } /* -------------------------------------------------------------------- 0 をなにげに返しているのは プログラムが成功したという希望から */ return 0; } /* -------------------------------------------------------------------- */
itoa の使い方説明終わり。
んでこれを最適化してみます。
まず文字に変換する処理は遅くなるので消します
消した関数が以下の char *search_3( const int num )です
http://codepad.org/2epZT4W8
#define TRUE 1 #define FALSE 0 char *search_3( const int num ) { int tmp; for(tmp=num;tmp>0;tmp /= 10) if( tmp%10 == 3 ) return TRUE; return FALSE; } int main() { int aho; for(aho=1; aho<50; aho++){ if( aho%3==0 || aho%5==0 || search_3(aho) ) printf("%d\n",aho); } return 0; }
他のitoa はどんなのだろう...
- Base = 10 のとき 10 余り出して 10 で割っていっている系
ライセンス不明 よい
16進のときにつぶしが利かない
X/OPEN 文字テーブル使用
GPL さすがGPL これはひどい
switch内 case〜break文 #defineしてる....
もっと素直にかけないものか...
GPL さすがGPL 問題外...
swapの仕方は悪くない
char s[]、char *sなら暗示的に \0 と考えていいと思うので
番人付けてstrlen(s)いらんはずだが...
- こちらは逆に、大きい桁から判定して行っている
GPL 桁数決め打ち(__int32や __int64なんて高々 4294967295や
9223372036854775807 なんだし、決め打ちでいいな..)
というわけで作成
/* keta_v2 */ int map_keta[] = { 0, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, /* 4294967295 */ 10000000000, 100000000000, 1000000000000, 10000000000000, 100000000000000, 1000000000000000, 10000000000000000, 100000000000000000, 1000000000000000000, /* 9223372036854775807 */ -1, }; int keta_v1( const int num ) { int tmp, n = 0; for(tmp=num;tmp>0;tmp /= 10) n++; return n; } int keta_v2( const int num ) { int tmp, n = 0; for(n=0;map_keta[n] != -1;n++) if(map_keta[n] > num) break; return n; } int main() { int i; for(i=0; i<50; i++) printf("%d: %d\n",i*i*i , keta_v2(i*i*i)); return 0; }
> time keta_v1.c
0.000u 0.006s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
> time keta_v2.c
0.000u 0.003s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
桁計算ルーチンが50% 速くなったコトがわかる
const int map_keta[] = { 3, 30, 300, 3000, 30000, 300000, 3000000, 30000000, 300000000, 3000000000, /* 4294967295 */ -1, }; int search_3_v1( const int num ) { int tmp, n = 0; for(tmp=num;tmp>0; tmp /= 10) { if( tmp % 10 == 3 ) return num; } return 0; } /* 1 〜 29 までは 一桁目しか見ない版 */ int search_3_v2( const int num ) { int tmp, n = 0; for(n=0, tmp=num;map_keta[n] != -1 || tmp>0;n++, tmp /= 10) { if(map_keta[n] > num) break; /* printf( "\t%d = %d = %d\n", num , map_keta[n], tmp % 10) ;*/ if( tmp % 10 == 3 ) return num; } return 0; } int main() { int i; for(i=0; i<50; i++) printf("%d: %d\n",i , search_3_v2(i)); return 0; }
- 0〜49
> time ./search_3_v1
0.000u 0.006s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
> time ./search_3_v2
0.000u 0.006s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
- 0〜4999
> time ./search_3_v1
0.084u 0.124s 0:00.24 83.3% 6+3014k 0+0io 0pf+0w
> time ./search_3_v2
0.084u 0.110s 0:00.22 86.3% 6+2974k 0+0io 0pf+0w
4999回ループならsearch_3_v2 の方が2秒程度速い
3 < A
13
23
30
31
32
33
34
35
36
37
38
39
43
53
63
73
83
93 < B
103 < 1A
113
123
130
131
132
133
134
135
136
137
138
139
143
153
163
173
183
193 < 1B
203 < 2A
213
:
283
293 < 2B
300 < 3X
:
399 < 3X
403 < 4A
413
:
483
493 < 4B
403 < 4A
413
:
483
493 < 4B
503 < 5A
513
:
583
593 < 5B
603 < 6A
613
:
683
693 < 6B
703 < 6A
713
:
783
793 < 7B
803 < 7A
813
:
883
893 < 8B
903 < 9A
913
:
983
993 < 9B
1003 < 10A
:
1093 < 10B
1,2桁目が A〜Bパターン以外の数値で3が憑くのは
387
1307
2309...
しかし、3, 13, 23, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 43, 53, 63, 73, 83, 93,のいづれかがかかる。
int map_3[] = { 3, 13, 23, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 43, 53, 63, 73, 83, 93, 0}; int search_3_v3( const int num ) { int tmp, n = 0; for(tmp=num;tmp>0; tmp /= 100) { for(n=0;;n++) { if(map_3[n] == 0) break; if(map_3[n] == tmp % 100) return num; // printf( "\t%d = %d = %d\n", num , map_3[n], tmp % 100); } } return 0; } int main() { int i; for(i=0; i<5000; i++) printf("%d: %d\n",i , search_3_v3(i)); return 0; }
- 0〜4999
> time ./search_3_v1
0.084u 0.124s 0:00.24 83.3% 6+3014k 0+0io 0pf+0w
> time ./search_3_v2
0.084u 0.110s 0:00.22 86.3% 6+2974k 0+0io 0pf+0w
> time ./search_3_v3
0.085u 0.106s 0:00.22 81.8% 6+2826k 0+0io 0pf+0w
v2 よりも 4ミリ秒速くなった。
この場合 v1の派生だから、v1 と比べるベきだが
> ./1 > 1out.txt
> ./2 > 2out.txt
> mv a.out 3
> ./3 >3out.txt
> diff 1out.txt 2out.txt
> diff 3out.txt 2out.txt
v2とv3の対策をくっつけた v4
const int map_keta[] = { 3, 30, 300, 3000, 30000, 300000, 3000000, 30000000, 300000000, 3000000000, /* 4294967295 */ -1, }; int map_3[] = { 3, 13, 23, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 43, 53, 63, 73, 83, 93, 0 }; int search_3_v4( const int num ) { int tmp, n, m; for(n=0, tmp=num;map_keta[n] != -1 || tmp>0;n++, tmp /= 100) { if(map_keta[n] > num) break; /* printf( "\t%d = %d = %d\n", num , map_keta[n], tmp % 100) ;*/ for(m=0;;m++) { if(map_3[m] == 0) break; if(map_3[m] == tmp % 100) return num; // printf( "\t%d = %d = %d\n", num , map_3[m], tmp % 100); } } return 0; } int main() { int i; for(i=0; i<5000; i++) printf("%d: %d\n",i , search_3_v4(i)); return 0; }
- 0〜4999
> time ./search_3_v1
0.084u 0.124s 0:00.24 83.3% 6+3014k 0+0io 0pf+0w
> time ./search_3_v2
0.084u 0.110s 0:00.22 86.3% 6+2974k 0+0io 0pf+0w
> time ./search_3_v3
0.085u 0.106s 0:00.22 81.8% 6+2826k 0+0io 0pf+0w
> time ./search_3_v4
0.059u 0.131s 0:00.21 85.7% 22+3019k 0+0io 0pf+0w
1秒速くなった気がする
オチ
> time ./search_3_v1 > /dev/null 0.000u 0.005s 0:00.00 0.0% 0+0k 0+0io 0pf+0w > time ./search_3_v2 > /dev/null 0.000u 0.005s 0:00.00 0.0% 0+0k 0+0io 0pf+0w > time ./search_3_v3 > /dev/null 0.000u 0.004s 0:00.00 0.0% 0+0k 0+0io 0pf+0w > time ./search_3_v4 > /dev/null 0.000u 0.006s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
printしなければ速い
ps: table[2]が3になってたの修正、tmp , tmp%10 ウォッチ式追加。 インデント修正
自分なりに頑張ました
http://q.hatena.ne.jp/1207585413 の問題
http://codepad.org/8BD5WPWo
#!/usr/bin/perl $_ = "ワン ワワンワ ンンワ ンワ ンワ ンワン ワンワ ンワ ワン ワンワ ンワンワンンワン ンワ ンワ ンンンワンワンワンワンワ ワン ワン ワンンンワン ワン ワン ンワ ンワ ンワン ワン ワン ワン ワン ワンワ ンワ ンワン ワン ンワ ンワ ンワ ンワン ワン ワン ワン ワン ワワワン ワン ンワ ンワ ンワ ンワンワ ンワ ワン ワ ンワ ンワンワン ワン ン ワン ワン ワン ワンワ ワ ワン ワン ワン ワンワワワン ンワン ワ ンワン ワ ンワ ワゥゥン ンワ ンワ ワンワ ワウゥゥン ワン ンワンワ ンワ ンワ ";$a=(s/ワワン//g);$b=(s/ンワ//g);$b/=$a*$a;s/ //g; split(/\n/,$_); print ((/$a/||$_%$a==0||$_%$b==0)?"$_[$_%$b], ":"$_, ") for(1..100);
> perl test.pl
1, 2, ンン, 4, ワンワン, ンワ, 7, 8, ワンワンワンンンワンワン, ワンワン, 11, ワンワンン,
ンン, 14, ワンワン, 16, 17, ンン, 19, ワンワン, ンワ, 22, ンン, ワンワンワンンンワンワン,
ワンワン, 26, ワンワンン, 28, 29, ワンワン, ンワ, ワンワンン, ンン, ワンワンワンンンワンワ
ン, ワンワン, ンワ, ワンワンン, ンン, ワンワンワンンンワンワン, ワンワン, 41, ワンワンン,
ンン, 44, ワンワン, 46, 47, ンン, 49, ワンワン, ンワ, 52, ンン, ワンワンワンンンワンワン,
ワンワン, 56, ワンワンン, 58, 59, ワンワン, 61, 62, ンン, 64, ワンワン, ンワ, 67, 68, ワン
ワンワンンンワンワン, ワンワン, 71, ワンワンン, ンン, 74, ワンワン, 76, 77, ンン, 79, ワン
ワン, ンワ, 82, ンン, ワンワンワンンンワンワン, ワンワン, 86, ワンワンン, 88, 89, ワンワン
, 91, 92, ンン, 94, ワンワン, ンワ, 97, 98, ワンワンワンンンワンワン, ワンワン, >
perl -le 'do{ print if(/3/||$_%3==0||$_%5==0) } for(1..49);'のかいせつ
perl -le 'do{ print if(/3/||$_%3==0||$_%5==0) } for(1..49);'
for 1 〜 49でくるやつは、指定がない場合 $_に代入される。
そいつ自体は文字でも数値でもありえる
$_=~ /3/ みたいに正規表現でマッチさせる場合は、暗示的に変換されるので
strへの変換 itoa やsprintfはいらない
そして正規表現の場合 $_= ~ は暗示的に指定されるのでいらない
$_%3==0
こういうばあいは数値として扱われる。
print $_
をしているが
このばあい $_ は省略できる
perl -le で改行付き出力
明示すると
do{ print "$_" . "\n" # perl -l オプション if( $_ =~ m/3/ || # - 3 を含むか? 正規表現マッチング $_ % 3 == 0 || # - 3 の倍数 $_ % 5 == 0 ); # - 5 の倍数 } for my $_ (1..49);