トップ回答者
List<T>のSort()について

質問
-
こんにちは
初歩的な質問なのですが、教えてください。
List<int> myList = new List<int>();
myList.Add(100);
myList.Add(90);
:
:
myList.Sort();
を実行すると、必ず昇順ソートになるようですが、簡単に降順ソートにする方法はないのでしょうか?
1.myList.Sort()実行後、myList.Reverse()を実行する。
2.降順ソート用の関数を定義する。
3.(理解できていませんが)IComparerクラスなどを定義する。
など考えてみましたが、一発で降順ソートができる手立てはあるのでしょうか?
よろしくお願いします。
回答
すべての返信
-
.NET 3.5以降ですがLINQを使うという手もあります。
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main(string[] args) { var list = new List<int> { 3, 1, 5, 2, 6, 4 }; var sorted = list.OrderBy(i => i).ToList(); var sortedDesc = list.OrderByDescending(i => i).ToList(); Console.WriteLine("-- ソート前"); foreach (var i in list) { Console.Write(i + ", "); } Console.WriteLine(); Console.WriteLine("-- OrderBy"); foreach (var i in sorted) { Console.Write(i + ", "); } Console.WriteLine(); Console.WriteLine("-- OrderByDescending"); foreach (var i in sortedDesc) { Console.Write(i + ", "); } Console.WriteLine(); } }
実行すると、以下のような結果になります。-- ソート前
3, 1, 5, 2, 6, 4,
-- OrderBy
1, 2, 3, 4, 5, 6,
-- OrderByDescending
6, 5, 4, 3, 2, 1,
かずき Blog:http://d.hatena.ne.jp/okazuki/ VS 2010のデザイナでBlendのBehaviorをサポートするツール公開してます。 http://vsbehaviorsupport.codeplex.com/- 編集済み KazukiOta 2011年9月5日 3:05
-
以下が簡単かな?
myList.Sort((x, y) => y.CompareTo(x));
★良い回答には回答済みマークを付けよう! わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/
- 編集済み trapemiyaModerator 2011年9月5日 8:40 ↑拡張メソッドじゃなくてただのメソッドです。orz
-
パフォーマンス重視なんですね。私が書いたラムダ式(Comparison)との比較に興味があったので比較してみました。
var list = new List<int>(); for (var i = 0; i < 10000000; i++) list.Add(i); var st = new Stopwatch(); Console.WriteLine(Stopwatch.IsHighResolution); st.Start(); list.Sort((x, y) => y.CompareTo(x)); st.Stop(); Console.WriteLine(st.ElapsedMilliseconds.ToString()); list = new List<int>(); for (var i = 0; i < 10000000; i++) list.Add(i); st = new Stopwatch(); IComparer<int> comp = new MyComparer(); st.Start(); list.Sort(comp); st.Stop(); Console.WriteLine(st.ElapsedMilliseconds.ToString()); public class MyComparer :System.Collections.Generic.IComparer<int> { public int Compare(int x, int y) { return y.CompareTo(x); } }
ラムダ式(Comparison) IComparer 差 (単位 ms) Windows 7 ultimate x64 Intel Core i7 930 2.80Ghz4714 4391 323
5278 4929 349
5556 4561 995
4714 4392 322
5543 4564 979
5237 4910 327
5529 4567 962
4943 4287 656
5527 4570 957
4713 4397 316
★良い回答には回答済みマークを付けよう! わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/ -
そんなこと言ったら
list.Sort();
list.Reverse();が断然速いですが…。
そうですね。Sort、Reverseもついでに計測してみました。また、ソートする前のListは、シャッフルするようにしました。
var list1 = new List<int>(); var list2 = new List<int>(); var list3 = new List<int>(); for (var i = 0; i < 10000000; i++) list1.Add(i); list1 = list1.OrderBy(i => Guid.NewGuid()).ToList(); //シャッフル list2 = list1.ToList(); list3 = list1.ToList(); var st = new Stopwatch(); Console.WriteLine(Stopwatch.IsHighResolution); //1.ラムダ式(Comparison)でソート-------------------- st.Start(); list1.Sort((x, y) => y.CompareTo(x)); st.Stop(); Console.WriteLine(st.ElapsedMilliseconds.ToString()); //2.IComparerでソート------------------------------- st = new Stopwatch(); IComparer<int> comp = new MyComparer(); st.Start(); list2.Sort(comp); st.Stop(); Console.WriteLine(st.ElapsedMilliseconds.ToString()); //3.SortとReverseでソート--------------------------- st = new Stopwatch(); st.Start(); list3.Sort(); list3.Reverse(); st.Stop(); Console.WriteLine(st.ElapsedMilliseconds.ToString());
1. 2. 3. 単位 ms
7088 6391 1200
6985 6312 1201
7075 6601 1196
7636 7034 1196
6952 6528 1198
★良い回答には回答済みマークを付けよう! わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/ -
フフフフフッ、圧倒的じゃないか、引数なしSort()は
とか言いたくなりますね。
種明かしすると、引数なしだったり、Comperer<T>.Defaultを渡した場合は、ICompererを使わずネイティブコードで並べ替えが実行されます。
-
コードを含む投稿を修正すると、コード間に空行がどんどん増えていくんで、修正しづらいんですよね・・・。この障害の報告してあったかな?
とりあえず報告が無さそうだったので、報告しておきました。
コードブロックを含む投稿を開いて修正すると、コードブロックで1行毎に空行を挿入される。
http://social.msdn.microsoft.com/Forums/ja-JP/suggestja/thread/fb0eab28-6820-4530-9883-0a936d267086
★良い回答には回答済みマークを付けよう! わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/ -
種明かしすると、引数なしだったり、Comperer<T>.Defaultを渡した場合は、ICompererを使わずネイティブコードで並べ替えが実行されます。
なるほど。
外池さんも言われていますが、海外のどこかの掲示板でもQuick Sortと書かれていましたから、これがネイティブで実行されるということですね。
思った以上に大差でした。佐祐理さんの一言で計測してみて良かったです。勉強になりました。ありがとうございます。
★良い回答には回答済みマークを付けよう! わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/ -
外池さんも言われていますが、海外のどこかの掲示板でもQuick Sortと書かれていましたから、これがネイティブで実行されるということですね。
Quick Sortはアルゴリズム名で、List<T>.Sort()やArray.Sort()に明記されています。海外のどこかの掲示板を見なくても見つかるかと…。ネイティブ実行されることはstack overflowにもありますね。 -
外池です。私が「ドキュメント」と書いたのは、佐祐理さんが示しておられるページのことです。
IComparer<T>を渡した場合であっても、個々の要素の大小判定にはこれが使われるものの、全体の並べ替えのアルゴリズムはQuick Sortだと私は理解しています。
以下、独り言。
IComparer<T>の呼び出しに大きなペナルティーがあるんでしょうね。ネイティブ実行に比べて。当たり前か。
Quick Sortを選んだところ・・・、Microsoft殿らしいなあ、とも思います。私は、Heap Sortの方が好きです。Numerical Recipesの著者は、版を重ねる途中で宗旨替えしてますね。もともとHeap Sortが一押しだったようですが、今の版ではQuick Sortになっている。
(ホームページを再開しました) -
IComparer<T>の呼び出しに大きなペナルティーがあるんでしょうね。ネイティブ実行に比べて。当たり前か。
Quick Sortを選んだところ・・・、Microsoft殿らしいなあ、とも思います。私は、Heap Sortの方が好きです。Numerical Recipesの著者は、版を重ねる途中で宗旨替えしてますね。もともとHeap Sortが一押しだったようですが、今の版ではQuick Sortになっている。
libcにもqsort()があったりと、ライブラリで用意する場合はQuick Sortにせざるを得ないと思います。好きか嫌いかでいえば、私もHeap Sortが好きですが、同じO(n log n)であっても、Quick Sortの方が早いので。
# trapemiyaさんの「Quick Sortと書かれていましたから、これがネイティブで実行されるということですね」という言い回しが、Quick Sortをアルゴリズム以外の何かを指しているような表現に受取れたために念のため書きました。
-
# trapemiyaさんの「Quick Sortと書かれていましたから、これがネイティブで実行されるということですね」という言い回しが、Quick Sortをアルゴリズム以外の何かを指しているような表現に受取れたために念のため書きました。
アルゴリズムの意味で使っていました。というか、アルゴリズム名以外に私は知りません(^^;
とはいうものの、昔はソートを自分で書いたりしていましたが、最近は自分でソートを書くことは無くなってしまい、ソートアルゴリズムに関してはすっかり忘れてしまいました(^^;
私が関わる仕事の範囲では大量のデータを扱うシビアなソートを要求されることは無いですし、ソートはデータベースで行うことが多くなりましたし、パソコンの性能が上がったのも理由の一つでしょうか。
しかし、決してソートのアルゴリズムを勉強する必要は無いと言うつもりはありません。古い記事ですが、日経ソフトウエア 2000年1月号の 「ソートの書ける」プログラマになろう! という記事を思い出しました。ソートもアルゴリズムですから、アルゴリズムを勉強することはプログラマとして幅が広がると思います。
★良い回答には回答済みマークを付けよう! わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/ -
アルゴリズムでなくても。
例えば、このスレッドを起こしたmokosanさんは別スレッドでSortedListについて質問されています。List.Sort()は一括でソートしますが、SortedListは項目が増減されるたびにソートし直します。(と言っても毎回Quick Sortをするわけじゃないでしょうが。)
項目の増減が激しく、なおかつ常にソートされた状態が必要とされているのならSortedListが適しているでしょうが、そうではない場合、ソート状態を維持するコストが高くなるでしょう。
# 質問を読む限り、Dictionaryの方が適しているアクセス方法をしていますし…。とかとか、コストについては理解しておいた方がいいでしょうね。
-
LINQに関しては、要素数が増えるとスピードダウンすると聞いたことがあるので、今回は除外しようと思います。
私はLINQ星人ではないのでうまく説明できませんが、この記述に引っかかったので。
LINQには確かにオーバーヘッドはあります。それは事実なのですが、それに勝る利点があります。
まず前提として遅延実行されます。そのため要素数が増えても必要な要素にしかアクセスせずに済ます書き方ができます。その場合、要素数が増えてもスピードダウンしないでしょう。またAsParallel拡張メソッドなどもあり、簡単にマルチスレッド実行できる仕組みも用意されています。通常の書き方ならシングルスレッドで逐次的に処理するものもマルチスレッドで並列に処理することで高速化できたりもあります。
というわけで「LINQに関しては、要素数が増えるとスピードダウンする」とは「下手な人が試してみたところスピードダウンした」程度の意味ですので、ぜひぜひLINQも使ってみてください。