Статьи

Функциональное программирование на Java 8 с примером jOOλ

Октябрь 27, 2017

Я наткнулся на интересный вопрос переполнения стека пользователем «mip» . Вопрос был:

Я ищу способ генерации буквенной последовательности:

A, B, C, ..., Z, AA, AB, AC, ..., ZZ.

Это можно быстро распознать как заголовки электронной таблицы Excel, которая делает именно это:

превосходить

До сих пор ни один из ответов не использовал функциональное программирование на Java 8, которое я принял за вызов. Мы собираемся использовать jOOλ , потому что Java 8 Stream API не предлагает достаточно функциональных возможностей для этой задачи .

Но сначала давайте разберем алгоритм функциональным образом. Нам нужны эти компоненты:

  1. (Воспроизводимое) представление алфавита
  2. Верхняя граница, т.е. сколько букв мы хотим произвести. Запрошенная последовательность переходит к ZZ, что означает, что верхняя граница будет 2
  3. Способ объединения каждой буквы алфавита с ранее созданными комбинированными буквами в декартовом произведении

Давайте посмотрим на некоторый код:

1. Генерация алфавита

Мы могли бы написать алфавит так:

List<String> alphabet = Arrays.asList("A", "B", ..., "Z");

но это было бы хромым. Давайте сгенерируем его, используя jOOλ:

List<String> alphabet = Seq
    .rangeClosed('A', 'Z')
    .map(Object::toString)
    .toList();

Выше генерируется «закрытый» диапазон ( Java-8-Stream-говорят для диапазона с включительно верхней границей ) символов между Aи Z, отображает символы в строки и собирает их в список.

Все идет нормально. Теперь:

2. Использование верхней границы

Запрашиваемая последовательность символов включает в себя:

A .. Z, AA, AB, .. ZZ

Но мы могли бы легко представить, как можно расширить это требование, чтобы произвести следующее или даже больше.

A .. Z, AA, AB, .. ZZ, AAA, AAB, .. ZZZ

Для этого мы rangeClosed()снова будем использовать :

// 1 = A .. Z, 2 = AA .. ZZ, 3 = AAA .. ZZZ
Seq.rangeClosed(1, 2)
   .flatMap(length -> ...)
   .forEach(System.out::println);

Идея здесь состоит в том, чтобы создать новый поток для каждой отдельной длины в диапазоне [1 .. 2]и объединить эти потоки в один отдельный поток. flatMap()по сути такой же, как вложенный цикл в императивном программировании.

3. Объединить буквы в декартовом произведении

Это самая хитрая часть: нам нужно объединить каждую букву с каждой буквой lengthраз. Для этого мы будем использовать следующий поток:

Seq.rangeClosed(1, length - 1)
   .foldLeft(Seq.seq(alphabet), (s, i) -> 
       s.crossJoin(Seq.seq(alphabet))
        .map(t -> t.v1 + t.v2))
    );

Мы снова используем rangeClosed()для получения значений в диапазоне [1 .. length-1]. foldLeft()это то же самое reduce(), за исключением того, что foldLeft()гарантированно идет «слева направо» в потоке, не требуя ассоциативной функции свертывания. Уф.

Другими словами, более понятные термины: foldLeft()это не что иное, как обязательный цикл. «Семя» цикла, то есть начальное значение цикла, представляет собой полный алфавит ( Seq.seq(alphabet)). Теперь для каждого значения в диапазоне [1 .. length-1]мы производим декартово произведение ( crossJoin()) между «сложенными» до сих пор буквами и новым алфавитом и объединяем каждую комбинацию в одну новую строку ( t.v1и t.v2).

Это оно!

Объединяя все

Следующая простая программа выводит все значения из A .. Z, AA .. ZZ, AAA .. ZZZв консоль:

import java.util.List;

import org.jooq.lambda.Seq;

public class Test {
    public static void main(String[] args) {
        int max = 3;

        List<String> alphabet = Seq
            .rangeClosed('A', 'Z')
            .map(Object::toString)
            .toList();

        Seq.rangeClosed(1, max)
           .flatMap(length ->
               Seq.rangeClosed(1, length - 1)
                  .foldLeft(Seq.seq(alphabet), (s, i) -> 
                      s.crossJoin(Seq.seq(alphabet))
                       .map(t -> t.v1 + t.v2)))
           .forEach(System.out::println);
    }
}

отказ

Это, конечно, не самый оптимальный алгоритм для этого конкретного случая. Одна из лучших реализаций была предоставлена ​​неназванным пользователем в переполнении стека :

import static java.lang.Math.*;

private static String getString(int n) {
    char[] buf = new char[(int) floor(log(25 * (n + 1)) / log(26))];
    for (int i = buf.length - 1; i >= 0; i--) {
        n--;
        buf[i] = (char) ('A' + n % 26);
        n /= 26;
    }
    return new String(buf);
}

Само собой разумеется, что последний работает намного быстрее, чем предыдущий функциональный алгоритм.

35
Share: