Эффективное средство нахождения положения конца строки

Question

Я работаю с C++, ifstream и текстовыми файлами. Я ищу позицию конца каждой строки, потому что мне нужно прочитать n символов из конца строки.

В настоящее время я читаю каждый байт и проверяю, соответствует ли он символу новой строки Unix (LF).

К сожалению, входной сигнал обычно длинный, и мой метод не является быстрым.

Есть ли более быстрый способ?

Answer 1

Если вы ищете необработанную скорость, я бы сделал карту памяти и использовал что-то вроде strchr, чтобы найти новую строку;

p = strchr(line_start, '\n'); 

тогда так долго, как p не NULL или первый символ в области памяти, вы можете просто использовать p[-1] для чтения символа перед символом новой строки.

Примечание: если файл мог содержать '\0' символы, то вы должны использовать memchr. На самом деле это может быть желательно независимо от того, как он позволяет указать размер буфера (область памяти).

Answer 2

Вы можете взглянуть на функцию getline в std::string. Попробуйте прочитать целую строку за раз, а затем прочитать символы с конца строки.

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

Answer 3

Быстрый & грязный способ что-то вдоль этих линий:

ifs.seekg(0, std::ifstream::end); 
std::string buffer(ifs.tellg(), '\0'); 
ifs.seekg(0, std::ifstream::beg); 
ifs.read(&buffer[0], buffer.size()); 

Затем работа на буфер вместо этого. Это, вероятно, даст вам всю необходимую вам скорость (на мой взгляд, много порядков). Если вы хотите иметь возможность обрабатывать произвольно большие файлы, вам нужно немного изменить логику (вместо этого выполните поиск в кусках).

Answer 4

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

Создайте массив символов размером n и используйте его в качестве циклического буфера: когда вы дойдете до конца массива, просто вернитесь к его началу. Сохраните символ в следующей позиции вашего кругового буфера.

При обнаружении '\n' в вашем буфере содержатся предшествующие символы n, только немного не в порядке: префикс начинается с указателя буфера и идет в конец буфера, а суффикс начинается с нуля и переходит в буфер указатель минус один.

Вот пример того, как вы можете заставить его работать (при условии, n == 20):

int main() 
{ 
    ifstream fs("c:\\temp\\a.txt"); 
    char buf[20]; 
    int bp = 0; 
    bool circular = false; 
    while (fs.good()) { 
     char ch = fs.get(); 
     if (ch != '\n') { 
      buf[bp] = ch; 
      bp = (bp+1) % 20; 
      circular |= !bp; 
     } else { 
      string s; 
      if (circular) { 
       s = string(buf+bp, buf+20) + string(buf, buf+bp); 
      } else { 
       s = string(buf, buf+bp); 
      } 
      cerr << s << endl; 
      circular = false; 
      bp = 0; 
     } 
    } 
    return 0; 
} 

Answer 5

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

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

Если это невозможно, вы можете создать отдельный «индексный» файл. Это не избавит вас от необходимости выполнять линейный поиск один раз, но избавит вас от необходимости повторять его в одном файле. Это, конечно, имеет значение только в том случае, если вы собираетесь обрабатывать один и тот же файл более одного раза.

BTW, даже линейное сканирование должно быть довольно быстрым. Вы должны быть связаны с I/O больше всего на свете. Насколько велики ваши файлы и что вы подразумеваете под «мой метод не быстрый»?

Answer 6

Я работаю с C++, ifstream и текстовыми файлами. Я ищу позицию конца каждой строки, потому что Мне нужно прочитать n символов из конца строки.

я сосредоточусь на ваше требование, чтение «N» символы конца строки, а не ваш вопрос:

// Untested. 
std::string s; 
while(std::getline(std::cin, s)) { 
    if(s.size() > n) s.erase(s.begin(), s.end()-n); 
    // s is the last 'n' chars of the line 
    std::cout << "Last N chars: " << s << "\n"; 
}