Все очень просто

Май 7, 2012 — Шарахов А.П.

Особенно арифметика, не так ли? Не верится, что можно программировать, не зная целочисленной арифметики. Хотя…

Самая быстрая на Земле

Обычно при использовании быстрой сортировки QuickSort применяют такую функцию сравнения целых чисел:

function CompareInt(Item1, Item2: pointer): integer;
begin;
  if integer(Item1^)<integer(Item2^) then Result:=-1
  else if integer(Item1^)>integer(Item2^) then Result:=+1
  else Result:=0;
  end;

Задача этой функции - выдавать любое положительное значение, если первое число больше второго, отрицательное значение, если первое число меньше второго, и 0 при равенстве чисел. Похожую функцию мы ранее использовали в тестах производительности быстрой сортировки. Но не потому, что она самая быстрая, а потому, что мы хотели играть по-честному и использовать функцию сравнения из библиотеки RTL Delphi.

В приведенной функции имеются 2 сравнения, что совсем не делает ее мониеносно быстрой. Почему бы вместо этого не использовать разность параметров в качестве результата, например, так:

//Wrong function
function VeryBadCompareInt(Item1, Item2: pointer): integer;
begin;
  Result:=integer(Item1^)-integer(Item2^);
  end;

Получилось быстро, но неверно. Если при вычислении разности произойдет переполнение, то это приведет к ошибочному результату.

Заметим, что переполнение не может возникнуть при вычитании чисел одного знака. Для строгости в скобках также замечу, что в целочисленной арифметике число может либо иметь знак и быть отрицательным, либо не иметь знака и быть нулем или положительным.

С другой стороны, если параметры функции имеют разные знаки, то в качестве результата функции можно просто вернуть первый параметр. Правда, есть одно исключение – первый параметр может оказаться нулем, который возвращать нельзя, ведь у нас числа имеют разные знаки, и, следовательно, они не совпадают. Обойти эту проблему можно, установив 1 в любом незнаковом бите первого параметра.

И, наконец, для быстрой проверки одинаковости знаков параметров подойдет операция "исключающее или", которая даст неотрицательный результат в этом случае.

Суммируя сказанное, получаем самую быструю на Земле функцию сравнения целых:

//First of all we test are the signs of integers the same.
//If it is so we calculate difference as result without risk of overflow.
//For different signs we can't use the first integer as result because it may be zero, but we can suppress zero value. 
function ShaCompareInt(Item1, Item2: Pointer): Integer;
var
  Second: integer;
begin;
  Result:=Integer(Item1^);
  Second:=Integer(Item2^);
  if Result xor Second>=0
    then Result:=Result-Second
    else Result:=Result or 1;
  end;

Попробуйте применить ее в любой версии QuickSort.

... и самая неожиданная (08.04.2017)

Но что делать, если требуется отсортировать массив целых так, чтобы в начале массива располагались все четные числа по убыванию, а затем все нечетные по возрастанию?

Мы опять возьмем самую быструю функцию сравнения:

function Cmp1(i1, i2: integer): integer;
begin;
  if i1 xor i2>=0
  then i1:=i1-i2
  else i1:=i1 or 1;
  Result:=i1;
  end;

и преобразуем ее так, чтобы она подходила для нашей задачи, но при этом не содержала дополнительных сравнений:

const
  m=-MaxInt-1; //MinInt
 
//произвольные числа: четные по убыванию, затем нечетные по возрастанию
function Cmp2(i1, i2: integer): integer;
begin;
  i1:=(i1 xor m) shr 1 xor -(i1 and 1 xor 1);
  i2:=(i2 xor m) shr 1 xor -(i2 and 1 xor 1);
  if i1 xor i2>=0
  then i1:=i1-i2
  else i1:=i1 or 1;
  Result:=i1;
  end;

Несколько необычно видеть жонглирование битами (bit twiddling) в функции сравнения. Не ясно также, дает ли этот финт прирост в скорости.

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

Итак, во-первых, необходимо избавиться от младшего бита и освободить старший разряд для нового знака числа, сдвинув все биты на 1 позицию вправо. Но из-за того, что старший бит бывших отрицательных чисел равен 1, они при таком сдвиге станут больше положительных. Чтобы этого не произошло и после сортировки бывшие отрицательные числа внутри своей группы разместились до положительных, мы предварительно инвертируем старший бит:

  j:=(i xor m) shr 1;

Во-вторых, необходимо выделить и инвертировать младший бит, чтобы использовать его в качестве знака измененного числа. Когда результат этой операции равен 0, мы имеем дело с нечетным числом, и дополнительных изменений не требуется. Когда результат равен 1, мы имеем дело с четным числом, и в измененном числе требуется вместо 0 установить 1 в знаковом разряде, а также инвертировать остальные биты числа (чтобы сделать большие числа маленькими для сортировки по убыванию в первой группе чисел). И то, и другое обеспечивается логическим сложением с -1, поэтому достаточно сменить знак у результата:

  k:=-(i and 1 xor 1);

И, наконец, соединим обе части в одно целое:

  //i:=j xor k;
  i:=(i xor m) shr 1 xor -(i and 1 xor 1);

Теперь настало время вернуться к вопросу о скорости. Совершенно ясно, что неразумно преобразовывать элементы массива при каждом сравнении. Это можно сделать один раз перед сортировкой. Затем отсортировать массив с использованием самой быстрой функции сравнения. И после сортировки вернуть прежние значения элементам (попробуйте разобраться самостоятельно, как это сделано):

  for i:=0 to Length(Arr)-1 do Arr[i]:=(Arr[i] xor m) shr 1 xor -(Arr[i] and 1 xor 1);
  Sort(Arr);
  for i:=0 to Length(Arr)-1 do Arr[i]:=(Arr[i] shl 1 xor m) xor -(Arr[i] shr 31) xor 1;

При таком упрощении функции сравнения и вынесении дополнительных преобразований в пре- и постобработку итоговая скорость сортировки массива с помощью QuickSort увеличивается примерно в 1.5 раза.

Интересно, что скорость работы RadixSort практически не зависит от вида функции выбора ключа. Для проверки решения данной задачи использовалась функция:

function RadixKey(Item: pointer): integer;
begin;
  Result:=(integer(Item) xor m) shr 1 xor (-(integer(Item) and 1 xor 1)) xor m;
  end;

Попробуйте догадаться, почему ее "начинка" отличается от предварительной обработки для QuickSort наличием финального сложения "xor m".

Прямое попадание

Иногда приходится проверять попадание целого числа (знакового или беззнакового) в некоторый диапазон [a..b):

if (a<=x) and (x<b) then …

Обычно одна-две проверки не составляют серьезной проблемы, но если их становится слишком много, с ними приходится бороться даже ценой ухудшения читаемости и усложнения отладки программы.

Давайте вспомним, что фактически целочисленные операции сложения и вычитания выполняются процессором без учета знака числа по модулю 2^32 (или 2^64 для Int64). А "знаковость" числа или результата используется при необходимости его расширения до большей длины, в операциях сравнения и при выводе числа функциями типа IntToStr.

Таким образом, перенос нуля в нижнюю границу интервала повлечет за собой перенос всех значений, лежащих вне интервала, за его верхнюю границу. Поэтому, в предположении, что a, b, x – одинаково объявленные 32-битные переменные, можно написать более быстрое условие, эквивалентное приведенному выше:

if cardinal(x-a)<cardinal(b-a) then …

Ну вот, надеюсь, теперь процессору станет легче, а во вселенной – прохладнее.

Забери их отсюда, чтобы они здесь не тикали

"Завернутость по модулю" операций сложения и вычитания не осознается многими новичками и не всегда используется даже опытными программистами. Яркий пример тому – вычисление длины интервала времени между последовательными моментами вызова функции GetTickCount.

Казалось бы, куда проще:

var
  Tick1, Tick2, Delta: Cardinal;
begin;
  Tick1:=GetTickCount;
  //some code here
  Tick2:=GetTickCount;
  Delta:=Tick2-Tick1;

Все это будет прекрасно работать, если только вам не требуется измерять интервалы времени больше 7 недель (более точно, цикл таймера составляет приблизительно 49.7 суток).

Тем не менее, встречаются функции вроде

//Wrong function
function TickDiff(const StartTick, EndTick: Cardinal): Cardinal;
begin;
  if EndTick>=StartTick
    then Result:=EndTick-StartTick
    else Result:=High(Cardinal)-StartTick+EndTick;
  end;

Что не так с этой функцией? Во-первых, по высоте полета фантазии она довольно сильно смахивает на всеми любимый IncDay, просто непонятно, зачем писать функцию, когда достаточно обычного вычитания. Во-вторых, дополнительная проверка, которая позволяет избежать переполнения, совершенно не требуется, т.к. абсолютно не влияет на результат. В-третьих, если вычисления пойдут по ветке else, то результат будет отличаться от правильного ровно на 1.

Кроме того, давайте задумаемся, что произойдет, если присвоить результат этой функции переменной типа Integer. Теоретически можно получить отрицательное значение, хотя, конечно, это очень маловероятно.

Иногда встречаются даже вот такие неудачные попытки борьбы с несуществующей угрозой:

//Wrong code
var
  Tick1, Tick2: Int64;
  Delta: Integer;
begin;
  Tick1:=GetTickCount;
  //some code here
  Tick2:=GetTickCount;
  Delta:= Tick2-Tick1;

которые также не спасают от отрицательного результата.

На самом деле все довольно просто: для того чтобы получить знаковое целое (Integer) из беззнакового (Cardinal), достаточно просто обнулить знаковый бит:

var
  Tick1, Tick2: Cardinal;
  Delta: Integer;
begin;
  Tick1:=GetTickCount;
  //some code here
  Tick2:=GetTickCount;
  Delta:=(Tick2-Tick1) and MaxInt;

Очевидно, при этом надо помнить, что по сравнению с использованием типа Cardinal максимальный измеримый интервал сокращается в 2 раза.

Бит установлен – это минус

Известно, что у отрицательных целых чисел старший (знаковый) бит имеет значение 1. Логические операторы работают со знаковым битом в точности так же, как с любым другим. В частности, после сдвига вправо на 31 бит любое отрицательное число типа Integer превращается в 1. А логическое произведение 100 отрицательных чисел будет отрицательным только в том случае, когда все 100 чисел отрицательны.

Применение логических операторов может ускорить, упростить и усложнить программу. Просто для того, чтобы почувствовать их в деле, приведу решение задачи, в которой требуется определить среднюю длину непрерывных участков неотрицательных чисел в массиве целых чисел:

function AverageLen(a: PIntegerArray; len: integer): double;
const
  rig =  SizeOf(a[0])*8-1;
var
  i, k, n: integer;
begin;
  k:=len;
  n:=0;
  for i:=0 to len-1 do begin;
    dec(k,a[i] shr rig);
    inc(n,(a[i] xor a[(i+1) mod len]) shr rig);
    end;
  Result:=0;
  if k>0 then begin;
    n:=(n+2-(a[0] or a[len-1]) shr rig) shr 1;
    Result:=k/n;
    end;
  end;

Можете считать, что материал усвоен, если вам кажется, что в приведенном решении достаточно комментариев.

Отчего люди не летают?

Понятно, что можно работать с отдельными байтами числа типа Integer, выделяя их при помощи операций логического умножения и/или сдвига. Но довольно интригующе выглядит одновременная работа со всеми байтами числа как с байтовым вектором. Для этого достаточно применять такие операции, которые не приводят к переносу результата между байтами. В качестве иллюстрации рассмотрим 2 функции быстрого сравнения строк без учета регистра (аналоги CompareText).

type
{$if CompilerVersion<=18.5}
  NInt=  integer;
  UInt = cardinal;
{$else}
  NInt=  NativeInt;
  UInt = NativeUInt;
{$ifend}
 
function ShaCompareText7(const s1, s2: AnsiString): integer;
var
  p1, p2: UInt;
  len, rest: integer;
  i1, i2: cardinal;
begin;
  p2:=UInt(s2);
  p1:=UInt(s1);
  i2:=0;
  len:=0;
  if p2<>0 then i2:=pIntegerArray(p2)[len+(-1)];
  if p1<>0 then len:=pIntegerArray(p1)[len+(-1)];
 
  Result:=len-integer(i2);
  if (len=0) or (i2=0) then exit;
 
  if len>integer(i2) then len:=i2;
  rest:=len and 3;
  if rest=0 then begin;
    dec(len);
    rest:=4;
    end;
  len:=len shr 2;
 
  inc(pInteger(p1), len);
  inc(pInteger(p2), len);
  len:=-len;
 
  repeat;
    i1:=pIntegerArray(p1)[len];
    i2:=pIntegerArray(p2)[len];
    if len<0 then begin;
      inc(len);
      if i1=i2 then continue;
      i1:=(i1 or $80808080 xor i1) and (i1 or $80808080 - $7B7B7B7B or $80808080 - $66666666) shr 2 xor i1;
      i2:=(i2 or $80808080 xor i2) and (i2 or $80808080 - $7B7B7B7B or $80808080 - $66666666) shr 2 xor i2;
      if i1=i2 then continue;
      len:=4;
      end
    else begin;
      if i1=i2 then exit;
      i1:=(i1 or $80808080 xor i1) and (i1 or $80808080 - $7B7B7B7B or $80808080 - $66666666) shr 2 xor i1;
      i2:=(i2 or $80808080 xor i2) and (i2 or $80808080 - $7B7B7B7B or $80808080 - $66666666) shr 2 xor i2;
      if i1=i2 then exit;
      len:=rest;
      end;
    break;
    until false;
 
  repeat;
    if (i1 xor i2) and 255<>0 then begin;
      Result:=i1 and 255 - i2 and 255;
      exit;
      end;
    dec(len);
    i1:=i1 shr 8;
    i2:=i2 shr 8;
    until len=0;
  end;

Высокая скорость этой функции достигается за счет чтения данных из обеих строк двойными словами. В случае несовпадения считанных данных они преобразуются к верхнему регистру и снова сравниваются.

type
{$if CompilerVersion<=18.5}
  NInt=  integer;
  UInt = cardinal;
{$else}
  NInt=  NativeInt;
  UInt = NativeUInt;
{$ifend}
 
function ShaCompareText8(const s1, s2: AnsiString): integer;
var
  p1, p2: UInt;
  len, rest: integer;
  i1, i2: cardinal;
begin;
  p2:=UInt(s2);
  p1:=UInt(s1);
  i2:=0;
  len:=0;
  if p2<>0 then i2:=pIntegerArray(p2)[len+(-1)];
  if p1<>0 then len:=pIntegerArray(p1)[len+(-1)];
 
  Result:=len-integer(i2);
  if (len=0) or (i2=0) then exit;
 
  if len>integer(i2) then len:=i2;
  rest:=len and 3;
  if rest=3 then begin;
    inc(len);
    rest:=0;
    end;
  len:=len shr 2;
 
  inc(pInteger(p1), len);
  inc(pInteger(p2), len);
  len:=-len;
 
  while true do begin;
    if len=0 then break;      
    i1:=pIntegerArray(p1)[len];
    i2:=pIntegerArray(p2)[len];
    inc(len);
    if i1=i2 then continue;
    i2:=i2 xor i1;
    i1:=i1 or i2;
    i1:=(i1 or $80808080 xor i1) and (i1 or $80808080 - $7B7B7B7B or $80808080 - $66666666) shr 2;
    if i2 and not i1=0 then continue;
    dec(len);
    rest:=4;
    break;
    end;
 
  if rest>0 then begin;
    i1:=pIntegerArray(p1)[len];
    i2:=pIntegerArray(p2)[len];
    if i1=i2 then exit;
    i1:=(i1 or $80808080 xor i1) and (i1 or $80808080 - $7B7B7B7B or $80808080 - $66666666) shr 2 xor i1;
    i2:=(i2 or $80808080 xor i2) and (i2 or $80808080 - $7B7B7B7B or $80808080 - $66666666) shr 2 xor i2;
    if i1=i2 then exit;
    len:=rest;
    repeat;
      if (i1 xor i2) and 255<>0 then begin;
        Result:=i1 and 255 - i2 and 255;
        exit;
        end;
      dec(len);
      i1:=i1 shr 8;
      i2:=i2 shr 8;
      until len=0;
    end;
  end;

Эта функция работает быстрее предыдущей на строках, имеющих длинный общий префикс, за счет меньшего числа преобразований, необходимых для принятия положительного решения.

Старая школа

Иногда умение делить в столбик помогает решать довольно интересные задачи. Простым числом Вифериха называется такое простое число p, что 2^(p-1)-1 делится на p^2 без остатка. Следующая функция находит все известные сегодня простые числа Вифериха без использования "длинной" математики:

function IsWieferichNumber(Number: integer): boolean;
var
  Dividend, Divisor: integer;
begin;
  Divisor:=Number*Number;
  Dividend:=0;
  dec(Number);
  repeat;
    Dividend:=Dividend+Dividend+1;
    if Dividend>=Divisor then Dividend:=Dividend-Divisor;
    dec(Number);
    until Number<=0;
  Result:=(Dividend=0);
  end;
 
procedure TForm1.Button1Click(Sender: TObject);
var
  i: integer;
begin;
  for i:=1 to $7FFF do if IsWieferichNumber(i) then Memo1.Lines.Add(IntToStr(i));
  Memo1.Lines.Add('done');
  end;

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

Продолжение следует. Под ногами все время путаются разные мелкие хитрости. Буду наступать на них здесь.

на главную

Comments (2)

ты ошибся

cmp и sub для процессора отличаются только "холостой" работой первого
в целочисленной арифметике постоянно происходят переполнения, и это не отменяет корректной работы

(-2147483648)-(-2147483647)=-1
X < Y. верно

(-2147483647)-(-2147483648)=1
X > Y. верно

(-2147483648)-(-2147483648)=0
X = Y. верно

ты забыл сказать, где

))