Гость
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Jump Search Algorithm: ошибка в псевдокоде / 25 сообщений из 62, страница 1 из 3
31.08.2020, 23:27
    #39994273
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Jump Search псевдокод из учебника по Алгоритмам и Структурам данных
Код: 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.
JUMP_SEARCH (A, lower_bound, upper_bound, VAL, N)

Step 1: [INITIALIZE] SET STEP = sqrt(N), I = 0, LOW = lower_bound, HIGH = upper_bound, POS = –1
Step 2: Repeat Step 3 while I < STEP
Step 3:     
	IF VAL < A[STEP]	
		SET HIGH = STEP – 1
	    ELSE		
		SET LOW = STEP + 1
            [END OF IF]
	    SET I = I + 1
        [END OF LOOP]
Step 4: SET I = LOW
Step 5: Repeat Step 6 while I <= HIGH
Step 6:
		IF A[I] = Val
			POS = I
			PRINT POS
			Go to Step 8
		[END OF IF]
		SET I = I + 1
	[END OF LOOP]
Step 7: IF POS = –1
		PRINT "VALUE IS NOT PRESENT IN THE ARRAY"
	[END OF IF]
Step 8: EXIT


я думаю, что алгоритм в учебнике реализован не верно, что думаете вы?
https://en.wikipedia.org/wiki/Jump_search
:-)
...
Рейтинг: 0 / 0
01.09.2020, 14:50
    #39994496
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Я думаю, что неплохо привести пример, результат прогона и на ЯП.
...
Рейтинг: 0 / 0
01.09.2020, 14:57
    #39994500
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Бремя доказательства - на утверждающем.
...
Рейтинг: 0 / 0
01.09.2020, 15:05
    #39994507
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
насколько я понимаю, Jump Search - это про задачу с небоскребом и 2 шариками, где надо выяснить, с какого этажа шарик разбивается. То есть для минимизации худшего случая брать sqrt(N) не совсем верно
...
Рейтинг: 0 / 0
01.09.2020, 15:50
    #39994534
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
выше я привела ссылку на алгоритм из Вики.
вот что пишет автор учебника:
автор учебникаWhen we have an already sorted list, then the other efficient algorithm to search for a value is jump
search or block search. In jump search, it is not necessary to scan all the elements in the list to
find the desired value. We just check an element and if it is less than the desired value, then some
of the elements following it are skipped by jumping ahead. After moving a little forward again,
the element is checked. If the checked element is greater than the desired value, then we have
a boundary and we are sure that the desired value lies between the previously checked element
and the currently checked element. However, if the checked element is less than the value being
searched for, then we again make a small jump and repeat the process.

Once the boundary of the value is determined, a linear search is done to find the value and its
position in the array.

For example, consider an array a[] = {1,2,3,4,5,6,7,8,9} . The length of the
array is 9. If we have to find value 8 then following steps are performed using the jump search
technique.

Step 1: First three elements are checked. Since 3 is smaller than 8, we will have to make a
jump ahead

Step 2: Next three elements are checked. Since 6 is smaller than 8, we will have to make a
jump ahead

Step 3: Next three elements are checked. Since 9 is greater than 8, the desired value lies
within the current boundary

Step 4: A linear search is now done to find the value in the array.

имхо, автор забыл, что нужно "прыгать"
...
Рейтинг: 0 / 0
01.09.2020, 15:53
    #39994536
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
у меня наблюдение: к концу книги становится все больше и больше опечаток
(т.е. получается, что до конца дочитывают немногие)
...
Рейтинг: 0 / 0
01.09.2020, 17:44
    #39994571
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Про книгу не знаю. А "про задачу с небоскребом и 2 шариками" мы зде же как-то решали на горизонте 1 - 1,5 года.
...
Рейтинг: 0 / 0
01.09.2020, 17:49
    #39994575
Leonid Kudryavtsev
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
mini.weblab

имхо, автор забыл, что нужно "прыгать"

почему?
первый цикл - прыгает
второй цикл - linear search

все в соответствии с процетированым английским текстом

не очень понятно, зачем это нужно (когда есть двоичный поиск), ну это уже другой разговор
...
Рейтинг: 0 / 0
01.09.2020, 18:03
    #39994583
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Техническое обоснование

