【C言語】最頻値(モード)を求める方法

最頻値の求め方解説ページアイキャッチ

このページでは、C言語で最頻値(モード)を求める方法について解説していきます。

最頻値とは、要は集合の中に最も多く存在する値のことです。今回は、この集合として配列を用いて最頻値を求めていきたいと思います。

例えば下図のような配列の場合、最頻値は 2 となります。

最頻値を求める例

すごく簡単に求められそうにも感じますが、どこまで対応するかによって難易度はかなり異なってきます。例えば最頻値が複数ある場合、そのうちの1つだけ求めれば良いのか、全てを求める必要があるのかでプログラムの難易度は大きく異なります。

最初は簡単なケースから解説していき、どんどん難易度を上げながら様々な最頻値の求め方を解説していきたいと思います。

MEMO

本ページで紹介するソースコードではエラーハンドリング処理を省略しているので注意してください

また、紹介する関数は全て、データの個数が 1 以上であることを前提にしているので、この点にも注意してください

最頻値を1つだけ求める場合

まずは、最頻値を1つだけ求める場合の最頻値の求め方について解説していきます。最頻値が複数ある場合は、その中の1つを最頻値とします。

最頻値を1つ求めれば良いだけなのであれば、実現は割と簡単だと思います。ただ、メモリ使用量や処理速度を考慮すると結構難易度は高くなってきます。

値の出現回数カウント用の配列を用意する

最頻値を求める一番簡単な方法は、値の出現回数カウント用の配列を用意する方法だと思います。

特にデータの集合内の値のとりうる範囲が狭い場合に有効です。

最頻値を求める際の考え方

例えば下記のような配列の場合、配列の中の値は 09 の範囲しかとらないため、値の範囲が狭い配列であると考えられます。

最頻値を求める例

このような場合、配列の中の値を全て網羅できるサイズの配列を別途用意し、その用意した配列の各要素で対応する値の出現回数をカウントしていくことで、全ての値の出現回数を別途用意した配列に格納することができます。

値の出現回数を別の配列でカウントする様子

あとは、出現回数が最大の要素に対応する値を最頻値として選んでやれば、最頻値を求める処理が完了します。

値の出現回数カウント用の配列を用意して最頻値を求める関数例

この方法で最頻値を求める関数は、下記ソースコードにおける getModeData となります。最頻値が複数ある場合、値が小さい方が最頻値として返却されるようになっています。

配列の中の値の範囲が狭い場合の最頻値
#include <stdio.h>
#include <stdlib.h>

int getMaxData(int *data, unsigned int num_data) {

    int max_data = data[0];

    for (int i = 1; i < num_data; i++) {
        if (max_data < data[i]) {
            max_data = data[i];
        }
    }

    return max_data;
}

int getMinData(int *data, unsigned int num_data) {

    int min_data = data[0];

    for (int i = 1; i < num_data; i++) {
        if (min_data > data[i]) {
            min_data = data[i];
        }
    }

    return min_data;
}

int getMaxIndex(int *data, unsigned int num_data) {

    int max_data = data[0];
    int max_index = 0;

    for (int i = 1; i < num_data; i++) {
        if (max_data < data[i]) {
            max_data = data[i];
            max_index = i;
        }
    }

    return max_index;
}

/****************************************
 * 最頻値を求める
 * 
 * data:最頻値を求めるデータの集合
 * num_data:データの集合内のデータの数
 * 
 * 返却値:最頻値
 ****************************************/
int getModeData(int *data, int num_data) {

    /* 取りうる値の範囲を計算 */
    int max_data = getMaxData(data, num_data);
    int min_data = getMinData(data, num_data);
    int num_range = max_data - min_data + 1;

    /* 配列の添字が負の値にならないようにするための調整値 */
    int offset = -min_data;

    /* 各値の出現回数をカウントする配列を作成 */
    int *count = malloc(sizeof(int) * num_range);

    for (int n = 0; n < num_range; n++) {
        /* 出現回数を初期化 */
        count[n] = 0;
    }

    for (int i = 0; i < num_data; i++) {
        /* data[i]の出現回数をカウントアップ */
        count[data[i] + offset]++;
    }

    free(count);

    /* countの中から最大値を持つ要素の添字を取得 */
    int mode_data = getMaxIndex(count, num_range);

    /* 添字から調整値を引いた値が最頻値 */
    return mode_data - offset;

}

int main(void) {

    /* 値の集合を作成 */
    int data[] = {
        1, 2, 3, 2, 5, 4, 3, 2, 1, -10,
        2, 3, 5, 2, 1, 3, 4, 3, 7, 8
    };

    /* 集合のデータ数を取得 */
    unsigned int num_data = sizeof(data) / sizeof(data[0]);

    /* 最頻値を取得して表示 */
    int mode_data = getModeData(data, num_data);
    printf("mode = %d\n", mode_data);

    return 0;
}

ソースコードの解説

いくつかポイントがあるので解説しておきます(最初なので詳しめに解説します)。

まず、最頻値を求める getModeData 以外の関数について説明しておきます。

getMaxData 関数と getMinData 関数はそれぞれ、第1引数で指定された配列の中から最大値および最小値を取得する関数になります(配列のサイズは第2引数で指定)。

最大値と最小値を求める方法については下記ページで解説していますので、これらについてご存知ない方は興味があれば読んでみてください。

C言語における最大値と最小値の求め方の解説ページアイキャッチ【C言語】最大値と最小値を求める方法

また、getMaxIndex 関数は第1引数で指定された配列の中から最大値を持つ要素の添字を取得する関数になります(配列のサイズは第2引数で指定)。

この添字の取得についても下記ページで解説していますので、必要に応じて参照していただければと思います。

C言語での配列の中の最大値を持つ要素の添字を求める方法の解説ページアイキャッチ【C言語】配列の中から最大値を持つ要素の”添字”を求める

さらに、main 関数では sizeof 演算子を用いて配列の要素数の計算を行なっています。

これに関しては下記ページで解説していますので、sizeof 演算子についてや、sizeof 演算子を用いた配列の要素数の求め方について知りたい方は読んでみてください。

C言語のsizeof演算子の解説ページアイキャッチ【C言語】sizeof演算子とは?sizeof演算子を利用するメリットは?

さて、本題の getModeData 関数ですが、この関数ではまず出現回数カウント用の配列を作成するために、出現回数カウント用の配列に必要な要素数の計算を行なっています。data の中の最大値 max_data と最小値 min_data を求め、さらに range_num = max_data - min_data + 1 を計算し、この結果を出現回数カウント用の配列に必要な要素数としています。

あとは、この要素数の配列として扱うためのメモリを malloc 関数により取得しています。この malloc 関数については下記ページで解説していますので、詳しく知りたい方は下記ページをご参照ください。

malloc解説ページのアイキャッチ【C言語】malloc関数(メモリの動的確保)について分かりやすく解説

本当は malloc 関数の返却値が NULL の場合は即座に関数を終了するようにした方が良いのですが、本ページの冒頭でも述べたように今回はエラー処理は省略させていただいています。

この配列(count)さえ作成してやれば、後は data の各要素の値の出現回数を count の各要素でカウントアップしてやれば良いだけです(カウントアップ前に count の全要素を 0 にしておく必要があるので注意してください)。

このカウントアップを行なっているのが下記部分になります。

出現回数のカウントアップ
for (int i = 0; i < num_data; i++) {
    /* data[i]の出現回数をカウントアップ */
    count[data[i] + offset]++;
}

offsetdata における最小値の符号を反転させた値です。この offsetdata[i] に足し合わせることで、data[i] が負の値であっても countに指定する添字が正の値になるようにしています。

offset を利用しているため、count[data[i]]data[i] の出現回数というわけではないので注意してください。count[data[i]]data[i] - offset の値の出現回数になります。

data 内の全ての値の出現回数をカウントし終わったら count に各値の出現回数が格納されていることになりますので、あとは出現回数が最大値となる要素の添字を getMaxIndex 関数で取得し、mode_data に格納しています。

count[mode_data]count における最大値ということですので、mode_data - offset の値が data において一番出現回数が多い値、すなわち最頻値ということになります。

ということで、最後に mode_data - offset の値を返却して、getModeData を終了するようにしています(終了する前に malloc 関数で確保したメモリは free 関数で解放しておく必要があります)。

全て正の値であることを前提として簡略化した関数

先程の関数では少し offset のあたりがややこしいかなぁと思います。

offset を利用しているのは、data の中に負の値があることを考慮しているためです。負の値がないことを前提とすれば、count0 から data の最大値までをカウントアップするように変更してもうちょっと簡単な関数に仕立てることができます。

その時の getModeData 関数は下記のように書くことができます。data の中に負の値があると上手く動作しないので注意してください。

負の値がない前提のgetModeData
int getModeData(int *data, int num_data) {

    /* 取りうる値の範囲を計算 */
    int max_data = getMaxData(data, num_data);

    /* 各値の出現回数をカウントする配列を作成 */
    int *count = malloc(sizeof(int) * (max_data + 1));

    for (int n = 0; n <= max_data; n++) {
        /* 出現回数を初期化 */
        count[n] = 0;
    }

    for (int i = 0; i < num_data; i++) {
        /* data[i]の出現回数をカウントアップ */
        count[data[i]]++;
    }

    free(count);

    /* countの中から最大値を持つ要素の添字を取得 */
    int mode_data = getMaxIndex(count, max_data + 1);

    /* その添字がdataの最頻値 */
    return mode_data;

}

malloc を利用しない場合の関数

また、コンパイラのバージョンによっては malloc 関数をわざわざ利用しなくても、配列の要素数に変数を指定して配列を変数宣言することもできます(少なくとも C99 の場合は配列の要素数に変数が指定可能なはず)。この場合、さらに getModeData 関数は下記のように変更することができます(stdlib.h のインクルードも不要になります)。

