Хеш-функция.

← →
Владислав © (2006-01-24 17:07) [40]

> Reindeer Moss Eater © (24.01.06 16:51) [38]
> >Коллекция на клиенте. Ее на клиенте и нужно обновить.
>
> Это я непонятно объясняю.
> Забыть про обработку коллекции на клиенте.

Еще раз. Коллекция на клиенте НЕ обрабатывается. Обрабатываться может какой-то элемент. Точнее, он может изменяться, удаляться, создаваться пользователем. Я не могу просто уничтожить элемент коллекции на клиенте потому, что он может быть открыт для редактирования/просмотра пользователем.

> Обработать её на сервере, а клиенту отдать готовый результат.

Первый раз именно так и происходит. А в последующем нужно обновление.

P.S. Подскажите алгоритм хеширования. :)

← →
MBo © (2006-01-24 17:11) [41]

>только что-то со старшими битами совсем все плохо.

достаточно равномерное распределение при Shift=4..18

procedure MeanStdDev(const Data: array of Integer; var Mean, StdDev: Extended); var S: Extended; N, I: Integer; begin N := High(Data) - Low(Data) + 1; Mean := 0; for I := Low(Data) to High(Data) do Mean := Mean + Data[i]; Mean := Mean / N; S := 0; for I := Low(Data) to High(Data) do S := S + Sqr(Mean - Data[I]); StdDev := Sqrt(S / (N - 1)); end; procedure TForm1.Button1Click(Sender: TObject); var s: string; i, k: Integer; a: array[0..1023] of Integer; Shift: Byte; Mn, StdD: Extended; begin for Shift := 0 to 22 do begin FillChar(a, SizeOf(a), 0); for k := 1 to 100000 do begin s := ""; for i := 1 to 38 do s := s + Chr(Ord("0") + Random(10)); i := ElfHash(s); Inc(a[(i shr Shift) and 1023]); end; // for i := 0 to 1023 do Memo1.Lines.Add(IntToStr(a[i])); MeanStdDev(a, Mn, StdD); Memo1.Lines.Add(Format("%d %6.1f %6.1f", [Shift, Mn, StdD])); end; end;

Еще можно попробовать CRC16

← →
Владислав © (2006-01-24 17:30) [42]

> MBo © (24.01.06 17:11) [41]

Понял я в чем дело. С числами с рандомным набором цифр действительно равномерно.
Если же числа идут по порядку, все плохо. :)

← →
Leonid Troyanovsky © (2006-01-24 17:56) [43]

> Владислав © (24.01.06 16:36) [36]

> А какой выигрыш в преобразовании на сервере? Кроме того
> NUMBER компактнее. При большом объеме данных и передачи
> по сети только проиграю.

Не, я имел ввиду такое преобразование, которое сохранит размер.
Т.е., 128 бит - это 4 клиентских Longint. Какой-нибудь пользовательский
тип данных и cast к нему. В общем, нужен запрос или хранимая
процедура, которая может быть использована для возвращения
клиенту вожделенных 128 бит (хотя бы в параметр).

> > А если уж нет, то руками преобразовать в 5 Longint,
> > экономия, все равно, существенная.

> Ну тогда остается открытым вопрос о хеш функции :)

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

--
Regards, LVT.

← →
Leonid Troyanovsky © (2006-01-24 18:09) [44]

> Владислав © (24.01.06 16:42) [37]

> > Неправ будет возжелавший оного :)

> Меня бы вполне устроил диапазон хеш значений от 0 до 1023
> плюс перебор до 1000 элементов для поиска.

Берем последний (с младшими разрядами) Longint и делаем
hash := a[4] and $3FF.

Только, эти списки поиска тоже надо поддерживать
(т.е., это тоже небесплатно).

--
Regards, LVT.

> Владислав © (24.01.06 16:36) [36]

> Да, но Insert(0), к примеру, в TList притянет за собой сдвиг
> большого массива. Сдвиг, к сожалению, и так есть, поскольку
> коллекции используются (TCollection), плюс будет еще один.

Дык, добавить все, а потом и сортировать.
При больших вставках так и делают.
Приурочить это дело к сеансам обмена с сервером.

Или индексированный поиск, плюс линейный по добавкам.
При объеме добавлений до 1000 записей оно будет уж не хуже
поиска по хеш-таблице.

--
Regards, LVT.

В итоге решил положиться на то, что ключевому полю будут присваиваться последовательные значения. Посему для значений хеша решил взять младшие разряды значения поля в таблице.

Спасибо огромное всем за помощь!

Хеш-функция. Найти похожие ветки