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

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

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

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


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

    Долгий ответ:

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

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

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

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

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

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

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

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


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

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

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

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


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

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

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

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

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

    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 -statement, указатель укажет на 0x48.)

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

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


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

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

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

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

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

    Interesting Posts

    Можно ли удалить указатель, который указывает на выделенный массив, но не на начало его?

    Направление пользователя в дочернее состояние при переходе в его родительское состояние с использованием UI-Router

    phpMyAdmin бросает # 2002 не может войти на сервер mysql phpmyadmin

    Вентилятор центрального процессора Sony Vaio работает на полной скорости после установки предварительного просмотра Windows 8.1

    jqGrid динамически разрешает идентификатор пейджинга сетки?

    Аутентификация Windows и добавление полномочий авторизации через базу данных – MVC asp.net

    Почему преобразование из строковой константы в ‘char *’ допустимо в C, но недействительно в C ++

    Что означает каждая из деталей в dpkg -l?

    Выбор размера экрана для Windows

    Зачем мне обновлять свой IP-адрес каждый раз, когда я запускаю свой компьютер, прежде чем я смогу получить доступ в Интернет?

    Windows 7 заблокирована в учетной записи администратора, которая не имеет пароля

    При каких условиях создается JSESSIONID?

    Динамический метод отправки в C

    Шпатлевка: как подавить предупреждения о безопасности?

    Как настроить собственный сервер GIT? Что такое голые / не-голые репозитории?

    Давайте будем гением компьютера.