配列の要素数を変数指定した場合のgetModeData
int getModeData(int *data, int num_data) {

    /* 取りうる値の範囲を計算 */
    int max_data = getMaxData(data, num_data);

    /* 各値の出現回数をカウントする配列を作成 */
    int count[max_data + 1];

    for (int n = 0; n <= max_data; n++) {
        /* 出現回数を初期化 */
        count[n] = 0;
    }

    for (int i = 0; i < num_data; i++) {
        /* data[i]の出現回数をカウントアップ */
        count[data[i]]++;
    }

    /* countの中から最大値を持つ要素の添字を取得 */
    int mode_data = getMaxIndex(count, max_data + 1);

    /* その添字がdataの最頻値 */
    return mode_data;

}

これらの変更により、結構スッキリした関数に仕上がったと思います。

ここまで3つの getModeData 関数を紹介してきましたが、いずれにしても data の各要素の取りうる値の範囲が大きすぎると、データの個数に関わらず出現回数カウント用の配列 count の要素数が巨大になってしまうので注意してください。

それにより必要なメモリサイズも大きくなってしまいますし、 大きくなりすぎるとメモリ不足でプログラムが動作しなくなる可能性もあります。また配列 count の要素数が多い分処理パフォーマンスが著しく悪くなります。

スポンサーリンク

全ての要素の出現回数をカウントする

前述の通り、先程紹介した 値の出現回数カウント用の配列を用意する の方法では、データの集合となる配列内の値の取りうる範囲によって出現回数カウント用の配列のサイズが巨大になり、それによるメモリ不足やパフォーマンス低下の発生が問題でした。

ということで、次は出現回数カウント用の配列を用意しない方法を紹介します。

最頻値を求める際の考え方

正直 “方法” という程のものでもなく、データの集合となる配列の先頭の要素から1つずつ値の出現回数を調べ、最大出現回数となる値、すなわち最頻値を見つけていきます。

例えば下の図のような配列の中から最頻値を求めることを考えていきましょう。

要素の値を1つずつカウントしていく様子を示すための配列の例

まずは最頻値を求めていくにあたって、最大出現回数と最頻値を初期化します。今回は最大出現回数を 0 に、最頻値も一旦 0 に初期化するものとしたいと思います。

  • 最大出現回数:0
  • 最頻値:0

続いて、配列の先頭の要素の値である 8 の配列内での出現回数をカウントします。

値8の出現回数をカウントする様子

配列内に存在する 82 つなので、8 の出現回数は 2 となります。この出現回数は現在の最大出現回数の 0 よりも大きいので、最大出現回数を 2 に更新し、合わせて最頻値も 8 に更新します。

  • 最大出現回数:2
  • 最頻値:8

次に、配列の次の要素の値である 4 の配列内での出現回数をカウントします。

値4の出現回数をカウントする様子

配列内に存在する 41 つなので、4 の出現回数は 1 となります。この出現回数は現在の最大出現回数の 2 よりも小さいので、最大出現回数も最頻値も更新しません。

さらに、配列の次の要素の値である 2 の配列内での出現回数をカウントします。

値2の出現回数をカウントする様子

配列内に存在する 23 つなので、2 の出現回数は 3 となります。この出現回数は現在の最大出現回数の 2 よりも大きいので、最大出現回数を 3 に更新し、合わせて最頻値も 2 に更新します。

  • 最大出現回数:3
  • 最頻値:2

こんな感じで、配列の各要素の値の出現回数をカウントし、最大出現回数を超えていたら最大出現回数と最頻値を更新する処理を繰り返し行います。最後の要素の値に対する上記の処理が完了した時点での最頻値が、配列全体における最頻値となります。

すごく単純な方法ではありますし、配列内に同じ値が何度も出現する場合、何度も同じ値に対して出現回数のカウントを行う必要があって無駄な処理もあります。ただ、値の出現回数カウント用の配列を用意する の方法に比べて出現回数カウント用の配列は不要なのでメモリの節約にもなりますし、配列内で取りうる値の範囲の広さに処理時間が依存しないという良さもあります(配列の要素数には依存する)。

全ての要素の出現回数をカウントして最頻値を求める関数例

この方法で最頻値を求める関数は、下記ソースコードにおける getModeData となります。最頻値が複数存在する場合、最頻値としてはデータの集合 data の先頭側にある値が返却されます。

全ての要素の出現回数を調べる
#include <stdio.h>

/****************************************
 * 最頻値を求める
 * 
 * data:最頻値を求めるデータの集合
 * num_data:データの集合内のデータの数
 * 
 * 返却値:最頻値
 ****************************************/
int getModeData(int *data, int num_data) {

    int max_count = 0; /* 現状の最大出現回数 */
    int mode_data = 0; /* 現状の最頻値 */

    for (int i = 0; i < num_data; i++) {

        /* data[i]の出現回数をカウント */
        int count = 0;
        for (int j = 0; j < num_data; j++) {
            if (data[i] == data[j]) {
                /* data[i]の出現回数をカウントアップ */
                count++;
            }
        }

        if (count > max_count) {
            /* data[i]の出現回数が最大出現回数を超えた場合 */

            /* 最大出現回数と最頻値を更新 */
            max_count = count;
            mode_data = data[i];
        }
    }

    return mode_data;

}

