ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / код-таймер
34 сообщений из 34, показаны все 2 страниц
  все  
код-таймер
    #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
| Ответить | Цитировать | Написать  
код-таймер
    #39997384
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
mini.weblab
где конкретно вами упомянутые погрешности повлияли на результат?
Данные интерполяции посмотрите. Если разброс между 0,02 и 0,11 это O(1), то я - пас.
Если "прыжки прыжка" это O(sqrt(n)), то я как-то по другому представлял себе функцию квадратного корня.
Собственно, асимптотику O(n) демонстрирует только линейный поиск.
Если что-то в ваших данных и похоже на O(1), то это, внезапно - бинарный поиск.
...
Рейтинг: 0 / 0
10.09.2020, 16:27
| Ответить | Цитировать | Написать  
код-таймер
    #39997422
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Basil A. Sidorov,
не принимается

1)
я не утверждаю, что clock() идеален, я утверждаю, что точности clock() вполне достаточно
Смотрю данные интерполяции:
(0.03, 0.04, 0.04, 0.02, 0.02, 0.03, 0.02, 0.11, 0.02, 0.02)
0.11 / 0.02 = 5
avg = 0.035

Данные показывают, что на равномерно распределенном массиве интерполяционный поиск показывает лучшие результаты. По теории, это будет О(1). И да погрешности есть и будут, но на результат они не повлияют.

2)
Бинарный поиск показал худшие результаты, чем интерполяция, поэтому не совсем понятно, почему он внезапно похож на О(1)
(разве что, если принять слово "внезапно" за ключевое...)

3)
Вы, наверное, внезапно удивитесь, но в показанных результатах нет ничего по асимптотике - массив фиксирован.
...
Рейтинг: 0 / 0
10.09.2020, 18:27
| Ответить | Цитировать | Написать  
код-таймер
    #39997474
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
теперь я включила в эксперимент точки, которые есть в массиве и точки, которых нет в массиве.
точки, которых в массиве нет оканчиваются на 50.

 
результаты
Код: 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.
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.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
 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.1400 | 
	 | Interpolation  |            0 |       0.0200 | 
	 | Jump           |            0 |       0.0300 | 
	 *----------------------------------------------*
	 | Linear         |       499950 |     298.9300 | 
	 | Binary         |       499950 |       0.1400 | 
	 | Interpolation  |       499950 |       0.0500 | 
	 | Jump           |       499950 |       1.0800 | 
	 *----------------------------------------------*
	 | Linear         |       999900 |      28.8200 | 
	 | Binary         |       999900 |       0.1400 | 
	 | Interpolation  |       999900 |       0.0300 | 
	 | Jump           |       999900 |       0.7900 | 
	 *----------------------------------------------*
	 | Linear         |      1499950 |     293.5500 | 
	 | Binary         |      1499950 |       0.1400 | 
	 | Interpolation  |      1499950 |       0.0400 | 
	 | Jump           |      1499950 |       1.1300 | 
	 *----------------------------------------------*
	 | Linear         |      1999900 |      57.4300 | 
	 | Binary         |      1999900 |       0.2000 | 
	 | Interpolation  |      1999900 |       0.0300 | 
	 | Jump           |      1999900 |       0.7100 | 
	 *----------------------------------------------*
	 | Linear         |      2499950 |     298.4900 | 
	 | Binary         |      2499950 |       0.1500 | 
	 | Interpolation  |      2499950 |       0.0600 | 
	 | Jump           |      2499950 |       1.4000 | 
	 *----------------------------------------------*
	 | Linear         |      2999900 |      88.4500 | 
	 | Binary         |      2999900 |       0.1200 | 
	 | Interpolation  |      2999900 |       0.0200 | 
	 | Jump           |      2999900 |       1.3300 | 
	 *----------------------------------------------*
	 | Linear         |      3499950 |     301.0200 | 
	 | Binary         |      3499950 |       0.1500 | 
	 | Interpolation  |      3499950 |       0.0400 | 
	 | Jump           |      3499950 |       1.5600 | 
	 *----------------------------------------------*
	 | Linear         |      3999900 |     117.8700 | 
	 | Binary         |      3999900 |       0.1500 | 
	 | Interpolation  |      3999900 |       0.0200 | 
	 | Jump           |      3999900 |       1.1100 | 
	 *----------------------------------------------*
	 | Linear         |      4499950 |     295.4800 | 
	 | Binary         |      4499950 |       0.1400 | 
	 | Interpolation  |      4499950 |       0.0500 | 
	 | Jump           |      4499950 |       1.5000 | 
	 *----------------------------------------------*
	 | Linear         |      4999900 |     147.9500 | 
	 | Binary         |      4999900 |       0.0200 | 
	 | Interpolation  |      4999900 |       0.0400 | 
	 | Jump           |      4999900 |       0.8700 | 
	 *----------------------------------------------*
	 | Linear         |      5499950 |     296.7100 | 
	 | Binary         |      5499950 |       0.1400 | 
	 | Interpolation  |      5499950 |       0.0500 | 
	 | Jump           |      5499950 |       1.7400 | 
	 *----------------------------------------------*
	 | Linear         |      5999900 |     181.8600 | 
	 | Binary         |      5999900 |       0.1500 | 
	 | Interpolation  |      5999900 |       0.0400 | 
	 | Jump           |      5999900 |       1.6700 | 
	 *----------------------------------------------*
	 | Linear         |      6499950 |     296.7000 | 
	 | Binary         |      6499950 |       0.2100 | 
	 | Interpolation  |      6499950 |       0.0400 | 
	 | Jump           |      6499950 |       1.7500 | 
	 *----------------------------------------------*
	 | Linear         |      6999900 |     206.3900 | 
	 | Binary         |      6999900 |       0.1400 | 
	 | Interpolation  |      6999900 |       0.0200 | 
	 | Jump           |      6999900 |       1.4800 | 
	 *----------------------------------------------*
	 | Linear         |      7499950 |     296.3500 | 
	 | Binary         |      7499950 |       0.1500 | 
	 | Interpolation  |      7499950 |       0.0500 | 
	 | Jump           |      7499950 |       2.0700 | 
	 *----------------------------------------------*
	 | Linear         |      7999900 |     238.2800 | 
	 | Binary         |      7999900 |       0.1200 | 
	 | Interpolation  |      7999900 |       0.0200 | 
	 | Jump           |      7999900 |       1.1600 | 
	 *----------------------------------------------*
	 | Linear         |      8499950 |     294.9300 | 
	 | Binary         |      8499950 |       0.1300 | 
	 | Interpolation  |      8499950 |       0.0400 | 
	 | Jump           |      8499950 |       2.0400 | 
	 *----------------------------------------------*
	 | Linear         |      8999900 |     268.3700 | 
	 | Binary         |      8999900 |       0.2000 | 
	 | Interpolation  |      8999900 |       0.0200 | 
	 | Jump           |      8999900 |       2.0000 | 
	 *----------------------------------------------*
	 | Linear         |      9499950 |     297.6300 | 
	 | Binary         |      9499950 |       0.1500 | 
	 | Interpolation  |      9499950 |       0.0400 | 
	 | Jump           |      9499950 |       2.3900 | 
	 *----------------------------------------------*

 Search Algorithms Average Performance Results (On Uniform Data Array of Length 100000) 
	 *-------------------------------*
	 | Algorithm      | Run Time,mcs | 
	 *-------------------------------*
	 | Linear         |     215.2615 | 
	 | Binary         |       0.1440 | 
	 | Interpolation  |       0.0360 | 
	 | Jump           |       1.3905 | 
	 *-------------------------------*
...
Рейтинг: 0 / 0
10.09.2020, 21:36
| Ответить | Цитировать | Написать  
код-таймер
    #39997514
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
mini.weblab
Данные показывают, что на равномерно распределенном массиве интерполяционный поиск показывает лучшие результаты. По теории, это будет О(1).
"Лучшие результаты" и "по теории это будет O(1)" - вообще никак не связано.
Пример: при поиске минимального значения в отсортированном по возрастанию списке лучшие результаты будут у линейного поиска, который обнаружит искомое за одно сравнение.3) Вы, наверное, внезапно удивитесь, но в показанных результатах нет ничего по асимптотике - массив фиксирован.Внезапно - есть. Для линейного поиска. "Магия данных". Ну или алгоритма, если вам будет угодно.
Если взять отсортированные по возрастанию массивы разных размеров с одинаковыми начальными значениями, искать в них одно и то же, существующее во всех массивах значение, то время поиска зависит только от этого значения, а не от размера массива.

Для бинарного и интерполяционного алгоритмов время должно быть константным.
Бинарный поиск на вашем массиве будет делать около семнадцати сравнений, кроме некоторых значений при некоторой реализации алгоритма.
Число сравнений в интерполяционном поиске должно быть примерно постоянным (иначе бы он не был O(1)), а значит и его время должно быть фиксировано.

Т.е. с одной стороны, вы, вроде как, понимаете, что асимптотика поиска не определяется по прогонам на массиве одного и того же размера, а с другой стороны, почему-то, ранжируете асимптотику алгоритмов именно по таким прогонам. Когда же я указал на это противоречие, то оказался "виноват" в незнании элементарных вещей.
Немного смахивает на демагогию. Нет? Или вы опять смахнёте в другую сторону?

