概要
計算量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で処理できると気持ちいいですね。
