Алоха всем.
Ни для кого не секрет, что алгоритмические задачи уже стали/становятся обыденными на техническом интервью. Кто-то может любить это, кто-то ненавидеть, но факт остается фактом, что бы пройти собеседование нужно научится решать алгоритмы.
А как быть интервьюерам? Какую задачу дать кандидату? Как понять сигналы, что кандидат «шарит»?
Я наткнулся на интересную статью по интервью на Senior инженера. Там у парня спрашивают базовую задачу FizzBuzz.
Условие задачи
Given an integer n, return a string array answer (1-indexed) where:
-
answer[i] == "FizzBuzz"ifiis divisible by3and5. -
answer[i] == "Fizz"ifiis divisible by3. -
answer[i] == "Buzz"ifiis divisible by5. -
answer[i] == i(as a string) if none of the above conditions are true. — это условие мы не будем проверять.
Example 1:
Input: n = 3 Output: ["1","2","Fizz"] Example 2:
Input: n = 5 Output: ["1","2","Fizz","4","Buzz"] Example 3:
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
В Java компилятор и оптимизатор JVM (Just-In-Time Compiler) могут вносить изменения в порядок выполнения инструкций в целях оптимизации производительности. Когда вы используете System.out.println для вывода данных, компилятор может решить переставить или оптимизировать строки кода, что может привести к неожиданным результатам при замерах времени выполнения.
Например, компилятор может решить отложить вывод в консоль до более позднего момента, когда это будет наименее влиятельным на производительность. Такие оптимизации могут сделать ваши замеры времени менее точными.
Для точных замеров производительности в Java лучше использовать специализированные инструменты, такие как Java Microbenchmarking Harness (JMH) или профайлеры производительности. Эти инструменты предоставляют надежные и консистентные результаты, учитывая различные аспекты работы с виртуальной машиной Java и оптимизациями кода.
Поэтому этот вариант мы отбрасываем. Я решил использовать бенч марки. Настроить их мне прекрасно помогла эта статья — https://www.baeldung.com/java-microbenchmark-harness. Я не претендую на то, что это сто процентно верное решение и если я делал что то не так дайте мне знать пожалуйста.
Зависимости
<!-- Start for benchmarks <dependency> <groupId>org.openjdk.jmh</groupId> <artifactId>jmh-core</artifactId> <version>1.37</version> </dependency><dependency> <groupId>org.openjdk.jmh</groupId> <artifactId>jmh-generator-annprocess</artifactId> <version>1.37</version> </dependency> <!-- End for benchmarks-->Аннотации
@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<String> 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<String> rez = new ArrayList<>(); for (int i = 0; i < LIMIT; i++){ StringBuilder sb = new StringBuilder(); if (i % 3 == 0){ sb.append("Fizz"); } 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<String> 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<String> 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<String> 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<String> printFizzBuzzInRange(int start, int end) { List<String> 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<CompletableFuture<List<String>>> futures = new ArrayList<>(); for (int i = 0; i < NUM_THREADS; i++) { final int start = i * chunkSize + 1; final int end = (i + 1) * chunkSize; CompletableFuture<List<String>> future = CompletableFuture.supplyAsync(() -> { return printFizzBuzzInRange(start, end); }); futures.add(future); } List<String> 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<String> printFizzBuzzInRange(int start, int end) { List<String> 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<String> 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)
Стало немного быстрее. Можно ли как-то это улучшить? Думаю нужно поиграться с потоками и размером чанков, который процессит каждый поток. Если знаете еще варианты буду рад их услышать.
Итоги:
|
Тест |
Min Time |
Avg Time |
|
init0 |
9_457_337.807 |
9_623_423.545 |
|
init1 |
30_502_586.036 |
32_507_915.687 |
|
init2 |
8_767_079.539 |
8_915_412.908 |
|
init3 |
401_633.964 |
405_473.708 |
|
init4 |
73_281.388 |
78_501.416 |
|
init5 |
122_244.382 |
128_504.915 |
|
init3 на 6 потоков |
951_781.368 |
1_141_332.416 |
|
init4 на 6 потоков |
60_190.729 |
62_439.748 |
Таким образом даже в простой базовой задаче вы можете найти шанс показать свои знания и опыт.
ссылка на оригинал статьи https://habr.com/ru/articles/781256/
Добавить комментарий