Реализация strlen() на Си в одну строку

#c #strlen #алгоритм

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

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


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

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

Ответы

Ответ 1

Попробую тоже добавить небольшой комментарий к ответу Дож: действительно, если не
прибегать к рекурсии, эти самые 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

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


Ответ 3

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

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


Ответ 4

int strlen(const char* str) {
    for (const char* c = str;;c++) if (!*c) return c-str;
}


Ответ 5

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;
}


Ответ 6

int strlen(const char* str) {
    for (const char* c = str;;({ if (*c++ == '\0') return c - str - 1; }));
}


Ответ 7

Я бы сделал так:
size_t SLen(const char *s)
{      
   int k = 0;
   while(s[k++]);
   return --k;
}