Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > C/C++: Общие вопросы > Реализация алгоритма сортировки "ручками"


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

Автор: Abyx 22.8.2010, 12:23
их надо уметь реализовывать только если собрался писать свою библиотеку алгоритмов

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

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

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

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

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

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

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

Автор: alexvs11 22.8.2010, 13:39
Цитата(djamshud @  22.8.2010,  13:11 Найти цитируемый пост)
Т.е. в данном случае обощеность алгоритма становится его ахилесовой пятой.


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

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

Автор: Abyx 22.8.2010, 13:40
djamshud, либо у вас плохой компилятор, либо вы не понимаете принципов работы компилятора в С++
В общем случае не будет никаких вызовов по указателям, и никаких накладных вызовов функций.
Цитата(djamshud @  22.8.2010,  14:11 Найти цитируемый пост)
std::sort не подойдет - он неиллюзорно сливает как минимум из-за кучи накладных вызовов функции, да еще и по указателю.

Автор: djamshud 22.8.2010, 13:54
Abyx,

Код

std::sort(start,end,sortfnc);


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

Код

std::sort<sortfnc>(start,end);


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

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

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

bool pred(..) {...}

sort(...., pred)


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

__declspec(dllexport) bool pred(..);

sort(...., pred)


Добавлено через 58 секунд
Цитата(djamshud @  22.8.2010,  14:54 Найти цитируемый пост)
std::sort<sortfnc>(start,end);

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

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

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

Автор: Любитель 22.8.2010, 14:14
Цитата(djamshud @  22.8.2010,  13:11 Найти цитируемый пост)
Я - имеющий собственую библиотеку контейнеров и алгоритмов - 

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

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

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

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

Автор: Abyx 22.8.2010, 14:37
Цитата(djamshud @  22.8.2010,  15:25 Найти цитируемый пост)
А так как std::sort может быть уже скомпилированной, в нее не заинланиться даже при желании. 

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

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

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

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

Автор: Любитель 22.8.2010, 15:24

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

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

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

Автор: alexvs11 22.8.2010, 15:43
Abyx, думаю это сразу станет очевидным

Автор: ИванМ 22.8.2010, 22:07
Цитата(borisbn @  22.8.2010,  12:04 Найти цитируемый пост)
Молодые специалисты на работе спрашивают: "Зачем нужно уметь реализовывать алгоритмы сортировки, поиска и т.п., если они уже написаны ( std::sort, std::find_if и т.д. ) ?"

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

Автор: Леопольд 23.8.2010, 09:40
Цитата(djamshud @  22.8.2010,  13:54 Найти цитируемый пост)
Код
std::sort<sortfnc>(start,end);
В таком случае функция подставилась бы, а при желании и заинлайнилась, во время компиляции. 
В параметрах шаблона передается только информация о типе. Для классов (функциональных объектов), это подойдёт, но не для функций, их нельзя инстанцировать. Однако это не означает что функция не встроится.

Добавлено @ 09:44
Цитата(Abyx @  22.8.2010,  14:37 Найти цитируемый пост)
Твой g++ - гуан*, и STL в нем гуан*.
g++ не его. А утверждение голословное и необдуманное.

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

Код

template<void(*bar)()>
void foo(){
bar();}

Автор: Леопольд 23.8.2010, 10:03
Код
template<void(*bar)()>
void foo(){
bar();}
Это не скомпилируется. Я же говорил что шаблоны это не копипаст... smile
Этот код можно переписать так:
Код
typedef void(*bar)();
bar();


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

Автор: Abyx 23.8.2010, 10:03
Цитата(Леопольд @  23.8.2010,  10:40 Найти цитируемый пост)
В параметрах шаблона передается только информация о типе.

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

Автор: djamshud 23.8.2010, 10:04
Леопольд, данунах?! :) УМВР

Автор: Леопольд 23.8.2010, 10:09
Цитата(Abyx @  23.8.2010,  10:03 Найти цитируемый пост)
А еще там можно передать константу, например указатель на функцию.
Кхм... Никогда не пробовал. Действтельно, что мешает...

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

Автор: Леопольд 23.8.2010, 10:16
Цитата(djamshud @  23.8.2010,  10:12 Найти цитируемый пост)
Леопольд, я же говорил, шаблоны - это копипаст smile 
Всегда готов "подставить ножку" если кто-то споткнулся... smile

Код
template<typename T>
void foo(){
    T()();
}
template<typename T, T& bar>
void foo(){
    bar();
}

void bar(){
    std::cout<<"test"<<std::endl;
}
struct Bar{
    void operator() (){
        std::cout<<"test"<<std::endl;
    }
};

int main(){

    foo<void(), bar>();
    foo<Bar>();

    return 0;
}

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

Автор: xvr 23.8.2010, 15:09
Цитата(djamshud @  22.8.2010,  14:25 Найти цитируемый пост)
А так как std::sort может быть уже скомпилированной, 
Не может - она шаблонная
Цитата

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

Автор: ИванМ 23.8.2010, 15:17
Цитата(borisbn @  22.8.2010,  12:04 Найти цитируемый пост)
"Зачем нужно уметь реализовывать алгоритмы сортировки, поиска и т.п., если они уже написаны ( std::sort, std::find_if и т.д. ) ?"

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

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

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

порекомендуйте своим коллегам http://www.ozon.ru/context/detail/id/2963462/

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

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

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

Автор: baldina 24.8.2010, 12:03
Цитата

и не посмотрел на дизасм

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

Автор: borisbn 31.8.2010, 21:28
Цитата(baldina @  23.8.2010,  15:31 Найти цитируемый пост)
1. программист должен понимать устройство основных алгоритмов. самое эффективное средство - реализовать самому2. это хорошая практика для того что бы перестать быть "начинающим". можно реализовывать и другие алгоритмы, но преимужество поиска, сортировки и т.п. в том, что они а) очень хорошо изучены б) в их реализациях используются приемы, применимые во многих других алгоритмах


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

Автор: Master01 3.9.2010, 23:27


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

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

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

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

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)