Как бы вы реализовали свой тип строки?

Question

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

Вопрос: Если программист объявляет строковую переменную (предположим, строго типизированный), как бы вы решили хранить эту переменную в памяти?

Есть много вариантов использования, но у вас есть конкретная модель, которая превосходит в определенных областях? Ваша строка изменчива? Это изменчиво, но только до определенной длины, которая не является концом памяти? Можно ли динамически установить длину или это можно сделать только во время компиляции? Легко ли получить доступ к n-му элементу? Требуется ли для строки непрерывный сектор памяти? Может ли он быть разбит на более мелкие строки?

Некоторые вещи, которые следует учесть программистам при работе с вашей строкой: Расчет длины. Добавление в строку. Извлечение частей строки (подстрок). Применяя Regex. Преобразование в другое значение (число, логическое значение и т. Д.)

РЕДАКТИРОВАТЬ: разъяснение того, что я имею в виду.

Если пользователь заявляет следующее:

var Name : string

Как бы вы выбрали, как дизайнер языков, как сохранить это в ОЗУ? Каковы преимущества и недостатки вашего метода и т. Д.

Answer 1

Если бы я писал язык с нуля, я бы хотел определить как изменяемые, так и неизменяемые строковые типы. Неизменность делает операции обработки строк намного быстрее, но создает серьезные ограничения, особенно когда речь идет о конкатенации и т. П.

Неизменяемая строка, которую я буду хранить в виде массива значений Unicode с нулевым символом в конце. Изменяемая строка, которую я бы сохранял в виде связанного списка символов Юникода для упрощения перестановки, нарезки и т. Д.

Answer 2

Я бы избегал строк C Вычисление длины O (n). Совместное использование подстрок практически невозможно. Непрерывное требование к памяти приводит к фрагментации. Любая проблема с терминатором приводит к ошибкам и дырам в безопасности. Если вы храните его как UCS-4, вы тратите много места на строки ASCII (и теряете совместимость с C, единственное преимущество строк C); если вы сохраните его как UTF-8, индексирование будет O (n). Тип ASCIZ в PDP-11 действительно имеет большой смысл, когда вы пишете библиотеку для ASCII на чистом PDP-11.

Языки, младше PDP-11, часто используют другую структуру:

• Паскаль использует поле длины вместо терминатора - их strlen () равен O (1).
• Forth использует double (адрес, длина) - их strlen () равен O (1), плюс они могут легко использовать подстроки.
• Многие современные "управляемые" языки, такие как Java, также хранят длину отдельно.
• В других языках (например, Common Lisp) строки являются просто подтипом вектора (элементы которого являются символами).
• Команда Excel использовала C, но реализовала свои собственные строки Pascal для повышения производительности.

Я бы использовал что-то вроде веревки . Конкатенация постоянная. Они не требуют непрерывной памяти. Совместное использование подстроки легко. Все операции могут выполняться без блокировки в многопоточной среде. Возможно, позволят узлам UCS-4 и ASCII сделать хранилище более компактным в обычном случае и / или автоматически использовать более простую структуру для очень коротких строк.

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

Answer 3

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

Конечно, я склонен к UTF-8, и, вероятно, договорился бы, чтобы стандартная библиотека работала в этом механизме

Кроме того, я бы подумал об использовании структурного представления, которое немного умнее, чем массив байтов, потому что кто хочет возиться с буферами!

Библиотека шаблонов SGI поставляется с абстрактным типом 'Rope', который делает это довольно хорошо. Итераторы (но не итерации) дороги, но взамен вставки, удаления, добавления, поддиапазоны и сравнения довольно дешевы.

В руководстве по программированию на Lua есть еще одна хорошая реализация, в которой реализована оптимизация «Ханойская башня», которая идеально подходит для итеративного построения строк спереди назад, как это часто делается при чтении большого файла.

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

Основная причина использования неизменяемых строк заключается в том, что динамический или интерпретируемый язык использует строки для себя. На самом деле он использует атомы, которые являются произвольными, но должны быть конвертируемыми в и из строк. Лисп делает это явно с символьными константами отдельно от строк. Мне это нравится, даже если я не влюблен в Лисп.

Answer 4

Я предполагаю, что вы имеете в виду, как будто вы разрабатывали язык? Тогда, я думаю, я бы пошел с моделью Си и сохранил ее как непрерывный фрагмент памяти, обнуляемый. Это кажется мне наиболее логичным.

Плюсы: не теряется память, если вы сбрасываете ноль.

Минусы: приходится вычислять длину строки с помощью метода и т. Д.

Answer 5

Я полагаю, вы спрашиваете, как бы вы реализовали строковый объект.

Из соображений производительности вы хотели бы сохранить память, выделенную для символов в строке, как один блок. Это ускорит операции, выполняемые со всеми элементами: изменение регистра, копирование, вычисление длины, indexof и т. Д. Это также облегчит реализацию операций, которые работают с началом или концом строки - обрезка, подстрока и т. Д.

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

Должна ли строка быть неизменной или нет, продиктовано двумя соображениями:

• вы предоставляете прямой доступ к памяти или все операции инкапсулированы в классе?
• Ваше распределение памяти управляется средой выполнения или вам нужно управлять этим самостоятельно?

Традиционный подход C ++ - предоставить прямой доступ к базовой памяти к коду, который использует строковый объект. Это имеет большой смысл, так как память в любом случае выделяется и управляется клиентским кодом, поэтому предоставление прямого доступа к нему обеспечивает наилучшую производительность. Недостатком является то, что любая операция, которая изменяет длину строки, обычно приводит к перераспределению памяти. Существуют умные строковые классы, которые управляют собственным диспетчером памяти для решения этой проблемы, например CString ATL.

Подход C # состоит в том, чтобы инкапсулировать базовую память в объекте и сделать строку неизменной. Это позволяет CLR управлять памятью, а объекты собирать мусор по тем же правилам, которые применяются к любому другому объекту. Из-за этого существует небольшая штрафная плата, но преимущества упрощенного использования и возможности предлагать стабильную реализацию довольно сложных операций перевешивают стоимость выполнения. Кроме того, есть сопутствующий класс StringBuilder, который предлагает некоторые преимущества прямого доступа к памяти, предварительно выделяя больший буфер и изменяя экземпляр в нем, пока он не будет завершен с экземпляром String.

Answer 6

Я бы разбирал класс .NET String и строил бы из этого.