Автор Тема: Как часто и каким образом используете алг  (Прочитано 16925 раз)

Илья Ермаков

  • Sr. Member
  • ****
  • Сообщений: 493
    • Просмотр профиля
Споров про (не)удобство обобщённых стандартных библиотек было много..

Всё-таки хотелось бы распросить уважаемых коллег:
а как часто и в каких задачах они вообще используют такие "типовые" алгоритмы, как сортировка, двоичный поиск и им подобные?

"До кучи" интересно, какие типы контейнеров применяете и как часто.

Но про алгоритмы более интересно. Потому что контейнеры общего характера реализовываются и без обобщённого программирования. А вот алгоритмы уже очень трудно представить.

(Потому что мне трудно представить класс практических задач, где та же сортировка бы встречалась на каждом шагу. В системщине - редко, в прикладухе её делает либо СУБД, либо уже GUI-компоненты...)

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Как часто и каким образом используете алг
« Ответ #1 : Февраль 21, 2012, 08:19:04 am »
Что подразумевается под обобщенкой? Параметрический полиморфизм?
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Как часто и каким образом используете алг
« Ответ #2 : Февраль 21, 2012, 11:51:33 am »
а как часто и в каких задачах они вообще используют такие "типовые" алгоритмы, как сортировка, двоичный поиск и им подобные?
Пишу на C#. Обощённые алгоритмы почти не использую. Несколько раз понадобилась сортировка (для встроенного в программу профилировщика), тогда я быстренько написал её сам. Двоичный поиск никогда не был нужен. Иногда использую generic типы в контейнерах (хэштаблицах), но только для значений, не для ключей, ключи конкретные ибо обобщённо делать поиск по generic ключу неэффективно получается (для каждого конкретного типа ключа поиск можно реализовать более эффективно чем обобщённо для всех сразу).

Berserker

  • Sr. Member
  • ****
  • Сообщений: 254
    • Просмотр профиля
Re: Как часто и каким образом используете алг
« Ответ #3 : Февраль 21, 2012, 01:17:18 pm »
Delphi. Сплошь и рядом нужны ассоциативные массивы и списки, а соответственно и сортировка на уровне быстрой. Обобщённые контейнеры, хранящие объекты-обёртки над реальными данными слишком затратны. В текущих реализациях использую ручное указание, владеет ли контейнер элементами и являются ли элементы объектами. INTEGER<>POINTER взаимоконвертируются друг в друга.

Peter Almazov

  • Sr. Member
  • ****
  • Сообщений: 482
    • Просмотр профиля
Re: Как часто и каким образом используете алг
« Ответ #4 : Февраль 21, 2012, 01:47:03 pm »
C#. Сортировка периодически встречается, в этом случае используется LINQ. Исключений не припомню.
Двоичный поиск забыл когда использовал (но такое было).

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Как часто и каким образом используете алг
« Ответ #5 : Февраль 21, 2012, 03:22:09 pm »
Споров про (не)удобство обобщённых стандартных библиотек было много..

Всё-таки хотелось бы распросить уважаемых коллег:
а как часто и в каких задачах они вообще используют такие "типовые" алгоритмы, как сортировка, двоичный поиск и им подобные?

Довольно часто. Ну не каждый день, потому что вообще большая часть моего времени - это сопровождение. Но если взять написания "нового" кода - то довольно часто. Кроме того, не следует забывать еще более типовые for_each/find/map - на каждый день :)

"До кучи" интересно, какие типы контейнеров применяете и как часто.

std::vector как универсальный динамический массив - вне конкуренции. Ну и map (ассоциативный), конечно. Хотя если взять последний месяц - то были и set и stack и queue и deque.

(Потому что мне трудно представить класс практических задач, где та же сортировка бы встречалась на каждом шагу. В системщине - редко, в прикладухе её делает либо СУБД, либо уже GUI-компоненты...)

Кстати, с сортировкой и СУБД все не так однозначно. Есть такой шаблон, что если СУБД, то она должна и сортировать. Но не всегда. Очень даже часто проще/быстрее/правильнее делать сортировку в прикладном коде.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Как часто и каким образом используете алг
« Ответ #6 : Февраль 21, 2012, 04:22:19 pm »
Ну, поскольку никто так и не уточнил что подразумевается под "обобщенными" алгоритмами, буду считать что это параметрический полиморфизм времени компиляции в C++.

Споров про (не)удобство обобщённых стандартных библиотек было много..

Всё-таки хотелось бы распросить уважаемых коллег:
а как часто и в каких задачах они вообще используют такие "типовые" алгоритмы, как сортировка, двоичный поиск и им подобные? "До кучи" интересно, какие типы контейнеров применяете и как часто.
Но про алгоритмы более интересно. Потому что контейнеры общего характера реализовываются и без обобщённого программирования. А вот алгоритмы уже очень трудно представить.
(Потому что мне трудно представить класс практических задач, где та же сортировка бы встречалась на каждом шагу. В системщине - редко, в прикладухе её делает либо СУБД, либо уже GUI-компоненты...)
А если ты сам пишешь эту самую СУБД и GUI-компоненты? ;-) Последнее - я писал. Точнее писал, как модно нынче выражаться, gui-framework. Кроме того, даже если gui "фреймворк" уже написан другими, то обычно это ж все равно конструктор. Какой-нибудь список (в гуи) выведет элементы ровно в таком порядке в котором ты их отсортируешь.
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"

alexus

  • Гость
Re: Как часто и каким образом используете алг
« Ответ #7 : Февраль 22, 2012, 05:57:38 am »
Вопрос о выборе тех или иных средств зависит от цели, которая должна быть достигнута. Как известно, цель может оправдывать средства, а может и... не оправдывать. Если цель написать небольшую (учебную, например) программу, то желательно использовать "стандартные" средства языка/среды разработки/ОС. Срок жизни таких программ, как правило, невелик и сопоставим со сроком жизни средств, которые используются. Если же речь идёт о создании большой системы/программного комплекса, то предпочтительнее подход с минимальным использованием "стандартных" средств, поскольку не исключено, что срок их жизни окажется короче не только срока жизни продукта, но... даже срока его создания. Для примера, что было бы с теми продуктами, которые созданы на Delphi, если бы эта среда разработки не была своевременно перекуплена, если бы в неё внесли критические изменения?..
Удобство... При создании небольшой программы можно не обращать внимания на незначительные неудобства использования "стандартных" средств (понятно же, что "тиражная" одежда редко хорошо сидит на фигуре конкретного человека), но если проект большой, то "маленькие" неудобства могут перерасти в большие проблемы. И здесь правильным будет решение о том, чтобы совсем отказаться от тех "стандартных" элементов, которые создают проблемы, написав вместо них свои элементы (алгоритмы, библиотеки, шаблоны, компоненты...). С учётом того, что было сказано ранее, такой проект можно  развивать и сопровождать дольше и с большими удобствами.
Эффективность... Применение "стандартных" библиотек даёт "стандартную" эффективность, которой... может оказаться недостаточно (в критических участках). Для примера стандартная подпрограмма/шаблон сортировки максимально дистанцирована от типа и порядка сортируемых данных, это обеспечивает ей широкое применение. И в простых случаях её производительности достаточно, но... для специфических данных (а, собственно, все реальные данные имеют некоторую специфику) "рукописная" сортировка может оказаться значительно эффективнее. Трудно ли написать свою сортировку (точнее сказать, свою разновидность сортировки)?.. Сортировка в среднем записывается в 20-30 строк... бинарный поиск в 5-10 строк.. Зная алгоритмы, их сильные и слабые стороны... толковому разработчику не потребуется много времени, чтобы написать свою разновидность алгоритмов, нацеленную на эффективную обработку специфических данных. И далее с учётом п.2 и п.1...

Не следует истолковывать мои слова, как призыв к переписыванию "стандартных" алгоритмов. Думать надо, прежде всего, о цели, а средства подбирать в зависимости от неё.

vlad

  • Hero Member
  • *****
  • Сообщений: 1391
    • Просмотр профиля
Re: Как часто и каким образом используете алг
« Ответ #8 : Февраль 22, 2012, 03:29:48 pm »
Вопрос о выборе тех или иных средств зависит от цели, которая должна быть достигнута. Как известно, цель может оправдывать средства, а может и... не оправдывать. Если цель написать небольшую (учебную, например) программу, то желательно использовать "стандартные" средства языка/среды разработки/ОС.

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

Срок жизни таких программ, как правило, невелик и сопоставим со сроком жизни средств, которые используются. Если же речь идёт о создании большой системы/программного комплекса, то предпочтительнее подход с минимальным использованием "стандартных" средств, поскольку не исключено, что срок их жизни окажется короче не только срока жизни продукта, но... даже срока его создания.

С таким подходом - вам прямая дорога в оберон :) Делаем железку, делаем компилятор и вперед... На самом деле нет ничего страшного в смене стандартных средств - ну будет у вас часть продукта собираться древнючей дельфей, для действительно большой системы - не проблема. Ну, конечно, на заведомо однодневки ставить не стоит (я бы вот на дельфи и не поставил, борланд загибаться давно начал ;)

