どちらがより良い配列の最大値を求めるアルゴリズムでしょうか？

Question

###はじめに
配列の中の最大値を求めるアルゴリズムについて質問します．
そのアルゴリズムについて友人と議論になり，客観的意見が欲しくて質問しました.

###サンプルコード

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <time.h>
#include <limits.h>

bool putMaxVal1(int array[],int size){
  if(size<=0){ return false; }
  int maxVal=array[0];
  int i;
  for(i=1; i<size; i++){
    if(array[i]>maxVal) maxVal=array[i];
  }
  printf("maxVal1 = %d\n",maxVal);
  return true;
}

bool putMaxVal2(int array[],int size){
  if(size<=0){ return false; }
  int maxVal=INT_MIN ;
  int i;
  for(i=0; i<size; i++){
    if(array[i]>maxVal) maxVal=array[i];
  }
  printf("maxVal2 = %d\n",maxVal);
  return true;
}

int main(void){
  int array[100]={0};
  
  srand(time(NULL));
  int i;
  for(i=0; i<sizeof array/sizeof array[0]; i++){
    array[i]=1+rand()%1000;
    printf("[%3d]  %3d\n",i+1,array[i]);
  }
  printf("maxVal1:%s\n",putMaxVal1(array,sizeof array/sizeof array[0])?"TRUE":"FALSE");
  printf("maxVal2:%s\n",putMaxVal2(array,sizeof array/sizeof array[0])?"TRUE":"FALSE");

  printf("maxVal1:%s\n",putMaxVal1(array,-1)?"TRUE":"FALSE");
  printf("maxVal2:%s\n",putMaxVal2(array,-1)?"TRUE":"FALSE");
  
  return 0;
}

###質問
0. 二つの関数(maxVal1 と maxVal2)のどちらのうがいいでしょうか．

質問内容を変更す．

「どちらを推奨しますか？」「どちらのほうが個人的に好きですか？」

2.引数sizeに-1を入れたところ二つの関数には以下のような違いが見られましたが，これは処理系によって違うのでしょうか．

maxVal1 = 984
maxVal2 = -2147483648

###補足など
質問について：
「いいでしょうか」という質問が不適切であるという指摘をいただいた為,「推奨しますか？」，「どちらのコードのほうが好きですか？」という質問に変更します．

コードについて：コードを修正しました．修正前コードは以下の通りです．

