Электронный научный журнал
Современные проблемы науки и образования
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 0,791

МОДЕЛИРОВАНИЕ РАЗРЯДНОГО РАСПАРАЛЛЕЛИВАНИЯ СРАВНЕНИЙ СТРОКОВЫХ И ЧИСЛОВЫХ ЭЛЕМЕНТОВ

Ромм Я.Е. 1 Белоконова С.С. 1
1 Таганрогский институт имени А.П. Чехова (филиал) РГЭУ (РИНХ)
В статье представлен метод поразрядно-параллельного алгебраического сложения n-разрядных чисел, который не включает операций вычисления переноса, и способ поразрядно-параллельного сравнения чисел и элементов строкового типа на его основе. Отмечены особенности применения метода для выполнения операций сравнения с временной сложностью O(1) независимо от числа символов сравниваемых строк, это выявляет потенциальную применимость метода для ускорения информационного поиска. Основной и конкретной целью излагаемой работы является программный эксперимент по моделированию поразрядно-параллельных сравнений элементов строкового типа для верификации разрабатываемого метода и алгоритмов на его основе. Приводится код программы на языке Delphi, посредством которой выполняется моделирование сравнений с разрядным распараллеливанием, описываются результаты эксперимента, подтверждающие достоверность метода и правильность работы предложенных алгоритмов.
разрядное распараллеливание алгебраического сложения -разрядных чисел
поразрядно-параллельное сравнение слов
моделирование сравнений с разрядным распараллеливанием
1. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. I. Приложение к бинарным арифметическим операциям // Кибернетика и системный анализ. – 1998. – № 3. – С. 123-151.
2. Ромм Я.Е. Метод вертикальной обработки потока целочисленных групповых данных. II. Приложение к бинарным арифметическим операциям // Кибернетика и системный анализ. – 1998. – № 6. – С. 146-162.
3. Ромм Я.Е., Белоконова С.С. Детерминированный информационный поиск на основе сортировки с распараллеливанием базовых операций. – М.: Научный мир, 2014. – 198 с.
4. Ромм Я.Е., Иванова А.С. Вертикальное групповое алгебраическое суммирование применительно к сортировке со слиянием и параллельному поиску / ТГПИ. – Таганрог, 2012. – 44 с. Деп. в ВИНИТИ 03.09.2012, № 362 – В 2012.
5. Ромм Я.Е., Иванова А.С. Вертикальные групповые арифметические операции над целочисленными данными без вычисления переноса. // «Фундаментальные исследования». №11 (4). – 2012. – С. 960 – 964
6. Ромм Я.Е., Чабанюк Д.А. Применение метода вертикальной обработки информации к операциям сравнения и поиска / ТГПИ – Таганрог, 2013. – 32 c. Деп. в ВИНИТИ 20.05.13, № 141 – В 2013.
7. Ромм Я.Е., Чабанюк Д.А. Сравнение слов с единичной временной сложностью // Известия ЮФУ. Технические науки. – № 7(156). – 2014. – С. 230 – 238.
8. Ромм Я.Е. Бесконфликтные и устойчивые методы детерминированной параллельной обработки / Диссертация на соискание ученой степени доктора технических наук. – Таганрог: ТРТУ. – 1998. – 546 с.; ВНТИ Центр. – № 05.990.001006.
9. Царев Р.Ю. Структуры и алгоритмы обработки данных. – Красноярск: Сиб.федер.ун-т, 2013. – 160с.
10. Чернов А.Ф. Ускорение поиска в индексах на основе R-деревьев // Программные продукты и системы, 2012. №2 (98), С. 46 - 50.

Постановка вопроса. Тема ускорения информационного поиска актуальна практически для всех существующих информационных систем [9, 10]. В качестве алгоритмической основы разработки быстродействующих систем поиска можно рассматривать разрядное распараллеливание операций сравнения слов и элементов строкового типа. С этой целью ниже излагается метод поразрядно-параллельного алгебраического сложения чисел, который не включает операций вычисления переноса, далее, излагается способ его переноса на случай поразрядно-параллельного сравнения чисел и данных строкового типа. Целью переноса является разработка основы для максимально параллельного выполнения базовых операций поиска, включая сравнение, сортировку, и распространение метода одновременно на поиск чисел и строк. Конкретной задачей излагаемого сообщения является программный эксперимент по моделированию предложенного поразрядно-параллельного сравнения элементов строкового типа для верификации разрабатываемого метода и алгоритмов на его основе. В работе приводится программа, по которой выполняется моделирование, и описываются результаты эксперимента.

