Подскажите алгоритм

← →
Немо © (2009-04-07 16:31) [0]

Пока использую половинное деление

Задача.
есть линейка целых положительных чисел от N до М включительно.
есть функция боол. Вход число
Нужно определить минимальное число от N до М для которого НЕТ.

Особенность функции, что она для числа К считает сначала все числа от N до К. (это типа 1с среза). И очень долгая по времени.
Функцию изменить не могу никак.

Как сейчас происходит дело
линейка от 0 до 10. Допустим, для 10 НЕТ.

на первом шаге 10 - НЕТ
на втором 0+int((10-0)/2)=5 - ДА
5+int((10-5)/2)=7 - ДА
7+int((10-7)/2)=8 - ДА
8+int((10-8)/2)=9 - ДА
получается, что считаем для 7,8,9 подряд..

А счет идет тем дольше, чем большее число проверяем.
или просто неудачный пример, в общем случае она лучше себя поведет..

Но все равно, смысл в том, что половинное деление оправдано, имхо , когда равные варианты остаются что справа, что слева. Тут же справа более тяжеловесные остаются.

← →
MBo © (2009-04-07 16:41) [1]

Не очень понятно - имеется функция типа
function AreAllRangeTrue(Start, End: Integer): Boolean;
так?

← →
Немо © (2009-04-07 16:43) [2]

не, типа
function IsTrue(Number: Integer): Boolean;

← →
MBo © (2009-04-07 16:45) [3]

И ее время работы пропорционально Number ?

← →
Немо © (2009-04-07 16:51) [4]

Да, т.е. разработчик дал функцию mssql with encription
на входе день, до которого она считает возможность сделать "срез"

чем дальше просчитываем возможность среза от последнего сделанного среза, тем дольше считает. Потому что считает опять заново, с первого дня от среза.

А чем ближе сделать срез к сегодняшней дате, тем лучше все работает

← →
MBo © (2009-04-07 16:52) [5]

И почему в примере не проверяются числа менее 5- что, из того, что 5 True -следует, что и для меньших true?

← →
Немо © (2009-04-07 16:56) [6]

да,
за пять дней срез можно сделать, значит все до этого дня в порядке.

← →
palva © (2009-04-07 21:18) [7]

> да,

Ну только теперь задача стала понятна. Вы совершенно правы. Желательно выбирать чтобы справа и слева от точки деления было что-то одинаковое по объему вычислений. Только здесь может вмешаться вероятность. Если распределение неравномерное, т. е. к примеру, начальные числа значительно вероятнее, то при вычислении объема нужно учитывать вероятность и домножать на нее. Т. е. минимизировать надо матожидание объема вычислений.

← →
TUser © (2009-04-07 22:22) [8]

> MBo © (07.04.09 16:45) [3]
>
> И ее время работы пропорционально Number ?
> <Цитата>
>
> Немо © (07.04.09 16:51) [4]
>
> Да

Нет, тут будет логарифмическое время, что весьма быстро.

← →
Немо © (2009-04-08 08:59) [9]

> может вмешаться вероятность

никакой вероятности. Вернее все равнозначны. Если в какой-то день накосячили, то это может быть любой день.

Спасибо
Кажется дома додумал

← →
MBo © (2009-04-08 09:11) [10]

>Вернее все равнозначны
Тогда вероятность того, что первый косяк случился на k-й день, подчинаяется геометрическому распределению P(k) = p*(1-p)^(k-1), где p - вероятность false в отдельно взятый день. Матожидание этого распределения 1/p (т.е. в среднем на 1/p-й день будет false), а вот медиану посчитать, мне кажется, затруднительно. Впрочем, асимптотического времени работы O(N*logN) не изменить даже при адаптивном поиске. Можно только немного уменьшить постоянный множитель - например, при малой вероятности false использовать не бинарный, а "тринарный" поиск, прижатый к правому краю (типа Med := (L + 2*R) div 3;), а при большой вероятности - прижатый к левому краю.

← →
Немо © (2009-04-08 09:27) [11]

> MBo © (08.04.09 09:11) [10]

тоже пришел к выводу, что лучше на 3 делить и брать справа
Спасибо
только не понял про O(N*logN), на да и ладно, в принципе :)

← →
MBo © (2009-04-08 09:41) [12]

Количество вызовов функции IsTrue пропорционально логарифму N (свойство бинарного поиска)
А каждый вызов ее работает за время, пропорциональное N. Так что обшее время работы N * Log(N).

>тоже пришел к выводу, что лучше на 3 делить и брать справа
Промоделировал ситуацию на массив с 32 элементами.
При вероятности False 0.005 прижатие вправо дает выигрыш до полутора раз. Однако это для случая, когда первый вызов для всего массива не делается.
Если же делать этот вызов (а это стоит делать, т.к. при такой малой вероятности в большинстве случаев все True и поиск не нужен), то выигрыш существенно меньше.

← →
TUser © (2009-04-08 09:46) [13]

> А каждый вызов ее работает за время, пропорциональное N.
> Так что обшее время работы N * Log(N).
>

?? min+((num-min) div 2)

константное у него время, имхо

"считает сначала все числа от N до К" - это (я так понимаю) про перечисление 7, 8, 9, но тут "просто пример неудачный"

← →
MBo © (2009-04-08 09:51) [14]

>TUser
Я логику работы понял так:
IsTrue - модель внешней функции

function IsTrue(N: Integer): Boolean; var i: integer; begin Result := True; for i := 0 to N do begin Inc(Cnt); //счетчик для оценки времени работы if not A[i] then //begin Result := False; // Break; // end; end; end; function Srch(L, R: Integer): Integer; var M: Integer; begin if L >= R then begin if IsTrue(L) then Result := -1 else Result := L; end else begin M := (L + R) div 2; if IsTrue(M) then Result := Srch(M + 1, R) else Result := Srch(L, M - 1) end;

в последней строчке Srch(L, M)

где то лог был, надо посмотреть/оцентить вероятность False

и.. а дай пожалуйста модельку, чтоб мне не писать :) тоже погоняю

а нет, не надо

procedure TForm2.Button4Click(Sender: TObject); const NN = 31; var A: array[0..NN] of Boolean; i, k, Cnt, F: Integer; function IsTrue(N: Integer): Boolean; var i: integer; begin Result := True; for i := 0 to N do begin Inc(Cnt); //счетчик для оценки времени работы if not A[i] then //begin Result := False; // Break; //разумная модель, если она используется во внешней функции // end; end; end; function Srch(L, R: Integer): Integer; var M: Integer; begin if L >= R then begin if IsTrue(L) then Result := L else Result := -1; end else begin M := (L + 2 * R) div 3; // M := (L + R) div 2; if IsTrue(M) then Result := Srch(M + 1, R) else Result := Srch(L, M) end; end; begin Randomize; Cnt := 0; for k := 1 to 1000 do begin for i := 0 to NN do A[i] := Random > 0.005; // if not IsTrue(NN) then F := Srch(0, NN); end; Caption := Format("Среднее время %d",[Cnt div 1000]); end;

>а нет, не надо
поздно, уже закомпостировано ;)

вряд ли вероятность 0.005, скорее больше. И вряд ли модель разумна.
с этими допущениями вариант делить на 3 и справа быстрее

> поздно, уже закомпостировано ;)
>

спасибо :)

Подскажите алгоритм Найти похожие ветки