среда, 21 октября 2009 г.

Блог Саттера: Опрос

Герб Саттер проводит опрос на тему: какие темы в конкурентном программировании на C++ осветить в дальнейших постах. You're welcome to participate.

В целом его блог для программистов на C++ из набора "очень желательны к ознакомлению". А цикл статей "Effective Concurrency" - это уже из набора "обязательных к прочтению", - 90% вопросов, которые возникают в процессе работы и на собеседованиях уже освещены.
Очень советую к прочтению.

P.S.

Вот и как на русский перевести правильно concurrency programming?.. Многопоточное и конкурентное программирование это всё же другие оттенки смысла.

четверг, 15 октября 2009 г.

Сортировки и сборки...

В http://www.reddit.com/r/programming/comments/9jj5z/vladimir_yaroslavskiys_dualpivot_quicksort/ прочитал об улучшении классического quicksort'а при помощи добавления второго опорного элемента. Автор показывает, что для худшего случая время работы получается на 20% лучше, чем у стандартной реализации.

Меня это заинтересовало. Да и захотелось сравнить с другими сортировками, а то использую в рабочем коде только обощённый метод из стандартной библиотеки C++, а в быстрых поделках на колене - шеловскую сортировку (настолько к этому сочетанию уже привык, что кажется - подними с кровати, напишу использование на полном автомате, не просыпаясь).

Для сравнения были выбраны следующие сортировки: реализация quicksort'а в лоб без каких-либо улучшений, реализация quicksort'а с использованием сортировки вставкой на малых массивах, dual pivot quicksort, sort из стандартной библиотеки C++ (чтобы был наглядней результат), quicksort из C runtime(насколько я понимаю, тут используется реализация из стандартной библиотеки C) и сортировка Шела с шагами 2^n -1.

Измерения проводились на векторе в 5 миллионов int'ов. Использование обощенного контейнера было основано на необходимости использовать в сравнении обобщённый sort из стандартной библиотеки C++. Среди контейнеров же был выбран вектор, т.к. хотелось посмотреть на результат qsort из C Runtime Library.

Измерения выполнялись в MS VC++2005.

Результаты получились, мягко говоря, странными.