LoginSignup
1
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@chunchunist

C#でバケットソートを実装する

Posted at

バケットソートとは

Wikipediaを参照してください。簡単に言うと、値の取りうる範囲が決まっている場合に高速なソートを実現するものです。

さっそく実装

とりあえず、値の取りうる範囲は与えられるものとします。

BucketSort.cs
using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    static void Main()
    {
        var rand = new Random();

        var source = new List<int>();
        for (var i = 0; i < 10000; ++i) {
            source.Add(rand.Next(100));
        }

        foreach (var v in BucketSort(source, v => v, Enumerable.Range(0, 100))) {
            Console.WriteLine(v);
        }
    }

    public static IEnumerable<TSource> BucketSort<TSource, TKey>(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEnumerable<TKey> keyDomain)
    {
        var buckets = keyDomain.ToDictionary(k => k, _ => new List<TSource>());

        foreach (var v in source) {
            var key = keySelector(v);
            buckets[key].Add(v);
        }

        return buckets.SelectMany(p => p.Value);
    }
}

keySelectorはOrderByなどと同じでソートのキーを選択するためのものです。keyDomainが取りうる値の範囲で、0と10しかとらない場合などはnew[] { 0, 10 }とか渡しても大丈夫です。
以上、非常に簡単に実装できました。

メソッドチェーンで使いたい

と、それで終わるのであればわざわざ記事を作ったりしないですよね。
C#で使うならLINQなんかに絡めて使いたいわけです。上の実装を拡張メソッドにしてしまえば「ほぼ」完了です。ええ。「ほぼ」です。

// BucketSortを拡張メソッドにしたとしたら
var source = new List<int>();
for (var i = 0; i < 10000; ++i) {
    source.Add(rand.Next(10000));
}
// LINQで使える
source.Where(v => v < 100)
      .BucketSort(v => v, Enumerable.Range(0, 100))
      .Select(v => v * 2);

お気づきだろうか……

BucketSortの後に別のキーでソートしたい場合を考えてみましょう。

var source = new List<Tuple<int, int>>();
for (var i = 0; i < 10000; ++i) {
    source.Add(Tuple.Create(rand.Next(100), rand.Next(100)));
}
var sorted = source
    .BucketSort(v => v.Item1, Enumerable.Range(0, 100))
    .BucketSort(v => v.Item2, Enumerable.Range(0, 100));

foreach (var v in sorted) Console.WriteLine(v); // ???

Item1をキーにしてソートした後にItem2でソートするため、やりたい順番とは逆になります。そのためにLINQにはThenByがあります。というわけで、ThenByのような処理も実装しましょう。

完成版ソース

OrderedEnumerableのソースを参考に実装しました。

BucketSortedEnumerable.cs
using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public interface IBucketComparer<TKey> : IComparer<TKey> {

    IEnumerable<TKey> KeyDomain { get; }

}

internal class BucketComparer<TKey> : IBucketComparer<TKey> {

    internal IEnumerable<TKey> keyDomain;

    internal BucketComparer(IEnumerable<TKey> keyDomain)
    {
        this.keyDomain = keyDomain;
    }

    public IEnumerable<TKey> KeyDomain { get { return keyDomain; } }

    public int Compare(TKey lhs, TKey rhs)
    {
        throw new NotSupportedException();
    }

}

internal abstract class BucketSortedEnumerable<TSource> : IOrderedEnumerable<TSource> {

    internal IEnumerable<TSource> source;

    internal abstract EnumerableSorter<TSource> GetEnumerableSorter(EnumerableSorter<TSource> next);

    IOrderedEnumerable<TSource> IOrderedEnumerable<TSource>.CreateOrderedEnumerable<TKey>(Func<TSource, TKey> keySelector, IComparer<TKey> comparer, bool descending)
    {
        var result = new BucketSortedEnumerable<TSource, TKey>(source, keySelector, comparer, descending);
        result.parent = this;
        return result;
    }

    public IEnumerator<TSource> GetEnumerator()
    {
        return GetEnumerableSorter(null).Sort(source).GetEnumerator();
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

}

internal class BucketSortedEnumerable<TSource, TKey> : BucketSortedEnumerable<TSource> {

    internal BucketSortedEnumerable<TSource> parent;
    internal Func<TSource, TKey> keySelector;
    internal IComparer<TKey> comparer;
    internal bool descending;

    internal BucketSortedEnumerable(IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer, bool descending)
    {
        if (source == null) throw new ArgumentNullException("source");
        if (keySelector == null) throw new ArgumentNullException("keySelector");

        this.source = source;
        this.parent = null;
        this.keySelector = keySelector;
        this.comparer = comparer != null ? comparer : Comparer<TKey>.Default;
        this.descending = descending;
    }

    internal override EnumerableSorter<TSource> GetEnumerableSorter(EnumerableSorter<TSource> next)
    {
        var bucketComparer = comparer as IBucketComparer<TKey>;

        var sorter = (bucketComparer != null) ?
            (EnumerableSorter<TSource>)new BucketSorter<TSource, TKey>(keySelector, bucketComparer, descending, next) :
            new DefaultSorter<TSource, TKey>(keySelector, comparer, descending, next);

        if (parent != null) sorter = parent.GetEnumerableSorter(sorter);

        return sorter;
    }

}

internal abstract class EnumerableSorter<TSource> {

    internal EnumerableSorter<TSource> next;
    internal bool descending;

    internal abstract IEnumerable<TSource> Sort(IEnumerable<TSource> source);

}

internal class DefaultSorter<TSource, TKey> : EnumerableSorter<TSource> {

