ASTRING

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-таблицы. Хотя, имхо, практически это маловероятно.