* [room] on binary search and merge-sort algos
@ 2007-08-20 7:18 Michael Shigorin
2007-08-20 7:40 ` Denis Kirienko
` (2 more replies)
0 siblings, 3 replies; 13+ messages in thread
From: Michael Shigorin @ 2007-08-20 7:18 UTC (permalink / raw)
To: smoke-room
Здравствуйте.
http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
"почти все бинарные поиски и сортировки слиянием сломанные"
2 Bcc: надеюсь, вы [пока] не против такого спама? :)
--
---- WBR, Michael Shigorin <mike@altlinux.ru>
------ Linux.Kiev http://www.linux.kiev.ua/
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 7:18 [room] on binary search and merge-sort algos Michael Shigorin
@ 2007-08-20 7:40 ` Denis Kirienko
2007-08-20 7:53 ` Damir Shayhutdinov
2007-08-20 7:48 ` Damir Shayhutdinov
2007-08-20 17:07 ` Alexey Voinov
2 siblings, 1 reply; 13+ messages in thread
From: Denis Kirienko @ 2007-08-20 7:40 UTC (permalink / raw)
To: smoke-room
Michael Shigorin пишет:
> Здравствуйте.
> http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> "почти все бинарные поиски и сортировки слиянием сломанные"
А я бы у школьника на зачете такой бинарный бы поиск не принял.
Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
возможных случая.
--
Денис
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 7:18 [room] on binary search and merge-sort algos Michael Shigorin
2007-08-20 7:40 ` Denis Kirienko
@ 2007-08-20 7:48 ` Damir Shayhutdinov
2007-08-20 17:07 ` Alexey Voinov
2 siblings, 0 replies; 13+ messages in thread
From: Damir Shayhutdinov @ 2007-08-20 7:48 UTC (permalink / raw)
To: культурный
офтопик
> Здравствуйте.
> http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> "почти все бинарные поиски и сортировки слиянием сломанные"
Ошибка тут в том, что mid объявлен как int, а не как unsigned. Так же,
как low и high.
Если индекс массива - неотрицательное число (а это как правило именно
так, кроме сложных случаев указательной арифметики), то и тип надо
ставить неотрицательный (unsigned). Тогда приведение к unsigned будет
излишним.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 7:40 ` Denis Kirienko
@ 2007-08-20 7:53 ` Damir Shayhutdinov
2007-08-20 8:00 ` Denis Kirienko
0 siblings, 1 reply; 13+ messages in thread
From: Damir Shayhutdinov @ 2007-08-20 7:53 UTC (permalink / raw)
To: культурный
офтопик
> А я бы у школьника на зачете такой бинарный бы поиск не принял.
> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
> возможных случая.
Если уж придираться - то по полной. Там на самом деле четыре возможных
случая, включая проверку в while (low <= high).
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 7:53 ` Damir Shayhutdinov
@ 2007-08-20 8:00 ` Denis Kirienko
2007-08-20 8:31 ` Damir Shayhutdinov
0 siblings, 1 reply; 13+ messages in thread
From: Denis Kirienko @ 2007-08-20 8:00 UTC (permalink / raw)
To: smoke-room
Damir Shayhutdinov пишет:
>> А я бы у школьника на зачете такой бинарный бы поиск не принял.
>> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
>> возможных случая.
> Если уж придираться - то по полной. Там на самом деле четыре возможных
> случая, включая проверку в while (low <= high).
А вот этого я уже не понимаю. Условие-то в цикле должно быть по-любому,
от него никуда не денешься.
Суть бинарного поиска в том, что массив на каждом шаге делится на две
части, между которыми осуществляется выбор. В том алгоритме, который
приведён по ссылке массив делится на три части.
--
Денис
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 8:00 ` Denis Kirienko
@ 2007-08-20 8:31 ` Damir Shayhutdinov
2007-08-20 8:49 ` Denis Kirienko
0 siblings, 1 reply; 13+ messages in thread
From: Damir Shayhutdinov @ 2007-08-20 8:31 UTC (permalink / raw)
To: культурный
офтопик
> >> А я бы у школьника на зачете такой бинарный бы поиск не принял.
> >> Поскольку он не бинарный, а тернарный - внутри идет ветвление на три
> >> возможных случая.
> > Если уж придираться - то по полной. Там на самом деле четыре возможных
> > случая, включая проверку в while (low <= high).
>
> А вот этого я уже не понимаю. Условие-то в цикле должно быть по-любому,
> от него никуда не денешься.
Смотря что в условие поставить.
>
> Суть бинарного поиска в том, что массив на каждом шаге делится на две
> части, между которыми осуществляется выбор. В том алгоритме, который
> приведён по ссылке массив делится на три части.
Если вы условие выхода из цикла не считаете за "деление массива",
тогда третью часть можно вынести в это условие цикла.
unsigned low = 0;
unsigned mid = 0;
unsigned high = a.length - 1;
while (low <= high && a[mid] != key)
{
mid = (low + high) / 2;
if (a[mid] < key)
low = mid + 1;
else
high = mid - 1;
}
if (a[mid] == key) return mid;
return -(low + 1);
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 8:31 ` Damir Shayhutdinov
@ 2007-08-20 8:49 ` Denis Kirienko
2007-08-20 14:16 ` Damir Shayhutdinov
0 siblings, 1 reply; 13+ messages in thread
From: Denis Kirienko @ 2007-08-20 8:49 UTC (permalink / raw)
To: smoke-room
Damir Shayhutdinov пишет:
> Если вы условие выхода из цикла не считаете за "деление массива",
> тогда третью часть можно вынести в это условие цикла.
>
> unsigned low = 0;
> unsigned mid = 0;
> unsigned high = a.length - 1;
>
> while (low <= high && a[mid] != key)
> {
> mid = (low + high) / 2;
> if (a[mid] < key)
> low = mid + 1;
> else
> high = mid - 1;
> }
> if (a[mid] == key) return mid;
> return -(low + 1);
То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
одного условия вынесена в условие цикла.
--
Денис
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 8:49 ` Denis Kirienko
@ 2007-08-20 14:16 ` Damir Shayhutdinov
2007-08-20 14:38 ` Denis Kirienko
2007-08-20 15:35 ` Denis Kirienko
0 siblings, 2 replies; 13+ messages in thread
From: Damir Shayhutdinov @ 2007-08-20 14:16 UTC (permalink / raw)
To: культурный
офтопик
> То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
> одного условия вынесена в условие цикла.
Тогда вы просто слишком формально относитесь к понятию "бинарный поиск".
Если я правильно понимаю, то, что вы назовете бинарным поиском, будет
_всегда_ выполняться за O(log n).
А этот алгоритм "тернарного" поиска будет выполняться за O(log n)
только в _худшем_ случае.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 14:16 ` Damir Shayhutdinov
@ 2007-08-20 14:38 ` Denis Kirienko
2007-08-20 15:35 ` Denis Kirienko
1 sibling, 0 replies; 13+ messages in thread
From: Denis Kirienko @ 2007-08-20 14:38 UTC (permalink / raw)
To: smoke-room
Damir Shayhutdinov пишет:
>> То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
>> одного условия вынесена в условие цикла.
> Тогда вы просто слишком формально относитесь к понятию "бинарный поиск".
Может быть.
> Если я правильно понимаю, то, что вы назовете бинарным поиском, будет
> _всегда_ выполняться за O(log n).
Да.
> А этот алгоритм "тернарного" поиска будет выполняться за O(log n)
> только в _худшем_ случае.
И всё равно за O(log n) в среднем...
--
Денис
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 14:16 ` Damir Shayhutdinov
2007-08-20 14:38 ` Denis Kirienko
@ 2007-08-20 15:35 ` Denis Kirienko
2007-08-20 17:08 ` Damir Shayhutdinov
1 sibling, 1 reply; 13+ messages in thread
From: Denis Kirienko @ 2007-08-20 15:35 UTC (permalink / raw)
To: smoke-room
Damir Shayhutdinov пишет:
>> То, что вы предлагаете - это тот же тернарный поиск, только проверка еще
>> одного условия вынесена в условие цикла.
>
> Тогда вы просто слишком формально относитесь к понятию "бинарный поиск".
>
> Если я правильно понимаю, то, что вы назовете бинарным поиском, будет
> _всегда_ выполняться за O(log n).
>
> А этот алгоритм "тернарного" поиска будет выполняться за O(log n)
> только в _худшем_ случае.
Решил сравнить быстродействие двух вариантов поиска. Написал свой поиск
и Ваш поиск, запускал на случайных массивах размером 10^7..10^8
элементов. Быстродействие одинаковое в пределах статистической
погрешности (1-2%).
На самом деле правильно написать бинарный поиск не так-то просто.
Присланная вами реализация содержит ошибку (программа попадает в
segfault). Найдете сами или подсказать?
--
Денис
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 7:18 [room] on binary search and merge-sort algos Michael Shigorin
2007-08-20 7:40 ` Denis Kirienko
2007-08-20 7:48 ` Damir Shayhutdinov
@ 2007-08-20 17:07 ` Alexey Voinov
2007-08-20 19:33 ` Michael Shigorin
2 siblings, 1 reply; 13+ messages in thread
From: Alexey Voinov @ 2007-08-20 17:07 UTC (permalink / raw)
To: культурный
офтопик
Michael Shigorin <mike@osdn.org.ua> writes:
> Здравствуйте.
> http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> "почти все бинарные поиски и сортировки слиянием сломанные"
Хмм.. а как насчёт реализация на языках, в которых проблема
переполнения целых как бы и не очень актуальна? :)
--
Best Regards!
Alexey Voinov
voins@voins.program.ru
voins@altlinux.ru
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 15:35 ` Denis Kirienko
@ 2007-08-20 17:08 ` Damir Shayhutdinov
0 siblings, 0 replies; 13+ messages in thread
From: Damir Shayhutdinov @ 2007-08-20 17:08 UTC (permalink / raw)
To: культурный
офтопик
> Решил сравнить быстродействие двух вариантов поиска. Написал свой поиск
> и Ваш поиск, запускал на случайных массивах размером 10^7..10^8
> элементов. Быстродействие одинаковое в пределах статистической
> погрешности (1-2%).
Вообще странно, должна быть разница где-то в 2 раза.
> На самом деле правильно написать бинарный поиск не так-то просто.
> Присланная вами реализация содержит ошибку (программа попадает в
> segfault). Найдете сами или подсказать?
То, что high может стать меньше нуля в результате присвоения high =
mid - 1, в результате оно станет равным максимальному беззнаковому
целому?
С этим можно бороться, если заменить на high = mid; быстродействие не
должно сильно пострадать.
^ permalink raw reply [flat|nested] 13+ messages in thread
* Re: [room] on binary search and merge-sort algos
2007-08-20 17:07 ` Alexey Voinov
@ 2007-08-20 19:33 ` Michael Shigorin
0 siblings, 0 replies; 13+ messages in thread
From: Michael Shigorin @ 2007-08-20 19:33 UTC (permalink / raw)
To: культурный
офтопик
On Mon, Aug 20, 2007 at 09:07:38PM +0400, Alexey Voinov wrote:
> > http://www.developers.org.ua/archives/redron/2007/08/19/binary-merge-search-broken/
> > "почти все бинарные поиски и сортировки слиянием сломанные"
> Хмм.. а как насчёт реализация на языках, в которых проблема
> переполнения целых как бы и не очень актуальна? :)
Вот в комментариях народ на ту же тему и прошёлся ;)
--
---- WBR, Michael Shigorin <mike@altlinux.ru>
------ Linux.Kiev http://www.linux.kiev.ua/
^ permalink raw reply [flat|nested] 13+ messages in thread
end of thread, other threads:[~2007-08-20 19:33 UTC | newest]
Thread overview: 13+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2007-08-20 7:18 [room] on binary search and merge-sort algos Michael Shigorin
2007-08-20 7:40 ` Denis Kirienko
2007-08-20 7:53 ` Damir Shayhutdinov
2007-08-20 8:00 ` Denis Kirienko
2007-08-20 8:31 ` Damir Shayhutdinov
2007-08-20 8:49 ` Denis Kirienko
2007-08-20 14:16 ` Damir Shayhutdinov
2007-08-20 14:38 ` Denis Kirienko
2007-08-20 15:35 ` Denis Kirienko
2007-08-20 17:08 ` Damir Shayhutdinov
2007-08-20 7:48 ` Damir Shayhutdinov
2007-08-20 17:07 ` Alexey Voinov
2007-08-20 19:33 ` Michael Shigorin
Культурный офтопик
This inbox may be cloned and mirrored by anyone:
git clone --mirror http://lore.altlinux.org/smoke-room/0 smoke-room/git/0.git
# If you have public-inbox 1.1+ installed, you may
# initialize and index your mirror using the following commands:
public-inbox-init -V2 smoke-room smoke-room/ http://lore.altlinux.org/smoke-room \
smoke-room@lists.altlinux.org smoke-room@lists.altlinux.ru smoke-room@lists.altlinux.com smoke-room@altlinux.ru smoke-room@altlinux.org smoke-room@altlinux.com
public-inbox-index smoke-room
Example config snippet for mirrors.
Newsgroup available over NNTP:
nntp://lore.altlinux.org/org.altlinux.lists.smoke-room
AGPL code for this site: git clone https://public-inbox.org/public-inbox.git