Считывание данных в С++

[Грымзик]

Заранее извините, если мой вопрос глупый.
Входные данные состоят из нескольких строк. Как можно, не дочитав строку до конца, начать считывать следующую строку?

[незваный гость]

Если я правильно понял Ваш вопрос, то никак. Поскольку строки в файлах C переменной длины, не существует способа найти конец строки иначе, чем дочитав до него. С другой стороны, легко написать функцию, которая читает до конца строки, выбрасывая прочитанное.

[Dan_Te]

А нельзя читать посимвольно?

[незваный гость]

Dan_Te писал(а):

нельзя читать посимвольно?

Грымзик писал(а):

не дочитав строку до конца

Читать посимвольно можно, читать посимвольно, не читая — нельзя . Вопрос, как я понял — нельзя ли сделать что-нибудь вроде seekline().

Я, кстати, упустил одну важную деталь. Это ведь вопрос про С++? Тогда очень важно, каким именно методом ввода пользуются. Мой ответ относится к файловому вводу-выводу, который почти не изменился с С. Если Вы пользуетесь IOStreams, то я за ответ не поручусь.

[Грымзик]

незваный гость писал(а):

Читать посимвольно можно, читать посимвольно, не читая — нельзя . Вопрос, как я понял — нельзя ли сделать что-нибудь вроде seekline().

А что такое seekline()?

Спасибо за ответы. И не могли бы Вы посмотреть задачу http://online-judge.uva.es/p/v102/10267.html.
Я задала этот вопрос, потому что она у меня не проходит по времени, и я уже просто не знаю как ее ускорить.

[незваный гость]

Грымзик писал(а):

А что такое seekline()?

Аналог функции seek() (не существует в стандартной библиотеке). seek() позволяет перепрыгнуть в нужное место файла (не читая), а seekline() позволила бы перепрыгнуть к нужной строке (тоже не читая). Название выдумано как гибрид (смесь бульдога с носорогом) seek() и readline().

[незваный гость]

Грымзик писал(а):

Я задала этот вопрос, потому что она у меня не проходит по времени, и я уже просто не знаю как ее ускорить.

А там не указано никаких временных ограничений. У меня есть подозрение, впрочем, далекое от уверенности, что Ваша программа либо зацикливается при каких-то исходных данных, либо очень неэкономно использует память, вызывая сумасшедший swapping.

Если Вам угодно, Вы можете опубликовать ее здесь (коли небольшая) или положить на какую-нибудь rapidshare.de, а здесь дав нам ссылку (лучше пользуясь тегом [url]).

[Грымзик]

Я не знаю, где я видела про 15 сек, но это точно было. У меня проходит примерно за 15.08 сек. Прогу я выкладываю, только, если что, не очень смейтесь над ней.

текст программы удален (см. сообщение с кодом ниже) // нг

[Грымзик]

У меня было с табами, только здесь они почему то не работают.

[незваный гость]

А Вы поправьте сообщение, используя [code] (выделите код и нажмите кнопку Code), и все заработает…

[Грымзик]

#include <iostream>
#include <cmath>
using namespace std;
int min(int x, int y){
return (x>=y) ? y: x;}
int max(int x, int y){
return (x>=y) ? x: y;}
class line{
public:
   int x, y;};
char a[300][300];
int i, j, N, M;
void O(){
for (i=1; i<=N; ++i)
   for (j=1; j<=M; ++j)
      a[j][i]='O';}
