Подтвердить что ты не робот

Действительно ли интернирование строк действительно полезно?

У меня был разговор о строках и разных языках, и тема string interning появилась. Очевидно, что Java и .NET framework делают это автоматически со всеми строками, а также с несколькими языками сценариев. Теоретически это экономит память, потому что у вас нет нескольких копий одной и той же строки, и это экономит время, потому что сравнение равенства строк - это простое сравнение указателей вместо O (N), проходящее через каждый символ строки.

Но чем больше я думаю об этом, тем более скептически я выражаю преимущества концепции. Мне кажется, что преимущества в основном теоретические:

  • Во-первых, чтобы использовать автоматическую интерполяцию строк, все строки должны быть неизменными, что значительно затрудняет выполнение задач строковой обработки, чем они должны быть. (И да, я слышал все аргументы в пользу неизменности вообще. Это не главное.)
  • Каждый раз, когда создается новая строка, она должна быть проверена на основе таблицы интерполяции строк, которая является, по меньшей мере, операцией O (N). ( EDIT:. Где N - размер строки, а не размер таблицы, так как это путало людей). Поэтому, если соотношение между сравнением равенства строк с созданием новой строки довольно велико, маловероятно, что чистая экономия времени будет положительной.
  • Если таблица равенства строк использует сильные ссылки, строки никогда не получат сбор мусора, когда они больше не нужны, тем самым теряя память. С другой стороны, если таблица использует слабые ссылки, то для строкового класса требуется какой-то финализатор для удаления строки из таблицы, что замедляет процесс GC. (Что может быть довольно значительным, в зависимости от того, как реализована статическая таблица строк. В худшем случае удаление элемента из хэш-таблицы может потребовать O (N) перестройки всей таблицы при определенных обстоятельствах.)

Это только результат того, что я думаю о деталях реализации. Есть что-то, что я пропустил? Действительно ли интернирование строк действительно дает какие-либо существенные преимущества в общем случае?

РЕДАКТИРОВАТЬ 2: Хорошо, видимо, я работал из ошибочной посылки. Человек, с которым я разговаривал, никогда не указывал, что интернирование строк необязательно для вновь созданных строк, и на самом деле произвело сильное впечатление, что противоположное было правдой. Спасибо Джону за то, что он задал вопрос прямо. Другой принятый для него ответ.

4b9b3361

ОТВЕТЫ

Ответ 1

