在 C 中拆分字符串的最快算法？

Question

我正在编写 CLI 输入解析器，我想知道将字符串拆分为标记的最快算法是什么。

规则：

A space表示令牌结束。
任何字符都可以用反斜杠转义，这意味着我按原样使用它，没有任何特殊含义。（目前只用于转义space）

这是我目前使用的代码：

#define POINTER_ARRAY_STEP 10
#define STRING_STEP 255

char **parse_line(char *line)
{
    char **array;
    size_t array_len;
    size_t array_index;
    size_t token_len;
    size_t token_index;

    array_len = POINTER_ARRAY_STEP;
    array = malloc((array_len + 1) * sizeof(char*)); /* +1 to leave space for NULL */
    array_index = 0;

    token_len = STRING_STEP;
    array[array_index] = malloc(token_len + 1);
    token_index = 0;

    for (; *line; ++line) {
        if (array_index == array_len) {
            array_len += POINTER_ARRAY_STEP;
            array = realloc(array, (array_len + 1) * sizeof(char*));
        }
        if (token_index == token_len) {
            token_len += STRING_STEP;
            array[array_index] = realloc(array[array_index], token_len + 1);
        }
        if (*line == '\') {
            array[array_index][token_index++] = *++line;
            continue;
        }
        if (*line == ' ') {
            array[array_index][token_index] = 0;
            array[++array_index] = malloc(token_len + 1);
            token_index = 0;
            continue;
        }
        array[array_index][token_index++] = *line;
    }
    /* Null terminate the last array element */
    array[array_index][token_index] = 0;

    /* Null terminate the array */
    array[array_index + 1] = NULL;
    return array;
}

Answer 1

建议的最快算法

只传2次。一次查找所需的令牌数和缓冲区长度。

第二次切掉重复的行。

令牌数组指向单个分配的内存，因此完成后，tokens[0] 需要像 tokens 一样被释放。

由于 OP 要求更快的算法，下面是$伪代码$/代码。

char **parse_line(const char *line) {
  size_t token_count = 1;
  const char *p = line;
  $Let `p` each element in `line`$
    $if `*p` is a separator, increment `token_count`
    $else `*p` is an escape not followed by a [=10=]$
      $advance `p`$
    }
  }

  $ `p`, at the end of the string, so allocate enough for a    $
  $ duplicate +1 based on the difference of `p` and the start. $
  $ Check allocation success                                   $ 
  $ Copy into `char *line_buffer`                              $

  // The token count is known, get enough pointers + 1 and check
  char **tokens = malloc(sizeof *tokens * (token_count + 1));

  // More complex code could perform only 1 allocation for `tokens` and `line_buffer`

  $ Let `q` be first element in line_buffer
  $ Let `d` be the same (destination pointer)
  $ set begin_token flag $
  size_t token_index = 0;
  for (;;) {
    $ if begin_token flag set $ {
      $ clear begin_token $
      tokens[token_index] = q;
      d = q;
    }
    $ if `*q` separator (space or [=10=]) $ {
      *d = '[=10=]';
      token_index++;
      $ if *q at end of string $ break;
      $ set begin_token flag $
    $else {
      if `*q` is an escape not followed by a [=10=]$
        $advance q$
      }
      $copy *q to *d, advance both pointers.
    }
  }
  $set last tokens[] to NULL$
  return tokens;
}

Answer 2

你的方法既不安全又低效：你没有检查内存分配失败，而且你调用 realloc() 的次数太多了。

这是另一种方法：

进行第一遍计算令牌和转义的数量，
为令牌分配指针数组和缓冲区
进行第二遍，将字符复制到缓冲区中，拆分令牌并使指针数组指向令牌。
return数组指针。

稍后可以通过对指针数组及其第一个元素调用 free() 来释放内存。

代码如下：

#include <stdlib.h>

char **parse_line(const char *line) {
    size_t len, i, j, k, items = 1, escapes = 0;
    char **array;
    char *buf;

    for (len = 0; line[len]; len++) {
        if (line[len] == '\') {
            escapes++;
            if (line[++len] == '[=10=]')
                break;
        } else
        if (line[len] == ' ') {
            items++;
        }
    }
    if (len == escapes) {
        /* special case empty line */
        array = malloc(sizeof(*array));
        if (array != NULL) {
            array[0] = NULL;
        }
        return array;
    }
    array = malloc((items + 1) * sizeof(*array));
    buf = malloc(len + 1 - escapes);

    if (array == NULL || buf == NULL) {
        free(array);
        free(buf);
        return NULL;
    }
    items[0] = buf;
    k = 1;
    for (i = j = 0; i < len; i++) {
        if (line[i] == '\') {
            if (++i == len)
                break;
            buf[j++] = line[i];
        } else
        if (line[i] == ' ') {
            buf[j++] = '[=10=]';
            items[k++] = buf + j;
        } else {
            buf[j++] = line[i];
        }
    }
    buf[j] = '[=10=]';
    items[k] = NULL;
    return items;
}

在 C 中拆分字符串的最快算法？

Fastest algorithm for splitting a string in C?

c

string

algorithm

command-line-interface

tokenize