Быстрое сравнение C

Question

Как часть протокола, я получаю строку C следующего формата:
WORD * WORD
Где оба слова - это одна и та же строка.
And, * - любая строка печатных символов, НЕ включая пробелы!

Таким образом, все следующие данные являются законными:

• WORD asjdfnkn WORD
• WORD 234kjk2nd32jk WORD

И следующие недопустимы:

1. WORD akldmWORD
2. WORD asdm zz WORD
3. NOTWORD admkas WORD
4. NOTWORD admkas NOTWORD

Где (1) отсутствует пробел;(2) имеет 3 или более пробелов;(3) / (4) не открывайте / не заканчивайте правильной строкой (WORD).

Конечно, это может быть реализовано довольно просто, однако я не уверен, что я делаю,самый эффективный.Примечание: WORD предустановлен для всего цикла, однако может меняться от запуска к запуску.

В настоящее время я строю каждую строку против "WORD".Если это проверяет вручную (char-by-char), запустите строку, чтобы проверить второй символ пробела.
[Если найдено] I, тогда strcmp (полностью) с "WORD".

Хотелось бы услышать ваше решение с акцентом на эффективность, так как в режиме реального времени я буду работать над миллионами диссертаций.

Answer 1

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

Или вы можете использовать некоторые готовые реализации.

У вас есть несколько действительно классических алгоритмов для поиска строк внутри другой строки:

KMP (Кнут-Моррис-Пратт)

Рабин-Карп

Бойер-Мур

Надеюсь, это поможет:)

Answer 2

Вы профилировали?

Здесь не так много выгоды, так как вы проводите базовые сравнения строк. Если вы хотите использовать последние несколько процентов производительности, я бы изменил функции str... для функций mem....

char *bufp, *bufe; // pointer to buffer, one past end of buffer
if (bufe - bufp < wordlen * 2 + 2)
    error();
if (memcmp(bufp, word, wordlen) || bufp[wordlen] != ' ')
    error();
bufp += wordlen + 1;
char *datap = bufp;
char *datae = memchr(bufp, ' ', bufe - buf);
if (!datae || bufe - datae < wordlen + 1)
    error();
if (memcmp(datae + 1, word, wordlen))
    error();
// Your data is in the range [datap, datae).

Прирост производительности, вероятно, меньше, чем впечатляющий. Вы должны изучить каждый символ в буфере, поскольку каждый символ может быть пробелом, а любой символ в разделителях может быть неправильным. Изменение цикла на memchr очень удобно, но современные компиляторы знают, как это сделать для вас. Изменение strncmp или strcmp на memcmp также, вероятно, будет незначительным.

Answer 3

Вероятно, необходимо найти компромисс между самым коротким кодом и самой быстрой реализацией.Доступны следующие варианты:

1. Регулярное выражение ^WORD \S+ WORD$ (требуется механизм регулярных выражений)

2. strchr на "WORD " и strrchr на «СЛОВО» с множеством грязных проверок (не очень рекомендуется)

3. Прогулка по всей строке символ за символом, отслеживание состояния, в котором вы находитесь (сканирование первого слова, сканированиепервый пробел, сканирование середины, сканирование последнего пробела, сканирование последнего слова, ожидание конца строки).

Вариант 1 требует наименьшего кода, но возвращается назад, а вариант 2 не требует выкупакачество.Я думаю, что вы можете сделать вариант 3 элегантно.Используйте переменную состояния, и все будет хорошо.Не забудьте вручную ввести последние два состояния, основанные на длине вашего слова и длине всей строки, и это позволит избежать возврата назад, который, скорее всего, будет иметь регулярное выражение.

Answer 4

Если ваша «начинка» должна содержать только «0» - «9», «A» - «Z» и «a» - «z» и в некоторой кодировке основана на ASCII (как большинство кодировок на основе Unicode), тогда вы можете пропустить два сравнения в одном из ваших циклов, поскольку только один бит различается между заглавными и второстепенными символами. Вместо

   ch>='0' && ch<='9' && ch>='A' && ch<='Z' && ch>='a' && ch<='a'

вы получите

   ch2 = ch & ~('a' ^ 'A')

   ch>='0' && ch<='9' && ch2>='A' && ch2<='Z'

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

Если ветвление стоит дороже по сравнению со сравнениями на вашем компьютере, вы также можете заменить && на &. Но большинство современных компиляторов знают этот трюк в большинстве ситуаций.

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

Кроме того, скомпилируйте специально для компьютера, на котором будет выполняться код, и не забывайте о любом поколении кода отладки.

Добавлено:

Не совершайте подпрограммных вызовов в циклах сканирования, если это того не стоит.

Какой бы трюк вы ни использовали для ускорения своих циклов, он уменьшится, если вам придется выполнять подпрограммный вызов в одном из них. Хорошо использовать встроенные функции, которые ваш компилятор встроит в ваш код, но если вы используете что-то вроде внешней библиотеки регулярных выражений, и ваш компилятор не может встроить эти функции (gcc может сделать это иногда, если вы попросите это ), затем выполнение этого вызова подпрограммы будет перетасовывать много памяти, в худшем случае между различными типами памяти (регистры, буферы ЦП, ОЗУ, жесткий диск и т. д.) и может испортить прогнозы ЦП и конвейеры. Если ваши текстовые фрагменты не очень длинные, и вы тратите много времени на их анализ, а подпрограмма достаточно эффективна, чтобы компенсировать стоимость вызова, не делайте этого. Некоторые функции для синтаксического анализа используют обратные вызовы, это может быть более эффективным, чем выполнение большого количества подпрограммных вызовов из ваших циклов (поскольку функция может сканировать несколько совпадений с шаблоном за один цикл и объединять несколько обратных вызовов вне критического цикла) , но это зависит от того, как кто-то другой написал эту функцию, и в основном это то же самое, что вы делаете вызов.

Answer 5

Вы знаете, какова длина строки, которая должна быть проверена? Если нет, вы несколько ограничены в том, что вы можете сделать. Если вы знаете, какова длина строки, вы можете немного ускорить процесс. Вы точно не указали, что часть '*' должна содержать хотя бы один символ. Вы также не указали, разрешены ли вкладки, или переводы строк, или ... это только буквенно-цифровые символы (как в ваших примерах) или знаки препинания и другие символы разрешены? Управляющие символы?

Вы знаете, как долго WORD, и можете заранее построить начальный и конечный маркеры. Функция error() сообщает об ошибке (однако вам необходимо сообщить об этом) и возвращает false. Функция тестирования может быть bool string_is_ok(const char *string, int actstrlen);, возвращая true в случае успеха и false в случае возникновения проблемы:

// Preset variables characterizing the search
static int  wordlen    = 4;
static int  marklen    = wordlen + 1;
static int  minstrlen  = 2 * marklen + 1;  // Two blanks and one other character.
static char bword[]    = "WORD ";          // Start marker
static char eword[]    = " WORD";          // End marker
static char verboten[] = " ";              // Forbidden characters

bool string_is_ok(const char *string, int  actstrlen)
{
    if (actstrlen < minstrlen)
        return error("string too short");
    if (strncmp(string, bword, marklen) != 0)
        return error("string does not start with WORD");
    if (strcmp(string + actstrlen - marklen, eword) != 0)
        return error("string does not finish with WORD");
    if (strcspn(string + marklen, verboten) != actstrlen - 2 * marklen)
        return error("string contains verboten characters");
    return true;
}

Возможно, вы не сможете значительно сократить количество тестов, если хотите получить гарантии. Часть, которая больше всего изменится в зависимости от ограничений в алфавите, это строка strcspn(). Это относительно быстро для небольшого списка запрещенных символов; вероятно, будет медленнее, так как количество запрещенных символов увеличивается. Если вы разрешаете только буквенно-цифровые символы, у вас есть 62 OK и 193 не OK символов, если только вы не считаете некоторые из старших битовых символов алфавитными. Эта часть, вероятно, будет медленной. Вы могли бы сделать лучше с пользовательской функцией, которая принимает начальную позицию и длину и сообщает, все ли символы в порядке. Это может быть в соответствии с:

#include <stdbool.h>

static bool ok_chars[256] = { false };

static void init_ok_chars(void)
{
    const unsigned char *ok = "abcdefghijklmnopqrstuvwxyz...0123456789";
    int c;
    while ((c = *ok++) != 0)
        ok_chars[c] = 1;
}

static bool all_chars_ok(const char *check, int numchars)
{
    for (i = 0; i < numchars; i++)
        if (ok_chars[check[i]] == 0)
            return false;
    return true;
}

Затем вы можете использовать:

return all_chars_ok(string + marklen, actstrlen - 2 * marklen);

вместо звонка на strcspn().

Answer 6

используя STL, найдите количество пробелов .. если они не два, очевидно, что строка неверна ... и используя find (gorith.h), вы можете получить положение двух пробелов и среднего слова! Проверьте на СЛОВО в начале и в конце! Вы сделали ..

Answer 7

Это должно вернуть истинное / ложное условие за O (n) время

int sameWord(char *str)
{
  char *word1, *word2;
  word1 = word2 = str;

  // Word1, Word2 points to beginning of line where the first word is found

  while (*word2 && *word2 != ' ') ++word2; // skip to first space
  if (*word2 == ' ') ++word2; // skip space

  // Word1 points to first word, word2 points to the middle-filler

  while (*word2 && *word2 != ' ') ++word2; // skip to second space
  if (*word2 == ' ') ++word2; // skip space

  // Word1 points to first word, word2 points to the second word

  // Now just compare that word1 and word2 point to identical strings.

  while (*word1 != ' ' && *word2)
     if (*word1++ != *word2++) return 0; //false
  return *word1 == ' ' && (*word2 == 0 || *word2 == ' ');
}

Answer 8

bool check_legal(
        const char *start, const char *end,
        const char *delim_start, const char *delim_end,
        const char **content_start, const char **content_end
) {
  const size_t delim_len = delim_end - delim_start;
  const char *p = start;

  if (start + delim_len + 1 + 0 + 1 + delim_len < end)
    return false;

  if (memcmp(p, delim_start, delim_len) != 0)
    return false;
  p += delim_len;

  if (*p != ' ')
    return false;
  p++;

  *content_start = p;
  while (p < end - 1 - delim_len && *p != ' ')
    p++;
  if (p + 1 + delim_len != end)
    return false;
  *content_end = p;
  p++;

  if (memcmp(p, delim_start, delim_len) != 0)
    return false;

  return true;
}

А вот как это использовать:

const char *line = "who is who";
const char *delim = "who";
const char *start, *end;

if (check_legal(line, line + strlen(line), delim, delim + strlen(delim), &start, &end)) {
  printf("this %*s nice\n", (int) (end - start), start);
}

(Это все не проверено.)

Answer 9

WORD - 4 символа, с uint32_t вы можете сделать быстрое сравнение.Вам понадобится другая константа в зависимости от порядкового номера системы.В остальном все в порядке.

Так как WORD может измениться, вам необходимо предварительно рассчитать uint32_t, uint64_t, ... вам нужно в зависимости от длины WORD.

Не уверен из описания, но если вы доверяете источнику, вы можете просто сжать первые n + 1 и последние n + 1 символов.