int main(void) {

    /* 値の集合を作成 */
    int data[] = {
        1, 2, 3, 2, 5, 4, 3, 2, 1, -10,
        2, 3, 5, 2, 1, 3, 4, 3, 7, 8
    };

    /* 集合のデータ数を取得 */
    unsigned int num_data = sizeof(data) / sizeof(data[0]);

    /* 最頻値を取得して表示 */
    int mode_data = getModeData(data, num_data);
    printf("mode = %d\n", mode_data);

    return 0;
}

ソースコードの解説

getModeData の内側のループ(j に対するループ)では、data[i] の出現回数(data[i] と同じ値のものがいくつあるか)を調べています。

data[i]の出現回数を数える様子

内側のループ終了時点で、data[i] の出現回数が count に格納されていることになり、さらに count が最大出現回数の max_count を超えている場合、data[0]data[i] の中で data[i] が最頻値ということになります。そのため、countmax_count を超えている場合、最頻値 mode_datadata[i] に、さらに 最大出現回数の max_countcount に更新しています。

これらの処理を全ての i に対して実行すれば、最終的に mode_data に格納されている値が、data の中の最頻値ということになりますので、最後に mode_data を返却しています。

繰り返し回数を減らして効率化した関数

上記の getModeData 関数の欠点は、data に同じ要素の値があったとしても毎回出現回数をカウントする点です。例えば配列 data の各要素の値が下の図のような場合、data[0]data[3] の出現回数は必ず同じになります。

重複して同じ値の出現回数をカウントしてしまう例

ですが、上記の getModeData 関数では一度出現回数をカウントしたかどうかに関わらず、毎回同じように出現回数をカウントしますので、無駄に出現回数をカウントしていることになります。

一度出現回数をカウントした値を配列等で覚え得ておけば、同じ値に関して再度カウントしないよう制御することもできますが、配列を用意するためのメモリや配列から値を探索する処理も必要になるので、これはこれで結構大変です。

お手軽に効率を上げるための方法の1つとして、下記のように getModeData を変更するという手があります。

出現回数を調べる際の繰り返し回数を減らす
int getModeData(int *data, int num_data) {

    int max_count = 0; /* 現状の最大出現回数 */
    int mode_data = 0; /* 現状の最頻値 */

    for (int i = 0; i < num_data; i++) {

        /* data[i]の出現回数をカウント */
        int count = 0;
        for (int j = i; j < num_data; j++) {
            if (data[i] == data[j]) {
                /* data[i]の出現回数をカウントアップ */
                count++;
            }
        }

        if (count > max_count) {
            /* data[i]の出現回数が最大出現回数を超えた場合 */

            /* 最大出現回数と最頻値を更新 */
            max_count = count;
            mode_data = data[i];
        }
    }

    return mode_data;

}

先程の getModeData との違いは、内側のループの初期化式のみで、j = 0 から j = i に変更しています。

つまり、data[i] の出現回数をカウントする際に、すでに出現回数をカウントした data[0]data[i - 1] を無視するようになっています。これでも最頻値は正しく求めることができます。

なぜ、これでも最頻値が正しく求められるのでしょうか?

まず data[0]data[i - 1] の中に data[i] と同じ値が存在した場合、data[i] の出現回数は本来の出現回数よりも少なくカウントされることになります。

ですが、data[0]data[i - 1] の中に data[i] と同じ値が存在するのであれば、data[0]data[i - 1] のいずれかの値に対する出現回数のカウントによって data[i] の出現回数も既に求められていることになります。

ループ範囲を狭めても正しく最頻値が求められる理由の説明図1

したがって data[i] の値が最頻値なのであれば既に mode_datadata[i] が格納されているはずであり、data[i] の出現回数が少なくカウントされたとしても、最終的に求める最頻値には影響がありません(いずれにせよ count > max_count が成立しない)。

また、data[0]data[i - 1] の中に data[i] と同じ値が存在しない場合、data[0]data[i - 1] を無視して出現回数をカウントしたとしても、data[i] の出現回数は正しく求めることができます。

ループ範囲を狭めても正しく最頻値が求められる理由の説明図2

こんな感じで、data[0]data[i - 1]data[i] と同じ値がある場合も無い場合も、最頻値は正しく求めることができます。さらに、出現回数をカウントする際の繰り返し回数が i の増加に応じて減っていきますので、若干処理時間は短くすることができるはずです。

最頻値を複数求める場合

次は最頻値を複数求める場合の最頻値の求め方について解説していきます。

最頻値を1つだけ求める場合は、単に関数の返却値として最頻値を返却して貰えば良かったので、最頻値を求めることさえできれば簡単に実現できました。

それに対して複数求める場合は、関数からの複数の最頻値の受け取り方や、複数の最頻値の管理の方法のあたりがポイントになります。また、複数最頻値が存在するわけですから、関数呼び出し元に最頻値がいくつあるかが判断できるような情報も返却してやる必要があります。

最頻値を求める際の考え方については大体 最頻値を1つだけ求める場合 で解説しましたので、ここでは複数の最頻値を管理する方法について焦点を当てて解説していきたいと思います。

実現方法はたくさんありますが、今回は下記の2つのパターンで複数の最頻値を管理し、最頻値を複数求める関数の作り方を紹介していきます。

  • 事前に用意した配列を利用する
  • リストを利用する

事前に用意した配列を利用する

1つ目は関数呼び出し元で用意した配列に、関数側で最頻値を格納してもらう方法です。

最頻値を配列で複数受け渡しする際の処理の流れ

C言語の関数においては、return で返却できる値は1つのみです。ですので、関数から複数の値を返却したいような場合、関数呼び出し元に複数の値を格納するための配列やメモリを事前に準備してもらい、それらのアドレスに対して値を格納することで間接的に値を返却するような処理が必要になります。

この辺りのことは下記ページで解説していますので、詳しく知りたい方は下記ページをご参照いただければと思います。

複数の関数を返却する方法の解説ページアイキャッチ【C言語】関数から複数の値を返却する方法

さて、複数の最頻値を受け取る際の処理の流れとしては、まず関数呼び出し元で最頻値を格納するのに十分な要素数の配列もしくは十分なサイズのメモリを用意します。

複数の最頻値を受け取るための処理の流れ1

次に、関数呼び出し元が用意した配列の先頭アドレスを引数に指定して関数を実行します。

複数の最頻値を受け取るための処理の流れ2

実行された関数は、最頻値を全て求め、それらの最頻値を引数で受け取ったアドレスから順に格納します。

複数の最頻値を受け取るための処理の流れ3

さらに関数は、最頻値の数を return で返却して関数を終了します。

複数の最頻値を受け取るための処理の流れ4

最後に関数呼び出し元は、返却値として受け取った値の分だけ、配列に入れられた最頻値を取得します。

複数の最頻値を受け取るための処理の流れ5

関数から複数の最頻値を受け取る際の処理の流れはこのようになります。

事前に用意した配列を利用して最頻値を求める関数例

上記の流れを踏襲して作成した最頻値を求めるプログラムのソースコードは下記のようになります。getAllModeData が最頻値を複数求める関数であり、繰り返し回数を減らして効率化した関数 で紹介した getModeData をベースにして作成したものになります。

配列に複数の最頻値を格納する
#include <stdio.h>
#include <stdlib.h>

/****************************************
 * 最頻値を求める
 * 
 * data:最頻値を求めるデータの集合
 * num_data:データの集合内のデータの数
 * mode_data:最頻値を格納する配列
 * 返却値:最頻値の数
 ****************************************/
int getAllModeData(int *data, int num_data, int *mode_data) {

    int max_count = 0; /* 現状の最大出現回数 */
    int mode_num = 0; /* 最頻値の数 */

    for (int i = 0; i < num_data; i++) {

        /* data[i]の出現回数をカウント */
        int count = 0;
        for (int j = i; j < num_data; j++) {
            if (data[i] == data[j]) {
                /* data[i]の出現回数をカウントアップ */
                count++;
            }
        }

        if (count > max_count) {
            /* data[i]の出現回数が最大出現回数を超えた場合 */

            /* 最大出現回数を更新 */
            max_count = count;

            /* 最頻値を配列の先頭に追加 */
            mode_num = 0;
            mode_data[mode_num] = data[i];
            mode_num++;
        } else if (count == max_count) {
            /* data[i]の出現回数が最大出現回数と同じ場合 */

            /* 最頻値を配列に追加 */
            mode_data[mode_num] = data[i];
            mode_num++;
        }
    }

    /* 最頻値の個数を返却 */
    return mode_num;

}

int main(void) {

    /* 値の集合を作成 */
    int data[] = {
        5, 2, 3, 2, 5, 4, 3, 2, 1, 1,
        2, 3, 5, 2, 1, 3, 4, 3, 7, 1,
        1, 4, 5, 4, 7, 5, 0, 0, 7, 4
    };

    /* 集合のデータ数を取得 */
    unsigned int num_data = sizeof(data) / sizeof(data[0]);

    /* 最頻値を格納するための配列を用意 */
    int *mode_data = malloc(sizeof(int) * num_data);

    /* 最頻値を取得して表示 */
    int mode_num = getAllModeData(data, num_data, mode_data);
    
    for (int i = 0; i < mode_num; i++) {
        printf("mode%d = %d\n", i + 1, mode_data[i]);
    }

    free(mode_data);
    
    return 0;
}

ソースコードの解説

まず main 関数では、下記で最頻値を getAllModeData 関数に格納してもらうための配列(として扱うためのメモリ)を用意しています。

配列の用意
/* 最頻値を格納するための配列を用意 */
int *mode_data = malloc(sizeof(int) * num_data);

malloc を利用しない場合の関数 でも解説しましたが、コンパイラのバージョンによっては、上記の malloc 関数を実行している行を int mode_data[num_data] で代替することができます(この場合は free の行も不要になります)。

続いて下記で getAllModeData 関数の実行を行なっていますが、この際に先程用意した配列(メモリ)の先頭アドレス mode_data を指定しているところがポイントになります。

配列のアドレスを渡す
/* 最頻値を取得して表示 */
int mode_num = getAllModeData(data, num_data, mode_data);

