Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Количество бит в байте

Страницы: < 1 2 3 4 5 >
Kerk © (2007-10-04 15:47:00)
Прислали тут тестовое задание.. и есть там вот этот пунктик:

3. Напишите функцию, которая принимает на вход байт и возвращает кол-во установленных в нем битов.
Сделайте несколько вариантов функции:
а) Оптимизированной по скорости
б) Оптимизированной по памяти
в) Компромиссный вариант
----

Вижу оптимальным такой вариант:

function BitsInByte(B: Byte): Integer; begin Result := 0; while B > 0 do begin Result := Result + (B and 1); B := B shr 1; end; end;

Это видимо оптимизировано по памяти.. еще меньше памяти использовать невозможно. Какой же тогда оптимизированный по скорости? Ну можно забить массив (1, 2, 4, 8 .... ) и по нему в цикле пробивать and'ом. Это памяти ест чуть больше, но не факт, что работает быстрее моего первого варианта. А компромиссный-то вариант какой? Что-то я запутался. Хелп плиз.

Суслик (2007-10-05 13:40:00) [21]
а при значении 3242432 ?

может суслик (лень проверять, если честно)

oxffff (2007-10-05 13:21:00) [22]

> Jeer © (05.10.07 13:00) [66]
> oxffff © (05.10.07 11:01) [58]
> Rouse_ © (05.10.07 10:41) [56]
>
> Попробуйте Jeer © (04.10.07 18:01) [34] и удивляйтесь.
>

А чему собственно?

при значении 0

1625 (Rouse)
1344 (oxffff) <-
1734 (Jeer)

при значении 128

7204 (Rouse)
2296 (oxffff) <-
4844 (Jeer)

при значении 31

3953 (Rouse) <-
9609 (oxffff)
4828 (Jeer)

при значении 255

7188 (Rouse)
15812 (oxffff)
5078 (Jeer) <-

Суслик (2007-10-05 13:02:00) [23]

> [66] Jeer © (05.10.07 13:00)
> oxffff © (05.10.07 11:01) [58]
> Rouse_ © (05.10.07 10:41) [56]
>
> Попробуйте Jeer © (04.10.07 18:01) [34] и удивляйтесь.

а лучше [59]

Jeer (2007-10-05 13:00:00) [24]
oxffff © (05.10.07 11:01) [58]
Rouse_ © (05.10.07 10:41) [56]

Попробуйте Jeer © (04.10.07 18:01) [34] и удивляйтесь.

oxffff (2007-10-05 12:49:00) [25]

> Но на "неплотных" единичках разрыв будет в разы.

А на плотных отставание в разы. :)

oxffff (2007-10-05 12:48:00) [26]

> FindBitCount($FFFFFF);

FindBitCount($FFFFFFFF);

Но тогда ты лидируешь в 2 раза . А inline сделает разрыв больше.

Спешу согласиться, что на плотных единичках твой код будет быстрее
, тогда как мой быстрее будет на неплотных единичках.
Оно и понятно
bsf+shr+inc vs shr+adc

Но на "неплотных" единичках разрыв будет в разы.

oxffff (2007-10-05 12:39:00) [27]

> Rouse_ © (05.10.07 12:16) [62]
>
> > А вот тут ты лукавишь. Попробуй так
>
> Хе, класс :))) Но 255 рулит по любому :))))

Опять лукавиш. У тебя проверяет байт, а меня у 4 байта.
Так что умножай свой результат на четыре. :)

Вот так будет справедливое сравнение .

procedure TForm1.FormCreate(Sender: TObject);
var
I: Integer;
V1, V2: DWORD;
begin
V1 := GetTickCount;
for I := 0 to 200000000 do
begin
BitCount(255);
BitCount(255);
BitCount(255);
BitCount(255);
end;
Memo1.Lines.Add(IntToStr(GetTickCount - V1)); // 5300 - моя победила :)
V2 := GetTickCount;
for I := 0 to 200000000 do
FindBitCount($FFFFFF);
Memo1.Lines.Add(IntToStr(GetTickCount - V2)); //6000
end;

Так что здесь тоже победа за мной.

Тебя может спасти только inline. Да и только ручками.

Но на "неплотных" единичках разрыв будет в разы.

Rouse_ (2007-10-05 12:16:00) [28]

> А вот тут ты лукавишь. Попробуй так

Хе, класс :))) Но 255 рулит по любому :))))

Суслик (2007-10-05 11:15:00) [29]

> [59] Суслик © (05.10.07 11:03)

это из книги "Алгоритмические трюки для программистов" Генри Уоррен, мл.
Оригинальное название "Hackers's Delight" Henry S. Warren, Jr.

Там вся книга из таких вот хитрых решений :)

