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

Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 9, средняя оценка - 4.89
m1namoto
0 / 0 / 0
Регистрация: 23.06.2012
Сообщений: 51
17.12.2012, 00:48     Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки #1
Почему вот это :
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
void sort(int *ar, int L, int R){
    int i, j, x, buf;
    x = ar[(L+R)/2];
    i = L;
    j = R;
    do
    {
        while(ar[i]<x)
            i++;
        while(ar[j]>x)
            j--;
        if(i<=j){
            buf = ar[i];
            ar[i] = ar[j];
            ar[j] = buf;
            i++;
            j--;
        }
    }
        while(i<=j);
 
        if(j>L)
            sort(ar, L, j);
        if(i<R)
            sort(ar, i, R);
    }
 
void sortQuick(int *ar, int cnt){
    int L, R;
    L = 0;
    R = cnt - 1;
    sort(ar, L, R);
}
выполняется быстрее чем вот это:
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
void Quick(int *arr, int cnt) {
      int base, left, right, i, j;
      base = left = right = i = j = 0;
      stack<int> st;
 
      st.push(cnt - 1);
      st.push(0);
 
      do {
 
          left = st.top();
          st.pop();
 
          right = st.top();
          st.pop();
 
 
              base = arr[(left + right) / 2];
              i = left;
              j = right;
 
              do {
                  while(base > arr[i])
                      ++i;
                  while(arr[j] > base)
                      --j;
                  if (i <= j) {
                      swap(arr, i++, j--);
                  }
              } while (i <= j);
 
          if (left < j) {
              st.push(j);
              st.push(left);
          }
          if (i < right) {
              st.push(right);
              st.push(i);
          }
      } while(!st.empty());
  }
Рекурсия ведь должна медленнее работать. Или нет ?
Проверяю таким образом :
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int main(){
srand(time(NULL));
int ar[100000];
for(int i=0; i<100000; i++){
    ar[i] = rand() % 1000;
}
cout << "Start:" << endl;
 
for(int i=0; i<100000; i++){
    cout << ar[i] << " ";
}
 
cout << endl;
cout << "Result:" << endl;
unsigned int start_time =  clock(); // начальное время
Quick(ar, 100000);
//sortQuick(ar, 100000);
unsigned int end_time = clock(); // конечное время
unsigned int search_time = end_time - start_time; // искомое время
for(int i=0; i<100000; i++){
    cout << ar[i] << " ";
}
cout << endl <<  "TIME = " << search_time;
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.12.2012, 00:48     Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки
Посмотрите здесь:

C++ Как узнать время выполнения алгоритма
C++ Время выполнения алгоритма
C++ Рассчитать время выполнения алгоритма
Алгоритмы сортировки. Время выполнения C++
прогресс выполнения быстрой сортировки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
17.12.2012, 09:15     Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки #2
Цитата Сообщение от m1namoto Посмотреть сообщение
Рекурсия ведь должна медленнее работать. Или нет ?
Рекурсия будет быстрее работать за счет более быстрого "стека".

В не-рекурсивном варианте у вас используется довольно "тяжелая" структура данных, которая, в общем-то, и просаживает производительность.

Не уверен, что упрощение стэка поможет, так как рекурсия -- суть то же помещение переменных в стек, только самим компилятором.
m1namoto
0 / 0 / 0
Регистрация: 23.06.2012
Сообщений: 51
17.12.2012, 15:39  [ТС]     Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки #3
Только кроме помещения переменных еще адреса возвратов, передача управления по этим адресам...
Получается STL не особо производительная ? Скорее универсальная ?
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
17.12.2012, 16:37     Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки #4
Цитата Сообщение от m1namoto Посмотреть сообщение
Получается STL не особо производительная ? Скорее универсальная ?
Конечно. Производительность помещения значений в стек вызова гораздо дешевле, чем работа с STL стеком.
diagon
Higher
 Аватар для diagon
1920 / 1186 / 49
Регистрация: 02.05.2010
Сообщений: 2,925
Записей в блоге: 2
17.12.2012, 17:04     Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки #5
У вас не студия случаем? По умолчанию стек реализован через дек, а в студии он дико тормозит. Попробуйте поставить вектор.
m1namoto
0 / 0 / 0
Регистрация: 23.06.2012
Сообщений: 51
17.12.2012, 18:15  [ТС]     Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки #6
Сделал на базе массива стек, разница результатов рекурсивной и итерационной реализации колеблется в районе 1 мс) То есть, можно говорить об одинаковом результате ... Где же тот прирост быстродействия в итерационной реализации, описанный в n-ом количестве источников ?
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
struct my_stack{
    int l, r;
};
 
void QuickA(int *arr, int cnt) {
      int top, base, left, right, i, j;
      base = left = right = i = j = 0;
      my_stack st[1000];
      top = 0;
 
 
 
      st[0].r = (cnt - 1);
      st[0].l = 0;
 
      do {
 
          left = st[top].l;
 
 
          right = st[top].r;
          top--;
 
 
 
              base = arr[(left + right) / 2];
              i = left;
              j = right;
 
              do {
                  while(base > arr[i])
                      ++i;
                  while(arr[j] > base)
                      --j;
                  if (i <= j) {
                      swap(arr, i++, j--);
                  }
              } while (i <= j);
 
          if (left < j) {
              top++;
              st[top].r = j;
              st[top].l = left;
          }
          if (i < right) {
              top++;
              st[top].r = right;
              st[top].l = i;
          }
      } while(top!=-1);
  }
А выполняю в Qt Creator, а не в студии.
Yandex
Объявления
17.12.2012, 18:15     Время выполнения рекурсивного и итерационного алгоритма быстрой сортировки
Ответ Создать тему
Опции темы

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