int main(){
char c=0, C, l, name[100], str[100];
int X, Y, X1, Y1, X2, Y2, kol, t;
line s[90000];
while (1>0){
   cin>>c;
   switch (c){
   case 'I':
      cin>>M>>N;
      O();
      for (i=0; i<=N+1; ++i){
         a[0][i]=0;
         a[M+1][i]=0;}
      for (j=0; j<=M+1; ++j){
         a[j][0]=0;
         a[j][N+1]=0;}
      break;
   case 'C':
      O();
      break;
   case 'L':
      cin>>X>>Y>>C;
      a[X][Y]=C;
      break;
   case 'V':
      cin>>X>>Y1>>Y2>>C;
      for (i=min(Y1,Y2); i<=max(Y1,Y2); ++i)
         a[X][i]=C;
      break;
   case 'H':
      cin>>X1>>X2>>Y>>C;
      for (j=min(X1,X2); j<=max(X1,X2); ++j)
         a[j][Y]=C;
      break;
   case 'K':
      cin>>X1>>X2>>Y1>>Y2>>C;
      for (i=Y1; i<=Y2; ++i)
         for (j=X1; j<=X2; ++j)
            a[j][i]=C;
      break;
   case 'F':
      cin>>X>>Y>>C;
      ///////////////////////////////////////////////////
      l=a[X][Y];
      s[1].x=X;
      s[1].y=Y;
      kol=1;
      t=1;
      a[X][Y]=C;
      while (t<=kol){
         if (a[s[t].x-1][s[t].y]==l){
            ++kol;
            s[kol].x=s[t].x-1;
            s[kol].y=s[t].y;
            a[s[kol].x][s[kol].y]=C;}
         if (a[s[t].x+1][s[t].y]==l){
            ++kol;
            s[kol].x=s[t].x+1;
            s[kol].y=s[t].y;
            a[s[kol].x][s[kol].y]=C;}
         if (a[s[t].x][s[t].y-1]==l){
            ++kol;
            s[kol].x=s[t].x;
            s[kol].y=s[t].y-1;
            a[s[kol].x][s[kol].y]=C;}
         if (a[s[t].x][s[t].y+1]==l){
            ++kol;
            s[kol].x=s[t].x;
            s[kol].y=s[t].y+1;
            a[s[kol].x][s[kol].y]=C;}
         ++t;}
      break;
   case 'S':
      cin>>name;
      cout<<name<<endl;
      for (i=1; i<=N; ++i){
         for (j=1; j<=M; ++j)
            cout<<a[j][i];
         cout<<endl;}
      break;
   case 'X':
      return 0;
      break;
   default:
      cin.getline(str,100);
      break;  }}
return 0;}

[PAV]

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

Вот, есть у Вас цикл.

for (j=min(X1,X2); j<=max(X1,X2); ++j)

Как я понял, внутри цикла величины X1 и X2 не меняются. Однако каждый раз после выполнения тела цикла происходит вызов функции max для проверки условия выхода. Нужно вычислить это значение заранее и сохранить в локальной переменной. Функции min и max, кстати, хорошо бы сделать inline, если их приходится вызывать часто, так как вызов функции - операция, в общем-то, накладная.

Или другой пример с двойным циклом

for (i=Y1; i<=Y2; ++i) 
for (j=X1; j<=X2; ++j) 
a[j][i]=C; 

Внутри тела цикла происходит умножение индекса j на 300, затем прибавление к этому значению i, затем сдвиг на полученную величину от адреса a. Как минимум стоит вести внешний цикл по j, а внутренний по i, и перед вызовом внутреннего цикла запомнить адрес, начиная с которого заполняется память. Внутренний цикл тогда, кстати, можно заменить на функцию memset.

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

[PAV]

Внутри цикла

while (t<=kol)

у Вас неоднократно происходит обращение к s[kol]. Лучше бы один раз вычислить и запомнить его адрес.

[незваный гость]

Эту программу можно оптимизировать долго, но это неважно (поскольку программа не отлажена). Самый первый прием, который Вы не используете — вынесение вычисления из цикла и повторное вычисление одного и того же выражения несколько раз.

Укажу на две-три-четыре принципиальные ошибки:
1) программа не инициализирует массив a (по умолчанию). При некоторых раскрасках и некоторой удаче то, что при заполнении нет проверки на выход за границы картинки может Вас весьма далеко увести…
2) Если новый цвет при заполнении совпадет с цветом закрашиваемого пикселя и закрашиваемый пиксел имеет соседа того же цвета, то Ваша программа зациклится.
3) Вы не проверяете ни одного из вводимых данных. Формально, это может быть и не ошибка, но я бы такую программу не принял
4) Программа выводит битмап в stdout, а задание явно указывает — в файл с именем S.

[Igor Borovikov]

Иногда также помогает читать не символам, а целиком сразу весь файл в буфер. Размер буфера вычисляется по размеру файла. Это стандартное упражнение, можно легко найти ссылки на инете. Потом уже буфер разбирается в памяти.

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

Кстати, вопрос несколько в сторону. Автор задания - Alexander Denisjuk. Он, случайно, не преподает у Вас?