これにより、getAllModeData 関数は最頻値をどこに格納していけば良いかが分かるようになります。また、getAllModeData 関数はこの配列のアドレスを受け取れるよう、getModeData 関数の時に比べて引数の追加も行っているので注意してください。

getAllModeData 関数が実行されるので、次は getAllModeData 関数が動作することになります。基本的に、data[i] の出現回数のカウントは 繰り返し回数を減らして効率化した関数 で紹介したものと同じ処理により実現しています。

data[i] の出現回数が確定した際には、最大出現回数と data[i] の出現回数との比較を行い、比較結果に応じて最頻値を格納する配列に data[i] の追加を行います。この追加の仕方が、「最大出現回数よりも data[i] の出現回数の方が大きい」場合と、「最大出現回数と data[i] の出現回数が同じである」場合とで異なるので注意してください。

まず、最大出現回数よりも data[i] の出現回数の方が大きい場合、既に最頻値を格納する配列に追加されていた値は最頻値では無かったことになります。

そのため、この場合は配列の先頭を1つ目の最頻値として data[i] で上書きします。この時、最頻値の個数は 1 個になります。

data[4]を1つ目の最頻値として登録する様子

この処理を行なっているのが、getAllModeData 関数の下記部分になります。

最大出現回数が更新された時の処理
if (count > max_count) {
    /* data[i]の出現回数が最大出現回数を超えた場合 */

    /* 最大出現回数を更新 */
    max_count = count;

    /* 最頻値を配列の先頭に追加 */
    mode_num = 0;
    mode_data[mode_num] = data[i];
    mode_num++;
}

また、最大出現回数と data[i] の出現回数が同じである場合、data[i] の出現回数は既に最頻値を格納する配列に追加されていた値と同じ出現回数であることになります。ですので、配列に既に追加されていた値も data[i] も最頻値ということになります。

ですので、この場合は、既に配列に格納されていた値を上書きしないよう、それらの値の後ろ側に data[i] を追加する必要があります。具体的には、最頻値を格納する配列を mode_data、既に mode_data に格納されている値の個数を mode_num とすれば、mode_data[mode_num] = data[i] によって data[i] を配列に追加します。

data[4]を3つ目の最頻値として登録する様子

この追加を実現するためには、配列に格納されている値の個数 mode_num をしっかり管理しておく必要があるので注意してください。

これらの処理を行なっているのが、getAllModeData 関数の下記部分になります。

最大出現回数と同じ場合の処理
else if (count == max_count) {
    /* data[i]の出現回数が最大出現回数と同じ場合 */

    /* 最頻値を配列の末尾に追加 */
    mode_data[mode_num] = data[i];
    mode_num++;
}

data の全ての要素の値の出現回数のカウントが完了して外側のループが終了した際には、配列 mode_data には mode_num 個の最頻値が格納されていることになります。

getAllModeData 関数で使用している mode_data は関数呼び出し元が用意した配列の先頭アドレスですので、関数さえ終了すれば関数呼び出し元で配列から最頻値を取得することが可能です。

ただ、いくつ最頻値が存在するかが分からないと、配列からいくつ最頻値を取得すれば良いかが分からないため、その最頻値の個数を伝えるために、最後に mode_numreturn して getAllModeData 関数は終了します。

getAllModeData 関数が終了すれば、関数呼び出し元に処理が戻りますが、この時に返却値として最頻値の個数を取得することができます。

ですので、あとはその個数分の値を元々用意した配列 mode_data の先頭から取得してやれば、最頻値を全て取得することができます。

これを行なっているのが main 関数の下記部分となります。mode_numgetAllModeData 関数から返却値として受け取った最頻値の個数となります。

最頻値の取得と表示
for (int i = 0; i < mode_num; i++) {
    printf("mode%d = %d\n", i + 1, mode_data[i]);
}

スポンサーリンク

リストを利用する

先程紹介した 事前に用意した配列を利用する でも複数の最頻値はしっかり求めることが出来ますが、ちょっとだけ気になるのが「事前に用意する配列の要素数」ですね…。

当然最頻値を求めるまでは最頻値がいくつあるかが分かりません。ですので最悪の場合を考慮して、この配列の要素数は データの集合の値の個数 に設定するしかないかなぁと思います。

このため、データの集合の値の個数が多いほど、メモリが多く必要になってしまうことになります。データの集合の値の個数が巨大だと、最悪メモリ不足でプログラムが正常に動作できなくなるかもしれません。

なので、最頻値を見つけるたびに、使用するメモリを増減させるような作りにして、必要最小限のメモリのみを使用するようにした方が、使用メモリ量の観点からすると良いです。

こういった使用するメモリを増減させる手段の1つとして、realloc 関数を利用するという手があります。

realloc 関数を利用すれば、使用するメモリを必要に応じて増減させることが出来ます。realloc 関数に関しては下記ページで解説していますので、詳細を知りたい方はこちらを参考にしていただければと思います。

【C言語】realloc関数の使い方・注意点を解説

もう一つの手段としてリストの利用が挙げられます。リストについては下記ページで解説していますので、まだリストをご存知ない方はこちらを参照していただければと思います。

