9月 032017
 

これまでC#の安定ソートが欲しくて色々と検討していました。

アロケーションを気にしなければ、LinkedListについては各要素にインデックス振ったListを作ってSort()するのが速いという結果が出ていました。その実装をここにまとめます。List版もありますが、先の記事で検討したマージソートの方が速いので、Listではそっちを使ったほうがいいです。性能比較については前回の記事を参照。

実装

インデックスと値のペアであるIndexedValueを値型(struct)で定義し、IndexedValueのListをSort()します。このListに詰め込む元はIEnumerableにしているので、IndexedValueのソート済みリストに変換する、というのが基本処理です。

配列、List、LinkedListには個別対応として、拡張メソッドstableSort()を定義することで、普段のSort()と同じような感覚で使えるようにしてあります。また、IndexedValueのリストからの変換も用意しています。

特にLinkedListには標準でソート機能が提供されていないので、LinkedListのソートが欲しい人にも需要あるかと。

public class FunctorComparer<T> : IComparer<T>
{
    public FunctorComparer(Comparison<T> comparison)
    {
        _comparison = comparison;
    }

    public int Compare(T x, T y)
    {
        return _comparison(x, y);
    }

    private Comparison<T> _comparison = null;
}
public static class StableSort
{
    #region 内部クラス
    public struct IndexedValue<T>
    {
        public int index;
        public T value;

        public IndexedValue(int index, T value)
        {
            this.index = index;
            this.value = value;
        }
    }

    public class IndexedComparer<T> : IComparer<IndexedValue<T>>
    {
        public IComparer<T> comparer;

        public IndexedComparer(IComparer<T> comparer = null)
        {
            if(comparer == null) {
                comparer = Comparer<T>.Default;
            }

            this.comparer = comparer;
        }

        public int Compare(IndexedValue<T> x, IndexedValue<T> y)
        {
            var result = comparer.Compare(x.value, y.value);
            if(result != 0) {
                return result;
            }

            return x.index - y.index;
        }
    }
    #endregion

    #region リスト変換
    public static T[] toArray<T>(this List<IndexedValue<T>> indexedList)
    {
        var array = new T[indexedList.Count];
        var count = indexedList.Count;
        for(var i = 0; i < count; ++i) {
            var value = indexedList[i].value;
            array[i] = value;
        }
        return array;
    }
    public static List<T> toList<T>(this List<IndexedValue<T>> indexedList)
    {
        var list = new List<T>(indexedList.Count);
        var count = indexedList.Count;
        for(var i = 0; i < count; ++i) {
            var value = indexedList[i].value;
            list.Add(value);
        }
        return list;
    }
    public static LinkedList<T> toLinkedList<T>(this List<IndexedValue<T>> indexedList)
    {
        var list = new LinkedList<T>();
        var count = indexedList.Count;
        for(var i = 0; i < count; ++i) {
            var value = indexedList[i].value;
            list.AddLast(value);
        }
        return list;
    }
    public static IEnumerable<T> toValues<T>(this List<IndexedValue<T>> indexedList)
    {
        foreach(var indexed in indexedList) {
            yield return indexed.value;
        }
    }
    public static List<IndexedValue<T>> toIndexedList<T>(this IEnumerable<T> values)
    {
        var collection = values as ICollection<T>;

        List<IndexedValue<T>> list = null;
        if(collection != null) {
            list = new List<IndexedValue<T>>(collection.Count);
        } else {
            list = new List<IndexedValue<T>>();
        }

        var i = 0;
        foreach(var value in values) {
            list.Add(new IndexedValue<T>(i, value));
            ++i;
        }

        return list;
    }
    #endregion

