|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sashka Yackubtchick 2:5054/29.54 03 Mar 2002 06:23:50
To : Andrew Doroshev
Subject : Binary search with duplicate values
--------------------------------------------------------------------------------
28 Feb 02 19:28, Andrew Doroshev писАл(а) к Dmitry Koren:
AD> Последовательный поиск при 25*10Е6 элементах в массиве вещь небыстрая.
Это для какой платформы?
AD> Это по техзданию, реально конечно меньше, при тестировании пока где
AD> то
AD> до 10Е4.
AD> А отладить двоичный поиск, если в массиве есть повторы, мне не удалось.
AD> Пришлось вводить дополнительные проверки. В конце поиска, когда разница
AD> "верхняя граница" - "нижняя граница" <= 1 ответ иногда на единицу
AD> отличается от правильного.
Я бы рассуждал так:
(Мне приходится многое предпологать в плане оценок вероятности,
если что-то существееное есть в этом плане сказать, напиши пожалуйста)
1. Hижним индексом может быть любой элемент от 0 до 108149 (если ты говоришь
о 25*10E6 (или 25 это 25h?)
2. Тем не менее, само колличество одинаковых элементов значительно меньше.
(сколько их может быть одинаковых максимум? в среднем? также непонятно
а может ли быть такое, что элемента, верхний и нижний индекс которого ищутся
вообще нет в массиве?)
Тогда напрашивается сначала такая логика.
- Hайти как можно быстрее первый элемент. Его индекс будет нижним
- верхний индекс = нижний ;
проверять по цепочке пока значение элемента совпадает с очередным,
инкриминируя значение верхнего индекса,
при первом же несовпадении возврат.
Мне бы казалось исходя из вышесказанного, что скорость стала бы определяться
процедурой поиска первого значения. Есть варианты резкого ускорения подобного
поиска но они платформо зависимы.
Там какой тип данных у элемента?
Видишь ли можно конечно проверять делением пополам или сходными по логике
методами, но деление пополам длины массива напрямую можно использовать лишь
если массив растёт плавно и каждый элемент уникален либо существует некая чёткая
зависимость.
Если зависимость между ростом индексов элементов и ростом их значения
неопределена то как можно использовать подобные методы.
Они могут наоборот замедлить.
Другое дело например ускорить нахождение группы значения которой например
превышают данное значение.
1. Способ примитивный.
Проверяем каждый надцатый элемент пока он не больше заданного.
Как только мы его найдём нужно лишь просканировать от найденного обратно
пока не наткнёмся на наш элемент.
Тогда максимальное колличество проверок длина массива\надцать (или цать как
хочешь) + надцать-1.
2. Способ примитивный делаем тоже самое что и в первом но с двух концов
в одном проверяя не больше ли равно во втором не меньше ли равно.
Преимущество - за одну итерацию проверить сразу две группы.
Как на HLL такое рисуется понятия неимею, но на машином языке очень просто.
3,4,5 - можно увеличить колличество секторов синхронной проверки.
Деление на 2 конечно напрашивается.
Hо ничего не сказано о равномерности распределения и усреднённости размера групп
элементов с одинаковыми значениями.
Могут быть случаи когда ты будешь делать sqrt(колличество элемментов) шагов а
сам элемент будет лежать под носом.
Пока!
Sashka, The Svin.
--- GoldED/W32 3.00.Beta1+
* Origin: Svin, Perm, Russia (2:5054/29.54)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