リスト構造の解説ページアイキャッチ【C言語】リスト構造について分かりやすく解説【図解】

リストは、下の図のように管理したいデータ(今回の場合は最頻値)を持たせたノードを連結させるようなデータの構造です。このノード同士の連結は、C言語の場合はポインタで行われることが多いです。

最頻値をリストで管理する様子

このリストの特徴に「ノードの追加や削除が容易」な点が挙げられます。従って、最初は空のリストを用意しておき、最頻値が増えるたびにリストにノードを追加、最大出現回数を超える値が見つかった場合は一旦リストを空にしてから再度先頭にノードを追加、といった操作も簡単に行えます。

ノードの数だけメモリを消費しますが、必要最小限の数のノードで最頻値を管理できるため、要素数が データの集合の値の個数 の配列やメモリを用意するよりもメモリ効率は良くなることが多いです。

ということで、今回はリストを使って関数が求めた複数の最頻値を受け渡しするソースコードを紹介したいと思います。そのソースコードが下記になります。

リストを利用する方法
#include <stdio.h>
#include <stdlib.h>

/* 最頻値を登録する構造体 */
struct NODE {
    int mode; /* 最頻値 */
    struct NODE *next; /* 次のノード */
};

void print(void);
void finalize(void);
int add(int);
int delete(int);

/* リストの先頭を指すポインタ */
static struct NODE *head = NULL;

/******************************
 * 全てのノードのデータを表示する関数
 ******************************/ 
void print(void){
    struct NODE *node;
    int i;

    node = head;
    i = 0;
    while (node != NULL) {
        printf("mode%d:%d\n", i + 1, node->mode);
        node = node->next;
        i++;
    }
}

/******************************
 * 全てのノードを削除する関数
 ******************************/ 
void finalize(void){
    int target;

    while (head != NULL) {
        /* まだリストが空でない場合 */
        
        /* 先頭のノードを削除 */
        target = head->mode;
        delete(target);
    }
}


/******************************
 * リストにノードを追加する関数
 * mode:追加するノードの最頻値
 * 返却値:0(成功時)
 *      :-1(失敗時)
 ******************************/ 
int add(int mode){
    struct NODE *new; /* 追加するノードのアドレス */
    struct NODE *node; /* 今注目しているノードのアドレス */
    struct NODE *prev; /* nodeの前のノードのアドレス */

    /* ノードを新規追加 */
    new = (struct NODE*)malloc(sizeof(struct NODE));
    if (new == NULL) {
        return -1;
    }

    new->mode = mode;

    /* リストの先頭のノードに注目 */
    node = head;

    /* ノードを追加する位置を決める */
    while (node != NULL) {
        if (node->mode > new->mode) {
            /* 追加する位置が見つかった */
            break;
        }

        /* nodeを前のノードとして覚えておく */
        prev = node;

        /* 次のノードを辿る */
        node = node->next;
    }

    if (node == head) {
        /* 追加する位置がリストの先頭の場合 */

        /* 元々先頭だったノードをnewの次のノードにする */
        new->next = head; /* リストが空の場合はheadはNULL */

        /* リストの先頭をnewとする */
        head = new;

        

    } else {
        /* 追加する位置がリストの先頭以外の場合 */

        /* prevとnodeの間にnewを追加 */
        prev->next = new;
        new->next = node; /* 追加する位置が末尾の場合ははnodeはNULLになっている */
    }

    return 0;
}

/******************************
 * リストからノードを削除する関数
 * target:削除するノードの最頻値
 * 返却値:0(成功時)
 *      :-1(失敗時)
 ******************************/ 
int delete(int target){
    struct NODE *node; /* 今注目しているノードのアドレス */
    struct NODE *prev; /* nodeの前のノードのアドレス */

    if (head == NULL) {
        /* リストが空なら何もしない */

        return -1;
    }

    /* リストの先頭のノードに注目 */
    node = head;

    if (node->mode == target) {
        /* 削除対象がリストの先頭のノードの場合 */

        /* リストの先頭をnodeの次のノードにしてnodeを削除 */
        head = node->next;
        free(node);

        return 0;
    }

    while (node != NULL) {

        if (node->mode == target) {
            /* 削除対象のノードが見つかった */

            /* prevの次のノードをnodeの次のノードに設定 */
            prev->next = node->next;

            /* 削除対象のノードを削除して終了 */
            free(node);

            return 0;
        }

        /* nodeを前のノードとして覚えておく */
        prev = node;

        /* 次のノードを辿る */
        node = node->next;

    }

    /* targetを持つノードが見つからなかった */
    return -1;
}

/****************************************
 * 最頻値を求める
 * 
 * data:最頻値を求めるデータの集合
 * num_data:データの集合内のデータの数
 * 返却値:なし
 ****************************************/
