Форум программистов, компьютерный форум CyberForum.ru

Засечь время выполнения пирамидальной сортировки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.77
Тиша
 Аватар для Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
25.01.2011, 18:31     Засечь время выполнения пирамидальной сортировки #1
мне нужно засечь время выполнения алгоритма сортировок, и у меня не выходит только с одной - с пиромидальной. программа на c++ код ниже. Засекаю все это дело clock();
на пузырке, выборе и вставке все работает прекрастно, а тут загрузы(
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void Sort::HeapSort() {
long i;
int temp;
 
 
for(i=size/2-1; i >= 0; i--)
downHeap(i, size-1);
 
for(i=size-1; i > 0; i--) {
temp=a[i]; a[i]=a[0]; a[0]=temp;
downHeap(0, i-1);
}
}
void downHeap(long k, long n) {
int new_elem;
long child;
new_elem = a[k];
 
while(k <= n/2) {
child = 2*k;
if( child < n && a[child] < a[child+1] )
child++;
if( new_elem >= a[child] ) break;
a[k] = a[child];
k = child;
}
a[k] = new_elem;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.01.2011, 18:31     Засечь время выполнения пирамидальной сортировки
Посмотрите здесь:

C++ оценки трудоемкости быстрой, пирамидальной, пузырьковой сортировки по времени и обьему памяти
C++ Засечь время выполнения поиска
Засечь время сортировки разных типов данных C++
Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки C++
Алгоритмы сортировки. Время выполнения C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
25.01.2011, 18:46     Засечь время выполнения пирамидальной сортировки #2
Тиша, так что конкретно не работает?
Тиша
 Аватар для Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
25.01.2011, 18:52  [ТС]     Засечь время выполнения пирамидальной сортировки #3
Nameless One, таймер выдает нули. То есть алгоритм сортировки правильный, программа компилируется, работает, все окей, но время работы выдает 0
в других сортировках не было рекурсии и все работало.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
25.01.2011, 18:53     Засечь время выполнения пирамидальной сортировки #4
Тиша, а выложи код, где конкретно замеряется скорость работы для данного алгоритма
Тиша
 Аватар для Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
25.01.2011, 18:57  [ТС]     Засечь время выполнения пирамидальной сортировки #5
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void Sort::HeapSort() {
clock_t start;
       start=clock();
long i;
int temp;
 
 
for(i=size/2-1; i >= 0; i--)
downHeap(i, size-1);
 
for(i=size-1; i > 0; i--) {
temp=a[i]; a[i]=a[0]; a[0]=temp;
downHeap(0, i-1);
}
  diff=(clock()-start)/(double)CLOCKS_PER_SEC;
}
просто это курсовой проэкт, код огромен, вот засечь время выполнения - это одна из частей
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
25.01.2011, 19:01     Засечь время выполнения пирамидальной сортировки #6
Ну и на всякий случай спрошу: diff - переменная с плавающей точкой?
Тиша
 Аватар для Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
25.01.2011, 19:03  [ТС]     Засечь время выполнения пирамидальной сортировки #7
Nameless One, да, типа double, описана у меня в классе
я просто не могу придумать уже что сделать
пробовала убирать рекурсию и все равно дает нули
вот никак не могу закончить проэкт из-за этого косяка :/
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
25.01.2011, 19:05     Засечь время выполнения пирамидальной сортировки #8
Тиша, а если попробовать увеличить размер сортируемого массива?
Тиша
 Аватар для Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
25.01.2011, 19:12  [ТС]     Засечь время выполнения пирамидальной сортировки #9
Nameless One, размер - 40000 цифорок, делаю рандомом *хмыкает*

Добавлено через 5 минут
если чем-то поможет, когда я вызывала саму функцию, например сортировки пузырьком

C++
1
2
3
4
clock_t start;
       start=clock();
a.BubleSort();
  diff=(clock()-start)/(double)CLOCKS_PER_SEC;
тогда тоже выдавало diff=0
а когда запихнула таймер в сам код функции BubleSort, то заработало
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
25.01.2011, 19:48     Засечь время выполнения пирамидальной сортировки #10
Если ты говоришь, что сама сортировка работает правильно (тестировала упорядоченность массива после сортировки?), то, значит, дело в самих замерах. Ну, вот аналогичный код (сравниваем стандратный qsort и пирамидальную сортировку):
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
typedef void (*sortingFunc)(int*, int);
 
#define SIZE 4096 * 16 * 8
#define L_T -100500
#define R_T  100500
 
void downHeap(int a[], int k, int n);
void heapSort(int a[], int size);
void qsortWrapper(int a[], int size);
int cmp(const void* a, const void* b);
void test(sortingFunc func, const char* name);
 
int main()
{
    srand((size_t) time(NULL));
 
    test(qsortWrapper, "Standart qsort");
    test(heapSort, "Heap Sort");
    
    exit(0);
}
 
void downHeap(int a[], int k, int n) 
{
    int new_elem;
    int child;
    new_elem = a[k];
 
    while(k <= n/2) 
    { 
        child = 2*k;
 
        if( child < n && a[child] < a[child+1] ) 
            ++child;
        if( new_elem >= a[child] ) 
            break; 
 
        a[k] = a[child]; 
        k = child;
  }
  a[k] = new_elem;
}
 
void heapSort(int a[], int size) 
{
    int i;
    int temp;
 
    for(i=size/2-1; i >= 0; --i) 
        downHeap(a, i, size-1);
 
 
    for(i=size-1; i > 0; --i) 
    {
        temp=a[i]; a[i]=a[0]; a[0]=temp;
        downHeap(a, 0, i-1); 
    }
}
 
void qsortWrapper(int a[], int size)
{
    qsort(a, size, sizeof(int), cmp);
}
 
int cmp(const void* a, const void* b)
{
    int A = *(const int*) a;
    int B = *(const int*) b;
    if(A < B)
        return -1;
    if(B < A)
        return 1;
    return 0;
}
 
void test(sortingFunc func, const char* name)
{
    int *iarray;
    size_t i;
    clock_t start, finish;
    
    if((iarray = malloc(SIZE * sizeof(int))) == NULL)
        exit(1);
    
    for(i = 0; i < SIZE; ++i)
        iarray[i] = rand() % (R_T - L_T + 1) + L_T;
        
    start = clock();
    func(iarray, SIZE);
    finish = clock();
    printf("Sorted (%s) in %.3f seconds\n", name, ((double) (finish - start))/((double) CLOCKS_PER_SEC));
    
    free(iarray);
}
И что он мне выдал:
Код
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$
И это при запуске на нетбуке, который отнюдь не блещет производительностью. Может, все же имеет смысл увеличить количество циферок?
Тиша
 Аватар для Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
25.01.2011, 19:51  [ТС]     Засечь время выполнения пирамидальной сортировки #11
Nameless One, хмм...сейчас попробую
Nameless One
25.01.2011, 19:58
  #12

Не по теме:

А вообще для таких дел предназначены профилировщики

Тиша
 Аватар для Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
25.01.2011, 20:02  [ТС]     Засечь время выполнения пирамидальной сортировки #13
Nameless One, да, увеличила до 100000 - время увеличилось. Только странно что так быстро сортирует. допустим тот же пузырек отсортировал массив на 40000 за 150 секунд, а тут сортирует 100000 за доли секунд

Добавлено через 22 секунды
Цитата Сообщение от Nameless One Посмотреть сообщение

Не по теме:

А вообще для таких дел предназначены профилировщики

а подробнее?
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
25.01.2011, 20:04     Засечь время выполнения пирамидальной сортировки #14
Как делал я: запускал функцию сортировки 5000 раз и делил полученное время на 5000. Вот. И для определения времени использовал SYSTEMTIME, т.к. насколько я знаю clock() замеряет только с точностью до секунды, а SUSTEMTIME до миллисекунд.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
25.01.2011, 20:12     Засечь время выполнения пирамидальной сортировки #15
Тиша, пузырек - это яркий пример алгоритма сортировки, который *никогда* не следует использовать.
Цитата Сообщение от Тиша Посмотреть сообщение
а подробнее?
Это специальные приложения, используемые для того, чтобы тестировать производительность своих программ, выявлять неэффективные участки кода и т.д. (подробнее). Самому для лаб приходилось использовать TrueTime и Intel VTune, скажу, что они достаточно просто изучаются.

Добавлено через 3 минуты
RUSya82, тогда к результатам замеров примешивается "шум" от дополнительных вызовов функций и т.д. Хотя, наверно, сильно на результаты он повлиять не должен.

Добавлено через 2 минуты
Цитата Сообщение от RUSya82 Посмотреть сообщение
насколько я знаю clock() замеряет только с точностью до секунды
Точность clock порядка десятков миллисекунд
RUSya82
 Аватар для RUSya82
236 / 114 / 3
Регистрация: 15.10.2010
Сообщений: 395
25.01.2011, 20:17     Засечь время выполнения пирамидальной сортировки #16
Цитата Сообщение от Тиша Посмотреть сообщение
Только странно что так быстро сортирует. допустим тот же пузырек отсортировал массив на 40000 за 150 секунд, а тут сортирует 100000 за доли секунд
Это ни странно. В этом наверняка и состоит Ваша задача - определить и проанализировать означенные методы сортировки.
Сортировка пузырьком - одна из самых медленных, но проста в реализации. И при некоторых входных последовательностях может быть весьма приемлема.
Пирамидальная же сортировка одна из быстрых. У неё есть одно замечательное качество: вне зависимости от входной последовательности, время сортировки постоянно и зависит только от количества ключей.

Добавлено через 3 минуты
Цитата Сообщение от Nameless One Посмотреть сообщение
к результатам замеров примешивается "шум"
А думал об этом, но этот шум даст всего лишь небольшое смещение по оси Y графика, т.к. он постоянен для каждого из 5000 вызовов, и как оказывается весьма несущественен, то есть рисунок останется тем же, просто поднимется по оси ординат. На анализ и изучение методов сортировки это не повлияет.
Nameless One
Эксперт С++
 Аватар для Nameless One
5753 / 3402 / 255
Регистрация: 08.02.2010
Сообщений: 7,393
25.01.2011, 20:17     Засечь время выполнения пирамидальной сортировки #17
Добавлю - сложность пузырьковой сортировки - O(n²), в то время как сложность пирамидальной - O(n log n)
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.01.2011, 20:30     Засечь время выполнения пирамидальной сортировки
Еще ссылки по теме:

прогресс выполнения быстрой сортировки C++
Отсортировать массив по убыванию через алгоритм пирамидальной сортировки C++
C++ Время выполнения сортировки

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Тиша
 Аватар для Тиша
1 / 1 / 0
Регистрация: 02.11.2009
Сообщений: 75
25.01.2011, 20:30  [ТС]     Засечь время выполнения пирамидальной сортировки #18
Я поняла ^^
спасибо-спасибо
Yandex
Объявления
25.01.2011, 20:30     Засечь время выполнения пирамидальной сортировки
Ответ Создать тему
Опции темы

Текущее время: 20:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru