ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Jump Search Algorithm: ошибка в псевдокоде
25 сообщений из 62, страница 2 из 3
  2  все
Jump Search Algorithm: ошибка в псевдокоде
    #39994758
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
mayton
Язык определяет сознание.
Казниь нельзя помиловать.
...
Рейтинг: 0 / 0
02.09.2020, 12:53
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994764
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
При адаптации алгоритмов из книжек я замечал что многие из них написаны на диалектах Pascal/Modula/Delphi.
И в этих языках массивы могут начинаться не с 0 а с 1 и это создает некоторые трудности при механическом
переводе.

В данном диалекте массивы какие?
...
Рейтинг: 0 / 0
02.09.2020, 13:12
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994767
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
exp98
mayton
Язык определяет сознание.
Казниь нельзя помиловать.

Да вот как написано - так программист и переведет. Кстати даже такой пустяк
как извлечение квадратного корня с округлением в нижнюю сторону у меня
вызывает некую оторопь и размышления? Мы можем потерять в точности
конвертируясь int->double->sqlrt->int или не имеем права? Казалось-бы
пустяк но мне этот пустяк тоже интересен. Вобщем математики-теоретики
вам написало код без типов данных. И без контрактов. А вы уже дальше думайте.

Казнить или помиловать.
...
Рейтинг: 0 / 0
02.09.2020, 13:14
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994772
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Кстати, в 1-м цикле может нужно было написать SET LOW = STEP + iiiii и т.п. Но мне откровенно неохота.
Не забыть, что пользуемся упорядоченным массивом - это во первых словах автора.
...
Рейтинг: 0 / 0
02.09.2020, 13:21
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994773
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
mayton
Да вот как написано - так программист и переведет.
Точнее - переведёт каково у него сознание.
...
Рейтинг: 0 / 0
02.09.2020, 13:22
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994775
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Меня вообще удивляет что мы тратим так много времени на старый и никому не нужный алгоритм
поиска блоков на магнитофонной ленточке.

Неужели автору нет дела до других (более актуальных) алгоритмов и структур данных?
...
Рейтинг: 0 / 0
02.09.2020, 13:27
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994787
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Писала же - у неё есть план. Всё же это и полезная гимнастика. Я для этих упражнений откровенно ржавею. Так что небольшая встряска.
...
Рейтинг: 0 / 0
02.09.2020, 13:48
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994800
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mayton
Неужели автору нет дела до других (более актуальных) алгоритмов и структур данных?

существует всего 4 основных алгоритма поиска:
1) линейный поиск
2) двоичный поиск
3) поиск методом интерполяции
4) прыжковый (пошаговый) поиск (Jump Search)

у меня проблема возникла только с методом 4
...
Рейтинг: 0 / 0
02.09.2020, 14:35
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994803
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А хеш-поиск?
...
Рейтинг: 0 / 0
02.09.2020, 14:39
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994805
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mayton
А хеш-поиск?
в отсортированном массиве он никаким боком
...
Рейтинг: 0 / 0
02.09.2020, 14:41
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994818
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mayton,

хэш поиск = поиск по хэш ключу + линейный поиск
поиск по хэш ключу будет проведен по одному из 4х методов
...
Рейтинг: 0 / 0
02.09.2020, 14:56
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994822
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mini.weblab
хэш поиск = поиск по хэш ключу + линейный поиск
если хэш - некоторое целое число, то это будет индекс массива, где всё хранится, то есть уже никакого поиска не потребуется (хотя, если у некоторых значений совпал хэш, то это будет коллизия и там придется поискать). В этом идея хэш-словаря.
...
Рейтинг: 0 / 0
02.09.2020, 15:00
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994850
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Чтобы не открывать новуютему, спрошу здесь.
Есть фрагмент и некий комментарий к нему. Чего я не понимаю?
mini.weblab
в вики, например, все происходите следующим образом (и это правильно):
Код: 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.
Есть фраза "пока val не станет".
Разве val не константа?
Если val < arr[high] затем мы прибавляем low = high + 1; ....
а) подразумевается убывающее упорядочивание.
б) А где обрабатывается случай val == arr[high] ?
...
Рейтинг: 0 / 0
02.09.2020, 15:46
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994854
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mini.weblab
mayton,

хэш поиск = поиск по хэш ключу + линейный поиск
поиск по хэш ключу будет проведен по одному из 4х методов

Мисс mini.weblab!

Мой комментарий касался утверждения о том что
существует всего 4 основных алгоритма поиска:
Я не знаю почему их всего 4. И почему алгоритм хеширования вдруг сюда не попал.
Разве поиск ключа в хеш-таблице это не поиск? Разве вероятностная проверка
в бит-карте Блума это не поиск? А вычисление квадратного корня? Разве это
не поиск точки на вещественной оси? А градиентный спуск это не поиск?
А обучение нейронной сети - разве это не поиск ее матрицы коэффициентов?
А генетический алгоритм? Разве это не поиск наилучшего вектора признаков
по заданной целевой функции?
...
Рейтинг: 0 / 0
02.09.2020, 15:50
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994860
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
exp98

и прыжки длиной в sqrt(n) происходят до тех пор, пока val не станет больше или равно arr[high] или пока low не станет больше чем n.
Есть фраза "пока val не станет".
Разве val не константа?
Если val < arr[high] затем мы прибавляем low = high + 1; ....
а) подразумевается убывающее упорядочивание.
б) А где обрабатывается случай val == arr[high] ?[/quot]

1) полный алгоритм вики можно найти по ссылке https://en.wikipedia.org/wiki/Jump_search
там все случаи обрабатываются
2) я привела только часть с прыжками, потому что именно она неправильно реализована в книге
3) по поводу констант, если быть точным, то нужно выполнение условия val = arr[high]
...
Рейтинг: 0 / 0
02.09.2020, 15:56
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994867
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Ну давайте блин. А то ведь пока первый не начнешь - никто не начинает.

Потихоньку. Шаг за шагом. С пониманием контракта. Можно даже сверять с линейным поиском.

Код: 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.
T jump_search(std::list<T> list) {
/*
algorithm JumpSearch is
    input: An ordered list L, its length n and a search key s.
    output: The position of s in L, or nothing if s is not in L.
    
    a &#8592; 0
    b &#8592; &#8970;&#8730;n&#8971;
    
    while Lmin(b,n)-1 < s do
        a &#8592; b
        b &#8592; b + &#8970;&#8730;n&#8971;
        if a &#8805; n then
            return nothing
    
    while La < s do
        a &#8592; a + 1
        if a = min(b, n)
            return nothing
    
    if La = s then
        return a
    else
        return nothing
*/
}
...
Рейтинг: 0 / 0
02.09.2020, 16:04
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994869
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mayton,
я говорю конкретно об алгоритмах поиска , а не о всех возможных алгоритмах
есть алгоритмы поиска (и их 4), а есть структуры данных, это не одно и тоже
не существует метода хэш-поиск, но зато существует структура данных - хэш таблица,
которая позволяет быстрый поиск данных по ключу. структуры данных как раз и
создаются для того, чтобы получить лучшие результаты, чем позволяют стандартные алгоритмы
...
Рейтинг: 0 / 0
02.09.2020, 16:11
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994873
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mayton,
с алгоритмом из вики проблем нет, там все норм.
проблема с алгоритмом в самом первом посте: там все будет находится правильно, но по скорости выполнения он будет не лучше, чем линейный поиск
...
Рейтинг: 0 / 0
02.09.2020, 16:16
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994875
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
mini.weblab
mayton,
с алгоритмом из вики проблем нет, там все норм.
проблема с алгоритмом в самом первом посте: там все будет находится правильно, но по скорости выполнения он будет не лучше, чем линейный поиск


А где было обещано что он лучше? Что вообще бывает лучше чем дихотомия на сортированном векторе?
...
Рейтинг: 0 / 0
02.09.2020, 16:18
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994881
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
exp98,

поправка
3) по поводу констант, если быть точным, прыжки должны совершатся до тех пор пока val >= arr[high]
...
Рейтинг: 0 / 0
02.09.2020, 16:22
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994889
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
mayton

А где было обещано что он лучше?

скорость поиска для JumpSearch O(sqrt(n)), это лучше, чем линейный поиск O(n)
mayton

Что вообще бывает лучше чем дихотомия на сортированном векторе?

при условии, что данные распределены равномерно, интерполяционный поиск будет эффективнее, чем двоичный
...
Рейтинг: 0 / 0
02.09.2020, 16:27
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994892
mini.weblab
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mini.weblab
Участник
Имя пользователя1
если хэш - некоторое целое число, то это будет индекс массива, где всё хранится, то есть уже никакого поиска не потребуется (хотя, если у некоторых значений совпал хэш, то это будет коллизия и там придется поискать). В этом идея хэш-словаря.

да, согласилась
...
Рейтинг: 0 / 0
02.09.2020, 16:30
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994893
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
Это всё о точном поиске. Существует прикладные задачи на - интервальный поиск, - нечёткий поиск.
Но метод Ньютона тоже ищет известное значение в неизвестном месте, но обычно не в дискретных последовательностях, а в континуумах.
Ещё веоятностный поиск, как пример точного решения вероятностными методами, поищу ссылку, старая работа, Фрейвальд - фамилия такая.
...
Рейтинг: 0 / 0
02.09.2020, 16:30
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994896
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Имя пользователя1
Участник
mini.weblab
maytonЧто вообще бывает лучше чем дихотомия на сортированном векторе?

при условии, что данные распределены равномерно, интерполяционный поиск будет эффективнее, чем двоичныйи при условии, что это данные с ключем сортировки в виде числа.
те же строки так не найти.
...
Рейтинг: 0 / 0
02.09.2020, 16:38
| Ответить | Цитировать | Написать  
Jump Search Algorithm: ошибка в псевдокоде
    #39994902
exp98
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
exp98
Участник
mini.weblab
я говорю конкретно об алгоритмах поиска , а не о всех возможных алгоритмах
есть алгоритмы поиска (и их 4), а есть структуры данных, это не одно и тоже
Не будь догматиком. Просто на той свисте-странице написаны 4 ссылки на эти 4 алгоритма. Ну у этого автора шоры на глазах. Он даже не в курсе, что в псевдоконтинуумах тоже иногда ищут-свищут. Что алгоритмы использовать "детерминированные методы", а могут - вероятностные. "Это Америка, детка", родина слонов.


Главное выяснено. Тема о том, что алгоритм в книге правильный, но недостаточно быстрый? или не настолько как заявлено автором книги?
...
Рейтинг: 0 / 0
02.09.2020, 16:45
| Ответить | Цитировать | Написать  
25 сообщений из 62, страница 2 из 3
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Jump Search Algorithm: ошибка в псевдокоде
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=39994767&tid=1339745]:
 0ms
get settings:
 12ms
get forum list:
 14ms
check forum access:
 4ms
check topic access:
 4ms
track hit:
 156ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 68ms
get tp. blocked users:
 2ms
others: 15ms
total:  290ms
созд. / загр.: 290ms
x
x
Закрыть


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