Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.60/5: Рейтинг темы: голосов - 5, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 16.10.2019
Сообщений: 77
1

Как работает время в программе, почему сортировка массива на 1000 элементов быстрее, чем сортировка массива на 8?

11.04.2020, 02:44. Просмотров 981. Ответов 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
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
99
100
101
102
#include <iostream>
#include <chrono>
#include <cmath>
#include "List.h"
#include <iomanip>
#include <cstdlib>
 
//генератор рандомных массивов
template <class T>
void randomArrayGenerator(T* arr, const int len)
{
  std::srand(std::time(NULL));
  for (size_t i = 0; i < len; ++i)
  {
    arr[i] = std::rand() % 10;
  }
}
 
//нахождение максимального элемента 
template <class T>
T maxArrayElement(T* arr, const int len)
{
  T max = arr[0];
  for (size_t i = 1; i < len; ++i)
  {
    if (arr[i] > max)
    {
      max = arr[i];
    }
  }
  return max;
}
 
//таймер
class SimpleTimer
{
public:
  SimpleTimer()
  {
    start = std::chrono::high_resolution_clock::now();
  }
  ~SimpleTimer()
  {
    end = std::chrono::high_resolution_clock::now();
    std::chrono::duration<double> dur = end - start;
    std::cout << "Time passed (in seconds): " << dur.count() << '\n' << '\n';
  }
private:
  std::chrono::time_point<std::chrono::steady_clock> start, end;
};
 
//сортировка подсчетом
void countingSort(int* arr, int N, int max)
{
  SimpleTimer t;
  int *c = new int[max + 1];
  for (int i = 0; i <= max; ++i)
  {
    c[i] = 0;
  }
  for (int i = 0; i < N; ++i)
  {
    c[arr[i]]++;
  }
  int k = 0;
  for (int i = 0; i <= max; ++i)
  {
    for (int j = 0; j < c[i]; ++j)
    {
      arr[k] = i;
      k++;
    }
  }
  delete [] c;
  std::cout << "coundting sort:\t";
}
int main()
{
  std::srand(std::time(NULL));
  const int a1Size = 8, a2Size = 7, a3Size = 10, a4Size = std::rand()%10000;
  std::cout << std::fixed << std::endl;
  int array1[a1Size] = { 2, 5, 3, 0, 2, 3, 0, 3 };
  std::cout << "average case countingSort(array1[8] = { 2, 5, 3, 0, 2, 3, 0, 3 }):\n ";
  countingSort(array1, a1Size, 5);
 
  int* array4 = new int[a4Size];
  randomArrayGenerator(array4, a4Size);
  int max = maxArrayElement(array4, a4Size);
  std::cout << "Length of the array: " << a4Size << "\nThe max element of the array: " << max << '\n';
  //for (int i = 0; i < a4Size;++i)
  //{
  //  std::cout << array4[i] << " , ";
  //}
  std::cout << '\n' << "after sort: \n";
  countingSort(array4, a4Size, max);
  //for (int i = 0; i < a4Size; ++i)
  //{
  //  std::cout << array4[i] << " , ";
  //}
  delete[] array4;
  return 0;
  }
0
Миниатюры
Как работает время в программе, почему сортировка массива на  1000 элементов быстрее, чем сортировка массива на 8?  
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.04.2020, 02:44
Ответы с готовыми решениями:

Алгоритм быстрой сортировки для двумерного массива. Получается, чем меньше столбцов, тем быстрее сортировка
Написал процедуру для сортировки двумерного массива. Для того, чтобы можно было менять число строк...

Сортировка выбором с обменом неотсортированного массива из 1000 элементов
#include &lt;stdio.h&gt; #define MAS 1000 void main(void) { int S; int P; int j = 0; int i =...

Сортировка Шелла быстрее чем Быстрая сортировка
В универе задали задание построить графики относительно скорости сортировок и размеров массивов....

Почему не работает сортировка массива в обратном порядке?
Почему не работает сортировка чисел в обратном порядке ? public static void main(String args)...

1
С чаем беда...
Эксперт CЭксперт С++
8498 / 4220 / 1169
Регистрация: 18.10.2014
Сообщений: 9,144
11.04.2020, 06:07 2
Лучший ответ Сообщение было отмечено eogenio777 как решение

Решение

Цитата Сообщение от eogenio777 Посмотреть сообщение
Как работает время в программе
"Тормозит" именно первый вызов вашей функции. Особенно динамическое выделение памяти через new[]. Поменяйте местами свои эксперименты и снова первый вызов будет требовать больше времени. На ваших входных данных это оказывает существенное значение. По этой причине не принято замерять время первых прогонов.

Замерьте вторые прогоны - и соотношение времен станет ожидаемым.

(Даже если устранить или "вынести за скобки" динамическое выделение памяти, эффект все равно сохранится, хоть и в существенно меньшей мере. Также может быть дело в начальной настройке каких-то процессорных механизмов: кэша памяти, предсказателя переходов и т.п. )

P.S. Ваша программа в общем случае не компилируема. std::chrono::high_resolution_clock::now() не обязан возвращать std::chrono::time_point<std::chrono::steady_clock>. Почему у вас пометки времени не объявлены просто как std::chrono::time_point<std::chrono::high_resolution_clock>. Откуда внезапно взялся steady_clock?
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.04.2020, 06:07

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Одномерные массивы. Вставка, удаление элементов массива. Перестановка элементов массива. Сортировка массива методом пузырька
Помогите пожалуйста! Дан массив, состоящий из N букв латинского алфавита а) Заполнить массив...


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.