1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
|
||||||
1 | ||||||
Засечь время выполнения пирамидальной сортировки25.01.2011, 18:31. Показов 5127. Ответов 17
Метки нет (Все метки)
мне нужно засечь время выполнения алгоритма сортировок, и у меня не выходит только с одной - с пиромидальной. программа на c++ код ниже. Засекаю все это дело clock();
на пузырке, выборе и вставке все работает прекрастно, а тут загрузы(
0
|
25.01.2011, 18:31 | |
Ответы с готовыми решениями:
17
Засечь время выполнения поиска Засечь время сортировки разных типов данных Время выполнения сортировки Алгоритмы сортировки. Время выполнения |
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
25.01.2011, 18:46 | 2 |
Тиша, так что конкретно не работает?
0
|
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
|
|
25.01.2011, 18:52 [ТС] | 3 |
Nameless One, таймер выдает нули. То есть алгоритм сортировки правильный, программа компилируется, работает, все окей, но время работы выдает 0
в других сортировках не было рекурсии и все работало.
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
25.01.2011, 18:53 | 4 |
Тиша, а выложи код, где конкретно замеряется скорость работы для данного алгоритма
0
|
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
|
||||||
25.01.2011, 18:57 [ТС] | 5 | |||||
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
25.01.2011, 19:01 | 6 |
Ну и на всякий случай спрошу: diff - переменная с плавающей точкой?
0
|
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
|
|
25.01.2011, 19:03 [ТС] | 7 |
Nameless One, да, типа double, описана у меня в классе
я просто не могу придумать уже что сделать пробовала убирать рекурсию и все равно дает нули вот никак не могу закончить проэкт из-за этого косяка :/
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
25.01.2011, 19:05 | 8 |
Тиша, а если попробовать увеличить размер сортируемого массива?
0
|
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
|
||||||
25.01.2011, 19:12 [ТС] | 9 | |||||
Nameless One, размер - 40000 цифорок, делаю рандомом *хмыкает*
Добавлено через 5 минут если чем-то поможет, когда я вызывала саму функцию, например сортировки пузырьком
а когда запихнула таймер в сам код функции BubleSort, то заработало
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
||||||
25.01.2011, 19:48 | 10 | |||||
Если ты говоришь, что сама сортировка работает правильно (тестировала упорядоченность массива после сортировки?), то, значит, дело в самих замерах. Ну, вот аналогичный код (сравниваем стандратный qsort и пирамидальную сортировку):
Код
nameless@nameless-laptop:~/foo$ make && ./foo cc -ansi -pedantic -Wall -c -o main.o main.c cc -o foo main.o Sorted (Standart qsort) in 0.430 seconds Sorted (Heap Sort) in 0.570 seconds nameless@nameless-laptop:~/foo$
0
|
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
|
|
25.01.2011, 19:51 [ТС] | 11 |
Nameless One, хмм...сейчас попробую
0
|
Nameless One
|
25.01.2011, 19:58
#12
|
Не по теме: А вообще для таких дел предназначены профилировщики
0
|
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
|
|
25.01.2011, 20:02 [ТС] | 13 |
Nameless One, да, увеличила до 100000 - время увеличилось. Только странно что так быстро сортирует. допустим тот же пузырек отсортировал массив на 40000 за 150 секунд, а тут сортирует 100000 за доли секунд
Добавлено через 22 секунды а подробнее?
0
|
242 / 120 / 14
Регистрация: 15.10.2010
Сообщений: 395
|
|
25.01.2011, 20:04 | 14 |
Как делал я: запускал функцию сортировки 5000 раз и делил полученное время на 5000. Вот. И для определения времени использовал SYSTEMTIME, т.к. насколько я знаю clock() замеряет только с точностью до секунды, а SUSTEMTIME до миллисекунд.
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
25.01.2011, 20:12 | 15 |
Тиша, пузырек - это яркий пример алгоритма сортировки, который *никогда* не следует использовать.
Это специальные приложения, используемые для того, чтобы тестировать производительность своих программ, выявлять неэффективные участки кода и т.д. (подробнее). Самому для лаб приходилось использовать TrueTime и Intel VTune, скажу, что они достаточно просто изучаются. Добавлено через 3 минуты RUSya82, тогда к результатам замеров примешивается "шум" от дополнительных вызовов функций и т.д. Хотя, наверно, сильно на результаты он повлиять не должен. Добавлено через 2 минуты Точность clock порядка десятков миллисекунд
0
|
242 / 120 / 14
Регистрация: 15.10.2010
Сообщений: 395
|
|
25.01.2011, 20:17 | 16 |
Это ни странно. В этом наверняка и состоит Ваша задача - определить и проанализировать означенные методы сортировки.
Сортировка пузырьком - одна из самых медленных, но проста в реализации. И при некоторых входных последовательностях может быть весьма приемлема. Пирамидальная же сортировка одна из быстрых. У неё есть одно замечательное качество: вне зависимости от входной последовательности, время сортировки постоянно и зависит только от количества ключей. Добавлено через 3 минуты А думал об этом, но этот шум даст всего лишь небольшое смещение по оси Y графика, т.к. он постоянен для каждого из 5000 вызовов, и как оказывается весьма несущественен, то есть рисунок останется тем же, просто поднимется по оси ординат. На анализ и изучение методов сортировки это не повлияет.
0
|
5828 / 3479 / 358
Регистрация: 08.02.2010
Сообщений: 7,448
|
|
25.01.2011, 20:17 | 17 |
Добавлю - сложность пузырьковой сортировки - O(n²), в то время как сложность пирамидальной - O(n log n)
0
|
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
|
|
25.01.2011, 20:30 [ТС] | 18 |
Я поняла ^^
спасибо-спасибо
0
|
25.01.2011, 20:30 | |
25.01.2011, 20:30 | |
Помогаю со студенческими работами здесь
18
Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки Отсортировать массив с помощью бинарной пирамидальной сортировки Отсортировать массив по убыванию через алгоритм пирамидальной сортировки Сортировать по убыванию одномерный динамический массив методом бинарной пирамидальной сортировки Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |