Давно уже пора начать программировать, но как-то не начинается. Может быть, если еще немного подождать, все произойдет само собой? А вдруг, лениться полезно?
Честно говоря, не знаю, зачем может потребоваться эта функция, но на одном форуме был задан такой вопрос. Дано два целых числа из диапазона 0..9999. Требуется узнать, различаются ли они ровно одной десятичной цифрой. Быстродействие функции критично, т.к. она многократно используется при обработке массива данных.
Понятно, что преобразование чисел в строки и посимвольное сравнение строк работает слишком медленно и в данном случае не подходит:
function OneDigitDifferent1(n1, n2: integer): boolean; var s1, s2: string; i, count: integer; begin; s1:=Format('%.4d',[n1]); s2:=Format('%.4d',[n2]); count:=0; for i:=1 to 4 do count:=count+ord(s1[i]<>s2[i]); Result:=count=1; end;
Другой способ состоит в следующем. Сначала проверяется допустимость разности чисел (она может быть от 1 до 9 единиц, десятков, сотен или тысяч), а затем — отсутствие переноса между десятичными разрядами. В худшем случае этому алгоритму требуется только 3 деления, что намного быстрее предыдущего варианта, но все еще недостаточно быстро:
function OneDigitDifferent2(n1, n2: integer): boolean; var delta : integer; begin; delta:=abs(n1-n2); if delta=0 then Result:=false else if delta<10 then Result:=(n1 div 10 = n2 div 10) else if delta<100 then Result:=(delta mod 10 =0) and (n1 div 100 = n2 div 100) else if delta<1000 then Result:=(delta mod 100 =0) and (n1 div 1000 = n2 div 1000) else Result:=(delta mod 1000 =0); end;
Если проанализировать работу приведенного алгоритма, то можно заметить, что мы делаем кое-что лишнее. Ведь для того, чтобы проверить отсутствие переноса между десятичными разрядами, совсем не обязательно их сравнивать. Достаточно убедиться в том, младшие разряды большего из чисел превышают их разность. Два деления вместо трех должны сказаться на скорости:
function OneDigitDifferent3(n1, n2: integer): boolean; var delta, max: integer; begin; if n1=n2 then Result:=false else begin; delta:=abs(n1-n2); max:=(n1+n2+delta) shr 1; if delta<10 then Result:=(delta <= max mod 10) else if delta<100 then Result:=(delta mod 10 =0) and (delta <= max mod 100) else if delta<1000 then Result:=(delta mod 100 =0) and (delta <= max mod 1000) else Result:=(delta mod 1000 =0); end; end;
С другой стороны, можно использовать таблицу размером 4x10000, в которой хранить разряды единиц, десятков, сотен и тысяч каждого числа от 0 до 9999. И тогда лишним окажется преобразование чисел в строки в самом первом алгоритме, останется только посчитать количество различий во всех разрядах сравниваемых чисел. Несколько громоздко, зато нет делений. К сожалению, этот вариант оказывается далеко не самым быстрым:
var DigitTable: array[0..3, 0..9999] of byte; procedure InitDigitTable; var i3, i2, i1, i0: integer; begin; for i3:=0 to 9 do for i2:=0 to 9 do for i1:=0 to 9 do for i0:=0 to 9 do begin; DigitTable[0, i3*1000 + i2*100 + i1*10 + i0] := i0; DigitTable[1, i3*1000 + i2*100 + i1*10 + i0] := i1; DigitTable[2, i3*1000 + i2*100 + i1*10 + i0] := i2; DigitTable[3, i3*1000 + i2*100 + i1*10 + i0] := i3; end; end; function OneDigitDifferent4(n1, n2: integer): boolean; begin; Result:=ord(DigitTable[0,n1]<>DigitTable[0,n2]) + ord(DigitTable[1,n1]<>DigitTable[1,n2]) + ord(DigitTable[2,n1]<>DigitTable[2,n2]) + ord(DigitTable[3,n1]<>DigitTable[3,n2]) = 1; end;
Можно даже заранее вычислить количество различных цифр для каждой пары чисел. Правда, размер таблицы для четырехзначных чисел будет 10000x10000, что, скорее всего, находится за гранью разумного. Если же разбить каждое число на 2 двухзначных, то потребуется таблица 100x100. Конечно, при этом придется делить. Но у нас в запасе есть грязные приемчики, позволяющие некоторые вещи делать проще. Например, заменить операции деления на операции умножения. Получается довольно быстро:
var CounterTable: array[0..9999] of byte; procedure InitCounterTable; var i1, i2, j1, j2: integer; begin; for i1:=0 to 9 do for i2:=0 to 9 do for j1:=0 to 9 do for j2:=0 to 9 do CounterTable[i1*1000 + i2*100 + j1*10 +j2] := Ord(i1<>j1) + Ord(i2<>j2); end; function OneDigitDifferent5(n1, n2: integer): boolean; const cf = 8 * 1024 * 1024 div 100 + 1; sh = 23; var d1, d2: integer; begin; if n1=n2 then Result:=false else begin; d1:=n1 * cf; d2:=n2 * cf; d1:=d1 shr sh; d2:=d2 shr sh; n1:=n1 - d1 * 100; d2:=d2 * 100; Result:=(CounterTable[n2-d2+n1*100] + CounterTable[d1+d2] = 1); end; end;
Каждый раз при решении этой задачи приходится в том или ином виде опускаться до работы с отдельными цифрами или частями чисел. Но давайте обратим внимание на то, что при операциях сложения или вычитания, изменяющих только одну цифру числа, точно также изменяется сумма его цифр. Это наблюдение делает лишним само выделение разрядов числа, позволяя нам работать целиком со всем числом, а не с его частями. Суммы цифр для чисел от 0 до 9999 мы вычислим предварительно и сохраним в таблице, благодаря этому работа с ними будет быстрой. Разумеется, нам также необходимо проверить допустимость разности чисел. Для этого все допустимые значения разности мы поместим в хеш-таблицу. В итоге результат будет вычислен всего за 4 обращения к памяти:
const DeltaMask = 511; MaxNumber = 9999; type TDeltaElem = record ds: integer; dn: integer; end; var DeltaTable: array[0..DeltaMask] of TDeltaElem; SumTable: array[0..MaxNumber] of Shortint; function SetDelta(dsValue, dnValue: integer): integer; var i: integer; begin; i:=dnValue and DeltaMask; Result:=DeltaTable[i].dn; DeltaTable[i].ds:=dsValue; DeltaTable[i].dn:=dnValue; end; function CalcSum(n: integer): integer; var t: integer; begin; Result:=0; while n>0 do begin; t:=n div 10; Result:=Result + n - t*10; n:=t; end; end; function InitDeltaAndSum: integer; var i: integer; begin; Result:=0; // force OneDigitDifferent(n1,n2)=false for n1=n2 DeltaTable[0].ds:=-1; DeltaTable[0].dn:=-1; for i:=1 to DeltaMask do DeltaTable[i].dn:=0; for i:=1 to 9 do Result:=Result or SetDelta(i, i) or SetDelta(i, i*10) or SetDelta(i, i*100) or SetDelta(i, i*1000); for i:=0 to MaxNumber do SumTable[i]:=CalcSum(i); end; function OneDigitDifferent6(n1, n2: integer): boolean; var dn: integer; begin; dn:=n2-n1; n2:=SumTable[n2]; n1:=SumTable[n1]; n2:=n2-n1; if dn<0 then begin; dn:=-dn; n2:=-n2; end; n1:=dn and DeltaMask; dn:=dn-DeltaTable[n1].dn; n2:=n2-DeltaTable[n1].ds; Result:= dn or n2 = 0; end;
Отсечение недопустимых разностей при помощи хеш-таблицы можно использовать для усовершенствования рассмотренных ранее функций, например:
function OneDigitDifferent7(n1, n2: integer): boolean; var delta: integer; begin; delta:=abs(n1-n2); if delta<>DeltaTable[delta and DeltaMask].dn then begin; Result:=false; exit; end; if n1<n2 then n1:=n2; if delta<10 then Result:=(delta <= n1 mod 10) else if delta<100 then Result:=(delta <= n1 mod 100) else if delta<1000 then Result:=(delta <= n1 mod 1000) else Result:=true; end;
Небольшое усложнение хеш-функции позволяет уменьшить размер хеш-таблицы. При этом можно работать даже с девятизначными десятичными числами почти без потери скорости:
type TDivisor = record divisor: integer; delta: integer; end; const HashMul = 16788946; HashShift = 24; HashMax = (1 shl (32-HashShift)) - 1; var DivisorTable: array[0..HashMax] of TDivisor; function SetDivisor(divisor, delta: integer): integer; var i: integer; begin; i:=delta * HashMul shr HashShift; Result:=DivisorTable[i].delta; DivisorTable[i].divisor:=divisor; DivisorTable[i].delta:=delta; end; function InitDivisors: integer; var i: integer; begin; Result:=0; // force OneDigitDifferent(n1,n2)=false for n1=n2 DivisorTable[0].divisor:=-1; DivisorTable[0].delta:=-1; for i:=1 to High(DivisorTable) do DivisorTable[i].delta:=0; for i:=1 to 9 do Result:=Result or SetDivisor(10, i) or SetDivisor(100, i*10) or SetDivisor(1000, i*100) or SetDivisor(10000, i*1000) or SetDivisor(100000, i*10000) or SetDivisor(1000000, i*100000) or SetDivisor(10000000, i*1000000) or SetDivisor(100000000, i*10000000) or SetDivisor(1000000000, i*100000000); end; // valid for 0<=(n1,n2)<1000000000 function OneDigitDifferent8(n1, n2: integer): boolean; var delta, divisor: integer; begin; delta:=n1-n2; if n1<n2 then begin; delta:=-delta; n1:=n2; end; n2:=delta * HashMul shr HashShift; divisor:=DivisorTable[n2].divisor; if delta<>DivisorTable[n2].delta then Result:=false else Result:=(delta <= n1 mod divisor); end;
или даже с десятизначными десятичными числами, представимыми в типе cardinal:
type TUDivisor = record divisor: cardinal; delta: cardinal; end; var UDivisorTable: array[0..HashMax] of TUDivisor; function SetUDivisor(divisor, delta: cardinal): cardinal; var i: integer; begin; i:=delta * HashMul shr HashShift; Result:=UDivisorTable[i].delta; UDivisorTable[i].divisor:=divisor; UDivisorTable[i].delta:=delta; end; function InitUDivisors: cardinal; var i: integer; begin; Result:=0; // force OneDigitDifferent(n1,n2)=false for n1=n2 UDivisorTable[0].divisor:=10; UDivisorTable[0].delta:=1; for i:=1 to High(UDivisorTable) do UDivisorTable[i].delta:=0; for i:=1 to 9 do Result:=Result or SetUDivisor(10, i) or SetUDivisor(100, i*10) or SetUDivisor(1000, i*100) or SetUDivisor(10000, i*1000) or SetUDivisor(100000, i*10000) or SetUDivisor(1000000, i*100000) or SetUDivisor(10000000, i*1000000) or SetUDivisor(100000000, i*10000000) or SetUDivisor(1000000000, i*100000000); Result:=Result or SetUDivisor($FFFFFFFF, 1000000000) or SetUDivisor($FFFFFFFF, 2000000000) or SetUDivisor($FFFFFFFF, 3000000000) or SetUDivisor($FFFFFFFF, 4000000000); end; // valid for any n1, n2 function OneDigitDifferent9(n1, n2: cardinal): boolean; var delta, divisor: cardinal; begin; delta:=n2-n1; if n2<n1 then begin; delta:=-delta; n1:=n2; end; n2:=delta * HashMul shr HashShift; divisor:=UDivisorTable[n2].divisor; if delta<>UDivisorTable[n2].delta then Result:=false else Result:=(n1 mod divisor + delta + 1 <= divisor); end;
Время работы функций на различных компьютерах:
Time(ms) of 3*10^9 runs =============================================== i5-2300 E6850 Pentium-D Function 3.0GHz 3.0GHz 2.8GHz ----------------------------------------------- Empty function 5906 6015 10859 OneDigitDifferent2 18000 17688 71141 OneDigitDifferent3 18766 17172 72844 OneDigitDifferent4 13734 22109 52875 OneDigitDifferent5 10313 11266 35797 OneDigitDifferent6 7375 8047 16625 OneDigitDifferent7 7453 8218 19328 OneDigitDifferent8 8953 9157 20328 OneDigitDifferent9 8953 9156 20297
Вероятно, суть оптимизации состоит в том, чтобы делать как можно меньше лишних действий. Делать проще и делать одновременно — это тоже хорошо, но не в этом суть. Суть именно в лени. В том, чтобы не делать лишнего. Только лень существенно экономит время и усилия, заставляя выбирать другой маршрут к цели.
А вдруг, лениться полезно? Я так думаю. Я не делаю лишнего?