XOR для массива

← →
MikeZ (2006-06-04 16:30) [0]

Всем день добрый!

Надо сделать XOR для чисел, являющихся элементами массива.
Сейчас делаю a[i] xor b[i], перебирая так весь массив.

Есть ли какой-нибудь способ делать это по-красивее и, главное, побыстрее.

← →
Rial © (2006-06-04 18:12) [1]

Это и так достаточно быстро и кравиво.
Быстродействие проверял ?
Точно уж быстрее записи, чтения и т.п. на порядок.

← →
Kolan © (2006-06-04 18:52) [2]

> Rial © (04.06.06 18:12) [1]

Я думаю автор хочек каким-то хитрым образом(может сдвигом каким-то) проXORить сразу весь массив... Мне тоже интересно возможно ли это.

← →
Asteroid © (2006-06-04 20:08) [3]

Не уверен, что это возможно, разве что можно ускорить процесс ассемблерной вставкой с операциями на XMM регистрах (movq, pxor).

← →
Rial © (2006-06-04 20:14) [4]

procedure XorData(Const MainData,KeyData :Pointer;Const MainSize,KeySize :Integer);
Var ptMain, ptKey : PByte;
I, J, D : Integer;
begin
If (MainSize<=0)or(KeySize<=0)then Exit;
D :=MainSize div KeySize;
ptMain :=MainData;
I :=0;
While (I<=D-1)do begin
ptKey :=KeyData;
J :=0;
While (J<=KeySize-1)do begin
ptMain^:=ptMain^ xor ptKey^;
Inc (ptMain);
Inc (ptKey);
Inc (J);
end;
Inc(I);
end;
D :=MainSize mod KeySize;
ptKey :=KeyData;
J:=0;
While (J<=D-1)do begin
ptMain^:=ptMain^ xor ptKey^;
Inc (ptMain);
Inc (ptKey);
Inc (J);
end;
end;

Не знаю, куда быстрее.
При сравнении с вариантом, написанном мною на асме, разницы
заметной не нашел.
Возможно, а плохо знаю ассемблер...

← →
Rial © (2006-06-04 20:15) [5]

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

← →
MikeZ (2006-06-04 21:54) [6]

Спасибо за ответ, попробуем

← →
Pavia © (2006-06-04 22:43) [7]

Rial не у меишь ты писать. Проверил я твой код. Он медленнее чем если делать по байтно.

2735 - твой код
1781 - по байтно
469 - мой код

В твоем коде много оброщений к памити.

И еще я так понил A,B одного размера.
type TAbyte=array [0..0] of byte; PAbyte=^TAbyte; TADWord=array [0..0] of DWord; PADWord=^TADWord; procedure pp1(a,b:PAbyte; size:integer); // По байтно var i:integer; begin for i:=0 to size-1 do a[i]:=a[i] xor b[i]; end; procedure pp2(a,b:PADWord; size:integer); // Мой вариант 4Байта за раз. var i:integer; begin for i:=0 to size div 4-1 do a[i]:=a[i] xor b[i]; for i:=i to size mod 4 -1 do PAbyte(a)[i]:=PAbyte(a)[i] xor PAbyte(b)[i]; end;

На асм переписать можно, но смысла невижу.

← →
Pavia © (2006-06-04 23:02) [8]

Блин. Сейчас проверил на шел ошибку у себя i пропустил.
procedure pp2(a,b:PADWord; size:integer); // Мой вариант 4Байта за раз. var i:integer; begin for i:=0 to size div 4-1 do a[i]:=a[i] xor b[i]; for i:=i to i+size mod 4 -1 do PAbyte(a)[i]:=PAbyte(a)[i] xor PAbyte(b)[i]; end;

← →
Pavia © (2006-06-04 23:04) [9]

Что-то у меня сегодня ошибка на ошибка.
procedure pp2(a,b:PADWord; size:integer); var i:integer; begin for i:=0 to size div 4-1 do a[i]:=a[i] xor b[i]; for i:=i*4 to i*4+size mod 4 -1 do PAbyte(a)[i]:=PAbyte(a)[i] xor PAbyte(b)[i]; end;
Пс модератору сотрите предыдущий пост.

← →
Loginov Dmitry © (2006-06-05 00:15) [10]

