Учитывая ФАЙЛ *, как эффективно найти смещение 1-го вхождения "abc"?

Question

Как эффективно выполнить такую ​​работу в C?

Что я могу придумать, это сначала загрузить весь файл в память, а затем выполнить поиск по нему ..

Но есть либолее эффективный способ?

ОБНОВЛЕНИЕ

Загрузить весь файл в память будет невозможно, если файл очень большой.

Answer 1

Загрузка всего файла в память не нужна и неэффективна.Попробуйте что-то вроде этого:

FILE *fl;
int cc = getc(fl);
while (cc != EOF)
{
   if (cc=='a')
   {
     cc = getc(fl);
     if (cc=='b')
     {
       cc = getc(fl);
       if (cc=='c')
          return "FOUND";
      }
    }
    cc = getc(fl);
  }
  return "NOT FOUND";

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

Answer 2

вы можете читать в файле блок за блоком и искать «abc» в каждом блоке.Существуют алгоритмы, такие как поиск Бойера-Мура, для уменьшения количества символов, которые вы должны явно проверять.

в linux, вы можете использовать posix_fadvise, чтобы сообщить ему, что вы будете бродить по файлу.

Answer 3

Какую ОС вы используете?Если это Linux, вы можете использовать карту памяти , чтобы автоматически отобразить определенную часть памяти непосредственно в файл.Это считается гораздо быстрее.

РЕДАКТИРОВАТЬ

mmap не загружает весь файл в память сразу.Это просто более эффективно.

Answer 4

Для поиска строк есть много интересных алгоритмов.Например, в Boyer-Moore вы бы использовали тот факт, что 3-я позиция должна быть 'c', если вы хотите соответствовать 'abc', и если это not 'c', то таблица скажеткак далеко продвинуться (например, если это «d», вы можете пропустить 3, потому что первые 3 буквы вообще не могут вас заинтересовать).

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