void getAllModeData(int *data, int num_data) {

    int max_count = 0; /* 現状の最大出現回数 */
    int mode_num = 0; /* 最頻値の数 */

    for (int i = 0; i < num_data; i++) {

        /* data[i]の出現回数をカウント */
        int count = 0;
        for (int j = i; j < num_data; j++) {
            if (data[i] == data[j]) {
                /* data[i]の出現回数をカウントアップ */
                count++;
            }
        }

        if (count > max_count) {
            /* data[i]の出現回数が最大出現回数を超えた場合 */

            /* 最大出現回数を更新 */
            max_count = count;

            /* リストのノードを全て削除 */
            finalize();

            /* 最頻値を持つノードをリストに追加 */
            add(data[i]);

        } else if (count == max_count) {
            /* data[i]の出現回数が最大出現回数と同じ場合 */

            /* 最頻値を持つノードをリストに追加 */
            add(data[i]);
        }
    }

}

int main(void) {

    /* 値の集合を作成 */
    int data[] = {
        5, 7, 3, 7, 5, 4, 3, 7, 1, 1,
        7, 3, 5, 7, 1, 3, 4, 3, 7, 1,
        1, 4, 5, 0, 0, 0, 0, 0, 0, 0
    };

    /* 集合のデータ数を取得 */
    unsigned int num_data = sizeof(data) / sizeof(data[0]);

    /* 最頻値を取得して表示 */
    getAllModeData(data, num_data);

    print();

    finalize();

    return 0;
}

リスト関連の関数は下記の4つになります。

  • add:引数で指定した最頻値を持つノードをリストに追加する
  • delete:引数で指定した最頻値を持つノードをリストから削除する
  • print:リストに存在する全てのノードの持つ最頻値を表示する
  • finalize:リストのノードを全て削除する

上記4つの関数の意味合いを理解すれば、大体 getAllModeData 関数で何をやっているかが分かるのではないかと思います。管理するためのデータ構造は異なるものの、最頻値の求め方は 事前に用意した配列を利用する で紹介した時と同じです。

また、上記の関数の詳細は前述でも紹介した下記ページで解説していますので、詳しく知りたい方はこちらを参考にしてください(NODE 構造体のメンバを変更しているため、その違いの分のみ、このページで紹介している関数と下記ページで紹介している関数とに違いがあります)。

リスト構造の解説ページアイキャッチ【C言語】リスト構造について分かりやすく解説【図解】

事前に用意した配列を利用する で紹介したソースコードのように、最悪の場合を考慮して配列やメモリのサイズを決める方法でもやりたいことが実現できる場合も多いですが、リストなどを利用すれば、使用するメモリを増減させながら必要最小限のメモリのみを使用して処理を進めることができるということも覚えておくと良いと思います!

まとめ

このページでは、C言語で最頻値を求める方法について解説しました!

値のとりうる範囲がある程度制限されているのであれば、値の出現回数カウント用の配列を用意する で紹介した方法で最頻値を求めるのが一番楽だと思います。

ただし、値のとりうる範囲が広い場合は出現回数カウント用の配列が大きすぎてメモリ不足になる可能性もあるので注意してください。その場合は 全ての要素の出現回数をカウントする で紹介した方法で集合内の全ての値の出現回数を1つずつ地道に数え上げていくのが良いです。出現回数カウント用の配列が不要なので、メモリ使用量を抑えることが出来ます。

複数の最頻値を求めたい場合は、事前に用意した配列を利用する で紹介した手順で複数の最頻値を関数から渡してもらえるようにするのが楽だと思います。というか、わざわざ関数に分けなければ引数でアドレスを渡す必要もないので更に楽に最頻値が求められます。

ただ、できるだけメモリ使用量を抑えたいような場合は、リストを利用する で紹介したように、リスト等を利用して必要な分のみのメモリで複数の最頻値を管理できるように工夫してみましょう!

オススメの参考書

C言語学習中だけど分からないことが多くて挫折しそう...という方には、下記の「スッキリわかるC言語入門」がオススメです!

まず学習を進める上で、参考書は2冊持っておくことをオススメします。この理由は下記の2つです。

  • 参考書によって、解説の仕方は異なる
  • 読み手によって、理解しやすい解説の仕方は異なる

ある人の説明聞いても理解できなかったけど、他の人からちょっと違った観点での説明を聞いて「あー、そういうことね!」って簡単に理解できた経験をお持ちの方も多いのではないでしょうか?

それと同じで、1冊の参考書を読んで理解できない事も、他の参考書とは異なる内容の解説を読むことで理解できる可能性があります。

なので、参考書は2冊持っておいた方が学習時に挫折しにくいというのが私の考えです。

特に上記の「スッキリわかるC言語入門」は、他の参考書とは違った切り口での解説が豊富で、他の参考書で理解できなかった内容に対して違った観点での解説を読むことができ、オススメです。題名の通り「なぜそうなるのか?」がスッキリ理解できるような解説内容にもなっており、C言語入門書としてもかなり分かりやすい参考書だと思います。

もちろんネット等でも色んな観点からの解説を読むことが出来ますので、分からない点は別の人・別の参考書の解説を読んで解決していきましょう!もちろん私のサイトも参考にしていただけると嬉しいです!

入門用のオススメ参考書は下記ページでも紹介していますので、こちらも是非参考にしていただければと思います。

https://daeudaeu.com/c_reference_book/

同じカテゴリのページ一覧を表示