|
|
|
|
|
|
|
| 21 Егоров Илья Валерьевич, 05 июня 2020 г. 19:53:46 |
| Можете нагуглить встроенную библиотеку io, там глянуть TextIOBase (лучше всего официальные доки, ибо все остальное — как правило поверхностная интерпретация или перевод ответов stackoverflow, как, скажем, материал про декораторы). + модуль sys и "Built-in Functions". Ну а так объясню также своими словами. Вызвать sys.stdin.readline() — это как, грубо, вызвать просто input(), но первое предпочитаем ради однородности кода. sys.stdin.read(n) считывает n символов (или меньше, если больше считывать нечего). Например, если файл имеет вид '123\n1234567' (\n тут обозначает символ перевода строки) и мы уже считали первую строку, то sys.stdin.read(5) вернет '12345'. Следующий sys.stdin.read(5) вернет '67', а дальнейшие — ''. Даб не импортировать sys, можно сделать в стиле stdin = open(0). 0 есть номер дескриптора стандартного потока ввода, встроенная функция open как раз принимает либо номер дескриптора, либо имя файла, после чего создает новый файловый объект. open также вторым аргументом принимает указание режима, но
|
|
|
| 22 Шарков Евгений Владимирович, 05 июня 2020 г. 9:04:14 |
| Илья я ещё не так хорош как вы или все кто смог обойти эту проблему видимо, мне незнакомы вещи которые были написаны там " sys.stdin.buffer" или "readline()", я пытался понять что-то это, но нигде толком не нашёл как этим пользоваться и что-то из себя представляет. Я буду благодарен если вы объясните или дадите ссылку на статью, сайт где наглядно можно понять как этим пользоваться.
|
|
|
| 23 Егоров Илья Валерьевич, 05 июня 2020 г. 6:48:56 |
| Шарков, см. ниже (например, сообщение от 8 мая). Есть, конечно, на данный момент 4 решения в списке, у которых потребление близко к лимиту (14-15 Мб), где скорее всего асимптотика по памяти та же O(n), но лично я пока с достижением подобного сильно не заморачивался, а потому чего-то кроме велосипеда или блочного чтения предложить не могу. Я вот регулярно слежу "как там у людей с 224", но насчет других не знаю. С ограничением по памяти тут, конечно не очень хорошо, т.к. в 41, где тоже заметный упор на ввод-вывод, условия более щадящие: 2 сек. и 128 Мб.
|
|
|
| 24 Шарков Евгений Владмирович, 04 июня 2020 г. 18:35:59 |
| Я скинул на Python 58 мб, если брать PyPy то 21 мб. Как уменьшить потребление памяти? m = list(map(int, input().split())) Я не обращал раньше внимание на то сколько памяти ушло, всегда проходило. Эта единственная задача в которой я задумался о памяти и незнаю как решить эту проблему.
|
|
|
| 25 Егоров Илья Валерьевич, 16 мая 2020 г. 21:52:00 |
| Поправка к предыдущему: "Пока в _конце_ чанка не будет пробела", чтоб не было недоразумений. И без серьезных изменений размер кода спокойно сокращается до 162, а не 189. С изменениями, из-за которой основная концепция не меняется, но потребление памяти асимптотической сложностью O(1) из наихудшей переходит в амортизированную (т.е. в большинстве случае все еще будет O(1), но при особом сценарии возможно теперь O(n)), можно сократить до 137.
|
|
|
| 26 Егоров Илья Валерьевич, 08 мая 2020 г. 22:10:56 |
| ...ез велосипед, что проверено и на собственном железе для объема данных более 0.5 Гб), но более-менее оптимально по совокупности: затраты времени и памяти удовлетворительны для обоих интерпретаторов, код относительно прост и невелик, асимптотическая сложность есть О(n) при устремлении объема данных к бесконечности.
|
|
|
| 27 Егоров Илья Валерьевич, 08 мая 2020 г. 22:10:39 |
| Универсальный подход для Python 3. Для ввода юзаем sys.stdin.buffer, первую строку игнорируем: просто вызываем readline(). В цикле считываем чанки через read(n), где n = 512 или 4096, зависимо от того, какой алгоритм предпочтете. Пока в чанке не будет пробела (32), делаем += read(1) or b' ' — это упрощенный вариант метода, описанного в предыдущем сообщении. Тут используется свойство ленивости or: b'4' or b' ' == b'4', b'' or b' ' == b' ', т.к. b'' ложно. Далее сплитаем чанк да мэпает в целые числа: map(int, чанк.split()), после чего действуем с полученной последовательностью чисел в соответствии с выбранным алгоритмом, и так для каждого чанка. По времени решение достигает 0.468, большинство значений варьируется в пределе от 0.45 до 0.55 — истинно для CPython и PyPy3. По памяти меньше 1 Мб для CPython / больше 2 Мб для PyPy3. Размер кода может быть сокращен до 189. Оно не оптимально по отдельным параметрам (скажем, для PyPy3 по времени получается в 3-4 раза медленнее описанного ранее специфического подхода чер
|
|
|
| 28 Егоров Илья Валерьевич, 14 апреля 2020 г. 18:17:59 |
| На всякий случай: на CPython можно пройти, если читать файл чанками: берем, скажем, 4 * 1024 байт через .read(), делаем .split() да map(int, ...). Обрезанные числа можно склеивать, чекая на пробел в начале и конце чанка. Скажем, если в конце нет пробела, то pop'аем (полученное до мэпы в числа) да сохраняем до следующей итерации. Наступила следующая итерация — конкатенируем с первым элементом, если в начале чанка нет пробела (есть — вставляем как есть в начало). Не наступила, т.к. файл кончился — обрабатываем отдельно а-ля int(...). Читая через mmap, можно достичь потребления памяти в 7xx Кб, но это зависит от размера кода да чанков. int — это, конечно, ересь, т.к. обобщен под юникод (включая особые виды цифр) и делает тучу проверок, но под CPython велосипеды не эффективны, да и вообще оптимизация под интерпретаторами — занятие не из веселых, ибо приходится плясать под особенности реализации.
|
|
|
| 29 Егоров Илья Валерьевич, 25 января 2020 г. 20:34:10 |
| С таким же успехом можно использовать int64_t (или любые другие два *64_t) из stdint.h, который появился в том же стандарте (C99), что и long long int. Так или иначе, все это упоминалось в ранних сообщениях обсуждения этой задачи, которые почему-то, судя по появлению новых, не особо много кто и читает. Так что совет всем тем, у кого те или иные проблемы с задачей: читайте предыдущие сообщения, их тут на данный момент 3 страницы. Там даже есть те, которые явно намекают на эффективный алгоритм решения задачи, а про обход ограничений и так полно (включая и мои собственные, разве что тут не описаны последние усовершенствования решения на плюсах).
|
|
|
| 30 Егоров Илья Валерьевич, 23 января 2020 г. 18:10:39 |
| Тьфу. *чуть больше мегабайта памяти: с привыканием к Linux API привыкаешь и к байтам в качестве единиц измерения.
|
|
|
| 31 Егоров Илья Валерьевич, 23 января 2020 г. 17:49:29 |
| ...поскольку тут лишь сказано как числа считывать, но нет и намека на алгоритм решения заданной задачи.
|
|
|
| 32 Егоров Илья Валерьевич, 23 января 2020 г. 17:49:06 |
| Открыть файл можно так (не забыв сделать import os, mmap): m = mmap.mmap(os.open('INPUT.TXT', os.O_RDONLY), 0, access = mmap.ACCESS_READ). Считать N можно так: n = 0; c = m.read_byte(); while c > 32:; ~~n = n * 10 + c - 48; ~~c = m.read_byte(); m.read_byte(), где ; обозначает новую строку, а ~~ — отступ. c > 32 проверяет, что код символа больше пробела, что соответствует видимым символам вроде цифр, но не соответствует пробелу, переводу строки, управляющим символам и т.п. 48 — код символа нуля, т.е., например, ord('5') - 48 = 5: так парсим цифры, а цикл строит из цифр число. Последний m.read_byte() нужен только для игнорирования символа возврата каретки, ибо тесты проверяющей системы в стиле винды: \n\r в качестве новой строки. В таком же духе можно парсить и следующие числа, но последний m.read_byte() уже не нужен будет (ибо числа разделяются одним пробелом), да и надо будет добавить обработку отрицательных чисел (символ '-', у которого код 45). P.s. Не считаю, что это относится к нарушению 8 пункта правил,
|
|
|
| 33 Егоров Илья Валерьевич, 23 января 2020 г. 17:27:37 |
| На CPython — среди решений прошедшие имеются, но оно отчасти сомнительно, поскольку на CPython разница между использованием встроенных функций и велосипеда сильно заметна: велосипед, в силу особенностей интерпретации, медленнее. На PyPy3 с этим гораздо лучше: последнее мое решение использует read_byte из модуля mmap, что потребляет лишь чуть больше килобайта памяти, а по времени спокойно достигает 0.156 сек.
|
|
|
| 34 Егоров Илья Валерьевич, 11 января 2020 г. 13:22:25 |
| Для питонистов: 1) Берите PyPy3, поскольку CPython оптимизирован от слова (почти) никак (особенно в случае requests + gevent, когда на CPython могут быть жуткие проседания, но на PyPy3 вообще никаких проблем — это как пример из реального мира); 2) Для ввода юзайте либо этак word = sys.stdin.buffer.read(n), либо, в лучшем случае, word = os.read(sys.stdin.fileno(), n); 3) int(...) не спасет, word.split(b' ') тем более: парсьте числа вручную; 4) Вопреки законам чистого кода, пишите все в одной функции (обязательно в функции), ибо иначе PyPy3 будет выполнять код в 2 раза дольше, жрать память тоже будет до неразумного много; memoryview (для обертки буфера прочитанных данных) ухудшит ситуацию, но array.array, если вам надо какие-то числа списками хранить (но лучше переменными), может самую малость помочь; 5) Размер буфера выставить этак в 8192, от сортировки откажитесь: обходитесь парой if-elif-else. F) Вполне может выдать 0.187 сек., потребляя около 2 с половиной мегов.
|
|
|
| 35 Егоров Илья Валерьевич, 20 августа 2019 г. 21:52:43 |
| Хорошие методы ввода по убыванию производительности: 0) См. пункт 1. В дополнение к там описанному еще и снижение влияния предсказателя ветвлений, зная максимальную длину токена (т.е. вместо проверки достижения конца буфера после каждого символа делаем это после считывания полностью числа). Еще более небезопасно, но еще более быстрее. 1) fread из stdio или in.read из iostream (с отключением блокировки) с кастомным небезопасным парсером. Если верить анализу выхлопа на ассемблере, fread все же быстрее из-за меньшего кол-ва инструкций. Очень быстро, но в прод лучше не надо. 2) fgetc из stdio с тем же парсером, но из-за идентичности логики и отсутствия буферизации смысла не имеет. 3) scanf из stdio. Как компромисс между скоростью, безопасностью и удобством. 4) Ввод через >> из iostream. Медленный, но безопасный и удобный. Отключайте синхронизацию только если уверены, что вы не будете смешивать чтение через stdio и iostream. Вы можете сами убедиться в их производительности, если пожелаете.
|
|
|
| 36 Егоров Илья Валерьевич, 20 августа 2019 г. 21:36:53 |
| Не соглашусь. Без отключения синхронизации iostream будет делать лишние действия, а если вы отключаете синхронизацию для iostream, но используете при этом stdio, то это не имеет смысла. Заметить мало: надо еще и доказать. Увы, мои бенчмарки не подтверждают ваши наблюдения.
|
|
|
| 37 Ерёменко Владислав Владиславович, 20 августа 2019 г. 14:49:39 |
| Давно заметил одну штуку, что обычный файловый ввод-вывод работает лучше таких бустов, как ios_base::sync_with_stdio... и printf, scanf. Поэтому напишите программу через cin, cout и вставьте в самом начале это: ifstream cin("input.txt"); ofstream cout("output.txt"); И всё, тогда пройдёт.
|
|
|
| 38 ГРигорий горбаченко, 29 января 2019 г. 18:58:40 |
| тест который помог 3 -30000 -30000 -30000
|
|
|
| 39 Коншин Андрей Сергеевич, 04 сентября 2018 г. 11:14:24 |
Если кому-то интересно, почему потоки ввода в C++ медленные, то вот статья: https://habr.com/post/246257/ А если ничего из статья непонятно, то просто перед первым вводов напишите: std::ios::sync_with_stdio(false);
Ещё рекомендуют std::cin.tie(nullptr);
|
|
|
| 40 Винк В В, 27 июня 2018 г. 8:37:44 |
| Используем <stdio.h> и scanf() и всё заходит за полсекунды. И printf("%lld",ans) нормально работает. Ну и, конечно, алгоритм должен быть близок к оптимальному.
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
