ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »配列操作
このページの記事一覧

【C#】 LowerBound, UpperBound (二分探索)  


 私は時折、頭の体操代わりにプロコン問題を解いたりしているのだが、使う言語はその時々で変えてるので、関数によっては無いと不便に思うものがある。LowerBound, UpperBound はその代表例かな。ものによっては BinarySearch でも同じ結果を得られるものもあるが、やはりあった方が良いので改めて書いておくことにした。内容的には JavaRuby 版と同じ。使い所を覚えれば、簡潔かつ高速に処理できるので、二分探索系のアルゴリズムは知っておいても損はないだろう。




■C# 版 LowerBound, UpperBound

using System;
using System.Collections.Generic;

/// <summary>
/// 指定した値以上の先頭のインデクスを返す
/// </summary>
/// <typeparam name="T">比較する値の型</typeparam>
/// <param name="arr">対象の配列(※ソート済みであること)</param>
/// <param name="start">開始インデクス [inclusive]</param>
/// <param name="end">終了インデクス [exclusive]</param>
/// <param name="value">検索する値</param>
/// <param name="comparer">比較関数(インターフェイス)</param>
/// <returns>指定した値以上の先頭のインデクス</returns>
public static int LowerBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
{
int low = start;
int high = end;
int mid;
while (low < high)
{
mid = ((high - low) >> 1) + low;
if (comparer.Compare(arr[mid], value) < 0)
low = mid + 1;
else
high = mid;
}
return low;
}

//引数省略のオーバーロード
public static int LowerBound<T>(T[] arr, T value) where T : IComparable
{
return LowerBound(arr, 0, arr.Length, value, Comparer<T>.Default);
}

/// <summary>
/// 指定した値より大きい先頭のインデクスを返す
/// </summary>
/// <typeparam name="T">比較する値の型</typeparam>
/// <param name="arr">対象の配列(※ソート済みであること)</param>
/// <param name="start">開始インデクス [inclusive]</param>
/// <param name="end">終了インデクス [exclusive]</param>
/// <param name="value">検索する値</param>
/// <param name="comparer">比較関数(インターフェイス)</param>
/// <returns>指定した値より大きい先頭のインデクス</returns>
public static int UpperBound<T>(T[] arr, int start, int end, T value, IComparer<T> comparer)
{
int low = start;
int high = end;
int mid;
while (low < high)
{
mid = ((high - low) >> 1) + low;
if (comparer.Compare(arr[mid], value) <= 0)
low = mid + 1;
else
high = mid;
}
return low;
}

//引数省略のオーバーロード
public static int UpperBound<T>(T[] arr, T value)
{
return UpperBound(arr, 0, arr.Length, value, Comparer<T>.Default);
}

 ついでに引数省略のオーバーロードも書いてあるが、実際にはもう何パターンかあった方が便利かも知れない(全要素+IComparer指定 / 範囲指定+IComparer省略など)。もし予め検索の範囲が絞りこめるなら、更に高速に処理できるので範囲指定はオススメだ。プロコン問題やリアルタイム処理が必要な高負荷アプリケーションなどでは積極的に使っていこう。

 ちなみに返ってくるインデクスは LowerBound は「指定した値以上の先頭のインデクス」で、UpperBound は「指定した値より大きい先頭のインデクス」になる。BinarySearch の場合は、値が見つかった場合はそのインデクスが返り、見つからないとき負の値となり、ビット反転することで「指定した値より大きい先頭のインデクス」が返る(つまり毎回正負を調べる必要がある)。完全一致の有無を調べるには BinarySearch の方が便利だが、一番近い値のインデクス見つけるなら LowerBound や UpperBound の方が便利だ。使い分けると良いだろう。

 以降は簡単な使用例なので、既に知っているなら読み飛ばしても良いだろう。



■いくつかの値の範囲で何番目の要素かを求める

 例えば以下のような表があり、「ある風速に対して風力を求める」問題があったとする。実際にこの問題は AtCoder の練習問題の一部を抜粋したものだが、色々な人の解答例を見ていると(AtCoderyukicoder などは他の人の解答を見れるので勉強になる)、逐次検索または if 文で頭から値を比較しているものが圧倒的に多い。しかしこの表のように単調増加なものなら、二分検索が使えると考えて良い。この場合は UpperBound を使うと簡単だ。

風力風速
風力00.0m⁄s 以上 0.2m⁄s 以下
風力10.3m⁄s 以上 1.5m⁄s 以下
風力21.6m⁄s 以上 3.3m⁄s 以下
風力33.4m⁄s 以上 5.4m⁄s 以下
風力45.5m⁄s 以上 7.9m⁄s 以下
風力58.0m⁄s 以上 10.7m⁄s 以下
風力610.8m⁄s 以上 13.8m⁄s 以下
風力713.9m⁄s 以上 17.1m⁄s 以下
風力817.2m⁄s 以上 20.7m⁄s 以下
風力920.8m⁄s 以上 24.4m⁄s 以下
風力1024.5m⁄s 以上 28.4m⁄s 以下
風力1128.5m⁄s 以上 32.6m⁄s 以下
風力1232.7m⁄s 以上

●UpperBound を使っての解答例
//※・・・関数などは略・・・

//表の各要素の開始の風速を配列にしたもの
double[] WindPower = {
0.0, 0.3, 1.6, 3.4, 5.5, 8.0, 10.8, 13.9, 17.2, 20.8, 24.5, 28.5, 32.7
};

double ms = 15.3; //※与えられた風速とする(m/s)
int wp = UpperBound(WindPower, ms) - 1;
Console.WriteLine("風速" + wp);

風速7

 実はこの問題の場合は BinarySearch でも事足りる。しかし BinarySearch の場合、値が見つかった時と見つからなかったときで処理を分岐する必要があり、冗長となることも多い。

●Array.BinarySearchを使っての解答例
//※・・・関数などは略・・・

//表の各要素の開始の風速を配列にしたもの
double[] WindPower = {
0.0, 0.3, 1.6, 3.4, 5.5, 8.0, 10.8, 13.9, 17.2, 20.8, 24.5, 28.5, 32.7
};

double ms = 15.3; //※与えられた風速とする(m/s)
int wp = Array.BinarySearch(WindPower, ms);
Console.WriteLine("風速" + (wp < 0 ? ~wp - 1 : wp)); //見つからなかったときビット反転(~)するとUpperBoundと同じになる

風速7

 実際にはこの問題くらいの要素数なら逐次検索でも構わないのだが、要素数が何千とあったり、60fpsで動作するゲームなどでフレーム毎で使用する必要などあった場合、検索回数を大幅に減らせるので効果はてきめんとなる。



■検索する値の個数を求める

 次によくあるパターンだが、ある数が連続して並んでいるとき、その範囲や個数を調べる方法などもある。例えば以下のような表があったとき、「2~4 の値を持つインデクスの範囲とその要素数を求めたい」としよう。一番初めに思い浮かぶアルゴリズムは先頭から検索していき、2 が出てきた所で開始インデクスを記録、4 より上の値が出てきた所で終了インデクスを記録するといった感じだろうか。開始と終了の差を取ればその個数もわかる。しかし、ここでは LowerBound, UpperBound を使ってみよう。

