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);

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

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

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

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

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

← →
Pavia © (2006-06-05 15:26) [29]

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

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

← →
tesseract © (2006-06-05 15:32) [30]

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

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

← →
Pavia © (2006-06-05 20:06) [31]

Прочел там написанно что в канце цикла указывается 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 будет не определенно.

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

← →
Джо © (2006-06-05 20:08) [32]

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

← →
begin...end © (2006-06-05 20:14) [33]

> tesseract © (05.06.06 12:16) [17]

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

Зачем?

← →
Pavia © (2006-06-05 20:28) [34]

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

← →
begin...end © (2006-06-05 20:37) [35]

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

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

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

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

← →
Pavia © (2006-06-05 20:48) [36]

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

← →
Pavia © (2006-06-05 20:50) [37]

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

← →
begin...end © (2006-06-05 20:52) [38]

> 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

← →
Джо © (2006-06-05 20:58) [39]

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

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

← →
Pavia © (2006-06-05 21:04) [40]

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

← →
Джо © (2006-06-05 21:05) [41]

> [40] Pavia © (05.06.06 21:04)
> Джо
> Я лично решил на Free Pascal перебираться. Там этого касяка
> нет.

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

← →
begin...end © (2006-06-05 21:09) [42]

> Pavia © (05.06.06 21:04) [40]

> Я лично решил на Free Pascal перебираться. Там этого касяка
> нет.

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

← →
Pavia © (2006-06-05 21:09) [43]

В доках не видно на практика код
var
I: Integer;
begin
for I := 1 to 5 do;
ShowMessage(IntToStr(I))
end
Выдал 5

← →
Kolan © (2006-06-05 21:12) [44]

> Выдал 5

С оптимизацией?

← →
tesseract © (2006-06-05 21:17) [45]

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

Кстати кроме break и exit возможно и изменение состояния счётчика, после выхода из цикла он может быть меньше макс значения , больше макс значения или равен макс значению.
Borland заявляет, что не факт что текущее состояние дел сохраниться в следующих выпусках (из книги по D5 если не ошибаюсь).

← →
Pavia © (2006-06-05 21:23) [46]

Kolan ©
3 уровень плюс не стандартная плюс регистры.
Стандарт паскаля мы уже разобрали там про это ни слова.

Сейчас под рукой только D7. Хотя кодил на всех начиная с D4 и зоканчивая D7. D8 Не вынес и снес, глючная больно.

Я же говорю Free pascal.

Pavia © (05.06.06 21:09) [43]

Да, упрямства тебе не занимать.
Попробуй, кстати, вот такую фичу, проверял под Delphi 2006, не знаю точно,
будет ли под остальными версиями работать:

Var
I : Integer;
Tmp : String[2];
begin
Tmp:="1";
for I := 1 to 5 do
If (I = 3) then begin
Tmp:="4";
Break;
end else
Tmp:=IntToStr(I);
Try
I:=TryStrToInt(Tmp);
Except
RunError(17);
ShowMessage("Ошибка !");
Exit;
end;
ShowMessage(IntToStr(I));
end;

Вовращает точно 4, сам проверял !
Так что ты прав, тут разработчики Delphi чего - то не учли.

Кстати, не могу сам разобраться, почему при ошибке в
I:=TryStrToInt(Tmp);
не выводится окно с сообщением об ошибке.
Если знаешь, что я не так сделал, помоги.

> Pavia © (05.06.06 21:28) [48]

А FreePascal-то тут причём, уважаемый? В [34] и [36] Вы разве не со справкой Delphi спорили? За словеса будем отвечать, или как?

Будем. Я у же сознался.

Lines property (TCustomMemo)

Warning: Unlike most TStrings objects, the Lines property stores its lines in a 1-based array, not a zero-based array.
А почему 1?

> А почему 1?

Потому что визуальные компоненты так запрограммированы.
Строка с номером 0 всегда присутствует. Если ее нет, она тут же создается.
ПОэтому невозможно для визуальных наследников получить ошибку при обращении к несуществующей строке с номером Count, Например, TMemo никогда не возвратит ошибку при обращении к Memo.Lines[Memo.Lines.Count].
В отличие от TStringList.

> Пусик © (05.06.06 22:26) [53]

> Потому что визуальные компоненты так запрограммированы.
Как "так"? Первая строка в Memo -- это строка с индексом 0, а не 1.

> Если ее нет, она тут же создается.
В самом визуальном компоненте её как не было, так и не будет. Просто в случае запроса несуществующей строки возвратится строка нулевой длины.

> begin...end © (06.06.06 07:53) [54]
> В самом визуальном компоненте её как не было, так и не будет.

Выполняю код:

Memo1.Lines.Clear; Memo1.Lines[0] := "test0";

Вижу:

В Memo появилась строка "test0"

Выполняю далее Memo1.Lines[1] := "test1";

В Memo появилась строка "test1"

>Пусик
Несколько странный спор.
откуда взято [51] - я не знаю, да и вообще про индексацию с единицы - неправда.
Твой пример [55] не противоречит begin...end © (06.06.06 07:53) [54]

> Пусик © (06.06.06 10:52) [55]

