|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrew Doroshev 2:5020/400 07 Mar 2002 13:52:08
To : Sashka Yackubtchick
Subject : Re: Binary search with duplicate values
--------------------------------------------------------------------------------
Dear Sashka Yackubtchick!
> AD> Последовательный поиск при 25*10Е6 элементах в массиве вещь небыстрая.
> Это для какой платформы?
Это для любой платформы.
Среднее количество проверок при бинарном поиске =
-- старт --
1 проверка что число >= a[0]
1 проверка что число <= a[N-1]
-- пока нет равенства --
(Log 25000000/Log 2 = 25)
k проверок что число < a[middle], 1<=к<=25
k проверок что число != a[middle],
-- успешный поиск --
l проверок что число < a[middle], l<=25-k, для поиска нижней границы
m проверок что число < a[middle], m<=25-k, для поиска верхней границы
-- а здесь гаденькая концовка, которая мне не нравится --
2-4 проверки что число == a[middle]
Итого: в самом плохом случае сделаем 56 проверок, в среднем - 31
> Я бы рассуждал так:
> (Мне приходится многое предпологать в плане оценок вероятности,
> если что-то существееное есть в этом плане сказать, напиши пожалуйста)
>
> 1. Hижним индексом может быть любой элемент от 0 до 108149 (если ты говоришь
от 0 до 25000000
> о 25*10E6 (или 25 это 25h?)
25*10E6 это 25000000 десятичное число
> 2. Тем не менее, само колличество одинаковых элементов значительно меньше.
> (сколько их может быть одинаковых максимум? в среднем? также непонятно
> а может ли быть такое, что элемента, верхний и нижний индекс которого ищутся
> вообще нет в массиве?)
> Тогда напрашивается сначала такая логика.
> - Hайти как можно быстрее первый элемент. Его индекс будет нижним
> - верхний индекс = нижний ;
> проверять по цепочке пока значение элемента совпадает с очередным,
> инкриминируя значение верхнего индекса,
> при первом же несовпадении возврат.
>
> Мне бы казалось исходя из вышесказанного, что скорость стала бы определяться
> процедурой поиска первого значения. Есть варианты резкого ускорения подобного
> поиска но они платформо зависимы.
Example, please. Я вполне серьёзно. Я не знаю примеров более быстрого поиска,
чем деление пополам. И тем более не знаю ничего платформо-зависимого. Кстати,
зависимость меня сильно не пугает. Мне надо решить задачу, здесь и сейчас, не
более того
> Там какой тип данных у элемента?
int, 32 бита
>
> Видишь ли можно конечно проверять делением пополам или сходными по логике
> методами, но деление пополам длины массива напрямую можно использовать лишь
> если массив растёт плавно и каждый элемент уникален либо существует некая
> чёткая зависимость.
никакой информации о вероятности тех или иных значений нет. от 1,1,1,...1 до
1,2,3,4...25000000
> Если зависимость между ростом индексов элементов и ростом их значения
> неопределена то как можно использовать подобные методы.
> Они могут наоборот замедлить.
> Другое дело например ускорить нахождение группы значения которой например
> превышают данное значение.
> 1. Способ примитивный.
> Проверяем каждый надцатый элемент пока он не больше заданного.
> Как только мы его найдём нужно лишь просканировать от найденного обратно
> пока не наткнёмся на наш элемент.
> Тогда максимальное колличество проверок длина массива\надцать (или цать как
> хочешь) + надцать-1.
пусть надцать=z
тогда макс количество проверок=const*Log(длина массива)/Log(z)*(z-1)
z Количество проверок
2 25
3 32
5 43
10 67
15 89
20 109
30 146
40 181
50 214
100 367
> 2. Способ примитивный делаем тоже самое что и в первом но с двух концов
> в одном проверяя не больше ли равно во втором не меньше ли равно.
> Преимущество - за одну итерацию проверить сразу две группы.
> Как на HLL такое рисуется понятия неимею, но на машином языке очень просто.
> 3,4,5 - можно увеличить колличество секторов синхронной проверки.
>
> Деление на 2 конечно напрашивается.
> Hо ничего не сказано о равномерности распределения и усреднённости размера
> групп элементов с одинаковыми значениями.
> Могут быть случаи когда ты будешь делать sqrt(колличество элемментов) шагов а
> сам элемент будет лежать под носом.
Сейчас пытаюсь преобразовать алгоритм обработки, с тем, чтобы не искать
произвольный элемент в массиве, а вместо этого искать элемент соседний с данным.
Это быстрее всего.
Andrew Doroshev
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
