ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / код-таймер
25 сообщений из 34, страница 1 из 2
  1  все
код-таймер
    #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:07
| Ответить | Цитировать | Написать  
код-таймер
    #39995272
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
передавать параметры в структуре
тогда "определенный тип" будет просто search_algorithm(void *)

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

IMHO

p.s. если в С++ есть лямбды, возможно можно с помощью их. Но я так не умею
...
Рейтинг: 0 / 0
03.09.2020, 16:22
| Ответить | Цитировать | Написать  
код-таймер
    #39995274
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Leonid Kudryavtsev,
спасибо, попробую использовать структуру
...
Рейтинг: 0 / 0
03.09.2020, 16:31
| Ответить | Цитировать | Написать  
код-таймер
    #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, 16:35
| Ответить | Цитировать | Написать  
код-таймер
    #39995289
PetroNotC Sharp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
PetroNotC Sharp
Участник
mini.weblab,
Как обобщить сказали.
Главное не потеряй читабельность кода при обобщении.
...
Рейтинг: 0 / 0
03.09.2020, 17:18
| Ответить | Цитировать | Написать  
код-таймер
    #39995369
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Судя по документации clock() возвращает число тиков которое надо делить на CLOCKS_PER_SEC чтоб получить
секунды. И делитель этот достаточно большой порядка миллиона. Тоесть мы имеем дело со счетчиком микросекунд.
С одной стороны это хорошо. С другой стороны такая точноть нужна при работе с сетью например. Но с алгоритмами
- нет. Например если ты намеряла 20 клоков. Алгоритм слишком быстро отработал.
А гранулярность планировщика процессов мультизадачности
во много раз превышает этот интервал - то твои измерения будут фейком. Тоесть они будут наполнены
большой случайной погрешностью которую надо как-то объяснить.

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

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

Вобщем лучше отказаться от этого клока и взять что-то более спокойное. Текущее время в милисекундах
будет практически полезнее.
...
Рейтинг: 0 / 0
03.09.2020, 20:31
| Ответить | Цитировать | Написать  
код-таймер
    #39995384
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Dimitry Sibiryakov,
спасибо, это я тоже возьму на заметку
...
Рейтинг: 0 / 0
03.09.2020, 21:20
| Ответить | Цитировать | Написать  
код-таймер
    #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, 21:55
| Ответить | Цитировать | Написать  
код-таймер
    #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:29
| Ответить | Цитировать | Написать  
код-таймер
    #39995399
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Она пока - на чистых сях. Без плюсов.
...
Рейтинг: 0 / 0
03.09.2020, 22:39
| Ответить | Цитировать | Написать  
код-таймер
    #39995403
Фотография Изопропил
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Изопропил
Участник
У винды свой хайрез таймер есть - https://docs.microsoft.com/en-us/windows/win32/sysinfo/acquiring-high-resolution-time-stamps
...
Рейтинг: 0 / 0
03.09.2020, 22:57
| Ответить | Цитировать | Написать  
код-таймер
    #39995405
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Anatoly Moskovsky,
спасибо, нашла :-)
...
Рейтинг: 0 / 0
03.09.2020, 23:00
| Ответить | Цитировать | Написать  
код-таймер
    #39995424
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Leonid Kudryavtsev
Участник
вроде еще есть счетчики процессора, как раз для замера времени работы кода.
...
Рейтинг: 0 / 0
04.09.2020, 00:00
| Ответить | Цитировать | Написать  
код-таймер
    #39995456
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
clock() в MSVC и в GCC работает по-разному. В MSVC возвращает время прошедшее с момента запуска программы. В GCC сколько процессорного времени использовано, причем даже если в коде нет никаких пауз и выполняется он на одном из ничем незагруженных ядер, то clock() возвращает меньше чем реально прошло, возможно приостанавливается во время дисковых операций.
...
Рейтинг: 0 / 0
04.09.2020, 07:26
| Ответить | Цитировать | Написать  
код-таймер
    #39995969
rdb_dev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
rdb_dev
Участник
TimeStampCounter
22140467
...
Рейтинг: 0 / 0
06.09.2020, 01:17
| Ответить | Цитировать | Написать  
код-таймер
    #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
07.09.2020, 15:19
| Ответить | Цитировать | Написать  
код-таймер
    #39997107
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mini.weblab,

Какие выводы?
...
Рейтинг: 0 / 0
09.09.2020, 23:36
| Ответить | Цитировать | Написать  
код-таймер
    #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, 12:51
| Ответить | Цитировать | Написать  
код-таймер
    #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, 13:20
| Ответить | Цитировать | Написать  
код-таймер
    #39997281
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mayton,

у меня нет цели точно измерить время выполнения функции/алгоритма.
я решаю другую задачу: сравниваю производительность алгоритмов между собой, поэтому для меня точное измерение времени исполнения функции вторично.
...
Рейтинг: 0 / 0
10.09.2020, 14:24
| Ответить | Цитировать | Написать  
код-таймер
    #39997285
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ты думаешь я вот такой злой mayton просто пристал к тебе? Да ради бога. Меряй дальше. Неужели я буду хватать тебя за руку.
...
Рейтинг: 0 / 0
10.09.2020, 14:29
| Ответить | Цитировать | Написать  
код-таймер
    #39997289
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
mini.weblab
для меня точное измерение времени исполнения функции вторично
... а погрешность измерения и асимптотика - нет.
...
Рейтинг: 0 / 0
10.09.2020, 14:32
| Ответить | Цитировать | Написать  
код-таймер
    #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:02
| Ответить | Цитировать | Написать  
код-таймер
    #39997322
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
mini.weblab
я думаю
Это пока лишнее.
Надо заняться (само)образованием и (у)знать о существовании случайной и систематической погрешности. Ну и понимать разницу между абсолютной и относительной погрешностями.
...
Рейтинг: 0 / 0
10.09.2020, 15:08
| Ответить | Цитировать | Написать  
код-таймер
    #39997333
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Basil A. Sidorov,
(вы говорите как exp98 = сотрясание воздуха ни о чем)
где конкретно вами упомянутые погрешности повлияли на результат?
...
Рейтинг: 0 / 0
10.09.2020, 15:24
| Ответить | Цитировать | Написать  
25 сообщений из 34, страница 1 из 2
  1  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / код-таймер
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=57&fpage=6&tid=2017337]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 76ms
get topic data:
 14ms
get forum data:
 3ms
get page messages:
 63ms
get tp. blocked users:
 2ms
others: 12ms
total:  200ms
созд. / загр.: 200ms
x
x
Закрыть


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