16

Давеча побывал на собеседовании, одним из заданий было реализовать функционал strlen() без применения сторонних функций, то есть руками. Как полный дилетант в Си я изобразил простой цикл. Мне было указано что данная реализация неэкономна, а также что ее можно записать без лишних переменных и в одну строку. Разумеется не в смысле засовывания все в одну строку, а именно иной алгоритм. Речь не шла о производительности или оптимизации с точки зрения практики, и как я понимаю, вопрос носил чисто академический характер. Это вызвало у меня интерес, так как на собеседовании я сделать этого не смог. Общаясь с более компетентным коллегой получил от него реализацию:

size_t str_len (const char *str)
{
    return (*str) ? str_len(++str) + 1 : 0;
}

Я бы пожалуй пока до такого сам не додумался бы, но теперь вопрос у коллеги - существует ли вариант в одну строку без рекурсии?

PS: завел также топик на SO на одноименную тему. Надеюсь будет интересно участвовавшим в дискуссии.

7
  • 1
    Мне бы тоже такая реализация в голову не пришла. IMHO тут или рекурсия (порядка strlen(s) лишних переменных, которые просто "спрятаны" в стеке) или "лишняя" переменная. size_t strlen (const char *str) { register const char *s = str; while(*str++); return str - s - 1; } Немного схитрим и "упрячем" ее в регистр.
    – avp
    11 мар 2014 в 19:36
  • avp, благодарю. Пока это единственное в этом треде что хоть как-то напоминает ответ, но по критерию "в одну строку" все же не подходит.
    – AlexThumb
    11 мар 2014 в 19:51
  • @AlexThumb, по крайней мере для gcc могу и в одну строку написать #define STRLEN(s) ({ register typeof((s)[0]) _start = (s); \ register typeof((s)[0]) *_s = _start; \ while (_s++); \ (size_t)(_s - _start - 1); }) только не короче (да и объяснять, почему так, дольше).
    – avp
    11 мар 2014 в 20:13
  • заменять цикл рекурсией это конечно более экономично. а, тут про количество строк речь, мде... 11 мар 2014 в 20:47
  • @Yura Ivanov, формально (с т.з. компилятора, после препроцессора) это одна строка.
    – avp
    11 мар 2014 в 20:51

7 ответов 7

14

В Си невозможно. Всё, что можно записать в одну строку и без вызова других функций, выполняется за время O(1), а нам нужно написать алгоритм, который работает по крайней мере O(N) (N — длина строки).

11

Попробую тоже добавить небольшой комментарий к ответу Дож: действительно, если не прибегать к рекурсии, эти самые N итерации должны быть осуществлены с помощью некоего цикла, будь то for, while или do while, откуда возникает принципиальная невозможность сделать алгоритм в одну строку:

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

size_t custom_strlen(...) {
    for (крутой однострочник) {}
    return длина; // от этой строки никуда не убежать
}

С учётом этого соображения и того, что условие чётко оговаривает лишь "реализовать функционал strlen() без применения сторонних функций", я попробовал немного схитрить:

void stanislaw_len(char * str, size_t *len) {
    for (*len = 0; *str; ++str, (*len)++);
}

P.S. Я знаю, что это хак, просто попробовал из спортивного интереса.


Более интересно другое: я сравнил предложенные здесь методы и strlen между собой:

void stanislaw_len(char * str, size_t *len) {
    for (*len = 0; *str; ++str, (*len)++);
}

size_t KoVadim_len(char * t) {
    return (strchr(t, 0) - t) / sizeof(char);
}

size_t avp_len (const char *str) {
    register const char *s = str;

    while(*str++);
    return (size_t)(str - s - 1);
}

char *STRING = "This is a rather long string! This is a rather long string! This is a rather long string!";

size_t N = 1000000;
size_t M = 10;

__block size_t counter = 0;

Benchmark(M, ^{
    for (int i = 0; i < N; i++) {
        size_t length;

        stanislaw_len(STRING, &length);

        counter += length;
    }
});

NSLog(@"stanislaw_len %ld", counter);

... остальные аналогично

Вот результаты для O3:

The block have been run 10 times. Average is: 67.163414 milliseconds
2014-03-12 16:59:10.429 SandboxCommandLineApp[17606:303] stanislaw_len() 890000000
The block have been run 10 times. Average is: 72.448875 milliseconds
2014-03-12 16:59:11.156 SandboxCommandLineApp[17606:303] avp_len() 890000000
The block have been run 10 times. Average is: 12.458966 milliseconds
2014-03-12 16:59:11.281 SandboxCommandLineApp[17606:303] KoVadim_len() 890000000
The block have been run 10 times. Average is: 8.514538 milliseconds
2014-03-12 16:59:11.367 SandboxCommandLineApp[17606:303] strlen() 890000000

Вопрос к знатокам: что такого может быть вжато в Apple-овских libc dylib-ах, что такая большая разница есть в скорости? Особенно это непонятно в связи с тем, что последняя опубликованная open source - версия strlen.c содержит очень схожие посимвольные проходы, как у меня и @avp (вариант KoVadim тут не в счёт, так как он опять же полагается на системную библиотеку) ?

2
  • 3
    @Stanislaw Pankevich, если интересуетесь, посмотрите strchr.com/optimized_strlen_function и ссылки оттуда. А здесь тоже обсуждают этот вопрос (и есть ссылка на glibc implementation).
    – avp
    12 мар 2014 в 13:30
  • @avp, ещё как интересуюсь! Большое спасибо за ссылку! 12 мар 2014 в 15:54
11

