Если строки являются неизменяемыми в .NET, то почему Substring занимает O (n) времени? - PullRequest
Новая
       42

Если строки являются неизменяемыми в .NET, то почему Substring занимает O (n) времени?

443 голосов
/ 19 июля 2011

Учитывая, что строки являются неизменяемыми в .NET, мне интересно, почему они были разработаны так, что string.Substring() занимает время O (substring.Length) вместо O(1)?

т.е. каковы были компромиссы, если таковые имеются?

Ответы [ 5 ]

417 голосов
/ 19 июля 2011

ОБНОВЛЕНИЕ: мне очень понравился этот вопрос, я просто написал в блоге. См. Строки, неизменность и постоянство

Краткий ответ: O (n) - это O (1), если n не становится большим. Большинство людей извлекают крошечные подстроки из крошечных строк, поэтому то, как сложность асимптотически возрастает, составляет полностью не имеет значения .

Длинный ответ:

Неизменяемая структура данных, построенная таким образом, что операции над экземпляром позволяют повторно использовать память оригинала с небольшим объемом (обычно O (1) или O (lg n)) копирования или нового выделения, называется «постоянная» неизменяемая структура данных. Строки в .NET являются неизменяемыми; Ваш вопрос по сути "почему они не являются постоянными"?

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

Люди обычно используют «подстроку» для извлечения короткой строки - скажем, десяти или двадцати символов - из несколько более длинной строки - может быть, пару сотен символов. У вас есть строка текста в файле, разделенном запятыми, и вы хотите извлечь третье поле, которое является фамилией. Длина строки может составить пару сотен символов, а название - пару десятков. Выделение строк и копирование памяти из пятидесяти байтов на современных аппаратных средствах удивительно быстро . То, что создание новой структуры данных, состоящей из указателя на середину существующей строки и длины, равно и удивительно быстро, не имеет значения; «достаточно быстро» по определению достаточно быстро.

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

Если бы операции с подстрокой, которые люди обычно выполняли со строками, были совершенно другими, то имело бы смысл придерживаться постоянного подхода. Если бы у людей обычно были строки из миллионов символов, и они извлекали тысячи перекрывающихся подстрок с размерами в диапазоне сотен тысяч символов, и эти подстроки долгое время жили в куче, тогда было бы разумно использовать постоянную подстроку. подход; это было бы расточительно и глупо не делать этого. Но большинство программистов, занимающихся бизнесом, не делают ничего, даже смутно подобного рода . .NET не является платформой, адаптированной для нужд проекта «Геном человека»; Программисты анализа ДНК должны решать проблемы с этими характеристиками использования строк каждый день; хорошие шансы, что вы нет. Те немногие, кто создает свои собственные постоянные структуры данных, которые близко соответствуют их сценариям использования.

Например, моя команда пишет программы, которые на лету анализируют код C # и VB по мере его ввода. Некоторые из этих файлов кода огромны , и поэтому мы не можем делать O (n) манипуляции со строками для извлечения подстрок или вставки или удаления символов. Мы создали ряд постоянных неизменяемых структур данных для представления изменений в текстовом буфере, что позволяет нам быстро и эффективно повторно использовать массив существующих строковых данных и существующих лексических и синтаксических анализов по типичным редактировать. Это была трудная проблема, и ее решение было узко приспособлено для конкретной области редактирования кода на C # и VB. Было бы нереально ожидать, что встроенный строковый тип решит эту проблему для нас.

119 голосов
/ 19 июля 2011

Точно , поскольку Строки являются неизменяемыми, .Substring должен сделать копию хотя бы части исходной строки. Создание копии n байт должно занять O (n) времени.

Как вы думаете, как скопировать кучу байтов за константу времени?

РЕДАКТИРОВАТЬ: Mehrdad предлагает вообще не копировать строку, но сохранить ссылку на ее часть.

Рассмотрим в .Net строку размером в несколько мегабайт, для которой кто-то вызывает .SubString(n, n+3) (для любого n в середине строки).

