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:

• Des personnes qui maîtrisent Scala --Les personnes qui souhaitent se familiariser avec les fonctionnalités fonctionnelles de Java

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