/*このコードは修正前のものです．*/
/*このコードは修正前のものです．*/
/*このコードは修正前のものです．*/
/*このコードは修正前のものです．*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>

int maxVal1(int array[],int size){
  int maxVal;
  int i;
  for(i=0; i<size; i++){
    if(0==i) maxVal=array[0];
    if(array[i]>maxVal) maxVal=array[i];
  }
  printf("maxVal1 = %d\n",maxVal);
  return maxVal;
}

int maxVal2(int array[],int size){
  int maxVal=INT_MIN ;
  int i;
  for(i=0; i<size; i++){
    if(array[i]>maxVal) maxVal=array[i];
  }
  printf("maxVal2 = %d\n",maxVal);
  return maxVal;
}

int main(void){
  int array[100]={0};
  
  srand(time(NULL));
  int i;
  for(i=0; i<sizeof array/sizeof array[0]; i++){
    array[i]=1+rand()%1000;
    printf("[%3d]  %3d\n",i+1,array[i]);
  }
  maxVal1(array,sizeof array/sizeof array[0]);
  maxVal2(array,sizeof array/sizeof array[0]);
  
  return 0;
}

Answer 1

質問1ですが、整数や浮動小数点数のように最小値がわかりきっているものについては、それを入れておくことで判定条件を簡略化する、番兵と呼ばれる技があります。

ただ、自分だったら、まずmax = array[0];として、ループを1から回す、という手段を取ると思います。

質問2ですが、どちらもループは1度も実行されません。maxVal2では最初に代入したINT_MINがそのまま帰りますが、maxVal1では初期化していない変数をそのまま返そうとして、厳密には「未定義の動作」となります（多くの処理系では、もとからメモリに入っていた何かしらの値が返ってくることになるでしょう）。

Answer 2

質問2については、maisumakunさんの回答が申し分ないので、思ったところがある質問1についてのみ書きます。

二つの関数(maxVal1 と maxVal2)のどちらのほうがいいでしょうか.

とのことですが、｢よい｣とはどういうことでしょうか。コードの分かりやすさですか? 実行速度ですか? 想定外の入力への安全性ですか? …
というように、「よい」と言っても、様々な基準があるので、単純には答えられないのが事実です。ただ、それだけでは何のアドバイスにもならないので、個人的にこれらの視点からどう評価するか、その理由を説明します。

分かりやすさ：ほぼ同じ
1.のほうは、0を特別扱いしていますが、理由は自明なので特に分かりにくいとは思いません。
速度：1.<=2.
最近のコンパイラなら、ループに関しては最適化で全く同じコードになる可能性が高いですが、1.は0との比較が挟まりうる分だけ、遅くなる可能性もあります。
安全性：1.<2.
不適切な入力時に、2.であれば決まった値が帰るのでエラーチェックにも使えますが、1.の場合は全く分かりません。
拡張性：1.>2.
今回は最小値があるint型でしたが、最小値が存在しない文字列型には2.のロジックは使えないですよね?

とまあ、こんな感じです。個人的には2.を推します。

Comments

[majiponi]

修正後の質問への回答としては、どのようなデータ型にも用いることができる1のほうを勧めたいです。他の条件が同じなので。

Answer 3

アルゴリズムというよりかは、変数(maxVal)の初期化はどのタイミングでやるのが良いかという感じですね。
どちらかと言えば2の方が好みです。
ループの外に書けるコードはなるべくループから出した方が、そのループの処理で何をしたいのかが明確になります。
質問2は、maisumakunさんの回答通りですね。
どちらの処理もループを回らないので、1の方は変数を初期化していないので不定値、2の方はINT_MINが返ります。
それからこの質問の場合、引数sizeが0以下の場合の仕様が曖昧なので、そこがきっちり決まっていればまた違うコードになるのではないでしょうか。

Comments

[maisumakun]

「自動記憶域期間のオブジェクトの値が不定の時に使用された場合」、不定の値が返るだけではすまないかもしれません（いわゆる「未定義の動作」です）。

https://www.jpcert.or.jp/sc-rules/c-exp33-c.html

最適化をかけた場合、「未定義な動作」をしたコードパスについて「そこは通らない」とみなして最適化してしまってもかまわないので、とんでもない動作になることがあります。

[ttyp03]

最適化の例は知らなかったので助かります。
でもまあ、対初心者なので小難しい話よりかは、想定していない値が返るコードは良くないよ、程度の話でいいと思いますけどね。

Answer 4

私だったら、こう書きます。

// #define NDEBUG
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Cはスネークケース、C++はキャメルケースというオレオレコーディングスタイルに
// 基づき関数名はスネークケースにする。
// 配列のサイズは size_t を使う。符号無しなので負の数にはならない。
int max_val(int *array, size_t size)
{
	// 範囲チェックは assert() を使う。
	// リリース版は NDEBUG を有効にして、チェック分をなくし、高速にする。
	assert(size > 0);
	// 最初の値を max に入れる。
	int max = *array;
	// size - 1 回分ループする。
	// 余計なインデックスの代入や比較が無い分速い。
	while (--size) {
		// 前置インクリメントした後にチェックしていく。
		// array[i] よりもインクリメントの方が速い。
		if (*++array > max)
			max = *array;
	}
	return max;
}

int main(void)
{
	int array[100] = {0};

	srand(time(NULL));
	for (int i = 0; i < sizeof(array) / sizeof(*array); i++) {
		array[i] = 1 + rand() % 1000;
		printf("[%3d]  %3d\n", i + 1, array[i]);
	}
	size_t size = sizeof(array) / sizeof(*array);
	printf("max_val:%d\n", max_val(array, size));
	printf("max_val:%d\n", max_val(array, 0));

	return 0;
}

「良いコード」というのは、基準がたくさんあるため、一概には言えません。上のコードはなるべくは速く、また、簡潔でわかりやすくしたつもりですが、人によっては「while(--size)の意味がわかりにくい、forループの方がいい」とか「最初の値だけ特別視しない方が良い」とか「インデントせずに添字アクセスの方が直感的」とか「assert()無効でsizeが0の時、デクリメントがアンダフローを起こすのはよくない」とか言う場合もあるでしょう。また、アルゴリズムさえ間違っていなければ、コンパイラの最適化によってほぼ同じになってしまう場合もあります。

明らかにアルゴリズムが間違っているというのでなければ、好みの使い方をするのが良いと思います。

【forやwhileが嫌いな人のためのおまけ】

// #define NDEBUG
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int max_val_r(int *array, size_t size, int max)
{
	if (!size)
		return max;
	if (*array > max)
		max = *array;
	return max_val_r(++array, --size, max);
}

int max_val(int *array, size_t size)
{
	assert(size > 0);
	int max = *array;
	return max_val_r(++array, --size, max);
}

int main(void)
{
	int array[100] = {0};

	srand(time(NULL));
	int i;
	for (i = 0; i < sizeof array / sizeof array[0]; i++) {
		array[i] = 1 + rand() % 1000;
		printf("[%3d]  %3d\n", i + 1, array[i]);
	}
	size_t size = sizeof(array) / sizeof(*array);
	printf("max_val:%d\n", max_val(array, size));
	printf("max_val:%d\n", max_val(array, 0));

	return 0;
}

関数型に毒されているとこっちの方がわかりやすいという人もいるとかいないとか。

Answer 5

僕だったら"最大値"ではなく"最大値なのは配列の何番目か"を返すかも。
そうすれば size <= 0 のときにたとえば-1を返すことで"該当なし"を表現できる。

さもなくば"size <= 0 のときの戻り値は不定(or INT_MIN)" と明記する。

Answer 6

「配列の最大値を求める」のが目的ならブーリアンで帰ってくるのはいただけません。
そういう意味では修正前の方が良いです。どうしてもブーリアンで返したいならMaxValを返せるようにポインタの引数を追加した方が良いでしょう。

Comments

[fuzzball]

「配列の最大値を求める関数」とは書いていないので問題ないかと。

[退会済みユーザー]

戻り値が最大値ではないので，関数名を「put・・・」という形にしました．

Answer 7

コード修正前

良い悪いの前に、maxVal1はsize <= 0のときにバグるのでダメ。

コード修正後

1かな。
カッコイイのは2だけど、無駄なコードがあるのは気持ち悪いです。

Answer 8

maxVal1のほうは、1回だけでいい初期化の処理判定をループごとに行っているため、若干効率が悪いです(とは言え優位な差はないでしょうが)。maxVal2の様に最小値で初期化するか、ループに入る前に0番の要素(あれば)で初期化するほうが好みです。