Проверить и прокомментировать вариант решения тестового задания при приёме на работу

Приветствую!
Сделал тестовое задание, которое попросил сделать один работодатель, на что получил отказ и комментарий о том, что "оно сделано неидеально". Как вы думаете, что могло там не понравиться, чтобы знать на будущее? Это работодатель такой капризный или я такой кривой программер, что там действительно сделано так нехорошо? Несколько шероховатостей я вижу, но могли ли они быть основанием для отказа?

Ниже привожу свои варианты решения задач.

0

Сообщение от Fulcrum_013 Ну зачем же std::? Кроме std:: еще и С++ существует.

Затем, что без std это будет велосипед в квадрате.

Сообщение от Fulcrum_013 а результат парсинга вы куда деваете? Часом не в динамическую память?

Причем тут результаты? Автомат должен обрабатывать любое количество вложенных скобок. Поэтому, он должен хранить где-то историю своих переходов. Иначе как он из вложенных скобок вылезет? В моем случае это хранение реализовано на аппаратном уровне. В вашем - через велосипед. Аппаратная реализация заведомо выигрывает.

Сообщение от Fulcrum_013 Затем что в штатный стеке нельзя сортировать.

res->list.push_back(parse_value(stream)); res->set.insert(parse_value(stream));

0

Добавлено через 2 минуты

Сообщение от Renji Автомат должен обрабатывать любое количество вложенных скобок.

Ошибка номер раз. Не любое а такое которое юзер не напишет. Достаточно один раз распределить буфер под стек.

0

Сообщение от Fulcrum_013 Не по теме: Новый патент на колесо выдают примерно раз в 10 лет.

Сообщение от Fulcrum_013 Ошибка номер раз. Не любое а такое которое юзер не напишет. Достаточно один раз распределить буфер под стек.

В аппаратной реализации стека так и сделали. Но разговор не о предельной глубине стека, а о том что совсем без него автомат не заведется. И о том что вместо вашего написанного пусть даже за месяц велосипеда, у нас есть аппаратная реализация стека, которую вылизывали десятки лет. И оптимизировали процессор именно под этот вылизанный стек, а не под ваш велосипед.

0

Сообщение от Renji res->set.insert(parse_value(stream));

А если два одинаковых куска попадутся? А при открытии скобок создаем новый set который динамически создает буфер а при закрытии удаляем тоже с удалением динамического буфера? А при вставке насколько часто он будет перераспределять память?

Добавлено через 1 минуту

Сообщение от Renji И оптимизировали процессор именно под этот вылизанный стек

А про стек вызовов никто не говорит. Тут по всей видимости можно вообще только inline "вызовами" обойтись. Во всяком случае того что будет касаться сортировки и стека скобок. А для определения символа по всей видимости удобнее таки таблица indirect call будет чем if-ы, современные процы ветвления не любят. Хотя при таком количестве символов в алфавите это стрельба из пушки по воробъям.

Добавлено через 7 минут

Сообщение от Renji Но разговор не о предельной глубине стека

Как раз разговор об этом. Стек скобок не может быть длине строки, а в синтаксически правильной строке - половины длины строки. Поэтому динамически растущий он не нужен.

0

Сообщение от Fulcrum_013 А если два одинаковых куска попадутся? А при открытии скобок создаем новый set который динамически создает буфер а при закрытии удаляем тоже с удалением динамического буфера? А при вставке насколько часто он будет перераспределять память?

Если два одинаковых куска попадутся, то std::multiset спасет отца русской демократии. Сверху втыкается аллокатор на основе пула, с константным временем работы. Причем, не велосипедный, а готовый из буста. Аппаратному стеку он, конечно, не соперник, но вот с вашим велосипедным стеком вполне посоперничает.

Сообщение от Fulcrum_013 А про стек вызовов никто не говорит. Тут по всей видимости можно вообще только inline "вызовами" обойтись. Во всяком случае того что будет касаться сортировки и стека скобок.

Ага, здесь можно обойтись только inline вызовами, раскиданными по разлапистому switch(stack.pop()) или его аналогам. Только вот функционал этого switch(stack.pop()) будет абсолютно идентичен функционалу стека вызовов. С единственным отличием - тормозить будет. Архитектура процессора не под это оптимизирована.
Про читаемость C++ кода в который втиснули indirect call я вообще молчу тихонько. Ну а че, в Си вон вообще делают longjmp из одной функции в другую и не жалуются.

0

Сообщение от Renji Про читаемость C++ кода в который втиснули indirect call я вообще молчу тихонько.

Прекрасно читается. лучше чем ифы. Код классов с виртуальными методами читается же нормально? а это список indirectcall

Сообщение от Renji Сверху втыкается аллокатор на основе пула, с константным временем работы.

