FizzBuzz for Senior19.12.2023 06:15

Алоха всем.

Ни для кого не секрет, что алгоритмические задачи уже стали/становятся обыденными на техническом интервью. Кто-то может любить это, кто-то ненавидеть, но факт остается фактом, что бы пройти собеседование нужно научится решать алгоритмы.
А как быть интервьюерам? Какую задачу дать кандидату? Как понять сигналы, что кандидат «шарит»?
Я наткнулся на интересную статью по интервью на Senior инженера C++. Там у парня спрашивают базовую задачу FizzBuzz.

Условие задачи

Input: n = 3
Output: ["1","2","Fizz"]

Input: n = 5
Output: ["1","2","Fizz","4","Buzz"]

Input: n = 15
Output: ["1","2","Fizz","4","Buzz","Fizz","7","8","Fizz","Buzz","11","Fizz","13","14","FizzBuzz"]

Постойте, это же изи таска, которая может показать что кандидат знает базовый синтакс и может немного в логику, как такая задача может показать сеньерность кандидата?

А для этого есть множество follow up вопросов. Как можно улучшить алгоритм и сделать ее быстрее?

Парень из статьи с++ оч круто оптимизировал решение. И мне стало интересно, а как эти решения ведут себя на Java.

Перед тем как перейти к алгоритмам нужно понять, как мы будем мерить скорость. Если погуглить то первые ссылки скажут использовать System.out.println и трэкать так время. Но это не до конца верный вариант. Вы же знаете об оптимизаторе в Java? Может получиться так, что оптимизатор переставит эти строки и ваши замеры будут неверными.

Just-In-Time Compiler

Поэтому этот вариант мы отбрасываем. Я решил использовать бенч марки. Настроить их мне прекрасно помогла эта статья — https://www.baeldung.com/java-microbenchmark-harness. Я не претендую на то, что это сто процентно верное решение и если я делал что то не так дайте мне знать пожалуйста.

Зависимости

Аннотации

@Benchmark
@OutputTimeUnit(TimeUnit.NANOSECONDS)
@Fork(value = 1, warmups = 2)
@BenchmarkMode(Mode.AverageTime)

Я начал с базового алгоритма, которым решал бы в лоб эту задачу на интервью. При нахождении Fizz, Buzz или FizzBuzz я выводил их на экран. Поставил порог равный 1_000_000, запустил… Подождал чутка, пошел сделал кофе, выпил кофе, еще сходил за кофе, понял что не дождусь завершения и нужно делать что-то по другому. Изменить порог на 100_000 тоже не особо сильно помогло. Решил изменить немного эту задачу. Я решил собирать все в лист и просто выводить длинну листа как результат. Это поможет замерить мне время работы алгоритма, а не время вывода строки на экран =) Кстати, можно «оптимизировать» вывод на экран и заменить его записью в файл. Но это думаю если интересно можете попробовать сами =) Я слишком ленив.

Итак нулевой вариант:

init0

    private static final int LIMIT = 1_000_000;

    @Benchmark
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @Fork(value = 1, warmups = 2)
    @BenchmarkMode(Mode.AverageTime)
    public void init0() {
        List rez = new ArrayList<>();
        for (int i = 0; i < LIMIT; i++){
            if (i % 3 == 0 && i % 5 == 0){
                rez.add("FizzBuzz");
            } else if (i % 3 == 0){
                rez.add("Fizz");
            } else if (i % 5 == 0){
                rez.add("Buzz");
            }
        }
        System.out.println(rez.size());
    }

Код как вы видите достаточно простой. А это результаты бенчмарков:

init0
Result "com.codewars.fizzbuzz.FizzBuzz.init0":
9623423.545 ±(99.9%) 963191.903 ns/op [Average]
(min, avg, max) = (9_457_337.807, 9_623_423.545, 10_057_615.367), stdev = 250137.879
CI (99.9%): [8660231.642, 10586615.448] (assumes normal distribution)

Если я правильно понял на что смотреть в бенчмарке, то нас интересует (min, avg, max) (поправьте меня если я не прав). Ну пока это просто результаты =) сравнить не с чем.

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

«ой какой я молодец и сэкономлю время на конкатенации строк» — подумал я.

Вариант 1:

init1

    @Benchmark
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @Fork(value = 1, warmups = 2)
    @BenchmarkMode(Mode.AverageTime)
    public void init1() {
        List rez = new ArrayList<>();
        for (int i = 0; i < LIMIT; i++){
            StringBuilder sb = new StringBuilder();
            if (i % 3 == 0){
                sb.append("Fizz");
            } else if (i % 5 == 0){
                sb.append("Buzz");
            }
            if (!sb.isEmpty()){
                rez.add(sb.toString());
            }
        }
        System.out.println(rez.size());
    }

Результаты бенчмарков:

