Каково обоснование для строк с нулевым символом в конце? - PullRequest
268 голосов
/ 11 декабря 2010

Столько, сколько я люблю C и C ++, я не могу не почесать голову при выборе строк с нулевым окончанием:

  • Длина строки с префиксом (т.е. Паскаль) существовала до C
  • Строки с префиксом длины ускоряют несколько алгоритмов, обеспечивая постоянный поиск по времени.
  • Строки с префиксом длины затрудняют возникновение ошибок переполнения буфера.
  • Даже на 32-битной машине, если вы позволите строке соответствовать размеру доступной памяти, строка с префиксом длины будет всего на три байта шире строки с нулевым символом в конце. На 16-битных машинах это один байт. На 64-битных компьютерах 4 ГБ - разумное ограничение длины строки, но даже если вы хотите расширить его до размера машинного слова, 64-битные машины обычно имеют достаточно памяти, что делает дополнительные семь байтов своего рода нулевым аргументом. Я знаю, что оригинальный стандарт C был написан для безумно плохих машин (с точки зрения памяти), но аргумент эффективности здесь меня не продает.
  • Практически все другие языки (например, Perl, Pascal, Python, Java, C # и т. Д.) Используют строки с префиксом длины. Эти языки обычно превосходят C в тестах работы со строками, потому что они более эффективны со строками.
  • C ++ исправил это немного с помощью шаблона std::basic_string, но массивы простых символов, ожидающие строки с нулевым символом в конце, все еще распространены. Это также несовершенно, поскольку требует выделения кучи.
  • Строки с нулевым символом в конце должны зарезервировать символ (а именно, ноль), который не может существовать в строке, в то время как строки с префиксом длины могут содержать встроенные нули.

Некоторые из этих вещей обнаружились совсем недавно, чем C, поэтому было бы разумно, чтобы C не знал о них. Тем не менее, некоторые были просты задолго до того, как появился С. Почему были выбраны строки с нулевым символом в конце вместо явно превосходящего префикса длины?

РЕДАКТИРОВАТЬ : Поскольку некоторые просили указать фактов (и им не понравились те, которые я уже предоставил) в моем пункте эффективности выше, они вытекают из нескольких вещей:

  • Concat, использующий строки с нулевым символом в конце, требует O (n + m) временной сложности. Длина префикса часто требует только O (м).
  • Длина с использованием строк с нулевым символом в конце требует O (n) временной сложности. Длина префикса O (1).
  • Длина и конкат являются наиболее распространенными строковыми операциями. Есть несколько случаев, когда строки с нулевым символом в конце могут быть более эффективными, но они встречаются гораздо реже.

Из ответов ниже приведены некоторые случаи, когда строки с нулевым символом в конце более эффективны:

  • Когда вам нужно отрезать начало строки и передать ее какому-либо методу. Вы не можете делать это в постоянное время с префиксом длины, даже если вам разрешено уничтожать исходную строку, потому что префикс длины, вероятно, должен следовать правилам выравнивания.
  • В некоторых случаях, когда вы просто просматриваете строку за символом, вы можете сохранить регистр ЦП. Обратите внимание, что это работает только в том случае, если вы не распределяете строку динамически (потому что тогда вам придется освободить ее, что потребует использования того регистра ЦП, который вы сохранили для хранения указателя, который вы изначально получили от malloc и друзей).

Ничто из вышеперечисленного не встречается так часто, как длина и конкат.

В ответах ниже утверждается еще один:

  • Вам нужно обрезать конец строки

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

Ответы [ 17 ]

5 голосов
/ 23 июля 2012

"Даже на 32-битном компьютере, если вы разрешите строке соответствовать размеру доступной памяти, строка с префиксом длины будет всего на три байта шире строки с нулевым символом в конце."

Во-первых, дополнительные 3 байта могут быть значительными издержками для коротких строк.В частности, строка нулевой длины теперь занимает в 4 раза больше памяти.Некоторые из нас используют 64-битные машины, поэтому нам нужно 8 байтов для хранения строки нулевой длины, или формат строки не справляется с самыми длинными строками, поддерживаемыми платформой.

Также могут бытьвопросы выравнивания, чтобы иметь дело с.Предположим, у меня есть блок памяти, содержащий 7 строк, например "solo \ 0second \ 0 \ 0four \ 0five \ 0 \ 0seventh".Вторая строка начинается со смещения 5. Аппаратное обеспечение может потребовать, чтобы 32-разрядные целые числа были выровнены по адресу, кратному 4, поэтому вам нужно добавить заполнение, увеличивая издержки еще больше.Сравнение с C очень эффективно по памяти.(Эффективность памяти хорошая, например, она помогает повысить производительность кэша.)

4 голосов
/ 11 декабря 2010

Нулевое завершение допускает быстрые операции на основе указателя.

3 голосов
/ 25 января 2012

Один момент, о котором еще не говорилось: когда проектировался C, было много машин, в которых символ char не был восьмибитным (даже сегодня есть платформы DSP, где его нет).Если кто-то решит, что строки должны иметь префикс длины, то сколько префикса длины 'char' следует использовать?Использование двух наложило бы искусственное ограничение на длину строки для машин с 8-битным символом и 32-битным адресным пространством, в то же время тратя пространство на машины с 16-битным символом и 16-битным адресным пространством.

Если кто-то хотел разрешить эффективное хранение строк произвольной длины, и если 'char' всегда был 8-битным, то можно - за некоторые затраты в скорости и размере кода - определить схему какстрока с префиксом четного числа N будет иметь длину N / 2 байта, строка с префиксом нечетного значения N и четное значение M (чтение в обратном направлении) могут быть ((N-1) + M * char_max) / 2 и т. д.и требуют, чтобы любой буфер, который утверждает, что предлагал определенное количество пространства для хранения строки, должен позволять достаточное количество байтов, предшествующих этому пространству, для обработки максимальной длины.Однако тот факт, что символ 'char' не всегда равен 8 битам, усложнит такую ​​схему, поскольку число символов 'char', необходимых для хранения длины строки, будет варьироваться в зависимости от архитектуры процессора.

2 голосов
/ 28 августа 2018

Не логическое обоснование обязательно , но контрапункт к кодированию длины

  1. Некоторые формы кодирования динамической длины превосходят кодирование статической длиныЧто касается памяти, все зависит от использования.Просто посмотрите на UTF-8 для доказательства.По сути, это расширяемый массив символов для кодирования одного символа.Это использует один бит для каждого расширенного байта.Окончание NUL использует 8 бит.Префикс длины, я думаю, можно разумно назвать бесконечной длиной, используя 64 бита.То, как часто вы сталкиваетесь с лишними битами, является решающим факторомТолько 1 чрезвычайно большая строка?Кого волнует, используете ли вы 8 или 64 бита?Много маленьких строк (т.е. строк английских слов)?Тогда ваши префиксные расходы будут большим процентом.

  2. Строки с префиксом длины, позволяющие сэкономить время, - не реальная вещь .Независимо от того, требуется ли указанная длина для предоставленных вами данных, вы рассчитываете во время компиляции или вам действительно предоставляются динамические данные, которые вы должны закодировать в виде строки.Эти размеры вычисляются в некоторой точке алгоритма.Можно указать отдельную переменную для хранения размера строки с нулевым символом в конце .Что делает сравнение на спор по экономии времени.У одного просто есть дополнительный NUL в конце ... но если кодирование длины не включает этот NUL, то между ними буквально нет никакой разницы.Там не требуется никаких алгоритмических изменений.Просто предварительный проход, который вы должны сделать самостоятельно, вместо того, чтобы компилятор / среда выполнения делали это за вас.C в основном о том, чтобы делать что-то вручную.

  3. Необязательный префикс длины - это точка продажи.Мне не всегда нужна эта дополнительная информация для алгоритма, поэтому необходимость сделать это для каждой строки делает мое время до вычислений + вычислений никогда не опускающимся ниже O (n).(Т.е. аппаратный генератор случайных чисел 1-128. Я могу извлечь из «бесконечной строки». Допустим, он генерирует только символы так быстро. Поэтому длина нашей строки все время меняется. Но мое использование данных, вероятно, не волнует, каку меня есть много случайных байтов. Он просто хочет получить следующий доступный неиспользованный байт, как только он сможет получить его после запроса. Я мог бы ждать на устройстве. Но я также мог бы иметь предварительно прочитанный буфер символов. Сравнение длиныбесполезная трата вычислений. Нулевая проверка более эффективна.)

  4. Префикс длины - хорошая защита от переполнения буфера?То же самое относится и к использованию библиотечных функций и их реализации.Что если я передам искаженные данные?Мой буфер имеет длину 2 байта, но я говорю функции, что это 7! Пример: Если gets () предназначался для использования с известными данными, он мог иметь внутреннюю проверку буфера, которая проверяла скомпилированные буферы и malloc () вызовыи все еще следовать спецификации.Если он предназначался для использования в качестве канала для неизвестного STDIN для получения неизвестного буфера, тогда очевидно, что невозможно определить размер буфера, что означает, что длина аргумента не имеет смысла, вам нужно что-то еще, например, канарейка.В этом отношении вы не можете использовать префикс длины некоторых потоков и входных данных, вы просто не можете.Это означает, что проверка длины должна быть встроена в алгоритм, а не в волшебную часть системы ввода. TL; DR NUL-прекращение никогда не должно было быть небезопасным, оно просто заканчивалось таким образом из-за неправильного использования.

  5. контрсчетчик: NUL-завершение раздражает двоичный файл.Вам нужно либо сделать префикс длины здесь, либо преобразовать байты NUL каким-либо образом: escape-коды, переназначение диапазона и т. Д., Что, конечно, означает «больше использования памяти / уменьшенная информация / больше операций на байт».Длина префикса в основном выигрывает здесь войну.Единственным преимуществом преобразования является то, что не нужно писать никаких дополнительных функций для покрытия строк с префиксом длины.Это означает, что в ваших более оптимизированных подпрограммах sub-O (n) вы можете автоматически использовать их как O (n) -эквиваленты, не добавляя больше кода.Недостатком является, конечно же, трата времени / памяти / сжатия при использовании на тяжелых строках NUL. В зависимости от того, сколько вашей библиотеки вы дублируете, чтобы работать с двоичными данными, может иметь смысл работать исключительно со строками с префиксом длины.Тем не менее, можно также сделать то же самое со строками с префиксом длины ... -1 длина может означать NUL-концевую, и вы можете использовать NUL-концевые строки внутри концевой длины.

  6. Concat: "O (n + m) vs O (m)" Я предполагаю, что вы ссылаетесь на m как общую длину строки после объединения, потому что они оба должны иметь такое количество операцийминимум (вы не можете просто привязать к строке 1, что если вам нужно перераспределить?).И я предполагаю, что n - это мифическое количество операций, которые вам больше не нужно выполнять из-за предварительного вычисления.Если это так, то ответ прост: предварительно вычислить. Если вы настаиваете, что у вас всегда будет достаточно памяти, чтобы не нуждаться в перераспределении, и это является основой для обозначения big-O, тогда ответ еще более прост: выполните бинарный поиск по выделенной памяти для завершениястрока 1, очевидно, есть большой образец бесконечных нулей после строки 1, чтобы мы не беспокоились о realloc.Там легко добрались до логов (n) и я едва попробовал.Который, если вы помните, log (n) по существу всего лишь 64 на реальном компьютере, что в сущности похоже на выражение O (64 + m), которое по существу равно O (m).(И да, эта логика использовалась при анализе во время выполнения реальных структур данных, используемых сегодня. Это не чушь, что у меня в голове.)

  7. Concat () / Len () снова : запоминание результатов.Легко.Превращает все вычисления в предварительные вычисления, если это возможно / необходимо.Это алгоритмическое решение.Это не принудительное ограничение языка.

  8. Передача суффикса строки легче / возможна с завершением NUL.В зависимости от того, как реализован префикс длины, он может быть разрушительным для исходной строки, а иногда даже невозможен.Требование копии и передача O (n) вместо O (1).

  9. Передача аргументов / разыменование меньше для NUL-завершенных по сравнению с префиксом длины.Очевидно, потому что вы передаете меньше информации.Если вам не нужна длина, это экономит много места и позволяет оптимизировать.

  10. Вы можете обмануть.Это действительно просто указатель.Кто сказал, что вы должны прочитать это как строку?Что если вы хотите прочитать его как один символ или как число с плавающей точкой?Что, если вы хотите сделать обратное и прочитать число с плавающей точкой как строку?Если вы осторожны, вы можете сделать это с помощью NUL-завершения.Вы не можете сделать это с префиксом длины, это тип данных, явно отличающийся от указателя.Скорее всего, вам придется построить строку побайтно и получить длину.Конечно, если вы хотите что-то вроде whole float (вероятно, внутри него есть NUL), вам все равно придется читать побайтово, но подробности оставлены на ваше усмотрение.

TL; DR Используете ли вы двоичные данные?Если нет, то NUL-завершение дает больше алгоритмической свободы.Если да, то количество кода против скорости / памяти / сжатия - ваша основная проблема.Лучше всего сочетать два подхода или запоминание.

2 голосов
/ 05 марта 2015

Многие проектные решения, связанные с C, проистекают из того факта, что при первоначальной реализации передача параметров была несколько дорогой. Имеется выбор между, например,

void add_element_to_next(arr, offset)
  char[] arr;
  int offset;
{
  arr[offset] += arr[offset+1];
}

char array[40];

void test()
{
  for (i=0; i<39; i++)
    add_element_to_next(array, i);
}

против

void add_element_to_next(ptr)
  char *p;
{
  p[0]+=p[1];
}

char array[40];

void test()
{
  int i;
  for (i=0; i<39; i++)
    add_element_to_next(arr+i);
}

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

Хотя существует много разумных способов, которыми C мог бы кодировать длины строк, подходы, которые были изобретены до этого времени, имели бы все необходимые функции, которые должны были бы работать с частью строки, чтобы принимать базовый адрес строка и требуемый индекс как два отдельных параметра. Использование нулевого байтового завершения позволило избежать этого требования. Хотя другие подходы были бы лучше с современными машинами (современные компиляторы часто передают параметры в регистрах, и memcpy можно оптимизировать способами strcpy () - эквиваленты не могут), достаточно производственного кода, использующего строки с нулевым байтом, которые трудно изменить на что-либо другое.

PS - В обмен на небольшое снижение скорости при выполнении некоторых операций и незначительные дополнительные затраты на более длинные строки было бы возможно иметь методы, работающие со строками, принимающие указатели непосредственно на строки, bounds -checked строковые буферы или структуры данных, идентифицирующие подстроки другой строки. Функция типа "strcat" выглядела бы как [современный синтаксис]

void strcat(unsigned char *dest, unsigned char *src)
{
  struct STRING_INFO d,s;
  str_size_t copy_length;

  get_string_info(&d, dest);
  get_string_info(&s, src);
  if (d.si_buff_size > d.si_length) // Destination is resizable buffer
  {
    copy_length = d.si_buff_size - d.si_length;
    if (s.src_length < copy_length)
      copy_length = s.src_length;
    memcpy(d.buff + d.si_length, s.buff, copy_length);
    d.si_length += copy_length;
    update_string_length(&d);
  }
}

Немного больше, чем метод K & R strcat, но он будет поддерживать проверку границ, чего нет у метода K & R. Кроме того, в отличие от текущего способа, можно было бы легко объединить произвольную подстроку, например

/* Concatenate 10th through 24th characters from src to dest */

void catpart(unsigned char *dest, unsigned char *src)
{
  struct SUBSTRING_INFO *inf;
  src = temp_substring(&inf, src, 10, 24);
  strcat(dest, src);
}

Обратите внимание, что время жизни строки, возвращаемой temp_substring, будет ограничено значениями s и src, которые когда-либо были короче (именно поэтому метод требует, чтобы inf передавался - если это было локальный, он умрет, когда метод вернется).

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

Конечно, K & R не реализовала ничего подобного, но, скорее всего, потому, что они не хотели тратить много усилий на обработку строк - область, где даже сегодня многие языки кажутся довольно анемичными.

1 голос
/ 24 июня 2016

По словам Джоэла Спольски в этом блоге ,

Это потому, что микропроцессор PDP-7, на котором были изобретены UNIX и язык программирования C, имел строку ASCIZтип.ASCIZ означало «ASCII с Z (ноль) в конце».

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

0 голосов
/ 20 июня 2017

gcc принимает следующие коды:

char s [4] = "abcd";

, и все будет в порядке, если мы рассматриваем это как массив символов, а не как строкуТо есть мы можем получить к нему доступ с помощью s [0], s [1], s [2] и s [3] или даже с помощью memcpy (dest, s, 4).Но мы получим беспорядочные символы, когда будем пытаться использовать put (s) или, что еще хуже, strcpy (dest, s).

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...