Метод поразрядно-параллельного алгебраического сложения заимствуется из [1, 2]. Пусть два двоичных полинома

, , , , (1)

условно расположены в двух входных разрядных сетках (РС), и , номера клеток которых совпадают с индексами коэффициентов из (1).

. (2)

Синхронно и взаимно независимо по всем номерам разрядов из (2) выполняется операция суммирования двоичных коэффициентов равного веса по вертикали (). Результат представляется в двоичном коде

, , . (3)

Коэффициенты из (3) располагаются по диагонали двух выходных РС, – и , образуя диагональную от j-го разряда запись (-запись) вида

. (4)

Предварительный результат сложения:

, (5)

где , из (4), .

Все переносы в (5) оказываются взаимно отделенными вертикальными парами нулей:

, ,

где , из (5), , поскольку [2] при любом из (4) складываются не более двух единиц одинакового веса. Аналогично, в (4) по диагонали – записи от 1 в не может располагаться 1 в . На этой основе корректным является следующее преобразование промежуточного набора (5). Все разряды, имеющие значение , из (и только из ) в (5) подвергаются тождественному преобразованию:

, . (6)

При этом правая часть (6) размещается в j-й клетке и в -й клетке в порядке – записи для всех номеров j преобразуемых разрядов:

(7)

Преобразование (7) корректно, поскольку в -й клетке всегда находится ноль – до применения (6) – при условии, что в , иначе – запись означала бы результат сложения трех единиц веса -го разряда, тогда как их число не больше двух [1, 2].

Вслед за тем параллельно по всем выполняется шаг вертикального сложения, результатом которого в каждом разряде всегда будет либо 0, либо , либо [1, 2]. При этом значение знакоразрядного кода расположится в, где, таким образом, сформируется окончательное значение вычисляемой суммы и из (1).

Временная сложность параллельного сложения в знакоразрядном коде составит при количестве элементов сумматора пропорциональном числу разрядов слагаемых:

, .

Сравнение двоичных чисел. Предполагается, что сравниваемые числа имеют формат (1) с нумерацией разрядов справа налево. Пусть число принимается за уменьшаемое, – за вычитаемое, тогда записывается в обратном коде (единицы заменяются нулями, нули – единицами), затем используется тождественное преобразование [6]:

, (8)

с учетом

, (9)

или, в позиционной системе,

. (10)

Над числом и числом , взятым в обратном коде, параллельно по всем номерам разрядов выполняется операция , затем и (в обратном коде) суммируются по схеме (2) – (7). Для восстановления правильного результата вычитания учитывается (8) – (10): от однорядного знакоразрядного двоичного кода полученного результата следует вычесть . Это равносильно тому, что с полученным результатом складывается – к младшему разряду добавляется , а к разряду веса добавляется .

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

Разрядное распараллеливание сравнения строк. Метод переносится [4, 5] на сравнение элементов строкового типа, для краткости, – строк. Все символы представляются в ASCII-коде в двоичной форме. Набор двоичных кодов всех символов строки в порядке расположения интерпретируется как единое числовое значение. Сравнение полученных двоичных кодов выполняется путем алгебраического сложения, изложенным поразрядно-параллельным способом, однако при этом, в соответствии с лексикографическим упорядочением слов, выравнивание весов разрядов выполняется по старшим разрядам, недостающие младшие разряды дополняются нулями. Например, сравниваются слова 'poisk' и 'primer'. Их двоичный код с выравниваем старших разрядов соответственно примет вид:

0 1 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0

0 1 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 1 0

Слово «poisk» интерпретируется как уменьшаемое, «primer» – как вычитаемое. После перевода вычитаемого в обратный код алгебраическому сложению подлежат:

0 1 1 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 1 1 0 1 0 1 1 0 0 0 0 0 0 0 0

1 0 0 0 1 1 1 1 1 0 0 0 1 1 0 1 1 0 0 1 0 1 1 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 1 0 1 0 0 0 1 1 0 1

Параллельно по всем номерам разрядов выполняется операция :

Согласно (5) – (7) выполняется преобразование:

Параллельное по всем разрядам суммирование по вертикали влечет:

1 0 0 0 0 0 0 0 0 0 0 -1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 -1 0 0 1 0 -1 1 -1

Результат корректируется в соответствии (8) – (11), что влечет окончательное значение алгебраической суммы

0 0 0 0 0 0 0 0 0 0 0 -1 1 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 -1 0 0 1 0 -1 1 0

Старший ненулевой разряд отрицателен, следовательно, первое слово лексикографически меньше второго: 'poisk' < 'primer'.

Замечание 1. Поразрядно-параллельное нахождение старшего ненулевого разряда в знакоразрядном коде – самостоятельная схемотехническая задача. Такой разряд требуется выделить программно или аппаратно, что возможно, например, при помощи схемы, представленной в [7]. Можно, с другой стороны, выделить старший ненулевой разряд аналогично нормализации мантиссы числа с плавающей точкой с помощью параллельного сдвигателя, описанного в [8]. Ниже решение этой задачи не обсуждается.

С учетом данного замечания изложенное бинарное сравнение независимо от числа разрядов занимает время одной бинарной операции над двоичными коэффициентами одного веса –

,

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

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

program Proverka;

{$APPTYPE CONSOLE}

uses

SysUtils;

CONST nn=100000;

S1='poisk'; S2='primer' ;

type mass=array[0..nn{*8}] of Integer;

var

a,b,a1,b1,a4,b4, a2,b2,a3,b3:mass;

s3:string;

cod,ii,y,n,m,i,k:integer;

function IntToBin(x:LongInt):string;

varres:string;

begin

RES:='';

while x<>0 doBegin

if (x mod 2=0) then res:='0'+res else res:='1'+res;

x:=x div 2; end;

while (Length(Res)<>8) do res:='0'+res;

IntToBin:=Res;

end;

procedure Assc(c:string;nm:Integer; var x:mass);

beginfor i:=1 to nm do x[i]:=Ord(c[i]);end;

procedure Assctobin(x: mass;nm:Integer; var x1:mass);

beginy:=1;

for i:=1 to n do

begin

s3:=inttobin(x[i]);

for ii:=1 to 8 dobegin

val(s3[ii],x1[y],cod);y:=y+1;end;

end;

end;

procedure srav(varx,y:mass;nm:Integer; varxr,yr:mass);

var i:integer;

begin

for i:=1 to nm*8 do

if y[i]=1 then y[i]:=0 else y[i]:=1; writeln; writeln;

for i:=1 to nm*8 do

if (x[i]=1) and (y[i]=1) then

begin a2[i]:=0;b2[i-1]:=1; end

else a2[i]:=a1[i]+b1[i];

Writeln ('massiv a2 i b2');

for i:=1 to n*8 do write(a2[i]:5);writeln;writeln;

for i:=1 to n*8 do write(b2[i]:5);writeln; writeln;

for i:=0 to nm*8 do

if (a2[i]=1) then a3[i]:=-1 else a3[i]:=a3[i];

for i:=0 to nm*8 dobegin b3[i]:=b2[i];

if (a3[i]=-1) then b3[i-1]:=1; end;

Writeln ('massiv a3 i b3');

for i:=1 to n*8 do write(a3[i]:5); writeln; writeln;

for i:=1 to n*8 do write(b3[i]:5);writeln; writeln;

for i:=0 to n*8 do

if (a3[i]=1) and (b3[i]=1) then

beginxr[i]:=0;yr[i-1]:=1;end

elsexr[i]:=a3[i]+b3[i];

xr[0]:= xr[0]-1;xr[nm*8]:=xr[nm*8]+1;end;

begin

n:=length(s1); m:=length(s2);

Assc(s1,n,a); Assc(s2,m,b);

writeln ('assci-kodeslova 1');

for i:=1 to n do write(a[i]:5);writeln;writeln;

writeln ('massiv b ');

for i:=1 to m do write(b[i]:5); Writeln; Writeln;

Assctobin(a,n,a1);Assctobin(b,m,b1);

if m>n then n:=m;

Writeln ('massiv a1 i b1');

for i:=1 to n*8 do write(a1[i]:5);writeln;writeln;

for i:=1 to n*8 do write(b1[i]:5); writeln; writeln;

srav(a1,b1,n,a4,b4);

Writeln ('massiv a4 i b4');

for i:=0 to n*8 dowrite(a4[i]:5); writeln; writeln;

for i:=0 to n*8 do write(b4[i]:5); writeln; writeln;

i:=0;

while (a4[i]=0)and (i<>n*8) do i:=i+1;

if a4[i]<0 then writeln ('1<2') else

