привет дзенствующим стоит простая задача на winxp измерить скорость выполнения различных видов сортировок, например пузырек, шелл, хоара, поразрядная и т.д. собственно, первое что пришло в голову - найти разницу во времени, а также количества тактов. сортировки выполняются отдельным потоком, который естественно может быть перепланирован, в результате чего получаются сильные перепады результатов даже при усредненной выборке из множества прогонов. буду благодарен услышать предложение, как можно максимально _точно_ определить реальную скорость выполнения алгоритмов на многозадачной ос
bvcbdbdn125678 Сами сортировки сравниваются вот здесь Сортируется массив из 26 двойных слов, сравнивается количество сравнений 1) Пузырьковая -- лучший случай — 25, средний — 289, худший — 325 2) Шейкер -- лучший случай — 25, средний — 259 (лучше пузырьковой сортировки на 20%), худший — 325 3) Пирамидальная -- средний случай — 109 (лучше пузырьковой сортировки почти в 3 раза) 4) сортировка прямым включением -- лучший случай — 25, средний — 172 (лучше пузырьковой сортировки на 40%), худший — 325 Алгоритм можно улучшить пользуясь тем, что готовая последовательность уже упорядочена. Место вставки нового элемента можно найти значительно быстрее, если применить бинарный поиск, исследовав сперва средний элемент упорядоченной последовательности и продолжая деление пополам, пока не будет найдено место вставки. Для n=26 элементов лучший случай — 25, средний и худший — 106 (лучше пузырьковой сортировки почти в 3 раза) 5) сортировка прямым выбором в худшем, среднем и лучшем случае n*(n-1)/2 6) сортировка Шелла Среднее время работы алгоритма зависит от длин промежутков, на которых будут находится сортируемые элементы исходного списка на каждом шаге алгоритма при выборе последовательности значений d1=n/2, d2=d1/2,...,1 в худшем случае алгоритм выполнит O(n2) — сравнений 140 Table dd 32768,16384,8192,4096,2048,1024,512,256,128,64,32,16,8,4,2,1 все значения (3^j−1)/2 < n, такая последовательность шагов приводит к алгоритму класса O(n^(3/2)) — сравнений 108 Table dd 797161,265720,88573,29524,9841,3280,1093,364,121,40,13,4,1 последовательности вида N=2*N+1 — сравнений 118 Table dd 32767,16383,8191,4095,2047,1023,511,255,127,63,31,15,7,3,1 последовательность Дж.Инсерпи и Р.Седгевика — сравнений 115: Table dd 198768,86961,33936,13776,4592,1968,861,336,112,48,21,7,3,1 7) сортировка Хоара (быстрая сортировка) Сортировка даёт в среднем O(n log n) сравнений По замеру времени под win32 поищи ответы leo на wasm.ru/forum
Квант времени планировщика если ничего не путаю ~20мс, (а если путаю, то сейчас кто-нибудь уточнит соответственно если время работы тестового кода существенно меньше кванта, то вероятность что он будет прерван весьма невелика и такие прерывания будут очень хорошо видны как аномалии при нескольких запусках. Поэтому подгоняй время тестирования примерно по 0,1-0,2 времени кванта и будет тебе счастье . Кроме того можно поднять приоритет потока, тогда кажется до 5с выделяется без прерывания. Другое дело, что не забудь учесть, что первое выполнение кода связана с кэшированием и данных и команд (в трэйскеше) и потому время там на порядок больше повторных исполнений. Поэтом выводи несколько, не менее 5х заходов и не удивляйся большой разнице между первым и 3м запусками - какое время "правильное" зависит от того чего ты хочешь получить - для редко исполняемого кода "правильный" первый замер, а для часто исполняемого - типовой после 3-го. И на многоядерниках будет ещё хитрая зависимость от загруженности остальных ядер, где-то тут leo подробности этого эффекта постил, но где не помню. Пример профилирования сортировки. и цитата оттуда:
Mikl___ спасиб за информацию Спецификой типов данных я пренебрегаю, н.у. у всех сортировок в моем примере одинаковые. Сортируется массив из 100 элементов целого типа без знака. Y_Mur поднятие приоритета не позволило устранить "помехи" на многопроцессорной системе, увы, почти самое первое что попробовал. Пробовалось также Sleep(0). Я измеряю скорость сортировки вызовом rdtsc непосредственно перед выполнением основного блока сортировки и вызовом rdtsc после. Соотвественно считаю разницу и получаю кол-во тактов. Некоторой погрешностью на выполнение самого замера тактов так и быть можно пренебречь. Конечный результат для каждой сортировки считается как усредненное значение из N прогонов (где всегда N >= 10). Код сортировок на C, при желании можно переписать на asm однако это врядли сильно что-то изменит в конечных результатах. На выходе я получаю графики для каждого типа сортировки, которые более и менее точно отражают теоретические выкладки (самая медленная пузырек, шейкер быстрее ~ 20%, самая быстрая, если исключить подсчет добавленный что называется для кучи с игнорированием особенности, - хоара). Тем не менее при сортировке одних и тех же начальных данных при разных прогонах получаются иногда сильные отклонения, например шейкер получается много больше пузырька и т.п., что наводит на мысль о переключении контекста потока во время сортировки. Задача получить максимально приближенные к реальным значениям скорости сортировок с перечисленными выше допущениями. т.е. идеально четкие значение как я понимаю будут получены при выполнении блока кода сортировки без переключения контекста. Поправьте если я неправ. Любые самые дикие предложения приветствуются user modом я не ограничен если что
Лучше не усреднять N прогонов, а выводить на экран результаты этих N замеров, тогда сразу увидишь и как отличется 1й прогон от типового, и на каком из прогонов возникает "аномалия" из-за переключения контекста. В этом случае "типовое" время увидеть значительно проще чем при усреднении - там одно аномальное значение портит все замеры в серии . Ну и на многоядернике результаты всегда менее стабильны чем на одноядерном, если эта нестабильность для тебя сильно существенна - отключай "лишние" ядра совсем.
Кстати не забывай про разницу между алгоритмической оптимизацией и оптимизайции при реализации алгоритма Например если один алгоритм работает за n сравнений, а другой за n^2, то сравнивать их скорости при конкретном значении n имхо изначально не корректно Собственно для этого "теоретические" оценки алгоритмов и придуманы, чтобы сравнивать функции от n, а не замеры привязанные к размеру сортируемого массива
Основные приниципы "борьбы" с виндовыми прерываниями см. например здесь Плюс к этому не мешает проверить величину системного кванта (тика) времени, т.к. мультимедийные службы могут уменьшать его до 1 мс (timeBeginPeriod), что ес-но негативно сказывается на всем остальном из-за слишком частого переключения потоков. Что касается многопроцессорности, то 1) С HyperThreading'ом бороться бесполезно - его нужно просто отрубать в биосе на время измерений 2) Работа с большими объемами памяти сама по себе нестабильна, а в многоядерных процах тем более. Поэтому для повышения точности сравнительных тестов лучше брать небольшие объемы и предварительно загружать данные в кэш. Если же нужна проверка работы именно с учетом подкачки данных из ОЗУ, то повышенный разброс неизбежен, а "дурное" влияние других ядер можно уменьшить, загрузив их своими потоками "пустышками", не обращаюшимися к памяти (крутить, какой-нить, fdiv в цикле) - ну и на всякий сл. задать всем потокам привязку к процессорам
А помойму виндовые прерывания и перепланирование это бред. Сколько их тестировал не замечал. Либы они уходили как средее либы были не успевали случиться. Зато вот кэш порой ускаряет обработку 1.5 раза. Дело в том что 10 недостаточно. 10 дает ошибку 10-50%. Для измерений рекомендуют более >30 Но меня это неустраивает лучше 50-100 тогда ошибка будет 1-5%. Когда время инструкций мерил брал 1000 и больше ошибка 1/1000, но тут проблемы что планировщик уже начинает мешать. Зато крассивые результаты (1.00x 0.33x) Теперь по поводу диких идей. На коре 2 дуе идет разброс значений даже если время измерения ниже кванта времени. Более точные результаты у меня получались если прогоны делать не в цикле, а в виде кнопочка и мышкай счелкаешь 50-100 на один алгоритм.
