netch80: (bird)
[personal profile] netch80
Дочка сдаёт задачи по программированию, как это сейчас модно, через e-judge и аналогичные системы.

Первая задача: много вывода. Лимит времени работы в системе - 100 мс. На моём десктопе показывает 45 мс. Вывод через cout << val. Вспоминаю рассказы про тормознутость iostreams, подсказываю про stdio. Переписывает, сдаёт. Локально время сократилось до 2 мс. В целевой системе - прошло.

Вторая задача: очень много ввода (максимум теоретически возможного по условиям - 20 миллионов intʼов). fscanf даёт 1.2 секунды. Ручная замена на враппер вокруг getc() - ~0.2 секунды. Лимит в системе тот же - 100мс. Всё равно много. Вытаскивает вчерашний вариант на Паскале, исправляет ошибки, отправляет. Проходит. Сравниваю время после локального freepascal. 3 миллисекунды(!)

Сначала я подумал, что случилось чудо и паскалевцы сумели оптимизировать до предела. Но решил посмотреть внимательнее. Когда ktrace показывает, что из файла на 10M целых читается только 256 байт... мягко говоря, странно. Пропущу пляски с бубном, но результат раскопок: во FreePascal двухбайтный integer. Соответственно, 10000000 превратилось на чтении обычным read(n) в... -27008. Последующий цикл чтения for i:=1 to n тупо выполнился ноль раз. А тесты как раз сошлись так, чтобы повторить эту ошибку.
Посмотрел, что там longint - 4 байта, заменил все integer на него. Время работы на те же 20M целых поднялось до 1.7 секунды. Что ж, отсутствие чуда уже доказано.

Вот как можно на таких допотопных средствах детей учить?
From:
Anonymous (will be screened)
OpenID (will be screened if not validated)
Identity URL: 
User
Account name:
Password:
If you don't have an account you can create one now.
Subject:
HTML doesn't work in the subject.

Message:

 
Notice: This account is set to log the IP addresses of everyone who comments.
Links will be displayed as unclickable URLs to help prevent spam.

Profile

netch80: (Default)
netch80

April 2017

S M T W T F S
      1
234 5678
9101112131415
1617 181920 2122
23242526272829
30      

Most Popular Tags

Style Credit

Expand Cut Tags

No cut tags
Page generated Jun. 27th, 2017 10:22 am
Powered by Dreamwidth Studios