Повідомлень: 167 Звідки: ЛНУ ім. Івана Франка Зареєстрований: 21.10.06
Опубліковано 24-12-2007 18:02
Ні для кого не секрет, що ввід\вивід у С++ через функції scanf, printf працює на порядок швидше, ніж через відповідні потоки cin і cout. Проте не всі знають, що той самий ввід скажімо цілих чисел можна зробити ще швидше, якшо враховувати специфіку вводу. Для цього потрібно використовувати функції getchar\putchar.
Приклад. Нехай нам потрібно зчитати ціле невід'ємне число, то можна написати щось на подобі такої функції:
char ch;
inline void GetInt(int& n)
{
n = 0;
ch = getchar();
while (ch>='0')
{
n = n*10+ch-48;
ch = getchar();
}
}
Інший приклад. Вивід цілого невід'ємного числа:
char st[16];
int top;
inline void PutInt(int n)
{
top = -1;
while (n>9)
{
st[++top] = n%10 + 48;
n/=10;
}
putchar(n+48);
while (top>=0)
putchar(st[top--]);
}
Таким чином швидкість виконання програм, які багато працюють із вводом і/або виводом ЗНАЧНО зростає.
Використовуючи щось подібне до вищенаписаних функцій + оптимізувавши дещо код, я зміг добитися накращого часу виконання на кількох задачах на Тімусі (<a href="http://acm.timus.ru/rating.aspx?space=1&num=1424">1424</a>, <a href="http://acm.timus.ru/rating.aspx?space=1&num=1512">1512</a>, <a href="http://acm.timus.ru/rating.aspx?space=1&num=1373">1373</a>, <a href="http://acm.timus.ru/rating.aspx?space=1&num=1450">1450</a>)
Ця оптимізація відбувається через те, що у С++ ввід/вивід відбувається через регулярні вирази.
Наприклад:
printf("d = %d by %s", dec, str);
той вираз звісно потрібно процесорі розбирати.
Так само, можна написати таке:
printf("%d", dec);
тут також потрібно кожен раз розбирати той вираз, навіть якщо він малий.
Наведені приклади вводу/виводу через getchar/putchar, можна ще оптимізувати наступним чином:
вивести весь вивід у одну стрічку, а потім тільки звичайним виводом (printf("%s", str). У цьому випадку також процесору потрібно розібрати той вираз, але це буде виконано тільки один раз, а при конструкції getchar/putchar відбувається багато викликів функцій, що потребує певного часу. Звісно ця оптимізація вже не дає такого сильного результату, але.
Приклад:
Повідомлень: 167 Звідки: ЛНУ ім. Івана Франка Зареєстрований: 21.10.06
Опубліковано 24-12-2007 23:16
Хм, по-моєму приклад некоректний, бо
while (n)
{
st[++top] = n%10 + '0';
n/=10;
}
дає наше число в перевернутому порядку. І знову ж таки по-моєму краще виводити puts(str), ніж printf("%s",str); , якшо лишень нам перевод стрічки не заважає.
+даний код для кожного числа дасть зайве ділення, і не буде працювати для нуля
Враховуючи наведені міркування мою функцію можна переписати наступним чином:
const int NM=50;
char st[NM];
int top;
inline void PutInt(int n)
{
top = NM - 1;
st[top] = 0;
while (n>9)
{
st[--top] = n%10 + 48;
n/=10;
}
st[--top] = n+48;
puts(st+top);
}
![dixond[злий_пес]acm[на]lviv[на]ua](../themes/Brasil-Fusion/forum/msn.gif)
. У цьому випадку також процесору потрібно розібрати той вираз, але це буде виконано тільки один раз, а при конструкції getchar/putchar відбувається багато викликів функцій, що потребує певного часу. Звісно ця оптимізація вже не дає такого сильного результату, але.
