Überblick

Ich habe versucht, die Stalin-Sortierung, einen epochalen Sortieralgorithmus für den Berechnungsbetrag O (n), in Haskell #Haskell zu implementieren

Es scheint, dass Starlin Sort beliebt ist, also werde ich es in Java schreiben. Die von Java 8 eingeführte Stream-API ist bereits bekannt, nicht wahr? Dieses Mal erstellen wir eine Implementierungsklasse der Collector-Schnittstelle, die die Collect-Methode empfängt, damit der Stream eine coole Sterling-Sortierung durchführen kann.

Code

/**
 *Collector-Implementierungsklasse, die die Stalin-Sortierung implementiert
 */
public final class StalinSortCollector {
    private StalinSortCollector() {}
    /**
     *Gibt einen Collector zurück, bei dem Starlin die Eingabeelemente in natürlicher Reihenfolge sortiert und das Ergebnis in einen Stream konvertiert.
     * @param <T>Eingabeelementtyp
     */
    public static <T extends Comparable<? super T>> Collector<T, List<T>, Stream<T>> sorting(){
        return new StalinSortCollectorImplements<T, T>(Comparator.naturalOrder(), x -> x);
    }

    /**
     *Gibt einen Collector zurück, bei dem Starlin die Eingabeelemente in umgekehrter natürlicher Reihenfolge sortiert und das Ergebnis in einen Stream konvertiert.
     * @param <T>Eingabeelementtyp
     */
    public static <T extends Comparable<? super T>> Collector<T, List<T>, Stream<T>> reverseSorting(){
        return new StalinSortCollectorImplements<T, T>(Comparator.reverseOrder(), x -> x);
    }

    /**
     *Gibt einen Collector zurück, bei dem Stalin die Eingabeelemente in der natürlichen Reihenfolge der von der Mapper-Funktion konvertierten Werte sortiert und das Ergebnis in einen Stream konvertiert.
     * @param mapper Funktion zum Konvertieren von Eingabeelementen
     * @param <T>Eingabeelementtyp
     * @param <A>Geben Sie ein, um Eingabeelemente zu vergleichen
     */
    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);
    }

    /**
     *Gibt einen Collector zurück, bei dem Stalin die Eingabeelemente in umgekehrter Reihenfolge der natürlichen Reihenfolge der von der Mapper-Funktion konvertierten Werte sortiert und das Ergebnis in einen Stream konvertiert.
     * @param mapper Funktion zum Konvertieren von Eingabeelementen
     * @param <T>Eingabeelementtyp
     * @param <A>Geben Sie ein, um Eingabeelemente zu vergleichen
     */
    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);
    }

    /**
     *Gibt einen Collector zurück, bei dem Starlin die Eingabeelemente in der Reihenfolge sortiert, in der sie vom Vergleicher verglichen werden, und das Ergebnis in einen Stream konvertiert.
     * @Komparator zum Vergleichen von Param-Komparatorelementen
     * @param <T>Eingabeelementtyp
     */
    public static <T> Collector<T, List<T>, Stream<T>> sorting(Comparator<? super T> comparator){
        return new StalinSortCollectorImplements<T, T>(comparator, x -> x);
    }

    /**
     *Gibt einen Collector zurück, bei dem Stalin die von der Mapper-Funktion konvertierten Eingabeelemente in der Reihenfolge sortiert, in der sie vom Vergleicher verglichen werden, und das Ergebnis in Stream konvertiert.
     * @param mapper Funktion zum Konvertieren von Eingabeelementen
     * @Komparator zum Vergleichen von Param-Komparatorelementen
     * @param <T>Eingabeelementtyp
     * @param <A>Geben Sie ein, um Eingabeelemente zu vergleichen
     */
    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 In Bezug auf die Klasse verfügt StalinSortCollector nur über statische Methoden, die Collectors zurückgeben. Ich lasse dich. Die StalinSortCollectorImplements-Klasse implementiert tatsächlich Stalin Sort.

Was ist die Collector-Schnittstelle?

Collector Die Schnittstelle gibt die Erfassungsmethode an, indem sie an die Erfassungsmethode von Stream übergeben wird. .. Es hat 3 Typparameter, 5 Methoden und 2 statische Methoden (nicht relevant, da es nicht implementiert ist).

