ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / код-таймер
9 сообщений из 34, страница 2 из 2
  2  все
код-таймер
    #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
| Ответить | Цитировать | Написать  
9 сообщений из 34, страница 2 из 2
  2  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / код-таймер
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=57&gotonew=1&tid=2017337]:
 0ms
get settings:
 11ms
get forum list:
 13ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 161ms
get topic data:
 10ms
get first new msg:
 6ms
get forum data:
 3ms
get page messages:
 52ms
get tp. blocked users:
 2ms
others: 248ms
total:  512ms
созд. / загр.: 512ms
x
x
Закрыть


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