FC2ブログ
ヽ|∵|ゝ(Fantom) の 開発blog? ホーム »C#
カテゴリー「C#」の記事一覧

【C#】二分探索の実装(範囲インデクス指定実装)  


 ただの実装用メモ。元々標準ライブラリで BinarySearch は実装されているので(配列も同様)、利用するだけなら、自分で実装する必要はない。ちょっと改造して、検索を高速化したいときにアルゴリズムだけ利用することもあるので(Java の標準ライブラリはすぐ実装見れるが、C# の標準ライブラリってメタデータだけだったりするので)、確認用に書いておくだけ(笑)。

●インデクスで範囲指定の二分探索の実装
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>0 以上のとき見つかったインデクス / 0 より小さいとき ~index (ビット反転)で挿入位置になる</returns>
public static int BinarySearch<T>(this List<T> list, int start, int end, T value, IComparer<T> comparer)
{
int low = start;
int high = end - 1;
int mid;
while (low <= high)
{
mid = ((high - low) >> 1) + low;
if (comparer.Compare(list[mid], value) < 0)
{
low = mid + 1;
}
else if (comparer.Compare(list[mid], value) > 0)
{
high = mid - 1;
}
else
{
return mid;
}
}
return -(low + 1);
}

//引数省略のオーバーロード
public static int BinarySearch<T>(this List<T> list, int start, int end, T value)
{
return BinarySearch(list, start, end, value, Comparer<T>.Default);
}

 実際には以前に書いた、LowerBound, UpperBound(配列で実装してるが、List でも同じ)と BinarySearch を使い分けると便利だったりする。大きな違いは検索結果のインデクスの値で、例えば BinarySearch では同値が並んでいるとどのインデクスになるかは不定だが、LowerBound を使うと同値の最初のインデクス、UpperBound を使うと同値の最後の次のインデクスとなる(「検索する値の個数を求める」の例がわかり易いと思う)。

 私の場合、一部のプロパティを二分探索で検索するために(例えば常にインクリメントする ID 番号など)、上記の実装を少し改造して使うことも多い。大量にデータが増えたとき、二分探索はその効果を発揮する(よく FindIndexFirstOrDefault で実装されている場合も多いが、逐次検索なので大量のデータには向かない)。LowerBound, UpperBound と共に使えば、かなりの高速化ができるので、色々やってみると良いだろう。





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


スポンサーサイト



category: C#

thread: プログラミング

janre: コンピュータ

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

【C#】【Unity】enum 型と string, int 型の相互変換など  


 enum 型をファイルに保存したり、UIなどのインデクスに対応させたりと、相互変換するとき確認したいことが多くあるので、備忘録的にまとめておいた。今回は通常の C# として書いているが、Unity などでも使用することは多いので、ちょっとしたトラブルシューティングなどもついでに。どちらかというとリファレンス的な使い方になると思うので、解説は少なめに凡例を列挙しておこう。


(※) mono-4.2.1 (C#6, CLI4.5)[paiza.io] / Unity 5.6.3p1 - 2018.1.5f1 / Windows10(x64) で確認



■enum → string 変換
using System;

enum BloodType //※enum 型は任意
{
A, B, O, AB
}

//enum → string 変換
BloodType bloodType = BloodType.A;
string str = bloodType.ToString();

Console.WriteLine(str);

A

 または以下のようにも書ける。
string str = Enum.GetName(typeof(BloodType), bloodType);

Console.WriteLine(str);

A




■string → enum 変換
using System;

enum BloodType //※enum 型は任意
{
A, B, O, AB
}

//string → enum 変換
string str = "B"; //"b" でも可
BloodType bloodType = (BloodType)Enum.Parse(typeof(BloodType), str, true); //true = IgnoreCase

Console.WriteLine(bloodType);

B

 ちょっと試しに IgnoreCase のオプションを外して小文字にしてみると、System.ArgumentException が出る。
string str = "b";
//↓このコードはエラーが出ます。
BloodType bloodType = (BloodType)Enum.Parse(typeof(BloodType), str); //System.ArgumentException

Console.WriteLine(bloodType);

System.ArgumentException




■enum → int 変換
using System;

enum BloodType //※enum 型は任意
{
A, B, O, AB
}

//enum → int 変換
BloodType bloodType = BloodType.AB;
int i = (int)bloodType;

Console.WriteLine(i);

3




■int → enum 変換
using System;

enum BloodType //※enum 型は任意
{
A, B, O, AB
}

//int → enum 変換
int i = 3;
BloodType bloodType = (BloodType)Enum.ToObject(typeof(BloodType), i);

Console.WriteLine(bloodType);

AB

 試しに範囲外の値を入れてみると、そのまま整数値が出てくる。
//int → enum 変換
int i = 4; //範囲外の値
BloodType bloodType = (BloodType)Enum.ToObject(typeof(BloodType), i);

Console.WriteLine(bloodType);

4




■enum の名前の配列を取得
using System;

enum BloodType //※enum 型は任意
{
A, B, O, AB
}

string[] names = Enum.GetNames(typeof(BloodType));

Console.WriteLine(string.Join(", ", names));

A, B, O, AB




■enum の値(enum)の配列オブジェクト(Array)を取得
using System;

enum BloodType //※enum 型は任意
{
A, B, O, AB
}

Array values = Enum.GetValues(typeof(BloodType));

foreach (var item in values) {
Console.WriteLine(item + " = " + (int)item);
}

A = 0
B = 1
O = 2
AB = 3




■enum を long 型で使う
using System;

enum LongRange : long //※enum 型は任意
{
Min = long.MinValue,
Num = 123456789L,
Max = long.MaxValue,
}

long min = (long)LongRange.Min; //キャストが必要
long num = (long)LongRange.Num; //キャストが必要
long max = (long)LongRange.Max; //キャストが必要

Console.WriteLine(min);
Console.WriteLine(num);
Console.WriteLine(max);

-9223372036854775808
123456789
9223372036854775807




■enum の値割当と Unity インスペクタのずれを直す(Unity トラブルシューティング)

 例えば以下のような列挙型があったとき、途中から "Banana" を削除したくなったとしよう。しかし、コメントアウトで消したとするとそれぞれに割り当てられれた値がずれ、インスペクタでの表示(名前)も変わってしまう。

public enum Hoge  //※enum 型は任意
{
Apple,
//Banana,
Cat,
Dog,
}
public Hoge hoge;

 これは、コメントアウト前は {Apple = 0, Banana = 1, Cat = 2, Dog = 3} であったのに対し、コメントアウト後は {Apple = 0, Cat = 1, Dog = 2} になるために出る症状なので、以下のように値を直接割り当てれば、元の並びと同じになる。

public enum Hoge  //※enum 型は任意
{
Apple,
//Banana,
Cat = 2,
Dog,
}
public Hoge hoge;

 また列挙型はデフォルトでは0からの整数連番だが、値は自由に割り当てられるので、飛び番号や負の値なども使える。色々やってみると良いだろう。



■enum の PlayerPrefs 保存と読み込み(Unity)

 Unity でユーザーデータとして enum 型の保存と読み込みをやってみよう。といっても内容的には先に述べた「enum←→stringの相互変換」をやっているだけである。ここでは Load と Save の機能を持ったメソッドを2つ作ったとする。シーンに UI-Button を2つ置いて、それぞれの OnClick() で呼び出すなどすれば、簡単に確認できるだろう。

using System;
using UnityEngine;

public enum Hoge { //※enum 型は任意
Apple,
Banana,
Cat,
Dog,
}
public Hoge hoge = Hoge.Apple;

string prefsName = "hoge";

public void LoadHoge() //UI-Button の OnClick に登録する等
{
string str = PlayerPrefs.GetString(prefsName, hoge.ToString());
hoge = (Hoge)Enum.Parse(typeof(Hoge), str);

Debug.Log("Loaded : " + hoge);
}

public void SaveHoge() //UI-Button の OnClick に登録する等
{
PlayerPrefs.SetString(prefsName, hoge.ToString());
PlayerPrefs.Save();

Debug.Log("Saved : " + hoge);
}

(インスペクタで「Banana」を選んで保存・読み込みをした場合)
Saved : Banana
Loaded : Banana

 ちなみに int 型で保存と読み込みをする場合には以下のように書ける。

・・・(略)・・・
public void LoadHoge()
{
int i = PlayerPrefs.GetInt(prefsName, (int)hoge);
hoge = (Hoge)Enum.ToObject(typeof(Hoge), i);

Debug.Log("Loaded : " + hoge + " (" + i + ")");
}

public void SaveHoge()
{
PlayerPrefs.SetInt(prefsName, (int)hoge);
PlayerPrefs.Save();

Debug.Log("Saved : " + hoge + " (" + (int)hoge + ")");
}
・・・(略)・・・

(インスペクタで「Banana」を選んで保存・読み込みをした場合)
Saved : Banana (1)
Loaded : Banana (1)

 stringint のどちらでも良いが、後から値の割当を変えたくなったときにも対応できるように、string 型で保存しておいた方が無難ではあるだろう(※public で宣言してる場合、後から変更するとインスペクタでの名前表示のずれが発生するので注意)。


(関連記事)
【Java】enum を int で取得する
【Java】文字列を enum 型に変換する
【Unity】色形式:Unity の Color と Android の ARGB(int32) の相互変換をする


category: C#

thread: プログラミング

janre: コンピュータ

tag: C#リファレンス  Unityトラブルシューティング 
tb: 0   cm: --

【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 ランク)も解けるようになる(タイムアウトしなくなる)。挑戦してみると良いだろう。





(関連記事)
【C#】二分探索の実装(範囲インデクス指定実装)
【Ruby】二分探索, lower_bound, upper_bound
【Java】lower_bound(), upper_bound() 関数を作る
【Java】二分探索を汎用的に使えるようにする


category: C#

thread: プログラミング

janre: コンピュータ

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

【C#】倍数での Floor, Ceil, Round(一定間隔での切り捨て、切り上げ、四捨五入) [double 版]  



 通常の Floor, Ceil, Round は小数の位を切り捨てたり切り上げたりして1ごとの整数にするものだが、5ごとの値とか10の倍数(下1桁を揃える)にしたいと思うことも少なくない。

 ゲームなどで一定間隔の座標に揃えたり、値の下n桁を0したいときなど応用範囲は広いので、毎回書くくらいなら簡単なライブラリとして作っておこう。





■nの倍数で切り捨てる(nおきの数に切り捨てる)

●double 版 MultipleFloor()
using System;

/// <summary>
/// より小さい倍数を求める(倍数で切り捨てられるような値)
///(例)倍数 = 10 のとき、12 → 10, 17 → 10
/// </summary>
/// <param name="value">入力値</param>
/// <param name="multiple">倍数</param>
/// <returns>倍数で切り捨てた値</returns>
public static double MultipleFloor(double value, double multiple)
{
return Math.Floor(value / multiple) * multiple;
}


//メインでは…
Console.WriteLine("5 -> " + MultipleFloor(5, 10)); //0
Console.WriteLine("12 -> " + MultipleFloor(12, 10)); //10
Console.WriteLine("27 -> " + MultipleFloor(27, 10)); //20

(例)n を10おきに切り捨てる(下1桁を0にする)
 5, 12, 27 → 0, 10, 20

(例)n を5おきに切り捨てる
 5, 12, 27 → 5, 10, 25




■nの倍数で切り上げる(nおきの数に繰り上げる)

●double 版 MultipleCeil()
using System;

/// <summary>
/// より大きい倍数を求める(倍数で繰り上がるような値)
///(例)倍数 = 10 のとき、12 → 20, 17 → 20
/// </summary>
/// <param name="value">入力値</param>
/// <param name="multiple">倍数</param>
/// <returns>倍数で切り上げた値</returns>
public static double MultipleCeil(double value, double multiple)
{
return Math.Ceiling(value / multiple) * multiple;
}


//メインでは…
Console.WriteLine("5 -> " + MultipleCeil(5, 10)); //10
Console.WriteLine("12 -> " + MultipleCeil(12, 10)); //20
Console.WriteLine("27 -> " + MultipleCeil(27, 10)); //30

(例)n を10おきに切り上げる(倍数で繰り上げる)
 5, 12, 27 → 10, 20, 30

(例)n を5おきに切り上げる
 5, 12, 27 → 5, 15, 30




■nの倍数で四捨五入のような値を求める(nおきの数の中間の値で切り捨て・切り上げをする)

●double 版 MultipleRound()
using System;

/// <summary>
/// 倍数での四捨五入のような値を求める(nおきの数の中間の値で切り捨て・切り上げをする)
///(例)倍数 = 10 のとき、12 → 10, 17 → 20
/// </summary>
/// <param name="value">入力値</param>
/// <param name="multiple">倍数</param>
/// <returns>倍数の中間の値で、切り捨て・切り上げした値
public static double MultipleRound(double value, double multiple)
{
return MultipleFloor(value + multiple * 0.5, multiple); //四捨五入的
//return Math.Round(value / multiple) * multiple; //五捨六入的(正の数のとき)
}


//メインでは…
Console.WriteLine("5 -> " + MultipleRound(5, 10)); //10
Console.WriteLine("12 -> " + MultipleRound(12, 10)); //10
Console.WriteLine("27 -> " + MultipleRound(27, 10)); //30

(例)n を10おきに切り捨て・切り上げる(10の中間の5を閾値として切り捨て・切り上げをする:4→0, 5→10)
 5, 12, 27 → 10, 10, 30

(例)n を5おきに切り捨て・切り上げる(5の中間の2.5を閾値として切り捨て・切り上げをする:2.4→0, 2.5→5)
 5, 12, 27 → 5, 10, 25

 1つだけ注意点は MultipleRound() に関しては、関数内部で MultipleFloor() を使っている点だ。これは C# の Math.Round() の丸め方はどちらかと言うと五捨六入に近いので、他の言語に移植などするとき、そのままでは結果が異なってしまうため、Round(v) の代わりに Floor(v + 0.5) を使っている。この辺りは C# 限定で Math.Round の仕様に則った値にしたいなら、コメントアウトしてある方を使っても良いだろう。他の言語との Round の値の違いは以下のページの一覧やフォーラムなどを参照して欲しい。

Java, C#, PHP, Ruby, Python, JavaScript での Math.round(四捨五入・五捨六入)比較
Math.Roundって五捨六入?


(関連記事)
【Unity】倍数での Floor, Ceil, Round(一定間隔での切り捨て、切り上げ、四捨五入) [float 版]
 Java, C#, PHP, Ruby, Python, JavaScript での Math.round(四捨五入・五捨六入)比較
【Java】Math.floor(), ceil(), round() 動作互換アルゴリズムを試す


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: --


プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR