Библиотека Generic классов - ошибки, описание, вопросы, особенности использования и предложения - страница 6

Новый комментарий
 
Vasiliy Sokolov:

Бывает так, что разные слова начинаются на одну и туже букву алфавита. Если в наш предыдущий словарь мы поместим слово "apple", а затет попытаемся поместить туда "application" то ничего не выйдет. Индекс 0 уже будет занят словом apple. В данном случае говорят о коллизии хеш-функции. Наша хеш-функция очень простая - она возвращает номер первого символа слова, поэтому коллизии в этой функции будут очень часты. Что бы хранить разные слова начинающиеся на одинаковую букву, сделаем дополнение: будем хранить элементы не в массиве, а в массиве массивов. Тогда по индексу 0 будет еще один массив содержащий два слова: "apple" и "application":

Теперь наш словарь хранит слова, даже начинающиеся на одну и туже букву. Но вот цена доступа к словам с одинаковой первой буквы возрастает. Потому что теперь требуется полный перебор всех слов, начинающихся на 'a', что бы понять, есть слово 'application' в словаре или нет. Если бы наша хеш функция выдавала бы разные числа даже если слова различались на один символ, тогда вероятность перебора слов с одинаковыми индексами стремилась бы к нулю, и доступ к произвольному элементу стремился бы к o(1). В настоящих словарарях именно так и присходят, функции которые там используются устойчивы к появлениям коллизций, поэтому мы с определенностью можем утверждать, что доступ к элементам в этих коллекциях происходит очень быстро и практически без перебора.

Попробую предоставить свое решение этого примера. Без указателей. Чуть позже.
 

Недавно прочитал книгу по теме. Называется "Грокаем алгоритмы". Все очень доходчиво изложено, с примерами.

 
Vasiliy Sokolov:

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

Большая просьба писать лаконично, без портянок в виде шапок и лишних сущностей.

Например, это

bool Contains(string word)
{
   uchar index = (uchar)StringGetCharacter(word, 0)-97;
   return words[index] != NULL;
}

можно было бы записать куда яснее

bool Contains(string word)
{
   return words[word[0]-'a'] != NULL;
}


Ну и все же код этот для MT4/5 может работать по-разному, т.к. в MT4 массив инициализируется NULL-значениями, а в MT5 - может и мусором.

 
fxsaber:

Большая просьба писать лаконично, без портянок в виде шапок и лишних сущностей.

...


Категорично ПРОТИВ! Код желательно писать развёрнуто. Посмотрите все кода MQ - везде есть "шапки". Это стандарт.


fxsaber:

...

Ну и все же код этот для MT4/5 может работать по-разному, т.к. в MT4 массив инициализируется NULL-значениями, а в MT5 - может и мусором.


Причём здесь старый терминал? Кто ленив и до сих пори сидит на старом - это только его личные проблемы. Сообщество не должно тормозиться из-за таких ленивцев.

 
Vladimir Karputov:

Посмотрите все кода MQ - везде есть "шапки". Это стандарт.

В топку стандарт, здесь суть важна, а не стайл, занимающий 50% кода.

 
fxsaber:

В топку стандарт, здесь суть важна, а не стайл, занимающий 50% кода.


Главная задача форума - ОБРАЗОВАНИЕ. Поэтому код должен быть развёрнут и понятен с максимальным приближением к стандарту.

 
Vasiliy Sokolov:

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

Т.е. нужно для каждой задачи нащупать золотую середину между размером словаря (RAM) и вычислительной сложностью хеш-функции (CPU).

 
Vladimir Karputov:

Главная задача форума - ОБРАЗОВАНИЕ. Поэтому код должен быть развёрнут и понятен

этого достаточно.

с максимальным приближением к стандарту.

Шапки можете и сами вставить. A100 сотни репортов выдал в СД без шапок - вот стандарт! Потому что важна суть, а не мишура.

 
Есть решение. Однако, чтобы временно сохранить интригу, я бы хотел выставить сюда экзешник. Далее, умеющие люди сравнят производительность моего решения и решения предоставленного автором выше. Интересно, что работает быстрее.
Файлы:
Dictionary.ex5  10 kb
 
Реter Konow:
Есть решение. Однако, чтобы временно сохранить интригу, я бы хотел выставить сюда экзешник. Далее, умеющие люди сравнят производительность моего решения и решения предоставленного автором выше. Интересно, что работает быстрее.
Нужно запустить экзешник. Появится поле ввода. Далее, можно вводить различные слова. Если есть совпадения, то через принт будет выводится уведомление что слово имеется в словаре. Если слова нет, то выведется уведомление, что слово добавлено в словарь.
12345678910111213...37
Новый комментарий