Удобство... При создании небольшой программы можно не обращать внимания на незначительные неудобства использования "стандартных" средств (понятно же, что "тиражная" одежда редко хорошо сидит на фигуре конкретного человека), но если проект большой, то "маленькие" неудобства могут перерасти в большие проблемы. И здесь правильным будет решение о том, чтобы совсем отказаться от тех "стандартных" элементов, которые создают проблемы, написав вместо них свои элементы (алгоритмы, библиотеки, шаблоны, компоненты...). С учётом того, что было сказано ранее, такой проект можно  развивать и сопровождать дольше и с большими удобствами.

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

Эффективность... Применение "стандартных" библиотек даёт "стандартную" эффективность, которой... может оказаться недостаточно (в критических участках). Для примера стандартная подпрограмма/шаблон сортировки максимально дистанцирована от типа и порядка сортируемых данных, это обеспечивает ей широкое применение. И в простых случаях её производительности достаточно, но... для специфических данных (а, собственно, все реальные данные имеют некоторую специфику) "рукописная" сортировка может оказаться значительно эффективнее. Трудно ли написать свою сортировку (точнее сказать, свою разновидность сортировки)?.. Сортировка в среднем записывается в 20-30 строк... бинарный поиск в 5-10 строк.. Зная алгоритмы, их сильные и слабые стороны... толковому разработчику не потребуется много времени, чтобы написать свою разновидность алгоритмов, нацеленную на эффективную обработку специфических данных. И далее с учётом п.2 и п.1...

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

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Как часто и каким образом используете алг
« Ответ #9 : Февраль 22, 2012, 06:30:52 pm »
for_each/find/map std::vector set и stack и queue и deque.
Осталось не понятным пишешь ли ты сам новые шаблонные алгоритмы или же всегда всё только из готовых-стандартных шаблонных кубиков собираешь?

Губанов Сергей Юрьевич

  • Hero Member
  • *****
  • Сообщений: 590
    • Просмотр профиля
    • Домашняя страница
Re: Как часто и каким образом используете алг
« Ответ #10 : Февраль 22, 2012, 06:51:59 pm »
Ну вот я как раз сейчас занимаюсь оптимизацией (по скорости)
Кстати, ни из одного стандартного контейнера нельзя удалить произвольный элемент за О(1) просто потому, что сначала его нужно в нём найти. Контейнеры из которых удаление элементов невозможно в принципе могут быть реализованы эффективнее контейноров из которых удаление элементов в принципе возможно. Ну и так далее. Так что, в моём понимании, оптимизация, если конечно это не просто чистка от говнокода, подразумевает неизбежный отказ от универсальных стандартных шаблонных кубиков.

DIzer

  • Гость
Re: Как часто и каким образом используете алг
« Ответ #11 : Февраль 22, 2012, 08:48:46 pm »
Кстати, ни из одного стандартного контейнера нельзя удалить произвольный элемент за О(1) просто потому, что сначала егоquote] Не понял - пусть мы имеем массив ссылок на  существующие простые обьекты(например, записи -куда уж стандартней) - разве нельзя из него удалить элемент за  О(1)?

DIzer

  • Гость
Re: Как часто и каким образом используете алг
« Ответ #12 : Февраль 22, 2012, 08:50:57 pm »
Не понял - пусть мы имеем массив ссылок на  существующие простые обьекты(например, записи -куда уж стандартней) - разве нельзя из него удалить элемент за  О(1)?

alexus

  • Гость
Re: Как часто и каким образом используете алг
« Ответ #13 : Февраль 22, 2012, 09:06:00 pm »
Вопрос о выборе тех или иных средств зависит от цели, которая должна быть достигнута. Как известно, цель может оправдывать средства, а может и... не оправдывать. Если цель написать небольшую (учебную, например) программу, то желательно использовать "стандартные" средства языка/среды разработки/ОС.
Как раз в учебных целях полезно изобретать велосипеды. В промышленном коде - только когда такая необходимость оправдана.
Изобретать велосипеды вообще полезно... Хорошая тренировка мышления, как такового.

Срок жизни таких программ, как правило, невелик и сопоставим со сроком жизни средств, которые используются. Если же речь идёт о создании большой системы/программного комплекса, то предпочтительнее подход с минимальным использованием "стандартных" средств, поскольку не исключено, что срок их жизни окажется короче не только срока жизни продукта, но... даже срока его создания.
С таким подходом - вам прямая дорога в оберон :) Делаем железку, делаем компилятор и вперед...
Проект оберона, по-моему мнению... самый неудачный. Для железки более удачной идеей может стать кросс-ассемблер.