Аллокатор с константным временем работы - это шутка такая или те кто это написал в доке не в курсе как менеджер кучи ищет память для выделения? Или выделяем кусок побольше а потом переставляем номер последнего? Для стека самое то, но я и без буста так умею.
Здесь можно обойтись вообще без динамического распределения в процессе работы. Достаточно выделить буфера на старте. И возможно вообще без ветвлений. Хотя stack underflow все равно проверять надо. а если indirect call в этом месте прикрутить то гудбай inline pop()

0

Сообщение от Fulcrum_013 Прекрасно читается. лучше чем ифы. Код классов с виртуальными методами читается же нормально? а это список indirectcall

Виртуальные методы, это все тоже "побить автомат на подфункции".

Сообщение от Fulcrum_013 Аллокатор с константным временем работы - это шутка такая или те кто это написал в доке не в курсе как менеджер кучи ищет память для выделения?

Это такая оптимизация под конкретный класс. Свободная память режется на равные ломтики, ломтики соединяются в список, выделение сводится к извлечению ломтика из списка. Размер ломтика при этом строго фиксирован, но что поделаешь, за скорость надо платить.

0

Сообщение от Renji Архитектура процессора не под это оптимизирована.

Ты в курсе что некоторые switch(i) вот так ассемблируются: jmp [casetable[i]] ? Cам jmp для проца не проблема, спотыкается проц на ветвлении, потому что откатывается ветка предвычислений несработавшего варианта.

Добавлено через 2 минуты

Сообщение от Renji Это такая оптимизация под конкретный класс. Свободная память режется на равные ломтики, ломтики соединяются в список, выделение сводится к извлечению ломтика из списка. Размер ломтика при этом строго фиксирован, но что поделаешь, за скорость надо платить.

сколько глупостей вместо банального Stack[StakPtr++]=Value;

0

Сообщение от Fulcrum_013 Ты в курсе что некоторые switch(i) вот так ассемблируются: jmp [casetable[i]] ? Cам jmp для проца не проблема, спотыкается проц на ветвлении, потому что откатывается ветка предвычислений несработавшего варианта.

Ты в курсе что переход по ret процессор нормально предскажет, а вот переход по jmp [casetable[i]], по понятным причинам - нет? Ты в курсе что ret одновременно выполняет jmp SS:[ESP] И удаляет значение из макушки стека?

Сообщение от Fulcrum_013 сколько глупостей вместо банального Stack[StakPtr++]=Value;

Можешь делать банальное Stack[StakPtr++]=Value, с банальным ручным вызовом процедуры сортировки. Это как бы не оправдывает отказа от разбиения парсера на отдельные функции, вызывающие друг друга штатным call, а не велосипедами.

0

Сообщение от Renji Это как бы не оправдывает отказа от разбиения парсера на отдельные функции, вызывающие друг друга штатным call, а не велосипедами.

А вызова они всегда штатным call или indirect call идут. Вопрос в том что свой стек данных всегда работает быстрее чем рекурсия. Возьми хотя бы тоже вычисление факториала или фибоначи, а закраска с затравкой - так вообще. А здесь в стек нужно заносить только положение скобки.

Сообщение от Renji Это как бы не оправдывает отказа от разбиения парсера на отдельные функции

Ну функции возможно, только принцип разбиения абсолютно другой. и смысл разбиения - заменить ветвления на indirect call

Сообщение от Renji с банальным ручным вызовом процедуры сортировки

Какой процедуры сортировки? Ты о чем? Здесь не сортировка нужна а добавление в упорядоченный список с сохранением упорядоченности. Да кстати а в бусте что Ктулху автоматически сортировку вызывает?

Сообщение от Renji а вот переход по jmp [casetable[i]], по понятным причинам - нет

Ну сбросит L1 кеш инструкций. При L2 на борту не критично, а тем более при L3. Так же как при call, но ветку вычислений откатывать не придется.
Поэтому call [proctable[i]] 1 раз на символ сработает лучше чем по несколько if-ов на символ. Если при этом учесть что подмена состояния осуществляется подменой таблицы, то еще веселее, потому как даже для проверки синтаксиса вместо кучи ифов просто переписывается один указатель.

Добавлено через 16 минут
Табличка функций правда будет скорее всего больше обрабатываемой строки в разы. но за скорость приходится платить.

0

Спасибо, товарищи. Я думаю, что вопрос исчерпан с той задачей.
Если уж "пошла такая пьянка", то вот вам вторая моя тестовая задача и решение (результат пока не известен, но что-то мне подсказывает, что он не радужный, судя по тому, что работодатель молчит уже вторую неделю).
Задание:
Sort a binary file of unsigned 32-bit integers in ascending order in the assumption that the file size is significantly larger than available memory.

Expected result

C++ source code with a project or a make file of a console application, that is built with VS 2010/2013 or gcc(g++) 4.6/4.8

The application may assume the execution on a semi-idle multi-core 64bit OS with plenty of HD space.

Bonus features:

Use of C++11, STL or Boost(1.51 or 1.55)
Cross-platform solution
Production-level code

Решение приложено.

Вложения

FileSort.zip (7.3 Кб, 13 просмотров)

0

Сообщение от a_shy Если уж "пошла такая пьянка"

