Сегодня узнал о том, что один преподаватель МГТУ им. Баумана имеет к 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

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