最頻値を求める | Programming Place Plus　Ｃ言語編　逆引き

トップページ – Ｃ言語編 – 逆引き

このページの概要 🔗

このページの解説は C99 をベースとしています。

以下は目次です。

目的 🔗

要素が数値の配列があるとき、その最頻値（モード）を求めたいとします（方法① は、要素が数値でなくても使えます）。

最頻値とは、一番多く登場する値のことです。

配列から、最頻値を求める get_mode関数を作ることを考えます。引数に、配列（を指すポインタ）と要素数を指定すると、戻り値で最頻値を返します。

#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int main(void)
{
    int array[] = {7, 2, 6, 2, 2, 6, 1, 3};

    printf("%d\n", get_mode(array, SIZE_OF_ARRAY(array)));
}

この場合、最頻値は 2 なので、2 が出力されることを望みます。

SIZE_OF_ARRAYマクロは、配列の要素数を取得するものです。詳細は「逆引き　配列の要素数を求める」を参照してください。

ところで、最頻値は複数個存在する可能性があります。

int array[] = {7, 2, 6, 2, 2, 6, 1, 6};

この配列の場合、2 と 6 がともに 3回ずつ登場しており、いずれもが最頻値です。

このような場合に、すべての最頻値を知りたいのであれば、実装の方法を変えなければなりません。方法④ で取り上げます。

方法①（各要素の値の登場回数の最大値を求める） 🔗

一番素直な方法は、各要素の登場回数をそれぞれ調べて、それが最大値になるものを探す方法です。この方法は、要素が数値でなくても使える利点があります。

たとえば、array[0] の値である 7 は何回登場するか調べて、その回数を保存しておく。次は、array[1] の値である 2 が何回登場するか調べて、先ほど保存しておいた回数よりも大きければ置き換え、小さければ何もしない。次は array[2] の値の登場回数を調べる・・・、といったことを最後の要素まで繰り返します。

これは、配列から最大値を求める方法を利用したものです（「逆引き　配列から最大値（最小値）を探す」を参照）。

#include <assert.h>
#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

/*
    最頻値を求める

    引数
        array: 対象の配列
        size:  array の要素数
    戻り値
        最頻値
*/
int get_mode(const int* array, size_t size)
{
    assert(array != NULL);
    assert(size > 0);

    int mode;              // これまでに調べた中での最頻値
    int count_max = 0;     // これまでに調べた登場回数の中で最大のもの

    for (size_t i = 0; i < size; ++i) {

        // array[i] の値の登場回数を調べる
        int count = 1;
        for (size_t j = i + 1; j < size; ++j) {
            if (array[i] == array[j]) {
                ++count;
            }
        }

        // これまでの最大の登場回数よりも多かったら、更新する
        if (count_max <= count) {
            count_max = count;
            mode = array[i];
        }
    }

    return mode;
}

int main(void)
{
    int array[] = {7, 2, 6, 2, 2, 6, 1, 3};

    printf("%d\n", get_mode(array, SIZE_OF_ARRAY(array)));
}

実行結果：

2

この方法には多少の無駄もあります。

array[1] と array[3] の値はともに 2 です。i == 1 のときのループで、2 の登場回数はすでに調べ終えていますが、i == 3 のときのループでも再び 2 の登場回数を調べてしまっています。

とはいえ、この無駄を省くために、調べ終えた値を覚えておこうとすると、それはそれで無駄な処理が増え、メモリも余分に消費してしまいます。

条件付きですが、解決策が２つあります。

１つは、配列に含まれている値の範囲が事前に分かっているのなら、それらの値を添字に対応させた配列を用意して、そこで登場回数をカウントすることです。この方法は、方法② で説明します。

もう１つは、配列がソートされているのなら、それを利用して効率を上げられます。この方法は、方法③ で説明します。

方法②（値の範囲の広さに応じた配列を利用する） 🔗

配列に含まれている値の範囲が分かっているのなら、要素の値を添字とする配列をつくって、そこで登場回数をカウントする方法があります。

