Гость
Войти | Профиль | Очистить
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / код-таймер / 25 сообщений из 34, страница 1 из 2
  1  все
03.09.2020, 16:07
    #39995267
mini.weblab
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
написала таймер, для измерения ран-таймов функций алгоритмов поиска, но пока что, он умеет работать только с функциями определенного типа, можно ли сделать что-то более общее? как?

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#include <stdio.h>
#include <time.h>
#include "search.h"

double code_timer( int *arr, int arr_size, int val, int nrun,
		int *(*search_algorithm)(int *arr, int arr_size, int val) )
{
	double interval = 0;
	clock_t start, end;

	start = clock();
	/* Code under Test */
	for (int j = 0; j < nrun; j++) {
		(*search_algorithm)(arr, arr_size, val);
	}
	/* End of Code under Test */
	end = clock();
	interval = (double)(end - start) / (double)(nrun) / (double) CLOCKS_PER_SEC * 1000.0;
    return interval; // in milliseconds (ms)
}
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 16:22
    #39995272
Leonid Kudryavtsev
Leonid Kudryavtsev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
передавать параметры в структуре
тогда "определенный тип" будет просто search_algorithm(void *)

для C++, можно ф-цию передалать в класс. Для каждого алгоритма свой класс содержащий параметры + виртуальная ф-ция

IMHO

p.s. если в С++ есть лямбды, возможно можно с помощью их. Но я так не умею
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 16:31
    #39995274
mini.weblab
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
Leonid Kudryavtsev,
спасибо, попробую использовать структуру
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 16:35
    #39995276
Dimitry Sibiryakov
Dimitry Sibiryakov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
mini.weblabможно ли сделать что-то более общее? как?

Если не извращаться со всякими темплейтами, то проще всего макрос:
Код: sql
1.
#define MEASURE(it) { timer_start(), it, timer_end(); }


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 17:18
    #39995289
PetroNotC Sharp
PetroNotC Sharp
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
mini.weblab,
Как обобщить сказали.
Главное не потеряй читабельность кода при обобщении.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 20:31
    #39995369
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
Судя по документации clock() возвращает число тиков которое надо делить на CLOCKS_PER_SEC чтоб получить
секунды. И делитель этот достаточно большой порядка миллиона. Тоесть мы имеем дело со счетчиком микросекунд.
С одной стороны это хорошо. С другой стороны такая точноть нужна при работе с сетью например. Но с алгоритмами
- нет. Например если ты намеряла 20 клоков. Алгоритм слишком быстро отработал.
А гранулярность планировщика процессов мультизадачности
во много раз превышает этот интервал - то твои измерения будут фейком. Тоесть они будут наполнены
большой случайной погрешностью которую надо как-то объяснить.

Поэтому мерять алгоритмы надо не микро-секундами а минутами. Алгоритм должен работать дооооооолго.

И общий полный цикл этого клока со сбросом составляет 72 минуты. Это слишком мало. Велика вероятность
что ты случайно проскочишь через циклический сброс и цифры снова будут фейком. И надо будет объяснять
почему время старта в микросекундах больше чем время финиша.

Вобщем лучше отказаться от этого клока и взять что-то более спокойное. Текущее время в милисекундах
будет практически полезнее.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 21:20
    #39995384
mini.weblab
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
Dimitry Sibiryakov,
спасибо, это я тоже возьму на заметку
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 21:55
    #39995389
mini.weblab
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
mayton,

1) в С у меня есть 2 опции: использовать либо time, либо clock
time_t позволяет измерить время с точнстью до секунд, т.е. это опция не подойдет
clock использует процессорное время, которое замеряется с точнстью до микросекунд, и это то, что рекомендуется к использованию
для измерения скорости выполнения программ.

2) мне не нужно точно замерять время выполнения алгоритма, мне нужно только сравнить время выполнения разных алгоритмов, и каждый из алгоритмов будет иметь случайную погрешность примерно одного и того же порядка.

3) Даже с такой погрешностью можно будет получить статисчески значимые результаты, потому что рассматриваются алгоритмы порядка N, sqrt(N), log(N).
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 22:29
    #39995398
Anatoly Moskovsky
Anatoly Moskovsky
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
mini.weblab
1) в С у меня есть 2 опции: использовать либо time, либо clock


Ну почему же.
Есть еще платформозависимые часы

Под Линуксом (да и практически везде кроме Винды):
Код: plaintext
1.
2.
3.
4.
5.
6.
double get_monotonic_time(void)
{
    struct timespec ts;
    clock_gettime(CLOCK_MONOTONIC, &ts);
    return ts.tv_sec + ts.tv_nsec/1e9;
}



Монотонные часы не имеют определенной базовой даты, но гарантируют неубывающие значения (и не зависят от смены часового пояса или других изменений системных часов).
Поэтому их удобно использовать в измерениях интервалов в разных тестах.

ЗЫ. В С++ есть платформонезависимый std::chrono::steady_clock::now() который делает то же самое.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 22:39
    #39995399
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
Она пока - на чистых сях. Без плюсов.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 22:57
    #39995403
Изопропил
Изопропил
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
У винды свой хайрез таймер есть - https://docs.microsoft.com/en-us/windows/win32/sysinfo/acquiring-high-resolution-time-stamps
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
03.09.2020, 23:00
    #39995405
mini.weblab
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
Anatoly Moskovsky,
спасибо, нашла :-)
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.09.2020, 00:00
    #39995424
Leonid Kudryavtsev
Leonid Kudryavtsev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
вроде еще есть счетчики процессора, как раз для замера времени работы кода.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
04.09.2020, 07:26
    #39995456
Dima T
Dima T
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
clock() в MSVC и в GCC работает по-разному. В MSVC возвращает время прошедшее с момента запуска программы. В GCC сколько процессорного времени использовано, причем даже если в коде нет никаких пауз и выполняется он на одном из ничем незагруженных ядер, то clock() возвращает меньше чем реально прошло, возможно приостанавливается во время дисковых операций.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
06.09.2020, 01:17
    #39995969
rdb_dev
rdb_dev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
TimeStampCounter
22140467
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
07.09.2020, 15:19
    #39996232
mini.weblab
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
вот что получилось на поисковых алгоритмах: линейный поиск, двоичный поиск, интерполяционный поиск, прыжковый поиск
 
Код: plaintext
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.
 Search Algorithms Performance Results at Check Points (On Uniform Data Array of Length 100000) 
	 *----------------------------------------------*
	 | Algorithm      |  Check Point | Run Time,mcs | 
	 *----------------------------------------------*
	 | Linear         |            0 |       0.0200 | 
	 | Binary         |            0 |       0.1500 | 
	 | Interpolation  |            0 |       0.0300 | 
	 | Jump           |            0 |       0.0300 | 
	 *----------------------------------------------*
	 | Linear         |       999900 |      28.1500 | 
	 | Binary         |       999900 |       0.1500 | 
	 | Interpolation  |       999900 |       0.0400 | 
	 | Jump           |       999900 |       0.8200 | 
	 *----------------------------------------------*
	 | Linear         |      1999900 |      59.7000 | 
	 | Binary         |      1999900 |       0.1300 | 
	 | Interpolation  |      1999900 |       0.0400 | 
	 | Jump           |      1999900 |       0.5200 | 
	 *----------------------------------------------*
	 | Linear         |      2999900 |      87.4200 | 
	 | Binary         |      2999900 |       0.1200 | 
	 | Interpolation  |      2999900 |       0.0200 | 
	 | Jump           |      2999900 |       1.3600 | 
	 *----------------------------------------------*
	 | Linear         |      3999900 |     115.4900 | 
	 | Binary         |      3999900 |       0.2000 | 
	 | Interpolation  |      3999900 |       0.0200 | 
	 | Jump           |      3999900 |       1.0700 | 
	 *----------------------------------------------*
	 | Linear         |      4999900 |     144.9400 | 
	 | Binary         |      4999900 |       0.0200 | 
	 | Interpolation  |      4999900 |       0.0300 | 
	 | Jump           |      4999900 |       0.9300 | 
	 *----------------------------------------------*
	 | Linear         |      5999900 |     174.1900 | 
	 | Binary         |      5999900 |       0.1300 | 
	 | Interpolation  |      5999900 |       0.0200 | 
	 | Jump           |      5999900 |       1.6000 | 
	 *----------------------------------------------*
	 | Linear         |      6999900 |     205.2000 | 
	 | Binary         |      6999900 |       0.1600 | 
	 | Interpolation  |      6999900 |       0.1100 | 
	 | Jump           |      6999900 |       1.4800 | 
	 *----------------------------------------------*
	 | Linear         |      7999900 |     236.1800 | 
	 | Binary         |      7999900 |       0.2300 | 
	 | Interpolation  |      7999900 |       0.0200 | 
	 | Jump           |      7999900 |       1.3400 | 
	 *----------------------------------------------*
	 | Linear         |      8999900 |     261.7600 | 
	 | Binary         |      8999900 |       0.1300 | 
	 | Interpolation  |      8999900 |       0.0200 | 
	 | Jump           |      8999900 |       2.0700 | 
	 *----------------------------------------------*

 Search Algorithms Average Performance Results (On Uniform Data Array of Length 100000) 
	 *-------------------------------*
	 | Algorithm      | Run Time,mcs | 
	 *-------------------------------*
	 | Linear         |     131.3050 | 
	 | Binary         |       0.1420 | 
	 | Interpolation  |       0.0350 | 
	 | Jump           |       1.1220 | 
	 *-------------------------------*
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.09.2020, 23:36
    #39997107
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
mini.weblab,

Какие выводы?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.09.2020, 12:51
    #39997236
mini.weblab
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
1) при сравнении алгоритмов будет достаточно функции clock() в качестве таймера
2) с этим тоже не соглашусь
авторПоэтому мерять алгоритмы надо не микро-секундами а минутами. Алгоритм должен работать дооооооолго.
3) у меня появился следующий вопрос
https://www.sql.ru/forum/1329005/ukazatel-na-funkciu-vozvrashhaushhuu-ukazatel-na-int
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.09.2020, 13:20
    #39997243
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
Хорошо. Не соглашайся со мной. Это тоже позиция.

А как ты сама для себя интерпретируешь эту величину? Будь то физика или любая другая наука. Экспериментатор должен
объяснить ее. Например если я мерял площадь обоев в своей комнате и увидел что они на порядок превышают площадь
моей команты по полу. Пересчитал. Нашел ошибку. В описании товара по рулону обоев был другой смысл.

Тоесть я нашел признак который мне подсказал что я ошибаюсь.

Интерполяционный алгоритм работал 0.035 микросекунды. Или 35 наносекунд. Время очень близко приближено
к предельным временам на которые способна реагировать оперативная память. Была реакция чтения одной ячейки?
Алгоритм прочитал 1 ячейку или кешлинию?

И я вообще сомневаюсь что современная мультизадачная операционка способна точно мерять такие интервалы.
Планировщик может твою задачу вытеснить в любую секунду. На минутах это незаметно. На нано-секундах
это парадоксы.

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
	 *-------------------------------*
	 | Algorithm      | Run Time,mcs | 
	 *-------------------------------*
	 | Linear         |     131.3050 | 
	 | Binary         |       0.1420 | 
	 | Interpolation  |       0.0350 | 
	 | Jump           |       1.1220 | 
	 *-------------------------------*
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.09.2020, 14:24
    #39997281
mini.weblab
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
mayton,

у меня нет цели точно измерить время выполнения функции/алгоритма.
я решаю другую задачу: сравниваю производительность алгоритмов между собой, поэтому для меня точное измерение времени исполнения функции вторично.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.09.2020, 14:29
    #39997285
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
Ты думаешь я вот такой злой mayton просто пристал к тебе? Да ради бога. Меряй дальше. Неужели я буду хватать тебя за руку.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.09.2020, 14:32
    #39997289
Basil A. Sidorov
Basil A. Sidorov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
mini.weblab
для меня точное измерение времени исполнения функции вторично
... а погрешность измерения и асимптотика - нет.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.09.2020, 15:02
    #39997317
mini.weblab
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
было учтено,
1) Мы сравниваем 4 алгоритма:
(а) Линейный поиск - производительность O(N); (b) Бинарный поиск - O( log2N ); (c) Интерполяция - O(1): данные распределены равномерно; (d) Прыжковый поиск: O(sqrt(N))
2) измерения проведены в 10 точках числовой прямой, точки распределены равномерно. Все контрольные точки принадлежат массиву, по которому ведется поиск
3) для оценки производительность алгоритма в точке каждый алгоритм запускался 100 раз, и ран-тайм вычислялся как среднее арифметическое.

не было учтено:
алгоритмы проверялись только на точках, существующих в массиве
точки, не принадлежащие массиву данных, я еще не проверяла