wikiThe advantage over the latter is that a jump search only needs to jump backwards once,
while a binary can jump backwards up to log n times. This can be important if a jumping
backwards takes significantly more time than jumping forward.
Я себе понимаю так.

У нас есть некое техническое устройство со специфичными характеристиками доступа.
Например. Магнитная лента на катушке. Стриммер. Проволока на катушке (в авиационном самопицсе).

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

Ну а наша юная сишница еще не знакома с такой техникой... да и не будет никогда
знакома. Вот у нее и возникают разные вопросы.

Вообще если читать Дональда Кнута (очень нудное времяпровождение) там будут
отсылки к виртуальному вычислителю MMIX и к накопителям на лентах.
...
Рейтинг: 0 / 0
01.09.2020, 19:04
    #39994608
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Leonid Kudryavtsev,

в том-то и дело, что нет: прыжок происходит только один раз в sqrt(n).
по идее прыжки в первом цикле должны происходить пока мы не наийдем нужное значение или число большее, чем искомое.

Вот что происходит в алгоритме из учебника


*) рассмотрим массив a[] = {0,1,2,3,4,5,6,7,8,9} и пусть искомое число будет 8 (как в примере)
*) low = 0; high = 8; step = 3; i = 0
*) Jump Loop:
1)
i = 0 < step = 3 -> True
val = 8 < arr[step] = arr[3] = 3 -> False
low = step + 1 = 3 + 1 = 4
i = i + 1 = 0 + 1 = 1

2)
i = 1 < step = 3 -> True
val = 8 < arr[step] = arr[3] = 3 -> False
low = step + 1 = 4
i = i + 1 = 0 + 1 = 2

3)
i = 2 < step = 3 -> True
val = 8 < arr[step] = arr[3] = 3 -> False
low = step + 1 = 4
i = i + 1 = 0 + 1 = 3

4)
i = 3 < step = 3 -> False -> we exit the loop
low = 3
и дальше мы с помощью линейного поиска проверяем все позиции от arr[3] до arr[9] в поисках нужного знчения
это неверно, и это не то, что должен делать JumpSearch, обратите внимание на количество операций нужное для реализации алгоритма (их 10, т.е фактически это не лучше, чем линейный поиск!)

в вики, например, все происходите следующим образом (и это правильно):
Код: plaintext
1.
2.
3.
4.
5.
n - size of ordered list (or array)
low = 0, high = sqrt(n);
if val < arr[high] 
    low = high + 1;
    high = high + sqrt(n)

и прыжки длиной в sqrt(n) происходят до тех пор, пока val не станет больше или равно arr[high] или пока low не станет больше чем n.
...
Рейтинг: 0 / 0
01.09.2020, 19:31
    #39994617
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Исходник и пример с результатом в студио!
Хоть на барсике. Ангийские слова, да и другие тоже, не всегда однозначно переводятся на ЯП.
...
Рейтинг: 0 / 0
01.09.2020, 19:43
    #39994619
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
exp98,
в книге только псевдокод. и свой код нужно писать по псевдокоду.
(у меня нет проблем с написанием кода по псевдокоду, проблема в том, что я думаю, что псевдокод не верен)
...
Рейтинг: 0 / 0
01.09.2020, 19:46
    #39994622
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
mini.weblab
exp98,
в книге только псевдокод. и свой код нужно писать по псевдокоду.
(у меня нет проблем с написанием кода по псевдокоду, проблема в том, что я думаю, что псевдокод не верен)

Не надо думать. Пиши модульный тест который подтверждает что твой код имеет такие-то и такие-то свойства
на рандомных исходных данных.
...
Рейтинг: 0 / 0
01.09.2020, 19:53
    #39994625
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Вот да, в данном случае надо стать компилятором/интерпретатором ... как бы это ни было противно. Мне, например, это делать противно.
...
Рейтинг: 0 / 0
01.09.2020, 19:59
    #39994626
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
mayton,
тут модульный тест не поможет :)
т.к. даже "неправильный" алгоритм найдет число в массиве (если оно там есть), и не найдет, если его там нет.

