Интернирование строк действительно полезно?
Некоторое время назад у меня был разговор о строках и различных языках, и возникла тема интернирования строк. Очевидно, Java и.NET Framework делают это автоматически со всеми строками, а также с несколькими языками сценариев. Теоретически, это экономит память, потому что вы не получаете несколько копий одной и той же строки, и это экономит время, потому что сравнения на равенство строк - это простое сравнение указателей, а не O(N), проходящий через каждый символ строки.
Но чем больше я об этом думаю, тем больше скептически отношусь к преимуществам концепции. Мне кажется, что преимущества в основном теоретические:
- Прежде всего, чтобы использовать автоматическое интернирование строк, все строки должны быть неизменяемыми, что делает многие задачи по обработке строк сложнее, чем они должны быть. (И да, я слышал все аргументы в пользу неизменности вообще. Это не главное.)
- Каждый раз, когда создается новая строка, она должна быть проверена по внутренней таблице строк, что является по крайней мере операцией O(N). (РЕДАКТИРОВАТЬ: где N - это размер строки, а не размер таблицы, поскольку это сбивало с толку людей.) Таким образом, если соотношение сравнений равенства строк и создания новой строки не слишком велико, маловероятно, что сэкономленное сетевое время будет положительная ценность.
- Если таблица равенства строк использует строгие ссылки, строки никогда не будут собирать мусор, когда они больше не нужны, тратя таким образом память. С другой стороны, если таблица использует слабые ссылки, тогда классу строк необходим какой-то финализатор для удаления строки из таблицы, что замедляет процесс GC. (Что может быть довольно значительным, в зависимости от того, как реализована строковая внутренняя таблица. В худшем случае удаление элемента из хеш-таблицы может потребовать O(N) перестроения всей таблицы при определенных обстоятельствах.)
Это всего лишь результат того, что я задумался о деталях реализации. Я что-то пропустил? Обеспечивает ли интернирование строк какие-либо существенные преимущества в общем случае?
РЕДАКТИРОВАТЬ 2: Хорошо, очевидно, я действовал из ошибочной предпосылки. Человек, с которым я разговаривал, никогда не указывал, что интернирование строк было необязательным для вновь создаваемых строк, и на самом деле создавало сильное впечатление, что все наоборот. Спасибо Джону за разъяснение. Еще один принятый ответ для него.
7 ответов
Нет, Java и.NET не делают это "автоматически со всеми строками". Они (ну, Java и C#) делают это с помощью константных строковых выражений, выраженных в байт-коде /IL, и по запросу через String.intern а также String.Intern (.NET) методы. Точная ситуация в.NET интересна, но в основном компилятор C# гарантирует, что каждая ссылка на одинаковую строковую константу в сборке в конечном итоге ссылается на один и тот же строковый объект. Это может быть сделано эффективно во время инициализации типа и может сэкономить кучу памяти.
Это не происходит каждый раз, когда создается новая строка.
(Что касается неизменности строк, я очень рад, что строки неизменяемы. Я не хочу снимать копию каждый раз, когда получаю параметр и т. Д., Большое спасибо. Я не видел, чтобы это делало строку обработка задач сложнее, либо...)
И, как уже отмечали другие, поиск строки в хеш-таблице обычно не является операцией O(n), если только вы не невероятно не везете с хеш-коллизиями...
Лично я не использую интернирование строк в пользовательском коде; если я хочу какой-то кеш строк, я создам HashSet<string> или что-то подобное. Это может быть полезно в различных ситуациях, когда вы ожидаете встретить одни и те же строки несколько раз (например, имена элементов XML), но с простой коллекцией вы не загрязняете системный кеш.
Прежде всего, чтобы использовать автоматическое интернирование строк, все строки должны быть неизменяемыми, что делает многие задачи по обработке строк сложнее, чем они должны быть. (И да, я слышал все аргументы в пользу неизменности вообще. Это не главное.)
Это верно, и строка неизменна в Java. Я не уверен, что это плохо. Не вдаваясь в "неизменяемый" и "изменяемый", мне нравится думать, что это отличный дизайн из-за кеширования и гораздо большей простоты, к которой я не буду подходить.
Каждый раз, когда создается новая строка, она должна быть проверена по внутренней таблице строк, что является по крайней мере операцией O(N). Таким образом, если отношение сравнений равенства строк к созданию новой строки не является достаточно высоким, маловероятно, что сэкономленное время будет положительным значением.
Не совсем O(n). Вы можете создавать хеш-карты и / или другие структуры данных, которые приведут это к почти постоянному поиску.
Если таблица равенства строк использует строгие ссылки, строки никогда не будут собирать мусор, когда они больше не нужны, тратя таким образом память. С другой стороны, если таблица использует слабые ссылки, тогда классу строк необходим какой-то финализатор для удаления строки из таблицы, что замедляет процесс GC. (Что может быть довольно значительным, в зависимости от того, как реализована строковая внутренняя таблица. В худшем случае удаление элемента из хеш-таблицы может потребовать O(N) перестроения всей таблицы при определенных обстоятельствах.)
Вы правы в этом, и я бы с вами согласился. Кроме того, я чувствую, что обработка GC и незначительна. Преимущества в долгосрочной перспективе гораздо полезнее, чем сборщик мусора, выполняющий дополнительную проверку. Я не уверен, что вы имеете в виду O (n) для удаления из хеш-таблицы. Большинство операций над хеш-таблицами O(1)
Итак, в заключение, я думаю, что вы предполагаете, что большинство операций являются линейными. Но поиск строк ближе к постоянному времени. Таким образом, этот подход будет иметь незначительную потерю производительности, но огромный выигрыш в памяти. Что, я бы сказал, того стоит.
Вот хорошая цитата о том, что на самом деле происходит и как это сохраняет память.
Чтобы сохранить память (и ускорить тестирование на равенство), Java поддерживает "интернирование" строк. Когда метод intern() вызывается для строки, поиск выполняется в таблице интернированных строк. Если объект String с таким же содержимым уже находится в таблице, возвращается ссылка на строку в таблице. В противном случае строка добавляется в таблицу и возвращается ссылка на нее.
A.equals(b) очень быстр для случайных строк. Это медленно только для строк, которые длинные и одинаковые (или почти одинаковые)
Random rand = new Random(1);
String[] list = new String[2000];
for(int i=0;i<list.length;i++)
list[i] = "1234567"+Long.toString(rand.nextInt(36*37), 36); // semi random
int count = 0;
long start = System.nanoTime();
for(int i=0;i<list.length;i++)
for(int j=0;j<list.length;j++)
if (list[i].equals(list[j]))
count++;
long time = System.nanoTime() - start;
System.out.printf("The average time for equals() was %,d ns.%n", time/list.length/list.length);
на ноутбуке с частотой 2,3 ГГц
The average time for equals() was 19 ns.
Если вы интернировали () первое значение и вам нужно интернировать () одно значение для сравнения
if (list[i] == list[j].intern())
печать
The average time for equals() was 258 ns.
Это распространенный случай, поскольку у вас часто есть одно значение, которое, как вы знаете, является интернированным, а второе - вводимым, а не интернированным.
если вы используете только строки String и == it и не учитываете стоимость, печатается
The average time for equals() was 4 ns.
Что во много раз быстрее, если вы делаете миллионы сравнений. Однако для небольшого числа сравнений вы экономите 8 нс, но это может стоить на 250 нс больше.
Может быть проще избежать intern() и использовать equals().
Вот что делает документация по питону:
sys.intern(string)Введите строку в таблицу "внутренних" строк и верните внутреннюю строку - которая является самой строкой или копией. Внутренние строки полезны, чтобы получить небольшую производительность при поиске в словаре - если ключи в словаре интернированы, а ключ поиска интернирован, сравнение ключей (после хеширования) может быть выполнено сравнением указателя вместо сравнения строк. Обычно имена, используемые в программах Python, автоматически интернируются, а словари, используемые для хранения атрибутов модуля, класса или экземпляра, имеют интернированные ключи.
Стажированные строки не бессмертны; вы должны хранить ссылку на возвращаемое значение intern(), чтобы извлечь из этого пользу.
Интернирование строк полезно, когда вам нужно несколько раз сравнить строки (1) из конечного набора (2).
Тогда накладные расходы на интернирование строки перевешиваются преимуществом возможности сделать быстрый == вместо equals(),
Иногда это может быть быстрее, чем при использовании HashMap, который опирается на hashCode() а также equals() звонки.
Все перечисленные вами пункты действительны в определенной степени. Но есть важные контраргументы.
- Неизменность очень важна, особенно если вы используете хеш-карты, и они часто используются.
- Операции со строками строк в любом случае очень медленные, потому что вы должны постоянно перераспределять массив, содержащий символы.
- С другой стороны,
subString()Операции очень быстрые. - Равенство строк действительно часто используется, и вы ничего не теряете там. Причина в том, что строки не интернируются автоматически. На самом деле в Java, если ссылки разные,
equals()возвращается к сопоставлению персонажа. - Очевидно, что использование сильных ссылок для таблицы интернов не является хорошей идеей. Вы должны жить с накладными расходами GC.
- Обработка строк Java была спроектирована так, чтобы экономить пространство, особенно для константных строк и операций с подстрокой.
В целом я бы сказал, что в большинстве случаев оно того стоит и хорошо вписывается в концепцию кучи, управляемой виртуальной машиной. Я мог бы представить некоторые особые сценарии, где это может быть настоящей болью, хотя.
Обеспечивает ли интернирование строк какие-либо существенные преимущества в общем случае?
Да. Это огромная. Попробуйте это в Java.
Напишите простые тесты, которые сравнивают тысячи полуслучайных строк на равенство с интернированием и без него.
a.equals( b ) is slow
a == b is fast.