погрешность и асимптотика:
я думаю, что функция clock(), не смотря на все свои недостатки способна корректно сравнить
O(N) ~ O(sqrt(N)) ~ O( log2N ) ~ O(1)

 
результаты сравнения
Код: plaintext
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.
 Search Algorithms Performance Results at Check Points (On Uniform Data Array of Length 100000) 
	 *----------------------------------------------*
	 | Algorithm      |  Check Point | Run Time,mcs | 
	 *----------------------------------------------*
	 | Linear         |            0 |       0.0200 | 
	 | Binary         |            0 |       0.1500 | 
	 | Interpolation  |            0 |       0.0300 | 
	 | Jump           |            0 |       0.0300 | 
	 *----------------------------------------------*
	 | Linear         |       999900 |      28.1500 | 
	 | Binary         |       999900 |       0.1500 | 
	 | Interpolation  |       999900 |       0.0400 | 
	 | Jump           |       999900 |       0.8200 | 
	 *----------------------------------------------*
	 | Linear         |      1999900 |      59.7000 | 
	 | Binary         |      1999900 |       0.1300 | 
	 | Interpolation  |      1999900 |       0.0400 | 
	 | Jump           |      1999900 |       0.5200 | 
	 *----------------------------------------------*
	 | Linear         |      2999900 |      87.4200 | 
	 | Binary         |      2999900 |       0.1200 | 
	 | Interpolation  |      2999900 |       0.0200 | 
	 | Jump           |      2999900 |       1.3600 | 
	 *----------------------------------------------*
	 | Linear         |      3999900 |     115.4900 | 
	 | Binary         |      3999900 |       0.2000 | 
	 | Interpolation  |      3999900 |       0.0200 | 
	 | Jump           |      3999900 |       1.0700 | 
	 *----------------------------------------------*
	 | Linear         |      4999900 |     144.9400 | 
	 | Binary         |      4999900 |       0.0200 | 
	 | Interpolation  |      4999900 |       0.0300 | 
	 | Jump           |      4999900 |       0.9300 | 
	 *----------------------------------------------*
	 | Linear         |      5999900 |     174.1900 | 
	 | Binary         |      5999900 |       0.1300 | 
	 | Interpolation  |      5999900 |       0.0200 | 
	 | Jump           |      5999900 |       1.6000 | 
	 *----------------------------------------------*
	 | Linear         |      6999900 |     205.2000 | 
	 | Binary         |      6999900 |       0.1600 | 
	 | Interpolation  |      6999900 |       0.1100 | 
	 | Jump           |      6999900 |       1.4800 | 
	 *----------------------------------------------*
	 | Linear         |      7999900 |     236.1800 | 
	 | Binary         |      7999900 |       0.2300 | 
	 | Interpolation  |      7999900 |       0.0200 | 
	 | Jump           |      7999900 |       1.3400 | 
	 *----------------------------------------------*
	 | Linear         |      8999900 |     261.7600 | 
	 | Binary         |      8999900 |       0.1300 | 
	 | Interpolation  |      8999900 |       0.0200 | 
	 | Jump           |      8999900 |       2.0700 | 
	 *----------------------------------------------*

 Search Algorithms Average Performance Results (On Uniform Data Array of Length 100000) 
	 *-------------------------------*
	 | Algorithm      | Run Time,mcs | 
	 *-------------------------------*
	 | Linear         |     131.3050 | 
	 | Binary         |       0.1420 | 
	 | Interpolation  |       0.0350 | 
	 | Jump           |       1.1220 | 
	 *-------------------------------*
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.09.2020, 15:08
    #39997322
Basil A. Sidorov
Basil A. Sidorov
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
mini.weblab
я думаю
Это пока лишнее.
Надо заняться (само)образованием и (у)знать о существовании случайной и систематической погрешности. Ну и понимать разницу между абсолютной и относительной погрешностями.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
10.09.2020, 15:24
    #39997333
mini.weblab
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
код-таймер
Basil A. Sidorov,
(вы говорите как exp98 = сотрясание воздуха ни о чем)
где конкретно вами упомянутые погрешности повлияли на результат?
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / код-таймер / 25 сообщений из 34, страница 1 из 2
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
созд. / загр.: 299ms
Закрыть
start [/forum/topic.php?fid=57&mobile=1&tid=2017337]:
 0ms
get settings:
 8ms
get forum list:
 13ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 178ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 64ms
get tp. blocked users:
 2ms
others: 10ms
total:  299ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]