И что? Вы, насколько я понял по [53], согласны с тем, что строки в Lines нумеруются с единицы? Если так, просьба подтвердить это кодом -- возьмите Memo с двумя строчками, и, обратившись к Lines[1], получИте самую первую строчку.

По поводу кода из [55] могу только сказать, что меня такое поведение не удивляет. И порекомендовать вспомнить, что Memo.Lines -- это не TStringList, и список Lines в Memo вообще не является контейнером строк.

> begin...end © (06.06.06 11:37) [57]
>
> > Пусик © (06.06.06 10:52) [55]
>
> И что? Вы, насколько я понял по [53], согласны с тем, что
> строки в Lines нумеруются с единицы?

Конечно не согласна. :-)

Про такое поведение я только недавно узнала. В исходниках видно, почему так происходит. Хотя и непонятно, зачем такое сделано.

← →
MikeZ (2006-06-07 13:18) [59]

Так, прошу всех не драться :-)

Таки да, виноват я, некорректно сформулровал вопрос - спешил...

Дано: есть три одинаковых массива (A,B,C), тип эл-та - integer.
Надо: i-му эл-ту 3-го массива (C) присвоить значение C[i] := A[i] XOR B[i].

Я это делал в цикле, проходя по всем эл-там массива. И хотелось узнать, можно ли делать XOR для массива целиком, а не по-элементно. Под словом "целиком" понимается не C := A XOR B, а какой-нибудь алгоритм, работающий быстрее моего. Как именно работающий - неважно.

2 Real: твой код таки медленнее - по моим расчетам в 8 раз.

2 Pavia: буду твой проверять :-)

> а какой-нибудь алгоритм, работающий быстрее моего. Как
> именно работающий - неважно.

Если массив имеено байт то код pavia должен быть в 4 раза быстрее.

← →
MikeZ (2006-06-07 14:11) [61]

В принципе - именно байт. Так что посмотрю.

← →
Sapersky (2006-06-07 17:12) [62]

Вот с MMX.
В 2 с лишним раза быстрее варианта Pavia (в 1.5 - если сделать там аналогичную развёртку цикла), но:
- результат будет в Src1, а не в отдельном массиве - писал по аналогии с [7], сейчас лень переделывать.
- адреса массивов должны быть выравнены на 8 (т.е. кратны 8). Нужно либо выравнивать вручную (Delphi выравнивает на 4), либо выделять память чем-нибудь вроде VirtualAlloc, который, если не ошибаюсь, выравнивает на 64k. Я для тестирования использовал битмапы, они тоже хорошо выравниваются.
- тестировал на Cel2.8, выяснилось, что имеет преимущество только с небольшими объёмами данных (которые помещаются в кэш), иначе ограничивает относительно медленная шина памяти.

procedure Mem_XorMMX(Src1, Src2: Pointer; Count: Integer);
// EAX = Src1, EDX = Src2, ECX = Count
asm
push esi
push edi

mov esi, eax // Src1 to esi
mov edi, edx // Src2 to edi
mov edx, ecx // copy Count to edx

shr ecx,5
jz @bytestart

@quads:
db $0F,$6F,$06 /// movq mm0,[esi]
db $0F,$6F,$4E,$08 /// movq mm1,[esi+8]
db $0F,$6F,$56,$10 /// movq mm2,[esi+16]
db $0F,$6F,$5E,$18 /// movq mm3,[esi+24]
db $0F,$EF,$07 /// pxor mm0, [edi]
db $0F,$EF,$4F,$08 /// pxor mm1, [edi+8]
db $0F,$EF,$57,$10 /// pxor mm2, [edi+16]
db $0F,$EF,$5F,$18 /// pxor mm3, [edi+24]
db $0F,$7F,$06 /// movq [esi], mm0
db $0F,$7F,$4E,$08 /// movq [esi+8], mm1
db $0F,$7F,$56,$10 /// movq [esi+16], mm2
db $0F,$7F,$5E,$18 /// movq [esi+24], mm3
add edi,32
add esi,32
dec ecx
jnz @quads

db $0F,$77 // emms

@bytestart:
mov ecx, edx
and ecx, 31 // cutting all >= 32
jz @exit

@bytes:
mov eax, [edi]
xor [esi], eax
inc edi
inc esi
dec ecx
jnz @bytes

@exit:

pop edi
pop esi
end;

Теория, если интересно:
http://www.tommesani.com/Docs.html

Sapersky
С MMX и SSE я пока не работал.
Но всеже ошибочка ;-)

@bytes:
mov al, [edi]
xor [esi], al
inc edi
inc esi
dec ecx
jnz @bytes

http://www.fastcode.sourceforge.net - интересная штучка кстати, обещают кое-где 3-х кратный прирост скорости.

← →
Sapersky (2006-06-08 13:12) [65]

Но всеже ошибочка ;-)

Да, точно. Спасибо за исправление.

http://www.fastcode.sourceforge.net

В RTL D2006 включили некоторые функции оттуда.
Только вот такой момент - на процессорах, которые в fastcode не тестируют (например P3), результаты часто получаются прямо противоположные. И без того неторопливые "старички" тормозят ещё сильнее :(

> Sapersky (08.06.06 13:12) [65]

при страте программы можно узнать тип процессора и вызывать функции напрямую.

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