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 секунды. Что ж, отсутствие чуда уже доказано.

Вот как можно на таких допотопных средствах детей учить?

Date: 2016-11-11 09:58 pm (UTC)
From: [identity profile] filonov.livejournal.com
А у враппера вокруг getc() буфер какого размера был?

Date: 2016-11-12 06:26 am (UTC)
From: [identity profile] netch80.livejournal.com
Читало из файла, опции по умолчанию => скорее всего, 4096. getc() в Torek stdio это макрос (простейший типа return *p++) вокруг буфера самого FILE, своего отдельного не заводилось.
Edited Date: 2016-11-12 06:35 am (UTC)

Date: 2016-11-12 07:38 am (UTC)
From: [identity profile] awind.livejournal.com
а с setbuf/setvbuf поиграть? помнится в давние времена эффект был заметный.

Date: 2016-11-12 08:29 am (UTC)
From: [identity profile] filonov.livejournal.com
Угу. Даже 64К могут дать заметный прирост. Пара мегабайт тем более.

Date: 2016-11-12 12:21 pm (UTC)
From: [identity profile] netch80.livejournal.com
Сейчас эффект будет сильно меньше - за счёт кэширования диска фактически весь входной файл уже давно лежит в RAM.

Реально я как-то сравнивал даже не это, а соотношение скоростей поблочного чтения сисколла read() и stdioʼшного getc(). На FreeBSD read() стал таким же по скорости или лучше при порциях где-то по 230 байт, а на Linux - около 50. То есть при 4096 уже эффект однозначно незаметен.

Date: 2016-11-12 12:34 am (UTC)
From: [identity profile] d1f.livejournal.com
Детей вообще не следует учить IT, только ламерьё плодить.

Date: 2016-11-12 06:37 am (UTC)
From: [identity profile] netch80.livejournal.com
Чушь. Ламерьё будет, если давать необоснованные надежды, но если у обучаемого видны способности, то это вполне причина к обучению.

Date: 2016-11-12 05:16 am (UTC)
From: [identity profile] wom.livejournal.com
В Уссурийском пединституте (теперь ДВФУ) последние 20+ лет учат на Turbo Pascal (запускает теперь только в эмуляторе) и Turbo Prolog 2.0

И потом эти учителя разъезжаются по всему дальнему востоку

Date: 2016-11-12 06:37 am (UTC)
From: [identity profile] netch80.livejournal.com
Интересно, а Пролог зачем?

Date: 2016-11-12 06:45 am (UTC)
From: [identity profile] wom.livejournal.com
в рамках изучения AI
но дают только умение написать пару мелких программ.
И половину лабышек спрашивают как открыть в оболочке TP файл, перейти в начало строки, выделить блок и тд

Date: 2016-11-12 01:24 pm (UTC)
From: [identity profile] d1f.livejournal.com
> последние 20+ лет учат на Turbo Pascal
> И потом эти учителя разъезжаются по всему дальнему востоку

Вот и я о том же.
Прямо карго-культ.

Date: 2016-11-12 09:04 am (UTC)
From: [identity profile] http://users.livejournal.com/_slw/
а какая разница для обучения понятию цикла/переменной/ветвления?

Date: 2016-11-12 12:25 pm (UTC)
From: [identity profile] netch80.livejournal.com
Разница в том, что минимизация эффектов за пределами собственно учебной задачи способствует обучению, а борьба с этими посторонними эффектами - наоборот, мешает.
Когда ученик вместо алгоритма должен гадать, влезет ли число в integer - это помеха. Когда чтение тайно обрезает число без предупреждения - помеха в кубе.
Для сравнения - в Яве попытка Scanner.nextInt() на 2147483648 даёт исключение. Это хуже, чем в Python прозрачное держание чисел до 2**1016-1, но лучше, чем молчаливое урезание.
From: [identity profile] pavel medvedev (from livejournal.com)
Если отключить синхронизацию iostreams с stdio (http://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio), то скорость вывода на консоль не очень отличается от printf. Но другой недостаток iostreams - shevron hell конечно остаётся.
Page generated Oct. 19th, 2017 03:32 am
Powered by Dreamwidth Studios