Здравствуйте, Mystic, Вы писали:

M>Здравствуйте, мыщъх, Вы писали:

М>>быстрая реализация на си? гм... без профайлера не скажу. табличная реализация vs калькуляция. трудно сказать, что будет быстрее на современных процессорах, тем более без указания типа процессора.

M>Одними и самых быстрых считается эти, по сути 4-5 ассемблерных команд без всяких условий.
1) надеюсь, вы не ожидаете, что этот код напишут прямо на собеседовании?
2) тормозную реализацию можно написать и на питоне (на глаз должно хватить дюжины строк);
3) даже для системщиков это очень узкий вопрос и не уверен, что показательный;
4) в качестве тестового задания -- ИМХО слишком просто (ответ быстро находится в иннете);
5) а почему вы против вычислительных алгосов? на x86 с LEA получается довольно шустро, даже если писать на си -- есть шанс, что оптимизатор это заоптимизирует как надо

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

хотя вы меня натолкнули на интересный вопрос для собеседования -- "в каком порядке искать ответ на вопрос". гугл? гугл не всемогущ. поиск по патентным базам зачастую сокращает ваш путь в десятки и сотни раз. как-то был случай в жизни. попросили реконструировать проприетарный протокол. протокол закрытый, но запатентованный. причем, протокол сношения с микроконтроллером, которому передается микропрграмма. для страховки заказчик дал задачу мне и еще одному парню. я быстро нашел патент и убедился, что опкоды совпадают на 90% (со времен подачи патента протокол претерпел несколько ревизий), в результате послал заказчику полную реконструкцию. мой коллега убил гораздо больше времени и реконстрировал лишь 30% опкодов (т.е. остальные не юзались в конкретной версии клиента, которую он реверсил).

в патентнах находится по меньше мере 60% ответов на мои вопросы, 30% находит гугл, 10% твиттер и потому когда человек говоит "що тут думать -- тут гуглить надо" с ним все ясно.

кстати, про вашу задачу. поднял исходники никсов и нашел там решение на си без привязки к асму. не уверен, что самое быстрое, но уврен, что:
а) рабочее;
б) не имеющее патентных ограничений;

про алгосы, найденные в иннете, ни того, ни другого сказать нельзя.