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

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

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

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

Страницы: < 1 2 3 >
Владислав © (2006-01-24 11:44:00)
Приветствую, Мастера.

Ситуация такая. Есть коллекции элементов, по которым производиться поиск элемента в коллекции по строке-идентификатору. Эти строки состоят из последовательностей символов с кодами #$30-#$39 (т.е. цифры).

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

P.S. До этого строка-идентификатор могла содержать любые символы латинского алфавита, цифры и некоторые другие символы. Простой xor всех символов в строке давал достаточно равномерное распределение хеш значений от 0 до 127. А как теперь поступить с цифрами?..

Владислав (2006-01-24 15:52:00) [21]

> MBo © (24.01.06 15:35) [22]

Спасибо. Это я нашел. Диапазон хеш-значений не подходит. Попробую адаптировать...

> Reindeer Moss Eater © (24.01.06 15:39) [24]
> А нельзя ли вообще исключить из этого процесса клиента?

Есть коллекция на клиенте, есть таблице в БД.
Нужно привести коллекцию в соответсвие, если данные в таблице изменились. При этом хотелось бы получить приемлемое быстродействие при наличии порядка 100000 записей.
Может быть и есть другие варианты, но они должны вписаться в уже существующую архитектуру приложения.

Leonid Troyanovsky (2006-01-24 15:52:00) [22]

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

> Вставка элемента в коллекцию также критична по времени.
> Вставка в сортированный список займет время.

Поиск позиции для вставки в отсортированный список - log(n).

Кроме того, чудес на свете не бывает.
Т.е., быстрее ищем - больше приседаний для подготовки.
Поиск с помощью хеш-функции имеет сложность ~ o(n).
Против log(n) бинарного поиска.

Так, что считай сам, сколько добавлений, сколько поисков.

И еще, полезность предварительного хеширования в массив Longint
для меня уже почти очевидна. Например, строка в 40 цифр без
особых усилий превращается в a[0..5] of Longint, т.е. по 8 цифр.

--
Regards, LVT.

Reindeer Moss Eater (2006-01-24 15:39:00) [23]
А нельзя ли вообще исключить из этого процесса клиента?

Владислав (2006-01-24 15:37:00) [24]

> Leonid Troyanovsky © (24.01.06 15:31) [21]

Вставка элемента в коллекцию также критична по времени. Вставка в сортированный список займет время.
По тому критерию, по которому коллекция отсортирована сейчас, так она отсортирована сервером.

MBo (2006-01-24 15:35:00) [25]
На паскале для понятности и вдвое быстрее - на асме (© Sha)
function ElfHashPas(const s: string): Integer; var i, h, g: Integer; begin h := 0; for i := 1 to Length(s) do begin h := h shl 4 + Byte(s[i]); g := h and $F0000000; if g <> 0 then h := h xor (g shr 24); h := h and (not g); end; Result := h; end; function ElfHash(const s: string): integer; asm mov edx, eax xor eax, eax test edx, edx jz @Ret sub eax, [edx-4] jz @Ret mov ecx, eax sub edx, eax xor eax, eax push ebx @Loop: movzx ebx, [edx+ecx] add ebx, eax lea eax, [ebx+ebx] shr ebx, 20 lea eax, [8*eax] and ebx, $0F00 xor eax, ebx add ecx, 1 jnz @Loop shr eax, 4 pop ebx @Ret: end;

Leonid Troyanovsky (2006-01-24 15:31:00) [26]

> Владислав © (24.01.06 15:05) [15]

> Не подходит. Элементы храняться в списке, но список этот
> уже отсортирован по другим критериям.

Никто не мешает для этого воспользоваться отдельным списком,
который будет ссылаться на индексы (указатели) первого списка.

Т.е., использовать этот список только для быстрого поиска.
Это всего лишь своебразный индекс.

--
Regards, LVT.

Владислав (2006-01-24 15:16:00) [27]

> Reindeer Moss Eater © (24.01.06 15:11) [19]
> А в списке на клиенте дабл нельзя иметь?

Можно. Но в [6] я привел код, который показывает, что такое решение не работает из-за разницы в количестве значащих цифр.

Reindeer Moss Eater (2006-01-24 15:11:00) [28]
А в списке на клиенте дабл нельзя иметь?

Владислав (2006-01-24 15:10:00) [29]

> Reindeer Moss Eater © (24.01.06 15:06) [16]

Осталось еще привести количество значащих цифр, чтобы до конца прояснить ситуацию...

Владислав (2006-01-24 15:09:00) [30]

> Reindeer Moss Eater © (24.01.06 14:49) [11]

Я уже понял Вашу мысль.
Вероятно я плохо объяснил свою проблему, что Вы не поняли, но мне нужен поиск именно на клиенте.

Reindeer Moss Eater (2006-01-24 15:06:00) [31]
Delphi:
Double 5.0 x 10^-324 .. 1.7 x 10^308

Oracle:
Number 1.0 x 10^-127 .. 9.9999999999999999999999999999999999999 x 10^121

Владислав (2006-01-24 15:05:00) [32]

> MBo © (24.01.06 14:02) [9]
> Elf-hash функция устроит?

Что-то я не могу найти алгоритм, чтобы суть понять и под задачу адаптировать. Может кто-нибудь ткнет пальцем?

> Leonid Troyanovsky © (24.01.06 14:35) [10]

Не подходит. Элементы храняться в списке, но список этот уже отсортирован по другим критериям.

Reindeer Moss Eater (2006-01-24 15:00:00) [33]
И что, разве диапазона Double не хватает для number(38)?

Leonid Troyanovsky (2006-01-24 14:53:00) [34]

> Reindeer Moss Eater © (24.01.06 14:51) [12]
> И уж тем более, зная, что у тебя только целочисленные значения
> в оракле, такого тупого сравнения как if Double1 = Double2
> можно легко избежать.

Если оно б помещалось в 8 байт, то Int64 было б лучше Double.
Но, как выяснилось, там не менее 16 байт.

--
Regards, LVT.

Reindeer Moss Eater (2006-01-24 14:51:00) [35]
И уж тем более, зная, что у тебя только целочисленные значения в оракле, такого тупого сравнения как if Double1 = Double2 можно легко избежать.

Reindeer Moss Eater (2006-01-24 14:49:00) [36]
Используй Double на клиенте.
И не сравнивай дабл на клиенте.
Зачем это надо?

Прочитав у записи number(38) в дабл на клиенте можно смело использовать его в параметрическом запросе. В оракле сравнение пройдет корректно и запись найдется.

Leonid Troyanovsky (2006-01-24 14:35:00) [37]

> Владислав © (24.01.06 11:44)

> Ситуация такая. Есть коллекции элементов, по которым производиться
> поиск элемента в коллекции по строке-идентификатору

Вообще-то, для быстрого поиска элемента можно воспользоваться
простой модификацией TList, содержащего индексы или идентификаторы
элементов. Этот список сортируется, а для поиска "ближайшего"
используется бинарный поиск Find:

http://groups.google.com/group/fido7.ru.delphi/msg/23b08e929a768df3

Однако, предварительное "хеширование" строкового представления
числа, например, в массив Longint должно ускорить процесс, бо
вместо строк длиной 38 символов сравниваться будут 16 байт(4х4).

--
Regards, LVT.

MBo (2006-01-24 14:02:00) [38]
Elf-hash функция устроит?

Leonid Troyanovsky (2006-01-24 14:02:00) [39]

> Владислав © (24.01.06 13:19) [5]

> Диапазон NUMBER, в принципе, 1 x 10^-130 - 9.99 x10^125.
> Диапазон значений, которые теоретически могут встретиться
> в поле, с которым я работаю, от -10^38 + 1 до 10^38 - 1.

Т.е., 128 бит?
Тогда, лучше если компоненты возвращали б не строку, a GUID.
Во всяком случае, IsEqualGUID уже есть.

--
Regards, LVT.

DiamondShark (2006-01-24 13:50:00) [40]

> Простой xor всех символов в строке давал достаточно равномерное
> распределение хеш значений от 0 до 127. А как теперь поступить
> с цифрами?..

Преобразовать в целое число и сделать тот же побайтный xor.
Получится достаточно равномерное распределение от 0 до 255

> Было бы замечательно, но эта строка - поле таблицы Oracle
> NUMBER(38). Не придумали такой тип целочисленный в Delphi,
> чтобы такие значения хранить.

Как так не придумали?
array[0..N] of byte

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

Наверх

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