Привет, друзья. Тут речь пойдет о маленьких конкурсах JavaScript-программистов, которые проводит стартап Хола. Мне до сих пор кажется, что посетители Хабрахабра — самая целевая аудитория для таких конкурсов, особенно после разделения сайтов на МикроМозг и тот, другой сайт.Принять участие в описанной здесь коллективной бессознательной потехе могут, конечно, все желающие; памятные подарки включают в себя суммарно чуть больше трех тысяч долларов американских денег (это я специально забегаю вперед для привлечения внимания, такой литературный прием).
Еще в этом посте я постараюсь подытожить опыт, сын ошибок трудных: что уже делали, что получилось, и как с этим теперь жить дальше.
Про конкурс
Сразу самое интересное: условия конкурса.
В состав Node.js входит имплементация высокопроизводительного связного списка, которая ко всему прочему бережно относится к оперативной памяти. Вот она, эта замечательная штука: github.com/joyent/node/blob/master/lib/_linklist.js
Этот код довольно специфичный: он написан для хранения idle timeouts (хоть это никак и не отражается на его работе), и не позволяет одному объекту содержать несколько списков. (Здесь, очевидно, имеется в виду непосредственное участие одного и того же узла в двух и более списках. — прим. перев.)
Требуется обобщить этот код, лишив его описанных ограничений, но не ухудшив при этом производительность его работы. К решению нужно приложить бенчмарк, подтверждающий, что скорость работы не снизилась.
Побеждает самая быстрая, эффективная и обобщенная реализация.
Почитать оригинал на английском можно вот тут.
Решения принимаются до 30 июня. Призы: 1500, 1000 и 500 долларов США за три самых лучших решения, и 350 долларов за самую оригинальную попытку.
Анализ задания
Дальше чистая спекуляция, т.е. мое собственное мнение. Оно может оказаться верным, а может не оказаться — настоящая квантовая механика; как и кота Шрёдингера, мое мнение поэтому нельзя ни погладить, ни накормить.
Во-первых, внимательный читатель уже догадался, что организаторы хотят увидеть прежде всего бенчмарк; связный список без бенчмарка — это очень просто и не очень интересно.
Во-вторых, предвосхищая одинаковые вопросы: по опыту прошлых лет, «официального» бенчмарка скорее всего не будет. Тестировать нужно применение, близкое к реальному; лучше всего взять какой-то алгоритм, который в основе своей имеет связный список, и погонять его на каких-то правдоподобных данных.
В-третьих, задание, конечно, нестрогое. Подразумевается условно-творческая работа в свободной форме, это одновременно плохо и хорошо. Обязательно напишите в комментариях, почему вы считаете, что это плохо — одинаковые сообщения образовывают в треде ритмический рисунок, создают неуловимую гармонию, как ковер на стене в спальне. Такой, знаете, с красным орнаментом. Наверное, у всех такой был.
О подвохе
А подвох вот в чем: нестрогость задания напрямую связана с настоящей целью проведения маленьких конкурсов. По секрету сообщаю: цель — найти программистов, чтобы пригласить их на работу. Работать в Холе можно удаленно, а можно локально, если вы случайно (или вовсе даже преднамеренно) очутились в Израиле.
Задачи, которые ставят перед соискателями ребята из Холы, отражают реалии работы в компании. Реалии таковы: подразумевается, что каждый программист может самостоятельно анализировать требования, проектировать и разрабатывать нужные вещи. Поэтому если постановка этой маленькой задачи вас смущает, вы, возможно, с высокой скоростью убежали бы из Холы на второй день, смешно размахивая руками.
Некоторым моим знакомым нравится так работать, а другим не нравится. Если провести аналогию с другим превосходным холиваром — одни думают, что Vim лучше, чем Emacs, а другим кажется, что Emacs хуже, чем Vim. Два еврея — три мнения.
Хроника событий
Конкурс, про который вы почитали выше — третий по счету.
Первая задача была втихаря опубликована на сайте Холы давным-давно, не имела срока годности, и подразумевала подарки вообще всем, чтобы никто не ушел обиженным. Задание заключалось в том, чтобы написать функции для работы со строками на языке Си.
Сначала эта задача была предложена лишь гражданам Израиля. Затем кто-то обратил внимание, что в офисе есть интернет, а это не только открывает невероятные возможности по посмотрению в ютубе на смешных котиков, но и позволяет работать удаленно, сидючи непосредственно в сибирских чащобах и залихватски попивая водку из провербиальных самоваров.
Основной критикой в адрес этого предприятия была, конечно, формулировка задания: требовалось представить, цитирую, «идеальное решение». Поскольку идеал — штуковина глубоко личная и непостижимая, многие ребята обижались на такую задачу, на жюри, на небо, на Аллаха.
Проблематика задания с точки зрения организаторов заключалась в другом: на первый взгляд, написать функции для работы со строками на языке Си очень легко. Плохих, негодных решений приходило очень много, а хороших, наоборот, исчезающе мало.
Второй конкурс был про функцию
strftime(). Предлагалось взять имеющуюся в Гитхабе реализацию этой функции и значительно ускорить ее. Тут в плане сложности получилось строго наоборот: наименее отважные ребята не стали даже пытаться, т.к. фронт работ выглядел чересчур монументально.
Задание также было довольно прохладно встречено сообществом, в частности это можно пронаблюдать на Хабре. Как обычно в таких случаях, участники конкурса (прямые и косвенные) разделились на два практически непересекающихся лагеря: те, кто прислал решение, и те, кто прислал критику.Тут я сейчас раскрою восхитительную тайну: за критику призов не было вообще никаких, а за удачное решение, наоборот, были. Ах да, еще интересный момент: многим откликнувшимся на конкурсные задания ребятам была предложена работа, вне зависимости от (не)призового места.
Выводы
- Можно написать ~10 строк кода и выиграть ~1000 долларов. Полтора барреля нефти за строку кода.
- Когда на халяву дают деньги, надо брать.
Надеюсь, рассказ получился не очень скучным. На всякий случай, ссылка на конкурс (я сам всегда читаю с конца, так эффективнее же).
Удачи!
Комментарии (20)
mark_ablov
19.05.2015 05:01+3> Здесь, очевидно, имеется в виду непосредственное участие одного и того же узла в двух и более списках
Очевидно?
Оригинал «and does not allow list parent to hold two or more different lists in the parent list object».
Что такое «list parent» я вообще не имею понятия, «list head» или «list previous node» еще можно понять. Возможно сам объект списка?
Может быть действительно дело в том, что узлы могут принадлежать только одному списку, но мне это не совсем ясно даже из оригинала. Типа list parent — объект, к которому «примешана» возможность работы в списках.
Видимо самостоятельно анализировать требования у меня не выходит :)
printf Автор
19.05.2015 07:43Типа list parent — объект, к которому «примешана» возможность работы в списках.
По-моему так, да. Вообще фигня какая-то написана, мне не нравится вся эта идея целиком — примеси делать. Непременно же потом захочется сериализовать эту штуку и отдать юзеру / сложить в базу данных, придется эти поля фильтровать.
Jabher
19.05.2015 07:54+3Задача откровенно дурацкая, к слову. Одновременно простая и невозможная.
Если нужно именно сохранить сложность O(1) и O(n) для добавления/удаления и поиска соответственно, и допустимы незначительные замедления (доли или единицы процентов от общего времени выполнения) из-за добавления дополнительного функционала — решение элементарное.
Банально заменяется обращение к _idleNext и _idlePrev на что-то вроде для, например, функции peek
function peek(list) { if (list.__prevPointers[listKey] == list) return null; return list.__prevPointers[listKey]; }
То есть решение довольно очевидное и «в лоб». Функция сложности не меняется, но возрастают затраты на дополнительные обращения.
А вот дальше начинается абсолютная дурость. Из-за неизвестной среды исполнения становится непонятно, что можно и что нельзя использовать, потому что подобный код замечательно оптимизируется через WeakMap, который может очень хорошо дать прироста в нативном исполнении.
А больше его и не оптимизировать толком никак, потому что проще и эффективнее, чем это сделано сейчас, сделать не выйдет. В основном потому что код практически эквивалентен определению двусвязного списка самого по себе и не обладает дополнительным обвесом из кода, оптимизировать его возможно будет только под какие-то специфические платформы. Либо сделать извращенную реализацию двусвязного списка поверх — опять же — какого-нибудь WeakSet, но тут вновь вопрос о том, какие требования по платформам.mark_ablov
19.05.2015 08:24+1Те же мысли.
Может ожидается какое-то красивое ООП? Ну вроде как ручками listKey пробрасывать неудобно, можно «класс»-обертку соорудить, которая бы еще и автоматом бы примешивала эти внутренние свойства (prev / next). Можно, к примеру, еще и допилить чтобы имена этих internal-полей были не жёстко захаркожены, а подстраивались, в случае если у исходного объекта они уже есть (банально перебираем __prev_X, скажем, а чтобы опознать, что это наше internal-поле, можно и наше magic-значение записать).
Если «Во-первых, внимательный читатель уже догадался, что организаторы хотят увидеть прежде всего бенчмарк» действительно так, то это немножко меняет дело, но не сильно.
Тем более, по бенчмарку тоже есть вопросы.
В общем, набросаю на выходных как для меня всё это выглядит, посмотрим.Jabher
19.05.2015 19:12Ну формальное требование — «не медленнее», значит, бенчмарк должен банально замерять то, что каждая из операций выполняется не медленнее: creating, updating, traversal. Это можно достигнуть только через вот да, эти «волшебные» ключи, потому что даже выборка по двум ключам не так эффективна.
Теоретически — да, это, пожалуй, единственный вариант, но апи будет такииим гемморойным… К тому же — придется кэшировать строки, потому что операция создания строки '__prev_' + x тоже ресурс жрет. Соответственно — нужна автоматическая генерация строк с их кэшированием.
В итоге код будет вида list[prevKey[x]], что в итоге тоже равно является выборкой по ключам. В итоге — тоже не катит.
Примесью в виде красивого ООП — я уже сказал, это чистый WeakMap, есть замечательный полифилл от Брэндона Бенви, который сумел создать скрытые свойства элементов и на этом сделал поддержку множественных WeakMap на одном объекте, у которых не течет память. Код практически эквивалентен, я как раз начал ковыряться с того, что взял его полифилл и выкинул все лишнее. Получилось именно так, как я сказал выше — двойная выборка по ключам, и минимальная просадка по перформансу. И вот что с этим дальше делать — вообще без понятия.
artem_drozdoff
20.05.2015 11:44Учавствовал в предидущем конкурсе по С от Хола. Всем решившим была обещана награда. Отправил решение — ни ответа ни привета. Написал им первый спустя 2 недели. Сказали что какая-то девочка проверяет. Уже примерно год как их девочка проверяет. Всем участникам удачи!
Louter
20.05.2015 13:57Да, с гарантиями жопа: как получить деньги и как понять, что твоё решение не лучшее? (приведёны ли будут варианты решений)
Может поэтому на втором конкурсе было так мало толкового народу?printf Автор
20.05.2015 14:02+1Поэтому первый вялотекущий контест свернули, а от второго всё опубликовано в гитхабе же. См. мой предыдущий пост на эту тему.
printf Автор
20.05.2015 14:17Оно было плохо организовано, да. «Плохие» решения периодически оставались без ответа.
artem_drozdoff
20.05.2015 17:52Могли бы оповестить о том что проверили, но решение не устраивает.
printf Автор
20.05.2015 20:03Да. На эту тему я с ними ругался, т.к. мне периодически рассказывали про такие случаи.
Хоть это и не извиняет организаторов, объясняется всё следующим образом: этой инициативой никто не занимался на самом деле. Хола — совсем маленький стартап, там каждый сотрудник «работает на нескольких работах», сиречь делает много разноплановых вещей. (Salespeople я за сотрудников, конечно, не считаю — они как аквариумные рыбки.)
Поэтому некоторые аспекты долгое время страдали. Например, оформление сайта и продуктов компании создавалось программистами по остаточному принципу. (Сейчас это уже не так.)
А больше всего от отсутствия фокуса страдают коммуникации с людьми, будь то пользователи, соискатели, кто угодно за пределами фирмы. Это, конечно, плохо.
staker
20.05.2015 15:07+2Так как:
* На первый конкурс «хороший» ответ не был опубликован даже после окончания конкурса.
<субъективно>
* Денег работникам предлагают мало.
* Работники увольняются из-за плохой обстановки.
</субъективно>
Мотивация участия в конкурсе понижена.printf Автор
20.05.2015 15:16$30 в час вроде не так уж мало, особенно по российским меркам-то.
А мотивация понижена потому что задача дурацкая, как по мне. Ну т.е. да, это как раз субъективно.
progchip666
Статья не плохая, но уж слишком сильно вы на денежный вопрос упирали. По моему тех, кто ставит минусы, именно этот момент раздражает.
printf Автор
На этот раз задача больно тоскливая, мне показалось что если деньги в шапку не вынести, то вообще потонет пост с нулем просмотров.
Прошу прощения, если переборщил. Больше не буду так делать.
Louter
Пояснити глупому: надо сохранить набор функций и аргументов или можно «твори что хоти», но выдать надо подобный набор методов и полноценный двусвязный список?