Сегодня узнал о том, что один преподаватель МГТУ им. Баумана имеет к STL достаточно негативное отношение. Мотивирует тем, что иногда программы с использованием STL ведут себя странно на больших объемах данных. Он приводил пример из жизни: студент выполнил курсовую, связанную с работой с БД на "живом" языке (или как оно называется) и при подключении больших словарей время работы стало экспоненциальным, хотя должно было быть линейным, что и наблюдалось на малых словарях. Так вот, потом для интереса переписали без STL, но с теми же алгоритмами — всё заработало.

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

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


NF>Возможно ли подобное?

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

NF>И как оно возможно?


Да, элементарно! Мало ли способов сделать программу тормозной!

NF>Сегодня узнал о том, что один преподаватель МГТУ им. Баумана имеет к STL достаточно негативное отношение.

Можно узнать, о каком именно преподавателе идет речь?

Я бы посоветовал не очень верить преподавателям нашего славного университета... за 6 курсов я видел только двух преподавателей (имеются в виду спецдисциплины), которые более-менее разбирались в преподаваемом предмете.

NoFate wrote:
> Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от
> преподавателей, но всё таки интересно мнение. Возможно ли подобное? И
> как оно возможно?
Элементарно, например если студент использовал std::list вместо
std::vector'а, или использовал метод size() из std::list.

Естественно, это примеры неправильного использования STL. В самой STL
мало чему тормозить — там используются годами проверенные алгоритмы для
списков, карт и векторов.

А теперь конкретней что, как, сколько ???

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

G>Все возможно . Хорошо бы саму прогу посмотреть, а то это получается разговор на тему "существует ли принципиальная возможность сделать так, чтоб некоторая гипотетическая программа на больших данных работала медленно".
G>Да, элементарно! Мало ли способов сделать программу тормозной!

Фишка была в том, что алгоритмы использовались, якобы, те же. Об этом я писал

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

av>Можно узнать, о каком именно преподавателе идет речь?
М-м-м =) Марков. ИУ-9

av>Я бы посоветовал не очень верить преподавателям нашего славного университета... за 6 курсов я видел только двух преподавателей (имеются в виду спецдисциплины), которые более-менее разбирались в преподаваемом предмете.
Да, для нашего славного ВУЗа это характерно...

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

NF>Сегодня узнал о том, что один преподаватель МГТУ им. Баумана имеет к STL достаточно негативное отношение. Мотивирует тем, что иногда программы с использованием STL ведут себя странно на больших объемах данных. Он приводил пример из жизни: студент выполнил курсовую, связанную с работой с БД на "живом" языке (или как оно называется) и при подключении больших словарей время работы стало экспоненциальным, хотя должно было быть линейным, что и наблюдалось на малых словарях. Так вот, потом для интереса переписали без STL, но с теми же алгоритмами — всё заработало.

Единорогам все равно верите ли вы в них или нет, так же как вам все равно, верят ли в вас единороги.

NF>Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от преподавателей, но всё таки интересно мнение. Возможно ли подобное? И как оно возможно?

Любой инструмент можно использовать не по назначению. Мало ли, что они там делали, какие предположения о временных сложностях и внутреннем устройстве делали, и как ровно использовали.

On Fri, 24 Feb 2006 18:02:40 +0200, NoFate <22574@users.rsdn.ru> wrote:

> Сегодня узнал о том, что один преподаватель МГТУ им. Баумана имеет к STL достаточно негативное отношение. Мотивирует тем, что иногда программы с использованием STL ведут себя странно на больших объемах данных. Он приводил пример из жизни: студент выполнил курсовую, связанную с работой с БД на "живом" языке (или как оно называется) и при подключении больших словарей время работы стало экспоненциальным, хотя должно было быть линейным, что и наблюдалось на малых словарях. Так вот, потом для интереса переписали без STL, но с теми же алгоритмами — всё заработало.
>
> Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от преподавателей, но всё таки интересно мнение. Возможно ли подобное? И как оно возможно?

возможно ли такое ? да очень просто:

берем вектор интов
std::vector<int> int_v;

