Help us understand the problem. What is going on with this article?

スターリンソートをJavaのCollectorで実装してみた

概要

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell

スターリンソートが流行っているようなのでJavaで書いてみます。
Java8から導入されたstreamAPIももうおなじみですよね。
今回はCollectメソッドが受け取るCollectorインターフェースの実装クラスを作って、streamでかっこよくスターリンソートができるようにします。

コード

/**
 * スターリンソートを実装したCollector実装クラス
 */
public final class StalinSortCollector {
    private StalinSortCollector() {}
    /**
     * 入力要素を自然順序でスターリンソートしその結果をStreamに変換するCollectorを返します。
     * @param <T> 入力要素の型
     */
    public static <T extends Comparable<? super T>> Collector<T, List<T>, Stream<T>> sorting(){
        return new StalinSortCollectorImplements<T, T>(Comparator.naturalOrder(), x -> x);
    }

    /**
     * 入力要素を自然順序の逆順でスターリンソートしその結果をStreamに変換するCollectorを返します。
     * @param <T> 入力要素の型
     */
    public static <T extends Comparable<? super T>> Collector<T, List<T>, Stream<T>> reverseSorting(){
        return new StalinSortCollectorImplements<T, T>(Comparator.reverseOrder(), x -> x);
    }

    /**
     * 入力要素をmapper関数により変換された値の自然順序でスターリンソートしその結果をStreamに変換するCollectorを返します。
     * @param mapper 入力要素を変換する関数
     * @param <T> 入力要素の型
     * @param <A> 入力要素を比較する型
     */
    public static <T, A extends Comparable<? super A>> Collector<T, List<T>, Stream<T>> sortingBy(Function<? super T, ? extends A> mapper){
        return new StalinSortCollectorImplements<T, A>(Comparator.naturalOrder(), mapper);
    }

    /**
     * 入力要素をmapper関数により変換された値の自然順序の逆順でスターリンソートしその結果をStreamに変換するCollectorを返します。
     * @param mapper 入力要素を変換する関数
     * @param <T> 入力要素の型
     * @param <A> 入力要素を比較する型
     */
    public static <T, A extends Comparable<? super A>> Collector<T, List<T>, Stream<T>> reverseSortingBy(Function<? super T, ? extends A> mapper){
        return new StalinSortCollectorImplements<T, A>(Comparator.reverseOrder(), mapper);
    }

    /**
     * 入力要素をcomparatorで比較した順序でスターリンソートしその結果をStreamに変換するCollectorを返します。
     * @param comparator 要素を比較するためのComparator
     * @param <T> 入力要素の型
     */
    public static <T> Collector<T, List<T>, Stream<T>> sorting(Comparator<? super T> comparator){
        return new StalinSortCollectorImplements<T, T>(comparator, x -> x);
    }

    /**
     * 入力要素をmapper関数により変換された値をcomparatorで比較した順序でスターリンソートしその結果をStreamに変換するCollectorを返します。
     * @param mapper 入力要素を変換する関数
     * @param comparator 要素を比較するためのComparator
     * @param <T> 入力要素の型
     * @param <A> 入力要素を比較する型
     */
    public static <T, A> Collector<T, List<T>, Stream<T>> sortingBy(Function<? super T, ? extends A> mapper, Comparator<? super A> comparator){
        return new StalinSortCollectorImplements<T, A>(comparator, mapper);
    }

    private static class StalinSortCollectorImplements<T, A> implements Collector<T, List<T>, Stream<T>> {
        private final Comparator<? super A> comparator;
        private final Function<? super T, ? extends A> mapper;
        private StalinSortCollectorImplements(Comparator<? super A> comparator, Function<? super T, ? extends A> mapper) {
            this.comparator = comparator;
            this.mapper = mapper;
        }

        @Override
        public Supplier<List<T>> supplier() {
            return ArrayList::new;
        }

        @Override
        public BiConsumer<List<T>, T> accumulator() {
            return (list, element) -> {
                if(list.isEmpty() || this.comparator.compare(this.mapper.apply(element), this.mapper.apply(list.get(list.size() -1))) >= 0) {
                    list.add(element);
                }
            };
        }