Index[0][1][2][3][4][5][6][7][8][9][10][11][12]
Value0011122344455

//※・・・関数などは略・・・

int[] arr = {0, 0, 1, 1, 1, 2, 2, 3, 4, 4, 4, 5, 5}; //表
int low = 2; //検索する最小値
int high = 4; //検索する最大値
int from = LowerBound(arr, low); //検索する最小値で最初のインデクス
int to = UpperBound(arr, high); //検索する最大値を超えた最初のインデクス
Console.WriteLine("from = " + from + ", to = " + to + ", count = " + (to - from));

from = 5, to = 11, count = 6

 この例も要素数が少ない場合は逐次検索でもそれほど大差ないが、何千・何万という要素数でなら、圧倒的な速さとなる。



 私の見たところ、実際の開発現場でのコードでも逐次検索は多用されている感じがあるので、データが単調増加ないし単調減少なら二分探索を取り入れると良いと思う。確実に高速化できるし、もしデータを順に並べて良いものなら、予めリアルタイムにソート済みデータを作っていくアルゴリズムを組んでおけば、何かと便利なことが多い(Ruby 版だが「ソート済み配列を作る」方法もある[※C# なら List にすると良い])。

 この辺りは慣れだと思うが、常に検索回数を減らせるような工夫を忘れないようにすれば、paizaCodeIQ などの上級者問題(A, S ランク)も解けるようになる(タイムアウトしなくなる)。挑戦してみると良いだろう。


(関連記事)
【Ruby】二分探索, lower_bound, upper_bound
【Java】lower_bound(), upper_bound() 関数を作る
【Java】二分探索を汎用的に使えるようにする


■参考になる書籍


スポンサーサイト

category: C#

thread: プログラミング

janre: コンピュータ

tag: C#ライブラリ  配列操作  二分探索 
tb: 0   cm: --

【C#】連想配列(Dictionary)を値 or キーでソート  


 このテーマはググればいくらでも出てくるので、どちらかというと自分用メモ。先に述べてしまうと、初めの LINQ 的な書き方が一番簡単だろう。ただ、他の方法もあったので、それも少しまとめてみた感じ。色々な書き方を知っておくと、他言語に移植するとき等にも役に立つからだ。




■IEnumerable でのソート (LINQ)

 LINQ (System.Linq) が使えるなら、とりあえずこれを使うのが一番楽だろう。内容的には Enumerable(IEnumerable) を使うことになる。キーでのソートも、値でのソートもプロパティを変えるだけで同様にできる。

●値でのソート (IEnumerable)
using System;
using System.Collections.Generic;
using System.Linq;

Dictionary<string, int> dic = new Dictionary<string, int>() {
{ "Becky", 85 },
{ "Daisy", 72 },
{ "Alice", 95 },
{ "Eliza", 78 },
{ "Cindy", 100 },
};

var sorted = dic.OrderBy((x) => x.Value); //昇順
//var sorted = dic.OrderByDescending((x) => x.Value); //降順

foreach (var v in sorted)
{
Console.WriteLine(v.Key + " => " + v.Value);
}

Daisy => 72
Eliza => 78
Becky => 85
Alice => 95
Cindy => 100

 コメントアウトの方は降順になる。キーでのソートはソート対象を変えるだけで良い(x.Value → x.Key に変更)。

●キーでのソート (IEnumerable)
var sorted = dic.OrderBy((x) => x.Key);  //昇順
//var sorted = dic.OrderByDescending((x) => x.Key); //降順

Alice => 95
Becky => 85
Cindy => 100
Daisy => 72
Eliza => 78




■KeyValuePair の List でのソート (ラムダ式)

 これはキーと値のペア(KeyValuePair)のリストを作って、それをソートする方法だ。他の言語でもよく使われる方法なので、覚えておくと役に立つ。List.Sort() はラムダ式が使えるようなので、簡潔に書くことも可能だ。

●値でのソート (KeyValuePair の List と ラムダ式)
using System;
using System.Collections.Generic;

Dictionary<string, int> dic = new Dictionary<string, int>() {
{ "Becky", 85 },
{ "Daisy", 72 },
{ "Alice", 95 },
{ "Eliza", 78 },
{ "Cindy", 100 },
};

List<KeyValuePair<string, int>> list = new List<KeyValuePair<string, int>>(dic);
list.Sort((a, b) => a.Value - b.Value); //昇順
//list.Sort((a, b) => b.Value - a.Value); //降順

foreach (var v in list)
{
Console.WriteLine(v.Key + " => " + v.Value);
}

Daisy => 72
Eliza => 78
Becky => 85
Alice => 95
Cindy => 100

 コメントアウトの方は降順になる。キーでのソートはソート対象を変えるだけで良い(x.Value → x.Key に変更)。なお、比較には CompareTo() を使っている。

●キーでのソート (KeyValuePair の List と ラムダ式)
list.Sort((a, b) => a.Key.CompareTo(b.Key));  //昇順
//list.Sort((a, b) => b.Key.CompareTo(a.Key)); //降順

Alice => 95
Becky => 85
Cindy => 100
Daisy => 72
Eliza => 78




■KeyValuePair の List でのソート (delegate)

 これは上記のラムダ式版の別表記と言っても良いのだが、改めて delegate を使えると覚えておくと、例えば、リアルタイムにソート方法を変更するような実装もできると考えることができる。まぁ、引き出しは多いことに越したことはない。

●値でのソート (KeyValuePair の List と delegate)
using System;
using System.Collections.Generic;

Dictionary<string, int> dic = new Dictionary<string, int>() {
{ "Becky", 85 },
{ "Daisy", 72 },
{ "Alice", 95 },
{ "Eliza", 78 },
{ "Cindy", 100 },
};

List<KeyValuePair<string, int>> list = new List<KeyValuePair<string, int>>(dic);
list.Sort(delegate(KeyValuePair<string, int> a, KeyValuePair<string, int> b) {
return a.Value - b.Value; //昇順
//return b.Value - a.Value; //降順
});

foreach (var v in list)
{
Console.WriteLine(v.Key + " => " + v.Value);
}

Daisy => 72
Eliza => 78
Becky => 85
Alice => 95
Cindy => 100

 コメントアウトの方は降順になる。キーでのソートはソート対象を変えるだけで良い(x.Value → x.Key に変更)。なお、比較には CompareTo() を使っている。

●キーでのソート (KeyValuePair の List と delegate)
list.Sort(delegate(KeyValuePair<string, int> a, KeyValuePair<string, int> b) {
return a.Key.CompareTo(b.Key); //昇順
//return b.Key.CompareTo(a.Key); //降順
});

Alice => 95
Becky => 85
Cindy => 100
Daisy => 72
Eliza => 78




■KeyValuePair の List でのソート (IComparer)

 ICompare(Comparer) も使えるのでやってみよう。このような比較関数(クラス)は他の言語でもよくあるので、移植もしやすい。ちなみに以前書いた Java での連想配列(Map)でのソートと全く同じ構成となる。

●値(or キー)でのソート (KeyValuePair の List と IComparer)
using System;
using System.Collections.Generic;

public static void Main()
{
Dictionary<string, int> dic = new Dictionary<string, int>() {
{ "Becky", 85 },
{ "Daisy", 72 },
{ "Alice", 95 },
{ "Eliza", 78 },
{ "Cindy", 100 },
};

List<KeyValuePair<string, int>> list = new List<KeyValuePair<string, int>>(dic);
list.Sort(new MyComparer<string, int>());

foreach (var v in list)
{
Console.WriteLine(v.Key + " => " + v.Value);
}
}

//比較クラス(関数)
public class MyComparer<K,V> : IComparer<KeyValuePair<K,V>>
where K : IComparable
where V : IComparable
{
public int Compare(KeyValuePair<K,V> a, KeyValuePair<K,V> b) {
return a.Value.CompareTo(b.Value); //値 昇順
//return b.Value.CompareTo(a.Value); //値 降順
//return a.Key.CompareTo(b.Key); //キー 昇順
//return b.Key.CompareTo(a.Key); //キー 降順
}
}

Daisy => 72
Eliza => 78
Becky => 85
Alice => 95
Cindy => 100

 上記の例では1つのクラスでまとめてしまったため、型パラメーターの制約を複数書いてしまっているが、値のみ(V)・キーのみ(K)とわかっているなら、制約はどちらかだけでも良い。同じようなことは delegate 版でもできると思うが、1つのクラスにまとめた利点としては、プロパティなどを追加して、いつでもソート方法を変更できる・同じソート方法を共有できること等にある。用途に合わせて使い分けるのも良いだろう。




■キーと値の2つの配列でのソート

 もう1つ、今回の連想配列のテーマからは少し外れるのだが、C# には「ソート対象となる1次元配列と、その項目に対応する別の1次元配列」をソートできる Array.Sort(Array, Array) がオーバーロードされている。まるで連想配列をソートするような感じになる。

●キーと値の2つの配列でのソート
using System;
using System.Collections.Generic;

public static void Main()
{
string[] name = {"Alice", "Becky", "Cindy", "Daisy", "Eliza"};
int[] value = {95, 85, 100, 72, 78};

Array.Sort(value, name); //昇順
//Array.Sort(value, name, new RevComparer<int>()); //降順

for (int i = 0; i < value.Length; i++)
{
Console.WriteLine(name[i] + " => " + value[i]);
}
}

//逆順(降順)
public class RevComparer<T> : IComparer<T> where T : IComparable
{
public int Compare(T a, T b) {
return b.CompareTo(a); //降順
}
}

Daisy => 72
Eliza => 78
Becky => 85
Alice => 95
Cindy => 100

 引数は Array.Sort(ソート対象の配列, 対応する配列, [IComparer]) となっている。

 ちなみに、コメントアウトされている「RevComparer」(逆順用 Comparer) で降順ソートすると結果は以下のようになる。

Cindy => 100
Alice => 95
Becky => 85
Eliza => 78
Daisy => 72

 ソートのキーとなる配列と値の配列(項目に対応する配列)は別々に作るので、型に自由が利くのが特徴だ。値の配列は何でも良いので、クラスや構造体の配列などをソートすることもできる。普段はクラスや構造体でデータを保持しておいて、ソートしたいときだけキーとなる配列を生成する等もできるだろう。

 Comparer(RevComparer)などもあらかじめ static で作っておけば(int など利用頻度が高い型を別に作っておけば)、毎回 new しなくて済むので実行速度がはやくなる。色々工夫してみると良いだろう。


(関連記事)
【C#】2次元配列(ジャグ配列・多次元配列)のソート
【C#】多次元配列とジャグ配列(2次元配列)のサイズ(長さ)、相互変換など


category: C#

thread: プログラミング

janre: コンピュータ

tag: C#  連想配列  配列操作  ソート 
tb: 0   cm: --

【C#】2次元配列(ジャグ配列・多次元配列)のソート  


 C#には「ジャグ配列」と「多次元配列」があるのだが、結論を先に言ってしまうと、ソートするならジャグ配列の方が簡単である。というのは初めから用意されている方法が色々あるからだ。では多次元配列はどうかというと、特に用意はされていないので自作することになる。なので、標準的な機能と一般的なソートアルゴリズムとを使って、いくつかの方法でソートをやってみよう。




■ジャグ配列でのソート

 まずジャグ配列の動作を確認しておこう。ジャグ配列とは配列の入れ子状態で、「親の次元は子の次元のオブジェクトの参照を持っている」と考えれば良い。今回の場合2次元配列なので、一番親の配列はそれぞれの配列の参照を格納にしている感じになる。つまりその参照を交換すれば1行分のデータ(配列)を交換したことと同じことになる。図のように考えた場合、縦方向のソート(列をキーに行をソート)となることがわかる。これは他の言語でもだいたい同じなので、覚えておくと色々と応用が利く。





●ジャグ配列でのソート (ラムダ式)
using System;
using System.Text;

//ジャグ配列
int[][] jag = {
new int[] {0, 1, 200},
new int[] {1, 3, 100},
new int[] {2, 4, 100},
new int[] {3, 2, 300},
new int[] {4, 0, 200},
};

Array.Sort(jag, (a, b) => a[1] - b[1]); //昇順(index=1)

Console.WriteLine(ToString(jag)); //デバッグ用関数(※下記を参照)

[[4, 0, 200],
[0, 1, 200],
[3, 2, 300],
[1, 3, 100],
[2, 4, 100]]

(※) ToString(T[][]) は前回作った関数を参照(配列の内容を文字列化→表示するだけのもの)

 ラムダ式の書き方だといまいちアルゴリズムがわかりずらいが、やっていることは上の図と同じと考えて良いだろう。もっとコードの意味を知りたいなら、以下に示す「Comparer」での書き方の方がわかりやすい。実行速度などの違いはあるかもしれないが、ラムダ式だと簡潔に書けることが利点だ。

 ちなみに、ソート第2キーを加えたいなら、ソート関数部分を次のように書くこともできる。これも「Comparer」での書き方と比較すると意味がわかりやすい。用途によって書き分けると良いだろう。

Array.Sort(jag, (a, b) => a[2] == b[2] ? a[1] - b[1] : b[2] - a[2]);  //降順(index=2), 昇順(index=1)

[[3, 2, 300],
[4, 0, 200],
[0, 1, 200],
[1, 3, 100],
[2, 4, 100]]

 これはインデクス[2]の列は降順に、インデクス[1]の列は昇順にしてソートしている(ソート第1キー:[2]が同じなら、ソート第2キー:[1]でソートする)。



●ジャグ配列でのソート (LINQ)
using System;
using System.Linq;

//ジャグ配列
var jag = new [] {
new [] {0, 1, 200},
new [] {1, 3, 100},
new [] {2, 4, 100},
new [] {3, 2, 300},
new [] {4, 0, 200},
};

var sorted = jag.OrderBy(e => e[1]); //昇順(index=1)

foreach (var s in sorted) {
foreach (var e in s) {
Console.Write(e + ", ");
}
Console.WriteLine();
}

4, 0, 200,
0, 1, 200,
3, 2, 300,
1, 3, 100,
2, 4, 100,

 これは先の例のラムダ式と同じ結果となる。型を必要としないなら、この方法でも良いだろう。「using System.Linq」が必要なので忘れずに。

 ちなみに、降順なら「OrderByDescending」を使う。また、「OrderBy~」で同じ値になる場合は「ThenBy/ThenByDescending」で順をつけることができる。つまり第2キーを加えたいなら、以下のようにする。

var sorted = jag.OrderByDescending(e => e[2]).ThenBy(e => e[1]);  //降順(index=2), 昇順(index=1)

3, 2, 300,
4, 0, 200,
0, 1, 200,
1, 3, 100,
2, 4, 100,

 これはインデクス[2]の列は降順に、インデクス[1]の列は昇順にしてソートしている(ソート第1キー:[2]が同じなら、ソート第2キー:[1]でソートする)。



●ジャグ配列でのソート (IComparer, IComparable)
using System;
using System.Collections.Generic;
using System.Text;

//比較クラス(比較関数)
public class MyComparer<T> : IComparer<T[]> where T : IComparable
{
public int Compare(T[] a, T[] b) {
return a[1].CompareTo(b[1]); //昇順
//return b[1].CompareTo(a[1]); //降順
}
}

public static void Main()
{
//ジャグ配列
int[][] jag = {
new int[] {0, 1, 200},
new int[] {1, 3, 100},
new int[] {2, 4, 100},
new int[] {3, 2, 300},
new int[] {4, 0, 200},
};

Array.Sort(jag, new MyComparer<int>());

Console.WriteLine(ToString(jag)); //デバッグ用関数(※下記を参照)
}

[[4, 0, 200],
[0, 1, 200],
[3, 2, 300],
[1, 3, 100],
[2, 4, 100]]

(※) ToString(T[][]) は前回作った関数を参照(配列の内容を文字列化→表示するだけのもの)

 「Comparer」「IComparer」「IComparable」と同じようなものが並んでいてややこしいが、「Comparer」は IComparer などを実装しているクラス、「IComparer」は「Compare()」(比較関数)を使うためのインターフェース、「IComparable」は「CompareTo()」(大小関係を返す関数)を使うためのインターフェースと覚えておけば良いだろう。比較関数は基本的に戻値が正の値だと a > b、負の値だと a < b、0だと a == b を表すと考えれば良い(要するに a - b)。ただこれは昇順の場合であって、降順(逆順)にしたければ、大小を反転(b - a)すれば良いことになる。これも他の言語でも使えることが多いので、覚えておくと役に立つ。

 ついでにこれもソート第2キーを加えてみよう。この場合は比較クラス(関数)の MyComparer にだけ変更を加えれば良い。プロジェクト共有で使用している等なら、一度にすべてのソート方法を変更できるメリットもある。ラムダ式版と合わせて使い分けをすると良いだろう。

●比較クラス(関数)に第2キーを加える
//比較クラス(比較関数)
public class MyComparer<T> : IComparer<T[]> where T : IComparable
{
public int Compare(T[] a, T[] b) {
if (a[2].CompareTo(b[2]) == 0) //第1キーが同じなら
{
return a[1].CompareTo(b[1]); //第2キー:昇順
}
return b[2].CompareTo(a[2]); //第1キー:降順
}
}

[[3, 2, 300],
[4, 0, 200],
[0, 1, 200],
[1, 3, 100],
[2, 4, 100]]

 内容的にはラムダ式版の第2キーを加えたものと同じものになる。Compare() 関数内は if 文で書いているが、ラムダ式のときのように三項演算子(条件演算子)で return しても良い。ただ if 文なら第3キーや特殊な条件を加えたくなったとき、非常に簡単に書ける利点がある。

 どちらの書き方が良いというわけでなく、保守性・拡張性を考えるか、一発簡潔に書くか等、用途によって使い分けるのが良いだろう。




■多次元配列でのソート (クイックソート)

 多次元配列でのソートは初めから用意されてはいないので、ここからは一般的なソートアルゴリズムを用いた方法になる。多次元配列は内部的にはひとつづきなので、要素ごとに交換しなくてはならないことに注意しよう。

 また、2次元配列の場合は縦方向(列をキーに行をソート)と横方向(行をキーに列をソート)の2つがあるが、とりあえずはジャグ配列版と比較のためにも縦方向のソートで書いてみよう。

●2次元配列(多次元配列)のクイックソート(縦方向)
using System;
using System.Collections.Generic;
using System.Text;

//2次元配列のクイックソート(縦方向)
public static void QuickSortRow<T>(T[,] arr, int sortIndex, int first, int last, IComparer<T> comp)
{
int i = first; //前方検索インデクス
int j = last; //後方検索インデクス
T p = Median(arr[i, sortIndex], arr[(j - i) / 2 + i, sortIndex], arr[j, sortIndex], comp);
int col = arr.GetLength(1);

while (true)
{
while (comp.Compare(arr[i, sortIndex], p) < 0) { //基準値以上の位置まで前方検索
i++;
}
while (comp.Compare(arr[j, sortIndex], p) > 0) { //基準値以下の位置まで後方検索
j--;
}
if (i >= j) { //交差したら終了
break;
}

//スワップ
for (int k = 0; k < col; k++) {
T tmp = arr[i, k];
arr[i, k] = arr[j, k];
arr[j, k] = tmp;
}

i++;
j--;
}

//基準値より2分割して再帰呼び出し(2分割できないときは再帰停止)
if (first < i - 1) {
QuickSortRow(arr, sortIndex, first, i - 1, comp);
}
if (j + 1 < last) {
QuickSortRow(arr, sortIndex, j + 1, last, comp);
}
}

//独自の Comparer(IComparer)用
public static void QuickSortRow<T>(T[,] arr, int sortIndex, IComparer<T> comp)
{
QuickSortRow(arr, sortIndex, 0, arr.GetLength(0) - 1, comp);
}

//既定の Comparer(IComparer)用
public static void QuickSortRow<T>(T[,] arr, int sortIndex) where T : IComparable
{
QuickSortRow(arr, sortIndex, 0, arr.GetLength(0) - 1, Comparer<T>.Default);
}

//x, y, z の中央値を返す
public static T Median<T>(T x, T y, T z, IComparer<T> comp)
{
if (comp.Compare(x, y) < 0)
{
if (comp.Compare(y, z) < 0) return y;
else if (comp.Compare(z, x) < 0) return x;
else return z;
}
else
{
if (comp.Compare(z, y) < 0) return y;
else if (comp.Compare(x, z) < 0) return x;
else return z;
}
}


public static void Main()
{
//多次元配列
int[,] grid = {
{0, 1, 200},
{1, 3, 100},
{2, 4, 100},
{3, 2, 300},
{4, 0, 200},
};

QuickSortRow(grid, 1);
Console.WriteLine(ToString(grid)); //デバッグ用関数(※下記を参照)
}

[[4, 0, 200],
[0, 1, 200],
[3, 2, 300],
[1, 3, 100],
[2, 4, 100]]

(※) ToString(T[,]) は前回作った関数を参照(配列の内容を文字列化→表示するだけのもの)

 クイックソートのアルゴリズムは、Wikipedia でも見て欲しい。コードも実装例を2次元配列用に改造したものである。実は以前に書いた Java 版(横方向)の焼き直しだったりもする。

 なお、基準値(p : Pivot) は簡略のために、検索範囲の最初と最後の値を加算して2で割る方法(平均値)でも良い。ここではジェネリック型で作っているので、Wikipedia に載っている med3 関数(中間値[中央値])を使っている(ジェネリック型で演算はできないので)。このピボットの値をどう取るかで効率が変わるので色々研究されているらしい。実際には元の並びにもよるのでやりやすいものを使えば良いだろう。

 また注意点としては、このクイックソートは安定ソートではないので、同値の場合は、他の列の並びは不定になる。他の列の順序も考慮に入れたいのなら、安定ソートのものでソート関数内に第2ソートキー比較などを入れる工夫が必要になるだろう。挿入ソートを2回使う手もある。ユニーク値や連番なら問題はない。

 逆順(降順)にしたいなら、以下の Comparer を使えば良い。

●逆順(降順)の Comparer を定義して使う
//逆順(降順)
public class RevComparer<T> : IComparer<T> where T : IComparable
{
public int Compare(T a, T b) {
return b.CompareTo(a); //降順
}
}

//メインでは...
QuickSortRow(grid, 1, new RevComparer<int>());

[[2, 4, 100],
[1, 3, 100],
[3, 2, 300],
[0, 1, 200],
[4, 0, 200]]




■多次元配列でのソート (挿入ソート)

 もう1つ、安定ソートを使いたいときのために、挿入ソートも書いておこう。といってもこれも以前 Java で書いた「2次元配列の挿入ソート(横方向)」の焼き直しである。縦と横の方向を入れ替えただけなので、難しくはないだろう。

●2次元配列(多次元配列)の挿入ソート(縦方向)
using System;
using System.Collections.Generic;
using System.Text;

//2次元配列の挿入ソート(縦方向)
public static void InsertionSortRow<T>(T[,] arr, int sortIndex, IComparer<T> comp)
{
int row = arr.GetLength(0);
int col = arr.GetLength(1);
T[] tmp = new T[col];

for (int i = 1; i < row; i++)
{
T t = arr[i, sortIndex];
if (comp.Compare(arr[i - 1, sortIndex], t) > 0)
{
//列の退避
for (int k = 0; k < col; k++)
{
tmp[k] = arr[i, k];
}

//上へずらす
int j = i;
do {
for (int k = 0; k < col; k++)
{
arr[j, k] = arr[j - 1, k];
}
j--;
} while (j > 0 && comp.Compare(arr[j - 1, sortIndex], t) > 0);

//列のストア
for (int k = 0; k < col; k++)
{
arr[j, k] = tmp[k];
}
}
}
}

//既定の Comparer(IComparer)用
public static void InsertionSortRow<T>(T[,] arr, int sortIndex) where T : IComparable
{
InsertionSortRow(arr, sortIndex, Comparer<T>.Default);
}


public static void Main()
{
//多次元配列
int[,] grid = {
{0, 1, 200},
{1, 3, 100},
{2, 4, 100},
{3, 2, 300},
{4, 0, 200},
};

InsertionSortRow(grid, 1); //昇順
//InsertionSortRow(grid, 1, new RevComparer<int>()); //降順
Console.WriteLine(ToString(grid)); //デバッグ用関数(※下記を参照)
}

[[4, 0, 200],
[0, 1, 200],
[3, 2, 300],
[1, 3, 100],
[2, 4, 100]]

(※) ToString(T[,]) は前回作った関数を参照(配列の内容を文字列化→表示するだけのもの)

 逆順(降順)にしたい場合は、RevComparer を使う。安定ソートなので、2回以上のソート(別々のキー[列]で)しても、並びは保持されるので、第2, 3,…ソートキーを使うのと同じ効果になる(※ただし、効率は良くない)。




■多次元配列→ジャグ配列 変換してソート

 これは、多次元配列では内部的にはひとつづきのため、要素ごとに処理する必要があるので、いっそのことジャグ配列に変換してしまおうという方法だ。

 「多次元配列→ジャグ配列 変換」は以前に作ったものをそのまま使う。あとは「ジャグ配列でのソート」と同じだ。

●多次元配列→ジャグ配列 変換(→前回作ったもの)してからソート
using System;
using System.Collections.Generic;
using System.Text;

/**
* 多次元配列をジャグ配列に変換
*/
public static T[][] ToJaggedArray<T>(T[,] arr)
{
int row = arr.GetLength(0);
int col = arr.GetLength(1);

T[][] jag = new T[row][];

for (int i = 0; i < row; i++)
{
jag[i] = new T[col];
for (int j = 0; j < col; j++)
{
jag[i][j] = arr[i, j];
}
}

return jag;
}


public static void Main()
{
//多次元配列
int[,] grid = {
{0, 1, 200},
{1, 3, 100},
{2, 4, 100},
{3, 2, 300},
{4, 0, 200},
};

int[][] jag = ToJaggedArray(grid); //多次元配列→ジャグ配列 変換
Array.Sort(jag, (a, b) => a[1] - b[1]); //昇順(index=1)
//Array.Sort(jag, (a, b) => b[1] - a[1]); //降順(index=1)
Console.WriteLine(ToString(jag)); //デバッグ用関数(※下記を参照)
}

[[2, 4, 100],
[1, 3, 100],
[3, 2, 300],
[0, 1, 200],
[4, 0, 200]]

(※) ToString(T[][]) は前回作った関数を参照(配列の内容を文字列化→表示するだけのもの)

 まぁ、はじめからジャグ配列を使うのが一番楽だが、負荷が許せるなら、変換するのもアリだろう。




■キーと値の2つの配列でのソート

 もう1つ、今回の2次元配列のテーマからは少し外れるのだが、C# には「ソート対象となる1次元配列と、その項目に対応する別の1次元配列」をソートできる Array.Sort(Array, Array) がオーバーロードされている。まるで連想配列をソートするような感じになる。

using System;
using System.Collections.Generic;

string[] name = {"Alice", "Becky", "Cindy", "Daisy", "Eliza"};
int[] value = {95, 85, 100, 72, 78};

Array.Sort(value, name); //昇順
//Array.Sort(value, name, new RevComparer<int>()); //降順

for (int i = 0; i < name.Length; i++)
{
Console.WriteLine(name[i] + " => " + value[i]);
}

Daisy => 72
Eliza => 78
Becky => 85
Alice => 95
Cindy => 100

 引数は Array.Sort(ソート対象の配列, 対応する配列, [IComparer]) となっている。

 ちなみに、コメントアウトされている「RevComparer」(逆順用 Comparer) で降順ソートすると結果は以下のようになる。

Cindy => 100
Alice => 95
Becky => 85
Eliza => 78
Daisy => 72

 ソートのキーとなる配列と値の配列(項目に対応する配列)は別々に作るので、型に自由が利くのが特徴だ。値の配列は何でも良いので、クラスや構造体の配列などをソートすることもできる。普段はクラスや構造体でデータを保持しておいて、ソートしたいときだけキーとなる配列を生成する等もできるだろう。

 Comparer(RevComparer)などもあらかじめ static で作っておけば(int など利用頻度が高い型を別に作っておけば)、毎回 new しなくて済むので実行速度がはやくなる。色々工夫してみると良いだろう。


(関連記事)
【C#】多次元配列とジャグ配列(2次元配列)のサイズ(長さ)、相互変換など
【C#】連想配列(Dictionary)を値 or キーでソート


■参考になる書籍


category: C#

thread: プログラミング

janre: コンピュータ

tag: C#  配列操作  ソート 
tb: 0   cm: --

【C#】多次元配列とジャグ配列(2次元配列)のサイズ(長さ)、相互変換など  


 Java では2次元配列はジャグ配列になるのだが、C#には「多次元配列」と「ジャグ配列」の選択肢がある。使う時は微妙に概念やプロパティなどが違うので、簡単な図解で理解し、相互変換などをやってみよう。




■概念・サイズなどのプロパティ

 「多次元配列とジャグ配列の違いは?」を超簡単に説明すると「多次元配列はデータを格子状に並べた配列」「ジャグ配列は個々の配列を更に並べた配列(入れ子の配列)」でいいと思う。そんな感じで理解してしまえば、「Length」や「GetLength()」の使い方がよくわかる。以下にそれぞれの違いを図解してみよう。



■多次元配列とは

 とりあえず「データを格子状に並べた配列」と考えれば良い。図解にすると以下のようになる。


●多次元配列
using System;
using System.Collections.Generic;
using System.Text;

public static void Main(){
//多次元配列
int[,] grid = {
{ 0, 1, 2, 3, 4},
{ 5, 6, 7, 8, 9},
{10, 11, 12, 13, 14},
};

Console.WriteLine(ToString(grid)); //デバッグ用関数(※下記を参照)
Console.WriteLine("Length = " + grid.Length);
Console.WriteLine("GetLength(0) = " + grid.GetLength(0));
Console.WriteLine("GetLength(1) = " + grid.GetLength(1));
Console.WriteLine("grid[2, 3] = " + grid[2, 3]);
}

[[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14]]
Length = 15
GetLength(0) = 3
GetLength(1) = 5
grid[2, 3] = 13

(※) ToString(T[,]) は下記を参照

 各次元のサイズは、

 GetLength(次元数)

になる。例では2次元配列になっているが、3次元配列なら GetLength(0~2) のようになる。

 そして「Lengthは全体の要素数」になるので注意しよう。ひとつづきのデータが格子状に並んでいるだけと考えればわかりやすいだろう。3次元以上になったときも同じように考えれば良い。ちなみに「foreach」で列挙すれば図のような並びで出てくる。

foreach (int i in grid) Console.Write(i + " ");

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

 また、実際にメモリ上でもひとつづきに領域が確保されており、ポインタで連続処理するのに利用することもできる。そういった処理の場合はジャグ配列より多次元配列の方が良いだろう。以下に参考URLを載せておこう。

(参考)
多次元配列の速度比較
C#のジャグ配列・多次元配列をpin_ptrでC++に渡せるか?




■ジャグ配列とは

 とりあえず「個々の配列を更に並べた配列(入れ子の配列)」と考えれば良い。図解にすると以下のようになる。


●ジャグ配列
using System;
using System.Collections.Generic;
using System.Text;

public static void Main(){
//ジャグ配列
int[][] jag = {
new int[] { 0, 1, 2, 3, 4},
new int[] { 5, 6, 7},
new int[] {10, 11, 12, 13},
};

Console.WriteLine(ToString(jag)); //デバッグ用関数(※下記を参照)
Console.WriteLine("Length = " + jag.Length);
Console.WriteLine("GetLength(0) = " + jag.GetLength(0)); //= jag.Length
Console.WriteLine("jag[0].Length = " + jag[0].Length);
Console.WriteLine("jag[1].Length = " + jag[1].Length);
Console.WriteLine("jag[2].Length = " + jag[2].Length);
Console.WriteLine("jag[2][3] = " + jag[2][3]);
}

[[0, 1, 2, 3, 4],
[5, 6, 7],
[10, 11, 12, 13]]
Length = 3
GetLength(0) = 3
jag[0].Length = 5
jag[1].Length = 3
jag[2].Length = 4
jag[2][3] = 13

(※) ToString(T[][]) は下記を参照

 次にジャグ配列だが、図のように個々の配列が、更にまとめられて1つの配列にされていると考えれば良い。なので多次元配列と違って個々の配列の長さは自由になる(Length はそれぞれのサイズになる)。なので例えば「隣接リスト」などに使えばメモリの節約にもなる(隣接行列ならどちらでも良い)。メモリ上でも配列ごとに違う領域に割り当てられると考えて良いだろう(システムが勝手に割り当てる)。例では1次元配列が入れ子になっているが、親の次元はオブジェクトの参照を要素としている(この例の場合は各配列の頭[0])ので、中身は何でも良い(型が邪魔なら object 配列などにすれば良い→ボックス化のようになる)。




■多次元配列→ジャグ配列 変換

 LINQ を使っても良いのかも知れないが、とりあえず今回は概念の図をそのままコーディングするという感じで、ついでにジェネリクスで書いておこう。こういう書き方はダサいかも知れないが(笑)、用途に合わせて改造しやすい利点がある。引数などを追加したバージョンも作りやすいしね。他の言語にも移植しやすい。ちなみに Java ではジェネリクスで new はできないので移植する際には注意しよう。

using System;
using System.Collections.Generic;
using System.Text;

/**
* 多次元配列をジャグ配列に変換
*/
public static T[][] ToJaggedArray<T>(T[,] arr)
{
int row = arr.GetLength(0);
int col = arr.GetLength(1);

T[][] jag = new T[row][];

for (int i = 0; i < row; i++)
{
jag[i] = new T[col];
for (int j = 0; j < col; j++)
{
jag[i][j] = arr[i, j];
}
}

return jag;
}


//メインでは...
int[,] grid = {
{ 0, 1, 2, 3, 4},
{ 5, 6, 7, 8, 9},
{10, 11, 12, 13, 14},
};

int[][] jag = ToJaggedArray(grid);
Console.WriteLine(ToString(jag)); //デバッグ用関数(※下記を参照)
Console.WriteLine("Length = " + jag.Length);
Console.WriteLine("GetLength(0) = " + jag.GetLength(0)); //= jag.Length
Console.WriteLine("jag[0].Length = " + jag[0].Length);
Console.WriteLine("jag[1].Length = " + jag[1].Length);
Console.WriteLine("jag[2].Length = " + jag[2].Length);

[[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14]]
Length = 3
GetLength(0) = 3
jag[0].Length = 5
jag[1].Length = 5
jag[2].Length = 5

(※) ToString(T[][]) は下記を参照




■ジャグ配列→多次元配列 変換

using System;
using System.Collections.Generic;
using System.Text;

/**
* ジャグ配列を多次元配列に変換
* col : 列数
*/
public static T[,] ToDimensionalArray<T>(T[][] arr, int col)
{
int row = arr.Length;

T[,] dim = new T[row, col];

for (int i = 0; i < row; i++)
{
for (int j = 0; j < arr[i].Length && j < col; j++)
{
dim[i, j] = arr[i][j];
}
}

return dim;
}

//最大の col(列数)で多次元配列に変換
public static T[,] ToDimensionalArray<T>(T[][] arr)
{
int row = arr.Length;
int col = 0;

//最大を取得
for (int i = 0; i < row; i++)
{
col = Math.Max(col, arr[i].Length);
}

return ToDimensionalArray(arr, col);
}


//メインでは...
int[][] jag = {
new int[] { 0, 1, 2, 3, 4},
new int[] { 5, 6, 7, 8, 9},
new int[] {10, 11, 12, 13, 14},
};

int[,] grid = ToDimensionalArray(jag);
Console.WriteLine(ToString(grid)); //デバッグ用関数(※下記を参照)
Console.WriteLine("Length = " + grid.Length);
Console.WriteLine("GetLength(0) = " + grid.GetLength(0));
Console.WriteLine("GetLength(1) = " + grid.GetLength(1));

[[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14]]
Length = 15
GetLength(0) = 3
GetLength(1) = 5

(※) ToString(T[,]) は下記を参照

 引数を1つとる関数の方はオーバーロード用で、ジャグ配列は個々の長さが違う可能性があるため、列の最大を取得している。長さが違う場合、列の最大に満たない要素は型の既定値で初期化される。作りたい多次元配列の列数がわかっている場合は、引数を2つとる関数の方の col に具体的な値を入れた方が速い。列の長さが同じとわかってるなら以下のようにしても良い。

int[,] grid = ToDimensionalArray(jag, jag[0].Length);





■文字列化

 これはどちらかというとデバッグ用なのだが、よく使うので書いておこう。ただ配列の中身を確認するためのものだ。

using System;
using System.Collections.Generic;
using System.Text;

//文字列変換用
static StringBuilder sb = new StringBuilder(1024);

/**
* 2次元配列の文字列化(多次元配列)
*/
public static string ToString<T>(T[,] arr, string sep = ", ", string rowSep = "\n",
string start_bracket = "[", string end_bracket = "]")
{
sb.Length = 0;
sb.Append(start_bracket);
for (int i = 0; i < arr.GetLength(0); i++) {
if (i > 0) {
sb.Append(sep);
sb.Append(rowSep);
}

sb.Append(start_bracket);

for (int j = 0; j < arr.GetLength(1); j++)
{
if (j > 0)
{
sb.Append(sep);
}
sb.Append(arr[i, j]);
}
sb.Append(end_bracket);
}
sb.Append(end_bracket);

return sb.ToString();
}

/**
* 2次元配列の文字列化(ジャグ配列)
* ※Totring<T>(T[])と曖昧エラーとなるので注意
*/
public static string ToString<T>(T[][] arr, string sep = ", ", string rowSep = "\n",
string start_bracket = "[", string end_bracket = "]")
{
sb.Length = 0;
sb.Append(start_bracket);
for (int i = 0; i < arr.Length; i++) {
if (i > 0) {
sb.Append(sep);
sb.Append(rowSep);
}

sb.Append(start_bracket);

for (int j = 0; j < arr[i].Length; j++)
{
if (j > 0)
{
sb.Append(sep);
}
sb.Append(arr[i][j]);
}
sb.Append(end_bracket);
}
sb.Append(end_bracket);

return sb.ToString();
}

 1つだけ注意点は、1次元配列用に「ToString<T>(T[] arr, ~)」を新たに作った場合、ジャグ配列の「ToString<T>(T[][] arr, ~)」と曖昧エラー(「The call is ambiguous between the following methods or properties: ~」)が出るかも知れない。これは T を int として int[][] と解釈、または、T を int[] として int[][] とも解釈できるからだ。その場合は関数をリネームなどして別々に使えば良い。


(関連記事)
【C#】2次元配列(ジャグ配列・多次元配列)のソート
【C#】連想配列(Dictionary)を値 or キーでソート


category: C#

thread: プログラミング

janre: コンピュータ

tag: C#  配列操作 
tb: 0   cm: --

【Ruby】二分探索, lower_bound, upper_bound  


 Ruby2.3 以降には見つけた値のインデクスを返す Array.bsearch_index() があるのだが、自作した方が使い勝手が良いことも多いので、Java 版をそのまま移植してみた。


なお、組み込み関数の場合は以下のようになる。

●Ruby の bsearch_index で lower_bound, upper_bound 的な動作 (Ruby 2.3以降)
     #[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3;
lower = arr.bsearch_index{|x| x >= v} #lower_bound 的(ただし、見つからない=nil) (Ruby 2.3以降)
upper = arr.bsearch_index{|x| x > v} #upper_bound 的(ただし、見つからない=nil) (Ruby 2.3以降)
print "lower = #{lower}\n"
print "upper = #{upper}\n"

lower = 2
upper = 5

 値の意味は lower_bound 的な方は「指定した値以上の先頭の要素を返す」ことになるので、配列 arr 内で v = 3 が続く値の先頭インデクス = 2 を、upper_bound 的な方は「指定した値より大きい先頭の要素を返す」ことになるので、v = 3 が続く値より後ろのインデクス = 5 という意味になる。

 ちなみに Array.bsearch() の方は要素の値そのものを返す。今回の関数と組み込み関数との大きな違いは、値が見つからないとき nil (組み込み関数)か、近いインデクスを返す(今回の関数)かという感じだ。実は見つからないとき値を返すようにしておくと、色々利用できるのでわざわざ Java から(元はC++) 移植したわけだ。

●二分探索:binary_search, lower_bound, upper_bound (オープンクラス版)
#オープンクラス版
class Array
#二分探索(同値連続はインデクス不定となる)
#見つからないとき=負の値となり、~index で挿入位置になる
def binary_search(value, from = 0, to = self.size)
low = from
high = to - 1
while low <= high
mid = (low + high) / 2
if self[mid] < value
low = mid + 1
elsif self[mid] > value
high = mid - 1
else
return mid
end
end
-(low + 1) #見つからない(~index で挿入位置)
end

#指定した値以上の先頭のインデクスを返す
def lower_bound(value, from = 0, to = self.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if self[mid] < value
low = mid + 1
else
high = mid
end
end
low
end

#指定した値より大きい先頭のインデクスを返す
def upper_bound(value, from = 0, to = self.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if self[mid] <= value
low = mid + 1
else
high = mid
end
end
low
end

end


#メインでは...
#[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3; #検索する値
print "binary_search = #{arr.binary_search(v)}\n"
print "lower_bound = #{arr.lower_bound(v)}\n"
print "upper_bound = #{arr.upper_bound(v)}\n"

print "bsearch_index(lower) = #{arr.bsearch_index{|x| x >= v}}\n" #lower_bound 的(ただし、見つからない=nil) (Ruby 2.3)
print "bsearch_index(upper) = #{arr.bsearch_index{|x| x > v}}\n" #upper_bound 的(ただし、見つからない=nil) (Ruby 2.3)

binary_search = 3
lower_bound = 2
upper_bound = 5
bsearch_index(lower) = 2
bsearch_index(upper) = 5

 意味は組み込み関数の例とだいたい同じになる。違いは値が見つからないときの戻値だ。例えば検索する値を v = 2 とすると、組み込み関数の場合 nil となるが、lower_bound()、upper_bound() は 2 となる。binary_search() の場合は -3 という値が返るが、この値はビット反転すると(~index = ~(-3))2 となる。つまり、binary_search() の場合、同値が連続しているとき、どのインデクスになるかは不定だが、負の値が返ってきたとき見つからなかったことがわかるので、処理分岐がしやすい利点がある。

 また、Ruby には関数のオーバーロードがないので、検索範囲を決める引数(from = 開始インデクス、to = 終了インデクス[このインデクスは含まない] はデフォルト値を設定してある(デフォは配列の最初から最後まで)。検索するインデクス範囲がわかっているなら、絞り込めば更に高速に動作する。余談だが、範囲を決める引数を関数に持たせる場合、終了インデクスは「含まない」としておくと、差分計算や連続検索などしやすくなる(標準ライブラリ等もだいたいそうなっている)。

 あと lower_bound() も upper_bound() も要素の最大より上の値を検索すれば、配列の長さと同じ値が返ってくる(例えば、v = 9 とすれば、どちらもインデクス = 15 が返る)。これらは値が見つからないとき、配列の最後に値を追加するのに使える。この方法を使えば、リアルタイムにソート済み配列を作ることも可能だ。試しにやってみよう。

●二分探索でソート済み配列を作る
arr = [3, 5, 6, 4, 2, 0, 8, 7, 1, 9]
sorted = []

arr.each{|e|
sorted.insert(sorted.upper_bound(e), e)

# sorted.insert(sorted.lower_bound(e), e)

# idx = sorted.binary_search(e)
# if idx < 0
# idx = ~idx
# end
# sorted.insert(idx, e)
}

p arr
p sorted

[3, 5, 6, 4, 2, 0, 8, 7, 1, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 この場合は binary_search(), lower_bound(), upper_bound() どれを使っても同じになる。しかし実際には同値がある場合、binary_search() は同値の中ではそのどこかに、lower_bound() の場合は同値の先頭に、upper_bound() の場合は同値の一番最後(=検索値の次の値の先頭)に挿入されることになる。追加順序が必要な場合は使い分けた方が良いだろう。もちろんこの例の場合は最後にソート(Array.sort())でも良いが、リアルタイムに追加・削除を繰り返す場合は、何度もソートするより負荷が軽くなる。

 もう1つ、lower_bound() と upper_bound() を上手く使う例として、指定範囲内の値の個数を求めてみよう。

●lower_bound() と upper_bound() で検索範囲内の値の個数を求める
arr = [0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 9, 9]

lo, hi = 1, 3 #検索する値の範囲
fr = arr.lower_bound(lo) #開始インデクスを表す
to = arr.upper_bound(hi) #終了インデクスを表す[このインデクスは含まない]

p arr
print "fr = #{fr}, to = #{to}, cnt = #{to - fr}\n" #差分が個数
p arr.slice(fr, to - fr) #範囲を抜き出し

[0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 6, 6, 6, 7, 8, 9, 9]
fr = 3, to = 17, cnt = 14
[1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3]

 この例は配列の中から、検索する値 = 1~3 のインデクス範囲(3~17 [17は含まない])を取得し、差分から個数を求めている。Array.slice() はおまけでその範囲を抜き出して表示しているだけだ。もちろんこのくらいの数なら逐次検索でもそれほど差がないかも知れないが、要素数が多くなると効果はてきめんとなる。

 最後にオープンクラスで使いたくない人のためにも通常のメソッドでも書いておこう。内容は全く同じになるので、好きな方を使えば良い。

●二分探索:binary_search, lower_bound, upper_bound (通常メソッド版)
#二分探索(同値連続はインデクス不定となる)
#見つからないとき=負の値となり、~index で挿入位置になる
def binary_search(arr, value, from = 0, to = arr.size)
low = from
high = to - 1
while low <= high
mid = (low + high) / 2
if arr[mid] < value
low = mid + 1
elsif arr[mid] > value
high = mid - 1
else
return mid
end
end
-(low + 1) #見つからない(~index で挿入位置)
end

#指定した値以上の先頭のインデクスを返す
def lower_bound(arr, value, from = 0, to = arr.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if arr[mid] < value
low = mid + 1
else
high = mid
end
end
low
end

#指定した値より大きい先頭のインデクスを返す
def upper_bound(arr, value, from = 0, to = arr.size)
low = from
high = to
while low < high
mid = (low + high) / 2
if arr[mid] <= value
low = mid + 1
else
high = mid
end
end
low
end


#メインでは...
#[0][1][2][3][4][5][6][7][8][9[10[11[12[13[14]
arr = [1, 1, 3, 3, 3, 4, 5, 5, 6, 6, 6, 6, 7, 8, 8];
v = 3; #検索する値

print "binary_search = #{binary_search(arr, v)}\n"
print "lower_bound = #{lower_bound(arr, v)}\n"
print "upper_bound = #{upper_bound(arr, v)}\n"

s, e = 3, 6 #検索する値の範囲
fr = lower_bound(arr, s)
to = upper_bound(arr, e)
print "fr = #{fr}, to = #{to}, cnt = #{to - fr}\n"

binary_search = 3
lower_bound = 2
upper_bound = 5
fr = 2, to = 12, cnt = 10


 オンラインジャッジの問題でも上級レベルになるほど、逐次検索では計算量が間に合わずタイムアウトしやすくなる。CodeIQ でも paiza でもランク A, S(★★★★)問題には必要となるシーンも多いので、使える場合は積極的に使ってみると良いだろう(要するに単純な昇順・降順データ・累積和・フィボナッチのような増加数列には使った方が安全)。標準ライブラリにあるものでも、その実装に近いものを知っていれば柔軟に対応できるようになるので、色々改造して使うと良いだろう。


(関連記事)
【Java】lower_bound(), upper_bound() 関数を作る
【Java】二分探索を汎用的に使えるようにする


■参考になる書籍


category: Ruby

thread: プログラミング

janre: コンピュータ

tag: 配列操作  二分探索 
tb: 0   cm: --


プロフィール

Twitter

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR

▲ Pagetop