и делаем следуещее

пример 1
for(int = i; i < 10000; ++i)
int_v.push_back(i);

пример 2
int_v.reserve(10000);
for(int = i; i < 10000; ++i)
int_v.push_back(i);

второй от первого отличаетса только одной строчкой кода,
но время виполнения у них будет раное, потому што в втором
варианте память выделяетса только раз, в то время как в первом,
ето будет сделано примерно 13~14 раз (если не ошибаюсь память в
stl выделяетса за принцыпом в 2-ва раза больше нежели просили,
хотя сам не проверял, тоесть логарифмическая зависмость) +
копирование, при необходимости, всех даних на новое место,
тепер прикиньте сколько біло лишних телодвижений ...

такшто использовиние библиотеки не освобождает от
использовоная головы

--
Andriy Ohorodnyk

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

C>NoFate wrote:
>> Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от
>> преподавателей, но всё таки интересно мнение. Возможно ли подобное? И
>> как оно возможно?
C>Элементарно, например если студент использовал std::list вместо
C>std::vector'а, или использовал метод size() из std::list.

Скорее всего использовал map так как для БД важно наличие ключа в таблице.

P.S. А что с size() в std::list — помоему оно не пересчитывает размер листа а является member-ом класса которое вычисляется по ходу дела + inline

On Fri, 24 Feb 2006 18:12:25 +0200, NoFate <22574@users.rsdn.ru> wrote:

> Здравствуйте, Glоbus, Вы писали:
>
> G>Все возможно . Хорошо бы саму прогу посмотреть, а то это получается разговор на тему "существует ли принципиальная возможность сделать так, чтоб некоторая гипотетическая программа на больших данных работала медленно".
> G>Да, элементарно! Мало ли способов сделать программу тормозной!
>
> Фишка была в том, что алгоритмы использовались, якобы, те же. Об этом я писал

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

--
Andriy Ohorodnyk

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

NF>Возможно ли подобное? И как оно возможно?

Кажется такие варианты возможны:
— алгоритмы были изменены / STL был использован неэффективно
— в некоторых оценках упоминается время в "среднем" и в "худшем" случае. Одно было выдано за другое (хотя разница до экспоненты врядли дойдет)
— сказался объем памяти (без STL как-то сэкономили), пошел своп

В общем без кода или хотя бы алгоритма и структур ничего не скажешь.

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

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

Т. е. написанное ручками эффективнее, чем STL-кие реализации? Субъективное мнение — это маловероятно.

andrij wrote:
> с етого можно сделать только один вывод — агоритмы тут нипричем.
> важна ефективность их реализации. конечно, когда переписивали
> ручками ть пришлось поработать головой и в следствии большая
> ефективность
В нормальных STL (Dinkumware, STLPort) достаточно хорошая реализация
стандартных алгоритмов. При их ручной реализации выигрыш будет на
проценты, а не в разы.

Может какой-то "эффект второго порядка" типа локальности кэша вмешался,
но это маловероятно.

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

C>В нормальных STL (Dinkumware, STLPort) достаточно хорошая реализация
C>стандартных алгоритмов. При их ручной реализации выигрыш будет на
C>проценты, а не в разы.

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

Здравствуйте, <Аноним>, Вы писали:

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

C>>NoFate wrote:
>>> Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от
>>> преподавателей, но всё таки интересно мнение. Возможно ли подобное? И
>>> как оно возможно?
C>>Элементарно, например если студент использовал std::list вместо
C>>std::vector'а, или использовал метод size() из std::list.

А>Скорее всего использовал map так как для БД важно наличие ключа в таблице.

А>P.S. А что с size() в std::list — помоему оно не пересчитывает размер листа а является member-ом класса которое вычисляется по ходу дела + inline

Сложность этой операции может быть O(n). Это не противоречит никаким требованиям стандарта. С линейной сложностью size можно реализовать list::splice со сложностью O(1). Если же сложность list::size — O(1), то list::splice будет работать соответственно за O(n). Разные разработчики STL жертвуют сложностью разных операций.

_DAle_ wrote:

> Сложность этой операции может быть O(n). Это не противоречит никаким
> требованиям стандарта. С линейной сложностью size можно реализовать
> list::splice со сложностью O(1). Если же сложность list::size — O(1), то
> list::splice будет работать соответственно за O(n). Разные разработчики
> STL жертвуют сложностью разных операций.
Насколько я помню, стандарт требует для операций size/begin/end всех контейнеров константную сложность.

Для "хитрых" контейнеров длина хранится в классе и обновляется при модификациях контейнера.

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

A>второй от первого отличаетса только одной строчкой кода,
A>но время виполнения у них будет раное, потому што в втором
A>варианте память выделяетса только раз, в то время как в первом,
A>ето будет сделано примерно 13~14 раз (если не ошибаюсь память в
A>stl выделяетса за принцыпом в 2-ва раза больше нежели просили,
A>хотя сам не проверял, тоесть логарифмическая зависмость) +
A>копирование, при необходимости, всех даних на новое место,
A>тепер прикиньте сколько біло лишних телодвижений ...

Размер выделенной памяти для вектора должен увеличиваться экспоненциально. Иначе сложности некоторых операций не будут соответствовать требованиям стандарта. А уже конкретная константа, на которую умножается размер, может быть различной. Может быть 5, может быть 0.1. В STLPort вроде бы 2, в какой-то реализации я видел 1.5.
(Кстати, переводчик русского третьего специального издания книги Строуструпа взял на себя смелость добавить собственное примечание о том, что обычно размер вектора увеличивается на константу. Лучше бы вообще ничего не писал.)

A>--
A>Andriy Ohorodnyk

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

_>_DAle_ wrote:

>> Сложность этой операции может быть O(n). Это не противоречит никаким
>> требованиям стандарта. С линейной сложностью size можно реализовать
>> list::splice со сложностью O(1). Если же сложность list::size — O(1), то
>> list::splice будет работать соответственно за O(n). Разные разработчики
>> STL жертвуют сложностью разных операций.
_>Насколько я помню, стандарт требует для операций size/begin/end всех контейнеров константную сложность.

_>Для "хитрых" контейнеров длина хранится в классе и обновляется при модификациях контейнера.

http://www.rsdn.ru/Forum/Message.aspx?mid=510567&amp;only=1

Автор: Павел Кузнецов
Дата: 19.01.04

Абсолютно так же можно утверждать,
что программы на С++ на больших объемах ведут себя странно и тормозят.
А что?
Программа была написана на С++? Да!
Тормозила? Еще как!
Вывод — С++ тормозной язык.

"NoFate" <22574@users.rsdn.ru> wrote in message
news:1697456@news.rsdn.ru...
From: NoFate nofatya.livejournal.com

Сегодня узнал о том, что один преподаватель МГТУ им. Баумана имеет к STL
достаточно негативное отношение. Мотивирует тем, что иногда программы с
использованием STL ведут себя странно на больших объемах данных. Он приводил
пример из жизни: студент выполнил курсовую, связанную с работой с БД на
"живом" языке (или как оно называется) и при подключении больших словарей
время работы стало экспоненциальным, хотя должно было быть линейным, что и
наблюдалось на малых словарях. Так вот, потом для интереса переписали без
STL, но с теми же алгоритмами — всё заработало.

Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от
преподавателей, но всё таки интересно мнение. Возможно ли подобное? И как
оно возможно?
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
STL (мнение преподавателя) Оценить


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

А вообще любопытно было бы узнать, о преподавателе какой дисциплины идет
речь? Не "охрана труда" случайно?

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

R>А вообще любопытно было бы узнать, о преподавателе какой дисциплины идет
R>речь? Не "охрана труда" случайно?

Базы данных, если не ошибаюсь

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

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

R>>А вообще любопытно было бы узнать, о преподавателе какой дисциплины идет
R>>речь? Не "охрана труда" случайно?

NF>Базы данных, если не ошибаюсь

Для этого есть СУБД, зачем еще stl там нужен?

Здравствуйте, <Аноним>, Вы писали:


NF>>Базы данных, если не ошибаюсь
А>Для этого есть СУБД, зачем еще stl там нужен?

Всё написано в корневом сообщении...

"Павел Кузнецов" <5834@users.rsdn.ru> wrote in message news:1697678@news.rsdn.ru...
>


теперь нормально?

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

DP>А теперь конкретней что, как, сколько ???

Значит ни чего конкретного ... просто захотелось мягко говоря по..говорить ...
У меня за много лет использования STL подобных проблем не было ...
но если все таки будет конкретный пример кода то я думаю можно будет сказать в чем проблема

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

NF>Сегодня узнал о том, что один преподаватель МГТУ им. Баумана имеет к STL достаточно негативное отношение. Мотивирует тем, что иногда программы с использованием STL ведут себя странно на больших объемах данных. Он приводил пример из жизни: студент выполнил курсовую, связанную с работой с БД на "живом" языке (или как оно называется) и при подключении больших словарей время работы стало экспоненциальным, хотя должно было быть линейным, что и наблюдалось на малых словарях. Так вот, потом для интереса переписали без STL, но с теми же алгоритмами — всё заработало.

NF>Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от преподавателей, но всё таки интересно мнение. Возможно ли подобное? И как оно возможно?



ИМХО Им просто обидно, что они в своё время писали всё это руками. Они не могут смириться, что сейчас программист может просто заюзать библиотечный класс. За такими дешёвыми наездами на стандартную библиотеку — толи желание самому подняться, толи не знаю ещё что. В общем — не уважение преподу. Единственная поблажка ему может быть сделана за старость.
Тяжёлое детство — велосипедный спорт
Надеюсь никто из доверчивых студентов не повёлся на такие тупые разводы.

Более печально, что и среди профессиональных программистов, которые начинали писать ещё лет 10 назад тоже такие встречаются...

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


DP>Значит ни чего конкретного ... просто захотелось мягко говоря по..говорить ...
DP>У меня за много лет использования STL подобных проблем не было ...
DP>но если все таки будет конкретный пример кода то я думаю можно будет сказать в чем проблема

Не могу сказать, что за много лет, но таких проблем не возникало и у меня. Примера действительно нет =) Не давал...

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

Здравствуйте, NoFate, Вы писали:
NF>Т. е. написанное ручками эффективнее, чем STL-кие реализации? Субъективное мнение — это маловероятно.
Для конкретной задачи ты скорее всего сможешь написать более эффективный контейнер

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

NF>Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от преподавателей, но всё таки интересно мнение. Возможно ли подобное? И как оно возможно?

бывает. из опыта: чаще всего это происходит с операциями new-delete.
то с чем сталкивался на MS visualC++:
1) вина программиста
map — большое число маленьких объектов. заполнение быстое, удаление всех (т.е. clear()) при 10000 объектах — задумывалась на несколько секунд. помог boost с его аллокаторами. Этот случай нельзя отнести к серьезным недостаткам реализации т.к. new-delete не оптимизированы для малых объектов и это нужно помнить.
2) вина реализации
deque. около 10000000 (или около того) push-back'ов затем полное удаление. в VC2003 проходит без проблем в VC2005 не дождался окончания (не помню точно на удалении или вставке). вектор летает.
---
Вывод:
1) сама по себе stl не может быть тормозной т.к. это только спецификация интерфейса библиотеки и некоторых особенностей ее работы
2) иногда проблемы с реализацией stl иногда с использованием. Лучше всего использовать одну реализацию (например stlport) поведение которой изучено чтобы не получать непронятное поведение при смене версии компилятора
3) действительно иногда самописный вариант работает быстрее, но сначала нужно изучить все, что предоставляет stl и особенности использования, и если стало очевидно, что выше скорости не добится, стоит подумать о велосипеде

В старой версии g++ кажется 2.95 в алгоритме sort была ошибка, которая проявлялась как раз на больших данных. Пришлось sort заменить на stable_sort.

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