Нет, Java и .NET не делают это автоматически со всеми строками. Они (ну, Java и С#) делают это с постоянными строковыми выражениями, выраженными в байткоде /IL, и по запросу через String.intern и String.intern (.NET). Точная ситуация в .NET интересна, но в основном компилятор С# гарантирует, что каждая ссылка на равную строчную константу в сборке заканчивается ссылкой на тот же строковый объект. Это можно сделать эффективно во время инициализации типа и может сэкономить кучу памяти.

Это происходит не каждый раз, когда создается новая строка.

(На фронте неизменяемости строки я очень рад, что строки неизменяемы. Я не хочу, чтобы каждый раз, когда я получаю параметр и т.д., мне нужно делать копию, я не видел. он делает задачи обработки строк сложнее, либо...)

И, как указывали другие, поиск строки в хеш-таблице обычно не является операцией O (n), если вы не невероятно неудачны с хэш-коллизиями...

Лично я не использую интернирование строк в коде пользователя-земли; если я хочу какой-то кеш строк, я создам HashSet<string> или что-то подобное. Это может быть полезно в различных ситуациях, когда вы ожидаете встретить одни и те же строки несколько раз (например, имена XML-элементов), но с простой коллекцией вы не загрязняете общесистемный кеш.

Ответ 2

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

Это верно, и строка неизменна в Java. Я не уверен, что это плохо. Не вдаваясь в неизменяемый vs mutable, мне нравится думать, что это отличный дизайн из-за кеширования и гораздо большей простоты, к которой я не получу.

Каждый раз, когда создается новая строка, она должна быть проверена на строка интерполяции, которая является, по меньшей мере, операцией O (N). Поэтому, если отношение сравнений равенства строк с новым построением строк довольно высоко, маловероятно, что чистая экономия времени будет положительной значение.

Не точно O (n). Вы можете делать hashmaps и/или другие структуры данных, которые будут приближать это к постоянному поиску.

Если таблица равенства строк использует сильные ссылки, строки будут никогда не собирайте мусор, когда они больше не нужны, теряя память. С другой стороны, если таблица использует слабые ссылки, то для строкового класса требуется какой-то финализатор для удаления строка из таблицы, что замедляет процесс GC. (Которая могла бы быть довольно значительным, в зависимости от того, как статическая таблица строк реализованы. В худшем случае удаление элемента из хеш-таблицы может требуют O (N) перестройки всей таблицы при определенных обстоятельства.)

Вы правы в этом, и я согласен с вами. Кроме того, я чувствую, что обработка GC и незначительная. Преимущества в долгосрочной перспективе гораздо полезнее, чем сборщик мусора, выполняющий дополнительную проверку. Я не уверен, что вы подразумеваете под O (n) для удаления из hashtable. Большинство операций с хэш-таблицами - O (1)

Итак, в целом, я думаю, ваше предположение, что большинство операций являются линейными. Но поиск строк ближе к постоянному времени. Таким образом, этот подход будет иметь незначительную потерю производительности, но огромный прирост памяти. Я бы сказал, что это того стоит.

Вот хорошая цитата о том, что на самом деле происходит и как оно сохраняет память.

Чтобы сохранить память (и ускорить тестирование для равенства), Java поддерживает "интернирование" строк. Когда метод intern() вызывается на Строка, поиск выполняется в таблице интернированных строк. Если Объект String с тем же содержимым уже находится в таблице, возвращается ссылка на строку в таблице. В противном случае Строка добавляется в таблицу и возвращается ссылка на нее.

Ответ 3

A.равнения (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.

Если вы станете() первым значением и должны выполнить intern() одно значение для сравнения

       if (list[i] == list[j].intern())

печатает

The average time for equals() was 258 ns.

Это обычный случай, так как у вас часто есть одно значение, которое, как вам известно, интернировано, а вторая - входная и не интернированная.

если вы используете только интернированные строки и == это, и не считаете стоимость, печатает

The average time for equals() was 4 ns.

Это во много раз быстрее, если вы делаете миллионы сравнений. Однако при небольшом количестве сравнений вы сохраняете 8 нс, но может стоить 250 нс больше.

Лучше просто избегать intern() и использовать equals().

Ответ 4

Здесь используется python документация:

sys.intern(string)

Введите строку в таблицу "интернированных" строк и верните интернированную строку, которая является самой строкой или копией. Внутренние струны полезно получить небольшую производительность при поиске в словаре - если ключи в словаре интернированы, а ключ поиска интернирован, ключевые сравнения (после хэширования) могут быть сделаны с помощью сравнения указателя вместо сравнения строк. Обычно имена, используемые в Python программы автоматически интернированы, а словари, используемые для хранения атрибуты модуля, класса или экземпляра имеют интернированные ключи.

Интернированные строки не бессмертны; вы должны сохранить ссылку на возвращаемое значение intern(), чтобы извлечь выгоду из него.

Ответ 5

Все перечисленные вами баллы действительны в определенной степени. Но есть важные контраргументы.

  • Неизбежность очень важна, особенно если вы используете хэш-карты, и они используются много.
  • Операции строковой композиции очень медленные, потому что вам необходимо постоянно перераспределять массив, содержащий символы.
  • С другой стороны, операции subString() выполняются очень быстро.
  • Равноправие строк действительно используется много, и вы ничего там не теряете. Причина в том, что строки не интернированы автоматически. Фактически в Java, если ссылки разные, equals() возвращается к символу путем сравнения символов.
  • Ясно, что использование сильных ссылок для таблицы intern не является хорошей идеей. Вы должны жить с накладными GC.
  • Обработка строки Java была разработана для обеспечения экономии пространства, особенно при работе с постоянными строками и подстроками.

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

Ответ 6

Предоставляет ли строка интернирование какие-либо существенные преимущества в общем случае?

Да. Это огромно. Попробуйте в java.

Напишите простые тесты, которые сравнивают 1000 полуслучайных строк для равенства и без интернирования.

a.equals( b )  is slow

a == b is fast.

Ответ 7

Интерпретация строк полезна, когда вам нужно несколько раз сравнивать строки (1) из конечного множества (2).

Затем накладные расходы на интернирование строки перевешиваются из-за возможности быстро выполнить == вместо equals().

Выполнение этого иногда может быть быстрее, чем использование HashMap, которое полагается на вызовы hashCode() и equals().