    #region インデックス付きリストのソート
    public static void sort<T>(this List<IndexedValue<T>> list)
    {
        sort(list, 0, list.Count, null);
    }
    public static void sort<T>(this List<IndexedValue<T>> list, Comparison<T> comparison)
    {
        if(list.Count <= 1) return;
        sort(list, new FunctorComparer<T>(comparison));
    }
    public static void sort<T>(this List<IndexedValue<T>> list, IComparer<T> comparer)
    {
        sort(list, 0, list.Count, comparer);
    }
    public static void sort<T>(this List<IndexedValue<T>> list, int index, int count, IComparer<T> comparer)
    {
        if(list.Count <= 1) return;
        if(comparer == null) {
            comparer = Comparer<T>.Default;
        }
        list.Sort(new IndexedComparer<T>(comparer));
    }
    #endregion

    #region ソート済みインデックス付きリストの取得
    public static List<IndexedValue<T>> toSortedList<T>(this IEnumerable<T> values)
    {
        IComparer<T> comparer = null;
        return toSortedList(values, comparer);
    }
    public static List<IndexedValue<T>> toSortedList<T>(this IEnumerable<T> values, Comparison<T> comparison)
    {
        IComparer<T> comparer = (comparison != null) ? new FunctorComparer<T>(comparison) : null;
        return toSortedList(values, comparer);
    }
    public static List<IndexedValue<T>> toSortedList<T>(this IEnumerable<T> values, IComparer<T> comparer)
    {
        var list = values.toIndexedList();
        if(list.Count <= 1) return list;

        if(comparer == null) {
            comparer = Comparer<T>.Default;
        }

        list.sort(comparer);
        return list;
    }
    public static List<IndexedValue<T>> toSortedList<T>(this IEnumerable<T> values, int index, int count, IComparer<T> comparer)
    {
        var list = values.toIndexedList();
        if(list.Count <= 1) return list;

        if(comparer == null) {
            comparer = Comparer<T>.Default;
        }

        list.Sort(new IndexedComparer<T>(comparer));
        return list;
    }
    #endregion

    #region T[]の安定ソート
    public static void stableSort<T>(this T[] array)
    {
        stableSort(array, 0, array.Length, null);
    }
    public static void stableSort<T>(this T[] array, Comparison<T> comparison)
    {
        stableSort(array, new FunctorComparer<T>(comparison));
    }
    public static void stableSort<T>(this T[] array, IComparer<T> comparer)
    {
        stableSort(array, 0, array.Length, comparer);
    }
    public static void stableSort<T>(this T[] array, int index, int count, IComparer<T> comparer)
    {
        var sortedList = array.toSortedList(index, count, comparer);
        for(var i = 0; i < count; ++i) {
            array[index + i] = sortedList[i].value;
        }
    }
    #endregion

    #region List<T>の安定ソート
    public static void stableSort<T>(this List<T> list)
    {
        stableSort(list, 0, list.Count, null);
    }
    public static void stableSort<T>(this List<T> list, Comparison<T> comparison)
    {
        stableSort(list, new FunctorComparer<T>(comparison));
    }
    public static void stableSort<T>(this List<T> list, IComparer<T> comparer)
    {
        stableSort(list, 0, list.Count, comparer);
    }
    public static void stableSort<T>(this List<T> list, int index, int count, IComparer<T> comparer)
    {
        var sortedList = list.toSortedList(index, count, comparer);
        list.Clear();
        list.AddRange(sortedList.toValues());
    }
    #endregion

    #region LinkedList<T>の安定ソート
    public static void stableSort<T>(this LinkedList<T> list)
    {
        stableSort(list, 0, list.Count, null);
    }
    public static void stableSort<T>(this LinkedList<T> list, Comparison<T> comparison)
    {
        stableSort(list, new FunctorComparer<T>(comparison));
    }
    public static void stableSort<T>(this LinkedList<T> list, IComparer<T> comparer)
    {
        stableSort(list, 0, list.Count, comparer);
    }
    public static void stableSort<T>(this LinkedList<T> list, int index, int count, IComparer<T> comparer)
    {
        var sortedList = list.toSortedList(index, count, comparer);
        list.Clear();
        for(var i = 0; i < count; ++i) {
            list.AddLast(sortedList[i].value);
        }
    }
    #endregion
}

コメントを残す(Markdown有効)

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください

Top