Fizzbuzz

[elglin]

Сегодня на собесе человек с плюсАми в резюме запоролся на сабже. Не, я понимаю, что на заборе тоже написано, а там доски.
Но я вслед за товарищем Спольским считаю, что практикующий программист должен на своем активном языке физзбазз написать за пару минут. Окей, за пять минут, из которых три он будет пытаться понять, зачем его заставили писать эту фигню.
Но не пишут же! Путаются в if-ах. Не могут написать цикл (!). И вот при этом люди рассказывают про то, что в анамнезе было дописывание чего-то на дельфи, или какая веб-приложенька или еще что. И вряд ли брешут.

Вот я и думаю, прав ли я со своим физзбаззом. С одной стороны, любой человек, умеющий придумать и запрогать алгоритм, должен суметь в физзбазз. Но, может, сейчас это уже излишне? Может, стоит попуститься и не мучать людей задачей на один цикл и три if-а? Может, сейчас уже всякие фреймворки дошли до того, что можно писать годный работающий код и вообще не мучаться вопросом, как что-то сделать?
С другой вот стороны, как только ты начинаешь решать какую-то задачу сложнее, чем "пять строчек шелла", то у тебя сразу начинают вылезать конечные автоматы, очереди, графы, структуры данных и вся прочая унылая, но нужная теория из соответствующих курсов. Помню, было очень обидно изобрести jump table чуть раньше, чем про нее прочитал.
Вот и сижу я такой умный в когнитивном диссонансе.

Comments

[juan_gandhi]

Скальщики удивляются, зачем там ифы. (n%3,n%5) match { case ... }

Но дело не в этом. А дело в том, что действительно количество людей, способных ПРОСТО ПИСАТЬ КОД, очень незначительно. Большинство передирает, с трудом продираясь. Писать код с нуля - редкое свойство.

Why Can't Programmers.. Program?

[elglin]

О, а я эту статью читал, и именно после нее начал давать физзбазз (раньше его место занимало вычисление N-ого числа Фибоначчи, разжалованное за излишнюю сложность).
Тут есть еще другой аспект. В недавней дискуссии у, кажется, vitus_wagner был пассаж про то, что в экосистеме, скажем, питона почти для любой твоей задачи найдется готовое решение. Моя печаль в том, что сплошь и рядом в какой-нибудь мелочи "написать самому" и "разобраться в этой нагугленной фигне и правильно воткнуть" суть задачи сравнимой сложности.

[juan_gandhi]

Фибоначчи я люблю; зададут такие, думают, о, мы крутые, а он лох - а я им или через матрицу, или формулу. Через матрицу же логарифмическая сложность.

[elglin]

Да, я видел этот элегантный алгоритм. Если правильно помню, сводится к возведению матрицы в n-ую степень, а это, как и любое возведение в степень, имеет логарифмическую сложность.
Константа там большая получается: умножение матриц 2х2 - это же 8 умножений и 4 сложения. Итеративный алгоритм тратит две инструкции на шаг (ADD EBX, EAX; XCHG EAX, EBX), если добавить сначала проверку четности N, то даже две инструкции на два шага (ADD EBX, EAX; ADD EAX, EBX) - да еше и умещается целиком в регистры. Поэтому, да, если мы говорим о больших N, то матричный алгоритм, конечно, решает. А вот для N < 100, как мне кажется, наивный итеративный алгоритм все еще быстрее.

[drraug]

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

[elglin]

И мы сразу вместо интов получаем флоты и всю радость с ошибками округления, в диагональной-то форме. Там еще и собственные значения одно по модулю больше 1, одно меньше, что сулит несравненную радость с машинным эпсилон.
Не-не-не, Дэвид Блейн, скукожь обратно.

[drraug]

Ну ты прав конечно, формально, но округление - это не такая уж и проблема. ты же знаешь, что в итоге ответ целочисленный. И тут ещё вопрос, а что ты вообще хочешь в качестве ответа, если он не лезет в стандартный long long int? ты же наверное хочешь эмулировать arbitrary precision arithmetic для интов? Ну так возьми тот же эмулятор (gmp наверное) и эмулируй им arbitrary precision arithmetic для floats. Все нормуль будет ))

[elglin]

Какая тут arbitrary precision, если у тебя иррациональные числа? Тут разве что тащить что-то, умеющее формально работать с квадратичным иррациональностями, но это быстро работать не будет.
Идея в том, что наивный линейный алгоритм жутко быстр на малых N, а с тех N, где выигрывает логарифмический, у тебя начинают сыпаться такие проблемы с флотами, что тебе проще проиграть константу числа операций, но остаться в пределах абсолютно точного интовой арифметики, которая к тому же, в отличие от флотовой, намного быстрее в пересчете на такты.

[drraug]

как какая? точно такая же как в IEEE, только мантисса длиннее. Но поскольку процессор нативно поддерживает только 64 или 128bit, то эмулируем всю нужную арифметику на уровне библиотеки. Библиотека уже давно есть, ну gmp та же.

Ну come on. Мне уже кажется, что проще написать, чем объяснить как. Но я к сожалению совсем забыл, как писать на Си, а ты наверное не захочешь читать код на фортране?

Ты не можешь остаться в станданртной интовой арифметике, потому что при N>40 кажется у тебя уже будет int overflow.

[elglin]

