О пользе лени

Октябрь 29, 2011 — Шарахов А.П.

Давно уже пора начать программировать, но как-то не начинается. Может быть, если еще немного подождать, все произойдет само собой? А вдруг, лениться полезно?

Честно говоря, не знаю, зачем может потребоваться эта функция, но на одном форуме был задан такой вопрос. Дано два целых числа из диапазона 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

Вероятно, суть оптимизации состоит в том, чтобы делать как можно меньше лишних действий. Делать проще и делать одновременно — это тоже хорошо, но не в этом суть. Суть именно в лени. В том, чтобы не делать лишнего. Только лень существенно экономит время и усилия, заставляя выбирать другой маршрут к цели.

А вдруг, лениться полезно? Я так думаю. Я не делаю лишнего?

на главную