Форум: "Основная";
Текущий архив: 2002.02.04;
Скачать: [xml.tar.bz2];
Вниз
Нужна приличная и Найти похожие ветки
← →
corvalol (2002-01-18 11:08) [0]Давненько я сюда не писал... :)
Короче, по роду деятельности постоянно приходится строить деревья из БД. В БД обычно для этого используется ID самой записи и ID родителя. Все просто и удобно. Но до сих пор я реализовал все это дело достаточно криво, а сейчас хочу попробовать с использованием хэшей. Сделал то же самое на Перле - намного проще! Поэтому сейчас ищу подходящую хэш-функцию. MD5 не годится, т.к. достаточно дорого в плане прожорливости.
Кто что может порекомендовать?
← →
Digitman (2002-01-18 12:09) [1]а надо ? именно хэш ? до сих пор я успешно обходился обычной CRC32, и проблем не было. Главное здесь - включить в уник.индекс несколько CRC, вычисленных по тем полям, комбинация значений которых д.б. уникальна. Тогда и вероятность дублирования уник.индекса будет астрономически ничтожной.
Вот, посмотри, чем я пользуюсь, к примеру, в IB UDF, когда необходимо вычислить контр.сумму BLOB-поля :
const
//CRC32-полином для расчета таблицы
CRC32Poly = $EDB88320; //WinZip использует именно такое зн-е полинома, но можно и изменить на свое, чуть подумав
type
TCRC32 = Longword;
PCRC32 = ^TCRC32;
TCRC32Table = array[0..255] of TCRC32;
PCRC32Table = ^TCRC32Table;
var
CRC32Table: PCRC32Table;
procedure MakeCRC32Table(
CRC32Table: PCRC32Table; // указатель на CRC32-таблицу, которую требуется заполнить
const InitCRC: TCRC32 // исходный CRC32-полином для расчета таблицы
);
var
i,j: Integer;
r: TCRC32;
begin
for i:= Low(TCRC32Table) to High(TCRC32Table) do begin
r:= i;
for j:= 8 downto 1 do
if (r and 1) = 1 then
r:= (r shr 1) xor InitCRC
else
r:= r shr 1;
CRC32Table[i]:= r;
end;
end;
function GetCRC32(
const Buffer; // ссылка на буфер, CRC32 которого д.б.расчитана
BufSize: DWord; // размер буфера
InitCRC: TCRC32; // вх.значение CRC32, обычно - $FFFFFFFF (-1)
const Inv: Boolean // инвертировать ли результат (обычно - True)
): TCRC32;
var
BufPtr: PByte;
begin
BufPtr:= PByte(Buffer);
while BufSize > 0 do begin
InitCRC:= CRC32Table[LoByte(InitCRC) xor BufPtr^] xor (InitCRC shr 8);
Inc(BufPtr);
Dec(BufSize);
end;
Result:= InitCRC;
if Inv then
Result:= not Result;
end;
...
//расчет контр.суммы BLOB-поля
function GetBlobCheckSum(Blob: PBlob): PCRC32;
var
CRC32: TCRC32;
SegBuf: Pointer;
BytesRemains, BytesRead: Integer;
begin
Result:= nil;
if Assigned(Blob) then with Blob^ do
if Assigned(BlobHandle) and Assigned(GetSegment) then
try
GetMem(SegBuf, MaxSegmentLength);
BytesRead:= 0;
CRC32:= CRC32InitMask;
try
BytesRemains:= TotalSize;
while (BytesRemains > 0) and Boolean(GetSegment(BlobHandle, SegBuf, Min(BytesRemains, MaxSegmentLength), BytesRead)) do begin
CRC32:= GetCRC32(SegBuf^, BytesRead, CRC32, False);
Dec(BytesRemains, BytesRead);
BytesRead:= 0;
end;
finally
FreeMem(SegBuf);
end;
Result:= PCRC32(Blob);
Result^:= not CRC32;
except
//исключение гасится, в IB возвращается Null, сигн.об исключении в UDF
Result:= nil;
end
end;
initialization
New(CRC32Table); // выделить память под CRC32-таблицу
MakeCRC32Table(CRC32Table, CRC32Poly); // заполнить таблицу
finalization
Dispose(CRC32Table); // освободить память под таблицу
...
это - скрипт для объявления UDF в IB :
DECLARE EXTERNAL FUNCTION GETBLOBCHECKSUM
BLOB
RETURNS INTEGER
ENTRY_POINT "GetBlobCheckSum" MODULE_NAME "my_udf.dll";
это - фрагмент скрипта триггера, в котором требуется получить CRC нового/обновленного BLOB-поля :
...
new.MyBlob_CRC_Field = GetBlobCheckSum(new.MyBlobField);
/* можно и не делать след.проверку, если
MyBlob_CRC_Field объявлено как "not Null" */
if (new.MyBlob_CRC_Field is Null) then
exception E_SOME_PREDEFINED_EXCEPTION_ON_THIS_SITUATION;
...
← →
yaJohn (2002-01-18 13:12) [2]Mn...
A zachem hash?
Ne proshe li prosto ID iz globalnoy sohroniaemoy peremennoy s avtoinkrementom?
Krome togo vozmojen sluchay, kogda dannie v raznih uzlah dereva sovpadaut. Hash vernet ravnie ID...
← →
corvalol (2002-01-18 14:28) [3]Нет, ты не понял. Имеется в виду, что по ID узла в базе данных я должен мгновенно получить его HTREEITEM, чтобы знать, к чему добавлять потомка в дереве. Вот для этого и нужен хэш - ID может начинаться с произвольного числа, и в нем могут быть пропущены какие-то значения. А ты говоришь, автоинкремент.
← →
yaJohn (2002-01-18 14:46) [4]Teper poniatno...
K sojaleniu edinstvenniy (izvestniy mne) hash v Delphi - TStrings.Values No bous on vriadli ustroit.
Pridetsia delat rukami. Esli ID - integer i zavedomo neveliki, mojno risknut sdelat cherez TList. T.e.
Pri sozdanii Node:
while ID>=List.Count do List.Add(nil);
List[ID]:=Node;
Poisk Node po ID trivialen. Ne ochen iziashno, no prosto i ochen bistro (kak pri napisanii, tak i v runtime :)
No opiat taki, dlia nebolshih ID. I jelatelno dat List.Capacity >= MaxID
← →
corvalol (2002-01-18 15:13) [5]Я делал по-другому. Динамический массив HTREEITEM-ов. По индексу, равному ID, загоняю в массив HTREEITEM нужного узла. Далее тривиально - если нужно узнать, где родитель в дереве, просто идем в нужный массив по нужному индексу. Получается за один шаг и ОЧЕНЬ быстро, но расходуется память. Представим, что у нас записей 100 тысяч, а ID распределены не по порядку, а с БОЛЬШИМИ пробелами (в диапазоне от 1 миллиона до 10-ти миллионов). Тогда получается, что придется делать массив НЕ из 100 тысяч элементов, а из 10 миллионов (ну, или 9-ти, если постараться). Вывод? Нужен нормальный хэш, как в Перле.
← →
yaJohn (2002-01-18 16:28) [6]Est" takaya bukva.
DelphiFundamentional
Tam est gruppa ob"ektov TStringDictionary, TSinglDictionary i t.d. Doljno bit na torry.net , esli nado - mogu namilit", okolo 700K
← →
vuk (2002-01-18 17:35) [7]Самый простой хэш - xor с циклическим сдвигом. Работает быстро и в большинстве случаев подходит.
function CalcHash( Data : pointer; DataSize : integer ) : integer;
register;
asm
push ebx
push esi
push edi
mov esi, Data
xor ebx, ebx
or esi, esi
jz @@Exit
mov edx, DataSize
or edx,edx
jz @@Exit
xor ecx,ecx
@@Cycle:
xor eax,eax
mov al,[esi]
inc esi
rol eax,cl
xor ebx,eax
inc ecx
dec edx
jnz @@Cycle
@@Exit:
mov eax,ebx
pop edi
pop esi
pop ebx
end;
function StrCalcHash( const S : string ) : integer;
begin
Result := CalcHash( pointer( S ), length( S ));
end;
Страницы: 1 вся ветка
Форум: "Основная";
Текущий архив: 2002.02.04;
Скачать: [xml.tar.bz2];
Память: 0.47 MB
Время: 0.005 c
