none
List<T>のSort()について RRS feed

  • 質問

  • こんにちは

    初歩的な質問なのですが、教えてください。

    List<int> myList = new List<int>();

    myList.Add(100);

    myList.Add(90);

         :

         :

    myList.Sort();

    を実行すると、必ず昇順ソートになるようですが、簡単に降順ソートにする方法はないのでしょうか?

    1.myList.Sort()実行後、myList.Reverse()を実行する。

    2.降順ソート用の関数を定義する。

    3.(理解できていませんが)IComparerクラスなどを定義する。

    など考えてみましたが、一発で降順ソートができる手立てはあるのでしょうか?

    よろしくお願いします。

    2011年9月5日 2:14

回答

すべての返信

  • お使いの C# のバージョンによって、できることが違ってきますが、匿名デリゲートとかラムダ式を使うとシンプルに書けると思います。

    配列やコレクション内の要素を並び替える: .NET Tips: C#, VB.NET, Visual Studio
    http://dobon.net/vb/dotnet/programing/icomparer.html
    • 回答としてマーク mokosan 2011年9月5日 6:47
    2011年9月5日 2:24
  • .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
    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
    2011年9月5日 3:19
    モデレータ
  • totojo様
    かずき_okazuki様
    trapemiya様


    ご回答ありがとうございます。
    LINQに関しては、要素数が増えるとスピードダウンすると聞いたことがあるので、今回は除外しようと思います。
    totojo様がご提示くださったサイトは見ていたのですが、IComparerクラスを勉強して対応してみようと思います。

    ありがとうございました。

    2011年9月5日 6:46
  • 外池と申します。

    List<T>のTには、何か、独自の型が入るんですよね?(思い込みが過ぎるかな・・・) 

    だとすれば、ソートするには降順・昇順にかかわらず「大小関係」を定義してやらないといけないので、IComparableかIComparable<T>のインターフェイスの実装は必須なのではないかと・・・。LINQを使うにしても。

     


    (ホームページを再開しました)
    2011年9月5日 7:18
  • パフォーマンス重視なんですね。私が書いたラムダ式(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.80Ghz

    4714                    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/
    2011年9月5日 8:53
    モデレータ
  • そんなこと言ったら

    list.Sort();
    list.Reverse();

    が断然速いですが…。 

    2011年9月5日 10:07
  • 外池です。念のため・・・、

    Sortって、ドキュメントによれば、QuickSortとなっていますが・・・、

    これ、最初から整列したものに対して適用すると、O(N^2) (汗)

     


    (ホームページを再開しました)
    2011年9月5日 10:22
  • そんなこと言ったら

    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/
    2011年9月6日 2:22
    モデレータ
  • 上の私の発言の追記です。コードを含む投稿を修正すると、コード間に空行がどんどん増えていくんで、修正しづらいんですよね・・・。この障害の報告してあったかな?
    これ、最初から整列したものに対して適用すると、O(N^2) (汗)

    シャッフルするようにしました。シャッフルしなきゃと思っていたんですが、忘れていました。ご指摘ありがとうございます。

     


    ★良い回答には回答済みマークを付けよう! わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/
    2011年9月6日 2:34
    モデレータ
  • フフフフフッ、圧倒的じゃないか、引数なしSort()は

    とか言いたくなりますね。

    種明かしすると、引数なしだったり、Comperer<T>.Defaultを渡した場合は、ICompererを使わずネイティブコードで並べ替えが実行されます。

    2011年9月6日 2:54
  • コードを含む投稿を修正すると、コード間に空行がどんどん増えていくんで、修正しづらいんですよね・・・。この障害の報告してあったかな?

    とりあえず報告が無さそうだったので、報告しておきました。

    コードブロックを含む投稿を開いて修正すると、コードブロックで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/
    2011年9月6日 3:13
    モデレータ
  • 種明かしすると、引数なしだったり、Comperer<T>.Defaultを渡した場合は、ICompererを使わずネイティブコードで並べ替えが実行されます。

    なるほど。
    外池さんも言われていますが、海外のどこかの掲示板でもQuick Sortと書かれていましたから、これがネイティブで実行されるということですね。
    思った以上に大差でした。佐祐理さんの一言で計測してみて良かったです。勉強になりました。ありがとうございます。

     


    ★良い回答には回答済みマークを付けよう! わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/
    2011年9月6日 3:21
    モデレータ
  • 外池さんも言われていますが、海外のどこかの掲示板でもQuick Sortと書かれていましたから、これがネイティブで実行されるということですね。
    Quick Sortはアルゴリズム名で、List<T>.Sort()やArray.Sort()に明記されています。海外のどこかの掲示板を見なくても見つかるかと…。ネイティブ実行されることはstack overflowにもありますね。
    2011年9月6日 3:55
  • 外池です。私が「ドキュメント」と書いたのは、佐祐理さんが示しておられるページのことです。

    IComparer<T>を渡した場合であっても、個々の要素の大小判定にはこれが使われるものの、全体の並べ替えのアルゴリズムはQuick Sortだと私は理解しています。

    以下、独り言。

    IComparer<T>の呼び出しに大きなペナルティーがあるんでしょうね。ネイティブ実行に比べて。当たり前か。

    Quick Sortを選んだところ・・・、Microsoft殿らしいなあ、とも思います。私は、Heap Sortの方が好きです。Numerical Recipesの著者は、版を重ねる途中で宗旨替えしてますね。もともとHeap Sortが一押しだったようですが、今の版ではQuick Sortになっている。


    (ホームページを再開しました)
    2011年9月6日 5:11
  • IComparer<T>の呼び出しに大きなペナルティーがあるんでしょうね。ネイティブ実行に比べて。当たり前か。

    .NET FrameworkにとってはIComperer<T>も入力引数なので、Compare()結果に矛盾がないか疑いながら並べ替える必要があったりする点もオーバーヘッドになるかも。

    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をアルゴリズム以外の何かを指しているような表現に受取れたために念のため書きました。

    2011年9月6日 5:46
  • # trapemiyaさんの「Quick Sortと書かれていましたから、これがネイティブで実行されるということですね」という言い回しが、Quick Sortをアルゴリズム以外の何かを指しているような表現に受取れたために念のため書きました。

    アルゴリズムの意味で使っていました。というか、アルゴリズム名以外に私は知りません(^^;
    とはいうものの、昔はソートを自分で書いたりしていましたが、最近は自分でソートを書くことは無くなってしまい、ソートアルゴリズムに関してはすっかり忘れてしまいました(^^;
    私が関わる仕事の範囲では大量のデータを扱うシビアなソートを要求されることは無いですし、ソートはデータベースで行うことが多くなりましたし、パソコンの性能が上がったのも理由の一つでしょうか。
    しかし、決してソートのアルゴリズムを勉強する必要は無いと言うつもりはありません。古い記事ですが、日経ソフトウエア 2000年1月号の 「ソートの書ける」プログラマになろう! という記事を思い出しました。ソートもアルゴリズムですから、アルゴリズムを勉強することはプログラマとして幅が広がると思います。

     


    ★良い回答には回答済みマークを付けよう! わんくま同盟 MVP - Visual C# http://d.hatena.ne.jp/trapemiya/
    2011年9月6日 9:43
    モデレータ
  • アルゴリズムでなくても。

    例えば、このスレッドを起こしたmokosanさんは別スレッドでSortedListについて質問されています。List.Sort()は一括でソートしますが、SortedListは項目が増減されるたびにソートし直します。(と言っても毎回Quick Sortをするわけじゃないでしょうが。)
    項目の増減が激しく、なおかつ常にソートされた状態が必要とされているのならSortedListが適しているでしょうが、そうではない場合、ソート状態を維持するコストが高くなるでしょう。
    # 質問を読む限り、Dictionaryの方が適しているアクセス方法をしていますし…。 

    とかとか、コストについては理解しておいた方がいいでしょうね。

    2011年9月7日 1:13
  • LINQに関しては、要素数が増えるとスピードダウンすると聞いたことがあるので、今回は除外しようと思います。

    私はLINQ星人ではないのでうまく説明できませんが、この記述に引っかかったので。

    LINQには確かにオーバーヘッドはあります。それは事実なのですが、それに勝る利点があります。

    まず前提として遅延実行されます。そのため要素数が増えても必要な要素にしかアクセスせずに済ます書き方ができます。その場合、要素数が増えてもスピードダウンしないでしょう。またAsParallel拡張メソッドなどもあり、簡単にマルチスレッド実行できる仕組みも用意されています。通常の書き方ならシングルスレッドで逐次的に処理するものもマルチスレッドで並列に処理することで高速化できたりもあります。

    というわけで「LINQに関しては、要素数が増えるとスピードダウンする」とは「下手な人が試してみたところスピードダウンした」程度の意味ですので、ぜひぜひLINQも使ってみてください。

    2011年9月7日 7:16