На самом деле нет ничего страшного в смене стандартных средств - ну будет у вас часть продукта собираться древнючей дельфей, для действительно большой системы - не проблема. Ну, конечно, на заведомо однодневки ставить не стоит (я бы вот на дельфи и не поставил, борланд загибаться давно начал ;)
Видимо, у нас немного разные представления о средствах, видимо цели/задачи не очень похожи... Для меня смена средства (даже переход на новую версию) связана с проблемами. Пересобрать проект под новыми средствами может оказаться сравнимо с полным переписыванием, поскольку этого нет... а это не поддерживается... вместо того, есть вот это, а оно несовместимо с тем-то... и т.д. и т.п. Если речь об отдельных частностях, то с этим можно смириться, а если о ключевых моментах?..
Борланд был приличной командой, пока там был Филип Канн (Philip Kahn)... Он был не только основателем, но и душой фирмы.

Удобство... При создании небольшой программы можно не обращать внимания на незначительные неудобства использования "стандартных" средств (понятно же, что "тиражная" одежда редко хорошо сидит на фигуре конкретного человека), но если проект большой, то "маленькие" неудобства могут перерасти в большие проблемы. И здесь правильным будет решение о том, чтобы совсем отказаться от тех "стандартных" элементов, которые создают проблемы, написав вместо них свои элементы (алгоритмы, библиотеки, шаблоны, компоненты...). С учётом того, что было сказано ранее, такой проект можно  развивать и сопровождать дольше и с большими удобствами.
В идеале :) На практике квалификация создателей велосипедов оказывается ниже уровня создателей стандартных средств. Конечно они с этим никогда не согласятся, но это так :) Я уже не говорю про мелочи типа вовлечения новых людей в проект.
Так оно... но для того и существуют... "старшие товарищи". И хороший проект не должен сразу писаться в виде "чистовика", пару первых версий надо готовить для "её величества" корзины... А к третьей версии либо появляется опыт, либо исчезает... программист.

Эффективность... Применение "стандартных" библиотек даёт "стандартную" эффективность, которой... может оказаться недостаточно (в критических участках). Для примера стандартная подпрограмма/шаблон сортировки максимально дистанцирована от типа и порядка сортируемых данных, это обеспечивает ей широкое применение. И в простых случаях её производительности достаточно, но... для специфических данных (а, собственно, все реальные данные имеют некоторую специфику) "рукописная" сортировка может оказаться значительно эффективнее. Трудно ли написать свою сортировку (точнее сказать, свою разновидность сортировки)?.. Сортировка в среднем записывается в 20-30 строк... бинарный поиск в 5-10 строк.. Зная алгоритмы, их сильные и слабые стороны... толковому разработчику не потребуется много времени, чтобы написать свою разновидность алгоритмов, нацеленную на эффективную обработку специфических данных. И далее с учётом п.2 и п.1...
Ну вот я как раз сейчас занимаюсь оптимизацией (по скорости) некоторых мест в нашем продукте. Ни одной сортировки не пришлось переписать :) Вот выкинуть совсем сортировку и переписать алгоритм так, чтоб работало без сортировки - пришлось :) Короче, ни одного велосипеда еще не написал по ходу этой оптимизационной деятельности. Все сводится к анализу существующего кода (вот уж когда хочется, чтоб все было написано стандартно и просто), потом выкидывается/переписывается код типа "из пустого в порожнее". Кода становится меньше, работает быстрее. Местами, конечно, код становится несколько витиеватый и не такой прямолинейный - ставится коммент типа "заоптимизировано".
У каждого свои задачи и свои взгляды на них, и свои методы их решения... Повторю, что с моей точки зрения, "изобретение велосипедов" - полезное занятие... Пока не изобретёшь несколько "велосипедов"... вообще ничего путнего не изобретёшь.

valexey

  • Administrator
  • Hero Member
  • *****
  • Сообщений: 1990
    • Просмотр профиля
Re: Как часто и каким образом используете алг
« Ответ #14 : Февраль 22, 2012, 09:21:55 pm »
Велосипеды рулят. Рулят в том плане, что пока велосипед свой не построишь, так до конца и не поймешь как устроен велосипед стандартный, промышленный. Но при этом обычно выгодней ездить таки на промышленных велосипедах :-)
"но сейчас, чтобы компенсировать растущую мощность компьютеров, программисты используют фреймворки"