Result "com.codewars.fizzbuzz.FizzBuzz.init1":
32507915.687 ±(99.9%) 9189517.780 ns/op [Average]
(min, avg, max) = (30_502_586.036, 32_507_915.687, 35_904_132.541), stdev = 2386488.585
CI (99.9%): [23318397.906, 41697433.467] (assumes normal distribution)

Кек, норм так «улучшил». Я честно говоря не мог поверить, что результат так сильно изменился. Вероятнее всего это происходит из-за того, что я в цикле каждый раз создаю новый объект и наполняю его. В то время, как в первом варианте константы попадают в стринг пулл и берутся оттуда. Это лишь мое предположение. Как поправить меня вы знаете, пишите комменты.

Надо что-то с этим делать, поэтому немного подумав пришел в голову еще один вариант. В этом варианте мы не используем операцию %

Вариант 2:

init2

@Benchmark
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @Fork(value = 1, warmups = 2)
    @BenchmarkMode(Mode.AverageTime)
    public void init2() {
        List rez = new ArrayList<>();
        int i = 1, fizz = 0, buzz = 0;
        while (i <= LIMIT){
            fizz++; buzz++;
            if (fizz == 3 && buzz == 5) {
                rez.add("FizzBuzz");
                fizz = buzz = 0;
            } else if (fizz == 3) {
                rez.add("Fizz");
                fizz = 0;
            } else if (buzz == 5) {
                rez.add("Buzz");
                buzz = 0;
            }
            i++;
        }

        System.out.println(rez.size());
    }

Результаты бенчмарков:

init2
Result "com.codewars.fizzbuzz.FizzBuzz.init2":
8915412.908 ±(99.9%) 514862.288 ns/op [Average]
(min, avg, max) = (8_767_079.539, 8_915_412.908, 9_056_679.338), stdev = 133708.101
CI (99.9%): [8400550.620, 9430275.196] (assumes normal distribution)

Отличненько, наконец-то буст перформанса. Если смотреть относительно второго avg то буст в 3.6 раз. А если относительно первого то в 1.07 раза

Двигаемся дальше. А что можно сделать дальше? Подсматриваем на статью и код с++ и приходим к следующей идее кода. Можно попробовать сделать наш алгоритм параллельным. И ведь правда, мы можем разбить LIMIT на определенные чанки и процессить их независимо друг от друга. Я взял 4 потока, вы можете поэксперементировать и добавлять/удалять потоки.

Вариант 3:

init3

    private static final int LIMIT = 1_000_000;
    private static final int NUM_THREADS = 4;


    @Benchmark
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @Fork(value = 1, warmups = 2)
    @BenchmarkMode(Mode.AverageTime)
    public void init3() {
        ExecutorService executorService = Executors.newFixedThreadPool(NUM_THREADS);
        CountDownLatch latch = new CountDownLatch(NUM_THREADS);

        int chunkSize = LIMIT / NUM_THREADS;

        List results = Collections.synchronizedList(new ArrayList<>());

        for (int i = 0; i < NUM_THREADS; i++) {
            final int start = i * chunkSize + 1;
            final int end = (i + 1) * chunkSize;
            executorService.submit(() -> {
                List threadResults = printFizzBuzzInRange(start, end);
                results.addAll(threadResults);
                latch.countDown();
            });
        }

        try {
            latch.await(); // Wait for all threads to finish
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        executorService.shutdown();

        // Print the results
        System.out.println(results.size());
    }

    private static List printFizzBuzzInRange(int start, int end) {
        List threadResults = new ArrayList<>();
        for (int i = start; i <= end && i <= LIMIT; i++) {
            boolean divisibleBy3 = i % 3 == 0;
            boolean divisibleBy5 = i % 5 == 0;

            if (divisibleBy3 && divisibleBy5) {
                threadResults.add("FizzBuzz");
            } else if (divisibleBy3) {
                threadResults.add("Fizz");
            } else if (divisibleBy5) {
                threadResults.add("Buzz");
            }
        }
        return threadResults;
    }

Результаты бенчмарков:

init3
Result "com.codewars.fizzbuzz.ParallelFizzBuzz.init3":
405473.708 ±(99.9%) 13594.474 ns/op [Average]
(min, avg, max) = (401_633.964, 405_473.708, 410690.669), stdev = 3530.442
CI (99.9%): [391879.234, 419068.182] (assumes normal distribution)

И бау. Просто невероятное улучшение алгоритма. Улучшение в 21.9 раз относительно последнего теста и в 23.7 раз относительно первого бенчмарка.

Ну кажется сделать оптимальней уже не получится. Я тоже так думал и просто для тестов решил использовать другое апи для создания потоков. И вот такой код у меня получился

Вариант 4:

init4

    @Benchmark
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @Fork(value = 1, warmups = 2)
    @BenchmarkMode(Mode.AverageTime)
    public static void init4() {
        int chunkSize = LIMIT / NUM_THREADS;

        List>> futures = new ArrayList<>();

        for (int i = 0; i < NUM_THREADS; i++) {
            final int start = i * chunkSize + 1;
            final int end = (i + 1) * chunkSize;
            CompletableFuture> future = CompletableFuture.supplyAsync(() -> {
                return printFizzBuzzInRange(start, end);
            });
            futures.add(future);
        }

        List results = futures.stream()
                .map(CompletableFuture::join) // Wait for each CompletableFuture to complete
                .collect(ArrayList::new, List::addAll, List::addAll);

        // Print the results
        System.out.println(results.size());
    }

    private static List printFizzBuzzInRange(int start, int end) {
        List threadResults = new ArrayList<>();
        for (int i = start; i <= end && i <= LIMIT; i++) {
            boolean divisibleBy3 = i % 3 == 0;
            boolean divisibleBy5 = i % 5 == 0;

            if (divisibleBy3 && divisibleBy5) {
                threadResults.add("FizzBuzz");
            } else if (divisibleBy3) {
                threadResults.add("Fizz");
            } else if (divisibleBy5) {
                threadResults.add("Buzz");
            }
        }
        return threadResults;
    }

Результаты бенчмарков:

init4
Result "com.codewars.fizzbuzz.ParallelFizzBuzz2.init4":
78501.416 ±(99.9%) 40269.999 ns/op [Average]
(min, avg, max) = (73_281.388, 78_501.416, 97177.380), stdev = 10457.991
CI (99.9%): [38231.417, 118771.415] (assumes normal distribution)

Бум и снова улучшение. Причем значительное улучшение. Если честно по началу я не мог это объяснить. Но потом понял, что значительное время тратится на создание Executors.newFixedThreadPool(NUM_THREADS). Также, вероятно тратится время на executorService.shutdown(), но это я не тестировал. Можно попробовать вынести создание executorService на уровень выше и тестировать только сам алгоритм, но тогда тесты будут не до конца «честными». Ведь мы тестируем решение задачи.

Можно как-то еще поизвращаться над этим кодом? Да давайте попробуем. Будем использовать стрим апи =)

