Если строки являются неизменяемыми в.NET, то почему Substring занимает O(n) времени?
Учитывая, что строки являются неизменяемыми в.NET, мне интересно, почему они были разработаны так, чтобы string.Substring() берет O (substring.Length) время, а не O(1)?
т.е. каковы были компромиссы, если таковые имеются?
5 ответов
ОБНОВЛЕНИЕ: мне очень понравился этот вопрос, я просто написал в блоге. См Строки, неизменность и постоянство
Короткий ответ: O(n) равно O(1), если n не становится большим. Большинство людей извлекают крошечные подстроки из крошечных строк, поэтому то, как асимптотически возрастает сложность, совершенно не имеет значения.
Длинный ответ:
Неизменяемая структура данных, построенная таким образом, что операции с экземпляром позволяют повторно использовать память оригинала с небольшим объемом (обычно O(1) или O(lg n)) копирования или нового выделения, называется "постоянным" неизменяемая структура данных. Строки в.NET являются неизменяемыми; Ваш вопрос по сути "почему они не являются постоянными"?
Потому что, когда вы смотрите на операции, которые обычно выполняются над строками в программах.NET, во всех соответствующих случаях едва ли вообще хуже просто создать совершенно новую строку. Стоимость и сложность построения сложной постоянной структуры данных не окупаются.
Люди обычно используют "подстроку" для извлечения короткой строки - скажем, десяти или двадцати символов - из несколько более длинной строки - возможно, из пары сотен символов. У вас есть строка текста в файле, разделенном запятыми, и вы хотите извлечь третье поле, которое является фамилией. Длина строки может составить пару сотен символов, а название - пару десятков. Распределение строк и копирование памяти объемом в пятьдесят байтов удивительно быстро на современном оборудовании. То, что создание новой структуры данных, состоящей из указателя на середину существующей строки и длины, также удивительно быстро, не имеет значения; "достаточно быстро" по определению достаточно быстро.
Извлекаемые подстроки, как правило, имеют небольшой размер и короткий срок службы; сборщик мусора скоро вернет их, и они не заняли много места в куче. Поэтому использование постоянной стратегии, которая поощряет повторное использование большей части памяти, также не является победой; все, что вы сделали, - замедлили сборщик мусора, потому что теперь он должен беспокоиться о работе с внутренними указателями.
Если бы операции с подстрокой, которые люди обычно выполняли со строками, были совершенно другими, то имело бы смысл придерживаться постоянного подхода. Если бы у людей обычно были строки из миллионов символов, и они извлекали тысячи перекрывающихся подстрок с размерами в диапазоне сотен тысяч символов, и эти подстроки долгое время жили в куче, тогда было бы разумно использовать постоянную подстроку. подход; это было бы расточительно и глупо не делать этого. Но большинство программистов, занимающихся бизнесом, не делают ничего, даже смутно подобного рода. .NET не является платформой, адаптированной для нужд проекта "Геном человека"; Программисты анализа ДНК должны решать проблемы с этими характеристиками использования строк каждый день; шансы хороши, что нет. Те немногие, кто создает свои собственные постоянные структуры данных, точно соответствуют сценариям их использования.
Например, моя команда пишет программы, которые на ходу анализируют код C# и VB по мере его ввода. Некоторые из этих файлов кода огромны, и поэтому мы не можем выполнять O(n) -текстовые манипуляции для извлечения подстрок или вставки или удаления символов. Мы создали ряд постоянных неизменяемых структур данных для представления изменений в текстовом буфере, что позволяет нам быстро и эффективно повторно использовать большую часть существующих строковых данных и существующих лексических и синтаксических анализов при типичном редактировании. Это была трудная проблема, и ее решение было узко приспособлено для конкретной области редактирования кода на C# и VB. Было бы нереально ожидать, что встроенный строковый тип решит эту проблему для нас.
Именно потому, что строки неизменны, .Substring должен сделать копию хотя бы части оригинальной строки. Создание копии из n байтов должно занять O(n) времени.
Как вы думаете, вы бы скопировали кучу байтов в постоянное время?
РЕДАКТИРОВАТЬ: Mehrdad предлагает вообще не копировать строку, но сохранить ссылку на ее часть.
Рассмотрим в.Net многомегабайтную строку, по которой кто-то звонит .SubString(n, n+3) (для любого n в середине строки).
Теперь ВСЮ строку нельзя собирать мусором только потому, что одна ссылка содержит до 4 символов? Это кажется нелепой тратой пространства.
Кроме того, отслеживание ссылок на подстроки (которые могут даже находиться внутри подстрок) и попытка копирования в оптимальные моменты времени, чтобы избежать победы над GC (как описано выше), делают эту концепцию кошмаром. Гораздо проще и надежнее копировать на .SubStringи поддерживать прямую неизменную модель.
РЕДАКТИРОВАТЬ: Вот хорошее небольшое чтение об опасности сохранения ссылок на подстроки в более крупных строках.
Java (в отличие от.NET) предоставляет два способа выполнения Substring(), вы можете решить, хотите ли вы сохранить только ссылку или скопировать целую подстроку в новую ячейку памяти.
Простой .substring(...) разделяет внутреннее использование char массив с исходным объектом String, который вы затем с new String(...) при необходимости можно скопировать в новый массив (чтобы не мешать сборке мусора из исходного).
Я думаю, что такая гибкость - лучший вариант для разработчика.
Ява использовалась для ссылки на более крупные строки, но:
Java также изменила свое поведение на копирование, чтобы избежать утечки памяти.
Я чувствую, что это может быть улучшено, хотя: почему бы просто не сделать условное копирование?
Если подстрока по крайней мере вдвое меньше родительского, можно ссылаться на родительский. В противном случае можно просто сделать копию. Это позволяет избежать утечки большого количества памяти, но при этом обеспечивает значительную выгоду.
Ни один из приведенных здесь ответов не относится к "проблеме скобок", то есть строки в.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.)
Эта структура обеспечивает быстрый поиск длины строки (полезно во многих контекстах) и позволяет передавать указатель в API P/Invoke для Win32 (или других), которые ожидают строку с нулевым символом в конце.
Когда вы делаете 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> "substring" хранит длину независимо, и это не гарантирует, что после конца значения стоит '\ 0'. Он может быть использован во многих отношениях "как строка", но это не "строка", поскольку он не имеет характеристик BStr или CStr (тем более, что они оба). Если вы никогда (напрямую) не вызываете P/Invoke, то нет большой разницы (если API, который вы хотите вызвать, не имеет ReadOnlySpan<char> перегрузки).
ReadOnlySpan<char> не может использоваться в качестве поля ссылочного типа, поэтому есть также ReadOnlyMemory<char> (s.AsMemory(0, 5)), который является косвенным способом ReadOnlySpan<char>так что те же отличия отstring существовать.
В некоторых ответах / комментариях к предыдущим ответам говорилось о том, что бесполезно, когда сборщик мусора должен хранить строку из миллиона символов, пока вы продолжаете говорить о 5 символах. Именно такое поведение вы можете получить с ReadOnlySpan<char> подход. Если вы просто делаете короткие вычисления, подход ReadOnlySpan, вероятно, лучше. Если вам нужно сохранить его на некоторое время, и вы собираетесь сохранить только небольшой процент от исходной строки, возможно, лучше сделать правильную подстроку (чтобы обрезать лишние данные). Где-то посередине есть точка перехода, но это зависит от вашего конкретного использования.