たとえば、配列には 0～9 の値のいずれかしか含まれていないとします。この場合なら、登場回数のカウント用に、int count[10]; という配列を用意します。そして、2 という値の登場回数は count[2] にカウントし、4 という値なら count[4] にカウントするようにします。

値の範囲は、要素の型の最小値～最大値には必ず収まるのですから、範囲はいつでも分かっているともいえますが、その範囲分の要素数を持った配列を作らなければならないので、範囲が広すぎると無理があります。

この方法で実装すると、ループを二重にまわす必要がなくなります。

#include <assert.h>
#include <stdio.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

/*
    最頻値を求める

    引数
        array: 対象の配列
        size:  array の要素数
    戻り値
        最頻値
*/
int get_mode(const int* array, size_t size)
{
    assert(array != NULL);
    assert(size > 0);

    // array に含まれる値が 0～9 の範囲であることを前提にしている
    int count[10] = {0};

    // 各要素の値の登場回数をカウント
    for (size_t i = 0; i < size; ++i) {
        ++count[array[i]];
    }

    // 一番登場回数が多いものを探す
    size_t max_index = 0;
    int max = count[max_index];
    for (size_t i = 1; i < size; ++i) {
        if (max <= count[i]) {
            max = count[i];
            max_index = i;
        }
    }

    return (int)max_index;
}

int main(void)
{
    int array[] = {7, 2, 6, 2, 2, 6, 1, 3};

    printf("%d\n", get_mode(array, SIZE_OF_ARRAY(array)));
}

実行結果：

2

配列count の添字と、配列array の要素の値を対応付けているのですから、登場回数が count にカウントされた後は、count の中で最大値を探し、その添字を調べれば、それが array の最頻値です。

方法③（配列がソートされていることを利用する） 🔗

もし配列がソートされているのなら、そのことを利用した実装ができます。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int compare_int(const void* a, const void* b)
{
    int a_num = *(int*)a;
    int b_num = *(int*)b;

    return a_num - b_num;
}

/*
    最頻値を求める

    引数
        array: 対象の配列
        size:  array の要素数
    戻り値
        最頻値
*/
int get_mode(const int* array, size_t size)
{
    assert(array != NULL);
    assert(size > 0);

    // [!] 配列が昇順にソートされていることを前提にしている

    int mode;              // これまでに調べた中での最頻値
    int count_max = 0;     // これまでに調べた登場回数の中で最大のもの

    for (size_t i = 0; i < size; ) {

        int value = array[i];
        int count = 1;
    
        // ソートされているのだから、
        // 同じ値があるとすれば、後続に連続して並んでいるはず。
        // その回数をカウントする。
        for (i = i + 1; i < size; ++i) {
            if (value == array[i]) {
                ++count;
            }
            else {
                // 違う値が登場したら終わり
                break;
            }
        };

        // これまでの最大の登場回数よりも多かったら、更新する
        if (count_max < count) {
            count_max = count;
            mode = value;
        }
    }

    return mode;
}

int main(void)
{
    int array[] = {7, 2, 6, 2, 2, 6, 1, 3};

    // 配列を昇順にソートする
    qsort(array, SIZE_OF_ARRAY(array), sizeof(int), compare_int);

    printf("%d\n", get_mode(array, SIZE_OF_ARRAY(array)));
}

実行結果：

2

ソートされていれば、ある値と同じ値は必ず連続的に並んでいますから、これを利用します。

ループは二重ですが、ループ制御変数はどちらも i です。配列を先頭から末尾に向かって一直線に辿っているだけであり、無駄がありません。

なお、ここでは配列を、qsort関数を使ってソートしていますが、ソートの処理が加わったことで結局、遅くなる可能性に注意してください（配列をソートする方法については、「逆引き　配列をソートする」を参照）。

なお、get_mode関数内で配列をコピーして、コピーの方をソートすることも考えられます。こうすれば、やはり効率面の問題はありますが、どんな配列にでも対応できます。