В формулировке сказано "без вызова сторонних функций". А функции стандартной библиотеки являются сторонними функциями? Как по мне, то нет. и мой вариант решения тогда такой:

int newlen(char * t) {
    return (strchr(t, 0) - t) / sizeof(char);
}

По поводу рекурсивного варианта с вопроса - посмотрел скомпилированный вариант (gcc 4.4-4.9 при уровне оптимизации O2, clang 3) - там нет рекурсии - компилятор разворачивает в цикл.

str_len(char const*):                          # @str_len(char const*)
    xorl    %eax, %eax
    cmpb    $0, (%rdi)
    je  .LBB0_3
    xorl    %eax, %eax
.LBB0_2:                                # %tailrecurse
    cmpb    $0, 1(%rdi,%rax)
    leaq    1(%rax), %rax
    jne .LBB0_2
.LBB0_3:                                # %tailrecurse._crit_edge
    ret

Код не идеальный, но достаточно хорош. Никакого стека, никаких лишних обращений к памяти.

5
  • 1
    @KoVadim, здорово Вы с рекурсией разобрались! Почему Вы считаете код gcc 4.4-4.9 не идеальным? Я посмотрел .ident "GCC: (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3" для Pentium(R) Dual-Core CPU E5400 с -O2 делает основной цикл ...... .L5: movl %edx, %eax .L3: leal 1(%eax), %edx cmpb $0, -1(%ecx,%edx) jne .L5 .L2: rep ret ...... тут на одну команду больше (а вот про время выполнения ничего сказать не смогу).
    – avp
    12 мар 2014 в 9:44
  • 2
    Еще немного поигрался. Самым коротким оказался вариант .L9: addl $1, %eax cmpb $0, (%eax) jne .L9 subl %edx, %eax .L8: rep ret для текста while(*str) str++; return str - s; Что интересно, текст while(*str++); return str - s - 1; почему-то производит .L8: movzbl (%eax), %edx addl $1, %eax testb %dl, %dl jne .L8 другой код внутреннего цикла. (Загадка...)
    – avp
    12 мар 2014 в 10:19
  • 2
    @avp > Почему Вы считаете код gcc 4.4-4.9 не идеальным? как минимум, в том коде, который я привел, похоже есть лишний xorl %eax, %eax. Но не нужно забывать, что современные процессоры очень хитрые. И возможно этот лишний xolr там нужен (Например, он будет спариваться с другой командой и делать более быстрый код в результате).
    – KoVadim
    12 мар 2014 в 10:58
  • 3
    Кстати, только что пришло в голову, что если пользоваться другими стандартными функциями (аналогично strchr()), то самым коротким будет #define str_len(s) (strcspn(s, ""))
    – avp
    12 мар 2014 в 11:45
  • 3
    тогда еще круче будет: #define str_len(s) (strlen(s)) 12 мар 2014 в 12:32
0
int strlen(const char* str) {
    for (const char* c = str;;c++) if (!*c) return c-str;
}
5
  • 1
    Вы понимаете, что отсутствие новых строк не означает, что вы написали код в одну строку?
    – user302909
    13 сен 2018 в 14:47
  • 1
    В один statement.
    – mirmik
    13 сен 2018 в 14:55
  • Это, for + if + return, это 3 statement`а, а не 1.
    – user302909
    13 сен 2018 в 15:20
  • statement for определяется рекурсивно. Остальные два являются statement, но входят в первый (а третий при этом входит во второй). Если что, можно ссылку на стандарт найти.
    – mirmik
    13 сен 2018 в 15:21
  • Даже если так, в обычном понимании это не считается за "в одну строку". Иначе какой смысл в этой фразе, если в одну строку можно запихнуть хоть всю программу целиком, минус препроцессорные директивы. 13 сен 2018 в 15:25
-1
int str_len(const char* str) {
    for (char const * a = str, *b = str;;a--,b++) if (!*b) for (int i = 0;; a++, i++) if (a == b) return i / 2;
}
-3
int strlen(const char* str) {
    for (const char* c = str;;({ if (*c++ == '\0') return c - str - 1; }));
}
-6

Я бы сделал так:

size_t SLen(const char *s)
{      
   int k = 0;
   while(s[k++]);
   return --k;
}
17
  • 3
    таким макаром можно целую операционную систему в одну строку написать. В одну длинную-длинную строку
    – DreamChild
    11 мар 2014 в 19:28
  • 1
    @Скрыто1, а вот гадать не надо (это я про sizeof). Учите матчасть.
    – avp
    11 мар 2014 в 19:40
  • 2
    >Я не собирался все в одну строчку указывать А какой тогда вообще смысл, если в вопросе явно стоит условие про одну строку? К тому же ТС изначально сказал, что вариант с циклом был опробован
    – DreamChild
    11 мар 2014 в 19:43
  • 1
    @Скрыто1, вы пробовали вот это "size_t SLen(const char *s) { return sizeof(s) / sizeof(char) - 1; }" запускать?
    – dzhioev
    11 мар 2014 в 19:49
  • 2
    @Скрыто1, не зря Вас минусуют. -- У Вас sizeof(s) - это размер указателя, а sizeof(char) (как ни странно) это 1. Тут дело в том, что в Си (и С++) размер, который дает sizeof() это размер объекта не в байтах, а в sizeof(char). Для получения размера в битах sizeof() надо умножать на константу CHAR_BIT, определенную в <limits.h>. Ну, а для пересчета в байты надо знать, сколько бит в Вашем байте (не везде в байте 8 бит).
    – avp
    11 мар 2014 в 19:55

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.