        @Override
        public BinaryOperator<List<T>> combiner() {
            return (x, y) -> Stream.concat(x.stream(), y.stream().dropWhile(p -> this.comparator.compare(this.mapper.apply(p), this.mapper.apply(x.get(x.size() -1))) < 0)).collect(Collectors.toList());
        }

        @Override
        public Function<List<T>, Stream<T>> finisher() {
            return List::stream;
        }

        @Override
        public Set<Characteristics> characteristics() {
            return EnumSet.of(Characteristics.CONCURRENT);
        }
    }
}

Collectorsクラスを参考にして、StalinSortCollectorはCollectorを返すstaticメソッドだけを持たせています。
実際にスターリンソートを実装しているのはStalinSortCollectorImplementsクラスです。

Collectorインターフェースとは

CollectorインターフェースはStreamのcollectメソッドに渡すことで蒐集方法を指示します。
これは3つの型パラメータと5つのメソッドおよび2つのstaicメソッド(実装に関係ないので説明は省略)を持っています。

型パラメータ <T,A,R>

  • T : 入力要素の型、Stream<T>のTに対応する。
  • A : 可変蓄積の型、コレクトする際の一時保存に使われる。
  • R : 結果の型、collectの返り値の型になる。

例としてintのコレクションをStringBuilderにappendしていって最終的にStringで返すCollectorであれば<Integer, StringBuilder, String>ということになります。
今回のStalinSortCollectorImplementsは、T型の要素をList<T>にaddして最終的にStreamにして返しているので、Collector<T, List<T>, Stream<T>>を実装しています。
なお、StalinSortCollectorImplements自体の型パラメータは比較用のmapperを受け取るため<T, A>です。

Supplier<A> supplier()

ここからは実装すべきメソッドの解説です。
supplierは途中結果を蓄積していくインスタンスを生成するSupplierを返します。
for文でいえば for([ここ];;) (forの初期化式)でやりたいことです。
なお、途中結果はこれが生成したインスタンスを使いまわすので、空文字列を返して文字列連結のようなことはできません。(文字列を結合すると新しいインスタンスが返るため)
ここでは、ArrayList::newを返しています。

BiConsumer<A, T> accumulator()

accumulatorはT型の入力要素を受け取ってA型のインスタンスに途中結果を蓄積するBiConsumerを返します。
for文でいえば for(;;)[ここ] (forの本文)でやりたいことです。
ここでは、途中結果を蓄積するListが空のときか、「入力要素 >= Listの最後の要素」となるときにListにaddしています。(逆に言えば「入力要素 < Listの最後の要素」のときに粛清しています。)

BinaryOperator<A> combiner()

combinerは途中結果を蓄積したA型のインスタンス同士を結合するBinaryOperatorを返します。
Streamは並列実行される可能性があるため、並列実行された場合に出来上がった結果同士をこのcombinerの関数で連結する必要があります。
ここでは、連結される側のListの要素が連結する側の最後の要素以上になるまで捨てて(粛清して)います。
なお、dropWhileはJava9以降でないと使えません。

Function<A, R> finisher()

finisherは結果を全て蓄積したA型のインスタンスに対してする仕上げの処理のFunctionを返します。
ここでは、スターリンソートの済んだListをStreamにして返しています。
こうすることで、collectは終端操作なのにもかかわらずメソッドチェーンを継続することが出来ます。

Set characteristics()

characteristicsはこのCollectorの属性を示すCollector.CharacteristicsのSetを返します。
CONCURRENT(並列実行できる), UNORDERED(順序を持たない), IDENTITY_FINISH(finisherを省略できる)の3つがあります。
ここでは、finisherに処理があり、順序が重要なソートであるためCONCURRENTのみを返しています。

使用例

public class Soviet {
    public static void main(String... args) {
        Stream.of(1,2,2,4,3,5,3,5,7,1,1,9)
            .collect(StalinSortCollector.sorting())
            .forEach(System.out::println);
    }
}
1
2
2
4
5
5
7
9
public class Russia {
    public static void main(String... args) {
        Stream.of(12,2,23,499,325,51,334,55555,7898,1019,19,12345)
            .parallel()
            .collect(StalinSortCollector.sortingBy(x -> String.valueOf(x).length()))
            .forEach(System.out::println);
    }
}
12
23
499
325
334
55555
12345

やはりstreamで処理できると気持ちいいですね。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away