配列をコピーする方法については、「逆引き　配列をコピーする」を参照してください。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int compare_int(const void* a, const void* b)
{
    int a_num = *(int*)a;
    int b_num = *(int*)b;

    return a_num - b_num;
}

/*
    最頻値を求める

    引数
        array: 対象の配列
        size:  array の要素数
    戻り値
        最頻値
*/
int get_mode(const int* array, size_t size)
{
    assert(array != NULL);
    assert(size > 0);

    // array のコピーを作って、ソートする
    int* array_copy = malloc(sizeof(int) * size);
    memcpy(array_copy, array, sizeof(int) * size);
    qsort(array_copy, size, sizeof(int), compare_int);


    int mode;              // これまでに調べた中での最頻値
    int count_max = 0;     // これまでに調べた登場回数の中で最大のもの

    for (size_t i = 0; i < size; ) {

        int value = array_copy[i];
        int count = 1;
    
        // ソートされているのだから、
        // 同じ値があるとすれば、後続に連続して並んでいるはず。
        // その回数をカウントする。
        for (i = i + 1; i < size; ++i) {
            if (value == array_copy[i]) {
                ++count;
            }
            else {
                // 違う値が登場したら終わり
                break;
            }
        };

        // これまでの最大の登場回数よりも多かったら、更新する
        if (count_max < count) {
            count_max = count;
            mode = value;
        }
    }

    free(array_copy);

    return mode;
}

int main(void)
{
    int array[] = {7, 2, 6, 2, 2, 6, 1, 3};

    printf("%d\n", get_mode(array, SIZE_OF_ARRAY(array)));
}

実行結果：

2


方法④（最頻値が複数ある場合） 🔗

最頻値が複数個あったときに、そのすべてを知りたい場合には、ここまでに取り上げた方法では対応できません。

関数化するのなら、そもそも戻り値では複数の結果を返せないので、呼び出し元で、結果を受け取るための配列を用意して、そのメモリアドレスを渡すようにします。

/*
    すべての最頻値を求める

    引数
        array: 対象の配列
        size:  array の要素数
        result_array: 最頻値を受け取る配列。要素数は size以上でなければならない。
    戻り値
        発見した最頻値の個数。

    呼び出し後の result_array は、
    先頭から、戻り値が返した個数分の要素以外は有効な状態を保証しないので、
    参照してはならない。
*/
size_t get_mode_all(const int* array, size_t size, int* result_array);

実装は、方法② をベースにするのが簡単です。カウント用の配列を作り終えて、最大値が分かったら、最大値と同じ値が入っている場所の添字を、result_array へ移し替えれば完了します。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int compare_int(const void* a, const void* b)
{
    int a_num = *(int*)a;
    int b_num = *(int*)b;

    return a_num - b_num;
}

/*
    すべての最頻値を求める

    引数
        array: 対象の配列
        size:  array の要素数
        result_array: 最頻値を受け取る配列。要素数は size以上でなければならない。
    戻り値
        発見した最頻値の個数。

    呼び出し後の result_array は、
    先頭から、戻り値が返した個数分の要素以外は有効な状態を保証しないので、
    参照してはならない。
*/
size_t get_mode_all(const int* array, size_t size, int* result_array)
{
    assert(array != NULL);
    assert(size > 0);
    assert(result_array != NULL);

    // array に含まれる値が 0～9 の範囲であることを前提にしている
    int count[10] = {0};

    // 各要素の値の登場回数をカウント
    for (size_t i = 0; i < size; ++i) {
        ++count[array[i]];
    }

    // 一番登場回数が多いものを探す
    int max = count[0];
    for (size_t i = 1; i < size; ++i) {
        if (max <= count[i]) {
            max = count[i];
        }
    }

    // 最大値と同じ値が入っている場所を調べ、
    // その添字を result_array へ入れていく。
    size_t result_index = 0;
    for (size_t i = 0; i < size; ++i) {
        if (count[i] == max) {
            result_array[result_index] = (int)i;
            ++result_index;
        }
    }

    return result_index;
}

