Количество строк в текстовом файле

[Igors]

в) QFile при уничтожении сам все закроет?
если в) - както я это упустил (а  лезть в ассист - уже лень).

Да. закроет. И еще одна мелочь: в студии может быть очень большая разница между STL скомпиленным в "debug" и "release". Для чистоты эксперимента (и чтобы избежать возможных обвинений в необъективности) нужно использовать "release". А вообще спасибо за проделанную работу - приятно видеть реальные факты и цифры. Конструктивно, по делу.

[ритт]

и использованием QTestLib результат был бы точнее, а код проще.
и почему это я - задро^W нерд? лишь из-за того, что мой код оказался много шустрее других? (

[sendevent]

<...>в студии может быть очень большая разница<...>

я ж грю - STL-вариант в приведенном виде студией (2008) не собирается. решение с переопределением

Код:

istream operator>>(istream& is, MyCustomStringImp& s)

(чтоб оно целиком строки читало) добавило компиллябильности, но с STL я встречаюсь довольно редко и "на Вы" - умудрился накосячить, не заработало потому проверял тока с gcc.

и использованием QTestLib результат был бы точнее, а код проще.

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

и почему это я - задро^W нерд? лишь из-за того, что мой код оказался много шустрее других? (

ну... мы же брутальные программисты, да еще и в рунете - если скажу "чувак, малаццом!" - может быть воспринято как "плюс адин", потому и приходится доносить мысли через дебри ироний, сарказмов, самоироний-самосарказмов и ваще поддерживать вид программиста с нЕрдически-стойким характером.
(как бы, задрот тут - я, ибо заморочился на такую, казалось бы, мелочь, как сабж, на таком уровне; да и еще, оказывается, обожаю, блин, запятые).

и так, перевод на КуТест, поточнее и пооопешнее, "первая кровь".
приведенные примеры кода постарался прооптимизировать - выкинул ненужные закрытия файлов, вместо break'ов - return'ы, поправил написание ника nixMan vs niXman, но это шутка. результат, вроде, не особо отличается, и теперь он примерно такой:

********* Start testing of LinesCounterTest *********
Config: Using QTest library 4.6.3, Qt 4.6.3
PASS   : LinesCounterTest::initTestCase()
<тут должно быть самое интересное, но получается большая простыня текста, поэтому выкинул. кому интересно - сами могут запустить тест>
PASS   : LinesCounterTest::cleanupTestCase()
Totals: 6 passed, 2 failed, 0 skipped
********* Finished testing of LinesCounterTest *********

или так:

author shortNS/shortWS longNS/longWS
niXman 0.4/-- 430/--
garryHotDog 1.4/1.3 1,397/1,305
sendevent 0.16/0.15 270/246
kambala 0.84/0.75 1,315/1,319
konstantin 0.11/0.10 115/113

здесь: short=1024, long=short*short, NS=NoSpaces, WS=WithSpaces, точка - дробь, запятая - тысячи.

при этом всплыла "неочевидная" особенность - в зависимости от исходного файла и отношения к пустым строкам в счестчике - сфейлить могут все приведенные варианты. (N строк в файле - необязательно N "переводов строк", и не всегда надо игнориовать пустую... комуто может показаться банальным, но я сразу об этом не подумал).
для теста используются файлы "кадждая строка с endl", чтобы работать с "последняя строка - без endl'а" - каждый вариант можно лехко допилить.
ну и, как можно было догадаться, опять не рассматривается вариант "на платформе X файл с endl'ами с платформы Y" - тот, у кого стоит такая задача, должен быть в состоянии самостоятельно воспользоваться ранее приведенным примером. (цель была не "протестить все на всем", а так, в общих чертах).

[spectre71]

1) Не правильно создаятся тестовые файлы!
Они открываются в текстовом режиме, соответственно под windows:
#define CURRENT_LINES_DELEMITER "\r\n" в конце строки образует 0D0D0A
2) Общее кол-во строк всегда считается с учетом пустых строк. И здесь без вариантов.
Не надо путать с задачей подсчета кол-ва непустых строк.
Так что не один из методов не дает правильный результат.

[spectre71]

Код

C++ (Qt)
qint64 lineCount(const char* FileName) {
  char fsm [256][8];
  int fh = open(FileName, O_RDONLY|O_BINARY);
 
  if(fh < 0) {
    return -1;
  } else {
    char fsm0 [8] = {6,0,0,0,0,0,6,0};
    char fsm1 [8] = {3,1,5,1,5,1,3,1};
    char fsm2 [8] = {4,2,2,2,2,2,4,2};
 
    for(int i=0; i<256; i++) {memcpy(&(fsm[i][0]), &(fsm0[0]), sizeof(fsm0));}
    memcpy(&(fsm[(unsigned char)'\n'][0]), &(fsm1[0]), sizeof(fsm1));
    memcpy(&(fsm[(unsigned char)'\r'][0]), &(fsm2[0]), sizeof(fsm2));
  }
 
  unsigned char  buff[1024*256];
  int  state = 7;
  qint64 lcount = 0;
  unsigned int len;
  unsigned char* str;
  unsigned char* strE;
 
  for(;;) {
    len = read(fh, buff, sizeof(buff));
    if(!len) {break;}
    if(len < 0) {
      close(fh);
      return -1;
    }
    str   = buff;
    strE  = str+len;
    for(; str<strE; ++str) {
      switch((state = fsm[*str][state])) {
        case 0: case 1: case 2: lcount++;
      }
    }
  }  
  if(lcount) {
    switch(state) {
      case 1: case 2: case 3: case 4: case 5: lcount++;
    }
  }
 
  close(fh);
  return lcount;
}  
 

Самый быстрый способ подсчета строк. Хорошо видно на больших файлах (100 MB; 1,2,10 GB, ...)
Понимает любые перносы строк, в том числе и комбинированные, а также испорченные файлы редактировавшиеся на разных плаформах (преносы типа "0D0D0A0D" итп)

Замена способа чтения буфера:
- "read" на "fread" - увеличит время ~ на 15%
- "read" на "QFile::read" - увеличит время ~ на 70%

Для подсчета строк кол-во состояний можно и уменьшить, поскольку часть из них нужна для определения начал и концов строк.

[Igors]

Ну если уж такое дело - вот мой вариант приаттачен. Интересно сравнить по скорости с предыдущими. Мне кажется разумный баланс это:

- большие файлы обрабатывать надо, не стоит надеяться что все влезет в память
- концы строк "чужой платформы" обрабатывать надо, эта ситуация встречается часто 
- смешанные (битые) концы строк - мне кажется это уже перебор, здесь можно и соврать 

И еще немаловажно: ф-ция должна быть достаточно простой и понятной. Spectre, я верю что Ваш вариант самый быстрый, но разобраться в нем ... Что делать если где-то заклинит? Ломать голову с теорией автоматов?  Пусть лучше медленнее - зато намного проще

[spectre71]

Два варианта
=================

Мой:

Код

C++ (Qt)
qint64 lineCount1(const char* FileName) {
  char fsm0 [8] = {6,0,0,0,0,0,6,0};
  char fsm1 [8] = {3,1,5,1,5,1,3,1};
  char fsm2 [8] = {4,2,2,2,2,2,4,2};
  char fsm [256][8];
 
  for(int i=0; i<256; i++) {memcpy(&(fsm[i][0]), &(fsm0[0]), sizeof(fsm0));}
  memcpy(&(fsm[(unsigned char)'\n'][0]), &(fsm1[0]), sizeof(fsm1));
  memcpy(&(fsm[(unsigned char)'\r'][0]), &(fsm2[0]), sizeof(fsm2));
 
  QFile File(FileName);
  if (!File.open(QFile::ReadOnly)) {return -1;}
 
  char   buff[1024*128];
  qint64 lcount = 0;
  int    len;
 
  int   state = 7;
  char* str;
  char* strE;
  for(;;) {
    len = File.read(buff, sizeof(buff));
    if (File.error()) return -1;
    if(!len) {break;}
 
    str   = buff;
    strE  = str+len;
    for(; str<strE; ++str) {
      switch((state = fsm[(unsigned char)*str][state])) {
        case 0: case 1: case 2: lcount++;
      }
    }
  }  
  if(lcount) {
    switch(state) {
      case 1: case 2: case 3: case 4: case 5: lcount++;
    }
  }
  return lcount;
}  
 

Немного переделаный вариант Igors:

Код

C++ (Qt)
qint64 lineCount2(const char* FileName) {
  QFile File(FileName);
  if (!File.open(QFile::ReadOnly)) return -1;
 
  char   buff[1024*128];
  qint64 lcount = 0;
  int    len;
 
  char prev = 0;
  char cur  = 0;
  for(;;) {
    len = File.read(buff, sizeof(buff));
    if (File.error()) return -1;
    if(!len) {break;}
 
    for (int i=0; i<len; ++i) {
      cur = buff[i];
      if      (cur  == 10) {++lcount;}
      else if (prev == 13) {++lcount;}
      prev = cur;
    }
  }
  if (cur == 13) {++lcount;}
  return lcount + 1;
}
 

В аттаче тестовые файлы с разными типами переводов строк

[sendevent]

раз уж никому, кроме меня, не интересно - "по традиции", циферь:
тестировалось на

qt 4.6.3, gcc 4.4.1, oSuSE 11.2, x86_64 (KDE 4.3.5 r0, если че)

тестовые файлы - чуть выше в треде: info.txt/lines-bad.txt/lines-good-lin.txt/lines-good-win.txt.
исходные файлы не изменялись, один прогон (файлы - 488/127/116/154 b соответственно):

spectre:
0.017/0.015/0.015/0.015
igors:
0.014/0.014/0.017/0.042

исходные данные увеличены таким образом (больше - у меня не помещается в ~):

Код:

void createLongFile( const QString& strFileName )
{
    QFile srcFile( strFileName );
    if( srcFile.open( QIODevice::ReadWrite ) )
    {
        QByteArray baContent = srcFile.readAll();
        for( long i = 65536*64; i >= 0; --i )
        {
            srcFile.write( baContent );
        }
    }
}

исходные данные стали 1,900/508/464/616 Mb соответственно; два прогона:

spectre:
1st: 109,592/18,213/16,003/22,033 (*)
2nd: 87,450/18,911/17,738/20,919
igors:
1st: 68,267/17,894/16,370/22,062
2nd: 65,527/18,603/15,370/21,145

(*) -- разница между прогонами (spectre's 109 vs 87 on info.txt)- хз почему: оба раза - молча курил в сторонке, машинку дополнительно ничем не загружал (в кроне нифига нету, апдейты - вручную, активен тока криейтор и дельфин), но, похоже,  либо я чегото накосячил (непойму хде), либо кьют чегото скешировала.

[spectre71]

(*) -- разница между прогонами (spectre's 109 vs 87 on info.txt)- хз почему: оба раза - молча курил в сторонке, машинку дополнительно ничем не загружал (в кроне нифига нету, апдейты - вручную, активен тока криейтор и дельфин), но, похоже,  либо я чегото накосячил (непойму хде), либо кьют чегото скешировала.

Естественно что система кеширует файлы. Повторный запуск подряд на том же файле размером в 1GB может дать разницу в порядок и больше! Что и было в моих тестах.
Время чтения из файла(которое может сильно варьировать) почти не имеет отношения к проверке скорости работы алгоритма и это необходимо учитывать.