Geben Sie den Parameter \ <T, A, R> ein

T: Entspricht dem Eingabeelementtyp T von Stream \ .
A: Variabler Speichertyp, der beim Sammeln für die temporäre Speicherung verwendet wird.
R: Der Ergebnistyp, der Rückgabetyp des Sammelns.

Wenn es sich beispielsweise um einen Collector handelt, der eine Sammlung von Ints an StringBuilder anfügt und sie schließlich als String zurückgibt, lautet sie \ <Integer, StringBuilder, String>. Dieses Mal fügt StalinSortCollectorImplements ein Element vom Typ T zu List \ hinzu und gibt es schließlich als Stream zurück. Implementieren Sie also Collector \ <T, List \ , Stream \ >. Ich bin. Der Typparameter von StalinSortCollectorImplements selbst ist \ <T, A>, da er zum Vergleich einen Mapper empfängt.

Supplier<A> supplier()

Das Folgende ist eine Beschreibung der zu implementierenden Methoden. Der Lieferant gibt einen Lieferanten zurück, der eine Instanz erstellt, die die Ergebnisse auf dem Weg sammelt. Apropos for-Anweisung, es ist das, was Sie mit for ([here] ;;) (Initialisierungsformel von for) tun möchten. Da das Zwischenergebnis die dadurch generierte Instanz wiederverwendet, ist es außerdem nicht möglich, eine leere Zeichenfolge zurückzugeben und so etwas wie eine Verkettung von Zeichenfolgen durchzuführen. (Weil das Kombinieren von Zeichenfolgen eine neue Instanz zurückgibt) Hier wird ArrayList :: new zurückgegeben.

BiConsumer<A, T> accumulator()

Der Akkumulator verwendet ein Eingabeelement vom Typ T und gibt einen BiConsumer zurück, der Zwischenergebnisse in einer Instanz vom Typ A akkumuliert. Apropos Aussagen, es ist das, was Sie mit for (;;) [here] (dem Körper von for) machen wollen. Hier wird es der Liste hinzugefügt, wenn die Liste, in der die Zwischenergebnisse gespeichert sind, leer ist oder wenn "Eingabeelement> = letztes Element der Liste". (Umgekehrt, wenn "Eingabeelement <letztes Element der Liste", wird ** Stille ** ausgeführt.)

BinaryOperator<A> combiner()

Der Kombinierer gibt einen BinaryOperator zurück, der Instanzen vom Typ A kombiniert, bei denen Zwischenergebnisse akkumuliert wurden. Da Stream parallel ausgeführt werden kann, müssen die Ergebnisse verkettet werden, die bei paralleler Ausführung mit dieser Kombiniererfunktion erzielt werden. Hier werden die Elemente der Liste auf der verketteten Seite verworfen (** bereinigt **), bis sie gleich oder größer als das letzte Element auf der verketteten Seite sind. Beachten Sie, dass dropWhile nur mit Java 9 oder höher verwendet werden kann.

Function<A, R> finisher()

Der Finisher gibt die Funktion des Endbearbeitungsprozesses für die Instanz vom Typ A zurück, die alle Ergebnisse gesammelt hat. Hier wird die nach Starlin sortierte Liste als Stream zurückgegeben. Auf diese Weise kann collect die Methodenkette fortsetzen, obwohl es sich um eine Beendigungsoperation handelt.

Set characteristics()

properties gibt eine Reihe von Collector.Characteristics zurück, die die Attribute dieses Collectors angeben. Es gibt drei Typen: CONCURRENT (kann parallel ausgeführt werden), UNORDERED (keine Reihenfolge) und IDENTITY_FINISH (Finisher kann weggelassen werden). Hier wird nur CONCURRENT zurückgegeben, da der Finisher verarbeitet wird und die Bestellung eine wichtige Sortierung ist.

Anwendungsbeispiel

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);
    }
}

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);
    }
}

Immerhin fühlt es sich gut an, mit Stream verarbeiten zu können.

Ich habe versucht, Sterling Sort mit Java Collector zu implementieren

Überblick

Code

Was ist die Collector-Schnittstelle?

Geben Sie den Parameter \ <T, A, R> ein

Anwendungsbeispiel