- プログラミングのお題スレ Part3
368 ：デフォルトの名無しさん[sage]：2014/03/20(木) 00:19:53.82 ID:v5V8kLPf - Cゲンガーの逆襲II！！
興味のあるベンチマークを作ってみよう。
なんでもいいです。コンピュータをイジメる欲望にしたがってベンチマークを作ってみましょう。
ベンチマークといったらタライ=竹内関数とかアッカーマン関数とかが有名ですが、
気が向いたら創作してみるのもいいじゃないですか。
貴方は何をつくりますか？
*見どころ。*
・速度向き極最適化後に重いほど良い。
・コーディングで手を抜いたら減点。
・なるべく読めるコードにしましょう。
発表時には、アルゴリズムについて一言ください。
*エラトステネスの篩ベンチ。*
5000個生成して更に最後に生成した数字から更に+50000プラスした数字の次の素数を求めた。
キャパシティは64bit整数です。それするとメモリもソレくらい必要になりますが。
追記型エラトステネスの篩を設計してみました。
作った後これクラス化できるナーと思ったけどヤってないです。
ttp://ideone.com/AtMDRS
ウチのPCでは15秒ほどかかります。
|
- プログラミングのお題スレ Part3
369 ：デフォルトの名無しさん[sage]：2014/03/20(木) 00:27:35.69 ID:v5V8kLPf - あー、同時にバグ情報なども募集中です。
|
- プログラミングのお題スレ Part3
371 ：デフォルトの名無しさん[sage]：2014/03/20(木) 01:03:59.14 ID:v5V8kLPf - >>370
ソレはideonさんが良いPC使ってるからだよ。数字上げればもっと重くなるよ。
ゾロ目なのはたまたまでいい数字だと思うよ。
10000万個生成した後100000万まで生成してみたらIdeonさんがランタイムエラー吐いたので減らしたんだよ。
多分出力が多すぎたんだ。
で、どれくらい重いといいと思う？
|
- プログラミングのお題スレ Part3
373 ：デフォルトの名無しさん[sage]：2014/03/20(木) 01:08:35.85 ID:v5V8kLPf - っていうか>>370もナイスなベンチマークつくろう。（提案
|
- プログラミングのお題スレ Part3
374 ：デフォルトの名無しさん[sage]：2014/03/20(木) 01:11:55.45 ID:v5V8kLPf - >>372
なかなかいいPC使ってるね。俺も良いPCほしいよ。
これ、どっちかって言うと処理も食うけど単純にメモリもガッツリ食うんだよね。
規模を大きくするとボトルネックになるのはどっちかって言うとメモリ量。
ちなみに、大きな素数はお金になるよ。数学的知見がいるけど。
|
- プログラミングのお題スレ Part3
375 ：デフォルトの名無しさん[sage]：2014/03/20(木) 01:13:36.17 ID:v5V8kLPf - さて、測るのはイイ。秤をつくろう。
|
- プログラミングのお題スレ Part3
378 ：デフォルトの名無しさん[sage]：2014/03/20(木) 01:26:32.48 ID:v5V8kLPf - >>376
いや、俺はもうベンチ作ったから、あんた作ってよ。www
普通に重み付き経路問題で再帰処理をループに置き換えれば大きな迷路もイケルと思うよ。
ただ、普通の重みなし経路問題でも2000*2000位のやつをペインターアルゴリズムで解くと結構重いよ。
C#でランダム重みなし迷路作ってMSペイントに解かせた事あるんだよ。
普通にフリーズしたわ。
|
- プログラミングのお題スレ Part3
380 ：デフォルトの名無しさん[sage]：2014/03/20(木) 01:32:17.58 ID:v5V8kLPf - >>377
おぉいいね。最新構成じゃない。
俺もスカイレークが出たら変えようと思っている。
来年の話なのでまだ我慢！
|
- プログラミングのお題スレ Part3
381 ：デフォルトの名無しさん[sage]：2014/03/20(木) 01:40:41.49 ID:v5V8kLPf - >>379
設計の要点として、通ったところを壁にする。ッて言うことかな。
壁はビットで持っておくと1変数に4枚入るよ。
ちなみにこれ全通り試行しないと答えでないタイプじゃないの？
|
- プログラミングのお題スレ Part3
382 ：デフォルトの名無しさん[sage]：2014/03/20(木) 01:49:52.20 ID:v5V8kLPf - 暇だから作ってみるか。期待すんなよ〜。
データ入力するのメンドクサ。
|
- プログラミングのお題スレ Part3
384 ：デフォルトの名無しさん[sage]：2014/03/20(木) 03:28:13.56 ID:v5V8kLPf - データ入力終わらん。何地獄だこれ。
うわわーん。
|
- プログラミングのお題スレ Part3
385 ：デフォルトの名無しさん[sage]：2014/03/20(木) 05:15:19.29 ID:v5V8kLPf - ttp://ideone.com/EEPhtH
データ入力して力尽きた。
これよく考えたら巡回セールスマン問題ライクなやつじゃねーか。
そりゃベンチになるけど、俺のターンは終わってるよ〜。
後は再帰的に解いてくだけなんだけど、再帰関数では足りないのでループで書かないとダメだな。
とにかく、データ入力は脳弱になるー。
この前の畳をヒントにすれば速度は出るかなーと思うけど、メモリが馬鹿にならん。
明日、覚えてたら続きやる。
|
- プログラミングのお題スレ Part3
387 ：デフォルトの名無しさん[sage]：2014/03/20(木) 06:54:02.18 ID:v5V8kLPf - >>386
え？まじで？素数間違ってる？
エラトステネスの篩って、低い方の素数で整数を割ってくんだよね。
あれ？
|
- プログラミングのお題スレ Part3
388 ：デフォルトの名無しさん[sage]：2014/03/20(木) 07:18:25.44 ID:v5V8kLPf - >>383
ギブアップ。素直に、経路問題的手法で解こうと思ったんだが。
ttp://ideone.com/pVs5KO
エラトステネスの篩じゃないって言われて思考全部吹き飛んだ。www
エラトステネスの篩については、
完全なアルゴリズムだからここ数年考察していて最近納得行くコードがかけるようになったんだ。
それ否定されちゃったら結構大変だ。どこがバグってるか是非聞きたい。
|
- プログラミングのお題スレ Part3
389 ：デフォルトの名無しさん[sage]：2014/03/20(木) 07:29:06.60 ID:v5V8kLPf - >>371
あー、この発言バグってる・・・。
10000万じゃなくて、1万。100000万じゃなくて10万。
うほぉおおおお。ごめんなさい。
|
- プログラミングのお題スレ Part3
391 ：デフォルトの名無しさん[sage]：2014/03/20(木) 12:48:27.08 ID:v5V8kLPf - >>390
エラトステネスの篩は簡単だよ〜。
数字の半分までの素数を判別すればいいからマルチスレッド化も可能。同期機構いるけどね。
メモ化すればメモリ食うけど超高速になる。高強度暗号創造して君も大金持ちだ。
しかし、中学や高校からC言語できるとはいい環境ですなー。しかも機材が素晴らしい。
自分の時はBASICだったもん。しかもコンピュータクラブ入らないと扱えなかった。
C言語は専門行ってから覚えたし、ひたすら模写して覚えたもんだ。（遠い目
最初ポケコンでプログラム覚えたから、1ソース200行以上扱えないんだよね俺。
ローテクすぎる。
俺マルチスレッドプログラミングってできないんだよね。
C++標準化待ちしてる間にドンドン時代遅れになってくわ。
君、結構ハイスペックだな。
|
- プログラミングのお題スレ Part3
392 ：デフォルトの名無しさん[sage]：2014/03/20(木) 12:56:56.09 ID:v5V8kLPf - とりあえず>>386の召喚待ち。
結局、どういう意味だったのかわからなくて寝てないんだよ。
さすがにそろそろ辛くなってきた。むはぁ〜。
|
- プログラミングのお題スレ Part3
394 ：デフォルトの名無しさん[sage]：2014/03/20(木) 13:48:55.18 ID:v5V8kLPf - >>393
おっさん流小言。。。
newするのやめよう。配列構造はvector、ツリー構造はset一族、list構造はlist一族をつかおう。これらはコンテナという。
<limits>のstd::numeric_limitsを使おう。C++標準定義の定数が得られる。
<cstdint>を使おうintはstd:::int32_t、unsigned intはstd::uint32_tを使おう。C/C++を使うからにはメモリのサイズも目を配ろう。
時間関係は<chrono>にお任せ。時計も取れます。
これらは標準なのでソース互換性が向上するよ。
C++は大きく行ってC++98、C++03、C++11、C++14、C++17。という規格があって大きな機能もそれに準じる。今はC++11が主流でC++14が準備中。未来では更に増えるだろう。
逆にSqrtMaxNumberはイイ最適化だね。ただ、!=だと切りの悪い数字で止まらなくなることがあるかも知れない。
大なり記号で制御したほうが安心。C++は生配列だとなかなかオーバーランで例外吐いて落ちるってことが無いからね。
コンテナだと違うんだけどね。
と、言うわけで今思いついた小言でした。
|
- プログラミングのお題スレ Part3
395 ：デフォルトの名無しさん[sage]：2014/03/20(木) 13:51:14.26 ID:v5V8kLPf - >>393
そだそだ。結構良いタイム出してるな。
俺もPC変えたい！Core2DuoE8500だよ。。。
|
- プログラミングのお題スレ Part3
396 ：デフォルトの名無しさん[sage]：2014/03/20(木) 14:17:34.39 ID:v5V8kLPf - *エラトステネスベンチ ver 0.3α*
ttp://ideone.com/0WsxkP
バージョンアーップ。
>>393の最適化をパクってみたら10倍位早くなった。吹いたわ。
ソレにともなって試験値を向上。
N200000まで生成後100000個追加で生成するように順番を入れ替えた。
これで改良まえと同じくらいの負荷になった。
あと、無意味にstd::map使ってたのをstd::setに差し替え。これは無知だった。
こういうことって有るんだねー。
|
- プログラミングのお題スレ Part3
402 ：デフォルトの名無しさん[sage]：2014/03/20(木) 22:06:56.25 ID:v5V8kLPf - おはよう。
>>397
何が違うのかワカラナイです。Orz
>>399
暗号とか知っとくとお金になるかもよ。RSAとかあのへん。
まぁ、完全なアルゴリズムだからね。簡単だし。
>>400
コンテナのほうが安全。
C言語系はバグでコンピュータをハード的にぶち壊せる言語なので一応気をつけるのだ。
まぁ、ハード的にぶち壊すのも結構大変だけどね。メモリ書き換えでOSの挙動変わることは結構あるよ。
|
- プログラミングのお題スレ Part3
404 ：デフォルトの名無しさん[sage]：2014/03/20(木) 23:12:28.61 ID:v5V8kLPf - >>403
ただの夜型人間だよ。昨日はたまたま昼も起きてたんだ。
うーん。わからん。Orz
ちとネット見てくる。
|
- プログラミングのお題スレ Part3
405 ：デフォルトの名無しさん[sage]：2014/03/20(木) 23:18:49.75 ID:v5V8kLPf - ウィキペディア見て分かった。
試し割り方は、素数を持つことが真で、
エラトステネスの篩は素数じゃない方を重視するのが真なんだな。
たぶん。
勘違いしてた。どっちもエラトステネスの篩の括りだとおもってたけど、名前ついてたとは。
エラトステネスのほうはまともなbitvectorあれば超高速だな。
追記型にするのはちと面倒だけども。
寝足りなくて頭回らん。。。Orz
|