|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Max Irgiznov 2:5051/1.79 07 May 2001 07:38:59
To : Oleg I Khovayko
Subject : Алгоритм поиска и счета данных
--------------------------------------------------------------------------------
Четверг Май 03 2001 Было когда-то 22:01, базарил некто Oleg I Khovayko с All, и
я задумал потрещать:
OK> То есть ты утверждаешь, что твои числа равномерно распределены
OK> в диапазаоне [0..2^31].
OK> Что ж, и эта проблема решается за один проход - правда, раз в 10
OK> медленее, чем пред. решение.
OK> идея такая:
OK> 1. Заводишь массив структур S :== (key, counter). Причем размер
OK> массива берешь раза в 3 больше, чем кoличество ожидаемых уникальных
OK> ключей.
OK> 2. Побежали циклом по входному массиву: while(!end_of_input)
OK> 2.1. Взяли очередное входное значение X из входного массива
OK> 2.2. Рассматривая X как key, посредством BinSearch-a нашли
OK> в массиве S структуру S[i], такую что S[i].key == X.
OK> 2.3. Увеличили S[i].counter++; goto 2.1.
OK> 2.4. Ежели поиск в 2.3. обломился, и нету еще структуры с X ==
OK> S[i].key, то создаем такую структуру и вставляем ее в массив S,
OK> сдвигая хвост массива. Я считаю, что тысяча сдвигов в среднем по 250
OK> слов не сьедят много времени.. goto 2.1. 3. Кончился входной массив --
OK> выводим пары (key, counter) из массива S. Они там и будут уже
OK> отсортированы по ключу key...
Вобщем спасибо, 50%побыстрее чем у меня, изначально идея такая и была.
OK> PS: Есть еще более эффективные решения с точки зрения скорости -
OK> например, использовать взвешеное дерево Ху-Такера, или хешировать
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
OK> что-либо, но тут надобно основательно проанализировать
OK> твои входные данные, чтобы придумать действительно
OK> оптимальный алгоритм.
OK> Что выходит за рамки данного постинга и количества времени,
OK> которое я готов безвозмездно потратить на писательство
OK> развернутого письма.
Об этом можно поподробнее?
PS спасибо за помощь. =)
Пока,Oleg!!! С вами был,есть и будет:Max Irgiznov [WebLabs UlSU]
ё-мыл:Max_ir@Rambler.ru(Mail.ru), ICQ#89349143 [UlNet] [VS]
--- С моих слов записано верно и мною прочитано. 3.0.1 Голый Дед.
* Origin: Кто бьет, тому и больно. (2:5051/1.79)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
