On 19.02.2013 4:08, SkyDance wrote:
> Именно в этом состоит претензия к собеседованию в стиле "экзамен". И да, > я тоже считаю неудачными такие собеседования. Ведь в реальной разработке > доступ в интернет у меня есть, и если я прямо сейчас не помню > асимптотики, скажем, radix sort — мне не составит труда за 5 минут > найти. Любые собеседования, основанные на проверке памяти у кандидата > могут проверить лишь память, но никак не уровень мышления.
Но тебе тут же ответят, что мы просим на собеседовании тут же некий код
написать. И таки да с таким подходом я согласен, если набирают студентов
и за ними потом еще год опытный товарищ будет присматривать.
З.Ы. Например, я вообще не умею код сходу писать. Мне надо подумать,
посмотреть на задачу с разных соторон, покрутить ее в голове, посмотреть
ее решения в инете. Потом делаю наброски и после того, как мне
становиться ясно процентов на 80%, что именно нужно сделать и как,
только после этого я начинаю писать код. Возможно это связано с тем, что
мне никогда не ставились задачи в стиле, вот интерфейс функции, вот
входные данные, вот выходные, напиши цикл. Сам тоже никогда в такой
постановке не ставил задач. Обычно в варианте, вот нужно реализовать
некую функциональность, разберись, составь план работы и приступай,
причем человек в курсе, что дальше предполагается ему делать и в общем в
курсе всего продукта.
_>* Данные не входят в оперативную память: памяти 16GB, данных 600GB. qsort() / std::sort() расчитывают, что данные доступны в любой момент. _>* Данные не входят на винчестер. Винт 10TB, данных 1000TB, размазанных по 100 машинам. Городить адаптер к стандартному алгоритму или сразу написать с нуля?
Разумным видится использование готовой системы работы с данными, обычная БД или специфическая готовая, или готовый сервис. Обычно над такими задачами работают хорошие специалисты и соревноваться с ними с нуля проблематично.
_>* Запись на диск очень дорогая, надо минимизировать количество обращений. Двупроходная сортировка: вначале строим перестановку, используя только индексы; потом двигаем непосредственно данные. Возможно, какая-то библиотека так умеет, но мне не попадалось.
std::sort позволяет менять компаратор , в том числе используя ключи к элементам (индексы, указатели и т.п.)
_>* Низкоуровнеый драйвер, куда вход CRT/STL заказан.
Почему заказан STL? сортировка не должна использовать обращений к CRT, и обычно неплохо реализована.
_>* Банально отсортировать linked-list. qsort() считает, что работает с массовом, как научить его брать next указатель?
Свои контейнеры можно адаптировать под требования стандартных. К сожалению std::sort() требует random access итераторов (про qsort() забудьте как кошмар) , так что свой односвязный список им сортировать можно но не нужно.
Здравствуйте, minorlogic, Вы писали:
_>>* Данные не входят в оперативную память: памяти 16GB, данных 600GB. qsort() / std::sort() расчитывают, что данные доступны в любой момент. _>>* Данные не входят на винчестер. Винт 10TB, данных 1000TB, размазанных по 100 машинам. Городить адаптер к стандартному алгоритму или сразу написать с нуля?
M>Разумным видится использование готовой системы работы с данными, обычная БД или специфическая готовая, или готовый сервис. Обычно над такими задачами работают хорошие специалисты и соревноваться с ними с нуля проблематично.
Хм, а этим специалистам-то где брать фреймворк?
_>>* Низкоуровнеый драйвер, куда вход CRT/STL заказан. M>Почему заказан STL? сортировка не должна использовать обращений к CRT, и обычно неплохо реализована.
Смесь Си и Ассемблера, bare metal. Какую библиотеку будем брать?
Здравствуйте, hpux100, Вы писали:
H>На собеседовании часто задают вопрос по алгоритмам сортировок. H>Но где реально на практике они применяются, я на этот вопрос не отвечу, поскольку никогда это на практике не применял. H>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.
Да совсем банально — топологическая сортировка графа, который описывает некоторые зависимости меж данными. Требуется при выборе правильного порядка их обработки. Скажем, генерация makefile-а собирающего генеренные проекты.
Ну в UI так постоянно — сортировка таблиц по разным столбцам, которым соответствуют различные критерии. Сортировка, как способ приведения данных в некоторую каноническую форму с целью сравнения и т.п.
V>Но тебе тут же ответят, что мы просим на собеседовании тут же некий код V>написать.
Так я этот момент и считаю бессмысленным. Писать тривиальный код (в т.ч. сортировки) не имеет смысла, он уже написан и протестирован в разных библиотеках. В крайнем случае, можно подсмотреть идею реализации (если библиотека не подходит по лицензии).
А нетривиальный код писать — не дело получаса на собеседовании, да без помощи гугла. А уж если понадобится какой более-менее реальный код, скажем, с тривиальными boost::function + boost::bind (ну нет в C++ "сахарных" делегатов!) — так и вовсе без помощи доков могу долго тыркаться. Ибо синтаксис непростой, хоть и часто применяется — плохо запоминается.
Здравствуйте, Sni4ok, Вы писали:
S>Здравствуйте, hpux100, Вы писали:
H>>Но где реально на практике они применяются, я на этот вопрос не отвечу, поскольку никогда это на практике не применял.
S>потому-что вы скорее всего плохой программист(или начинающий) и работаете над плохими задачами, которые не будут генерировать много денег.
1C и все вокруг ERP — это плохие задачи? Судя по HH они таки дают денег поболее всяких яйцеголовых наворотов типа проектов с самописными сортировками и прочим hand made.
On 20.02.2013 0:58, SkyDance wrote:
> Так я этот момент и считаю бессмысленным. Писать тривиальный код (в т.ч. > сортировки) не имеет смысла, он уже написан и протестирован в разных > библиотеках. > А нетривиальный код писать — не дело получаса на собеседовании, да без > помощи гугла.
Я тоже, но большинство здесь считают наоборот. Причем код на
собеседовании ничего не показывает, кроме твоего стиля оформления кода.
Для студентов можно попросить написать несколько сnрочек, чтобы увидеть
насколько они любят голые указатели, пользуются ли const. Но когда
подобное просят у людей, у которых за плечами 10-ки выполненных
проектов, это я понять могу только в двух вариантах: детское
самоутверждение или боязнь принятия решений или и то и другое вместе.
On 20.02.2013 0:59, SkyDance wrote:
> C runtime, из нее просто скопировать функцию qsort. Там никакой магии, и > протестировано как следует.
Это сильно просто и быстро. Надо же часто долго писать этот велосипед,
затем полгода-год в нем баги править. А все это время будет капать
зарплата и не только этому программисту, но и всем начальникам и
продажникам не придется бегать нового заказчика искать, пока этого
пилить удается.
Здравствуйте, SkyDance, Вы писали:
H>>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.
SD>Правильнее было бы задать вопрос "в каком таком месте вам понадобилось применить нестандартный алгоритм сортировки, при этом нельзя было бы заглянуть в google или учебник" SD>Именно в этом состоит претензия к собеседованию в стиле "экзамен". И да, я тоже считаю неудачными такие собеседования. Ведь в реальной разработке доступ в интернет у меня есть, и если я прямо сейчас не помню асимптотики, скажем, radix sort — мне не составит труда за 5 минут найти. Любые собеседования, основанные на проверке памяти у кандидата могут проверить лишь память, но никак не уровень мышления.
Чтобы воспользоваться интернетом нужно знать, что ты ищешь. И даже если ты найдёшь то, что ищешь скопировать это к себе (особенно гнутый кодт) не всегда тривиальная задача. Проще самому.
Сортировки и структуры данных в моей практике применялись в эвристике и анализе данных. 99,9% работы это LDR, STR, BL. Но мы-то как раз и работаем, чтобы увидеть этот самый 0,1%, постоянно совершенствуясь и выгрызая его у нубов.
Это не стоит спрашивать на собеседовании. Лучше про кэши, потокобезопасность и заработную плату.
_>* Данные не входят на винчестер. Винт 10TB, данных 1000TB, размазанных по 100 машинам. Городить адаптер к стандартному алгоритму или сразу написать с нуля?
Это задача довольно успешно решается, так называемыми грид-вычислениями. Oracle, начиная с 10g, на это очень хорошо заточен.
Здравствуйте, IObserver, Вы писали:
_FR>>В VB 6 стандартная библиотека была настолько убога, что бинарный поиск вот приходилось писать самим. Так же, если было нужно отсортировать набор чего-то по какому-либо условию — засучивай рукава.
IO>А что там засучивать: находишь на github готовую реализацию на любимом языке программирования и меняешь названия функций. Все! Даже не нужно понимать как оно работает.
Интересно, откуда тогда столько неприязни к начинающим кодерам на Дельфи, которые на любой чих компоненты ищут?
Здравствуйте, hpux100, Вы писали:
H>Подскажите кто нибудь сталкивался в промышленных проектах с необходимость применять алгоритмы сортировок.
Приходилось реализовывать топологическую сортировку в самописной ERP, причем на T-SQL, для формирования партий изготовляемых деталей и оптимального распределения загрузки оборудования. Естественно сама сортировка была лишь элементом этого бизнес-процесса.
При использовании merge-алгоритмов требуется, чтобы источники были отсортированы по ключу. Да много где...
Мне приходилось, писать сортировку файла.
Как ты знаешь, доступ к большинству бинарных файлов последовательный. Файл большой, время его сортировки критично
