Здравствуйте, skeptik_, Вы писали:
_>А ну да, ну да, на 8 элементах. Это конечно потрясающий результат, на векторе из 8 элементов выиграть 8 наносекунд. Из-за этого конечно надо имплементировать пузырёк.
8 наносекунд — это сферический конь в вакууме. попробуйте запустить этот тест на 20MHz risc-процессоре и посчитайте разницу во времени
ваши громкие крики относятся к конкретной области применения данного алгоритма и некорректны в общем случае.
Здравствуйте, vayerx, Вы писали:
V>Здравствуйте, skeptik_, Вы писали:
_>>А ну да, ну да, на 8 элементах. Это конечно потрясающий результат, на векторе из 8 элементов выиграть 8 наносекунд. Из-за этого конечно надо имплементировать пузырёк. V>8 наносекунд — это сферический конь в вакууме. попробуйте запустить этот тест на 20MHz risc-процессоре и посчитайте разницу во времени V>ваши громкие крики относятся к конкретной области применения данного алгоритма и некорректны в общем случае.
Я повторюсь — сортировку вставками пузырёк не бьёт.
Здравствуйте, andy1618, Вы писали:
A>У пузырька есть свои плюсы:
У пузырька только один плюс — запоминающееся название.
A>1) простота/надёжность (безошибочно написать по памяти qsort с первой попытки — задача не тривиальная)
Сортировка вставками или выбором гораздо проще и понятнее.
Здравствуйте, skeptik_, Вы писали:
_>Здравствуйте, vayerx, Вы писали: V>>8 наносекунд — это сферический конь в вакууме. попробуйте запустить этот тест на 20MHz risc-процессоре и посчитайте разницу во времени V>>ваши громкие крики относятся к конкретной области применения данного алгоритма и некорректны в общем случае. _>Я повторюсь — сортировку вставками пузырёк не бьёт.
Sort an almost sorted vector with 10% exchanged elements
size std::sort merge_sort heap_sort insertion_sort bubble_sort selection_sort
8 0.226562 1.03906 0.6875 0.09375 0.078125 0.4375
16 0.351562 2.00781 1.45312 0.117188 0.117188 1.14062
Sort an almost sorted vector with 25% exchanged elements
size std::sort merge_sort heap_sort insertion_sort bubble_sort selection_sort
4 0.171875 0.945312 0.34375 0.078125 0.0703125 0.140625
8 0.226562 1.03906 0.6875 0.0859375 0.078125 0.4375
Здравствуйте, vayerx, Вы писали:
V>Здравствуйте, skeptik_, Вы писали:
_>>Здравствуйте, vayerx, Вы писали: V>>>8 наносекунд — это сферический конь в вакууме. попробуйте запустить этот тест на 20MHz risc-процессоре и посчитайте разницу во времени V>>>ваши громкие крики относятся к конкретной области применения данного алгоритма и некорректны в общем случае. _>>Я повторюсь — сортировку вставками пузырёк не бьёт.
V>
V>Sort an almost sorted vector with 10% exchanged elements
V>size std::sort merge_sort heap_sort insertion_sort bubble_sort selection_sort
V>8 0.226562 1.03906 0.6875 0.09375 0.078125 0.4375
V>16 0.351562 2.00781 1.45312 0.117188 0.117188 1.14062
V>Sort an almost sorted vector with 25% exchanged elements
V>size std::sort merge_sort heap_sort insertion_sort bubble_sort selection_sort
V>4 0.171875 0.945312 0.34375 0.078125 0.0703125 0.140625
V>8 0.226562 1.03906 0.6875 0.0859375 0.078125 0.4375
V>
Вообще говоря таймер у Вас похоже не самый точный, это видно из повторяющихся значений в разных колонках. В таких условиях обуждать 8 миллисекунд нет смысла. Кроме того, обмен здесь есть только в последней строке. В остальных случаях мы имеем дело с полностью отсортированным вектором. А вот у меня с точным таймером (QueryPerformanceCounter) пузырёк проигрывает вставкам.
Здравствуйте, andy1618, Вы писали:
А>>>...(поменять сортировки пузырьком на qsort...
E>>IMHO от сортировки пузырьком следует отказаться раз и навсегда... A>У пузырька есть свои плюсы: A>1) простота/надёжность (безошибочно написать по памяти qsort с первой попытки — задача не тривиальная) A>2) устойчивость (qsort не обладает этим качеством) A>Так что при небольшом числе элементов сортировка пузырьком вполне имеет право на жизнь
Не в тему, но.. всегда интересовало, почему в качестве самой простой (ну или первой в книге) сортировки приводят bubble sort. IMHO, не знающему алгоритмов сортировки школьнику придет в голову скорее алгоритм: находим минимум, меняем с первым, и т.д. Обычный selection sort, простой как топор, еще и эффективнее, чем пузырек.
Здравствуйте, _DAle_, Вы писали:
_DA>Не в тему, но.. всегда интересовало, почему в качестве самой простой (ну или первой в книге) сортировки приводят bubble sort. IMHO, не знающему алгоритмов сортировки школьнику придет в голову скорее алгоритм: находим минимум, меняем с первым, и т.д. Обычный selection sort, простой как топор, еще и эффективнее, чем пузырек.
Сортировка вставками тоже весьма интуитивна, так народ обычно карты на руках сортирует.
Re[9]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, skeptik_, Вы писали:
_>Здравствуйте, anton_t, Вы писали:
_>>>>>Вывод: пузырьку в коду делать нечего. Без исключений.
_>>>>У меня был реальный случай, когда я без зазрения совести не взял qsort из стандартной библтотеки, а реализовал сортировку пузырьком: было известно, что в более 90% случаев данные отсортированы, а в оставшихся случаях имеют 2 неотсортированных элемента и, кроме того, менять местами равные элементы было нельзя. Естественно это решение в коде я прокомментировал.
_>>>В этом случае лучшим решением была бы сортировка вставками, а не пузырёк.
_>>И на сколько лучшим?
_>Это прекрасно видно из моего кода и результатов. Сортировка вставками быстрее (в несколько раз на случайных данных, на порядок при почти отсортированных) и проще в имплементации (3 строки против 4).
В коде и результатах нет случая, когда данные отсортированы, поэтому ничего не видно.
Re[10]: Почему преждевременная оптимизация - корень всех зол
Здравствуйте, anton_t, Вы писали:
_>Здравствуйте, skeptik_, Вы писали:
_>>Здравствуйте, anton_t, Вы писали:
_>>>>>>Вывод: пузырьку в коду делать нечего. Без исключений.
_>>>>>У меня был реальный случай, когда я без зазрения совести не взял qsort из стандартной библтотеки, а реализовал сортировку пузырьком: было известно, что в более 90% случаев данные отсортированы, а в оставшихся случаях имеют 2 неотсортированных элемента и, кроме того, менять местами равные элементы было нельзя. Естественно это решение в коде я прокомментировал.
_>>>>В этом случае лучшим решением была бы сортировка вставками, а не пузырёк.
_>>>И на сколько лучшим?
_>>Это прекрасно видно из моего кода и результатов. Сортировка вставками быстрее (в несколько раз на случайных данных, на порядок при почти отсортированных) и проще в имплементации (3 строки против 4).
_>В коде и результатах нет случая, когда данные отсортированы, поэтому ничего не видно.
Да, и добавлю, что данные представляли из себя много массивов длинной в 99% случаев не больше сотни элементов, в остальных случаях ну максимум пара тысяч, а в случае 64-х элементов, как я вижу, разница при 1% не сортированных элементов считанные проценты. Так что я пока остаюсь при мнении, что пузырёк был верным решением.
Здравствуйте, skeptik_, Вы писали: _>Здравствуйте, _DAle_, Вы писали:
_DA>>Не в тему, но.. всегда интересовало, почему в качестве самой простой (ну или первой в книге) сортировки приводят bubble sort. IMHO, не знающему алгоритмов сортировки школьнику придет в голову скорее алгоритм: находим минимум, меняем с первым, и т.д. Обычный selection sort, простой как топор, еще и эффективнее, чем пузырек.
Selection sort на многих тестах проигрывает — см. ссылку внизу (если, конечно, там с реализацией не накосячили)
_>Сортировка вставками тоже весьма интуитивна, так народ обычно карты на руках сортирует.
Мда, почитал тут Википедию:
Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm, or a sorting algorithm, to introductory computer science students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught.[1]
The Jargon file, which famously calls bogosort "the archetypical perversely awful algorithm", also calls bubble sort "the generic bad algorithm".[2] Donald Knuth, in his famous The Art of Computer Programming, concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems", some of which he discusses therein.
Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case, but the two algorithms differ greatly in the number of swaps necessary. Experimental results such as those of Astrachan have also shown that insertion sort performs considerably better even on random lists. For these reasons many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort.
V>Здравствуйте, andy1618, Вы писали: A>>У пузырька есть свои плюсы: A>>безошибочно написать по памяти qsort с первой попытки — задача не тривиальная V>вы считаете частой задачей написание собственных велосипедов?
Зависит от платформы — иногда в базовой поставке готовые велосипеды отсутствуют. А бывает и другая крайность — что проще наваять свой дизайнерский велик, чем разгребать огромные залежи готовых велосипедов, самокатов и веломобилей
Но, в целом, согласен — частой эту задачу не назовёшь.
Недавно, кстати, видел пузырьковую сортировку в топовых решениях в турнире Google Code Jam
Здравствуйте, andy1618, Вы писали:
A>Здравствуйте, skeptik_, Вы писали: _>>Здравствуйте, _DAle_, Вы писали:
_DA>>>Не в тему, но.. всегда интересовало, почему в качестве самой простой (ну или первой в книге) сортировки приводят bubble sort. IMHO, не знающему алгоритмов сортировки школьнику придет в голову скорее алгоритм: находим минимум, меняем с первым, и т.д. Обычный selection sort, простой как топор, еще и эффективнее, чем пузырек.
A>Selection sort на многих тестах проигрывает — см. ссылку внизу (если, конечно, там с реализацией не накосячили)
Я про разную асимптотику в количестве свопов.
Re[10]: Почему преждевременная оптимизация - корень всех зол
Здравствуйте, anton_t, Вы писали:
_>>>>>У меня был реальный случай, когда я без зазрения совести не взял qsort из стандартной библтотеки, а реализовал сортировку пузырьком: было известно, что в более 90% случаев данные отсортированы, а в оставшихся случаях имеют 2 неотсортированных элемента и, кроме того, менять местами равные элементы было нельзя. Естественно это решение в коде я прокомментировал.
_>>>>В этом случае лучшим решением была бы сортировка вставками, а не пузырёк.
_>>>И на сколько лучшим?
_>>Это прекрасно видно из моего кода и результатов. Сортировка вставками быстрее (в несколько раз на случайных данных, на порядок при почти отсортированных) и проще в имплементации (3 строки против 4).
_>В коде и результатах нет случая, когда данные отсортированы, поэтому ничего не видно.
Там есть случай, когда в отсортированном векторе меняется местами один элемент из тысячи. Это почти отсортированный вектор. На полностью отсортированном сортировка вставками это один проход. O(N). Вообще, из теста видно, что ни один алгоритм не ускоряется так сильно на отсортированных данных. Хотя обычно берется без зазрения совести std::sort/std::stable_sort. Единственный оправданием в вашем случае может быть то, что Вы писали на чистом С.
Re[11]: Почему преждевременная оптимизация - корень всех зол
Здравствуйте, skeptik_, Вы писали:
_>Здравствуйте, anton_t, Вы писали:
_>>>>>>У меня был реальный случай, когда я без зазрения совести не взял qsort из стандартной библтотеки, а реализовал сортировку пузырьком: было известно, что в более 90% случаев данные отсортированы, а в оставшихся случаях имеют 2 неотсортированных элемента и, кроме того, менять местами равные элементы было нельзя. Естественно это решение в коде я прокомментировал.
_>>>>>В этом случае лучшим решением была бы сортировка вставками, а не пузырёк.
_>>>>И на сколько лучшим?
_>>>Это прекрасно видно из моего кода и результатов. Сортировка вставками быстрее (в несколько раз на случайных данных, на порядок при почти отсортированных) и проще в имплементации (3 строки против 4).
_>>В коде и результатах нет случая, когда данные отсортированы, поэтому ничего не видно.
_>Там есть случай, когда в отсортированном векторе меняется местами один элемент из тысячи. Это почти отсортированный вектор. На полностью отсортированном сортировка вставками это один проход. O(N). Вообще, из теста видно, что ни один алгоритм не ускоряется так сильно на отсортированных данных. Хотя обычно берется без зазрения совести std::sort/std::stable_sort. Единственный оправданием в вашем случае может быть то, что Вы писали на чистом С.
На отсортированном массиве пузырёк тоже делает только один проход.
Re[5]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, Константин Л., Вы писали:
_FR>>Не раз видел, когда при необходимости всего-то найти пересечение двух множеств (заданных массивом\IList\IEnumerable, не важно) делался foreach по одному списку, а внутри него — по другому И на все пожелания сделать правильно отвечалось, что "нечего преждевременной оптимизацией заниматься", тогда как дело попросту в незнании более эффективных алгоритмов (что, к счастью, поправимо) и нежелании их узнать (с чем уже ничего не поделать)
КЛ>а правильно это как? что может быть быстрее на неотсортированной коллекции
Примерно так:
using System;
using System.Collections.Generic;
using System.Linq;
internal static class Program
{
private static void Main() {
var first = Enumerable.Range(1, 10);
var second = Enumerable.Range(5, 10);
var intersect = first.Intersect(second, null);
foreach(var item in intersect) {
Console.WriteLine(item);
}//for
}
private static IEnumerable<T> Intersect<T>(this IEnumerable<T> left, IEnumerable<T> right, IEqualityComparer<T> comparer) {
var set = new HashSet<T>(comparer ?? EqualityComparer<T>.Default);
foreach(var item in left) {
set.Add(item);
}//forforeach(var item in right) {
if(set.Contains(item)) {
yield return item;
}//if
}//for
}
}
Help will always be given at Hogwarts to those who ask for it.
Re[5]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, minorlogic, Вы писали:
M>Стандартную , это потдерживаемую языком/фреймворком, библиотеками. Вручную написанную сортировку я бы мог понять если требуется жесткая специфическая оптимизация(но тогда уже речь идет о днях проведенных в профайлере ).
Если разработчик находится в цейтноте, он превращается в "чукчу-писателя". Особенно, если балбес-менеджер отрапортовал, что "вчера все будет готово". Во многих прикладных задачах сортировку вообще не приходится реализовывать, поскольку данные уже приходят упорядоченными по требуемым критериям. Поэтому, читая описание фреймворка/библиотеки, разработчик, как правило, не сталкивается с описанием средств сортировки. А в условиях работы "на вчера" ему проще, легче и быстрее настрочить метод пузырька, чем копаться в документации в поисках стандартных средств.
Вот попробовал я заменить свою функцию на предоставленное фреймворком средство (в моем случае Arrays.sort() из Java 1.4). Выдалась пара свободных часов. Закодировать его несложно, однако нужно все время обращаться к документации, а это потеря времени. Поскольку производительность программы в моем случае не имеет никакого значения (объем данных мал, и вызывается сортировка редко), абсолютно безразлично, как эту сортировку делать. В условиях жесткого дефицита времени на первый план выходит производительность разработчика. При реализации метода пузырька мне даже не пришлось никуда подсматривать (ну еще бы, не я ли сам его изобрел не первом курсе ).
А при попытке заменить "своего" пузырька на Arrays.sort пришлось сначала узнать, где этот самый Arrays.sort находится, потом разобраться с его параметрами, выяснить, как и когда передается в него функция сравнения. Все достаточно просто, но времени на все это нет. Ибо вокруг все бегают, суетятся, торопят. Так что отложил я это дело в сторонку и сижу, пока QA какой-нибудь баг в том районе найдут. Тогда, может, и заменю сортировку. Хотя, откуда в медоде пузырька баги?
Естественно, второй раз на реализацию сортировки штатными средствами времени уйдет гораздо меньше, но для этого ее надо сделать первый раз. А задача это, как я уже сказал, делается не каждый день. Тот пузырек, кажется, единственная ручная сортировка на все приложение.
Re[6]: Почему преждевременная оптимизация - корень всех зол?
Двавал группе не самых слабых разработчиков написать функцию нахождения максимального элемента в массиве целых чисел.
В итоге больше половины написали с ошибками , из которых 3 были просто багами и одна архитектурная, а теперь попробую себе представить когда подобные алгоритмы пишутся в спешке , жуть .....
А если подумать это очень несложный алгоритм, по сравнению с сортировкой просто дет сад. Хотите проверить ? попробуйте сразу после прочтения поста написать за 5 минут такую функцию.
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Ищу работу, 3D, SLAM, computer graphics/vision.
Re[7]: Почему преждевременная оптимизация - корень всех зол?
Здравствуйте, minorlogic, Вы писали:
M>Добавлю про правильность написания пузырька.
M>Двавал группе не самых слабых разработчиков написать функцию нахождения максимального элемента в массиве целых чисел.
M>В итоге больше половины написали с ошибками , из которых 3 были просто багами и одна архитектурная, а теперь попробую себе представить когда подобные алгоритмы пишутся в спешке , жуть .....
А в чём заключалась архитектурная?
ЗЫ У меня получился за 3 минуты почти один в один std::max_element.
И на все пожелания сделать правильно отвечалось, что "нечего преждевременной оптимизацией заниматься", тогда как дело попросту в незнании более эффективных алгоритмов (что, к счастью, поправимо) и нежелании их узнать (с чем уже ничего не поделать) 
).
