| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Общие вопросы по .NET и C# > Интернация строк в .NET |
| Автор: iskan 22.4.2005, 13:34 |
| Я тут Дж Рихтера и читал. В главе по интернированию строк (стр223) рассказывается о том как это самое и интернирование ускоряет сравнение строк ( =) ). Хотя в основе интернирования лежит поиск в хэш таблице. По моему полная ерунда =) |
| Автор: arilou 22.4.2005, 13:47 |
| Самое интересное то, что по фразе "интернирование строк" Гугль выдает только 1 (!!!!!!!) результат... и тот про Python. Ты не мог бы пояснить, что это такое, или ссылку дать... ? |
| Автор: stab 22.4.2005, 14:47 |
| Почему же ерунда? Для каждой уникальной строки есть только один объект, следовательно сравнение строк можно производить, как сравнение ссылок. Т.е. есть у нас строка "String A" и где бы мы не использовали ее в коде всегда обращаемся к глобальному объекту представляющим эту строку и есть строка "String B" с которой мы работаем аналогичным образом, следовательно для сравнения этих строк достаточно сравнить ссылки, но не сами строки. Теперь про .NET: Есть некоторая глобальная таблица строк (intern pool) в которой зарегестрированны все строки с которыми мы хотим работать как с интернироваными. Компилятор автоматически туда помещает все строковые константы опеределенные в коде. Добавить строку в эту таблицу или получить уже интернированую строку можно с помощью метода String.Intern. Беда в том, что в .NET сравнение строк происходит, как обычное стравнение строк  т.е. для того что бы сравнить интернированные строки из кода надо их превести к object и потом сравнивать или вызвать Object.ReferenceEquals, что не очень удобно.Похоже единственная область, где можно выгодно применять такой механизм работы со строками это парсеры и подобные вещи. Парсер выдает на выходе огромное кол-во строк многие их которых одинаковы (например public, private, т.д. для C#), хранить их в виде уникальных объектов невыгодно, плюс ко всему, если все строки на выходе парсера интернированы, то получаем значительный выйгрыш во время последующей работы с этими строками за счет ускорения сравнения. Добавлено @ 14:56 Под сравнением понимается определение равенства\неравенства. |
| Автор: iskan 23.4.2005, 12:32 |
| Простите уважаемый cully но ведь поиск в хэш-таблице это генерация хэш кода (тоже не очень дешёвая операция) и как минимум одно (а как правило больше) сравнение. Какой же тогда выигрыш? Если можно приведите пример где интернирование может быть действительно выгодно. |
| Автор: stab 23.4.2005, 15:01 | ||
Добавление в хеш-таблицу происходит только один раз в момент интернации строки, далее происходят операции только со ссылкой (возможно с неким уникальным идентификатором строки). Сама таблица нужна только для того, что бы дважды не интернировать одинаковую строку и не получить разный идентификатор, т.е. для того, что бы гарантировать строгое соответствие между строкой и её идентификатором.
Повоторяю, в парсерах и подобных вещах. Например, нам требуется реализовать парсер C#, метод ParseNext() будет возвращать не строку, а некий глобальный идентификатор этой строки (int). В .NET в роли этого идентификатора выступает уникальный объект класса string, таким образом он совмещает в себе и идентификатор и значение строки. Заранее известно, что строка "public" имеет идентификатор 1, "private" = 2, т.д. Тогда имеем две выгоды: 1. Для определения того равна ли строка строке "public", мы не делаем сравнения строк, а делаем стравнение int. Повышает скорость работы. 2. Можно хранить результат работы парсера не в виде набора строк, а в виде набора int. Уменьшает использование памяти. По сути, мы однозначно отображаем некоторое множество строк в некоторое множество целых чисел. Потом работаем уже со множеством целых чисел и при надобности обращаемся к словарю, что бы отобразить элемент из одного множества в другое. Хеш-таблица помогает автоматизировать процес составления этого словаря и обеспечивает поиск в этом словаре. Если требуется большое кол-во операций по отображению элементов, т.е. большое кол-во обращений к словарю, то интернацию использовать не выгодно. |
| Автор: iskan 25.4.2005, 09:22 |
| Парсер получает данные из вне(со стандартного ввода или из файла)... Следовательно что-бы сравнивать полученную строку с другой интернированной её тоже нужно интернировать. |
| Автор: Akina 25.4.2005, 09:56 | ||||
это понятно, но вот
это уже более чем непонятно - что это за хэширование такое, которое на одну и ту же строку разные хэши даст??? |
| Автор: iskan 25.4.2005, 10:04 |
| Неет на одну и ту же строку то хэш функция даст один и тот же хэш Просто она может дать один хэш для разных строк ( например некоторые хэш функции дают одинаковый хэш для перевёртышей ) |
| Автор: stab 26.4.2005, 12:44 | ||
О чем и разговор, да, нужно, но после интернации 1 000 000 сравнений уже интернированных строк пройдет намного быстрее, чем не интернированных. Ясно дело, если сравнение встречается не часто, то на интернировании мы только потеряем, но в парсерах\компиляторах это происходит часто. |