некорректность алгоритма можно доказать
а) методом подсчета шагов цикла (это можно сделать прямо в псевдокоде)
б) сравнив ран-тайм "верного" алгоритма с ран-таймом алгоритма из книги
(например, мы можем принять алгоритм из вики за "верный")
...
Рейтинг: 0 / 0
01.09.2020, 20:07
    #39994627
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
ну exp98,
в данном случае это необходимо, потому что речь идет о корректности/некорректности логики решения
(сначала планируем - потом пишем) :-)
...
Рейтинг: 0 / 0
01.09.2020, 20:24
    #39994630
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
mini.weblab
в данном случае это необходимо,
Понятно. Загвоздка в том, что не хочется. Тоже понятно. Если уверена на 101%, можешь не проверять,но как бы потом не вылезло.
Что до меня, я лично сначала решил, что в книге алгоритм, к-рый даёт ош поиска. Тогда д.б. пример на эту ошибку.
Теперь же я не понимаю, о чём речь?
То ли обошибочном поиске?
То ли авторский код не соответствует его же декларации. Но формализованной!
То ли авторский код не соответствует викишной декларации, но ищет правильно.
То ли скорость просто не та?..
...
Лично мне всё равно. В книгах нередки и ошибки , и опечатки, я тоже сталкивался. Из книги нельзя копи-паст без отладки.
...
Рейтинг: 0 / 0
01.09.2020, 23:07
    #39994654
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
mini.weblab
mayton,
тут модульный тест не поможет :)
т.к. даже "неправильный" алгоритм найдет число в массиве (если оно там есть), и не найдет, если его там нет.

Там-же критерий есть. Я-же говорил как о тестировании свойства алгоритма. Как property-based testing.
Вот у него должно быть свойство. На любых данных - дает не более 1 прыжка назад.

Вот и проверяй. Затолкни в него миллион рандомных данных.

А ты как хотела? Заглянуть честным взглядом в глаза? И пообещать что алгоритм правильный?
...
Рейтинг: 0 / 0
02.09.2020, 11:02
    #39994710
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
mayton,
вопрос адресован в первую очередь к тем кто может понять псевдокод и сравнить с кодом приведенным в Вики
...
Рейтинг: 0 / 0
02.09.2020, 11:18
    #39994715
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
mini.weblab
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
Step 2: Repeat Step 3 while I < STEP
Step 3:     
	IF VAL < A[STEP]	
		SET HIGH = STEP – 1
	    ELSE		
		SET LOW = STEP + 1
            [END OF IF]
	    SET I = I + 1
        [END OF LOOP]
тут какая-то непонятная хрень.
зачем 3 шаг повторять, если переменная STEP не меняется?
что-то забыто, в общем.
...
Рейтинг: 0 / 0
02.09.2020, 11:46
    #39994728
Имя пользователя1
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
mini.weblab
к тем кто может понять псевдокод
как ты вообще читаешь книгу по алгоритмам, не понимая тамошний псевдокод?
...
Рейтинг: 0 / 0
02.09.2020, 12:23
    #39994746
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Имя пользователя1,

да обыкновенно, беру книгу и читаю, а если что-то непонятно, спрашиваю на sql.ru
...
Рейтинг: 0 / 0
02.09.2020, 12:35
    #39994750
mini.weblab
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Имя пользователя1тут какая-то непонятная хрень.
зачем 3 шаг повторять, если переменная STEP не меняется?
что-то забыто, в общем.
с этим я согласна
...
Рейтинг: 0 / 0
02.09.2020, 12:39
    #39994751
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Начните переводить потихоньку на С++ с комментариями. И все прояснится.

P.S. Язык определяет сознание.
...
Рейтинг: 0 / 0
02.09.2020, 12:52
    #39994757
exp98
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Jump Search Algorithm: ошибка в псевдокоде
Копи-пасты - они такие копи-пасты. Возможно, что автор хотел здесь
Код: vbnet
1.
IF VAL < A[STEP]

написать A[i]. Но тогда и массив должен с 0 начинаться. Но я сильно не всматривался, так что могу и ошибаться.
...
Рейтинг: 0 / 0
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Jump Search Algorithm: ошибка в псевдокоде / 25 сообщений из 62, страница 1 из 3
Целевая тема:
Создать новую тему:
Автор:
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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