Implémenter un tri rapide de type fonction en Java

introduction

J'ai essayé d'implémenter un tri rapide en utilisant l'expression lambda et Stream en Java. Le public cible de cet article est:

expression lambda

L'expression lambda peut être écrite sous la forme (argument) -> return value, et la fonction peut être appelée avec la méthode apply.

import java.util.function.Function;

public class Main {
    public static void main(String[] args) {
        Function<String, String> addHoge = (final String str) -> str + "hoge";
        System.out.println(addHoge.apply("fuga"));
    }
}

De plus, si vous souhaitez écrire plusieurs expressions, vous pouvez utiliser des blocs.

import java.util.function.Function;

public class Main {
    public static void main(String[] args) {
        Function<String, String> addHoge = (final String str) -> {
            String hoge = "hoge";
            return str + hoge;
        };
        System.out.println(addHoge.apply("fuga"));
    }
}

Stream Stream est une classe qui prend en charge les opérations de type fonction sur les éléments d'une collection. Stream peut être utilisé en appelant la méthode stream () de la classe de collection.

Si vous écrivez un programme qui affiche des multiples de 2 en utilisant stream (), ce sera comme suit.

Java


Arrays.asList(3, 21, 34, 0).stream().filter(n -> n % 2 == 0).forEach(System.out::println);

Avec Scala, cela ressemble à ceci: Comparé à Java, le code est plus simple car vous n'avez pas besoin d'écrire stream ().

Scala


List(3, 21,34, 0).filter(_ % 2 == 0).foreach(println)

Code source (Scala)

Avant d'implémenter le tri rapide en Java, voici le code implémenté dans Scala. Le tri rapide «pivot» est spécifié au début du tableau.

object Main extends App {
    println(quickSort(List(3, 21, 34, 0, -30, 55, 10)))
    
    def quickSort(nums: List[Int]): List[Int] = {
      nums.headOption.fold(List[Int]()){ pivot =>
        val left = nums.filter(_ < pivot)
        val right = nums.filter(pivot < _)
        quickSort(left) ++ List(pivot) ++ quickSort(right)
      }
    }
}

Code source (Java)

Ce qui suit est une implémentation du tri rapide en Java.

Comparé au code de Scala, je suis submergé par la quantité de code Java, mais je pense que la logique elle-même a presque la même implémentation.

La seule différence de logique est la méthode du pli. Il y a des endroits où la méthode fold est utilisée dans le code Scala, mais il n'y a pas de méthode fold dans le type Java Optional (type Option dans Scala). Au lieu de cela, la méthode map et la méthode OrElseGet (méthode getOrElse dans Scala) sont utilisées en combinaison.

import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
import static java.util.stream.Collectors.toList;
import java.util.stream.Stream;

public class Main {
    public static void main(String[] args) {
        final List<Integer> nums = Arrays.asList(3, 21, 34, 0, -30, 55, 10);
        final List<Integer> sorted = quickSort(nums);
        System.out.println(sorted.toString());
    }

    private static List<Integer> quickSort(final List<Integer> nums) {
        return nums.stream().findFirst().map((final Integer pivot) -> {
            final List<Integer> left = nums.stream().filter(n -> n < pivot).collect(toList());
            final List<Integer> middle = Collections.singletonList(pivot);
            final List<Integer> right = nums.stream().filter(n -> pivot < n).collect(toList());
            return Stream.of(quickSort(left), middle, quickSort(right)).flatMap(Collection::stream).collect(toList());
        }).orElseGet(Collections::emptyList);
    }
}

Recommended Posts

Implémenter un tri rapide de type fonction en Java
Essayez le type fonctionnel en Java! ①
Implémentation de l'authentification en deux étapes en Java
Implémenter l'authentification de base en Java
Implémenter une combinaison de mathématiques en Java
2 Implémentez une analyse syntaxique simple en Java
Implémenter l'envoi d'e-mails en Java
Implémentez rm -rf en Java.
Implémenter la signature XML en Java
3 Implémentez un interpréteur simple en Java
Implémenter reCAPTCHA v3 dans Java / Spring
Implémenter la fonction PHP implode en Java
Essayez d'implémenter Yuma en Java
1 Implémentez une analyse de phrase simple en Java
Comment implémenter le calcul de la date en Java
Comment implémenter le filtre de Kalman par Java
Implémenter l'autorisation API Gateway Lambda dans Java Lambda
Partition en Java
Essayez d'implémenter l'ajout n-aire en Java
Changements dans Java 11
Janken à Java
Comment appliquer les conventions de codage en Java
[Java] Interface fonctionnelle
Implémenter quelque chose comme une pile en Java
Taux circonférentiel à Java
FizzBuzz en Java
À propos de l'interface fonctionnelle Java
Lire JSON en Java
Implémentation de l'interpréteur par Java
Faites un blackjack avec Java
Application Janken en Java
NVL-ish guy en Java
Joindre des tableaux en Java
"Hello World" en Java
Interface appelable en Java
Commentaires dans la source Java
Fonctions Azure en Java
Formater XML en Java
Implémentation Boyer-Moore en Java
Hello World en Java
Utiliser OpenCV avec Java
Mémorandum WebApi avec Java
Détermination de type en Java
Exécuter des commandes en Java (ping)
Divers threads en java
Implémentation du tri de tas (en java)
API Zabbix en Java
Art ASCII à Java
Comparer des listes en Java
POST JSON en Java
Exprimer l'échec en Java
Implémenter CustomView dans le code
Créer JSON en Java
Manipulation de la date dans Java 8
Nouveautés de Java 8
Utiliser PreparedStatement en Java
Nouveautés de Java 9,10,11
Exécution parallèle en Java