Теперь ВСЮ строку нельзя собирать мусором только потому, что одна ссылка содержит до 4 символов? Это кажется нелепой тратой пространства.

Кроме того, отслеживание ссылок на подстроки (которые могут даже находиться внутри подстрок) и попытка копирования в оптимальные моменты времени, чтобы избежать победы над GC (как описано выше), делает эту концепцию кошмаром. Гораздо проще и надежнее копировать на .SubString и поддерживать прямую неизменяемую модель.

РЕДАКТИРОВАТЬ: Вот хорошее небольшое чтение об опасности сохранения ссылок на подстроки в более крупных строках.

33 голосов
/ 19 июля 2011

Java (в отличие от .NET) предоставляет два способа выполнения Substring(), вы можете решить, хотите ли вы просто сохранить ссылку или скопировать целую подстроку в новое место в памяти.

Простой .substring(...) разделяет используемый внутренне массив char с исходным объектом String, который затем можно при помощи new String(...) при необходимости скопировать в новый массив (чтобы не мешать сборке мусора исходного).

Я думаю, что такая гибкость - лучший вариант для разработчика.

12 голосов
/ 03 декабря 2013

Java используется для ссылки на более крупные строки, но:

Java также изменила свое поведение на , копируя , чтобы избежать утечки памяти.

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

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

2 голосов
/ 16 июля 2018

Ни один из приведенных здесь ответов не относится к «проблеме скобок», то есть строки в .NET представлены в виде комбинации BStr (длина, хранящаяся в памяти «перед» указателем) и CStr (строкаоканчивается на '\ 0').

Строка "Hello there", таким образом, представляется как 

0B 00 00 00 48 00 65 00 6C 00 6F 00 20 00 74 00 68 00 65 00 72 00 65 00 00 00

(если она присваивается char* в fixed заявленииуказатель будет указывать на 0x48.)

Эта структура позволяет быстро искать длину строки (полезно во многих контекстах) и позволяет передавать указатель в P / Invoke на Win32 (или другое) API, которые ожидают строку с нулевым символом в конце.

Когда вы делаете Substring(0, 5) правило "о, но я обещал, что после последнего символа будет нулевой символ", вы должны сделать копию,Даже если вы получили подстроку в конце, тогда не было бы места, чтобы поместить длину без искажения других переменных.

Иногда, тем не менее, вы действительно хотите поговорить о «серединестрока ", и вам не обязательно заботиться о поведении P / Invoke.Недавно добавленная структура ReadOnlySpan<T> может использоваться для получения подстроки без копирования: 

string s = "Hello there";
ReadOnlySpan<char> hello = s.AsSpan(0, 5);
ReadOnlySpan<char> ell = hello.Slice(1, 3);

Подстрока ReadOnlySpan<char> хранит длину независимо, и это не гарантирует, что есть '\ 0после окончания значения.Он может быть использован во многих отношениях «как строка», но это не «строка», поскольку он не имеет характеристик BStr или CStr (тем более, что они оба).Если вы никогда (напрямую) не вызываете P / Invoke, то нет большой разницы (если API, который вы хотите вызвать, не имеет перегрузки ReadOnlySpan<char>).

ReadOnlySpan<char> не может использоваться в качестве поляссылочного типа, поэтому есть также ReadOnlyMemory<char> (s.AsMemory(0, 5)), который является косвенным способом иметь ReadOnlySpan<char>, поэтому существуют такие же отличия от * string.

Некоторые изответы / комментарии к предыдущим ответам говорили о том, что сборщик мусора должен расточительно хранить строку из миллиона символов, пока вы продолжаете говорить о 5 символах.Именно такое поведение вы можете получить с помощью подхода ReadOnlySpan<char>.Если вы просто делаете короткие вычисления, подход ReadOnlySpan, вероятно, лучше.Если вам нужно сохранить его на некоторое время, и вы собираетесь сохранить только небольшой процент от исходной строки, возможно, лучше сделать правильную подстроку (чтобы обрезать лишние данные).Где-то посередине есть точка перехода, но это зависит от вашего конкретного использования.

...