2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу 1, 2  След.
 
 Считывание данных в С++
Сообщение09.08.2006, 17:41 
Заранее извините, если мой вопрос глупый. :oops:
Входные данные состоят из нескольких строк. Как можно, не дочитав строку до конца, начать считывать следующую строку?

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

 
 
 
 
Сообщение09.08.2006, 18:40 
А нельзя читать посимвольно?

 
 
 
 
Сообщение09.08.2006, 18:43 
Аватара пользователя
:evil:
Dan_Te писал(а):
нельзя читать посимвольно?

Грымзик писал(а):
не дочитав строку до конца

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

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

 
 
 
 
Сообщение09.08.2006, 19:35 
незваный гость писал(а):
Читать посимвольно можно, читать посимвольно, не читая — нельзя :). Вопрос, как я понял — нельзя ли сделать что-нибудь вроде seekline().

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

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

 
 
 
 
Сообщение09.08.2006, 19:48 
Аватара пользователя
:evil:
Грымзик писал(а):
А что такое seekline()?

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

 
 
 
 
Сообщение09.08.2006, 20:00 
Аватара пользователя
:evil:
Грымзик писал(а):
Я задала этот вопрос, потому что она у меня не проходит по времени, и я уже просто не знаю как ее ускорить.

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

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

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

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

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

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

 
 
 
 
Сообщение09.08.2006, 20:57 
Код:
#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;}

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

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

Код:
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.

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

 
 
 
 
Сообщение09.08.2006, 21:16 
Аватара пользователя
Внутри цикла

Код:
while (t<=kol)


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

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

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

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

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

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

 
 
 [ Сообщений: 20 ]  На страницу 1, 2  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group