プログラミング初学者の基礎的疑問

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
おもちんこ
記事: 6
登録日時: 5年前

プログラミング初学者の基礎的疑問

#1

投稿記事 by おもちんこ » 5年前

プログラミングにおいて、効率の悪さは致命的だといいますが、どの程度の効率の悪さなら許されるのかが初学者ゆえに、いまいちピンときません。
機能すればそれでいいって感じでも最初のころはいいのでしょうか?

誰か詳しいお方無知なわたくしに教えをください。

コード:

#include <iostream>
#include<ctime>
#include<cstdlib>
using namespace std;
int main(void) {
	srand(time(NULL));//乱数発生

	const int j =3000;
	int num[j] = { 0 };

	for (int i = 0; i < j; i++) {
		if(!i)
			num[i] = rand() % j + 1;
		else {
			int n;//n定義
			do {
				n = 0;//n初期化
				num[i] = rand() % j + 1;
				for (int k = 0; k < i; k++) {
					if (num[k] == num[i])
						n = 1;
				}
			} while (n);
		}
		cout << num[i] << "\n";
	}
}
こちらの1~定数jまでの数値をかぶらないように配列に格納して表示するプログラム…なんかどことなく効率が悪いように感じられます…一応機能します。

かずま

Re: プログラミング初学者の基礎的疑問

#2

投稿記事 by かずま » 5年前

i が 0 の場合を、特別扱いしたいのなら、

コード:

    num[0] = rand() % j + 1;
	for (int i = 1; i < j; i++) {
		int n;//n定義
		do {
			n = 0;//n初期化
			num[i] = rand() % j + 1;
			for (int k = 0; k < i; k++) {
				if (num[k] == num[i])
					n = 1;
			}
		} while (n);
	}
としたほうが良いでしょう。元のままだと、i が 0 か
どうかのチェックを 3000回実行することになります。

もっと問題なのが、1~3000 の値を乱数で生成し、それが既に
存在するかどうかを毎回チェックしていることです。

既に 2999個の値が確定しているとき、残り 1個の値は1通り
しかありません。それなのに 3000通りの値を乱数で生成すると
既に存在するものにぶつからない確率は 1/3000。

既に 2998個の値が確定しているとき、残り 2個の値は2通り
しかありません。それなのに 3000通りの値を乱数で生成すると
既に存在するものにぶつからない確率は 2/3000。

試しにデータの個数を 3万個にしてみてください。
表示していると時間の計測ができなので、
出力はファイルにリダイレクトするとして、
何秒かかりますか?

改善案として、次のようなやり方を考えましょう。

コード:

#include <iostream>  // cout
#include <ctime>     // time
#include <cstdlib>   // srand, rand
using namespace std;

int main()
{
	srand(time(NULL));
	const int n = 20;
	int num[n];
	for (int i = 0; i < n; i++) num[i]= i + 1;
	for (int i = 0; i < n; i++) {
		int j = rand() % n, t = num[i];
		num[i] = num[j], num[j] = t;
	}
	for (int i = 0; i < n; i++) cout << num[i] << '\n';
}
また、こんなやり方もあります。

コード:

#include <iostream>  // cout
#include <ctime>     // time
#include <cstdlib>   // srand, rand
using namespace std;

int main()
{
	srand(time(NULL));
	const int n = 20;
	int num[n];
	for (int i = 0; i < n; i++) num[i]= i + 1;
	for (int i = n; i > 0; ) {
		int j = rand() % i, t = num[--i];
		num[i] = num[j], num[j] = t;
	}
	for (int i = 0; i < n; i++) cout << num[i] << '\n';
}
それぞれ、どういうことをやっているか説明できますか?

かずま

Re: プログラミング初学者の基礎的疑問

#3

投稿記事 by かずま » 5年前

const int n = 20; としましたが、
これは 3000 や 30000 に置き換えてください。

アバター
usao
記事: 1887
登録日時: 10年前

Re: プログラミング初学者の基礎的疑問

#4

投稿記事 by usao » 5年前

オフトピック
どこまで許されるか……なる問いに関しては,「場の条件による」としか言えないのでは.
(「場」に自分しかいないならば
あからさまに無意味に効率の悪いコード書いたって,それを許すかどうかは自分次第だろうし.)

逆に(?) 効率を求める行為(に要するコスト)がどこまで許されるのか,というのもある.

おもちんこ
記事: 6
登録日時: 5年前

Re: プログラミング初学者の基礎的疑問

#5

投稿記事 by おもちんこ » 5年前

すげぇわかりやすい説明でした!
なるほど!配列にぶちこんでからそれをランダムに組み替えるという発想は、わかなかったです。
私のやつだと、最後になるほど表示が遅くなるのに対し、こちらは最後までスムーズでした。

回答ありがとうございました。
質問してよかったです。

おもちんこ
記事: 6
登録日時: 5年前

Re: プログラミング初学者の基礎的疑問

#6

投稿記事 by おもちんこ » 5年前

できるだけ、効率の良いプログラミングができるように精進していきます!

ISLe
記事: 2650
登録日時: 13年前
連絡を取る:

Re: プログラミング初学者の基礎的疑問

#7

投稿記事 by ISLe » 5年前

オフトピック
かなり昔の話だけれど、ガラケー用のゲームで、20体程度のエネミーの群れから3体を選んで隊列を作るという処理があった。
iアプリ版では、3体すべて全体からランダムに選出していたが特に問題はなかったものを、そのまま別のケータイに移植したところ、ウォッチドックに引っ掛かって端末に強制リセットが掛かるという致命的な不具合が発生した。

たまたま知っていたから、すぐに原因を見つけて修正できたけれど、知らなかったらその機種でのリリースは延期や中止にもなりかねなかった。


今回の質問の内容は頻出で、こういう質問掲示板を巡回していればたびたび目にして、使う機会がなくてもなんとなく覚えてしまう。
質問があるときだけ掲示板にくるひととか、掲示板にきても関係なさそうなトピは見ないというひとにとっては、頻出ではないので、とっさの対応力には大きな差が生まれる。

「効率の良いプログラミングができる」ということと「効率の良いプログラミングができる方法を効率よく見つける」ということとは相反する、というか「効率よく見つける」ということは一足飛びにはできない。
http://labaq.com/archives/51206672.html

おもちんこ
記事: 6
登録日時: 5年前

Re: プログラミング初学者の基礎的疑問

#8

投稿記事 by おもちんこ » 5年前

貪欲に技術を取り込んでいく姿勢をこれからのプログラミングライフにおいて、忘れないようにします!

ためになる情報ありがとうございました!

アバター
usao
記事: 1887
登録日時: 10年前

Re: プログラミング初学者の基礎的疑問

#9

投稿記事 by usao » 5年前

オフトピック
> 機能すればそれでいいって感じでも最初のころはいいのでしょうか?

文面からは,これ↑が主たる質問内容に見えたのだけど,違ったようですね.

おもちんこ
記事: 6
登録日時: 5年前

Re: プログラミング初学者の基礎的疑問

#10

投稿記事 by おもちんこ » 5年前

そっちが確かにメインだったのですが、まぁ何となく解決したのでおKです!

ISLe
記事: 2650
登録日時: 13年前
連絡を取る:

Re: プログラミング初学者の基礎的疑問

#11

投稿記事 by ISLe » 5年前

いまはインターネットを使って膨大な情報にリーチ可能です。
「知っている」ことと「できる」ことは乖離が進み、「知っているけどできない」ことはどんどん増えていくでしょう。
でも「知っている」ことは強みです。
それだけで、いまはできなくても将来の備えになります。

とは言え、やみくもに膨大な情報に触れるだけで良し悪しを判断できなければ選択できません。


>機能すればそれでいいって感じでも最初のころはいいのでしょうか?
学ぶ上では、むしろ効率の悪いコードに触れることは貴重な体験となるでしょう。

>こちらの1~定数jまでの数値をかぶらないように配列に格納して表示するプログラム…なんかどことなく効率が悪いように感じられます…一応機能します。
まず第一に、「どことなく効率が悪い」を「どこがどう効率が悪い」とはっきりできるようになることが基礎となります。

たまたま効率の良いコードから勉強を始めて、どうして効率が良いか分からないままもよくない。
コード自体の効率の良し悪しに関係なく、目の前のコードから学べることはたくさんあるはず。
そういう意味では、最初のころに、機能すればそれでいいとなるのは必然。
オフトピック
リアルで他のプログラマのひとと話していてスタンスに関する齟齬をしばしば感じます。
他のひとはほとんど、自分が効率の良いコードを書けるようになりたいと考えているのに対し、わたしは、わたしがコードを書く必然性はないと考えます。

おもちんこ
記事: 6
登録日時: 5年前

Re: プログラミング初学者の基礎的疑問

#12

投稿記事 by おもちんこ » 5年前

自分でまず考えることを放棄しないようにします!
貴重な返信ありがとうございます。

返信

“C言語何でも質問掲示板” へ戻る