Пъянка пошла такая что все бросил и сел писать этот чертов автомат

0

)))

0

Сообщение от a_shy Решение приложено.

Нормально. В нашем ликбезе у автоматчиков на втором курсе такая лаба была, примерно так же делал, правда на паскале и процедурно, а то бы объяснить не смогли. Одно непонятно на кой ляд тут баст или STL? Ну разве что qsort оттуда попользовать для сортировки фрагментов, оно обшаблоненное быстрее должно быть чем с каллбэком для сравнения элементов.

Добавлено через 16 минут

Сообщение от a_shy he application may assume the execution on a semi-idle multi-core 64bit OS with plenty of HD space.

Так, а слона то мы и не заметили. Куски очень неплохо бы было сортировать в разных потоках. т.е. макс отведенное место делишь на количество конвейеров, сортируешь такие куски в памяти параллельно, а потом слияешь их прямо во временный кусочный файл . причем один поток слияет, другие в это время следующую порцию кусков сортируют. Ну а потом файлы слияешь в один.

0

Да, я это заметил, но поленился отсортировать многопоточно, написал это в todo. Честно говоря было вломак много времени на эту задачу расходовать.

0

a_shy, сразу же бросается в глаза бардак с генерацией исключений: в одной и той же функции в одних случаях throw, в других — throw new.

Сообщение от a_shy Темплейты - сам понимаю - там абсолютный оверкилл, но я их использовал, чтобы показать, что я не совсем лошара какой-нибудь и их тоже знаю.

Я не возьмусь оценивать насколько тут нужны шаблоны (т.к. дерево само по себе хочет быть шаблоном, и это нормально), но использование возможностей языка по принципу «чтобы было» негативно сказывается на тестовом задании. Адекватность кода важнее. Это так, на будущее.

Не знаю критериев, по которым конкретная контора оценивает задание, но я бы отменил высокую степень велосипедизма: свои структуры данных, свой парсер. Могу сослаться на Андрея Аксенова (неточная цитата):

…известная байка про производительность программиста, когда она отличается в двадцать раз. Она не в двадцать раз отличается, она отличается в сто раз. Живой пример — тестовое задание «Калькулятор». Специально обученный человек этот калькулятор пишет за тридцать минут. Причем аккуратненько, на yacc+lex (…). Специально обученный тупой баран пишет его за двое суток. (…) Почему за тридцать минут? Потому что человек знает классические инструменты, которым 50 лет и которые позволяют решать широкий спектр задач.

Доклад, примерно на 38 минуте.

0

Сообщение от 0x10 Не знаю критериев, по которым конкретная контора оценивает задание, но я бы отменил высокую степень велосипедизма

А мне например первое что сказали когда на работу устроился после универа - "Забудь все стандартные библиотеки и алгоритмы которые применял раньше, особенно буфера. Они здесь не работают. Тут мозгами думать надо а не библиотеки искать. Их подходящих нету. Это тебе не бабки в банке считать и не даже не САПР сопромутить. Здесь АСУТП а не сборище говнокода."

0

Сообщение от Fulcrum_013 Забудь все стандартные библиотеки

Если явно оговорено — претензий нет. В исходном задании ограничений не было.

0

Сообщение от 0x10 Если явно оговорено — претензий нет. В исходном задании ограничений не было.

Я к тому что велосепедизм штука полезная. Всегда находится 10% функционала из за которых приходится свое пилить, а не либу пользовать. Или как минимум что то свое допиливать. Сейчас к примеру сижу полностью перепиливаю борландовскую обертку WinHTTP, при том что штука обалденная. Одна беда - WebSocket туда не приделан и куки изнутрей не вытащить, чтоб отдельно сделанному сокету дать. вот и приходится полностью перепиливать.

0

Сообщение от Fulcrum_013 А вызова они всегда штатным call или indirect call идут.

В схеме ТС с дословной реализацией автомата, никаких indirect call нету. Есть явно объявленная переменная состояния, определяющая какая ветка алгоритма будет выполнена и подменяющая собой штатный механизм call. И самопальный std::stack, подменяющий собой штатный механизм возврата. Я так понял, вы ратовали именно за это чудо-юдо. И да, вы в курсе что indirect call будет тормознутее call, из-за все того же предсказания переходов?

Сообщение от Fulcrum_013 Какой процедуры сортировки? Ты о чем? Здесь не сортировка нужна а добавление в упорядоченный список с сохранением упорядоченности. Да кстати а в бусте что Ктулху автоматически сортировку вызывает?

Сортировка вставкой в отсортированный список, все равно остается сортировкой. Ну а вызывают ее потроха шаблона.

Сообщение от Fulcrum_013 Ну сбросит L1 кеш инструкций. При L2 на борту не критично, а тем более при L3. Так же как при call, но ветку вычислений откатывать не придется.

Ну да, подумаешь, спекулятивное выполнение инструкций отвалилось, так как процессор не знает чего там спекулятивно считать надо. Главное что кеш на месте.

0