Добрый 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, особо одаренным вроде вас, я предлагаю привести конкретные цифры и код.

!  Любитель

Предлагаю всем перестать ругаться и перевести дискусию в мирное русло!

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

alexvs11, а эффективность(стоимость) написания и поддержки кода сравнивать будем?

Abyx, думаю это сразу станет очевидным

Для того, что бы из словосочетания "молодой специалист" исключить слово "молодой".

В параметрах шаблона передается только информация о типе. Для классов (функциональных объектов), это подойдёт, но не для функций, их нельзя инстанцировать. Однако это не означает что функция не встроится.

Добавлено @ 09:44
g++ не его. А утверждение голословное и необдуманное.


Это сообщение отредактировал(а) Леопольд - 23.8.2010, 09:45

Леопольд, в параметры шаблонов можно передавать любые значения времени компиляции. Функцию тоже можно передать, как-то так:

Это не скомпилируется. Я же говорил что шаблоны это не копипаст... 
Этот код можно переписать так:

Не, нельзя. Разные вещи...

Это сообщение отредактировал(а) Леопольд - 23.8.2010, 10:10

А еще там можно передать константу, например указатель на функцию. Не знали?

Леопольд, данунах?! :) УМВР

Кхм... Никогда не пробовал. Действтельно, что мешает...

Леопольд, я же говорил, шаблоны - это копипаст :)

Всегда готов "подставить ножку" если кто-то споткнулся... 


Так будет более обобщённо.

Это сообщение отредактировал(а) Леопольд - 23.8.2010, 10:27

Не может - она шаблонная
При желании (и доброй воле) компилятора в нее всегда можно заинлайнится (т.к. она шаблонная - см. выше)   

На счет поиска. Если кто-то не умеет реализовывать алгоритм поиска, то он не знает конструкций for и if, а если он их не знает, то до звания "специалиста" ему далеко.
На счет сортировки. Что значит "уметь"? Есть, например, простой алгоритм сортировки "пузырька". Если уметь значит знать его наизусть, то это не сложно, и смысла большого в этом нет, т.к. этот алгоритм годится только в простейших программах. Что касается более сложных и оптимальных алгоритмов (пирамидальный и проч.), то они довольно сложны, и выучивать их нет смысла. Всегда можно обратиться в справочник и проч..

Это сообщение отредактировал(а) ИванМ - 23.8.2010, 15:18

все реализации std::sort,  которые я видел, довольно похожи, и весьма неплохо реализованы.
написать лучше для частного случая (если сортируемая последовательность не имеет особенностей) довольно сложно, проще грамотно осуществить вызов std::sort. разговор про накладные расходы на вызов функции вздор, конечно. 

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

порекомендуйте своим коллегам эту книжку

Эх, что-то у меня настроение хорошее...
На самом деле, djamshud в чем-то прав на счет инлайна и std::sort.

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

Abyx скомпилил несколько вариантов кода, и получил весьма занятные результаты.
Но выкладывать я сюда ничего не буду, ибо неохота бисер метать. Кому интересно, компилятор в руки и вперед.

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

честно говоря, единственное здравое высказывание по теме. 
baldina, спасибо.
Закрываю

Вообще знания никогда не бывают лишними! А уж такая тема как "базовые алгоритмы" должна быть для программистов как мёд для пчёл! на роду написано читать и читать...

То что это изучено и 10 раз заимплеменчено КЕМ-ТО, вовсе не значит, что это не надо изучать НАМ!, а тем более, когда речь идёт о таких базовых вещах... это нужно знать, чтобы потом применить - и, как справедливо было замечено, "применение" может найтись совсем не в области поиска и тогда никакие справочки увы не помогут.

Ландау своим студентам говорил "не спрашивайте как это вам может понадобиться, когда оно вам понадобиться вы этим воспользуетесь."

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