|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Oleg I. Khovayko 2:5020/400 07 May 2001 23:20:47
To : All
Subject : Re: Алгоритм поиска и счета данных
--------------------------------------------------------------------------------
Max Irgiznov wrote:
>
> OK> выводим пары (key, counter) из массива S. Они там и будут уже
> OK> отсортированы по ключу key...
> Вобщем спасибо, 50%побыстрее чем у меня, изначально идея такая и была.
Кстати, про binsearch со вставкой. Hа всякий случай, даю кусок сырца
/* BinSearch for position for insert */
l = 0; u = found_listN - 1;
do {
key = found_list[i = (l + u) >> 1];
if(X == key) {
found_list[i].cnt++;
goto next_X;
}
l = i + 1;
else
u = i - 1;
} while(u >= l);
// А вот здесь "l" указывает на то место, где надобно
// вставить новую запись.
> OK> PS: Есть еще более эффективные решения с точки зрения скорости -
> OK> например, использовать взвешеное дерево Ху-Такера, или хешировать
> ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> Об этом можно поподробнее?
Долго писать - там несколько страниц.
см. Д. Кнут, "Искусство программирования для ЭВМ",
М:Мир, 1978, стр. 523.
Смысл в том, что если тебе известна вероятность прихода твоих X-ов,
то вместо бинарного поиска применяешь дерево, причем сбалансированное
таким образом, что к частым элементам путь по дереву короткий, а к
редким - длинный. Таким образом, резко снижается среднее число сравнений.
--
#include <best/regards.hpp>
Oleg I. KHOVAYKO
(301)435-5885 || WEB: http://olegh.spedia.net
--- ifmail v.2.15dev5
* Origin: National Center of Biotechnology Information (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: Алгоритм поиска и счета данных 