Цепочки битов

← →
Servelat © (2007-09-25 02:26) [0]

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

В общем-то, чтобы уменьшить количество изобретаемых велосипедов, я воспользовался стандартным классом TBits (пронаследоваться не получилось, так как некоторые полезные поля там недальновидно объявлены как private), немного подогнав его под свои необходимости. На третий день (то есть сегодня), алгоритм заработал, однако скорость его работы оставляет желать лучшего (46 сек сжатие, 260 сек разжатие на файле размером 22 кб, если кто не догадался, лаба суть архиватор). Есть пара функций, которые были написаны "лишь бы работало, а потом разберемся", которые, как я думаю, сильно тормозят весь процесс. Вот их код.

// сравнивает свои биты начиная c SelfOffset с битам Second начиная с SecondOffset // возвращает количество совпавших бит function TBitsEx.MatchLen(const Second: TBitsEx; const SecondOffset, SelfOffset: Integer): Integer; var I: Integer; begin Assert(Second <> nil, "Nil pointer not allowed in TBitsEx.MatchLen"); I := SelfOffset; while (I < Size) and (I - SelfOffset + SecondOffset < Second.Size) do if Bits[I] = Second.Bits[I - SelfOffset + SecondOffset] then Inc(I) else Break; Result := I - SelfOffset; end; // копирует ASize бит из Source начиная с бита SourcePos // в себя, начиная с бита InsertPos procedure TBitsEx.CopyFromPos(const Source: TBitsEx; SourcePos, InsertPos, ASize: Integer); var I, NSize: Integer; begin Assert(Source <> nil, "Nil pointer not allowed in TBitsEx.CopyFromPos"); NSize := ASize; if NSize = -1 then NSize := Source.Size; if SourcePos + NSize > Source.Size then NSize := SourcePos + Source.Size; if InsertPos + NSize > Self.Size then Self.Size := InsertPos + NSize; for I := 0 to NSize - 1 do Bits[InsertPos + I] := Source[SourcePos + I]; end;

Знаю, что оптимизация по моему коду плачет, а великие программисты прошлого переворачиваются в гробах. Так что буду очень благодарен, если кто-нибудь подскажет направление, в котором копать, чтобы оптимизировать эти функции.

← →
Джо © (2007-09-25 02:33) [1]

> [0] Servelat © (25.09.07 02:26)
> если кто-нибудь подскажет направление, в котором копать,
> чтобы оптимизировать эти функции.

Заменить TBits на работу с битами посредством or, and, xor, shr, shl. Этого должно хватить, я думаю :)

← →
Германн © (2007-09-25 02:34) [2]

> (пронаследоваться не получилось, так как некоторые полезные
> поля там недальновидно объявлены как private)

Эээ. А кто запретил "повышать видимость полей класса?"

← →
Джо © (2007-09-25 02:36) [3]

> [1] Джо © (25.09.07 02:33)
> > [0] Servelat © (25.09.07 02:26)
> > если кто-нибудь подскажет направление, в котором копать,
>
> > чтобы оптимизировать эти функции.
>
> Заменить TBits на работу с битами посредством or, and, xor,
> shr, shl. Этого должно хватить, я думаю :)

+ http://podgoretsky.com/ftp/Docs/Delphi/Podgoretsky/bits.html

← →
Джо © (2007-09-25 02:39) [4]

> [2] Германн © (25.09.07 02:34)
> Эээ. А кто запретил "повышать видимость полей класса?"

Дядя Борланд :)

Впрочем, ума не приложу, что там такого в тех полях, что к ним понадобился прямой доступ? Всего два поля:

private FSize: Integer; FBits: Pointer;

← →
Servelat © (2007-09-25 02:46) [5]

>[2]
Я всегда наивно полагал, что поля, объявленные как private доступны только этому классу (ну и всем остальным в пределах модуля, если private не strict), а его потомки могут получить доступ лишь к protected секции.

>[1] [3]
Указанные операторы мне известны, но, я затрудняюсь применить их к данному случаю. Допустим, у меня есть последовательность бит, мне необходимо найти наибольший общий кусок подпоследовательностей, начинающихся с третьего и с тридцатьтретьего бита исходной последовательности. Как подойти к решению этой задачи, при возможной длине последовательности больше 64 бит?

← →
Германн © (2007-09-25 02:48) [6]

> Джо © (25.09.07 02:39) [4]
>
> > [2] Германн © (25.09.07 02:34)
> > Эээ. А кто запретил "повышать видимость полей класса?"
>
> Дядя Борланд :)
>
>

Неужели дядя Борланд такой злой?

← →
Servelat © (2007-09-25 02:48) [7]

> Впрочем, ума не приложу, что там такого в тех полях, что
> к ним понадобился прямой доступ

Например, чтобы сохранить цепочку бит, без необходимости вытряхивать их по одному через свойство Bits.

← →
Германн © (2007-09-25 02:55) [8]

> Указанные операторы мне известны, но, я затрудняюсь применить
> их к данному случаю. Допустим, у меня есть последовательность
> бит, мне необходимо найти наибольший общий кусок подпоследовательностей,
> начинающихся с третьего и с тридцатьтретьего бита исходной
> последовательности. Как подойти к решению этой задачи, при
> возможной длине последовательности больше 64 бит?
>

Значит тебе "плохо" известна сама тема. Тогда тебе к АП. На урок по байтам и битам!

← →
Servelat © (2007-09-25 03:11) [9]

> [8]

Вот я решаю задачу из [5].
Когда цепочка помещается в, скажем, integer, то решение достаточно очевидно.

function MatchLen(const Chain: Integer; const Index1, Index2: Integer): Integer; var T1, T2: Integer; begin T1 := Chain shl Index1; T2 := Chain shl Index2; T1 := T1 xor T2; // теперь первый ненулевой бит соответствует различию цепочек // как его лучше найти я еще не придумал... ну для начала, можно // попробовать вот так Result:=0; while (T1 and $80000000) = 0 do begin T1 := T1 shl 1; Result := Result + 1; end; end;

А если она не влазит и в Int64? Тут мой мозг отказывается мне помогать).

← →
Anatoly Podgoretsky © (2007-09-25 08:55) [10]

> Германн (25.09.2007 02:34:02) [2]

А кто разрешил повышать видимость для private?

← →
Сергей М. © (2007-09-25 10:22) [11]

> А если она не влазит и в Int64

Что мешает цепочке "жить" в массиве, например, типа Byte ?

← →
Anatoly Podgoretsky © (2007-09-25 10:23) [12]

> Сергей М. (25.09.2007 10:22:11) [11]

Ну там только восемь бит, а массивы мы еще не проходили.

← →
umbra © (2007-09-25 10:24) [13]

> кусок подпоследовательностей, начинающихся с третьего и
> с тридцатьтретьего бита исходной последовательности.

если я правильно понял, то вас должны интересовать только биты с 4-го по 33-й.

> Когда цепочка помещается в, скажем, integer

Что она, цепочка, забыла в Integer ?

Чем не устроил вариант

function GetMatchCount(const Chain1, Chain2: TBits): Integer;

?

> Servelat © (25.09.07 02:26)

В целом написано нормально, без перехода на низкий уровень сильно ускорить эти функции вряд ли получится. Хотя есть несколько моментов (см. ниже). Каждый из них сам по себе влияет не так уж и сильно, но если этии функции вызываются часто, то итог может быть заметным.

MatchLen
1. Assert - убрать. Пусть вылетает иходное исключение, не стоит тратить время на проверку (тем более, что вероятность передачи nil практически нулевая).
2. Заголовок цикла заменить на while i < MinSize, где MinSize - заранее (перед циклом) вычисленный наименьший из Self и Second размер.
3. Вычисление инварианта SelfOffset + SecondOffset вынести за цикл.
4. Стоит подумать о том, как бы доработать алгоритм, чтобы в этой функции можно было использовать CompareMem (вот это было бы существенно).

CopyFromPos
1. Assert - аналогично.
2. Цикл заменить на CopyMem.

> Servelat © (25.09.07 02:26)

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

Никто не мешает выдрать код TBits в свой модуль и правит его
от меня:
procedure TBitsEx.GetBits(const buf:pointer;const SizeOfBuf,Offset,Count:integer); var ByteOffset,ByteSh,ByteCount:integer; w:word; i:integer; begin ByteCount:=Count div 8; if (Count mod 8)<>0 then Inc(ByteCount); if ByteCount<SizeOfBuf then raise Exception.Create("Buf small"); ByteOffset:=Offset div 8; ByteSh:=Offset mod 8; ZeroMemory(buf,SizeOfBuf); for i:=0 to ByteCount-1 do begin w:=PWord(pointer(integer(FBits)+ByteOffset+i))^; w:=w shr ByteSh; PByteArray(buf)[i]:=w; end; end; function TBitsEx.MatchLen(const Second: TBitsEx; const SecondOffset,SelfOffset: Integer): Integer; var MatchSize,MatchBytes:integer; SelfBits,SecondBits:pointer; i:integer; x:byte; begin Assert(Second <> nil, "Nil pointer not allowed in TBitsEx.MatchLen"); result:=0; MatchSize:=Min((Self.Size-SelfOffset),(Second.Size-SecondOffset)); if MatchSize=0 then exit; MatchBytes:=MatchSize div 8; if (MatchSize mod 8)<>0 then Inc(MatchBytes); GetMem(SelfBits,MatchBytes); GetMem(SecondBits,MatchBytes); try result:=MatchSize; GetBits(SelfBits,MatchBytes,SelfOffset,MatchSize); Second.GetBits(SecondBits,MatchBytes,SecondOffset,MatchSize); for i:=0 to MatchBytes-1 do if PByteArray(SelfBits)[i]<>PByteArray(SecondBits)[i] then begin result:=i*8; x:=PByteArray(SelfBits)[i] and PByteArray(SecondBits)[i]; repeat if (x and 128)= 0 then break; x:=x shl 1; inc(result); until x>0; break; end; result:=min(MatchSize,result); finally FreeMem(SelfBits,MatchBytes); FreeMem(SecondBits,MatchBytes); end; end;

> Никто не мешает выдрать код TBits в свой модуль и правит
> его

Так и делал :). Спасибо за пример кода, однако меня берут сомнения, что выделения памяти в процедуре, вызывающейся кучу раз приведет к ускорению работы :)

> GetMem(SelfBits,MatchBytes);
> GetMem(SecondBits,MatchBytes);

Впрочем я посмотрю код подробнее, спасибо что откликнулись.

> [16]
Анализ с использованием QueryPerformanceCounter показал, что действительно затык был в соседней функции, которую я почему-то забыл расценить как потенциально медленную. Для интересующихся приведу как было и как стало.

Было:
procedure TBitsEx.ShiftLeft(const Count: Integer); var I: Integer; begin for I := Count to Size - 1 do Bits[I - Count] := Bits[I]; for I := Max(Size - Count, 0) to Size - 1 do Bits[I] := False; end;

Стало:
procedure TBitsEx.ShiftLeft(const Count: Integer); var I, Cnt, Full, Add, Add2: Integer; begin Cnt := Count; Full := Cnt div BitsPerInt; if Full > 0 then begin Move(PIntegerArray(FBits)^[Full], FBits^, (((Size - Full*BitsPerInt) + BitsPerInt - 1) div BitsPerInt) * SizeOf(Integer)); FillChar(PByteArray(FBits)^[(((Size + BitsPerInt - 1) div BitsPerInt) - Full) * SizeOf(Integer)], 0, Full * SizeOf(Integer)); Cnt := Cnt mod BitsPerInt; end; Add := 0; if Cnt > 0 then for I := ((Size + BitsPerInt - 1) div BitsPerInt) - 1 downto 0 do begin Add2 := PIntegerArray(FBits)^[I] shl (BitsPerInt - Cnt); PIntegerArray(FBits)^[I] := (PIntegerArray(FBits)^[I] shr Cnt) or Add; Add := Add2; end; end;

Работа всей программы ускорилась на порядок - вместо десятков секунд - две-три. Если кто-то видит недочеты или имеет соображения по еще большей оптимизации - буду рад услышать.

Советы из [15] приняты на вооружение и воплощены на практике (правда пока без CompareMem и CopyMem).

Цепочки битов Найти похожие ветки