Здравствуй, Хабр.
Недавно я проходил собеседование в одну солидную айтишную контору. Когда мы разобрались с формальностями, начался технический этап, на котором мне поручили написать fizzbuzz. По не вполне понятным мне причинам обсуждение решения этой задачи растянулось на довольно большой срок, после которого время на интервью уже вышло. Мы расстались на хорошей ноте, и мне пообещали перезвонить. Пока я жду оффер, я решил поделиться своим опытом прохождения интервью с широкой публикой, равно как и своим решением, ибо они показались мне заслуживающим внимания.
Начинаем
Интервьюер был настроен доброжелательно.
— Напишите программу, которая бы вывела числа от одного до ста включительно по следующим правилам: если число делится на 3, то выведите "fizz", если число делится на 5, то выведите "buzz", если число делится и на 3, и на 5, то выведите "fizzbuzz", а если ни одно из этих условий не выполняется, то выведите число как обычно.
— Хорошо. Как отделять числа друг от друга? По одному на строчку?
— Как вам удобно.
— Ясно. Какой язык программирования я могу использовать?
— Любой, с которым вам удобно. Впрочем, крайне желательно, чтобы это не был какой-то эзотерический язык программирования. А то у нас как-то один кандидат — доброжелательный интервьюер на секунду поёжился — как-то развернул список на чём-то вроде Haskell и даже тестов не написал.
— Спасибо, я буду использовать Rust.
— Это тот новый хайповый язык программирования?
— Да. Он похож по синтаксису на C, так что проблем с пониманием возникнуть не должно.
В этот момент интервьюер облегчённо выдохнул.
— Хорошо. Можете начинать.
Я открыл Rust playground и начал писать код:
struct Z;
struct S<T>(T);Интервьюер слегка нахмурился.
— Не могли бы вы пояснить, что вы делаете?
— Конечно. Я делаю свои собственные числа согласно аксиоматике Пеано. Как видите, эти два определения напрямую отражают аксиомы: натуральное число — это либо ноль, либо некоторое иное натуральное число, увеличенное на единицу.
— А зачем вам эти определения? Разве вы не можете обойтись встроенными числовыми типами?
— Разумеется, могу. Однако в той задаче, которой вы мне дали, отсутствуют входные данные, весь вывод программы можно подсчитать заранее, поэтому я бы хотел избежать ненужных вычислений в рантайме. С другой стороны, все преобразования над типами гарантированно выполняются на этапе компиляции — всё-таки Rust статически типизированный язык — поэтому вынесение чисел на уровень типов позволит делать меньше в рантайме.
— А, ну если вы так считаете, — сказал интервьюер после некоторой паузы — хорошо, продолжайте.
Я где-то читал, что на собеседовании хорошим тоном является проговаривать свои мысли вслух. Поэтому, а также из-за вопросов интервьюера я решил самостоятельно комментировать то, что пишу:
— Конечно, мы можем составить из этих S нужную нам сотню, но это несколько утомительно и вдобавок увеличивает шанс внести ошибку из-за опечатки, поэтому я реализую способ складывать подобные числа:
trait Add<Rhs> {
type Sum;
}
type SumOf<N, M> = <N as Add<M>>::Sum;— Для того, чтобы составить сумму из чисел, записанных в типах, нам потребуются трейты (некоторые также называют их "типажами", но мне этот термин не очень нравится). Функций на уровне типов в Rust, увы, нет, но трейты с ассоциированными типами позволяют до некоторой степени их эмулировать. Сейчас я написал новый трейт, который будет сопоставлять Self (типу, для которого определяется трейт) и Rhs их сумму через ассоциированный тип Sum. Так как развёрнутый синтаксис, используемый для сопоставления типу его ассоциированного типа определённого трейта, несколько шумный, для удобства я определил псевдоним, который скрывает эту громоздкую конструкцию.
Я сделал небольшую паузу, чтобы дать интервьюеру переварить услышанное, и продолжил:
— В силу того, что определение чисел у меня индуктивное, определение суммы также должно быть индуктивным. Базой индукции, очевидно, является случай, когда одно из слагаемых равно нулю: в этом случае сумма равна другому слагаемому. Но что делать в шаге индукции, когда мы складываем два ненулевых числа? В таком случае мы можем одно слагаемое — скажем, первое — уменьшить на единицу, а другое — увеличить на единицу, и для вновь образованных слагаемых подсчитать сумму. Сумма от этого, разумеется, не изменится, но мы свели задачу к меньшей. Рано или поздно это уменьшение приведёт к тому, что одно из слагаемых станет нулевым, и мы сможем воспользоваться базой индукции. Выразим это в коде:
impl<N> Add<N> for Z {
type Sum = N;
}
impl<N, M> Add<M> for S<N>
where
N: Add<S<M>>,
{
type Sum = SumOf<N, S<M>>;
}— Имея на руках сложение, уже несложно выписать нужные нам константы: три, пять и количество требуемых элементов: сто.
type One = S<Z>;
type Two = SumOf<One, One>;
type Three = SumOf<One, Two>;
type Five = SumOf<Two, Three>;
type Ten = SumOf<Five, Five>;
type TwentyFive = SumOf<Five, SumOf<Ten, Ten>>;
type Fifty = SumOf<TwentyFive, TwentyFive>;
type OneHundred = SumOf<Fifty, Fifty>;
type N = OneHundred;Составляем список
— Окей, с числами мы разобрались. Теперь нам нужно каким-то образом отсчитать от единицы до сотни. Судя по всему, нам понадобится список из них. Списки также несложно определить индуктивно: это или пустой список, или пара из первого элемента списка и всех остальных элементов списка:
struct Nil;
struct Cons<H, T>(H, T);— Кстати, как нетрудно видеть, определённые мною числа изоморфны спискам из элементов unit-типов, то есть я вполне мог бы вместо S<N> использовать Cons<(), N>. Но я решил этого не делать, чтобы сохранить ясность кода.
Интервьюер медленно кивнул. Убедившись, что меня понимают, я продолжил:
— Теперь встаёт вопрос, а как нам составить список из чисел от единицы до сотни включительно. К сожалению, попытка сделать это напрямую вынудит нас задать на числах отношение порядка, и в силу того, что требования к типам в Rust вычисляются не лениво, подход в лоб приведёт нас к рекурсии при вычислении ограничений на типы. Поэтому поступим по-другому: сделаем сначала список от сотни до единицы, а потом обратим его.
Нам опять потребуется функция на уровне типов, которую мы выразим как трейт с ассоциированным типом:
trait RangeDownFrom {
type Output;
}
impl RangeDownFrom for Z {
type Output = Cons<Z, Nil>;
}
impl<N> RangeDownFrom for S<N>
where
N: RangeDownFrom,
{
type Output = Cons<S<N>, N::Output>;
}
type MakeRangeDownFrom<N> = <N as RangeDownFrom>::Output;— Кстати, кое-что с этой функцией не так. Вам очевидно, что именно?
Интервьюер немного помолчал, а потом ответил:
— Наверное… Но не могли вы сами сказать?
Сообразив, что меня проверяют, я продолжил со своим ответом:
— Эта функция делает список, который кончается нулём, а не единицей. К счастью, отбросить потом голову списку — плёвое дело, а в некоторых аспектах это даже окажется удобным, — тут я виновато улыбнулся — я уже прикидывал, как такое делать.
Интервьюер тоже улыбнулся, но, как мне показалось, несколько натянуто. Я перешёл к следующей части решения:
— Обращение списка, как известно, является банальной левой свёрткой по списку с операций cons с аргументами в обратном порядке и пустым списком в качестве начального значения. К сожалению, система типов Rust недостаточно продвинута, чтобы выразить на уровне типов функции высшего порядка, поэтому свёртку придётся писать руками. Впрочем, она тут достаточно простая: для пустого списка нам достаточно вернуть аккумулятор, а для cons нам надо отделить голову, приставить её к аккумулятору и продолжить обращение с хвостом списка. Всё это достаточно коротко и ясно выражается в коде:
trait ReverseWith<Acc> {
type Output;
}
impl<Acc> ReverseWith<Acc> for Nil {
type Output = Acc;
}
impl<Head, Tail, Acc> ReverseWith<Acc> for Cons<Head, Tail>
where
Tail: ReverseWith<Cons<Head, Acc>>,
{
type Output = <Tail as ReverseWith<Cons<Head, Acc>>>::Output;
}
type Reverse<List> = <List as ReverseWith<Nil>>::Output;
type RangeTo<N> = Reverse<RangeDownFrom<N>>;Считаем тройки и пятёрки
— Теперь перейдём к сути задания. От нас требуется классифицировать числа по их остаткам от деления на три и на пять. В принципе, мы можем реализовать деление с остатком чисел Пеано, но это заняло бы довольно много нудного кода. Вместо это попробуем прикинуть, как добиться нужного результата меньшими усилиями.
Я на время откинулся от клавиатуры.
— Что вообще означает, что остаток числа от деления на, скажем, три, равен нулю? По другому это можно сформулировать так, что если мы начнём считать от нуля, то каждое третье число будет, очевидно, делиться на три без остатка. Мы можем пройтись по всему списку, вручную отмечая каждый третий элемент. Конечно, мы не хотим повторять себя и хотим использовать схожий подход для пятёрки. Мы хотим абстрагироваться от конкретного числа, используя счётчик, который будет инкрементироваться для каждого элемента списка по некоторому модулю. Таким образом, нам нужно определить операцию инкрементирования по модулю некоего числа n, а потом прикрепить к этому счётчик и поднять эту операцию на уровень списков.
— Или же нет? — прервал я сам себя — при таком подходе мы неизбежно столкнёмся с теми же проблемами, что и при наивной реализации RangeTo: бесконечной рекурсии требований к типам. С другой стороны, реализовать декремент по некоторому модулю мы спокойно можем. При этом позиции, где счётчик принимает значение ноль, останутся теми же самыми — а именно они нам и нужны.
Снова определим результат индуктивно: ноль, уменьшенный на единицу по некоторому модулю, равен числу, на единицу меньшему модулю, а число, большее единицы, декрементированное по тому же модулю, ну, то же самое число, только без единицы. В коде это выглядит менее неловко, чем мои слова, — я снова принялся печатать:
trait DecrementByMod<M> {
type Output;
}
impl<T> DecrementByMod<S<T>> for Z {
type Output = T;
}
impl<M, T> DecrementByMod<M> for S<T> {
type Output = T;
}
type DecMod<T, M> = <T as DecrementByMod<M>>::Output;Теперь нам нужно прикрепить счётчик к списку. Конечно, можно сказать, что это какая-то правая свёртка, но тут это ясности не прибавляет, проще написать код:
trait EnumerateFromWithCycle<Start, N> {
type Output;
}
type EnumeratedFromWithCycle<T, Start, N> =
<T as EnumerateFromWithCycle<Start, N>>::Output;
impl<Start, N> EnumerateFromWithCycle<Start, N> for Nil {
type Output = Nil;
}
impl<Start, N, Head, Tail> EnumerateFromWithCycle<Start, N> for Cons<Head, Tail>
where
Start: DecrementByMod<N>,
Tail: EnumerateFromWithCycle<DecMod<Start, N>, N>,
{
type Output = Cons<
(Head, Start),
EnumeratedFromWithCycle<Tail, DecMod<Start, N>, N>,
>;
}Код становится немного угрожающим, но более сложных наворотов на уровне типов нам уже не потребуется. Введём алиасы для нужных нам операций:
type EnumerateFromZeroWithCycle3<T> = EnumerateFromZeroWithCycle<T, Three>;
type EnumerateFromZeroWithCycle5<T> = EnumerateFromZeroWithCycle<T, Five>;
type FizzBuzzEnumerate<T> = EnumerateFromZeroWithCycle5<
EnumerateFromZeroWithCycle3<T>>;Осталось только отобразить значение со счётчиками на нужное значение на уровне типов, что фактически сводится к сопоставлению с образцом:
struct Fizz;
struct Buzz;
struct FizzBuzz;
trait FizzBuzz {
type Output;
}
type ToFizzBuzz<T> = <T as FizzBuzz>::Output;
impl<T> FizzBuzz for ((T, Z), Z) {
type Output = FizzBuzz;
}
impl<T, N> FizzBuzz for ((T, Z), S<N>) {
type Output = Fizz;
}
impl<T, N> FizzBuzz for ((T, S<N>), Z) {
type Output = Buzz;
}
impl<T, N, M> FizzBuzz for ((T, S<N>), S<M>) {
type Output = T;
}
impl FizzBuzz for Nil {
type Output = Nil;
}
impl<Head, Tail> FizzBuzz for Cons<Head, Tail>
where
Head: FizzBuzz,
Tail: FizzBuzz,
{
type Output = Cons<
Head::Output,
Tail::Output,
>;
}Если честно, моего внутреннего пуриста немного коробит, что одно и то же определение используется и для отдельных элементов, и для списка целиком, но вреда тут это не несёт, а введение отдельного трейта для операций на списках не дало бы никаких преимуществ.
Я сделал небольшую паузу, чтобы выдохнуть, и продолжил:
— Что ж, у нас почти всё готово, осталось лишь собрать всё это воедино — и учесть тот факт, что список в итоге начинается с нуля и потому нуждается в срезании головы:
trait TailOf {
type Output;
}
type Tail<T> = <T as TailOf>::Output;
impl<Head, Tail> TailOf for Cons<Head, Tail> {
type Output = Tail;
}
type FizzBuzzList<T> = ToFizzBuzz<Tail<FizzBuzzEnumerate<RangeTo<T>>>>;
type List = FizzBuzzList<N>;Фактически, нам сейчас даже не нужно писать никакого рантайм-кода: мы можем просто написать что-то с использованием List, что не будет тайпчекаться, и компилятор выведет нам тип сам, — я с энтузиазмом набросал код:
fn foo() {
let _: List = ();
}Затем я нажал Ctrl+Enter и через пару секунд с довольным видом показал интервьюеру ошибку компиляции:
error[E0308]: mismatched types
--> src/lib.rs:162:19
|
162 | let _: List = ();
| ---- ^^ expected struct `Cons`, found `()`
| |
| expected due to this
|
= note: expected struct `Cons<S<Z>, Cons<S<S<Z>>, Cons<Fizz, Cons<S<S<S<S<Z>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<Z>>>>>>>, Cons<S<S<S<S<S<S<S<S<Z>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<FizzBuzz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Buzz, Cons<Fizz, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<S<Z>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>, Cons<Fizz, Cons<Buzz, Nil>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>`
found unit type `()`
For more information about this error, try `rustc --explain E0308`.
error: could not compile `playground` due to previous errorПереводим в строки
Интервьюер посмотрел на экран, прокрутил его вплоть до конца длинной ошибки, немного помолчал со сосредоточенным видом, а потом спросил меня:
— Извините, а что в итоге сделала ваша программа?
— Моя? — я развёл руками — моя программа не сделала ничего. В конце-концов, она не скомпилировалась.
Интервьюер вздохнул.
— Это не то, что от вас требовалось. От вас требовалось написать программу, которая будет, гм, запускаться, и выдавать нужный результат. Вдобавок, этот вывод, возможно, и правильный, но я не могу его прочитать, так что я не смогу сказать, правильный он или нет.
Я хлопнул себя по лбу.
— Ну конечно! Я совсем забыл про начальную задачу. Что ж, технически нам достаточно наваять скрипт на баше, который будет вызывать rustc на этом файле, но я согласен, что вывод не особо читаемый. Выходит, нам требуется сопоставить каждому элементу списка строковое значение. Для структур Fizz, Buzz и FizzBuzz это делается тривиально через трейт с ассоциированной константой строкового типа, а вот для чисел Пеано это несколько сложнее. Создание на этапе компиляции строки из числа в Rust является почти невыполнимой задачей, так что мы поступим иначе: будем использовать пару из массива байт и длины итоговой строки. Благодаря системе типов Rust мы легко можем объединить обе возможности в одном типе:
enum Str<const N: usize> {
Plain(&'static str),
Decomposed([u8; N], usize),
}Как вы могли заметить, этот тип параметризован максимальным размером байтового представления строки. В каком-то смысле это перебор, поскольку мы могли бы указать, скажем, массив из трёх байт, которых бы хватило для представления всех чисел до сотни включительно, но мне не хотелось бы затачиваться на конкретную верхнюю границу, тем более что требуемую длину мы всегда можем подсчитать. Что ж, займёмся переводом в строку и начнём с жужжащих типов:
trait AsStr<const N: usize> {
const VALUE: Str<{ N }>;
}
impl<const N: usize> AsStr<{ N }> for Fizz {
const VALUE: Str<{ N }> = Str::Plain("fizz");
}
impl<const N: usize> AsStr<{ N }> for Buzz {
const VALUE: Str<{ N }> = Str::Plain("buzz");
}
impl<const N: usize> AsStr<{ N }> for FizzBuzz {
const VALUE: Str<{ N }> = Str::Plain("fizzbuzz");
}Перейдём к численным типам. Вот тут уже посложнее: для перевода числа в строку нам нужно его численное значение. Значение это, впрочем, получается элементарно:
trait NumericValue {
const VALUE: usize;
}
impl NumericValue for Z {
const VALUE: usize = 0;
}
impl<N> NumericValue for S<N>
where
N: NumericValue,
{
const VALUE: usize = N::VALUE + 1;
}После того, как мы получили на руки численное значение, вывести его строковое представление уже не так сложно: достаточно последовательно брать остатки от деления на 10 и прибавлять их к ASCII-символу нуля — тут мы эксплуатируем тот факт, что в кодировке ASCII коды для цифр идут по порядку. Главное тут — не забыть, что мы таким образом получаем цифры в обратном порядке, поэтому после окончания процесса надо обернуть порядок символов:
const fn to_str<const N: usize>(mut value: usize) -> Str<{ N }> {
let mut s = [0; N];
if value == 0 {
s[0] = b'0';
return Str::Decomposed(s, 1)
}
let mut i = 0;
while value > 0 {
s[i] = (value % 10) as u8 + b'0';
value /= 10;
i += 1;
}
let n_digits = i;
let mut i = 0;
while i < n_digits / 2 {
let digit = s[n_digits - i - 1];
s[n_digits - i - 1] = s[i];
s[i] = digit;
i += 1;
}
Str::Decomposed(s, n_digits)
}Отлично. Теперь, получив нужное разложение, мы можем написать реализации AsStr одним махом для всех чисел на уровне типов:
impl<T, const N: usize> AsStr<{ N }> for T
where
T: NumericValue,
{
const VALUE: Str<{ N }> = to_str(<T as NumericValue>::VALUE);
}И теперь уже несложно отобразить список типов на список строковых значений:
trait AsStrList<const N: usize> {
type List;
const LIST: Self::List;
}
impl<const N: usize> AsStrList<{ N }> for Nil {
type List = Nil;
const LIST: Nil = Nil;
}
impl<Head, Tail, const N: usize> AsStrList<{ N }> for Cons<Head, Tail>
where
Head: AsStr<{ N }>,
Tail: AsStrList<{ N }>,
{
type List = Cons<Str, Tail::List>;
const LIST: Self::List = Cons(
<Head as AsStr<{ N }>>::VALUE,
<Tail as AsStrList<{ N }>>::LIST,
);
}А теперь подумаем о том, как получить из Str нативную растовую строку. Для варианта Str::Plain это тривиально, мы просто достаём значение. А что делать с Str::Decomposed? Тоже ничего сложного: обрезаем массив до указанной длины и вызываем std::str::from_utf8. Тут, однако, есть парочка неприятных вещей. Первое: std::str::from_utf8 возвращает Result, с которым надо что-то делать. Второе: и конвертация из байтов в строку, и нарезка слайса делают в рантайме проверки – вообще говоря, ненужные. Мы кладём в массив только ASCII-коды, так что строка заведомо корректна для UTF-8, а возвращаемая длина никогда не превысит длину массива: если это вдруг произойдёт, функция to_str или не скомпилируется, или запаникует, в зависимости от того, была она вызвана в const-контексте или нет. Так что мы можем использовать unsafe для того, чтобы избежать этих проверок… Но поля перечисления Str — публичные, туда можно положить всё, что угодно, в том числе и данные, для которых эти предположения неверны. Чтобы обойти эту проблему, мы сделаем новый тип с приватным полем, для которого оставим два публичных конструктора: обычный для создания из литерала и unsafe для создания из массива байт и длины. Пользователь небезопасного конструктора должен обещать, что предоставляемая длина не превышает длины массива, а сами данные в массиве до указанной длины корректно закодированы в UTF-8. В таком случае мы можем спокойно вызывать небезопасные функции внутри метода, который будет конструировать строку из этого нового типа. Этот новый тип я, пожалуй, назову Str, а старый Str назову StrInner. Вынесем всё это в отдельный модуль, так как границы видимости в Rust проходят именно по ним, — я начал печатать, вынося код в отдельный модуль:
mod str {
pub struct Str<const N: usize>(StrInner<{ N }>);
enum StrInner<const N: usize> {
Plain(&'static str),
Decomposed([u8; N], usize),
}
impl<const N: usize> Str<{ N }> {
pub const fn from_literal(s: &'static str) -> Self {
Self(StrInner::Plain(s))
}
pub const unsafe fn from_parts_unchecked(bytes: [u8; N], len: usize) -> Self {
Self(StrInner::Decomposed(bytes, len))
}
pub fn as_str(&self) -> &str {
match &self.0 {
&StrInner::Plain(s) => s,
&StrInner::Decomposed(ref bytes, len) => unsafe {
std::str::from_utf8_unchecked(bytes.get_unchecked(..len))
}
}
}
}
}
use crate::str::Str;Пару минут интервьюер ждал, пока я адаптировал код к новым изменениям.
— Ага, уже почти готово. Из крупного нам осталось реализовать обход списка, который у нас в итоге получится. К счастью, тут нет ничего сложного, всё опять определяется индуктивно:
trait ForEach<Arg> {
fn for_each<F>(&self, f: F)
where
F: FnMut(&Arg);
}
impl<Arg> ForEach<Arg> for Nil {
fn for_each<F>(&self, f: F)
where
F: FnMut(&Arg),
{}
}
impl<Arg, Tail> ForEach<Arg> for Cons<Arg, Tail>
where
Tail: ForEach<Arg>,
{
fn for_each<F>(&self, f: F)
where
F: FnMut(&Arg),
{
f(&self.0);
self.1.for_each(f);
}
}И ещё нам всё ещё нужно определить необходимое количество памяти для Str. Ну, тут всё элементарно:
const fn n_digits(mut n: usize) -> usize {
if n == 0 {
return 1
}
let mut ret = 0;
while n > 0 {
n /= 10;
ret += 1;
}
ret
}Окончательный результат
Я немного потянулся, разминая затёкшую спину.
— Итак, все необходимые части в сборе. Осталось только собрать их вместе:
fn main() {
<List as AsStrList<{ n_digits(<N as NumericValue>::VALUE) }>>::LIST
.for_each(|s| println!("{}", s.as_str()));
}Набрав этот код, я с некоторым колебанием нажал Ctrl+Enter, и через несколько секунд отобразился результат запуска программы:
Compiling playground v0.0.1 (/playground)
Finished dev [unoptimized + debuginfo] target(s) in 3.55s
Running `target/debug/playground`
1
2
fizz
4
buzz
fizz
7
8
fizz
buzz
11
fizz
13
14
fizzbuzz
16
17
fizz
19
buzz
fizz
22
23
fizz
buzz
26
fizz
28
29
fizzbuzz
31
32
fizz
34
buzz
fizz
37
38
fizz
buzz
41
fizz
43
44
fizzbuzz
46
47
fizz
49
buzz
fizz
52
53
fizz
buzz
56
fizz
58
59
fizzbuzz
61
62
fizz
64
buzz
fizz
67
68
fizz
buzz
71
fizz
73
74
fizzbuzz
76
77
fizz
79
buzz
fizz
82
83
fizz
buzz
86
fizz
88
89
fizzbuzz
91
92
fizz
94
buzz
fizz
97
98
fizz
buzzИнтервьюер несколько раз перевёл взгляд с экрана на меня и обратно, не проронив ни слова. Я терпеливо молчал. Через несколько секунд он спросил меня с видом, как будто только что что-то вспомнил:
— Скажите, а как вы собираетесь всё это тестировать?
Я ожидал это вопроса, так что мой ответ не заставил себя ждать:
— Что ж, в этом проекте можно выделить две части, которые можно тестировать независимо друг от друга. Одна из них — это перевод числа в декомпозированную строку. К счастью, эту часть можно элементарно покрыть тестами на основе свойств. А вот что касается построения списка, тот тут можно писать тесты этапы компиляции, которые будут проверять, что создаваемый тип равен ожидаемому. Конечно, выписывать вручную все эти типы будет несколько утомительно, но если сюда прикрутить макросы — можно процедурные для красивого синтаксиса, но, в принципе, можно обойтись и декларативными…
Интервьюер перебил меня, замахав руками:
— Хорошо, хорошо, мы вам верим.
Он вышел из кабинета, сославшись на то, что ему нужно переговорить с коллегами, а через пару минут вернулся и сказал мне, что на сегодня интервью окончено и что я могу идти домой.
— Мы вам позвоним, — сказал он мне на прощание, пожимая руку.
Правда, этого звонка я почему-то жду до сих пор.
Комментарии (217)
etoropov
16.09.2021 01:55+36Конечно, выписывать вручную все эти типы будет несколько утомительно, но если сюда прикрутить макросы — можно процедурные для красивого синтаксиса
fn main() { <List as AsStrList<{ n_digits(<N as NumericValue>::VALUE) }>>::LIST .for_each(|s| println!("{}", s.as_str())); }
Наверное интервьюер решил, что в продакшене потом так же будет, и сбежал.
Flux
16.09.2021 02:18+131Хороший рассказ, качественно написан.
Meanwhile, in our universe:
…
Я открыл Rust playground и начал писать код:struct Z; struct S<T>(T);Интервьюер слегка нахмурился.
— Не могли бы вы пояснить, что вы делаете?
— Конечно. Я делаю свои собственные числа согласно аксиоматике Пеано...
— Извините, вы не подходите нам по софт-скиллам
Konstanty_PL
16.09.2021 11:50+1Шутки шутками, но на своё "джунство" я попал благодаря софт-скиллам, у меня были(есть) пробелы в знаниях, но по фидбэку от HR моему ПМ и ПО я понравился как человек, манера общения, реакции в стрессовых ситуациях. Пробелы сказали, что заполнят.
mapron
18.09.2021 01:15+4Не-не-не, так не пойдет, на Хабре полагается поливать помоями все треды про софт-скиллы, ну что вы творите-то?
vitalijs
16.09.2021 12:23+8Это если у самого интервьюера хорошо прокачаны софт скиллы. А ведь может и му***ом назвать
AnthonyMikh Автор
16.09.2021 12:27Мне кажется, если интервьюер заворачивает соискателя только из-за того, что не понимает терминологии, которой употребляет соискатель, и при этом даже не пытается спросить её значение, то это не очень хороший интервьюер.
Rhombus
16.09.2021 12:48+19Так может он понял терминологию и именно поэтому и завернул.
PsyHaSTe
16.09.2021 15:44+4Заворачивать сразу считаю тут дурным тоном. Я бы чисто из интереса посмотрел, что интервьювер напишет. А бонус раундом был бы ответ "а в прод в бы так же писали?" — ответы могут быть совершенно разными. Ну а если время отведенное на задачу давно вышло а она сделана только на половину — что ж, тут уже очевидный пробел в грамотной оценки трудоемкости задач, и вот это уже может быть основанием ля отказа. Но никак не "ой, он написал
data Num = Z | S Num"
Cerberuser
16.09.2021 16:22Я бы чисто из интереса посмотрел, что интервьювер напишет.
Оговорка по фрейду или взгляд глазами соискателя?..
PsyHaSTe
16.09.2021 16:28+1Оговорка, потому что "интервьюемый" очень трудновыговариваемое, а соискатель почему-то даже в голову не пришло, видимо отдает какой-то стариной.
sshikov
17.09.2021 22:25>Ну а если время отведенное на задачу давно вышло а она сделана только на половину
Трудоемкость скорее всего оценили неверно — но кто из двоих, как раз совсем не очевидно. Вы же наверняка читали похожую историю про задачу на копирование файла? Интервьюер там тоже наверняка считал ее простой, в тоже время, при всей дотошности (и даже занудстве) кандидата, нельзя сказать, чтобы он задавал бессмысленные вопросы, не имеющие отношения к делу. Ну и потом, если вы хотите оценить способности кандидата к планированию — можно же прямо задать ему вопрос, за какое время он планирует это реализовать?
И еще аспект — я лично обычно пытаюсь кандидата разговорить, думаю что многие делают тоже самое — потому что кроме умения решать задачи обычно интересно и умение человека рассказать, что он сделал и почему, а еще интересно узнать, как он думает. В такой ситуации считать промашку с оценкой серьезной вряд ли стоит. Уж лучше сразу кандидату временные рамки ограничить. Не сумеешь за 15 минут рассказать, как на типах в расте решить вот это — не начинай, выбери решение попроще.PsyHaSTe
17.09.2021 22:38Интервьюер там тоже наверняка считал ее простой, в тоже время, при всей дотошности (и даже занудстве) кандидата, нельзя сказать, чтобы он задавал бессмысленные вопросы, не имеющие отношения к делу. Ну и потом, если вы хотите оценить способности кандидата к планированию — можно же прямо задать ему вопрос, за какое время он планирует это реализовать?
Время интервью обычно заранее известно и стоит в каленаре. Задача не должна занять больше, чем все время собеседования.
И еще аспект — я лично обычно пытаюсь кандидата разговорить, думаю что многие делают тоже самое — потому что кроме умения решать задачи обычно интересно и умение человека рассказать, что он сделал и почему, а еще интересно узнать, как он думает.
Ну так тут вполне хватало и разговоров, и озвучивания что делается и почему.
Уж лучше сразу кандидату временные рамки ограничить. Не сумеешь за 15 минут рассказать, как на типах в расте решить вот это — не начинай, выбери решение попроще.
На собесах в фаанги принято кстати сначала сделать дуболомное решение, а потом уже его улучшать. Как раз чтобы в любой момент "время стоп" было хоть что-то рабочее.
sshikov
17.09.2021 22:58>Ну так тут вполне хватало и разговоров
Именно. Так я и говорю — интервьюеру-то чего тут обижаться? Тут все прекрасно о человеке понятно, а если ты скажем не понимаешь, что такое аксиоматика Пеано, или не знаешь чего о расте (но тебя ведь за язык не тянули разрешать писать на чем угодно, верно?) — ну так эта, тебе же язык для этого дан, спроси, правда же?
Будь я реально интервьюером в такой ситуации — я бы скорее остановил бы автора по другой причине. То есть, спросил бы достаточно рано, а какие другие решения он видит, и каковы их преимущества и недостатки. А потом уточнил бы критерии качества решения.
>Как раз чтобы в любой момент «время стоп» было хоть что-то рабочее.
В этом наверное есть смысл, но с учетом желания разговорить — лично для меня наличие рабочего уже не так важно.
Flux
17.09.2021 00:11+4А если интервьюер как раз таки понимает в метапрограммировании но ему в команде не нужны душнилы пытающиеся щегольнуть своим знанием всяческой эзотерики и воспринимающие это знание языка как индикатор превосходства над простыми смертными а не как инструмент для решения задач?
PsyHaSTe
16.09.2021 15:41+6Если вы пропустили, этот рассказ достаточно толсто отсылается к другому прекрасному посту.
v1000
16.09.2021 06:03+43Я что-то подобное всегда представляю, когда в Discord пишет %USERNAME% is playing Rust.
insecto
16.09.2021 06:20+35— На хаскеле было понятнее, — резюмировал интервьюер, и подняв взгляд куда-то в окно добавил, — а где доказательство что компилятор не ошибся?
AnthonyMikh Автор
16.09.2021 12:39+3— Корректную работу компилятора мы принимаем за аксиому, без этого мы бы просто не смогли писать программы.
nickolaym
16.09.2021 15:40+4Существование багов и разночтений в компиляторах - хорошо известный факт. (Разночтения возникают на дефектах спецификации языка).
И при программировании нужно учитывать, какие места в языке компилируются хорошо, а какие - нет.
Юнит-тесты, в том числе, служат выборочной проверкой корректности скомпилированной программы. А уж разбираться, кто ошибся - программист в программе, или компилятор, - дело второе.
Не скажу за Rust, а вот на C++ точно - в хитровывернутых шаблонах можно отгрести люлей от ошибок компилятора или стандарта. Если знать, где искать, или если натолкнуться на свежий баг.
PsyHaSTe
16.09.2021 15:46+2Существование багов и разночтений в компиляторах — хорошо известный факт. (Разночтения возникают на дефектах спецификации языка).
А ещё есть errata. И космические лучи. И ещё 100500 источников багов, которые учитывать в разработке совершенно непрактично. Мы берем это за аксиому вне зависимости от того, верно это или нет. Просто потому что там проще жить. Я больше доверяю условному гхц/гцц, чем с обственному коду.
Не скажу за Rust, а вот на C++ точно — в хитровывернутых шаблонах можно отгрести люлей от ошибок компилятора или стандарта. Если знать, где искать, или если натолкнуться на свежий баг.
Пока что не встречал ни 1 бага от компилятора раста, который бы не упал с паников проверки инварианта в его кишках. Да и с ними тоже встречался в сложных случаях и буквально пару раз за 5 лет.
0xd34df00d
16.09.2021 18:02+9Существование багов и разночтений в компиляторах — хорошо известный факт. (Разночтения возникают на дефектах спецификации языка).
Практика показывает, что эти баги чаще сводятся к реджекту корректной программы, чем к акцепту некорректной. Я не помню, когда я последний раз натыкался на последнее для языков вроде агды с не-бета-версиями компилятора (а вот «блин, придётся переписывать, чтобы компилятор принял код» было).
Юнит-тесты, в том числе, служат выборочной проверкой корректности скомпилированной программы.
А как вы протестируете, что фреймворк юнит-тестирования не ошибся и не вывел зелененькое OK там, где имелось в виду красненькое Failed?
fcoder
16.09.2021 15:50+5https://github.com/rust-lang/rust/issues?q=is%3Aissue+is%3Aopen+label%3AC-bug
2729 Open, 5645 Closed.
Ну такая себе аксиома, конечно.
Лучше ответить, что на этот случай у нас должен быть отдел QA с автоматическими интеграционными тестами для проверки требований заказчика/бизнеса, написанными с использованием инструментов никак не связанных с языком разработки. И весьма маловероятно что никак не связанные друг с другом тулы сломаются таким образом, что при выполнении разных алгоритмов для достижения одинакового результата будут показывать одинаковый неправильный ответ
PsyHaSTe
16.09.2021 16:57+2А у вас (где вы щас работаете) такой отдел есть? У нас вот просто нет, и я даже лично не знаю никого, у кого бы такой был.
buldo
16.09.2021 19:22+1Уже в паре компаний встречал такое.
В одной продукт на C#, а тесты на Java. В другой продукт на C#, тесты на JS.
PsyHaSTe
16.09.2021 20:15+1Я что-то не понял, как это защищает хоть от чего-то. У нас вот тоже код на C# написан, а тесты на TS и питоне.
Я про проверку того, что компилятор правильно скомпилировал наш код. Как это сделать, не реимплементируя компилятор мне даже не сильно понятно сходу. И уж точно я не видел это в реально продакшне, там куда более ценные и дешевые проверки зачастую не делают ведь "и так понятно что работает".
fcoder
16.09.2021 20:52+3Отличное уточнение в вопросе! Ведь не нужно проверять правильность всего компилятора, достаточно проверить что программа написана, скомпилирована и отконфигурирована без ошибок.
С т.з. бизнеса - эти все ошибки вообще равноценны - его интересует лишь возвращает ли разработанная система (сколь сложной бы она ни была) ожидаемый результат или нет.
Хороший способ убедиться - запустить систему в контролируемом окружении и сравнить возвращаемый результат и ожидаемый для определенного набора входных данных.
Это кажется и есть определение тестирования.
Ну а дальше уже пытаемся как можно сильнее отделить тестовое окружение от возможных сайд-эффектов, балансируя между требуемым уровнем уверенности в результате, ресурсами и здравым смыслом. Если ожидаем подвоха от реализации, генерируем ожидаемый ответ используя другой алгоритм (например вычисляем ожидаемое значение вручную и хардкодим). Если нет уверенности в компиляторе, то для генерации тестов очевидно нужно использовать независимый компилятор. Тем самым мы сильно уменьшаем вероятность того что разные люди ошибутся по разному, но их ошибки в тесте компенсируют друг друга таким образом, что тест даст ложно-позитивный результат.
PsyHaSTe
16.09.2021 22:14+3Ну а дальше уже пытаемся как можно сильнее отделить тестовое окружение от возможных сайд-эффектов, балансируя между требуемым уровнем уверенности в результате, ресурсами и здравым смыслом.
Как известно, тесты показывают только то, что тестовые сценарии проходят. В отличие от типов, которые корректность доказывают для открытого класса проблем. И подходу "компилятор в котором может быть ошибка, но который верифицирует программу" против "просто написали что угодно а дальше накрутили тестов" я всегда предпочту первый. Если только ублажать компилятор не слишком дорого.
Тем самым мы сильно уменьшаем вероятность того что разные люди ошибутся по разному, но их ошибки в тесте компенсируют друг друга таким образом, что тест даст ложно-позитивный результат.
Немного наивное предположение, как мне кажется. Особенно когда разработчики второго компилятора пишут не с закрытыми глазами код, а поглядывая в первый (привет, реактос).
mikhanoid
17.09.2021 07:47+1Есть же исследование по GitHub, в котором показано, что типы не снижают концентрацию багов. Так что... Ошибки в типах обычно довольно грубые, и сразу же проявляются на тестах, поэтому редко просачиваются в коммиты.
Более же тонкие алгоритмические ошибки системы типов не вылавливают. Даже с зависмыми типами можно написать так, что всё будет проходить проверки, а фактическое поведение будет багованное и не будет соответствовать реальности.
0xd34df00d
17.09.2021 09:01+3Есть же исследование по GitHub, в котором показано, что типы не снижают концентрацию багов. Так что… Ошибки в типах обычно довольно грубые, и сразу же проявляются на тестах, поэтому редко просачиваются в коммиты.
Учитывая, что далеко не все баги выявляются (успехов выявить редкий рейс-кондишон с многопоточностью), и далеко не все проекты одинакового уровня (на питоне пишут сильно меньше компиляторов, чем на хаскеле), у этого есть и ряд других интерпретаций. Например, что более-менее выживают проекты со сходной по порядку величины плотностью багов, и с правильным выбором инструмента.
Более того, дело ведь не только в том, сколько багов (не) дошло до продакшена, но и как быстро вы разрабатываете код, и насколько этот код поддерживаем. Это по количеству ишшуезов не измерить.
Более же тонкие алгоритмические ошибки системы типов не вылавливают. Даже с зависмыми типами можно написать так, что всё будет проходить проверки, а фактическое поведение будет багованное и не будет соответствовать реальности.
Против этого вообще нет никаких средств. С тестами-то это ещё более возможно.
svr_91
17.09.2021 09:20и далеко не все проекты одинакового уровня
Но также и то, что случайный человек не пойдет в хаскел и агду, в отличие от питона с js, а значит и требования к такому человеку выше.
но и как быстро вы разрабатываете код, и насколько этот код поддерживаем
Вроде была чуть похожая статья
0xd34df00d
17.09.2021 09:30+3Но также и то, что случайный человек не пойдет в хаскел и агду, в отличие от питона с js, а значит и требования к такому человеку выше.
Ошибки вылезают не из-за того, что надо отличить монаду от моноида, а это не все могут, а из-за того, что у среднего хьюмана ограниченный attention span. И вот что-то мне подсказывает, что здесь разница между хаскелистами и питонистами сильно меньше.
Более того, личный опыт: я на питоне выдаю настолько отвратительный и бажный код, и моих мозговых ресурсов настолько не хватает, что мой предел объёма программы, после которого скорость написания кода на питоне стремится к нулю — строк 50-100 максимум.
Вроде была чуть похожая статья https://habr.com/ru/post/456638/
Там сравнивалась не производительность написания кода на языке при условии его более-менее знания, а производительность новичка:
В команду Haskell входило два моих друга, которые написали, возможно, пару тысяч строк Haskell каждый, плюс прочитали много онлайн-контента о Haskell и других подобных функциональных языках, таких как OCaml и Lean.
Не нахожу это релевантным.
svr_91
17.09.2021 10:19что у среднего хьюмана ограниченный attention span
Проблема в том, что в "языки попроще" довольно часто идут совсем случайные люди. Ну вот те, которые "вайти в айти". А с haskell такое представить уже гораздо труднее. Тоесть вопрос как раз в том, что хьюман далеко не средний
0xd34df00d
17.09.2021 09:24+3Собственно, в пользу этой гипотезы говорит это исследование — там брали проекты на JS, выбирали коммиты, чинящие баги, добавляли аннотации типов в окрестности бажного кода, и смотрели, сколько багов поймается (поймалось 15%). Проблем с методологией меньше — это заведомо один язык (JS с навёрнутым поверх TS или Flow), одни проекты (разница в сложности до фикса и после фикса пренебрежимо мала), и явно прошедшие через тесты и какое-то использование автором до коммита баги.
Учитывая, что это заведомо консервативная оценка (выявляются только локальные проблемы в языке без прямого управления памятью, без многопоточности с разделяемой памятью, етц), с, можно предположить, очень малым подмножеством выразимых на TS ограничений, без контроля эффектов, и так далее, на практике для условной сишечки оно будет, гм, повыше.
mikhanoid
17.09.2021 11:42-1Сложно сказать, насколько это всё релевантно. Они проделали это с конкретными 400 bugfix-ами, говорят, что случайными, но даже негде посмотреть на список этих bugfix-ов. В статье есть битая ссылка. Поэтому, ну... Может быть, а может быть и нет.
0xd34df00d
17.09.2021 19:07+1В статье есть битая ссылка.
Вот это, кстати, минус, да.
Было бы очень круто, если бы был какой-то централизованный ресурс с errata и дополнениями (вроде тех же обновлённых ссылок) к статьям.
mikhanoid
17.09.2021 14:52-1Доверия к "On Programming Language Impact" у меня больше, потому что есть данные и методика, и исходники, можно всё проверить. В "To Type or Not to Type" есть только текст статьи и битая ссылка на данные, с которыми они работали.
Как-то это не очень...
Если у PVS более качественное исследование, был бы весьма признателен за ссылку.
mikhanoid
17.09.2021 10:42Заключение обсуждаемой статьи формулируется так "Количество выявляемых багов в популярных проектах на GitHub не зависит от языка программирования". Можно говорить, что на разных языках пишут разное по сложности, но в статье есть описание методологии сбора данных, можно её применить, и увидеть, что в выборку попали компиляторы не только на Haskell.
Гонки вообще плохо выявляются. Системы типов в этом не помогают. Rust обещает, что гонок не будет, но учитывая объёмы unsafe кода, который приходится писать для реализации даже простейших структур данных, сложно на это обещание полагаться. Да и баги в системе типов тоже никто не отменял. Какие-то виды гонок отлавливаются, конечно, типами, проверкой моделей, разделяющей логикой, но гораздо лучше, чтобы runtime семантика системы вообще не позволяла гонку создать.
Подходы Erlang, Oz или Clojure намного безопаснее в этом смысле.
0xd34df00d
17.09.2021 19:10+2Гонки вообще плохо выявляются. Системы типов в этом не помогают.
Эмм, STM (как один вариант) и линейные типы (как другой) этому очень помогают.
Да и баги в системе типов тоже никто не отменял.
Но площадь поверхности кода, которому надо слепо доверять, сильно меньше, что сильно лучше.
гораздо лучше, чтобы runtime семантика системы вообще не позволяла гонку создать. Подходы Erlang, Oz или Clojure намного безопаснее в этом смысле.
Я что-то думаю, что без оверхеда это не получится. На эрланге или кложуре не особо пишут какое-нибудь там HFT.
mikhanoid
17.09.2021 20:45-1STM помогает, но для эффективности нужны хитрые кеши. Линейные типы ограничивают выразительные возможности весьма существенно. Многие базовые алгоритмы синхронизации линейно не протипизировать (алгоритм Деккера, например). Сессионные типы помогли бы, но они сводятся к проверке моделей, что затратно для больших проектов. Нет тут панацеи, к сожалению.
В теме HFT не разбираюсь, но поиск по HFT Clojure выдаёт результаты. Ну, и на TechEmpower пишут, что Clojure может более 60000 обновлений в секунду обслуживать. Этого достаточно для HFT?
Кроме того, тут возникает вопрос: насколько эффективно это всё может быть вообще скомпилированно? Этими вопросами почти никто и не занимался, насколько я могу судить по научным публикациям. Мэйнстрим сосредоточен на теории типов и на эффективной компиляции для GPU или TPU, полиэдральные преобразования и тому подобное.
Поэтому не известно, насколько реализации агентов, процессов или распределённой унификации могут быть эффективны в пределе. Вот Haskell уделывает же Java и даже C в некоторых задачах. JS тоже поражает эффективностью. Кто бы мог подумать лет 20 назад? Но над оптимизациями в Haskell и JS усердно и долго работали. Кто знает, до чего можно раскочегарить Erlang, если взяться серьёзно?
0xd34df00d
17.09.2021 21:25+3STM помогает, но для эффективности нужны хитрые кеши.
А для эффективности какого-нибудь эрланга что нужно? :]
Линейные типы ограничивают выразительные возможности весьма существенно.
Так в этом и смысл. Да и наличие линейных типов не требует от вас их использовать там, где в линейные типы что-то не впихивается.
Сессионные типы помогли бы, но они сводятся к проверке моделей, что затратно для больших проектов.
Эмм, я не то чтобы спец в этой части, но, насколько я знаю, они вполне себе выразимы что завтипизированно, что, в некоторых (но практически достаточно полезных) случаях — через rank-2 polymorphism.
Rank-2 polymorphism вообще полезен, например, как в lvish. Интересно, что вот это вот
If an adversarial user defines invalid Eq instances (claiming objects are equal when they're not), or if they define a compare function that is not a pure, total function, and then they store those types within LVars, then nondeterminism may leak out of a parallel runPar computation.
могло бы быть формально проверено в более выразительном языке, чем хаскель.
В теме HFT не разбираюсь, но поиск по HFT Clojure выдаёт результаты. Ну, и на TechEmpower пишут, что Clojure может более 60000 обновлений в секунду обслуживать. Этого достаточно для HFT?
Для HFT важнее не количество, а латентность и её распределение. В одном месте, где я работал, мы стремились к существенно субмикросекундным временам (и выигрыш в десяток наносекунд в некоторых частях кода был более чем достойной победой).
mikhanoid
19.09.2021 15:31Для эффективности Erlang специальное оборудование не нужно. Достаточно обычных межпроцессоррых прерываний, которые и так на всех платформах есть. А вот чтобы STM быстро работала нужны транзакционные кэши, которые были (не знаю, как сейчас) в IBM Power каких-то серий.
Так в этом и смысл. Да и наличие линейных типов не требует от вас их использовать там, где в линейные типы что-то не впихивается.
Не впихивается очень многое, к сожалению, из необходимого на практике.
Сессионные типы через зависимые не выражаются. Есть урезанный вариант, который можно выразить (label-dependent), но в нём коммуникация ограничена только, так называемыми, рандеву.
<просто-мысли>
Не знаю. Можно, конечно, усложнять и усложнять системы типов, увеличивать сложность чекеров, потом усложнять структуры алгоритмов, чтобы они в эти системы типов вписывались. Наверное, это приемлемый путь. Проблема, однако, в том, что не у всех есть такое количество времени и интеллектуального ресурса, которые необходимы, чтобы это всё осваивать и применять, особенно, с учётом необходимости усложнения структуры алгоритмов.
Вот прохожу я курс по компьютерному зрению для автопилотов, где нужно думать о куче математических моделей. Мне совсем не хочется при выполнении заданий думать ещё и о временах жизни переменных или о функторах. Поэтому я не буду программировать это на Haskell или Rust. Опять же, типы не схватывают корректность необходимых для решения этих задач алгоритмов. Поэтому, я использую Julia или Python. Не круто, зато, работает.
</просто-мысли>
svr_91
17.09.2021 09:11А можно ссылку на исследование?
mikhanoid
17.09.2021 10:44https://web.cs.ucdavis.edu/~filkov/papers/lang_github.pdf - исходная статья с описанием метода сбора данных, но с ошибками в статистическом анализе.
https://arxiv.org/pdf/1901.10220.pdf - статья с более точным анализом тех же данных.
svr_91
17.09.2021 11:18+1Хоть авторы и говорят про "незначительную разницу", по моему разница между самым "плохим" (эх, C++) и самым "хорошим" (Typescript??) языком составляет почти 2 раза
svr_91
17.09.2021 15:31О числах, которые называются coeff.
В первом документе написана методика подсчета
We can read the coefficients as the expected change in the log of the response for a one unit change in the predictor with all other predictors held constant; i.e., for a coefficient βi, a one unit change in βi yields an expected change in the response of e βi
Thus, if, for some number of commits, a particular project developed in an average language had four defective commits, then the choice to use C++ would mean that we should expect one additional buggy commit since e 0.23 × 4 = 5.03
e^(0.22)/e^(-0.41) = 1.88
mikhanoid
17.09.2021 15:39Лучше результаты смотреть во второй статье. Там указаны ошибки первой работы, сделан пересчёт и получены другие значения, не такие впечатляющие.
svr_91
17.09.2021 15:42Да, результаты я брал из второй статьи, а методику подсчета из первой. Если честно, не увидел прям сильного отличия в результатах
mikhanoid
17.09.2021 16:32Кажется, там другие числа. "Худший" язык - C++ (0.16), а "лучший" Clojure (-0.15), разница 1.3. Отчётливо, как мне кажется, видно, что больший вклад в корректность кода даёт иммутабельность, а не типизированность.
svr_91
17.09.2021 16:39Видимо я не в ту таблицу смотрел. Наплодят тут одинаковых таблиц с одинаковыми названиями и без пояснений...
Sulerad
17.09.2021 01:21+5Ну такая себе аксиома, конечно.
Потому что лучше сказать, что "компилятор выдает только корректный результат компиляции".
По вашей ссылке большая часть проблем — какие-то краши компилятора, медленная работа, нестабильные (сырые) фичи и ещё тысяча вещей. Обычно компилятор просто не выдает программу в таком случае.
Гораздо лучше смотреть на приоритеты. Получается отношение open/closed такое: P-high: 88/945, P-critical: 1/75. Уже гораздо выглядит, причем их них I-unsound только 21/80, а единственная открытая critical про то, что некоторый код вдруг перестал компилироваться на бета-ветке.
Не говорю, что это идеально, но уже гораздо ближе к правде, чем страшные 2729/5645.
0xd34df00d
16.09.2021 06:22+27Спасибо, что напомнили про недописанную статью о физзбаззе на идрисе.
Refridgerator
16.09.2021 08:07+2А мне напомнило статью о производных на шаблонах — но там таки побольше смысла было.
Lirein
16.09.2021 07:49-25Потерял мысль на середине статьи… А не проще было вот так (можно через shr/shl и cout, но классический подход читабельнее и проще для понимания).
#include <stdint.h> #include <stdio.h> int main(int argc, char** argv) { int i = 1; while(i<=100) { printf("%d", i); if(i%3 == 0) printf("fizz"); if(i%5 == 0) printf("buzz"); printf("\n"); i++; } return 0; }Lirein
16.09.2021 08:02-18Уважаемые минусаторы, если у вас есть вариант проще и быстрее работающий — приведите его ниже.
n0isy
16.09.2021 08:13+39Задача FizzBuzz - это мемчик (хотя половина соискателей написать не могут), а статья - ирония. Как я понял, автор решает задачу на основе введения типизации компилятора, так, чтобы ответ был до запуска программы.
IvanG
16.09.2021 10:46+13Слишком тонкий тролинг, интервьювер похоже тоже не оценил, больше похоже что автор решил потешить чсв и блеснуть знаниями и применением конструкций, которые в ынтерпрайз разработке больше вреда приносят, а не пользы. KISS никто не отменял
VitalySh
16.09.2021 15:07+23Троллинг на столько тонкий, что даже вы похоже не заметили, что интервьюер здесь вымышленный и необходим лишь для интересного повествования.
avitek
16.09.2021 09:21+8Пожалуйста, и не один.
AnthonyMikh Автор
16.09.2021 12:42+3быстрее работающий
Определённо.
проще
А вот это уже под вопросом.
vladvul
16.09.2021 11:38+5у вас же ошибка, число печатается в любом случае, а нужно fuzzbuzz печатать ВМЕСТО числа.
Кроме того, работа с i в трех местах, что мешало использовать классический for цикл ?
Lirein
16.09.2021 11:47-1Ниже патч. Цикл со счетчиком for(i=1; i<=100; i++) имеет права на жизнь. Вообще сначала хотел написать на целочисленном делении в степени двойки и умножением, но не вспомнил как получить значение сдвигового регистра на C и забил на это дело.
Ну и до кучи, ещё вариант, уже не такой простой, но работает быстрее, без memcpy.#include <stdint.h> #include <string.h> #include <stdio.h> int myitoa(int number, char *buf) { char *cur = buf; int i = 1000000; while(number > 0) { int tmp = number / i; number %= i; i /= 10; if(tmp) *cur++ = tmp + '0'; } return cur-buf; } int main(int argc, char** argv) { int i = 1; char d3, d5; char buff[255]; char *start; while(i<=1000000) { d3 = i%3 == 0; d5 = i%5 == 0; start = buff; if(d3) { *start++ = 'F'; *start++ = 'i'; *start++ = 'z'; *start++ = 'z'; } if(d5) { *start++ = 'B'; *start++ = 'u'; *start++ = 'z'; *start++ = 'z'; } if(!(d3|d5)) { start += myitoa(i, start); } *start++=0; *start='\n'; fwrite(buff, start-buff+1, 1, stdout); i++; } return 0; }
P.S. Переменную buff можно ограничить до 10и байт.Lirein
16.09.2021 12:09+1Перепроверил, даже нет необходимости сразу писать деление через умножение, с опцией -O3 уже генерируется оптимальное целочисленное деление через imul/sar
matwel
16.09.2021 11:51-1print('\n'.join(f"{'' if i%3 else 'Fiz'}{'' if i%5 else 'Buz'}" or f'{i}' for i in range(100)))
AnthonyMikh Автор
16.09.2021 11:53+1А
joinтут лишнее, можно распаковать генератор:print(*(f"{'' if i%3 else 'Fiz'}{'' if i%5 else 'Buz'}" or f'{i}' for i in range(100)), sep='\n')matwel
16.09.2021 12:12+1А вот так на 3-а символа короче
print(*(f"{'' if i%3 else 'Fiz'}{'' if i%5 else 'Buz'}" or i for i in range(100)), sep='\n')
matwel
17.09.2021 00:43+1Ещё короче
print(*('Fiz'[i%3*9:] + 'Buz'[i%5*9:] or i for i in range(100)), sep='\n')Допускаю, что на некоторых языках будет ещё короче
slonopotamus
16.09.2021 08:10+17Во-первых, ваша программа работает неверно. Вы печатаете число вообще всегда, а по условию задачи "если ни одно из этих условий не выполняется, то выведете число как обычно".
Во-вторых, статья вообще не об этом.
Lirein
16.09.2021 08:31-15Что может быть проще?
#include <stdint.h> #include <stdio.h> int main(int argc, char** argv) { int i = 1; char d3, d5; while(i<=100) { d3 = i%3 == 0; d5 = i%5 == 0; if(d3) printf("fizz"); if(d5) printf("buzz"); if(!(d3|d5)) printf("%d", i); printf("\n"); i++; } return 0; }
Но про посыл статьи — понятно. Я так и не смог переварить даже функциональное программирование. Императивные, декларативные, транзакционные языки — всё просто. Но вот это уже сносит крышу.
Yuuri
16.09.2021 08:41+2Функциональное программирование — разновидность декларативного.
0xd34df00d
16.09.2021 09:04+3Я бы с этим поспорил для практически любого определения функционального программирования.
Yuuri
16.09.2021 13:32+1Поспорить можно всегда, но я не хочу заниматься буквоедством, а руководствуюсь более-менее общепринятой классификацией, описанной в т. ч. в Википедии.
PsyHaSTe
16.09.2021 15:50+2Контрол флоу может быть неочевидным для ленивого ЯП, но для строго ЯП вполне определен. А строгие ФП языки есть, тот же идрис.
0xd34df00d
16.09.2021 23:23+4Эта классификация в современном мире ИМХО не имеет смысла, потому что в более-менее любом современном языке «functions are treated as first-class citizens, meaning that they can be bound to names (including local identifiers), passed as arguments, and returned from other functions, just as any other data type can. This allows programs to be written in a declarative and composable style, where small functions are combined in a modular manner.», от, естественно, всяких хаскелей до условного C++. Получается, почти любой язык функциональный (и заодно декларативный).
Что куда важнее — типчики, чтобы статически рассуждать о поведении этих самых функций, ИМХО.
Yuuri
17.09.2021 12:59Получается, почти любой язык функциональный (и заодно декларативный).
Да, а в чём проблема? Так же как почти любой язык императивный. Одно другого не исключает, если имеется более-менее полноценная возможность писать в любом из вариантов.
PsyHaSTe
17.09.2021 13:56+3То что определение, в которое попадает всё множество объектов — тавтология, и бесполезность. Определения нам нужны, чтобы разбивать объекты на классы, а не просто чтобы придумать новый синоним слову "любой объект".
Yuuri
17.09.2021 17:04Так ведь не всё множество, а большинство современных. Остаётся как минимум пачка более старых языков, которые живее всех живых, но даже лямбдами не обзавелись (ну там C, Fortran, COBOL...)
Насколько функционален Rust с учётом проблем с funarg и композируемостью — вопрос тоже дискуссионный.PsyHaSTe
17.09.2021 18:01+1Мне сложно вводить определения, но чисто эмпирически кажется что Haskell/Idris/Scala функциональные, а Rust/C#/Java/JS — нет. И если пытаться их кластеризовать, то кажется что функциональность в первую очередь про систему типов, которая позволяет выражать и удобно работать с эффектами. Без этого нет ссылочной прозрачности, а без неё нет и ФП. Это куда полезнее чем некие first class citizen функции.
sshikov
17.09.2021 22:36+1Более того, хотя у вас скажем Java и JS в одной группе, чисто интуитивно кажется, что реально статическая типизация, имеющая место в Java, даже при всей слабости системы типов, все равно сильно полезнее ее отсутствия в JS. Т.е. опять же — языки разбиваются по этому же критерию дальше, и это разбиение вероятно практически полезно.
kitsoRik
16.09.2021 08:32-1Плюс там нет условия для fizzbuzz вывода т.е. когда одновременно модуль равен нуль при делении на 3 и на 5
Lirein
16.09.2021 08:37-1Почему нет? Перечитайте код ещё раз, нигде нет ветки else, впрочем при трех условиях в цикле предсказатель ветвления будет работать хуже, особенно в тупик его ставит условие !(d3|d5), т.к. если условие стоит как != то на интеле конвеер считает что операция по ветке je маловероятна.
AnonimYYYs
16.09.2021 12:42+2Но ведь ваш код неправильный. Для числа 3 будет выведено "3fizz".
Спасибо, вы не прошли так как не умеете делать тесты.
Lirein
16.09.2021 13:18-4На самом деле я не внимательно прочитал задание и первый вариант кода родился буквально за полминуты.
PsyHaSTe
16.09.2021 15:51+7Т.е. вам полминуты хватило чтобы начать строчить "КГ/АМ, статья мусор"? Стоит наверное побольше времени уделять критичности своего мышления, а то какое-то крайнее высокомерие и желание поиграть в уставшего от жизни циника, вокруг которого одни бездарности.
Lirein
16.09.2021 16:13Одно дело прочитать статью, другое — написать решение на СИ. На первое времени уходит куда больше чем набросать кусок кода для FuzzBuzz. К тому же после окончания прочтения статьи начальное ТЗ в полном объёме из головы уже выпало.
AnonimYYYs
17.09.2021 13:20Ага, то есть вы прочитали тз, потратили кучу времени на относительно левый материал, забыли конкретное тз за 10 минут и.... вместо того, чтобы потратить 30 секунд на повторное прочтение тз, вы сразу ломанулись в бой? А еще из вашего же коммента понятно, что вы вполне знакомы с задачей... но не помните такого важного уточнения?
Или вы это недосмотрели, такой микро косяк? Так это, опять же, проблема тестов и проверки. А вы кинули в прод даже без компиляции на тесте. Зато хвастаетесь скоростью. Вспоминаю анекдот.
- А я считаю со скоростью калькулятора!
- 263478 * 12786
- *мгновенно отвечает* 42!
- ???
- Я сказал быстро, а не правильноВ общем, в любом случае вы собеседование не прошли.
saboteur_kiev
16.09.2021 22:07+4На самом деле я не внимательно прочитал задание и первый вариант кода родился буквально за полминуты.
Если вы еще не поняли, основной смысл fizzbuzz - написать без ошибок с первого раза. Проверка идет не знаний языка программирования, а вашей внимательности к тех.условиям и вашему результату.
P.S. Понятно, что без фанатизма - без ошибок с первого раза программа не обязана отработать корректно, но ожидается, что она должна без ошибок отработать, когда вы ее уже "сдаете заказчику", а это вы сделали, когда опубликовали ваш код в первом комментарии.
csl
16.09.2021 07:54+6Чего только люди не делают, чтобы не писать на Idris, Agda.
ApeCoder
16.09.2021 08:36+1Так из контекста ясно, что он собеседовался на позицию в компьютер-сайенс-ресерче и ему не перезвонили именно из-за этого. Он просто выбрал не тот язык.
PsyHaSTe
16.09.2021 15:54+1На идрисе по-моему ничего практичного написать нельзя. По крайней мере даже примеры из конца книжки TyDD компилируются по 10 секунд, и это для пары сотен строк кода. Агда же лично меня вымораживает ютфом — можете называть меня старомодным, но если я вижу код который нельзя написать с помощью ascii клавиатуры то мне становится грустно. Да и честно говоря для людей, не изучавших 5 лет в универе математику какой-нибудь
isValid(isMemberOfSet(x, Y))проще математической нотации говорящей о том же самом. Даже если она в 10 раз короче.0xd34df00d
16.09.2021 18:19+2По крайней мере даже примеры из конца книжки TyDD компилируются по 10 секунд, и это для пары сотен строк кода.
Если честно, я не припомню, по крайней мере, своей фрустрации от этого
, может, после C++ было норм.В любом случае, в Idris 2 сильно улучшили скорость тайпчекинга, особенно на богатом имплиситами коде.Агда же лично меня вымораживает ютфом — можете называть меня старомодным, но если я вижу код который нельзя написать с помощью ascii клавиатуры то мне становится грустно.
Пишу на обычной клавиатуре, полёт нормальный, просто каждый уникодный символ требует пару-тройку нажатий :]
PsyHaSTe
16.09.2021 20:18+1Если честно, я не припомню, по крайней мере, своей фрустрации от этого, может, после C++ было норм. В любом случае, в Idris 2 сильно улучшили скорость тайпчекинга, особенно на богатом имплиситами коде.
Ну мне на полном серьезе говорили не использовать Nat чуть менее чем везде. Попытка сделать
toNat intMaxValueзакончилась для меня печально.Пишу на обычной клавиатуре, полёт нормальный, просто каждый уникодный символ требует пару-тройку нажатий :]
Вот что-что, а учить мнемоники каждого юникод символа я точно не хотел бы. Люди с мат. бекграундом конечно очень радуются, когда получают возможность писать на нативном языке предметной области, но мне кажется, что этот подход пусть остается в этих ваших мэплах/маткадах, а в коде должно быть ascii. ИМХО конечно, юммв.
0xd34df00d
16.09.2021 23:46+1Ну мне на полном серьезе говорили не использовать Nat чуть менее чем везде. Попытка сделать toNat intMaxValue закончилась для меня печально.
Ну в репле это правда плохая идея (там оптимизаций нет), а вне репла идрис это успешно оптимизирует в обычную длинную арифметику:
% cat Main.idr module Main prev' : Nat -> Nat prev' (S n) = n prev' Z = Z main : IO () main = printLn $ prev' $ toNat $ the Int 2147483647 % idris Main.idr -o Main % time ./Main 2147483646 ./Main 0,00s user 0,00s system 79% cpu 0,001 totalА на этапе тайпчекинга такие задачи, как правило, всё равно не возникают — в реальном коде заниматься настоящей арифметикой на уровне типов нужно нечасто (вне всяких индуктивных-рекурсивных предположений с плюс-минус единицей).
Вот что-что, а учить мнемоники каждого юникод символа я точно не хотел бы.
А частые и учить не надо, там мнемоники либо ожидаемые, либо систематизированные. Для греческих символов — соответствующий символ с большой G перед ним (например, для α это
\Ga), для условного ℕ —\bN. Для всяких математических символов — тоже ожидаемые названия (ну типа\forall,\mapsto,\inи так далее). Для всяких стрелочек — это направление стрелки, её вид и так далее. Например,\r~для волнистой стрелки вправо ↝, или\l=для ⇐.
А для более редких символов есть такое, оно у меня даже в закладках.Но смысл понятен, да, я понимаю, что это может отпугивать и печалить. Меня поначалу тоже отпугивало, потом привык.
Плюс, я согласен, что это несколько замедляет набор, хотя печатать
Γ ⊢ ε ⦂ τвсё равно быстрее, чемTermHasType ctx term type, а визуально распарситьΓ ⊢ ε₁ · ε₂ ⦂ [ zero ↦τ ε₂ ] τ₂проще, чемTermHasType ctx (App term1 term2) (substOnType zero term2 type1). Но я вроде уже в разговоре прям с тобой этот пример приводил, так что тут ничего нового :]Короче, зависит от предметной области, наверное.
KoCMoHaBT61
16.09.2021 08:57+1Интересно, если заявить, что уже есть эталонная реализация FizzBuzz Enterprise Edition на Java -- это прокатит на собеседовании:
https://github.com/EnterpriseQualityCoding/FizzBuzzEnterpriseEdition.git
Кстати, а почему не попытаться сделать стандарт IEEE для FizzBuzz?
Kelbon
16.09.2021 09:19+4Шаблоны в С++ куда понятнее как по мне... И в С++ это пишется одной обыкновенной функцией consteval, которая формирует строку, далее constinit строки и вывод. Даже магии не надо и всё будет вычислено на этапе компиляции.
Да и без consteval штук просто на типах, скажем index sequence, вычислил бы за меньшее количество строк и понятнее
AnthonyMikh Автор
16.09.2021 12:44+3А вы покажите, как это будет выглядеть. Насколько я помню, в constexpr-функциях можно использовать std::string, но нельзя это значение возвращать.
Kelbon
16.09.2021 14:36Выглядеть это будет примерно так:
https://godbolt.org/z/664venGW3Перевод из строки в число на компайл тайме достаточно неудобная задача, но что ш...
AnthonyMikh Автор
16.09.2021 14:54+1Благодарю. А теперь прикиньте, в скольких местах придётся править код, если нам понадобится поменять верхнюю границу. В моём варианте достаточно поменять определение
N.Kelbon
17.09.2021 11:05+1Вот, держи, 51 строка вообще без использования стандартной библиотеки, выдаёт результат не просто на компиляции, а в ошибке
https://godbolt.org/z/31cnb5sdfAnthonyMikh Автор
17.09.2021 16:39+1Посмотрел. Итого выходит, что перевод из числа в строку (точнее, в структуру
c) происходит при помощи специализации шаблонной структурыto_stringпо подставленному значению. На мой взгляд, это весьма неряшливый подход. Более того, в текущей форме он ещё и может сломаться при переносе между компиляторами: multi-character character literals определяют значения типаint, но это поведение implementation-defined, то есть, строго говоря, у нас нет гарантии, что, скажем,'fizz'не попадёт в диапазон от 1 до 100. То, что эти значения потом неявно конвертируются изintвunsigned— тоже не прибавляет уверенности.Если уж и сохранять общий подход к переводу в строку, то можно было бы: убрать аннотации значений у вариантов анонимного перечисления, в
Transformдля варианта, когда число остаётся как есть, возвращатьvalue + 3, а в реализацииto_stringпо умолчанию писатьusing type = decltype(ToString<Value - 3>);. Но этот вариант плох тем, что вносит магическую константу, которая ещё и повторяется дважды, и технически всё ещё исключает три числа из диапазона, который он в состоянии корректно напечатать — благо, это три числа из верхней границы диапазона, и компилятор, скорее всего, грохнется с OOM при попытке напечатать fizzbuzz-список с таким количеством чисел.А, и
ToStringвсё ещё не в состоянии обрабатывать числа больше трёх знаков.
technic93
17.09.2021 17:26так тут строки в тип перевели, а в версии на расте просто
struct { val: &str }
Kelbon
17.09.2021 17:47-1Меня очень умиляет как вы придираетесь к тому что реализация выдающая результат в ошибке КОМПИЛЯТОРА "зависит от реализации компилятора". Остальные придирки того же уровня...
AnthonyMikh Автор
17.09.2021 21:58Товарищ, таки где нормальный
ToString?technic93
18.09.2021 00:56Просто не надо переводить строки в массив чаров на уровне типов, достаточно просто сделать constepxr функцию
template<size_t n> auto constexpr gen() { std::array<char, count_digits(n)> arr; if (n == 0) { arr = {'0'}; return arr; } size_t x = n; auto it = arr.begin(); while (x > 0) { if (it == arr.end()) { throw std::logic_error{"ooops"}; } *it = (x % 10) + '0'; x /= 10; ++it; } std::reverse(arr.begin(), it); return arr; }и получать нужный массив как
constexpr auto data = gen<n>()А ещё тут места под лишние цифры не выделяется.
PsyHaSTe
16.09.2021 15:59+1FastToString выглядит так же, как у автора (за исключением того, что у него код корректен для любого N).
Что до самого вывода, то выглядит конечно ближе к обычному языку, чем акробатика на типах из статьи. Но смотря на выхлоп компилятора кажется что вышло не очень — миллион
mov BYTE PTR $S1$5[rsp+531], 0. К сожалению, полученного кода автор не выложил, надеемся что добавит.AnthonyMikh Добавь ссылку на гист в конце, интересно же поковырять :)
Readme
17.09.2021 10:32+3https://godbolt.org/z/cq9sWqMhP
- Более чистый вариант в ассемблере без
<iostream>. Хороший трюк — отправлять вывод в volatile-переменную, тогда и компилятор его и не выкинет, и не требуется I/O. - При включенной оптимизации результат вообще красиво слёг в статическую строку, а
mainвекторизовался, лол. MSVC, моё почтение.
- Более чистый вариант в ассемблере без
0xd34df00d
16.09.2021 18:21+1Кстати, это вроде как обещали починить в C++23. Там была какая-то мутная тема с тем, что делать с памятью, выделенной в константном контексте.
apro
16.09.2021 14:47+3В Rust тоже есть "const" фукнции, которые вычисляются во время компиляции. Но с их использованием статьи бы не получилось.
vvbob
16.09.2021 09:38+18Юмор понятен, конечно. Но на месте интервьюера я бы пообщался с человеком еще, с целью понять - это он так странно шутит, или реально он так и работает. Если не шутит, то "мы вам перезвоним". Имею неудовольствие работать вот прямо сейчас с проектом, написанным в стародавние времена такими вот любителями все сделать "круто". На практике такая "крутизна" выливается в то, что даже очень сильные разработчики в коде разбираются плохо, и он переполнен сложно воспроизводимыми багами, которые править крайне тяжело, практически из-за каждой ерунды приходится подолгу сидеть и разгадывать "крутые ребусы". Ошибки обычно не локализуются каком-то одном легко обозримом месте, а расползаются почти по всему проекту, изменение где-то в одном месте может дать неожиданный эффект в казалось бы малосвязанным с ним другом модуле.
Silvestor
16.09.2021 11:55+6Ну интервьювер конечно терпеливый излишне. Возможно он ожидал, что задача вот-вот кончится, но она и не спешила заканчиваться, а он все терпел и терпел и терпел...
Какой смысл сидеть и с умным видом делать гримасы полного понимания происходящего. Если уж тебе не понятно с самого начала и далее по тексту, то зачем продолжать? Вы видите что человека так сказать понесло в интерес, ну остановите его и попросите теперь постараться объяснить все то, что он сделал до определенного момента, на языке понятном для интерна-джуна. Если он опять будет объяснять в тех же понятиях и принятой им парадигме или скажем не сможет объяснить это в виду избыточной сложности или еще чего-то, то пожалуй работать с ним в команде не получится. А если этот человек весьма уверенно может это перевести на простой язык, то пожалуй это всего лишь тонкий троллинг и кандидат умеет работать, поговорите с ним еще о чем нибудь.
Katasonov
16.09.2021 10:11+2Представляю картину, приходит мужик устраиваться шахтером. Его просят продолбить в стене 100 дырок. Он вместо этого начинает собирать бомбу с часовым механизмом и удаленным управлением с мобильника, объясняя это тем что хотел бы избежать ненужных долблений дырок, а лучше захреначить всю стену сразу.
ignat99
16.09.2021 10:23-1Может ему атмосфера в офисе не понравилась и он решил пошутить и нарисовать чертёж бомбы.
nihlete
16.09.2021 10:30+7А то у нас как-то один кандидат — доброжелательный интервьюер на секунду поёжился — как-то развернул список на чём-то вроде Haskell и даже тестов не написал.
Крайне порадовала отсылка к 0xd34df00d
PsyHaSTe
16.09.2021 16:16+2Так там вся статья одна большая отсылка. Даже обороты местами переиспользованы)
inv2004
16.09.2021 10:38-2Умей раст нормально в const и статьи бы не было
AnthonyMikh Автор
16.09.2021 12:46+3Это всё можно и на const fn написать. Но изначально у меня была цель всё сделать на типах.
inv2004
16.09.2021 13:24С ходу не знаю можно ли: там и for и mut, хотя не проверял, но в плане того что можно в const - раст в текущем состоянии очень ущербен
apro
16.09.2021 15:00+1Ну например такой код скомпилируется текущим "stable":
const fn f() -> [bool; 100] { let mut ret = [false; 100]; let mut i = 0; while i < 100 { if i % 3 == 0 && i % 5 == 0 { ret[i] = true; } else { ret[i] = false; } i += 1; } ret }inv2004
16.09.2021 18:24Здорово конечно, но это только одно условие и массив, хотя, наверное, его размер можно дженериком
antonkrechetov
16.09.2021 10:59Мне кажется, я это уже где-то читал.
Не специалист по Расту, но нельзя ли сделать реализацию попроще с той же идеей? Например, вместо списка и его обращения реализовать шаблон, или как тут это называется, который увеличивает значение на «1», а для «100» останавливается. Наверное, вместо конвертации в строку тоже можно как-то попроще…dasFlug
17.09.2021 01:35Мне кажется, я это уже где-то читал.
Да, на Хабре, стилистика и посыл текста одинаковые https://habr.com/ru/post/463957/
no_future
16.09.2021 11:56Кто может подсказать, какая алгоритмическая сложность у этого кода?
AnthonyMikh Автор
16.09.2021 12:47+1O(1), ибо в рантайме код лишь выводит на печать уже вычисленное значение.
no_future
16.09.2021 13:01+3В рантайме или при компиляции, но время будет потрачено на вычисление результата, иначе можно любой алгоритм сделать O(1), вычислив результат заранее и сохранив в JSON.
mikhanoid
17.09.2021 07:59+1Нельзя. Алгоритмы вообще отображают натуральные числа в натуральные. А натуральных чисел много, поэтому, вы не сможете представить любой алгоритм конечной таблицей.
TheAthlete
16.09.2021 13:06+2Вот реально интересно, а для компилятора какая сложность, чтобы вычислить значение?
a1ex322
16.09.2021 14:39равна сложности постоения синтаксического дерева?
nickolaym
16.09.2021 15:46+4Дерево построить - дурное дело нехитрое. А вот насытить синтаксис семантикой - тут уже могут быть варианты.
Программа в десяток строк может потребовать экспоненту по памяти и времени для вывода типа.
Или, например, закодируйте функцию Аккермана на арифметике Пеано, и она будет разворачиваться за время, равное своему значению.
technic93
17.09.2021 18:08Ввод и вывод тоже занимают время и растут линейно с тем что у вас в коде названо N.
AnthonyMikh Автор
17.09.2021 22:00Ввода нет, это параметр этапа компиляции, а значит, об асимптотической сложности говорить смысла не имеет.
technic93
18.09.2021 00:30Тогда надо уточнить что "компайл-тайм" не связан с асимптотической сложностью этой задачи.
Shalopay1337
16.09.2021 11:57-11Статью можно сделать гораздо компактней . Что-то в духе - Пасаны !!! Смари как могу!! В ответ прозвучало - Ну ты и кодер.. Ну а так опять кто-то решил усложнить себе жизнь , когда поставлена задача с 6 класса времён Паскаль АБЦ.
zagayevskiy
16.09.2021 13:05Интересно, а сколько реально времени это заняло и смог бы ТС повторить это на реальном собеседовании?
AnthonyMikh Автор
16.09.2021 13:16+1Интересно, а сколько реально времени это заняло
С учётом подходов, которые себя не оправдали — часа… Три-четыре? Честно, я не засекал.
… и смог бы ТС повторить это на реальном собеседовании?
Да без проблем.
apro
16.09.2021 15:07Из "юмористических" решений мне больше всего нравиться https://www.youtube.com/watch?v=mZWsyUKwTbg , где предлагается решать задачу на haskell для крутости, но на самом деле код генерирует vim с помощью макросов.
technic93
16.09.2021 16:30+1Вот похожей дурью (в хорошем смысле) маются https://github.com/doctorn/trait-eval/
middle
16.09.2021 16:56поэтому я бы хотел избежать ненужных вычислений в рантайме.
А что, компилятор сам не умеет развернуть цикл, заинлайнить и соптимизировать в вывод большой строки?
AnthonyMikh Автор
16.09.2021 17:17+1Развернуть и заинлайнить — может (хотя с большими циклами это, как правило, не работает), соптимизировать в вывод одной строки — точно нет.
mickvav
16.09.2021 17:33type One = S<Z>; type Two = SumOf<One, One>; type Three = SumOf<One, Two>; type Five = SumOf<Two, Three>; type Ten = SumOf<Five, Five>; type TwentyFive = SumOf<Five, SumOf<Ten, Ten>>; type Fifty = SumOf<TwentyFive, TwentyFive>; type OneHundred = SumOf<Fifty, Fifty>; type N = OneHundred;Вот где-то тут я бы уже спросил, "а как поменяется ваша программа, если 100 не жестко задано а читается с стандартного ввода?"
AnthonyMikh Автор
16.09.2021 17:36+1Кардинально, зависимых типов в Rust нету.
mickvav
16.09.2021 17:42Не удивительно. FizzBuzz - очевидная warm-up задача, ее предполагается решить за 10-15 минут не особо приходя в сознание. До задачи с "мясом" автор даже не дошел, что дало интервьюеру возможность со спокойной душой оставить негативный фидбек.
inv2004
16.09.2021 19:26+1Юмор понятен, если это флек от типов, то тоже понятно, но если отталкиваться от сюжета, где автор хотел просто сделать compile-time решение то:
Пишем первое что пришло на ум:
func fb(n: int): string = for x in 1..n: if x mod 3 == 0: result.add "fizz" if x mod 5 == 0: result.add "buzz" if result.len > 0 and result[^1] == '\n': result.add $x result.add '\n' let res = fb(100) echo resхм, хорошо бы это посчитать при компиляции:
const res = fb(100) echo resГотово:
PsyHaSTe
16.09.2021 20:30Так и в расте можно так же:
#[derive(Debug, Clone, Copy)] enum FizzBuzz { Fizz, Buzz, FizzBuzz, Value(usize) } const fn fizz_buzz<const N: usize>() -> [FizzBuzz; N] { let mut ret = [FizzBuzz::Fizz; N]; let mut i = 1; while i <= N { ret[i-1] = match (i%3 == 0, i%5 == 0) { (true, true) => FizzBuzz::FizzBuzz, (true, false) => FizzBuzz::Fizz, (false, true) => FizzBuzz::Buzz, (false, false) => FizzBuzz::Value(i) }; i += 1; } return ret; } fn main() { for x in fizz_buzz::<100>() { println!("{:?}", x); } }Но ведь это будет не на типах, да?:)
cross_join
16.09.2021 20:10"Ирония - дочь бессилия" (с)
Подход понятен, но возникает вопрос о накладных расходах. В чистом Си в embedded, например, используют предвычисленные таблицы вместо операций целочисленного деления на некратное 2^N, достигая лучшего быстродействия за счет увеличения размера скомпилированного модуля.
AnthonyMikh Автор
16.09.2021 20:33В рантайме все накладные расходы — проитерироваться по уже вычисленным значениям. Неважно, насколько всё это (не)эффективно работает, это всё подсчитывается на этапе компиляции.
cross_join
16.09.2021 20:36Если неважно, что пойдет в эксплуатацию, то можно и так и даже круче с использованием одного m4.
RetroGuy
16.09.2021 20:35+1Интересно, из тех кому понравилась статья и кто посмеялся над нерадивостью собеседующего, сколько бы из вас действительно хотело бы быть коллегой автора статьи?
bogolt
16.09.2021 20:52+2Ну я вот люблю знающих коллег да еще и с таким супреским чувством юмора. Чертовски важное качество имхо.
RetroGuy
16.09.2021 21:04Как насчет колег, которые получают такое видимое удовольствие самоутверждаясь за счет других людей? Людей, которые не такие умные, по их мнению, как они сами? Вы не боитесь что в повседневной жизни вы сами не раз окажетесь на месте собеседующего из статьи? Только выйти из комнаты и сказать "мы вам перезвоним" уже так просто не выйдет.
bogolt
16.09.2021 21:22Давно таких не встречал и уже как-то позабыл что такое бывает. Но тут возможны варианты, можно выйти с человеком на какое-то плато общения где он не будет лично на вас самоутверждаться например. Можно просто минимизировать общение, оставив только совершенно необходимое по работе. Если человек создает проблемы на работе ( не важно создавая конфликтные ситуации или отрываясь на код-ревью) то это вполне доносится до менеджмента с соответствующими последствиями для последнего.
Если внезапно оказывается что человек делает мою жизнь хуже и компания не реагирует то значит с такой компанией мне не по пути.
Впрочем возможен вариант что я и есть такой человек поэтому ничего такого не замечаю. Надеюсь если это так то мне кто-то об этом сообщит.
0xd34df00d
16.09.2021 21:32+1Вы не боитесь что в повседневной жизни вы сами не раз окажетесь на месте собеседующего из статьи? Только выйти из комнаты и сказать "мы вам перезвоним" уже так просто не выйдет.
Регулярно оказываюсь. В этом можно найти повод расти.
PsyHaSTe
16.09.2021 22:17+5Не вижу тут никакого самоутверждения. Просто хорошая статья, причем написанная в духе другой, тоже популярной.
Вы не боитесь что в повседневной жизни вы сами не раз окажетесь на месте собеседующего из статьи?
Я бы с удовольствием провел такое интервью. например, предложил бы после всей реализации всей этой акробатики сделать ввод N с клавиатуры и посмотрел бы как соискатель начинает рвать волосы на голове) В подобную игру ведь можно играть вдвоем. И что самое характерное, по результатам такого собеседования обычно удовольствие получают обе стороны. Как и неплохое представление о способностях друг друга. Что куда лучше кмк, чем сидеть спрашивать по шпаргалке и ставить галочки знает/не знает.
sshikov
16.09.2021 22:22Не понимаю, где вы вот тут видите самоутверждение именно за счет других? Ну да, автор — он конечно самоутверждается, в каком-то смысле. Вы хотите сказать, что другие в итоге чувствуют себя глупыми, и страдают? А автор при чем тут?
>Людей, которые не такие умные, по их мнению, как они сами?
Ну, во-первых, в реальной жизни на самом деле одни не такие умные как другие. Это просто факт. А уж самоутверждаться иногда пытаются чуть ли не самые тупые.RetroGuy
16.09.2021 23:58+1Как где? Да вся статья, каждый следующий шаг - открытое наслаждение предполагаемой "глупостью" интервьювера. Автор прекрасно знал с самого начала что именно, от него требуется, так же как и то, что его решение поймут далеко не все (единицы?). Суть всей статьи вкратце - "я на 10 голов умнее того кто меня должен был проверять (по мной придуманной метрике), хаха, как смешно правда". Это и есть самоутверждение.
sshikov
17.09.2021 07:24+1Мне кажется все что про глупость — домыслы. Ну в смысле — вот откуда кто-то заранее может знать, человек напротив — он умнее в 10 раз, или наоборот? Как тут уже резонно заметили, в эту игру можно играть вдвоем, причем с другой стороны это еще и сильно проще. Ну т.е. тривиально — иньервьюеру не нужно понимать всю конструкцию, которую автор строит, чтобы ее развалить одним вопросом.
>Это и есть самоутверждение.
Не, так я этого и не отрицаю. Автор вполне себе демонстрирует «я умный». Но не за счет других. Хотя бы потому, что выбирать иньервьюера мы не можем.
>я слишком серьезно все воспринял
100%. Эта статья, как и предыдущая, в значительной степени шутка с отсылом к паре других, для тех кто помнит. Хотя возможно если вы ту не читали, то и не сразу обратили внимание.
mikhanoid
17.09.2021 06:20+2Мне кажется, переживать тут не стоит.
У людей не бывает универсального интеллекта. Если человек запарился и виртуозно овладел typelevel программированием, значит, он не запарился и не овладел чем-то другим (и времени не потратил на это, и физического ресурса мозга меньше оставил под другие задачи). Я нередко встречаю подобных персонажей. На typelevel они творят чудеса, как им кажется, но на деле же в интерпретаторе с необычной семантикой (абстрактный интерпретатор системы типов языка) сложным образом реализуют простецкие алгоритмы (необычность поражает публику, конечно). А когда нужно разработать более сложный алгоритм теряются. Встречал даже таких, кто сортировку не может запрограммировать, хотя только что рассуждал о
-категориях.Это не упрёк, просто все мы - узкие специалисты.
Поэтому, если такой человек заведётся в команде, то он либо окажется адекватным и поймёт, что зависит от других людей, которые лучше решают другие задачи, и начнёт работать на общее дело, либо окажется неадекватным, тогда просто вылетит, потому что конечному пользователю его typelevel не нужен, конечному пользователю (если, конечно, это не человек, занимающийся логикой) нужна эффективность в runtime, а не вот это вот всё.
sshmakov
16.09.2021 20:50+4
MacJIEHok
16.09.2021 22:03Перед вами лежит доска, молоток и гвоздь.
Вас просят забить молотком гвоздь в эту доску.
Вы как и игре Rust идете делать делать плавильную печь, на которой можно будет из руды выплавить молоток и гвоздь . . .
TrashboxBobylev
05.10.2021 13:44+1Нет, в этой статье автор определяет доску, молоток и гвоздь как математические категории, а затем создает теорему, по которой гвоздь магическим образом попадет в доску, даже не касаясь молотка.
nektopme
16.09.2021 22:39Открыли бы Excel и может быть и перезвонили:
Option Explicit Sub FizzBuzz_Test() Debug.Print FizzBuzz(1, 100) End Sub Function FizzBuzz(low_ As Long, high As Long) As String Dim sTxt As String Dim indx As Long For indx = low_ To high sTxt = sTxt & _ Buzz( _ Fizz( _ Fizz_Buzz(indx))) & _ vbCrLf Next FizzBuzz = sTxt End Function Function Fizz(vvar As Variant) As Variant Fizz = IIf(Mod_Var(vvar, 3), "Fizz", vvar) End Function Function Buzz(vvar As Variant) As Variant Buzz = IIf(Mod_Var(vvar, 5), "Buzz", vvar) End Function Function Fizz_Buzz(indx As Long) As Variant Fizz_Buzz = IIf(indx Mod 15, indx, "FizzBuzz") End Function Function Mod_Var(vvar As Variant, numb As Long) As Boolean If IsNumeric(vvar) Then _ Mod_Var = (vvar Mod numb) = 0 End Function
Soarerru
16.09.2021 22:42-1Я бы такого соискателя тоже не взял бы. Просишь элементарную задачу решить максимально оптимально, а получаешь НИОКР на три часа, который потом нельзя ни поддерживать, ни новые фичи прикрутить. И так во всех задачах.
Если не секрет: а сколько з/п на той должности предлагали?
Ndochp
17.09.2021 16:25+3Ну вообще кажется статьи про FizzBuzz максимально извращенным способом это идейный продолжатель анекдота про то, что можно измерить высоту академии при помощи барометра обменяв барометр на правильный ответ у сторожа здания.
Shreedeer
16.09.2021 22:58То есть суть статьи в том, что автор считает себя умнее, чем интервьюер, я правильно понял? А ещё не очень понятно, как вот эти все очень умные вещи помогут писать production code. Статья в духе, а смотрите, как я могу использовать те знания, которые я почерпнул в умных книжках, но их некому показать. Очень круто, но довольно бесполезно.
faiwer
17.09.2021 00:49+6Shreedeer, Soarerru и др… Вы это серьёзно? Нет, правда…
Это же стёбная статья с полностью вымышленной ситуацией юмористического характера. Так называемое "ненормальное программирование" (этот хаб, кстати, указан).
Я делаю свои собственные числа согласно аксиоматике Пеано
Уже на этой фразе должны были улетучиться последние сомнения :)
PsyHaSTe
17.09.2021 00:50+2Очень круто, но довольно бесполезно.
Это вы думаете, что бесполезно, а потом оказывается, что полезно. Не на таком игрушечном примере, конечно. Но у нас подобным образом в одном компоненте достигается оптимальность в tight цикле, где засчет этой акробатики выпиливаются многие вещи, которые не нужно в итоге считать в рантайме, что дает разницу в производительности в разы относительно скорости всей операции (а сам цикл ускоряется на порядки). В коде где люди с vtune лазят и префетчи руками выставляют чтобы в кэш попало что нужно заранее — и не такое бывает. И да, этим мы занимались не в каком-то компиляторе, а в обычном бизнесовом коде, чтобы быть конкурентноспособными с десятком конкурирующих компаний, включая яндекс. ИСЧХ получилось.
mikhanoid
17.09.2021 08:13А почему не использовали макросы? Макросы проще, гибче и прямолинейнее в подобных оптимизациях.
PsyHaSTe
17.09.2021 14:02+1Во-первых макросы не проще.
Во-вторых макросы хуже композируются: в случае с типами вы получите нормальную ошибку если где-то ошибетесь, а в километрах макросов он скажет что после подстановки что-то где-то не сошлось, и идти искать cargo expand что там накрутилось. Нет, это ан порядок сложнее. Да и не все в макросе емнип сделать можно из того, что нужно. Например, макросы не умеют останавливать рекурсию. Попробуйте написать факториал как рекурсивный макрос — не выйдет. На типах — пожалуйста.mikhanoid
17.09.2021 15:06Эвоно оно как... Вроде, хвастались, что макросы в Rust прям как в Lisp, и даже лучше... А они рекурсивный факториал не могут. Странно. Разве нельзя вызвать произвольный код пользователя?
PsyHaSTe
17.09.2021 15:23Не знаю, кто такое сказал. Макросы раста ограничены как минимум тем, что работают с синтаксисом, а не с семантикой. Если макрос видит тип SomethingType он никак не сможет узнать, например, какие поля есть у этого типа — это нужна семантическая модель, тогда как макросы раскрываются чисто синтаксически.
mikhanoid
17.09.2021 05:49+3Вам не перезвонили по очевидной причине: вы не решили поставленную перед собой задачу.
Вы же хотели минимизировать runtime, но на деле только увеличили его. Первый вариант с выводом ошибки через запуск rustc требует запуска компилятора, что гораздо накладнее, чем запуск простого fizzbuzz. Второй вариант требует сохранения в бинарнике большого списка строк (размер программы вылезет за размер сектора), его загрузки, релокации, большего замусоривания кэшей при исполнении, что снова приведёт к большему runtime.
Кроме этого, в такой простой задаче вы использовали unsafe, что же будет в более сложных ситуациях? Ай-я-яй!
(:
PsyHaSTe
17.09.2021 14:05+2А что такое "простой запуск fizzbuzz"? Про первый говорится что запускается целый компилятор, откуда можно сделать вывод, что во втором случае компилятор запускать не нужно? Просто я всегда думал, что раст компилируемый язык.
Это первое. А во-вторых время компиляции всегда называлось compile time и отличалось от run time. Включать одно в другое как-то странно.
Кроме того, никто не говорил вроде про большой рантайм, речь шла про быстрый/медленный. А размер дата секции из-за пары строк — да ну пофиг.
</zanudaOff>mikhanoid
17.09.2021 15:00Программа должна при каждом запуске выдавать fizzbuzz-последовательность. В первом случае каждый запуск потребует запуск компилятора. Вроде как, это очевидно. Нет? Во время исполнения такого решения, то есть, в его runtime, потребуется большой объём ресурсов, чем для однократно скомпилированной программы с обычной тривиальной реализацией, которую я и назвал "простым fizzbuzz".
PsyHaSTe
17.09.2021 15:25С чего бы каждый запуск потребует запуска компилятора? Запустили компилятор один раз, получили бинарь. Запускаем этот бинарь сколько душе угодно — где тут компилятор?
Я-то грешным делом подумал что включение compile time в рантайм это такой сарказм, но если это сказано на полном серьезе...
mikhanoid
17.09.2021 16:37Так в первом решении поста нет формирования исполняемого файла, результат выдаётся в виде ошибки компиляции.
PsyHaSTe
17.09.2021 17:44С чего бы это? Вы может не обратили внимание, но там написано:
Compiling playground v0.0.1 (/playground) Finished dev [unoptimized + debuginfo] target(s) in 3.55s Running `target/debug/playground`Что это за running
target/debug/playgroundтакой по-вашему?technic93
17.09.2021 18:00-1Речь про эту цитату
Затем я нажал
Ctrl+Enterи через пару секунд с довольным видом показал интервьюеру ошибку компиляции: ...как глухой с немым =)
vtb_k
17.09.2021 19:13Нету никакого первого решения. Есть просто решение тут
Набрав этот код, я с некоторым колебанием нажал Ctrl+Enter, и через несколько секунд отобразился результат запуска программы:как глухой с немым =)Попахивает маразмом честно
technic93
17.09.2021 20:26Я сказал что человек имеет ввиду (на мой взгляд), с надеждой помочь людям понять друг друга. С какой целью писался ваш комментарий для меня пока загадка.
mikhanoid
17.09.2021 21:10Ну, в тексте подано всё так, что в процессе сочинения типов герой забыл о задании и попытался выдать за решение ошибку компиляции с типом, напоминающим искомый fizzbuzz.
Но, ok. Пусть в тексте есть только одно решение, но оно тоже не эффективно в runtime. Вместо того, чтобы плюсовать пару байтовых счётчиков в паре регистров и периодически выпихивать в порт вывода пару байтов или строк, оно грузит здоровый массив, по которому к тому же проходит, читает значения из памяти (sic!), ветвится по результатам чтения, и копирует их в порт вывода. Жуткая жуть, растрата и оверхед по меркам конкретно этой задачи, если мы меряемся именно эффективностью во время исполнения.
AnthonyMikh Автор
17.09.2021 15:54+1Второй вариант требует сохранения в бинарнике большого списка строк (размер программы вылезет за размер сектора)
Не понимаю, чем это плохо.
его загрузки, релокации
Как и абсолютно любой другой бинарник.
большего замусоривания кэшей при исполнении
У меня большие сомнения в том, что это использование кеша (который, кстати, тут поможет, данные-то почти наверняка лежат в памяти последовательно) будет хоть сколько-то заметно на фоне использования кешей функциями ввода-вывода.
Кроме этого, в такой простой задаче вы использовали unsafe
Само по себе это не плохо. unsafe код не безопасен не сам по себе, а из-за того, что при его вызове нужно соблюсти инварианты, которые компилятор проверить не может. У обеих использованных небезопасных функций предусловия локальные.
std::str::from_utf8_uncheckedтребует, чтобы все байты в слайсе были в кодировке ASCII. Это требование соблюдено, поскольку мы начинаем с массива из нулевых байтов и на каждой итерации цикла записываем код, отвечающий ASCII-цифре.<[u8]::get_unchecked>требует, чтобы указанный диапазон лежал в пределах размера слайса. Так как мы используем диапазон с открытой нижней границей и конкретной верхней, это фактически означает, что требование сводится к тому, чтобыlenне превосходил длинны массива. Это требование так же соблюдено: возвращаемое значение — это финальное значение счётчика, который используется для индексации массива. На каждой итерации это значение сначала используется для индексации, а потом инкрементируется. Таким образом, после цикла счётчик имеет значение, которое, уменьшенное на единицу, можно использовать для индексации массива, что фактически и означает, что финальное значение счётчика не превосходит длины массива. Индексация массивов в Rust проверяет диапазон, так что если я вдруг что-то напутал с реализацией, тоto_str, вызванная в константном контексте, завершится ошибкой компиляции.Можно ли было бы написать
Str::as_strбез unsafe? Безусловно:impl Str { fn as_str(&self) -> &str { match &self.0 { &StrInner::Plain(s) => s, &StrInner::Decomposed(ref bytes, len) => str::str::from_utf8( bytes.get(..len).unwrap_or(&[]) ).unwrap_or(""), } } }Но в этом коде проходит проверка на включение
lenв диапазон и UTF-8-валидация. Первое не так существенно, а вот вторая проверка требует исполнения значительного количества нетривиального кода. Я сильно сомневаюсь в том, что компилятор в состоянии убрать этот код валидации даже для аргументов, известных на этапе компиляции. Использование unsafe-варианта позволит надёжно этот код исключить.
ZakharS
17.09.2021 11:47+2У нас в компании уже мем есть, когда коллега написал довольно большой проект на boost::spirit, и мы потом на спор показывали фрагменты другим командам и спрашивали, на каком языке написано. Человек долго мялся, а потом говорил "ну не С++ же..".
По итогу все переписали потом на нормальном С++, потому что поддерживать было нереально.
0xd34df00d
17.09.2021 19:14+3На нормальном C++ — это написали парсер руками?
Spirit x3 в плане поддержки вообще относительно норм (насколько «норм» вообще может быть поддержка нетривиального плюсового кода).
ZakharS
17.09.2021 22:02Ну да, руками, можно сказать. Просто в том проекте это получилось вполне органично.
Со спиритом там проблемы еще в гигантских шаблонах, которые иногда даже не компилируются из-за нехватки памяти. Но это, конечно, зависит от того, как спроектируешь.
0xd34df00d
17.09.2021 22:19+3Ну, руками писать комбинаторы в современном мире как-то печально, ИМХО. Плюс, опять же, x3 сильно чинит и время компиляции, и потребление памяти.
У него там другие проблемы есть — адаптировать структуры, чтобы сразу в них парсить, слишком многословно и не нужно в современных плюсах. Можно было бы взять подход а-ля magic get и наваять свой парсер, в конце концов. На месте этого вашего коллеги бы так и сделал.
nikbond
02.10.2021 16:56Если на собеседовании (не на джуна) вам дают решить FizzBuzz, то подобный подход — единственно правильный в данной ситуации.
obozrevatelua
04.10.2021 15:11-2На Rust:
fn main() {let mut x = 0;loop {x += 1;if x % 5 == 0 && x % 3 == 0 {println!("fizzbuzz");} else if x % 3 == 0 {println!("fizz");} else if x % 5 == 0 {println!("buzz");} else if x % 5 != 0 && x % 3 != 0 {println!("{}", x);} if x > 100 {break x;}};}
semenyakinVS
Тоже с год как подсел на метапрограммирование. Правда, на плюсах)
AnthonyMikh Автор
Брось каку
MatrixResolvere
Пффф, оно и понятно почему вам не перезвонили. Не вижу определения для натурального числа 1.
AnthonyMikh Автор
Так вот же:
TTimur
Прочитал сначала "правда, на колесах", извините.