Pavia © (04.06.06 23:04) [9]
for i:=0 to size div 4-1 do
a[i]:=a[i] xor b[i];
for i:=i*4 to i*4+size mod 4 -1 do
PAbyte(a)[i]:=PAbyte(a)[i] xor PAbyte(b)[i];

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

procedure pp_(a,b:PADWord; size:integer); var i, k:integer; wA, wB: ^DWORD; begin wA := @a[0]; wB := @b[0]; for i:=0 to size div 4-1 do begin wA^ :=wA^ xor wB^; Inc(wA); Inc(wB); end; for i:=i*4 to i*4+size mod 4 -1 do PAbyte(a)[i]:=PAbyte(a)[i] xor PAbyte(b)[i]; end;

← →
Rial © (2006-06-05 00:51) [11]

Loginov Dmitry © (05.06.06 00:15) [10]
Использование счетчика цикла за самим циклом...

не у меишь
по байтно
медленнее чем
оброщений к памити
понил
невижу
ошибка на ошибка
Сейчас проверил на шел ошибку у себя i пропустил.

Я тоже могу придраться, но просили побайтно...
Мало ли, вдруг в этом вся суть ...
А так то можно и с Int64.

← →
Loginov Dmitry © (2006-06-05 10:30) [12]

Rial © (05.06.06 0:51) [11]

Будь внимательнее, когда цитируешь посты, а то могут и обидеться!

← →
han_malign © (2006-06-05 10:58) [13]

> хотя по существу является полным аналогом твоего кода
> wA^ :=wA^ xor wB^;
> Inc(wA);
> Inc(wB);

- не ребята - индексированный доступ побыстрее работает, чем разадресация с инкрементом, это нам еще в школе вдалбливали, на 80286-х...

← →
Rial © (2006-06-05 11:04) [14]

> Loginov Dmitry © (05.06.06 10:30) [12]

Извиняюсь, действительно нехорошо получилось ...

← →
Loginov Dmitry © (2006-06-05 11:37) [15]

han_malign © (05.06.06 10:58) [13]
не ребята - индексированный доступ побыстрее работает, чем разадресация с инкрементом

Это бред!

← →
MBo © (2006-06-05 11:59) [16]

>han_malign © (05.06.06 10:58) [13]

Поясни, ведь вопрос этот неоднозначен.

← →
tesseract © (2006-06-05 12:16) [17]

насчёт скорости посмотрите pascal-реализацию system.move.
Там вот такое :

procedure Move( const Source; var Dest; count : Integer ); {$IFDEF PUREPASCAL} var S, D: PChar; I: Integer; begin S := PChar(@Source); D := PChar(@Dest); if S = D then Exit; if Cardinal(D) > Cardinal(S) then for I := count-1 downto 0 do D[I] := S[I] else for I := 0 to count-1 do D[I] := S[I]; end; {$ELSE}

← →
Loginov Dmitry © (2006-06-05 12:25) [18]

Не, с какой стати "индексированный доступ побыстрее работает, чем разадресация с инкрементом"?
При индексированном доступе внутри цикла выполняются операции сдвига и сложения.
Во втором случает внутри цикла выполняется только операция сложения - операции сдвига нет, так что скорость должна (по идее) увеличиваться.

← →
tesseract © (2006-06-05 12:40) [19]

> Не, с какой стати "индексированный доступ побыстрее работает,
> чем разадресация с инкрементом"?При индексированном доступе
> внутри цикла выполняются операции сдвига и сложения.Во втором
> случает внутри цикла выполняется только операция сложения
> - операции сдвига нет, так что скорость должна (по идее)
> увеличиваться.

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

← →
Loginov Dmitry © (2006-06-05 12:43) [20]

tesseract © (05.06.06 12:40) [19]
А затраты на доп операции с памятью ?

А какие там затраты?

← →
tesseract © (2006-06-05 12:48) [21]

> А какие там затраты?

Сорри код не смотрел.
While (J<=D-1)do begin ptMain^:=ptMain^ xor ptKey^; Inc (ptMain); Inc (ptKey); Inc (J); end;

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

← →
Loginov Dmitry © (2006-06-05 13:22) [22]

В моем коде в теле цикла было все-таки 2 сложения...

← →
tesseract © (2006-06-05 13:34) [23]

> В моем коде в теле цикла было все-таки 2 сложения...

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

Профайлер врать не может.

← →
Loginov Dmitry © (2006-06-05 14:41) [24]

Повторюсь:
При индексированном способе доступа к элементам массива используется И сдвиг И сложение.

← →
Pavia © (2006-06-05 14:47) [25]

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

Бред, счетчик после цикла должен быть ровно таким каким его задал программер, а не оптимизатор. Иначе компилятор на свалку.

Дело в том что компилятор не умеет хорошо оптимизировать
Inc(wA);
Inc(wB);
Здесь идет чтение из памяти. прибавление 1 и запись обратно в память.
Сдвиг и сложение выполняется одинаково. Другое дело что мой код оптимизатор оптимизирует хорошо. Обращение к памяти происходит только для считывания данных и записи результата. Сдвиг уже предусмотрен в процессоре и не занимает процессорного времени.

← →
MBo © (2006-06-05 14:52) [26]

>Pavia © (05.06.06 14:47) [25]
>Бред, счетчик после цикла должен быть ровно таким каким его задал программер

По стандарту языка, переменная-счетчик цикла не определена после окончания цикла.

← →
Kolan © (2006-06-05 14:58) [27]

> Сдвиг уже предусмотрен в процессоре и не занимает процессорного
> времени.
>

Что вообще бесплатно? Не занимает вообще?

← →
tesseract © (2006-06-05 14:59) [28]

> Бред, счетчик после цикла должен быть ровно таким каким
> его задал программер, а не оптимизатор. Иначе компилятор
> на свалку.

Это официальное предупреждение Borland.
И на самом деле счётчик в конце цикла может иметь непредсказуемое значение (хотя я с таким не сталкивался).

> Дело в том что компилятор не умеет хорошо оптимизировать
> Inc(wA); Inc(wB);

Современный суперскаляр должен прогнать это за такт, хотя должен и прогонит вещи разные :-)

> Сдвиг уже предусмотрен в процессоре и не занимает процессорного
> времени.

Не напрягает математический сопроцессор будем точнее, он действительно почти бесплатен.

> При индексированном способе доступа к элементам массива
> используется И сдвиг И сложение.

Сдвиг проц не напряжёт.

То MBO стандарт покажи. Или где об этом написанно.

Сдвиг и сложение при вычисление адресса занимает ровно один такт.
Inc(wA); Inc(wB);
Оптимизатор я проверил в давнном случае он использует регистры. Так что простой только произходит из-за числа инструкций.

> То MBO стандарт покажи. Или где об этом написанно.

http://www.moorecad.com/standardpascal/home.html

Прочел там написанно что в канце цикла указывается final-value конечное значение. Как оно может быть не определенно???

Про то что не определенно. Так переводить надо вниметельней.
After a for-statement is executed,
other than being left by a goto-statement, the control-variable shall be undefined. Да написанно что не определенно, но читать нужно внимательней. Написанно сдесь, что значение переменной будет не определенно если выйти из цикла используя goto.
После того как будит начито выполнение for-конструкции, кроме того если будет остановленно используя goto-конструкцию, control-variable будет не определенно.

Известный факт.

After the for statement terminates, the value of counter is undefined.
Delphi Help, "For statesments" topic.

After the for statement terminates (provided this was not forced by a break or an exit procedure), the value of counter is undefined.
Я считаю ошибкой(не давно еще ошибка поподалась). Но вы в праве им верить.

> Pavia © (05.06.06 20:28) [34]

> Я считаю ошибкой...

LOL, уважаемый.

var
I: Integer;
begin
for I := 1 to 5 do;
ShowMessage(IntToStr(I))
end

Немного поразмыслив пришол к выводу, что ошибки нет значение будет не определенно только в том случае если мы выйдим используя Break или exit. О чем так коряво и написанно.

Про это я знаю. Сам пару раз на тыкался. ;-)

> Pavia © (05.06.06 20:48) [36]

> значение будет не определенно только в том случае если мы
> выйдим используя Break или exit

LOL, уважаемый.

var
I: Integer;
begin
for I := 1 to 5 do
if I = 3 then Break;
ShowMessage(IntToStr(I))
end

> [36] Pavia © (05.06.06 20:48)
> Немного поразмыслив пришол к выводу,

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

Джо
Я лично решил на Free Pascal перебираться. Там этого касяка нет.
Что-то я много на спамил. Все закругляюсь.

XOR для массива Найти похожие ветки