ヒストグラムソートとランキングフィルター
ヒストグラムソートとランキングフィルター
２０２４年１０月２９日初稿
「ヒストグラムソート」も「ランキングフィルター」も
何方の単語も普通の読者様には馴染みが無い名前だと思い
ますが、これらの単語を分解して「ヒストグラム」は、
数学の統計関連の話で聞いた事が有り、実際にグラフの
作画を行ったり、何かのレポートで使用した事が有ると思
います！
そして「ソート」も整理する「順番に並べ替える」処理だと
は、コンピュータプログラミングに馴染んでいる方には、
ピンと来る名称と思いますが、「ヒストグラムソート」と
名付けられたアルゴリズムには、恐らく、馴染みが無いと
思います！
ソーティング技法を扱ったコンピュータプログラミングの
解説書の中にもヒストグラムソートを扱った書籍が在り、
私が学生時代にゼミの英論文輪読会の俎上に上がった御題の
一つとして侃々諤々している時、指導教官が、「良く存在
する事が分からないが、恐らく、経験したアルゴリズムの中
で最も非効率な奴」と解説して頂いたアルゴリズムだった！
だった！と過去形で記述した事に注意して下さい！
私も輪読会でソウ思ったのだ！
でも、「ランキングフィルター」をＣ言語でＡＤＳ社の
画像処理装置に組み込む時、アルゴリズム元ネタとして
「スパイダーＳＰＩＤＥＲ」と称するフォートラン
ＦＯＲＴＲＡＮ言語のソースコードで記述された
アルゴリズムをＣ言語に置き換える必要が有る時に
ソーティングに「ヒストグラムソート」を使用して居る事が
判り、暫く混乱し、所謂、コペルニクス的転回を起こしたの
だ！
極めて非効率なアルゴリズムと頑なに頭の中で思って居た
処理が、「ランキングフィルター」を効率よく実現する為に
必須だったのだ？！
１．英語の論文でヒストグラムソートが非効率と記載して有ったか解説
（１）用意
先ず、ヒストグラム（度数分布）データをカウント出来る表
≪エクセルのシートの様な物と考えて下さい、Ｃ言語での
ソースコード表現では配列「最小値から最大値までカウント
出来る大きさ」に成ります！≫を用意して表を初期値として
０クリアします！
（２）ヒストグラム計測
ヒストグラム（度数分布）データをカウントと記載したら、
多分、普通に数学を義務教育の中で習って来た読者様には、
理解できると思いますが？！
如何にノート（ｃｏｄｅ）機能でサンプルデータを示し、
如何、ヒストグラム結果が算出されるか示します！
ｃｏｄｅ：
3 50 44 25 34 23 50 0 7 5 6 24 43 44 45 27 37 7
25 53 44 3 42 44 40 8 7 37 27 44 46 48 20 25 23
0 44 49 26 27 34 42 49 37 33と有ったとします！
次に結果をｄａｔａ（数値データ）、頻度ｈｉｓｔ（同じ
数値データが何個有ったかの個数）＝ｈｉｓｔに成る結果を
示します！
ｃｏｄｅ：
data hist
0 2
1 0
2 0
3 2
4 0
5 1
6 1
7 2
8 1
9 0
10 0
11 0
12 0
13 0
14 0
15 0
16 0
17 0
18 0
19 0
20 1
21 0
22 0
23 2
24 1
25 3
26 1
27 3
28 0
29 0
30 0
31 0
32 0
33 1
34 2
35 0
36 0
37 3
38 0
39 0
40 1
41 0
42 2
43 1
44 5
45 1
46 1
47 0
48 1
49 2
50 2
51 0
52 0
53 1そしてこれを動作させたＣ言語風ソースコードを示して置き
ます！
ｃｏｄｅ：
int data[]={ // 初期値として元データを示します！
3,50,44,25,34,23,50,0,7,5,6,24,43,44,45,27,37,7,
25,53,44,3,42,44,40,42,44,40,8,7,37,27,44,46,48,
20,25,23,0,44,49,26,27,34,42,49,37,33,
};
int hist[100]; // ヒストグラム結果格納配列：
//勿論、十分サイズが大き目に
// 必要です！
int i; // 配列の添え字用インデックス値
int a; // データ最小値＝必要な配列
// 添え字最小値
int b; // データ最大値＝必要な配列
// 添え字最大値
// ヒストグラムを演算する範囲「a..b」を算出する
a = data[0]; // 初期値
b = a: // 初期値
for(i=0; i< sizeof(data)/sizeof(int);i++){ // data配列を全てナメル
if( a > data[i] ){ // お馴染みの最小値を算出する構文
a = data[i]; //
}
if( b < data[i] ){ // お馴染みの最大値を算出する構文
b = data[i]; //
}
}
// ヒストグラム結果格納配列を初期化
for( i=a; i<=b; i++ ){ // 範囲「a..b」内でループ
hist[i] = 0; // ０クリア
}
// ヒストグラムを演算
for( i=a; i<=b; i++ ){ // 範囲「a..b」内で演算
hist[data[i]]++; // ヒストグラム演算⇒対象の場所をカウント
// アップ
}
此処までは、数学的な配列を使用したソースコード記載なの
でＣ言語に馴染んで無い読者様にも分かったと思いますが、
私は「Ｃ言語系言語」は「ポインタを使ってコソ本領発揮の
高速処理」と恒恒、説明して来たので蛇足ですが、
ポインタを使用した場合のソースコードも記載します！
ｃｏｄｅ：
int data[]={ // 初期値として元データを示します！
3,50,44,25,34,23,50,0,7,5,6,24,43,44,45,27,37,7,25,53,44,3,42,44,40,
42,44,40,8,7,37,27,44,46,48,20,25,23,0,44,49,26,27,34,42,49,37,33,
};
int* pData; // 上記配列をアクセスするポインタ
int hist[100]; // ヒストグラム結果格納配列：勿論、十分サイズ
// が大き目に必要です！
int* pHist; // 上記配列をアクセスするポインタ
int size; // 配列のサイズ
int i; // カウンター
int a; // データ最小値＝必要な配列添え字最小値
int b; // データ最大値＝必要な配列添え字最大値
// ヒストグラムを演算する範囲「a..b」を算出する
size = sizeof(data) / sizeof(int); // 配列のサイズを算出
pData = data; // ポインタを配列data先頭にセット
a = data[0]; // 初期値
b = a: // 初期値
for( i = 0; i < size; i++ ){ // data配列を全てナメル
int d = *pData++; // data配列からデータ取出＆進行
if( a > d ){ // お馴染みの最小値を算出する構文
a = d; //
}
if( b < d ){ // お馴染みの最大値を算出する構文
b = d; //
}
}
// ヒストグラム結果格納配列を初期化
pHist = &hist[a]; // ポインタをヒストグラム結果格納配
// 列の範囲「a」にセット
for( i = a; i <= b; i++ ){ // 範囲「a..b」内でループ
*pHist++ = 0; // ０クリア＆ポインタ進行
}
// ヒストグラムを演算
for( i = a; i <= b; i++ ){ // 範囲「a..b」内で演算
pHist = &hist[data[i]]; // ポインタをヒストグラム結果格納配列の
// 対象データdata[i]にセット
*pHist++; // ヒストグラム演算⇒対象の場所をカウント
// アップ
}これ等でヒストグラムを算出した所までは、理解して頂けた
と思います！
余り記載したく無いが、意外と「hist[data[i]]++;」の方が
高速な機械コードに変換され処理自体が速く成るコンパイラ
は存在します！
勿論、往々にしてポインタを使用した方がコンパクトで高速
なコードが出来る筈ですが、「意外と」と書いた様に昔、
確かに有った事は事実です！
（３）ヒストグラムデータから昇順（小さい方から大きい方へ）にソート
此処までの記載でソーティングする方法が分かった人は、
ヨッポド、ソート方法をアアでも無い・コウでも無いと
試行錯誤に苦しんだか、天才に近い！秀才的プログラマーと
思います！天才なら、ヒストグラムソートを説明し無くても
分かるでしょう？！
私は、秀才寄りの凡人プログラマーだったのでピント来なか
ったがと余計な事を言ってから解説します！では、
具体的に勿論、最小値は「a」＝「0」、
最大値は「b」＝「53」に成る事は、理解していると思い
ます！
では、最小値より一つ大きい値は、今回は「hist[0]」が
「2」とヒストグラムデータが２詰り、２個同じ値が有る
事が判ります！
だとすると最小値より一つ大きい値も「a」に成ります！
ココの意味が分かって貰え無いと次の説明以降が無駄に成り
ますので良く理解して下さい！
さて、その次は、「hist[1]」、「hist[2]」と
ヒストグラムデータが０、詰り、元のデータが無かった事を
示します！
そして「hist[3]」は、データが２個入っていますので
「a+3」＝「3」に成ります！
ヒツコイかも知れ無いが、理解して貰えたかな？！
次から、具体なソースコードを記載してソート結果
「int result[50];」に格納します！
「50」の値は、元のデータ数より十分大きな値です！
ｃｏｄｅ：
int data[]={ // 初期値として元データを示します！
3,50,44,25,34,23,50,0,7,5,6,24,43,44,45,27,37,7,25,53,44,3,42,44,40,
42,44,40,8,7,37,27,44,46,48,20,25,23,0,44,49,26,27,34,42,49,37,33,
};
int result[50]; // ソーティング結果格納配列
int hist[100]; // ヒストグラム結果格納配列：勿論、十分サイズ
// が大き目に必要です！
int i; // 配列の添え字用インデックス値
int j; // 結果格納配列の添え字用インデックス値
int a; // データ最小値＝必要な配列添え字最小値
int b; // データ最大値＝必要な配列添え字最大値
int size; // 配列のサイズ
// ヒストグラムを演算する範囲「a..b」を算出する
a = data[0]; // 初期値
b = a: // 初期値
size = sizeof(data) / sizeof(int); // 配列のサイズを算出
for( i = 0; i < size; i++ ){ // data配列を全てナメル
int d = data[i]; // data配列からデータ取出＆進行
if( a > d ){ // お馴染みの最小値を算出す
a = d; // る構文
}
if( b < d ){ // お馴染みの最大値を算出す
b = d // る構文
}
}
// ヒストグラム結果格納配列を初期化
for( i = a; i <= b; i++ ){ // 範囲「a..b」内でループ
hist[i] = 0; // ０クリア＆ポインタ進行
}
// ヒストグラムを演算
for( i = a; i <= b; i++ ){ // 範囲「a..b」内で演算
int d = data[i]; // data配列からデータ取出＆進行
hist[d]++; // ヒストグラム演算⇒対象の場所をカウント
// アップ
}
// ヒストグラムを結果を使用して元のデータを昇順に並び替える
j = 0; // 結果格納配列用インデックス
// 初期化
for( i = a; i <= b; i++ ){ // 範囲「a..b」内でループ
int c = hist[i]; // カウント値：ヒストグラム結果
// データ個別値取得
int k; // ローカルカウンタ
for( k = 0; k < c; k++ ){ // データ個別値分ループ
result[j++] = i; // 結果データを配列保存
}
}これで「result」に昇順（小⇒大）にソーティング（並び
替え）したデータが格納されます！
ソースコードを順にトレースして頂ければ分かるし、勿論、
コンパイラかベーシックの様なインタプリタで動作させて
見れば、分かると思います！
此処までは、数学的な配列を使用したソースコード記載なの
でＣ言語に馴染んで無い読者様にも分かったと思いますが、
私は「Ｃ言語系言語」は「ポインタを使ってコソ本領発揮の
高速処理」と恒恒、説明して来たので蛇足ですが、
ポインタを使用した場合のソースコードも記載します！
ｃｏｄｅ：
int data[]={ // 初期値として元データを示します！
3,50,44,25,34,23,50,0,7,5,6,24,43,44,45,27,37,7,25,53,44,3,42,44,40,
42,44,40,8,7,37,27,44,46,48,20,25,23,0,44,49,26,27,34,42,49,37,33,
};
int* pData; // 上記配列をアクセスするポインタ
int result[50]; // ソーティング結果格納配列
int* pResult; // 上記配列をアクセスするポインタ
int hist[100]; // ヒストグラム結果格納配列：勿論、十分サイズ
// が大き目に必要です！
int* pHist; // 上記配列をアクセスするポインタ
int i; // 配列の添え字用インデックス値
int a; // データ最小値＝必要な配列添え字最小値
int b; // データ最大値＝必要な配列添え字最大値
int c; // カウント値：ヒストグラム結果データ個別値
int size; // 配列のサイズ
// ヒストグラムを演算する範囲「a..b」を算出する
size = sizeof(data) / sizeof(int); // 配列のサイズを算出
pData = data; // ポインタを配列data先頭にセット
a = data[0]; // 初期値
b = a: // 初期値
for( i = 0; i < size; i++ ){ // data配列を全てナメル
int d = *pData++; // data配列からデータ取出＆進行
if( a > d ){ // お馴染みの最小値を算出する構文
a = d; //
}
if( b < d ){ // お馴染みの最大値を算出する構文
b = d; //
}
}
// ヒストグラム結果格納配列を初期化
pHist = &hist[a]; // ポインタをヒストグラム結果格納配
// 列の範囲「a」にセット
for( i = a; i <= b; i++ ){ // 範囲「a..b」内でループ
*pHist++ = 0; // ０クリア＆ポインタ進行
}
// ヒストグラムを演算
for( i = a; i <= b; i++ ){ // 範囲「a..b」内で演算
pHist = &hist[data[i]]; // ポインタをヒストグラム結果格納配列の
// 対象データdata[i]にセット
*pHist++; // ヒストグラム演算⇒対象の場所をカウント
// アップ
}
// ヒストグラムを結果を使用して元のデータを昇順に並び替える
pResult = result; // 結果格納配列へのポインタ先頭
// にセット
pHist = &hist[a]; // ポインタをヒストグラム結果格
// 配列の範囲「a」にセット
for( i = a; i <= b; i++ ){ // 範囲「a..b」内でループ
int c = *pHist++; // カウント値：ヒストグラム結果
// データ個別値取得
int k; // ローカルカウンタ
for( k = 0; k < c; k++ ){ // データ個別値分ループ
*pResult++ = i; // 結果データを配列保存
}
}ここで告白しよう？！実は、ヒストグラムソートの
ソースコードを作成したのは、初めてです？！何故か、
ランキングフィルターを実現する為にここで解説した
ヒストグラムソートが必要と冒頭で言ったと思いますから、
矛盾するのではと批判されるオッチョコチョイが読者様の
中に居ると思いますが、ランキングフィルターに必要なの
は、完全にデータをソーティングする事が必要で無く、
ランキングと言う文言で分かる様に「第何番目」の
データが、必要なのでコノ手法を使用したのです！
更に、「最も非効率なアルゴリズム」と冒頭付近で記載して
いた筈ですが、読者様の中には、意外とソーティング
アルゴリズムとして簡単で効率的に動作するので無いかと
誤解≪良く初心者向けソーティングで説明に使用される？！
所謂「Ｎ自乗ソート」と二重ループで構成される
アルゴリズムと大差無い≫と誤解された思慮の足ら無い
読者様も居るでしょう？！
今回、例文として使用したデータ
ｃｏｄｅ：
3 50 44 25 34 23 50 0 7 5 6 24 43 44 45 27 37 7 25 53 44 3 42 44 40
8 7 37 27 44 46 48 20 25 23 0 44 49 26 27 34 42 49 37 33は、「0」から「53」までの値とデータのバラツキが
少ない為、ヒストグラム（度数分布）を計算するのに使用
する配列が、「int hist[100];」と１００個サイズを用意
していますが、実際には５４個有れば、アルゴリズムとして
は動作します！
所が、実際にソーティングするデータの範囲が、抑々、
分からない場合、考えられるだけ、巨大サイズ、
例えば「unsigned int」詰り、符号無しの３２ビット
データならば、「int hist[4294967296];」が必要に成り
ますが実現無理でしょうから、実際に使う場合は、
データの最小値・最大値を把握してからプログラミングする
とか、では、現実的なソースコードも記載して見るか！
ｃｏｄｅ：
void SortOfHistogram( // 関数宣言：関数名「SortOfHistogram」
int data[], // 仮引数：ソートする元データ配列
int result[], // 仮引数：ソートされた結果データ配列
int size ); // データ配列のサイズ
int data[10000]; // 元のデータ配列
int result[10000]; // ソーティング結果格納配列
int size; // データ配列の実質的サイズ
// 「int data[10000]」と「int size」に何らかの手段でデータとその
// サイズを格納する☆これは、読者様が自分自身で作成して下さい☆
SortOfHistogram( data, result, size ); // ヒストグラムソート関数で
// 処理する
// result には、ソーティングされたデータが入っている筈なので
// 関数適応後は、昇順（小⇒大）に並べ替えている筈です！
// ヒストグラムソート関数本体ソースコードの記載
void SortOfHistogram( // 関数定義：関数名「SortOfHistogram」
int data[], // 仮引数：ソートする元データ配列
int result[], // 仮引数：ソートされた結果データ配列
int size // データ配列のサイズ
){ // 関数本体のブロックスタート
int* pData; // 元データ配列をアクセスするポインタ
int i; // 配列の添え字用インデックス値
int a; // データ最小値＝必要な配列添え字最小値
int b; // データ最大値＝必要な配列添え字最大値
int Hsize; // ヒストグラムデータ配列の必要サイズ
// ヒストグラムを演算する範囲「a..b」を算出する
pData = data; // ポインタを配列data先頭にセット
a = data[0]; // 初期値
b = a: // 初期値
for( i = 0; i < size; i++ ){ // data配列を全てナメル
int d = *pData++; // data配列からデータ取出＆進行
if( a > d ){ // お馴染みの最小値を算出する構文
a = d; //
} //
if( b < d ){ // お馴染みの最大値を算出する構文
b = d; //
} //
} //
Hsize = b - a + 1; // ヒストグラムデータ配列の
// 必要サイズを算出
// ヒストグラム結果格納配列を初期化
{ // 一段、内側にブロックを作成
new int hist[Hsize]; // ヒストグラム結果格納配列：勿論
// 動的に必要なサイズを確保
int* pHist; // ヒストグラムデータ配列をアクセ
// スするポインタ
pHist = hist; // ヒストグラムデータ配列先頭
for( i = 0; i < Hsize; i++ ){ // ヒストグラムデータ配列範囲内で
// ループ
*pHist++ = 0; // ０クリア＆ポインタ進行
} //
// ヒストグラムを演算
for( i = a; i <= b; i++ ){ // 範囲「a..b」内で演算
int d = data[i] - a; // data配列からデータ取出＆調整
pHist = &hist[d]; // ポインタをヒストグラム結果格納
// 配列の対象データdata[i]に
// セット
*pHist++; // ヒストグラム演算⇒対象の場所を
// カウントアップ
} //
// ヒストグラム結果を使用して元のデータを昇順に並び替える
pResult = result; // 結果格納配列へのポインタ先頭
// にセット
pHist = hist; // ヒストグラムデータ配列先頭
for( i = 0; i < Hsize; i++ ){ // ヒストグラム範囲内でループ
int c = *pHist++; // カウント値：ヒストグラム結果
// データ個別値取得
int k; // ローカルカウンタ
for( k = 0; k < c; k++ ){ // データ個別値分ループ
*pResult++ = i + a; // 結果データを配列保存
} //
} // 「new int hist[];」存在終了
}☆一寸、補足「new int hist[Hsize];」の構文は、
Ｃ言語では多分エラーに成ると思う？！
Ｃ＋＋言語やＣ＃で使える様に成る筈でＣ言語では
「int* hist;」とポインタ変数を定義した後で
「hist=new(Hsize*sizeof(int));」で動的にメモリ確保し
関数の最後に「free(hist);」とメモリーを開放しシステム
に返す操作が必要です☆
取り敢えず、今日は、ここまでの「ヒストグラムソート」の
紹介で終わりにします！
コンピュータプログラミングに馴れて無い読者様には、
理解するのに多少、時間が掛かると思えるからで！
冒頭で述べた、コペルニクス的転回を起こした
「ランキングフィルター」の件は、乞うご期待と言って置き
ます！
それでもセッカチな読者様には、画像処理ライブラリの
ソースコードの中にランキングフィルターが存在しますので
ダウンロードしてから、クラス「Filterフィルター」の
メソッド「RankingFilterランキングフィルター」＝
ファイルとしては、「Filter200.cpp」の中に入って居
ます！同じ名称で仮引数の違うバージョンも有るので全て
探して下さい！
老婆心ながら、この「ヒストグラムソート」のアルゴリズム
が、普通に高等数学に馴染みの無い読者様の中に
「再帰的定義」を使用する「クイックソート」等の
「二分岐」ソートの類より馴染みやすいループを数回≪
データ配列の最小値・最大値算出やヒストグラム結果配列
０クリアとヒストグラム計数処理及びヒストグラム（度数
分布）から結果データを算出する２重ループ≫
と比較的理解し易いと誤解し、更に例文で示した「0」
から「53」までのデータ配列では、比較的に効率良く処理が
完了したと思って居る！可能性が有り！
比較的、少数データ配列のソーティングに使用される
「Ｎ自乗ソート」依り、早く処理が終わると思った読者様も
いるでしょう！因みに以下に
【Ｎ自乗ソート】のアルゴリズムをＣ言語風に記載します！
ｃｏｄｅ：
int data[]={ // 初期値として元データを示します！
3,50,44,25,34,23,50,0,7,5,6,24,43,44,45,27,37,7,25,53,44,3,42,44,40,
42,44,40,8,7,37,27,44,46,48,20,25,23,0,44,49,26,27,34,42,49,37,33,
};
int i; // 配列の添え字用インデックス値その１
int j; // 配列の添え字用インデックス値その２
int d; // データ置き場
int size; // データ配列のサイズ
size = sizeof(data) / sizeof(int); // 配列のサイズ算出
for( i = 0; i < size; i++ ){ // お馴染みの配列全体を舐める
// 外側ループ構文
d = data[i]; // 外側ループでの値取得
for( j = i + 1; j < size; j++ ){ // 内側のループとして外より一回り
// 小さい配列を舐める
if( d > data[j] ){ // 外側データの方が大きい場合
d = data[j]; // 外側データを最小値で更新
} //
} //
data[i] = d; // 外側の配列の対象場所を更新
}お馴染みの「Ｎ自乗ソート」です！
一番内側の「ｉｆ構文」＝最小値判断は
Ｎ自乗のＮが「size変数」の値なので
約「size×size÷2」回実行され、「d=data[j];」と
最小値を更新する構文は、必要なだけ実行された事が分か
ると思います！知って居る人は知っていて少量のデータなら
上記で分かる様にシンプル≪ごく普通のコンピュータ
プログラミング技術者なら当然既知の筈≫なアルゴリズム
構造です！
今回の「data[]={3,50,44,・・・・37,33,」では、
私が「最も非効率なアルゴリズム」と紹介した
「ヒストグラムソート」の方が、効率的に処理出来る気が
します！
これでは、「コペルニクス的転回」を起こした前提が狂って
しまうのでデータを以下の様に
ｃｏｄｅ：
0 100000とすると「Ｎ自乗ソート」では、Ｎが「size変数」の
値＝２なので一回、「if(d>data[j]){」を実行し、
「d=data[j];」も０回だけ実行する事は理解できる
でしょう？！
コレを理解して頂けなければ、この解説は、無意味
お手上げに成ってしまいます！
さて、この状態で前述した
「SortOfHistogram(data,result,size;」を適応する
と「size」＝２で有るが、内部の「int Hsize;」詰り
ヒストグラム算出用配列のサイズが、「100000」に成り、
この配列に対する処理をループする回数が１０００００回に
成る事が分かるでしょう？！
コレで恐らく、私の思慮の出来る賢い読者様には、
「ヒストグラムソート」が不都合な場合が多々有る事≪
データにバラツキが有る場合≫が分かるでしょうし、抑々、
データが離散的（整数値とデジタル値）なデータしか、
直接的には想定して無いアルゴリズムで実数値（浮動小数点
数値）に関しては、有る程度の範囲をデータの区切りで
ヒストグラムを算出する等、特別な処置を施す必要が有る
方式です！
と上記までで解説した「ヒストグラムソート」が一般化し
普遍的に使用出来るソーティングアルゴリズムとしては、
非効率で不都合だと理解して頂いたと思います！
では、私が「コペルニクス的転回」を起こした
「ランキングフィルター」の件は、一寸、待ってね？！
乞うご期待と言って置きます！！！
解説エッセイ『ヒストグラムソートとランキングフィルター
続編』で記載予定です！