- C#, C♯, C＃相談室 Part85
649 ：デフォルトの名無しさん[]：2014/12/13(土) 01:50:46.98 ID:y9otNf+T - ソートの話なんだけど、ちょっとご相談。
例えば以下のようなkey-valueペアがあったとする。
int[] key = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
int[] val = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
keyには同じ値が入る可能性があって、valは単なる順番を表してるだけ。
んで、やりたいことは基本的にはkeyを降順でソートすることなんだけど、
もし同じ値があった場合にどちらが先になるかはランダムにしたいわけ。
まず、これをLINQで解決した例を示しとく。
public static IEnumerable<int> OrderingDescending<T>(this IEnumerable<T> self, Random random)
{
IEnumerable<int> order = Enumerable.Range(0, self.Count());
Tuple<int, T>[] merge = new Tuple<int, T>[self.Count()];
for (int i = 0; i < self.Count(); i++)
{
merge[i] = Tuple.Create(Enumerable.ElementAt(order, i), Enumerable.ElementAt(self, i));
}
return merge.OrderByDescending(tuple => tuple.Item2).ThenBy(tuple => random.Next()).Select(tuple => tuple.Item1);
}
【サンプルコード】
Random random = new Random(0);
val = key.OrderingDescending(random).ToArray();
Console.WriteLine(val.ToStringExtension());
random = new Random(1);
val = key.OrderingDescending(random).ToArray();
Console.WriteLine(val.ToStringExtension());
【実行結果】
{ 5 7 4 8 2 9 0 6 3 1 }
{ 5 7 8 4 2 0 9 6 1 3 }
ちなみにソートされたkeyは
{ 9 6 5 5 4 3 3 2 1 1 }
| - C#, C♯, C＃相談室 Part85
650 ：デフォルトの名無しさん[]：2014/12/13(土) 02:04:02.56 ID:y9otNf+T - んで、じゃーやりたいことは何なのかというと、
これをArray.Sortを使って実現したいんだよね。
普通の降順のソートであれば
public class DescendingComparer : IComparer<int>
{
public int Compare(int x, int y)
{
return -x.CompareTo(y);
}
}
っていうのを定義すれば
【サンプルコード】
DescendingComparer descendingComparer = new DescendingComparer();
//Array.Sort(key, val, descendingComparer);
//Console.WriteLine(key.ToStringExtension());
//Console.WriteLine(val.ToStringExtension());
【実行結果】
{ 9 6 5 5 4 3 3 2 1 1 }
{ 5 7 4 8 2 0 9 6 1 3 }
っていう感じになる。
ここでやっと相談内容！
ランダム性を持たせるためにはどんなComparerを作ればいい？
| - C#, C♯, C＃相談室 Part85
652 ：デフォルトの名無しさん[]：2014/12/13(土) 03:10:36.80 ID:y9otNf+T - >>651
そう思って書いた以下のコードなんだが・・・
public class DescendingRandomComparer : IComparer<int>
{
public int Compare(int x, int y)
{
return x == y ? Form1.random.Next(2) * 2 - 1 : -x.CompareTo(y);
}
}
自分のデータでやると落ちるんだよね＾＾；
ちなみにメッセージは以下
追加情報:IComparer.Compare() メソッドから矛盾する結果が返されたため、
並べ替えできません。値をそれ自体と比較したときに等しい結果にならないか、
またはある値を別の値と繰り返し比較したときに異なる結果が生じます。
同じデータに対してLINQ版は正常に動作するから、
Comparer版はどっかロジックに穴があるはずなんだよね＾＾；
| - C#, C♯, C＃相談室 Part85
669 ：デフォルトの名無しさん[]：2014/12/13(土) 11:32:42.84 ID:y9otNf+T - 寝て起きた。みんな色々考えてくれてありがとう。
>>655
ソートを完了することができなくて落ちてるんでしょう。
>>656
Comparerで対応することができないなら、
「Array.Sortによってランダム性を持たせたソートはできない」
っていうことかな？
それならそれでいいんだけど、ほんとにできない？
>>657
どうでもよくない、コードの最適化は大歓迎だわ。
そもそも今回のLINQ版→Array.Sort版を検討してるのは
自分で作ったLINQ版が遅いからだったんだよね＾＾；
ちょっとこれからおまえのコードの速度をチェックしてくるわ
逆にいえばArray.Sortにこだわる必要は本来はなくて、
「ランダム性を持たせたソートで一番高速な手法は？」
というのが今回の相談の一般形。
それがLINQであろうとArray.Sortであろうと第3の手法であろうと大歓迎。
| - C#, C♯, C＃相談室 Part85
670 ：デフォルトの名無しさん[]：2014/12/13(土) 11:34:31.42 ID:y9otNf+T - >>658
どういうこと？
具体的な実装で示してくれる？
keyのGetHashCodeに、ランダム性を持たせるがkeyに対して一意のハッシュ関数を定義するとか？
>>659
自分でも確認したが>>649のデータでは発生しないみたい。
>>660の言うとおりたまたま動いただけ。
>>661
10000回でも発生しなかったんだ。
ちょっと俺も今デバッグ中で、再現できるデータが得られたらまた報告するわ。
>>662
俺の環境でバージョン情報だしたら4.5.50938って書いてあった
>>666-667
一回ソートしてからさらに同一値のものに対して処理をかけるって遅そうじゃない？
GroupByも遅そう。
Tupleでランダムな値の付与も同一値じゃないところにメモリを使うのでちょっと効率的じゃない。
遅そうというのは単に俺の想像でしかないから実際は速いのかもしれない。
既出の手法よりも効率的ならぜひ教えてほしい。
>>668
肝心の中身が無いじゃねーかｗ
| - C#, C♯, C＃相談室 Part85
672 ：デフォルトの名無しさん[]：2014/12/13(土) 11:50:02.96 ID:y9otNf+T - >>671
なるほど。
ちょっと要求仕様が明確でなかったみたいなんで補足します。
「ランダム性」はすべてRandomクラスのインスタンスrandom（俺の実装ではForm1に存在）が担っているものとします。
あと、背景についても少し話しておくと、
二人対戦のゲームの思考エンジンを考えてて、
ゲーム木のある深さの局面を評価値でソートするときに、
最善のものを使ってたんじゃ、人間が同じ手を打つと、
コンピュータも必ず同じ手を打って面白くないわけ。
そこで、ランダム性を持たせたいというわけです。
このランダム性はシードを与えることによってユーザーが管理できるものとします。
つまり、シードとして0を与えれば必ず同じ着手系列を打ってくるし、
シードとして1を与えれば必ず同じ着手系列を打ってくるというもの。
ランダム性はboolでオン・オフできるようになってて、
基本はオフにしてあって、この場合には普通の降順ソートを作動させる。
オンにしたときでも、オフの場合に比べて大幅に遅くなるのは問題がある。
ランダム性付与の処理はなるべく最小限に抑えたい。
現状、普通の降順ソートにはArray.Sortを利用している。
>>657からランダム性を抜いたものが速ければそっちに変える。
速さは正義。
| - C#, C♯, C＃相談室 Part85
682 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 13:03:12.16 ID:y9otNf+T - >>673
俺の中でのArray.Sortの利便性が下がるだけで何も問題ないよ。
LINQさまさまだぜｗ
>>674
情報thx
Comparerでの対応は不可能ってことか。
ということは>>666の言うように2ステップで
①普通のソート
②同じ値のものをシャッフル
という風にするしかないね。
でも②の処理でぱっと思いつく
「順番に舐めて前と後をランダムに入れ替え」
だと一般性を失ってしまうね。
つまり、同一の値のものがA,B,Cだったとして
C,A,BとかC,B,Aが生成されなくなってしまう(>>680)。
>>677, >>679, >>681
安定ソートか不安定ソートかはあんまり関係なくて、
最速の普通のソートによって得られた順番と、違う順番のものが欲しい
ということ。
ソートの結果によってコンピュータが打つ手が一意に対応づくんだけど、
普通のソートの結果による着手と強さが変わらない着手を生成するために、
普通のソートの結果とは違うソートの結果が必要なんだ（ちゃんと評価値順に並んでる）。
>>678
まぁ正論なんだが、ちょっと今はパス。
ライブラリを流用したいｗ
| - C#, C♯, C＃相談室 Part85
693 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 14:55:52.48 ID:y9otNf+T - >>661のためにデバッグで落ちるデータの特定してたんだが、
なかなか大変だった。
めったにおこらないレアケースらしい。
逆にいえば、ほとんどの場合、望んでいる振る舞いをする。
以下が落ちるコード。みんなも確認してみてほしい。
public class DescendingRandomComparer : IComparer<int>
{
public int Compare(int x, int y)
{
return x == y ? Program.random.Next(2) * 2 - 1 : -x.CompareTo(y);
}
}
class Program
{
public static Random random = new Random(1);
static void Main(string[] args)
{
int[] key = { -9, -11, -10, -10, -10, -10, -11, -10, -10, -9, -11, -11, -9, -11, -14, -13, -10, -11, -13 };
int[] val = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18 };
DescendingRandomComparer descendingRandomComparer = new DescendingRandomComparer();
Array.Sort(key, val, descendingRandomComparer);
Console.WriteLine(key.ToStringExtension());
Console.WriteLine(val.ToStringExtension());
Console.ReadLine();
}
}
| - C#, C♯, C＃相談室 Part85
695 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 15:03:54.48 ID:y9otNf+T - 俺は>>661じゃないからわからないが、
>>661本人が実行する限り現象が再現しないんじゃ問題意識もてないでしょ。
問題が起きるパターンを提示するのは問題提起した俺の責任だ。
| - C#, C♯, C＃相談室 Part85
699 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 18:30:02.77 ID:y9otNf+T - 色々試したので報告。
まず、>>657のコードを試してみた。
今までの自分のコードはforループの中でリスト構造の要素位置を
参照するというO(n)の操作をやってしまっていた。
指摘されて確かにこれは無駄だなと思ったんだが、
>>657のコードに変更して実行してみても結果はまったくといっていいほど変わらなかった。
なんで改善しないんだ？と思って色々調べていると以下の記述を発見。
Enumerable.ElementAt
source の型が IList<T> を実装する場合、その実装を使用して、指定したインデックス位置にある要素を取得します。 それ以外の場合、このメソッドは、指定した要素を取得します。
http://msdn.microsoft.com/ja-jp/library/bb299233%28v=vs.110%29.aspx
つまり、O(n)だと思っていた操作は対象がintだったことからO(1)になっていたわけだ。
| - C#, C♯, C＃相談室 Part85
701 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 18:37:55.46 ID:y9otNf+T - 次に、現状でのライブラリを用いたソートに関する見解。
【純粋ソート】
Array.Sortがやっぱり速い。
自分のソフトのあるベンチマークを走らせてみると、
LINQ版が11.8秒かかるところが、Array.Sort版だと10.3秒で終わる。
なので、ランダム性オフの場合はやはり今後もArray.Sortを利用することになる。
【ランダム性ソート】
Array.Sortはこれまでの議論から達成する手段がない状態。
なので、しかたなくLINQ版を使っている。
しかし、よくよく考えてみれば、
Array.Sort版は例外は発生しているが、ソート結果は望み通りの結果なのだから、
Array.Sortのソースが手に入れば、そこから例外処理を削除すれば、
Array.Sortのランダム性版が達成できるのかな？
VSのバージョンによっては一切エラー吐かないみたいだし、
副作用はなさそう。
そして、とても高速そう。
Array.Sortのソースってどっかから入手できるの？
| - C#, C♯, C＃相談室 Part85
704 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 18:59:43.53 ID:y9otNf+T - >>702
正しい方向に導いてくれ
>>703
それ、直感的になんだけど、不安定ソートと相性悪くない？
安定ソートだったら良いと思うんだけど・・・。
| - C#, C♯, C＃相談室 Part85
706 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 19:02:32.31 ID:y9otNf+T - ちょっと補足すると、
安定ソートは同じ値の中での順番がオリジナルと同一であることが保証されてる。
一方で、
不安定ソートは同じ値の中での順番がどういう並び順になっているかは一切保証されない。
つまり、ある秩序をもった特定の並び方になるかもしれないわけだ。
| - C#, C♯, C＃相談室 Part85
711 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 19:20:22.19 ID:y9otNf+T - >>707
出力結果をToArrayしてました＾＾；
拡張メソッドはいろんなところで使えるんで、
作成するときはより一般的に作るように心掛けてて
IEnumerableで書いてますが、実際はint[]です＾＾；
ToArrayなければやはり効果があるんですね～、確認できてよかった。
あなたが>>657のコード書いた人かな？
とりあえず性能は変わらなかったけど、可読性の観点だけからみても
あなたのコードの方がよかったので、置き換えました＾＾；
性能面でも効果を発揮する場面があるとなれば、なおさらだわ。
とりあえず感謝。
| - C#, C♯, C＃相談室 Part85
713 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 19:59:04.17 ID:y9otNf+T - >>712
直感が先行してるだけでうまく説明できないかもしれないが
①純粋ソート→同一値のものをシャッフル
②全体をシャッフル→純粋ソート
たくさんの実験を行った後の、
実験結果の頻度ヒストグラムを想像してみよう。
①は完全に一様であることが自明だが、
②はどうだろうか？
ソートアルゴリズムがクイックソートやバブルソートによって違ったり、
乱数生成アルゴリズムがメルセンヌツイスターやカオス乱数によって違ったり、
直感的に一様であるとは思えない。
ま、一様じゃなくて、特定の分布をもってたとしても、実害はないとは思うんだけどね。
いずれにせよ、これからも色々実験してみる予定。
今まで俺が色々試した中でのアウトプットは
「純粋ソートはLINQよりもArray.Sortを使え！」
ということ。
これからの俺のアウトプットとして
「ランダム性ソートはHogeHogeを使え！」
のHogeHogeは求める予定。
| - C#, C♯, C＃相談室 Part85
715 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 20:20:40.75 ID:y9otNf+T - ＞特殊なソートしたければ自分で作る（何を作るかは考える）
どうやったらそう解釈できるんだよＯＴＺ
評価値いじって改善しろとかいう頭脳だとそうなるんだなｗ
| - C#, C♯, C＃相談室 Part85
722 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 21:34:45.72 ID:y9otNf+T - ソース探して例外処理を無効にして・・・とか、
なにやってんだこいつ？と思うのはわからなくはない、
が、少しでも速いコードにするためには
手段を選ばないというのがこの分野の常識なんだわ。
ボードサイズ8で8回のループするんであれば、
forループ書くよりもべた書きするとかね。
んで、おまえたちは、やりたいことができればいいじゃん、
っていう、そういう考えだよな。違うんだよ俺は。
シャッフルするにもO(n)のオーダーで計算量がかかるだろ？
これをComparerにランダム性あたえて普通にソートさせたらどうなる？
| - C#, C♯, C＃相談室 Part85
726 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 21:52:47.11 ID:y9otNf+T - nは着手可能手数だぞ？
単純計算でn=10として23と比べて無視できると思うのか？
| - C#, C♯, C＃相談室 Part85
731 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 22:37:55.05 ID:y9otNf+T - なぜ無駄を省くか？
そこに無駄があるからだろう。
無駄だらけなんだから一部の無駄を省いても無駄とかいう議論が無駄
| - C#, C♯, C＃相談室 Part85
732 ：名無しさん＠そうだ選挙に行こう[]：2014/12/13(土) 22:42:06.14 ID:y9otNf+T - 幅優先探索は使ってる人みたことない。遅いし。
この分野ではアルファベータ探索が常識。俺はMTD(f)だが。
アルファベータ探索は着手可能手のうち、
どういう順番で探索するかが非常に重要なんだ。
ソートも10秒で一千万から一億程度よばれるので非常に重要。
ランダム性を与えるのは面白くするだけじゃない。
|
|