Я тут Дж Рихтера и читал.
В главе по интернированию строк (стр223) рассказывается о том как это самое и интернирование ускоряет сравнение строк ( =) ). Хотя в основе интернирования лежит поиск в хэш таблице. По моему полная ерунда =)

Самое интересное то, что по фразе "интернирование строк" Гугль выдает только 1 (!!!!!!!) результат... и тот про Python. Ты не мог бы пояснить, что это такое, или ссылку дать... ?

Почему же ерунда? Для каждой уникальной строки есть только один объект, следовательно сравнение строк можно производить, как сравнение ссылок. Т.е. есть у нас строка "String A" и где бы мы не использовали ее в коде всегда обращаемся к глобальному объекту представляющим эту строку и есть строка "String B" с которой мы работаем аналогичным образом, следовательно для сравнения этих строк достаточно сравнить ссылки, но не сами строки.

Теперь про .NET:
Есть некоторая глобальная таблица строк (intern pool) в которой зарегестрированны все строки с которыми мы хотим работать как с интернироваными. Компилятор автоматически туда помещает все строковые константы опеределенные в коде. Добавить строку в эту таблицу или получить уже интернированую строку можно с помощью метода String.Intern. Беда в том, что в .NET сравнение строк происходит, как обычное стравнение строк т.е. для того что бы сравнить интернированные строки из кода надо их превести к object и потом сравнивать или вызвать Object.ReferenceEquals, что не очень удобно.

Похоже единственная область, где можно выгодно применять такой механизм работы со строками это парсеры и подобные вещи. Парсер выдает на выходе огромное кол-во строк многие их которых одинаковы (например public, private, т.д. для C#), хранить их в виде уникальных объектов невыгодно, плюс ко всему, если все строки на выходе парсера интернированы, то получаем значительный выйгрыш во время последующей работы с этими строками за счет ускорения сравнения.
Добавлено @ 14:56
Под сравнением понимается определение равенства\неравенства.

Простите уважаемый cully но ведь поиск в хэш-таблице это генерация хэш кода (тоже не очень
дешёвая операция) и как минимум одно (а как правило больше) сравнение.
Какой же тогда выигрыш?

Если можно приведите пример где интернирование может быть действительно выгодно.

Это сообщение отредактировал(а) iskan - 23.4.2005, 12:34

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

Цитата(iskan @ 23.4.2005, 09:32)

Если можно приведите пример где интернирование может быть действительно выгодно.

Повоторяю, в парсерах и подобных вещах. Например, нам требуется реализовать парсер C#, метод ParseNext() будет возвращать не строку, а некий глобальный идентификатор этой строки (int). В .NET в роли этого идентификатора выступает уникальный объект класса string, таким образом он совмещает в себе и идентификатор и значение строки. Заранее известно, что строка "public" имеет идентификатор 1, "private" = 2, т.д. Тогда имеем две выгоды:

1. Для определения того равна ли строка строке "public", мы не делаем сравнения строк, а делаем стравнение int. Повышает скорость работы.

2. Можно хранить результат работы парсера не в виде набора строк, а в виде набора int. Уменьшает использование памяти.

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

Парсер получает данные из вне(со стандартного ввода или из файла)...
Следовательно что-бы сравнивать полученную строку с другой интернированной
её тоже нужно интернировать.

Цитата(cully @ 23.4.2005, 16:01)

Сама таблица нужна только для того, что бы дважды не интернировать одинаковую строку

это понятно, но вот

Цитата(cully @ 23.4.2005, 16:01)

и не получить разный идентификатор

это уже более чем непонятно - что это за хэширование такое, которое на одну и ту же строку разные хэши даст???

Неет на одну и ту же строку то хэш функция даст один и тот же хэш
Просто она может дать один хэш для разных строк ( например некоторые хэш функции дают
одинаковый хэш для перевёртышей )

Цитата(iskan @ 25.4.2005, 06:22)

Парсер получает данные из вне(со стандартного ввода или из файла)... Следовательно что-бы сравнивать полученную строку с другой интернированной её тоже нужно интернировать.

О чем и разговор, да, нужно, но после интернации 1 000 000 сравнений уже интернированных строк пройдет намного быстрее, чем не интернированных. Ясно дело, если сравнение встречается не часто, то на интернировании мы только потеряем, но в парсерах\компиляторах это происходит часто.