if a4[i]>0 then writeln ('1>2')else writeln ('1=2');

Readln;

Readln;

{ TODO -oUser -cConsole Main : Insert code here }

end.

1. На вход программы были поданы 2 предложения S1 и S2.

S1='Уже было начало июня, когда князь Андрей, возвращаясь домой, въехал опять в ту березовую рощу, в которой этот старый, корявый дуб так странно и памятно поразил его.'

S2='Уже было начало июня, когда, возвращаясь домой, мы въехали в березовую рощу.'

В результате работы программы был получен верный результат сравнения: S1< S2.

2. Если в этих же исследуемых строках удалить все знаки препинания, то получится другой, но также верный результат: S1> S2.

3. В следующем примере в сравнении рассматривается только фрагменты строк, сформированные следующим образом:

t:=pos('мой',s1);

s11:=copy(s1,t,6);

writeln(s11);

t:=pos('мой',s2);

s22:=copy(s2,t,6);

S1='Уже было начало июня, когда князь Андрей, возвращаясь домой, въехал опять в ту березовую рощу, в которой этот старый, корявый дуб так странно и памятно поразил его.';

S2='Уже было начало июня, когда возвращаясь домой, въехали в березовую рощу.';

Таким образом, на вход программы для сравнения были поданы следующие фрагменты строк:

S11 ='мой, в'

S22='мой, в'

ASCII-код символов S11: 236 238 233 44 32 226

ASCII-код символов S22:236 238 233 44 32 226

Соответственные двоичные формы ASCII-кодов:

1 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 0

1 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 0

С представлением вычитаемого в обратном коде получится:

1 1 1 0 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 1 0 0 0 0 0 1 1 1 0 0 0 1 0

0 0 0 1 0 0 1 1 0 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 0 0 0 1 1 1 0 1

Представление промежуточной суммы:

0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Преобразование (6), (7) влечет:

Результат поразрядно-параллельного выполнения :

Коррекция суммы в соответствии с формулами (8), (9):

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Таким образом, сравниваемые элементы строк равны между собой: S11=S22.

4. Метод непосредственно применим для сравнения целых чисел с тем изменением, что сравниваемые числа выравниваются по младшему разряду.

Например, представленная программа выдаст сравнение строковых констант '16' и '24': S1<S2.

5. При сравнении целых чисел разной разрядности следует предварительно дополнить меньшее число предшествующими незначимыми нулями. Так, для сравнения чисел 160 и 24 они предварительно должны быть преобразованы в строки вида '160' и '024'.

6. С выравниванием порядков эта схема переносится на сравнение вещественных чисел с плавающей точкой. В этом случае представленная программа выдаёт: '16.05'>'16.03', '16.005'<'17.003', '016.050'<'170.003'.

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

В [3] приводится близкий к изложенному способ, при этом он непосредственно объединяет поиск чисел и слов. В файле при помощи сортировки ищутся абсолютные величины разностей ASCII-кодов строк или их элементов, аbs (ord()-ord()), или непосредственно разности чисел в формате представления языка программирования, аbs (х-у). Нулевое значение разности, в последнем случае с точностью до приближения, означает искомое значение. С выравниванием порядков эти операции осуществимы поразрядно-параллельным способом, отсюда на изложенной основе возможно объединение операций поиска чисел с плавающей точкой и элементов строкового типа.

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

Рецензенты:

Боженюк А.В., д.т.н., профессор кафедры информационно аналитических систем безопасности Инженерно-технологическая академия Южного федерального университета, г. Таганрог;

Карелин В.П., д.т.н., профессор, заведующий кафедрой прикладной математики и информационных технологий Таганрогского института управления и экономики, г. Таганрог.


Библиографическая ссылка

Ромм Я.Е., Белоконова С.С. МОДЕЛИРОВАНИЕ РАЗРЯДНОГО РАСПАРАЛЛЕЛИВАНИЯ СРАВНЕНИЙ СТРОКОВЫХ И ЧИСЛОВЫХ ЭЛЕМЕНТОВ // Современные проблемы науки и образования. – 2015. – № 2-1.;
URL: http://science-education.ru/ru/article/view?id=21302 (дата обращения: 20.09.2019).

Предлагаем вашему вниманию журналы, издающиеся в издательстве «Академия Естествознания»
(Высокий импакт-фактор РИНЦ, тематика журналов охватывает все научные направления)

«Фундаментальные исследования» список ВАК ИФ РИНЦ = 1.074