    private Func<TSource, TKey> keySelector;
    private IComparer<TKey> comparer;

    internal DefaultSorter(Func<TSource, TKey> keySelector, IComparer<TKey> comparer, bool descending, EnumerableSorter<TSource> next)
    {
        this.keySelector = keySelector;
        this.comparer = comparer;
        this.descending = descending;
        this.next = next;
    }

    internal override IEnumerable<TSource> Sort(IEnumerable<TSource> source)
    {
        source = (descending) ? source.OrderByDescending(keySelector, comparer) : source.OrderBy(keySelector, comparer);
        if (next != null) source = next.Sort(source);
        return source;
    }

}

internal class BucketSorter<TSource, TKey> : EnumerableSorter<TSource> {

    private Func<TSource, TKey> keySelector;
    private IBucketComparer<TKey> comparer;

    internal BucketSorter(Func<TSource, TKey> keySelector, IBucketComparer<TKey> comparer, bool descending, EnumerableSorter<TSource> next)
    {
        this.keySelector = keySelector;
        this.comparer = comparer;
        this.next = next;
        this.descending = descending;
    }

    internal override IEnumerable<TSource> Sort(IEnumerable<TSource> source)
    {
        var keyDomain = comparer.KeyDomain;
        if (keyDomain == null) {
            keyDomain = source.Select(keySelector).Distinct().OrderBy(v => v, comparer);
        }

        var buckets = (descending ? keyDomain.Reverse() : keyDomain).ToDictionary(k => k, _ => new List<TSource>());

        foreach (var v in source) {
            var key = keySelector(v);
            buckets[key].Add(v);
        }

        return buckets.SelectMany(p => (next != null) ? next.Sort(p.Value) : p.Value);
    }

}

public static class Extension {

    public static IOrderedEnumerable<TSource> OrderWithDomainBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEnumerable<TKey> keyDomain)
    {
        return new BucketSortedEnumerable<TSource, TKey>(source, keySelector, new BucketComparer<TKey>(keyDomain), false);
    }

    public static IOrderedEnumerable<TSource> OrderWithDomainBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IBucketComparer<TKey> comparer)
    {
        return new BucketSortedEnumerable<TSource, TKey>(source, keySelector, comparer, false);
    }

    public static IOrderedEnumerable<TSource> OrderWithReversedDomainBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEnumerable<TKey> keyDomain)
    {
        return new BucketSortedEnumerable<TSource, TKey>(source, keySelector, new BucketComparer<TKey>(keyDomain), true);
    }

    public static IOrderedEnumerable<TSource> OrderWithReversedDomainBy<TSource, TKey>(this IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IBucketComparer<TKey> comparer)
    {
        return new BucketSortedEnumerable<TSource, TKey>(source, keySelector, comparer, true);
    }

    public static IOrderedEnumerable<TSource> ThenWithDomainBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEnumerable<TKey> keyDomain)
    {
        return source.CreateOrderedEnumerable(keySelector, new BucketComparer<TKey>(keyDomain), false);
    }

    public static IOrderedEnumerable<TSource> ThenWithDomainBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IBucketComparer<TKey> comparer)
    {
        return source.CreateOrderedEnumerable(keySelector, comparer, false);
    }

    public static IOrderedEnumerable<TSource> ThenWithReversedDomainBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IEnumerable<TKey> keyDomain)
    {
        return source.CreateOrderedEnumerable(keySelector, new BucketComparer<TKey>(keyDomain), true);
    }

    public static IOrderedEnumerable<TSource> ThenWithReversedDomainBy<TSource, TKey>(this IOrderedEnumerable<TSource> source, Func<TSource, TKey> keySelector, IBucketComparer<TKey> comparer)
    {
        return source.CreateOrderedEnumerable(keySelector, comparer, true);
    }

}

しれっとLINQっぽい名前に変えました。で、肝心の使い方ですが、2通りあります。
まずは最初の方でやっていた、keyDomainを指定する方法。

source.OrderWithDomainBy(v => v.Item1, Enumerable.Range(0, 100))
      .ThenWithReversedDomainBy(v => v.Item2, Enumerable.Range(0, 100))

こんな感じでItem1で昇順に並べた後、Item2で降順に並べます。
昇順や降順というのはkeyDomainの並びに依存して、Reversedがつかない方はkeyDomainの順番で、つく方は逆順でということになります。

もう1つの方はkeyDomainを指定しない方法。値の範囲がわからない場合に使えますが、バケットソートの性質上、あまり使わない方がいいと思います。

class MyComparer : IBucketComparer<int> {

    public IEnumerable<int> KeyDomain { get { return null; } }

    public int Compare(int lhs, int rhs)
    {
        return lhs - rhs;
    }

}

var comparer = new MyComparer();
source.OrderWithDomainBy(v => v.Item1, comparer)
      .ThenWithReversedDomainBy(v => v.Item2, comparer)

IBucketComparerを実装したクラスを作り、KeyDomainをnullで返すと、ソートの際に一度sourceを走査してキーを洗い出し、Compareに従って並べ替えてkeyDomainを作成します。
想定外にbucketsの数が増える可能性もあるのでご利用は計画的に。

余談

もしかしたらこの実装は厳密に言うと鳩の巣ソートかもしれません。
あと、軽くググって見つからなかったので作ってみた（そして、結局使わなかったのでここに供養することにした）のですが、こんな感じのものは太古の昔に誰かが作ってそうなんですが、どうでしょう？

1
6
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
6

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?