Фортран я, наверное, даже прочитаю.
Я бы все-таки остался в рамках интовой (пусть bigint) арифметики, главным образом потому, что в ней у тебя абсолютная точность. Вся игра с диагонализацией хороша тогда, когда ты знаешь число шагов алгоритма, то есть можешь прикинуть нужную тебе точность.
Грубо говоря, проблема в том, что для любой наперед заданной точности можно указать такое N, что алгоритм, начиная с F(N), начнет считать с ошибкой просто в силу недостаточной точности приближения. Ну или если переформулировать: любое целое число ты можешь представить в виде bigint с абсолютной точностью для любых целочисленных вычислений, использовав конечное число байт. А вот нужное нам для диагонализации золотое сечение, (sqrt(5)+1)/2, мы можем представить (почти принцип неопределенности Гейзенберга, получается) только с конечной точностью за конечное число байт. Более того, как только мы начали что-то считать, отрезав хвост мантиссы, мы уже безвозвратно потеряли в точности, то есть мы не можем (как по сути происходит в целочисленной или рациональной арифметике) ее произвольно наращивать.

Да и с длинной математикой тоже не все просто, там умножение все-таки сложнее, чем O(N), где N - длина в битах, хотя, конечно, не O(N^2), а сложение-то строго O(N). Так что я бы сказал, что наивный алгоритм достаточно долго выигрывает за счет низкой константы на шаг, а потом еще сколько-то выигрывает за счет того, что длинное сложение все же дешевле длинного умножения. На длинной дистанции выиграет, конечно, матричный алгоритм - другой вопрос (и вот тут мы с тобой смотрим с разных сторон, ибо ты ученый, а я ремесленник), что в приложениях финиш часто будет раньше этой дистанции.

[scif_yar]

>>раньше его место занимало вычисление N-ого числа Фибоначчи, разжалованное за излишнюю сложность).
-
лолшто ?

[elglin]

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

[scif_yar]

бле.
а у меня другой прикол. Приходят ко мне соседи - говорят некая прога тормозит, чо там у вас в инфре?
Я повтыкал в варю, ну говорю вот тут ваш приклад весь проц сожрал, но накинем, а вот на вашей бд - в инфре все збс, что там выше в БД - не знаю. Пришел шеф, он так то дба - у вас говорит родные таблица залочена уже часов (ЧАСОВ!) несколько и роллебек висит, вы какого чуда хотите вообще? Как оно у вас вообще работает то?
те почесали репы и пошли разбираться.

И это не 1с, там все мрачно.

[drraug]

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

[elglin]

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

[drraug]

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

Автомеханики не получают 100500, понимаешь в чем дело. Они сидят в той же финансовой нише, что и учителя, строители, водители поезда метро - обычные люди. А программеры получают как юристы или политики - патриции нового времени. И как бы это ОК для тех, что может прогать, потому что программки оч нужны, это я понимаю. Но как существуют эти 199 из 200 программеров которые не умеют прогать совсем, как индустрия ползёт с этим балластом?

[elglin]

Я тут странную вещь скажу. Рациональное объяснение только в том, что ИТ реально сберегает деньги. Настолько сберегает, что даже неэффективные в него вложения окупаются со свистом. Причем, возможно, строго по пропаганде позднего совка, не за счет вымывания дешевых мест, а за счет вымывания квалицифированных рабочих.
Простейший пример - такси. Цены на такси после появления Убера/Яндекса рухнули. При этом Убер/Яндекс и их программеры снимают львиную долю прибылей. Секрет в том, что требования к водителю немедленно рухнули ниже плинтуса, предложение таковых взлетело в эфир, расценки рухнули ажно ниже минималок. По сути, несколько десятков (пара сотен) программеров, клепающих это дело, получают долю с десятков, если не сотен тысяч разниц зарплат профи-таксеров со стажем и Ашота с рыдваном и смартфоном.
И так по всей отрасли.

[scif_yar]

я даже вводной не помню.

[brmail]

не смейтесь - я только что узнал про такую игру - fizzbuzz, и погуглив нашел ее правила. Думаю, что вопрос на интервью, написать код для физбазз, случись такое вчера, вызывал бы у меня сильное недоумение, что это такое и с чем его едят.
Что касается интервью, и вообще о чем сегодня спрашивать на нем - проси написать простейшую функцию возвращающую факториал числа. Через рекурсивный вызов. Если человек спросит что такое факториал, рекурсия, или не сможет написать такое - можно гнать сразу.
Мне персонально никакие графы и десять способов быстрой сортировки массивов за 25+ лет программизма не пригодились не разу. Но я не исключаю, что полно работы, такой, где эти графы действительно нужны дозарезу.

[elglin]

Я же культурный человек. Кандидату предлагается файлик на языке его предпочтения, где многострочным комментом (в питоне - докстрингом) в начале пустой функции описано, что надо сделать, а не просто "напишите физзбазз".
За идею с факториалом спасибо, надо будет обкатать.

Про сортировку и поиск по факту пригождается знание плюсов и минусов - и то только в том объеме, чтобы соображать, нужен в базе индекс или нет. А, один раз попросили написать mergesort на собесе, было дело.
Про графы тоже соглашусь, нечастые гости, просто у меня сейчас есть две вялотекущие задачи, в одной из которой есть дерево зависимостей, а в другой граф связности, по которому надо запускать алгоритм покойного Дийкстры. Потому и помянул.

[scif_yar]

>>Мне персонально никакие графы и десять способов быстрой сортировки массивов за 25+ лет программизма не пригодились не разу. Но я не исключаю, что полно работы, такой, где эти графы действительно нужны дозарезу.
-
stp и прочий ospf. Графы и прочий обход.