Вариант 5:

init5

    @Benchmark
    @OutputTimeUnit(TimeUnit.NANOSECONDS)
    @Fork(value = 1, warmups = 2)
    @BenchmarkMode(Mode.AverageTime)
    public static void init5() {
        List results = IntStream.rangeClosed(1, LIMIT)
                .parallel()
                .mapToObj(ParallelFizzBuzz3::printFizzBuzz)
                .filter(s -> !s.isEmpty())
                .toList();

        // Print the results
        System.out.println(results.size());
    }

    private static String printFizzBuzz(int num) {
        boolean divisibleBy3 = num % 3 == 0;
        boolean divisibleBy5 = num % 5 == 0;

        if (divisibleBy3 && divisibleBy5) {
            return "FizzBuzz";
        } else if (divisibleBy3) {
            return "Fizz";
        } else if (divisibleBy5) {
            return "Buzz";
        } else {
            return "";
        }
    }

Результаты бенчмарков:

init5
Result "com.codewars.fizzbuzz.ParallelFizzBuzz3.init5":
128504.915 ±(99.9%) 22111.085 ns/op [Average]
(min, avg, max) = (122_244.382, 128_504.915, 137007.708), stdev = 5742.179
CI (99.9%): [106393.830, 150616.000] (assumes normal distribution)

Как видите этот вариант работает тоже достаточно не плохо. Но медленнее если использовать CompletableFuture. Я решил увеличить колличество потоков для теста номер 4 и получил такой результат

Результаты бенчмарков вариант init3 на 6 потоков:
Result "com.codewars.fizzbuzz.ParallelFizzBuzz.init3":
1141332.416 ±(99.9%) 475676.047 ns/op [Average]
(min, avg, max) = (951_781.368, 1_141_332.416, 1_295_257.063), stdev = 123531.559
CI (99.9%): [665656.369, 1617008.463] (assumes normal distribution)

Получилось так себе. А что будет, если я добавлю 6 потоков в CompletableFuture

Результаты бенчмарков вариант init4 на 6 потоков:

Result "com.codewars.fizzbuzz.ParallelFizzBuzz2.init4":
62439.748 ±(99.9%) 7159.969 ns/op [Average]
(min, avg, max) = (60_190.729, 62_439.748, 64_841.281), stdev = 1859.421
CI (99.9%): [55279.779, 69599.717] (assumes normal distribution)

Стало немного быстрее. Можно ли как-то это улучшить? Думаю нужно поиграться с потоками и размером чанков, который процессит каждый поток. Если знаете еще варианты буду рад их услышать.

Итоги:

Таким образом даже в простой базовой задаче вы можете найти шанс показать свои знания и опыт.

© Habrahabr.ru