ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Микширование бит
25 сообщений из 104, страница 2 из 5
  2  все
Микширование бит
    #40022880
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Polesov

Похоже, у меня ошибка - в ТЗ младший бит результата = младший бит 2-го аргумента


Ну это не критично
Я свой код не проверял )
...
Рейтинг: 0 / 0
27.11.2020, 19:41
| Ответить | Цитировать | Написать  
Микширование бит
    #40022881
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Polesov
Участник
SOFT FOR YOU
Та-даааа )

Имя, сестра, имя ... )
Какие в итоге результаты?
...
Рейтинг: 0 / 0
27.11.2020, 19:41
| Ответить | Цитировать | Написать  
Микширование бит
    #40022882
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Dimitry Sibiryakov

SOFT FOR YOUогромных заранее рассчитанных таблиц?

Табличка в 256 word (то бишь 512 байт) - огромна?


Ну через таблицы понятно как решить
Я чёт думал, что можно через умножения и сдвиги
А похоже что нельзя
Мож Шарахов придёт, интересный вариант накатает )
...
Рейтинг: 0 / 0
27.11.2020, 19:42
| Ответить | Цитировать | Написать  
Микширование бит
    #40022883
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alekcvp
Участник
Leonid Kudryavtsev

Почему "Result shl 1" ?

Потому что он "вдвигает" по 1му биту из WordA, а WordB остаётся на месте.
...
Рейтинг: 0 / 0
27.11.2020, 19:42
| Ответить | Цитировать | Написать  
Микширование бит
    #40022884
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Polesov,

Ну у кого как
У меня получилось в 2 раза быстрее, чем твой
...
Рейтинг: 0 / 0
27.11.2020, 19:43
| Ответить | Цитировать | Написать  
Микширование бит
    #40022886
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Polesov
Участник
SOFT FOR YOU
Polesov,

Ну у кого как
У меня получилось в 2 раза быстрее, чем твой

Странно, у меня получилось, что твой вариант быстрее всего на ~2%, что и понятно - меньше переходов.
Видимо, зависит от модели процессора.
Если будет не влом, реализую твой алгоритм на asm и сравню ... )
...
Рейтинг: 0 / 0
27.11.2020, 19:52
| Ответить | Цитировать | Написать  
Микширование бит
    #40022890
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alekcvp
Участник
Polesov
У меня получился выигрыш ~17%

Во-первых, надо увеличить количество итераций в 100 раз, а то у меня разброс времени выполнения от 170 до 240 при разных запусках.

Во-вторых, вот читерский вариант:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function MixPas2( w1, w2 : word ) : dWord;
const
  Mask: array [0..15] of Word =
    ($0001, $0002, $0004, $0008, $0010, $0020, $0040, $0080,
     $0100, $0200, $0400, $0800, $1000, $2000, $4000, $8000);
var
  i : integer;
begin
  Result := 0;
  for i := 15 downto 0 do
    Result := Result shl 1 or DWORD(w1 and Mask[i]) shl 1 or DWORD(w2 and Mask[i]);
end;



У меня на компе вот так:
Код: plaintext
1.
2.
3.
302845473 302845473 302845473
Asm: 14204237
Pas: 14497624
Tbl: 11670659

SOFT FOR YOU,

Результат твоего кода не совпадает с нашим.
...
Рейтинг: 0 / 0
27.11.2020, 19:56
| Ответить | Цитировать | Написать  
Микширование бит
    #40022891
istrebitel
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
istrebitel
Гость
...
Рейтинг: 0 / 0
27.11.2020, 19:56
| Ответить | Цитировать | Написать  
Микширование бит
    #40022892
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Polesov
Участник
alekcvp
Polesov
У меня получился выигрыш ~17%

Во-первых, надо увеличить количество итераций в 100 раз, а то у меня разброс времени выполнения от 170 до 240 при разных запусках.

Во-вторых, вот читерский вариант:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
function MixPas2( w1, w2 : word ) : dWord;
const
  Mask: array [0..15] of Word =
    ($0001, $0002, $0004, $0008, $0010, $0020, $0040, $0080,
     $0100, $0200, $0400, $0800, $1000, $2000, $4000, $8000);
var
  i : integer;
begin
  Result := 0;
  for i := 15 downto 0 do
    Result := Result shl 1 or DWORD(w1 and Mask[i]) shl 1 or DWORD(w2 and Mask[i]);
end;



У меня на компе вот так:
Код: plaintext
1.
2.
3.
302845473 302845473 302845473
Asm: 14204237
Pas: 14497624
Tbl: 11670659

SOFT FOR YOU,

Результат твоего кода не совпадает с нашим.
А, понял, он тоже слова местами меняет.

