YF> Здравствуйте, Олег.
YF> Вы писали 4 декабря 2002 г., 3:25:23:ОАР>> Здравствуйте!
ОАР>>> А после этого опять пробежать по очереди и сравнить оригинальные
ОАР>>> строки и значения из ASTRING.
ОАР>>> Если получим где-то несовпадения, то значит были сгенерены
ОАР>>> несколько одинаковых Hash-ключей.YF> Любой порядочный алгоритм хеширования должен иметь средства
YF> разрешения коллизий (Д.Кнут, Искусство программирования для
Учитывая, что в моих тестах повторений не было, то SV так-же читают его книги:)
YF> ЭВМ, т.1). Я не думаю, что в SV об этом не знают. Кстати, как это
YF> соотносится с их заявлениями об использовании ATOM-фукнций WinAPI?
Явно никак. По крайней мере, в блоке работы с ASTRING-ами. Хотя, конечно, реализация ASTRING от SV сильно напоминает виндусовые Атомы.
У меня вообще давно уже сложилось впечатление, что SV никак еще не отойдет от практики разработки языка времен Виндов3.11 Когда в WinAPI многого не хватало и TopSpeed недостающее делал сам в ядре Клары. Может просто они таким образом пытаются застраховаться от возможных нестыковок и несовместимостей между API различных версий Винды?
>>> Так что имей в виду, что чисто теоретически при достаточно
>>> большом кол-ве ASTRING-переменных может произойти совпадение
>>> Hash-ключей для некоторых из них. В таком случае эти переменные
>>> будут указывать на одну и ту-же ячейку Hash-таблицы.
>>> Хотя, имхо, практически это маловероятно.NT>> Вероятность «на глазок» в этом вопросе очень обманчивая вещь! Есть известная
NT>> задачка: «Сколько нужно собрать гостей, чтобы вероятность совпадения дней
NT>> рождения хотя бы у двух из них была больше 1/2 ?» Правильный ответ — 22 чел.ОАР> Ну так вот, прекрасный и повод и вариант проверки стойкости Hash-ключей.
ОАР> Написать простенькую прогу, в которой сгенерить несколько сотен
ОАР> (или тысяч) строк, попутно «запихивая» их в ASTRING и сохраняя
ОАР> оригинальные строки и полученные ASTRING в очередь.
ОАР> А после этого опять пробежать по очереди и сравнить оригинальные
ОАР> строки и значения из ASTRING.
ОАР> Если получим где-то несовпадения, то значит были сгенерены
ОАР> несколько одинаковых Hash-ключей.
Стало интересно и проверил — сгенерил 100.000 записей, получил ~13.000 дубликатов и ни одного совпадения Hash-ключей. Так что, или теория вероятности здесь не работает или этот алгоритм вычисления Hash-ключа действительно надежный.
Проверял еще и на 1.000.000 но не хватило терпения дождатся завершения теста — когда задача требует очень много памяти, то менеджер памяти Клары сильно тормозит.
Значения строк генерил просто:
Clear(TstQue)
L# = Round(2,Size(TST:Original)) ! для CSTRING
Loop N# = 1 to (L#-1)
TST:Original[N#] = Chr(Round(33,250))
.
TST:Original[L#] = ''
Проверял на маленьких строках (CSTRING(10)) и на средних (CSTRING(40)).
Кол-во дубликатов, естественно, менялось. Но совпадений по ключам не было ни одного!
>> Так что имей в виду, что чисто теоретически при достаточно
>> большом кол-ве ASTRING-переменных может произойти совпадение
>> Hash-ключей для некоторых из них. В таком случае эти переменные
>> будут указывать на одну и ту-же ячейку Hash-таблицы.
>> Хотя, имхо, практически это маловероятно.NT> Вероятность «на глазок» в этом вопросе очень обманчивая вещь! Есть известная
NT> задачка: «Сколько нужно собрать гостей, чтобы вероятность совпадения дней
NT> рождения хотя бы у двух из них была больше 1/2 ?» Правильный ответ — 22 чел.
Ну так вот, прекрасный и повод и вариант проверки стойкости
Hash-ключей.
Написать простенькую прогу, в которой сгенерить несколько сотен (или тысяч) строк, попутно «запихивая» их в ASTRING и сохраняя оригинальные строки и полученные ASTRING в очередь. А после этого опять пробежать по очереди и сравнить оригинальные строки и значения из ASTRING. Если получим где-то несовпадения, то значит были сгенерены несколько одинаковых Hash-ключей.
ЧС> Кто-нибудь знает, есть ли ограничения на число переменных типа ASTRING?
ЧС> Есть мысль, вместо строковых констант использовать переменные этого типа.
ЧС> Почему-то у меня компилятор включает в проект константы столько раз, сколько
ЧС> они применяются.
ЧС> Вот я и подумал, что наверное лучше будет вместо, например, константы
ЧС> ‘Предупреждение!’, используемой 100 раз, использовать
ЧС> ct:Warning astring(‘Предупреждение!’)
ЧС> Еще плюс, эта «костанта» удобна для замены, в том числе и програмно.
ЧС> Ну, например, при локализации.
ЧС> Но сейчас тотальный переход уперся в возможное число astring-ов…
ЧС> Вот и спрашивается — где край?
Все ASTRING-переменные, независимо от того, где они обьявлены, Кларион хранит в своей внутренней Hash-таблице. Очистка этой таблицы производится при завершении программы. Размер этой Hash-таблицы ограничен лишь размером доступной физической памяти.
Кстати, имей в виду, что Кларион автоматически у ASTRING-переменных «обрезает» хвостовые пробелы.
Да, и еще! Кажется в нашей рассылке уже как-то обсуждался вопрос о надежности Hash-ключевания. Т.е. о НЕПОВТОРЕНИИ Hash-кода для разных исходных значений.
Так что имей в виду, что чисто теоретически при достаточно большом кол-ве ASTRING-переменных может произойти совпадение Hash-ключей для некоторых из них. В таком случае эти переменные будут указывать на одну и ту-же ячейку Hash-таблицы. Хотя, имхо, практически это маловероятно.