P.S.
Подумайте над цитатой из мелкомягкой документации "микросекундное разрешение , но не микросекундная точность ".
...
Рейтинг: 0 / 0
11.09.2020, 07:07
| Ответить | Цитировать | Написать  
код-таймер
    #39997520
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
mini.weblab
точки, которых в массиве нет оканчиваются на 50.
Исходя из банальной логики видно, что (линейный) поиск несуществующих значений выполняется константное время. И даже это время плавает на единицы миллисекунд. Страшно представить, что вы там меряете на десятых и сотых миллисекунды.
...
Рейтинг: 0 / 0
11.09.2020, 07:35
| Ответить | Цитировать | Написать  
код-таймер
    #39997801
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Basil A. Sidorov
mini.weblab
точки, которых в массиве нет оканчиваются на 50.
Исходя из банальной логики видно, что (линейный) поиск несуществующих значений выполняется константное время. И даже это время плавает на единицы миллисекунд. Страшно представить, что вы там меряете на десятых и сотых миллисекунды.


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

2)
Я ничего не измеряю до сотых микросекунды, я изпользую статистические оценки (которые я при желании могу улучшить).
...
Рейтинг: 0 / 0
11.09.2020, 20:59
| Ответить | Цитировать | Написать  
код-таймер
    #39997807
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
а теперь я буду не соглашаться!

Basil A. Sidorov

"Лучшие результаты" и "по теории это будет O(1)" - вообще никак не связано.

В этом как раз суть эксперимента, и это часть валидации алгоритмов: сравнить ожидаемые (по теории результаты) с результатами полученными по факту.
Пример: при поиске минимального значения в отсортированном по возрастанию списке лучшие результаты будут у линейного поиска, который обнаружит искомое за одно сравнение.

Это лучший результат для локальной точки, и это не интересно. Интерполяционный поиск показывает лучшие результаты на всем равномерном массиве, и, признайтесь, вы этого не знали. :-)
Если взять отсортированные по возрастанию массивы разных размеров с одинаковыми начальными значениями, искать в них одно и то же, существующее во всех массивах значение, то время поиска зависит только от этого значения, а не от размера массива.

Да? А теория утверждает нечто противоположное.

[0, 10101]
[0, 1, 2, ..., 10009, 10101, ..., 15000]
нужно найти число 10101 :-)
Для бинарного и интерполяционного алгоритмов время должно быть константным.

Бинарный алгоритм позиционно зависимый, с наихудшей оценкой выполнения О(sqrt(N)).
Число сравнений в интерполяционном поиске должно быть примерно постоянным (иначе бы он не был O(1)), а значит и его время должно быть фиксировано.

Оно и по результатам близко к постоянному, но как вы ранее справедливо упомянули, временная оценка в эксперименте очень грубая. Т.е. используя эту оценку я могу сравнить время выполнения бинарного поиска и время выполнения интерполяционного поиска: если я сравниваю объект весом в 10кг с объектом в 5мг, мне будет достаточно весов, взвешивающих с точностью до 1 кг.
Т.е. с одной стороны, вы, вроде как, понимаете, что асимптотика поиска не определяется по прогонам на массиве одного и того же размера, а с другой стороны, почему-то, ранжируете асимптотику алгоритмов именно по таким прогонам. Когда же я указал на это противоречие, то оказался "виноват" в незнании элементарных вещей.
Немного смахивает на демагогию. Нет? Или вы опять смахнёте в другую сторону?

Нет, не верно. Вы неправильно поняли суть эксперимента: я сравниваю и оцениваю 3 позиционно зависимых алгоритма, и я показываю это в результатах, это важно.
...
Рейтинг: 0 / 0
11.09.2020, 21:39
| Ответить | Цитировать | Написать  
код-таймер
    #39997892
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
mini.weblab
Да? А теория утверждает нечто противоположное.
[0, 10101]
[0, 1, 2, ..., 10009, 10101, ..., 15000]
нужно найти число 10101 :-)
А теперь - внимательно перечитайте моё определение и сравните его с вашим примером.
Бинарный алгоритм позиционно зависимый, с наихудшей оценкой выполнения О(sqrt(N)).Хреново вы теорию знаете ...
Ну или думаете как-то неправильно.и я показываю это в результатах, это важно."Сама меряет. Было что мерять - сказал Остап передавая слесарю астролябию".
...
Рейтинг: 0 / 0
12.09.2020, 10:05
| Ответить | Цитировать | Написать  
код-таймер
    #39997929
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
куда уж мне до "эксперта" вроде вас...
...
Рейтинг: 0 / 0
12.09.2020, 15:36
| Ответить | Цитировать | Написать  
34 сообщений из 34, показаны все 2 страниц
  все  
Форумы / C++ [игнор отключен] [закрыт для гостей] / код-таймер
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=57&tid=2017337]:
 0ms
get settings:
 11ms
get forum list:
 16ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 156ms
get topic data:
 13ms
get forum data:
 3ms
get page messages:
 75ms
get tp. blocked users:
 2ms
others: 12ms
total:  296ms
созд. / загр.: 296ms
x
x
Закрыть


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