Да, этот вариант быстрее
...
Рейтинг: 0 / 0
27.11.2020, 20:03
| Ответить | Цитировать | Написать  
Микширование бит
    #40022893
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Ну мне кажется нет разницы, сначала идут биты w1 или w2
Ассемблер можно посмотреть дизассемблировав функцию (Ctrl+Alt+C в отладке)

Там кстати сделано в 3 регистра :)
...
Рейтинг: 0 / 0
27.11.2020, 20:05
| Ответить | Цитировать | Написать  
Микширование бит
    #40022894
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
alekcvp,

Ты можешь ускорить свой вариант
Можно проинициализировать переменную Mask стартовым значением
Сделать repeat/until цикл, где на каждой итерации модифицируется Result и потом сдвигается Mask
При достижении Mask определенного значения - выходить из цикла
...
Рейтинг: 0 / 0
27.11.2020, 20:12
| Ответить | Цитировать | Написать  
Микширование бит
    #40022899
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alekcvp
Участник
SOFT FOR YOU
alekcvp,

Ты можешь ускорить свой вариант
Можно проинициализировать переменную Mask стартовым значением
Сделать repeat/until цикл, где на каждой итерации модифицируется Result и потом сдвигается Mask
При достижении Mask определенного значения - выходить из цикла

Я уже забил маску в таблицу. Со сдвигом маски будет медленнее, я проверял.
Самый быстрый цикл - for , по крайней мере раньше был.
Хотел сделать свой ассеблерный вариант, но обломался.
На Z80 была команда сдвига через флаги (то ли ZF, то ли CF, не помню уже), был очень удивлён не обнаружив ничего похожего в x86...
...
Рейтинг: 0 / 0
27.11.2020, 20:46
| Ответить | Цитировать | Написать  
Микширование бит
    #40022901
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Polesov
Участник
SOFT FOR YOU
Polesov,

Ну у кого как
У меня получилось в 2 раза быстрее, чем твой


Вот такая простыня оказалась самой быстрой )
 
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.
76.
77.
78.
79.
80.
81.
82.
83.
84.
85.
86.
87.
88.
89.
90.
91.
92.
93.
94.
95.
96.
97.
98.
99.
100.
101.
102.
103.
104.
105.
106.
107.
108.
109.
110.
111.
112.
113.
114.
115.
116.
117.
118.
119.
120.
121.
122.
123.
124.
125.
126.
127.
128.
129.
130.
131.
132.
133.
134.
135.
136.
137.
138.
139.
140.
141.
142.
143.
144.
145.
146.
147.
148.
149.
150.
151.
152.
153.
154.
155.
156.
157.
158.
159.
160.
161.
162.
163.
164.
165.
166.
167.
168.
169.
170.
171.
function MixBig( w1, w2 : word ) : dWord; assembler; register;
asm
     Push    EBX

     Xor     EBX,    EBX

@@00:
     Test    EDX,    0001h
     Jz      @@01
     Or      EBX,    00000001h

@@01:
     Test    EAX,    0001h
     Jz      @@02
     Or      EBX,    00000002h

@@02:
     Test    EDX,    0002h
     Jz      @@03
     Or      EBX,    00000004h

@@03:
     Test    EAX,    0002h
     Jz      @@04
     Or      EBX,    00000008h

@@04:
     Test    EDX,    0004h
     Jz      @@05
     Or      EBX,    00000010h

@@05:
     Test    EAX,    0004h
     Jz      @@06
     Or      EBX,    00000020h

@@06:
     Test    EDX,    0008h
     Jz      @@07
     Or      EBX,    00000040h

@@07:
     Test    EAX,    0008h
     Jz      @@08
     Or      EBX,    00000080h

@@08:
     Test    EDX,    0010h
     Jz      @@09
     Or      EBX,    00000100h

@@09:
     Test    EAX,    0010h
     Jz      @@10
     Or      EBX,    00000200h

@@10:
     Test    EDX,    0020h
     Jz      @@11
     Or      EBX,    00000400h

@@11:
     Test    EAX,    0020h
     Jz      @@12
     Or      EBX,    00000800h

@@12:
     Test    EDX,    0040h
     Jz      @@13
     Or      EBX,    00001000h

@@13:
     Test    EAX,    0040h
     Jz      @@14
     Or      EBX,    00002000h

@@14:
     Test    EDX,    0080h
     Jz      @@15
     Or      EBX,    00004000h

@@15:
     Test    EAX,    0080h
     Jz      @@16
     Or      EBX,    00008000h

@@16:
     Test    EDX,    0100h
     Jz      @@17
     Or      EBX,    00010000h

@@17:
     Test    EAX,    0100h
     Jz      @@18
     Or      EBX,    00020000h

@@18:
     Test    EDX,    0200h
     Jz      @@19
     Or      EBX,    00040000h

@@19:
     Test    EAX,    0200h
     Jz      @@20
     Or      EBX,    00080000h

@@20:
     Test    EDX,    0400h
     Jz      @@21
     Or      EBX,    00100000h

@@21:
     Test    EAX,    0400h
     Jz      @@22
     Or      EBX,    00200000h

@@22:
     Test    EDX,    0800h
     Jz      @@23
     Or      EBX,    00400000h

@@23:
     Test    EAX,    0800h
     Jz      @@24
     Or      EBX,    00800000h

@@24:
     Test    EDX,    1000h
     Jz      @@25
     Or      EBX,    01000000h

@@25:
     Test    EAX,    1000h
     Jz      @@26
     Or      EBX,    02000000h

@@26:
     Test    EDX,    2000h
     Jz      @@27
     Or      EBX,    04000000h

@@27:
     Test    EAX,    2000h
     Jz      @@28
     Or      EBX,    08000000h

@@28:
     Test    EDX,    4000h
     Jz      @@29
     Or      EBX,    10000000h

@@29:
     Test    EAX,    4000h
     Jz      @@30
     Or      EBX,    20000000h

@@30:
     Test    EDX,    8000h
     Jz      @@31
     Or      EBX,    40000000h

@@31:
     Test    EAX,    8000h
     Jz      @@32
     Or      EBX,    80000000h

@@32:
     Mov     EAX,    EBX

     Pop     EBX
end;

...
Рейтинг: 0 / 0
27.11.2020, 21:09
| Ответить | Цитировать | Написать  
Микширование бит
    #40022902
Фотография Квейд
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Квейд
Участник
Polesov
SOFT FOR YOU,
Такие вещи на ассемблере, как правило, быстрее.
В основном, за счет регистровой ручной оптимизации - нет обращений к стеку.
сейчас обращение к стеку по скорости мало чем отличается от обращения к регистру
...
Рейтинг: 0 / 0
27.11.2020, 21:25
| Ответить | Цитировать | Написать  
Микширование бит
    #40022905
Polesov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Polesov
Участник
Квейд
сейчас обращение к стеку по скорости мало чем отличается от обращения к регистру

Все же обращение к стеку хоть и немного, но медленнее обращения к регистру - где-то на 0.08%

Замерял на этом коде:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
procedure MovReg; assembler;
asm
     Mov    ECX,    100000000

@@10:
     Mov    EAX,    EBX
     Loop   @@10
end;

procedure MovMem; assembler;
asm
     Mov    ECX,    100000000

@@10:
     Mov    EAX,    dword ptr [EBP - 04h]
     Loop   @@10
end;
...
Рейтинг: 0 / 0
27.11.2020, 21:49
| Ответить | Цитировать | Написать  
Микширование бит
    #40022912
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alekcvp
Участник
Polesov

Вот такая простыня оказалась самой быстрой )


А вот фиг:
 
Ассеблер для упоротых :)
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
function MixAsm2( w1, w2 : word ) : dWord; assembler; register;
asm
  push    ebx
  push    ebp
  movzx   ebx, al
  shl     ebx, 16
  shl     eax, 8   // w1 - eax, ebx
  movzx   ecx, dl
  shl     ecx, 16
  shl     edx, 8   // w2 - edx, ecx
  mov     ebp, $8

@@loop:
  shr     ax, 1
  shr     bx, 1
  shr     eax, 1
  shr     ebx, 1
  shr     ecx, 1
  shr     edx, 1
  shr     cx, 1
  shr     dx, 1
  dec     ebp
  jnz     @@loop

  or      eax, edx
  shl     eax, 16
  or      ebx, ecx
  or      eax, ebx

  pop     ebp
  pop     ebx
end;


Код: plaintext
1.
BIG: 9331272
AA2: 8216673
...
Рейтинг: 0 / 0
27.11.2020, 22:24
| Ответить | Цитировать | Написать  
Микширование бит
    #40022915
SOFT FOR YOU
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SOFT FOR YOU
Участник
Выложите полный файл
А то сравниваете не понятно что с чем :)
...
Рейтинг: 0 / 0
27.11.2020, 22:32
| Ответить | Цитировать | Написать  
Микширование бит
    #40022917
Фотография makhaon
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
makhaon
Участник
посмотрел список команд. увы, но проц нативно биты не почередует, ничего подходящего нет.
мне ассемблерный вариант с or mask нравится. наверно это лучшее, что можно сдлать
...
Рейтинг: 0 / 0
27.11.2020, 22:34
| Ответить | Цитировать | Написать  
Микширование бит
    #40022919
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alekcvp
Участник
Всё, быстрее уже не получается :)

Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
function MixAsm2( w1, w2 : word ) : dWord; assembler; register;
asm
  push    ebx
  movzx   ebx, al
  shl     eax, 8   // w1 - eax, ebx
  shl     ebx, 16
  movzx   ecx, dl
  shl     edx, 8   // w2 - edx, ecx
  shl     ecx, 16
  or      ebx, $7FFF

@@loop:
  shr     ecx, 1
  shr     edx, 1
  shr     cx, 1
  shr     dx, 1
  shr     ax, 1
  shr     bx, 1
  shr     eax, 1
  shr     ebx, 1
  jc      @@loop

  or      eax, edx
  shl     eax, 16
  or      ebx, ecx
  or      eax, ebx
  pop     ebx
end;
...
Рейтинг: 0 / 0
27.11.2020, 22:49
| Ответить | Цитировать | Написать  
Микширование бит
    #40022924
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
alekcvp,

так немного быстрее
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
function ShaMix(w1, w2: dword): dword;
begin;
  w1:=(w1 or w1 shl 8) and $00FF00FF;
  w2:=(w2 or w2 shl 8) and $00FF00FF;
  w1:=(w1 or w1 shl 4) and $0F0F0F0F;
  w2:=(w2 or w2 shl 4) and $0F0F0F0F;
  w1:=(w1 or w1 shl 2) and $33333333;
  w2:=(w2 or w2 shl 2) and $33333333;
  w1:=(w1 or w1 shl 1) and $55555555;
  w2:=(w2 or w2 shl 1) and $55555555;
  w1:=w1+w1;
  w1:=w1+w2;
  Result:=w1;
  end;
...
Рейтинг: 0 / 0
28.11.2020, 01:34
| Ответить | Цитировать | Написать  
Микширование бит
    #40022927
L1G
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
L1G
Участник
Вы что-то, ребята, затупили и с таблицами не попробовали.
Сибиряков правильно подсказал, они небольшие. Только их 2 нужно:
Код: pascal
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
var tbl0, tbl1: array[Byte] of Word;

procedure InitTables();
  var i, j, d, mask: byte;
begin
  for i:=0 to 255 do
  begin
    d := 0;
    for j := 0 to 7 do
    begin
      mask := 1 shl j;
      d := d or ((j and mask) shl j);
    end;
    tbl0[i] := d shl 1;
    tbl1[i] := d;
  end;
end;

function TableMix(w1, w2: word): dWord;
begin
  Result := ((tbl0[Hi(w1)] or tbl1[Hi(w2)]) shl 16) or tbl0[Lo(w1)] or tbl1[Lo(w2)];
end;
...
Рейтинг: 0 / 0
28.11.2020, 01:47
| Ответить | Цитировать | Написать  
Микширование бит
    #40022928
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alekcvp
Участник
Aleksandr Sharahov,

Только по условиям задачи тип параметров - word.

L1G,

Только время генерации таблиц тоже включай 🤣
...
Рейтинг: 0 / 0
28.11.2020, 01:50
| Ответить | Цитировать | Написать  
Микширование бит
    #40022929
Aleksandr Sharahov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aleksandr Sharahov
Участник
alekcvp
Aleksandr Sharahov,

Только по условиям задачи тип параметров - word.


Значит, надо исправить условия.
...
Рейтинг: 0 / 0
28.11.2020, 01:51
| Ответить | Цитировать | Написать  
Микширование бит
    #40022930
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alekcvp
Участник
Но да, там всё равно уже бесполезно рыпаться 😁
...
Рейтинг: 0 / 0
28.11.2020, 01:53
| Ответить | Цитировать | Написать  
Микширование бит
    #40022932
alekcvp
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alekcvp
Участник
Aleksandr Sharahov,

Кстати, если её вручную на ассемблер перевести, то там прилично так в скорости прибавляется, чуть больше 20 процентов.
Всё-таки у новых дельфей с оптимизатором беда... 😒
...
Рейтинг: 0 / 0
28.11.2020, 02:10
| Ответить | Цитировать | Написать  
25 сообщений из 104, страница 2 из 5
  2  все
Форумы / Delphi [игнор отключен] [закрыт для гостей] / Микширование бит
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=58&msg=40022912&tid=2037816]:
 0ms
get settings:
 7ms
get forum list:
 14ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 174ms
get topic data:
 8ms
get forum data:
 2ms
get page messages:
 68ms
get tp. blocked users:
 1ms
others: 204ms
total:  484ms
созд. / загр.: 484ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]