README
¶
Задача на оптимизацию алгоритма №1
Задача создана для собеседований и для соревнования на конференции SpectrumData 2022
В данном пакете содержится постановка задачи, базовая функция и набор шаблонных тестов и бенчмарков для проверки своего решения.
Использование GoLang в качестве языка задания связано со следующими причинами
- встроенная поддержка benchmark на уровне основных утилит языка
- с точки зрения кодирования задача относительно простая и как раз даст возможность легко освоить новый язык и попробовать на нем писать тем, кто работает с Kotlin, Python, PHP
Естественно Вам нужно установить на Ваш компьютер (если еще не установлено):
- golang 1.18 (обязательно читайте инструкцию по установке на сайте golang),
не полагайтесь на автоматический
apt-get install! - можете получить старую версию - если не хочется работать в блокноте - если есть подписка JetBrains - ставьте GoLand, если есть IDEA EE - ставьте на нее плагин, если и этого нет, то ставьте vscode - а на него плагин основной для работы с GoLang
Итак, условия задачи
Вам дана функция:
package basis
//BasicSuperFuncImpl - начальная не оптимизированная версия функции
// описывает основной инвариантный алгоритм:
// 1. `n==0` -> `x1`
// 2. `n==1` -> `x1 * x2`
// 3. `n>1` -> `f(x1, x2, n-2) * f(x1, x2, n-1)`
func BasicSuperFuncImpl(x1 float64, x2 float64, n uint8) float64 {
switch n {
case 0:
return x1
case 1:
return x1 * x2
default:
return BasicSuperFuncImpl(x1, x2, n-2) * BasicSuperFuncImpl(x1, x2, n-1)
}
}
Функция имеет более чем скромные показатели производительности. Так в случае значений n 30 она начинает тратить ~5500000 ns/op на достаточно мощной машине автора задачи.
В то же время при грамотном подходе, можно добиться прироста производительности в 30000, так у автора среднее время ~170 ns/op
Как же решать задачу
В данном репозитории кроме функции BasicSuperFuncImpl еще определены и базовые функции для тестов SuperFuncTestCase, SuperFuncBenchmark, которым можно передать ссылку на Вашу реализацию и они проведут тестирование на сходимости результатов, а затем выполнят проверку производительности.
Ну и конечно не надо курочить сам этот репозиторий! Тем более что все решения всех участников должны быть изолированы.
Для этого вы должны использовать шаблон для решения - это отдельный репозиторий и как с ним работать подробно описано в его README.md
Собственно добавить к этому нечего - читайте эту инструкцию, и пытайтесь решить задачу.
P.S. Нет никакой тайны в том как устроен тест и бенчмарк, которым будет проверяться Ваш код - спокойно изучите все что душе угодно тут
Directories