NF>Сегодня узнал о том, что один преподаватель МГТУ им. Баумана имеет к STL достаточно негативное отношение. Мотивирует тем, что иногда программы с использованием STL ведут себя странно на больших объемах данных. Он приводил пример из жизни: студент выполнил курсовую, связанную с работой с БД на "живом" языке (или как оно называется) и при подключении больших словарей время работы стало экспоненциальным, хотя должно было быть линейным, что и наблюдалось на малых словарях. Так вот, потом для интереса переписали без STL, но с теми же алгоритмами — всё заработало.

NF>Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от преподавателей, но всё таки интересно мнение. Возможно ли подобное? И как оно возможно?

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

1) Все зависит от платформы, например, в последних библиотеках Линуксячьих граммотный маллок с кешем малых объектов. STLport тоже имеет аналогичный кеш
2) Еще раз соглашусь. См. мой пост выше. Баги в реализациях STL бывают.

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

NF>>Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от преподавателей, но всё таки интересно мнение. Возможно ли подобное? И как оно возможно?

WA>бывает. из опыта: чаще всего это происходит с операциями new-delete.
WA>то с чем сталкивался на MS visualC++:
WA>1) вина программиста
WA>map — большое число маленьких объектов. заполнение быстое, удаление всех (т.е. clear()) при 10000 объектах — задумывалась на несколько секунд. помог boost с его аллокаторами. Этот случай нельзя отнести к серьезным недостаткам реализации т.к. new-delete не оптимизированы для малых объектов и это нужно помнить.
WA>2) вина реализации

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

A>пример 2
A>int_v.reserve(10000);
A>for(int = i; i < 10000; ++i)
A> int_v.push_back(i);

A>такшто использовиние библиотеки не освобождает от
A>использовоная головы

Так это и есть "странное" поведение. Лектор прав.

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

B>Абсолютно так же можно утверждать,
B>что программы на С++ на больших объемах ведут себя странно и тормозят.
B>А что?
B>Программа была написана на С++? Да!
B>Тормозила? Еще как!
B>Вывод — С++ тормозной язык.

Перепиши программу на Perl.

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

NF>Сегодня узнал о том, что один преподаватель МГТУ им. Баумана имеет к STL достаточно негативное отношение.

вот ещё один случай: http://www.rsdn.ru/Forum/?mid=1189102

Автор: McSeem2
Дата: 25.05.05

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

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

av>>Можно узнать, о каком именно преподавателе идет речь?
NF>М-м-м =) Марков. ИУ-9

av>>Я бы посоветовал не очень верить преподавателям нашего славного университета... за 6 курсов я видел только двух преподавателей (имеются в виду спецдисциплины), которые более-менее разбирались в преподаваемом предмете.
NF>Да, для нашего славного ВУЗа это характерно...

Характерно не только для вашего ВУЗа. У нас не лучше, за все предметы не ручаюсь, говорю именно о тех, что касаются программирования. Преподаватели на нашей кафедре повергают меня в тоску и уныние. Бесполезно, что-то спрашивать и боже упаси сказать, что я программист, могут потом все нервы вытрясти. Докапываться до ерунды.

Я думаю преподаватель с негативным отношением к STL, просто её плохо знает и никогда не участвовал в разработке больших проектов.

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

NF>Сегодня узнал о том, что один преподаватель МГТУ им. Баумана имеет к STL достаточно негативное отношение. Мотивирует тем, что иногда программы с использованием STL ведут себя странно на больших объемах данных. Он приводил пример из жизни: студент выполнил курсовую, связанную с работой с БД на "живом" языке (или как оно называется) и при подключении больших словарей время работы стало экспоненциальным, хотя должно было быть линейным, что и наблюдалось на малых словарях. Так вот, потом для интереса переписали без STL, но с теми же алгоритмами — всё заработало.

NF>Я, в общем-то, не очень верю подобным рассказам пусть даже идут они от преподавателей, но всё таки интересно мнение. Возможно ли подобное? И как оно возможно?

Может просто он скомпилировал в Debug?
У меня такое было — STL vector в VisualC++ 6.0 в Debug Mode был медленнее самого себя в
Release Mode в ДЕСЯТКИ раз. Из-за того что очень много вызовов функций,
которые в Release разворачиваются в inline.