Здравствуйте, minorlogic, Вы писали:
M>Сортировку логично использовать стандартную , и уж точно в коде не должна появляться пузырьковая по определению.
Ух какая уверенность в себе! Мне б такую.
По делу: пузырек в случае почти отсортированных данных рвет qsort по производительности. Учите матчасть.
... << RSDN@Home 1.2.0 alpha rev. 677>>
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[3]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, jazzer, Вы писали:
J>если тормоза уже заметны, то, очевидно, это уже не преждевременная оптимизация
Осталось ответить на вопрос — как они заметны? "На глазок"? Многоопытным взглядом ищем вложенные циклы и начинаем костерить ламеров писавших код за квардатичные алгоритмы? Если так — это и есть преждевременная оптимизация.
Браться что-то оптимизировать стоит только после того, как:
1. Был запущен профайлер, причем очень желательны данные приблеженные к реальным.
2. Были найдены проблемные места.
"На глазок" видны только самые очевидные места, те самые 3% о которых говорится в оригинальной цитате. Их можно исправить сразу. Но опять же ключевое слово "можно". Если уж браться за оптимизацию серьезно — то и очевидные места тоже надо профайлить. Особенно в сравнении с другими проблемными местами и опять же желательно на реальных данных.
Re: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, Аноним, Вы писали:
А>Ведь оптимизация может привести к переписыванию много чего и даже в рамках одного модуля или класса. Какой смысл в этой фразе?
А>И реальная ситуация — есть какой-то проект который должен делать что-то. Сейчас сделана четверть нужной функциональности, но уже заметгны тормоза. Судя по этой фразе — на оптимизацию пока надо забить, но ведь тогда может оказаться, что в конце будет такая ж..а, что на это никто сомтреть не станет
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, minorlogic, Вы писали:
M>>Сортировку логично использовать стандартную , и уж точно в коде не должна появляться пузырьковая по определению. S>Ух какая уверенность в себе! Мне б такую. S>По делу: пузырек в случае почти отсортированных данных рвет qsort по производительности. Учите матчасть.
Хорошо, давайте учить матчасть:
#define _SECURE_SCL 0
#define _SECURE_SCL_THROWS 0
#include <iostream>
#include <algorithm>
#include <vector>
#include <iomanip>
using namespace std;
#include <boost/timer.hpp>
using boost::timer;
template< typename Func, typename Cont >
double sort_timing( Cont c, Func f )
{
timer t1;
f( c.begin(), c.end() );
return t1.elapsed();
}
#include <boost/random/uniform_int.hpp>
#include <boost/random/variate_generator.hpp>
#include <boost/random/mersenne_twister.hpp>
template< typename Dist, typename Cont, typename Arg >
Cont generate_random( typename Cont::size_type size, Arg arg1, Arg arg2 )
{
static boost::mt11213b gen( std::time(0) );
boost::variate_generator< boost::mt11213b&, Dist > rand_gen( gen, Dist( arg1, arg2 ) );
Cont c;
generate_n( back_inserter( c ), size, rand_gen );
return c;
}
template< typename Cont >
Cont& make_almost_sorted( Cont& cont, double swap_percent )
{
sort( cont.begin(), cont.end() );
using namespace boost;
static mt11213b gen( std::time(0) );
variate_generator< mt11213b&, uniform_int<> > rand_gen( gen, uniform_int<>( 0, cont.size() - 1 ) );
for ( int i = 0, N = swap_percent * cont.size() / 2; i < N; ++i )
swap( cont[ rand_gen() ], cont[ rand_gen() ] );
return cont;
}
template<class Iterator>
void insertion_sort( Iterator First, Iterator Last )
{
for( Iterator i = First; i < Last; ++i )
for( Iterator j = i; First < j && *j < *(j - 1); --j )
std::iter_swap( (j - 1), j );
}
template<class Iterator>
void bubble_sort( Iterator First, Iterator Last )
{
while( First < --Last )
for( Iterator i = First; i < Last; ++i )
if ( *i > *(i + 1) )
std::iter_swap( (i + 1), i );
}
template<class Iterator>
void selection_sort( Iterator First, Iterator Last )
{
for( ; First < Last; ++First )
{
Iterator min = First;
for( Iterator i = First; i < Last; ++i )
if ( *i < *min )
min = i;
std::iter_swap( First, min );
}
}
template<class Iterator>
void heap_sort( Iterator First, Iterator Last )
{
partial_sort( First, Last, Last );
}
int main()
{
typedef std::vector< int > vt;
typedef void (*SORT_FUNC)( vt::iterator, vt::iterator );
struct Func { SORT_FUNC func; const char* name; };
Func sort_functions[] =
{
{ &sort< vt::iterator >, "std::sort" }
, { &stable_sort< vt::iterator >, "merge_sort" }
, { &heap_sort< vt::iterator >, "heap_sort" }
, { &insertion_sort< vt::iterator >, "insertion_sort" }
, { &bubble_sort< vt::iterator >, "bubble_sort" }
, { &selection_sort< vt::iterator >, "selection_sort" }
};
const double pc_min = 0.001, pc_max = 0.1, pc_step = 10;
for( double i = pc_min; i <= pc_max; i *= pc_step )
{
cout << "Sort an almost sorted vector with " << 100*i << "% exchanged elements\n";
cout << setw(8) << left << "size";
for ( int fn = 0; fn < sizeof(sort_functions)/sizeof(Func); ++fn )
std::cout << setw(16) << left << sort_functions[fn].name;
cout << endl;
const int min = 16000, max = 128000, step = 2;
for( vt::size_type n = min; n <= max; n *= step )
{
cout << setw(8) << left << n;
vt cont = generate_random< boost::uniform_int<>, vt, int >( n, 0, INT_MAX );
make_almost_sorted( cont, i );
for ( int fn = 0; fn < sizeof(sort_functions)/sizeof(Func); ++fn )
std::cout << setw(16) << left << sort_timing( cont, sort_functions[fn].func );
cout << endl;
}
cout << endl;
}
}
Здравствуйте, skeptik_, Вы писали:
M>>>Сортировку логично использовать стандартную , и уж точно в коде не должна появляться пузырьковая по определению. S>>Ух какая уверенность в себе! Мне б такую. S>>По делу: пузырек в случае почти отсортированных данных рвет qsort по производительности. Учите матчасть.
_>Хорошо, давайте учить матчасть: _>... _>Вывод: пузырьку в коду делать нечего. Без исключений.
С каких пор изучение матчасти заключается в написании тонны сомнительного кода, из которого потом делаются такие далеко идущие выводы? Кормана лучше почитайте.
Re[5]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, skeptik_, Вы писали:
_>Здравствуйте, Sinclair, Вы писали:
S>>Здравствуйте, minorlogic, Вы писали:
M>>>Сортировку логично использовать стандартную , и уж точно в коде не должна появляться пузырьковая по определению. S>>Ух какая уверенность в себе! Мне б такую. S>>По делу: пузырек в случае почти отсортированных данных рвет qsort по производительности. Учите матчасть.
_>Хорошо, давайте учить матчасть: _>[ccode]
_>Вывод: пузырьку в коду делать нечего. Без исключений.
У меня был реальный случай, когда я без зазрения совести не взял qsort из стандартной библтотеки, а реализовал сортировку пузырьком: было известно, что в более 90% случаев данные отсортированы, а в оставшихся случаях имеют 2 неотсортированных элемента и, кроме того, менять местами равные элементы было нельзя. Естественно это решение в коде я прокомментировал.
Re[6]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, anton_t, Вы писали:
_>Здравствуйте, skeptik_, Вы писали:
_>>Здравствуйте, Sinclair, Вы писали:
S>>>Здравствуйте, minorlogic, Вы писали:
M>>>>Сортировку логично использовать стандартную , и уж точно в коде не должна появляться пузырьковая по определению. S>>>Ух какая уверенность в себе! Мне б такую. S>>>По делу: пузырек в случае почти отсортированных данных рвет qsort по производительности. Учите матчасть.
_>>Хорошо, давайте учить матчасть: _>>[ccode]
_>>Вывод: пузырьку в коду делать нечего. Без исключений.
_>У меня был реальный случай, когда я без зазрения совести не взял qsort из стандартной библтотеки, а реализовал сортировку пузырьком: было известно, что в более 90% случаев данные отсортированы, а в оставшихся случаях имеют 2 неотсортированных элемента и, кроме того, менять местами равные элементы было нельзя. Естественно это решение в коде я прокомментировал.
В этом случае лучшим решением была бы сортировка вставками, а не пузырёк.
А>>...(поменять сортировки пузырьком на qsort...
E>IMHO от сортировки пузырьком следует отказаться раз и навсегда...
У пузырька есть свои плюсы:
1) простота/надёжность (безошибочно написать по памяти qsort с первой попытки — задача не тривиальная)
2) устойчивость (qsort не обладает этим качеством)
Так что при небольшом числе элементов сортировка пузырьком вполне имеет право на жизнь
E>Вообще, можно завсети правило, что использование квадратичных и более медленных алгоритмов требует обоснования...
Как уже писали, у qsort в худшем случае может вылезти O(n^2), поэтому в критических приложениях (медицина, транспорт, системы реального времени) использование qsort может оказаться недопустимым, т.е. придётся искать более стабильные по ресурсам алгоритмы.
Re[3]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, minorlogic, Вы писали:
M>Сортировку логично использовать стандартную , и уж точно в коде не должна появляться пузырьковая по определению.
Стандартную — это какую?
Совсем недавно мне надо было сортировать массив, содержащий от 4 до 15 элементов, и сортировка вызывается раз в пару часов. Что здесь логичнее всего применить?
Re[4]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, Privalov, Вы писали:
P>Здравствуйте, minorlogic, Вы писали:
M>>Сортировку логично использовать стандартную , и уж точно в коде не должна появляться пузырьковая по определению.
P>Стандартную — это какую?
P>Совсем недавно мне надо было сортировать массив, содержащий от 4 до 15 элементов, и сортировка вызывается раз в пару часов. Что здесь логичнее всего применить?
Стандартную , это потдерживаемую языком/фреймворком, библиотеками. Вручную написанную сортировку я бы мог понять если требуется жесткая специфическая оптимизация(но тогда уже речь идет о днях проведенных в профайлере ).
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[7]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, skeptik_, Вы писали:
_>Здравствуйте, anton_t, Вы писали:
_>>Здравствуйте, skeptik_, Вы писали:
_>>>Здравствуйте, Sinclair, Вы писали:
S>>>>Здравствуйте, minorlogic, Вы писали:
M>>>>>Сортировку логично использовать стандартную , и уж точно в коде не должна появляться пузырьковая по определению. S>>>>Ух какая уверенность в себе! Мне б такую. S>>>>По делу: пузырек в случае почти отсортированных данных рвет qsort по производительности. Учите матчасть.
_>>>Хорошо, давайте учить матчасть: _>>>[ccode]
_>>>Вывод: пузырьку в коду делать нечего. Без исключений.
_>>У меня был реальный случай, когда я без зазрения совести не взял qsort из стандартной библтотеки, а реализовал сортировку пузырьком: было известно, что в более 90% случаев данные отсортированы, а в оставшихся случаях имеют 2 неотсортированных элемента и, кроме того, менять местами равные элементы было нельзя. Естественно это решение в коде я прокомментировал.
_>В этом случае лучшим решением была бы сортировка вставками, а не пузырёк.
И на сколько лучшим?
Re[5]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, skeptik_, Вы писали:
_>Хорошо, давайте учить матчасть: _>
_>template<class Iterator>
_>void bubble_sort( Iterator First, Iterator Last )
_>{
_> while( First < --Last )
_> for( Iterator i = First; i < Last; ++i )
_> if ( *i > *(i + 1) )
_> std::iter_swap( (i + 1), i );
_>}
_>
Если я не ошибаюсь, в сортировке пузырьком есть простая оптимизация -- если на очередной итерации не было ни одной перестановки, то дальнейшие действия не выполняются. Пусть меня поправят, если я не прав. Но, если я прав, то данная реализация метода пузырька весьма не оптимальна.
SObjectizer: <микро>Агентно-ориентированное программирование на C++.
Здравствуйте, andy1618, Вы писали: A>У пузырька есть свои плюсы: A>безошибочно написать по памяти qsort с первой попытки — задача не тривиальная
вы считаете частой задачей написание собственных велосипедов?
Re[8]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, anton_t, Вы писали:
_>>>>Вывод: пузырьку в коду делать нечего. Без исключений.
_>>>У меня был реальный случай, когда я без зазрения совести не взял qsort из стандартной библтотеки, а реализовал сортировку пузырьком: было известно, что в более 90% случаев данные отсортированы, а в оставшихся случаях имеют 2 неотсортированных элемента и, кроме того, менять местами равные элементы было нельзя. Естественно это решение в коде я прокомментировал.
_>>В этом случае лучшим решением была бы сортировка вставками, а не пузырёк.
_>И на сколько лучшим?
Это прекрасно видно из моего кода и результатов. Сортировка вставками быстрее (в несколько раз на случайных данных, на порядок при почти отсортированных) и проще в имплементации (3 строки против 4).
Re[6]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, eao197, Вы писали:
E>Здравствуйте, skeptik_, Вы писали:
_>>Хорошо, давайте учить матчасть: _>>
_>>template<class Iterator>
_>>void bubble_sort( Iterator First, Iterator Last )
_>>{
_>> while( First < --Last )
_>> for( Iterator i = First; i < Last; ++i )
_>> if ( *i > *(i + 1) )
_>> std::iter_swap( (i + 1), i );
_>>}
_>>
E>Если я не ошибаюсь, в сортировке пузырьком есть простая оптимизация -- если на очередной итерации не было ни одной перестановки, то дальнейшие действия не выполняются. Пусть меня поправят, если я не прав. Но, если я прав, то данная реализация метода пузырька весьма не оптимальна.
Она мне известна, но она почти ничего не даёт:
template< typename Iterator >
void bubble_sort1( Iterator First, Iterator Last )
{
bool test = true;
for( --Last; First < Last && test; --Last )
{
test = false;
for( Iterator j = First; j < Last; ++j )
if( *(j + 1) < *j )
std::iter_swap( j, j + 1 ), test = true;
}
}
Результат:
Sort an almost sorted vector with 0.1% exchanged elements
size std::sort insertion_sort bubble_sort bubble_sort1
4000 0 0 0.031 0.015
8000 0 0 0.079 0.046
16000 0 0 0.172 0.157
32000 0 0 0.687 0.594
64000 0 0.016 2.719 2.625
Sort an almost sorted vector with 1% exchanged elements
size std::sort insertion_sort bubble_sort bubble_sort1
4000 0 0 0 0.016
8000 0 0 0.047 0.047
16000 0 0.015 0.172 0.188
32000 0 0.015 0.719 0.719
64000 0.016 0.031 2.875 2.844
Sort an almost sorted vector with 10% exchanged elements
size std::sort insertion_sort bubble_sort bubble_sort1
4000 0 0.015 0.016 0.015
8000 0 0 0.063 0.062
16000 0 0.016 0.265 0.25
32000 0 0.078 1.047 1.031
64000 0 0.359 4.141 4.094
Sort an almost sorted vector with 100% exchanged elements
size std::sort insertion_sort bubble_sort bubble_sort1
4000 0 0.015 0.031 0.047
8000 0 0.032 0.156 0.14
16000 0 0.125 0.594 0.594
32000 0 0.5 2.406 2.422
64000 0 2.031 9.828 9.75
Кнут кстати тоже пишет, что у пузырька нет никаких преимуществ, чтобы найти хоть какой-нибудь сценарий применения.
Re[5]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, skeptik_, Вы писали:
_>Здравствуйте, Sinclair, Вы писали:
S>>Здравствуйте, minorlogic, Вы писали:
M>>>Сортировку логично использовать стандартную , и уж точно в коде не должна появляться пузырьковая по определению. S>>Ух какая уверенность в себе! Мне б такую. S>>По делу: пузырек в случае почти отсортированных данных рвет qsort по производительности. Учите матчасть.
_>Хорошо, давайте учить матчасть:
PS Ну и на тот случай, если кто-нибудь возразит, что std::sort это не qsort:
время выполнения фунции соизмеримо со временем ее вызова, тем не менее, на некторых тестах различе в скоростях проявляется.
замечу, что на других аппаратных платформах (C64 или Mega168, к примеру) преимущество пузырька гораздо выше.
Здравствуйте, _FRED_, Вы писали:
_FR>Здравствуйте, Erop, Вы писали:
А>>>...(поменять сортировки пузырьком на qsort... E>>IMHO от сортировки пузырьком следует отказаться раз и навсегда... E>>Вообще, можно завсети правило, что использование квадратичных и более медленных алгоритмов требует обоснования...
_FR>Не раз видел, когда при необходимости всего-то найти пересечение двух множеств (заданных массивом\IList\IEnumerable, не важно) делался foreach по одному списку, а внутри него — по другому И на все пожелания сделать правильно отвечалось, что "нечего преждевременной оптимизацией заниматься", тогда как дело попросту в незнании более эффективных алгоритмов (что, к счастью, поправимо) и нежелании их узнать (с чем уже ничего не поделать)
а правильно это как? что может быть быстрее на неотсортированной коллекции
А ну да, ну да, на 8 элементах. Это конечно потрясающий результат, на векторе из 8 элементов выиграть 8 наносекунд. Из-за этого конечно надо имплементировать пузырёк.
Я изменил свой тест, так что для сортировки передаётся вектор с миллионом сортируемых векторов, замер времени изменил на QueryPerformanceCounter:
Итог: сортировку вставками пузырёк не бьёт. Стандартную он бьёт только на отсортированных данных до примерно двух десятков элементов. В итоге я всё ещё не вижу, где бы был применим пузырёк. insertion sort допустим можно запустить на маленьких и/или отсортированных данных, а пузырёк нафиг не нужен.