int main(void)
{
    int array[] = {7, 2, 6, 2, 2, 6, 1, 6};

    // 配列を昇順にソートする
    qsort(array, SIZE_OF_ARRAY(array), sizeof(int), compare_int);

    // すべての最頻値を取得する
    int mode_array[SIZE_OF_ARRAY(array)];
    size_t mode_count = get_mode_all(array, SIZE_OF_ARRAY(array), mode_array);

    for (size_t i = 0; i < mode_count; ++i) {
        printf("%d\n", mode_array[i]);
    }
}

実行結果：

2
6

この方法の欠点は、値の範囲が分かっていなければならないことです。そのため、実質的には使いものにならない可能性もあります。

方法③ をベースにすることもできます。ソート済みでなければなりませんが、get_mode_all関数の中で、コピーを取って、ソートする方法を採ることにします。

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define SIZE_OF_ARRAY(array)    (sizeof(array)/sizeof(array[0]))

int compare_int(const void* a, const void* b)
{
    int a_num = *(int*)a;
    int b_num = *(int*)b;

    return a_num - b_num;
}

/*
    すべての最頻値を求める

    引数
        array: 対象の配列
        size:  array の要素数
        result_array: 最頻値を受け取る配列。要素数は size以上でなければならない。
    戻り値
        発見した最頻値の個数。

    呼び出し後の result_array は、
    先頭から、戻り値が返した個数分の要素以外は有効な状態を保証しないので、
    参照してはならない。
*/
size_t get_mode_all(const int* array, size_t size, int* result_array)
{
    assert(array != NULL);
    assert(size > 0);
    assert(result_array != NULL);

    // array のコピーを作って、ソートする
    int* array_copy = malloc(sizeof(int) * size);
    memcpy(array_copy, array, sizeof(int) * size);
    qsort(array_copy, size, sizeof(int), compare_int);


    int count_max = 0;        // これまでに調べた登場回数の中で最大のもの
    size_t result_index = 0;  // 次に result_array に値を入れるときに使う添字

    for (size_t i = 0; i < size; ) {

        int value = array_copy[i];
        int count = 1;
    
        // ソートされているのだから、
        // 同じ値があるとすれば、後続に連続して並んでいるはず。
        // その回数をカウントする。
        for (i = i + 1; i < size; ++i) {
            if (value == array_copy[i]) {
                ++count;
            }
            else {
                // 違う値が登場したら終わり
                break;
            }
        };

        // これまでの最大の登場回数よりも多かったら、更新する
        if (count_max < count) {
            count_max = count;

            // 新しい最大値が見つかったので、
            // これまでに result_array に入れた分は無視して、
            // あらためて 0番目から入れ直す。
            result_array[0] = value;
            result_index = 1;
        }
        else if (count_max == count) {
            // これまでの最大の登場回数と同じなら、結果の配列へ保存
            result_array[result_index] = value;
            ++result_index;
        }
    }

    free(array_copy);

    return result_index;
}

int main(void)
{
    int array[] = {7, 2, 6, 2, 2, 6, 1, 6};

    // すべての最頻値を取得する
    int mode_array[SIZE_OF_ARRAY(array)];
    size_t mode_count = get_mode_all(array, SIZE_OF_ARRAY(array), mode_array);

    for (size_t i = 0; i < mode_count; ++i) {
        printf("%d\n", mode_array[i]);
    }
}

実行結果：

2
6

登場回数の最大値が更新されたときと、これまでの最大登場回数と同じ登場回数の値を発見したとき、result_array に値を入れてやります。

最大値が更新された場合には、これまでに result_array に入れてしまったものは最頻値ではなかったことになるので、0番目から入れ直します。戻り値を使って、実際に発見された最頻値の個数を返すので、入れてしまった値を削除するような行為は不要です。


参考リンク 🔗


更新履歴 🔗


逆引きのトップページへ

Ｃ言語編のトップページへ

Programming Place Plus のトップページへ

はてなブックマーク に保存 Pocket に保存 Facebook でシェア
X で ポスト／フォロー LINE で送る noteで書く
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー
先頭へ戻る