Добрый currentDayTime() 
Столкнулся с проблемой, не очень связанной с программированием, но где задать вопрос - не знаю.
Молодые специалисты на работе спрашивают: "Зачем нужно уметь реализовывать алгоритмы сортировки, поиска и т.п., если они уже написаны ( std::sort, std::find_if и т.д. ) ?"
То что это нужно уметь - я знаю ( и просьба - не переубеждайте меня в этом ), а вот аргументов - настоящих, а не "просто нужно", "поверь моему опыту" - найти не могу.
Помогите, плиз.
Списибо.

их надо уметь реализовывать только если собрался писать свою библиотеку алгоритмов

скажите им, что вы любитель изобретать велосипеды, причем скорее всего уступающие по качеству существующим

а че минусовать, интересно будет аргументы за посмотреть  

Это сообщение отредактировал(а) alexvs11 - 22.8.2010, 12:56

Я - имеющий собственую библиотеку контейнеров и алгоритмов - пару дней назад повнивательнее познакомился с std::sort. Штука хорошая в общем и может быть даже удобная в применении. И все хорошо, если вам нужно прогнать массив из сотни элементов. Если же элементов у вас ого-го, а правило сортировки чуть более сложное, чем сравнение интов, и еще вам не наплевать на производительность, то std::sort не подойдет - он неиллюзорно сливает как минимум из-за кучи накладных вызовов функции, да еще и по указателю.

Добавлено через 40 секунд
Т.е. в данном случае обощеность алгоритма становится его ахилесовой пятой.

Реализация дело второстепенное. Главное -- понимание. Просто дёргать std::sort или std::find для всего и всегда как минимум неэффективно. Скажем, нужно понимать, что например в задаче поиска k-го наименьшего числа в массиве необязательно сортировать весь массив, можно воспользоваться частичной сортировкой, а если мы имеем массив целых чисел в небольшом диапазоне, то сортировка подсчётом будет эффективнее стандартной. Тоже самое касается поиска, когда для std::set стандартный линейный std::find менее эффективен, чем двоичный std::set::find.

Как человек узнает все эти вещи -- вопрос другой. Есть несколько способов:
-- реализовать и проверить самому;
-- прочитать в книге; 
-- спросить у более опытного коллеги; 

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

алгоритм не очень то обобщен, ибо он имеет как минимум неск олько различных реализаций для всех типов итераторов, те для vector, list, deque итд не придется писать различные алгоритмы сортировки изза разных способов доступа
его нельзя будет просто использовать со всеми остальными контейнерами

а реализация достаточно эффективная, вообщем на работе надо заниматься работой, а не переписыванием стандартных сортировок

djamshud, либо у вас плохой компилятор, либо вы не понимаете принципов работы компилятора в С++
В общем случае не будет никаких вызовов по указателям, и никаких накладных вызовов функций.

Abyx,



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



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

djamshud, вы все же не понимаете работу компилятора.
если Callable *может быть заинлайнен* - он *будет заинлайнен*

вот тут будет инлайн


а вот тут не будет


Добавлено через 58 секунд

а вот это говорит о том что вы вообще не понимаете С++, и термина Callable в частности

Писать сортировки нужно в двух случаях: 
1. Когда учишься программировать. Сортировки - прекрасный способ повысить свою квалификацию в реализации не совсем уж тривиальных алгоритмов.
2. Когда стандартная сортировка не удовлетворяет по производительности. 

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

Ничего не имею против (в данном случае), но звучит красиво. Предлагаю писать, как Имеющий Собственную Библиотеку Контейнеров и Алгоритмоа 

Сорри за оффтоп.

Мальчик, меня твои наезды уже ###али. Разговор про С++, а не вижуалстудиевский компилятор. В gcc например это зависит от включенных настройек оптимизации, а не магических __decl-ов в исходнике. А так как std::sort может быть уже скомпилированной, в нее не заинланиться даже при желании. Поумерь пыл.

Добавлено через 1 минуту и 52 секунды
Любитель, ну тут кто-то что-то сказал про тех, кто реализует собственные библиотеки, вот я и уточнил про себя:).

Твой g++ - гуан*, и STL в нем гуан*.
C++ - хороший язык, а из за всяких кривых компиляторов у всяких джамшутов о нем складывается неверное впечатление.
Нормальные компиляторы компилят нормальный код, и в нормальных компиляторах есть кодогенерация во время линковки, и она работает по крайней мере для CRT+STL.

Abyx, ну что тебя вечно на обсуждение говна тянет? _Особо_ одаренным я рекомендую узнать значение выражения "в общем случае", а потом подумать, какое отношение к этому имет реализации конкретных компиляторов и библиотек.

ах да, накладные расходы на вызов по указателю при "сложном правиле сортировки" - это сколько?
в процентах от времени работы сложного правила сортировки?

Добавлено через 1 минуту и 31 секунду
djamshud, особо одаренным вроде вас, я предлагаю привести конкретные цифры и код.