Главная страница
    Top.Mail.Ru    Яндекс.Метрика
Форум: "Основная";
Текущий архив: 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.48 MB
Время: 0.006 c
1-8917
Eraser
2002-01-17 09:13
2002.02.04
Расположение фрейма на форме


1-8808
DDDeN
2002-01-16 07:29
2002.02.04
Restorator


3-8789
Akimpinpavel
2002-01-08 12:22
2002.02.04
Как связать Delphi с базой данныx Access


7-9019
gunner
2001-10-25 17:43
2002.02.04
Неизвестный модуль !


1-8911
Марина
2002-01-17 13:48
2002.02.04
Цветшрифта в ячейке StringGrid





Afrikaans Albanian Arabic Armenian Azerbaijani Basque Belarusian Bulgarian Catalan Chinese (Simplified) Chinese (Traditional) Croatian Czech Danish Dutch English Estonian Filipino Finnish French
Galician Georgian German Greek Haitian Creole Hebrew Hindi Hungarian Icelandic Indonesian Irish Italian Japanese Korean Latvian Lithuanian Macedonian Malay Maltese Norwegian
Persian Polish Portuguese Romanian Russian Serbian Slovak Slovenian Spanish Swahili Swedish Thai Turkish Ukrainian Urdu Vietnamese Welsh Yiddish Bengali Bosnian
Cebuano Esperanto Gujarati Hausa Hmong Igbo Javanese Kannada Khmer Lao Latin Maori Marathi Mongolian Nepali Punjabi Somali Tamil Telugu Yoruba
Zulu
Английский Французский Немецкий Итальянский Португальский Русский Испанский