> [60] oxffff © (05.10.07 11:07)

не офтопь - почта есть.

oxffff (2007-10-05 11:07:00) [30]

> Суслик © (05.10.07 11:03) [59]

offtop.
Дмитрий я последовал твоему совету. Меня приняли.
Спасибо тебе. :)
Осталось подключить безлимитный инет.

Суслик (2007-10-05 11:03:00) [31]
на си:

x = (x & 0x55555555) + ((x >> 1) & 0x55555555) x = (x & 0x33333333) + ((x >> 2) & 0x33333333) x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F) x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF) x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF)

для 32-битного числа.

oxffff (2007-10-05 11:01:00) [32]

> Мой код разгромил твой в 5 раз.
>
> УРА!!!!!!!!!!!!!!!

Мой код считает в 5 раз быстрее для четырех байтов, чем твой для одного. Итого в 20 раз byte per byte.

Это разгром!!!! УрА!!!!!!! Четыре раза

oxffff (2007-10-05 10:53:00) [33]

> 5300 - моя победила :)

А вот тут ты лукавишь. Попробуй так

procedure TForm1.FormCreate(Sender: TObject);
var
I: Integer;
V1, V2: DWORD;
begin
V1 := GetTickCount;
for I := 0 to 20000000 do
BitCount(128);
Memo1.Lines.Add(IntToStr(GetTickCount - V1)); // 5300 - моя победила :)
V2 := GetTickCount;
for I := 0 to 20000000 do
FindBitCount(128);
Memo1.Lines.Add(IntToStr(GetTickCount - V2)); //6000
end;

Мой код разгромил твой в 5 раз.

УРА!!!!!!!!!!!!!!!

Rouse_ (2007-10-05 10:41:00) [34]

> Мой код 17 байт работает c integer и шустрее.

Ну это то просто проверить :)

function BitCount(const Value: Byte): Byte; asm and ax, $FF shr al, 1 @@: adc ah, 0 shr al, 1 jnz @@ adc ah, 0 shr ax, 8 end; function FindBitCount(a:integer):integer; asm xor edx,edx; @Continue: bsf ecx,eax; jz @done inc ecx; shr eax,cl; inc edx jmp @Continue; @done: mov eax,edx; end; procedure TForm29.FormCreate(Sender: TObject); var I: Integer; V1, V2: DWORD; begin V1 := GetTickCount; for I := 0 to 200000000 do BitCount(123); Memo1.Lines.Add(IntToStr(GetTickCount - V1)); // 5300 - моя победила :) V2 := GetTickCount; for I := 0 to 200000000 do FindBitCount(123); Memo1.Lines.Add(IntToStr(GetTickCount - V2)); //6000 end;

> Звиняй если чем обидел.

Да ты что, какие блин обиды? :) Мыж спорили а не ругались :)

oxffff (2007-10-05 10:40:00) [35]

> Rouse_ © (05.10.07 10:29) [51]
> А, инкремент - согласен, тут ступил :)
>
> function BitCount(const Value: Byte): Byte;
> asm
> and ax, $FF
> clc
> shr al, 1
> @@: adc ah, 0
> shr al, 1
> jnz @@
> shr ax, 8
> end;

Вот по размеру хоть идентично. 17 байт.

oxffff (2007-10-05 10:36:00) [36]

> Rouse_ © (05.10.07 10:30) [52]
> блин, теперь точно CLC не нужен :)))

Теперь 18 байт. Но [53].

Ладно. Хватит писками мериться. :)
А то со стороны наверно полный LOL.
Звиняй если чем обидел.

oxffff (2007-10-05 10:33:00) [37]

> and ax, $FF

Кто я чудак? Ты что милейший?

LOL.
Твой алгоритм 19 байт работает с byte.

Мой код 17 байт работает c integer и шустрее.

Зритель сделает вывод сам, кому из нас незачет.

Rouse_ (2007-10-05 10:30:00) [38]
блин, теперь точно CLC не нужен :)))

Rouse_ (2007-10-05 10:29:00) [39]
А, инкремент - согласен, тут ступил :)

function BitCount(const Value: Byte): Byte; asm and ax, $FF clc shr al, 1 @@: adc ah, 0 shr al, 1 jnz @@ shr ax, 8 end;

Rouse_ (2007-10-05 10:28:00) [40]

> Твой алгоритм медленный да еще и бажный

Чудак, мой алгорит решает задачу в рамках задачи :)
Считает кол-во взведенных бит в байте, а не в Integer. В корайнем случае ничкто не мешает сделать вызов and ax, $FF
А по поводу скорости - замеряй, твой тормозит :)

Страницы: < 1 2 3 4 5 >

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »