Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 
[Вернуться к задаче]   1 2 3
  1  Егоров Илья Валерьевич, 06 сентября 2020 г. 22:37:27
     Соколов, стена комментариев не просто так дана. А покуда ограничения не меняются (см. 41 для сравнения "насколько 224 агрессивен"), пусть люди хотя бы подумают заглянуть в лицо тьмы работы с вводом-выводом и качественно оценить "преимущества" построчного чтения перед пословным (которого нет) в Python. Уж извиняюсь, но конструкция вида input().split(), хоть и pythonic way, есть полный изврат по ресурсам, что в той же сишке обходится изящностью нормального решения. {тут было углубление оффтоп про пагубность Python как языка для начинающих}
  2  Соколов Александр Сергеевич, 06 сентября 2020 г. 12:16:50
     У кого падает 48 тест перепишите на плюсы и отправьте через MV C++ ,админ надеюсь ты подправишь это ибо по другому эта задача не проходит ни на каком языке
  3  Абдуматин и Абдуводжид, 12 августа 2020 г. 10:10:35
     ГРигорий горбаченко спасибо за тест, очень помогло.:)
  4  Егоров Илья Валерьевич, 05 июня 2020 г. 21:12:37
     В любом случае, таблица ASCII в помощь. Дополнительно поясню то, что подзабыл упомянуть (как дополнение к сообщению от 8 мая): 1) sys.stdin.buffer не обязателен, можно использовать сам текстовый sys.stdin или же создать новый файловый объект через open(0), даб не импортировать sys. Соответственно, вместо bytes считываться будет простой str. Побочный эффект: на PyPy3 резко перестанет укладываться по времени, поэтому оно и не приводилось, но, учитывая активность гольфистов, не такое уж оно и зло; 2) Вместо += read(1) or b' ' (или же ' ' в случае использования текстового режима) можно и лишь += read(1), т.к. на данный момент во всех тестах имеется в конце пробельный символ. В реальном мире такой срез приводил бы к вечным циклам.
  5  Егоров Илья Валерьевич, 05 июня 2020 г. 21:09:25
     В данном случае разница между использованием текстового и байтового чтения, помимо проходимости на PyPy3, заключается в интерпретации вводимого. Скажем, если рассматривать тот же пример, sys.stdin.buffer.read(5) вернет b'12345' (что есть bytes, или же байтовая строка). '12345'[1] == '2', но b'12345'[1] == 50, т.е. байтовые строки напрямую выдают код символа (ord('2') == 50). Код будет в том стиле, какой режим предпочтете. Например, описанное "пока в конце чанка не будет пробела (пробельного символа)" при текстовом режиме можно сделать в виде while chunk[-1] > ' ': chunk += stdin.read(1). При режиме байтовом — while chunk[-1] > 32: chunk += stdin.read(1).
  6  Егоров Илья Валерьевич, 05 июня 2020 г. 19:54:02
     ...дефолтно это 'r' — текстовое чтение (а вот open(0, 'rb') заменяет sys.stdin.buffer). Можете, собственно, вместо использования стандартного потока ввода считывать из файла INPUT.TXT, даб не изощряться. Вызовы в данном случае примут вид stdin.readline() и stdin.read(n).
  7  Егоров Илья Валерьевич, 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 также вторым аргументом принимает указание режима, но
  8  Шарков Евгений Владимирович, 05 июня 2020 г. 9:04:14
     Илья я ещё не так хорош как вы или все кто смог обойти эту проблему видимо, мне незнакомы вещи которые были написаны там " sys.stdin.buffer" или "readline()", я пытался понять что-то это, но нигде толком не нашёл как этим пользоваться и что-то из себя представляет. Я буду благодарен если вы объясните или дадите ссылку на статью, сайт где наглядно можно понять как этим пользоваться.
  9  Егоров Илья Валерьевич, 05 июня 2020 г. 6:48:56
     Шарков, см. ниже (например, сообщение от 8 мая). Есть, конечно, на данный момент 4 решения в списке, у которых потребление близко к лимиту (14-15 Мб), где скорее всего асимптотика по памяти та же O(n), но лично я пока с достижением подобного сильно не заморачивался, а потому чего-то кроме велосипеда или блочного чтения предложить не могу. Я вот регулярно слежу "как там у людей с 224", но насчет других не знаю. С ограничением по памяти тут, конечно не очень хорошо, т.к. в 41, где тоже заметный упор на ввод-вывод, условия более щадящие: 2 сек. и 128 Мб.
  10  Шарков Евгений Владмирович, 04 июня 2020 г. 18:35:59
     Я скинул на Python 58 мб, если брать PyPy то 21 мб. Как уменьшить потребление памяти? m = list(map(int, input().split())) Я не обращал раньше внимание на то сколько памяти ушло, всегда проходило. Эта единственная задача в которой я задумался о памяти и незнаю как решить эту проблему.
  11  Егоров Илья Валерьевич, 16 мая 2020 г. 21:52:00
     Поправка к предыдущему: "Пока в _конце_ чанка не будет пробела", чтоб не было недоразумений. И без серьезных изменений размер кода спокойно сокращается до 162, а не 189. С изменениями, из-за которой основная концепция не меняется, но потребление памяти асимптотической сложностью O(1) из наихудшей переходит в амортизированную (т.е. в большинстве случае все еще будет O(1), но при особом сценарии возможно теперь O(n)), можно сократить до 137.
  12  Егоров Илья Валерьевич, 08 мая 2020 г. 22:10:56
     ...ез велосипед, что проверено и на собственном железе для объема данных более 0.5 Гб), но более-менее оптимально по совокупности: затраты времени и памяти удовлетворительны для обоих интерпретаторов, код относительно прост и невелик, асимптотическая сложность есть О(n) при устремлении объема данных к бесконечности.
  13  Егоров Илья Валерьевич, 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 раза медленнее описанного ранее специфического подхода чер
  14  Егоров Илья Валерьевич, 14 апреля 2020 г. 18:17:59
     На всякий случай: на CPython можно пройти, если читать файл чанками: берем, скажем, 4 * 1024 байт через .read(), делаем .split() да map(int, ...). Обрезанные числа можно склеивать, чекая на пробел в начале и конце чанка. Скажем, если в конце нет пробела, то pop'аем (полученное до мэпы в числа) да сохраняем до следующей итерации. Наступила следующая итерация — конкатенируем с первым элементом, если в начале чанка нет пробела (есть — вставляем как есть в начало). Не наступила, т.к. файл кончился — обрабатываем отдельно а-ля int(...). Читая через mmap, можно достичь потребления памяти в 7xx Кб, но это зависит от размера кода да чанков. int — это, конечно, ересь, т.к. обобщен под юникод (включая особые виды цифр) и делает тучу проверок, но под CPython велосипеды не эффективны, да и вообще оптимизация под интерпретаторами — занятие не из веселых, ибо приходится плясать под особенности реализации.
  15  Егоров Илья Валерьевич, 25 января 2020 г. 20:34:10
     С таким же успехом можно использовать int64_t (или любые другие два *64_t) из stdint.h, который появился в том же стандарте (C99), что и long long int. Так или иначе, все это упоминалось в ранних сообщениях обсуждения этой задачи, которые почему-то, судя по появлению новых, не особо много кто и читает. Так что совет всем тем, у кого те или иные проблемы с задачей: читайте предыдущие сообщения, их тут на данный момент 3 страницы. Там даже есть те, которые явно намекают на эффективный алгоритм решения задачи, а про обход ограничений и так полно (включая и мои собственные, разве что тут не описаны последние усовершенствования решения на плюсах).
  16  Егоров Илья Валерьевич, 23 января 2020 г. 18:10:39
     Тьфу. *чуть больше мегабайта памяти: с привыканием к Linux API привыкаешь и к байтам в качестве единиц измерения.
  17  Егоров Илья Валерьевич, 23 января 2020 г. 17:49:29
     ...поскольку тут лишь сказано как числа считывать, но нет и намека на алгоритм решения заданной задачи.
  18  Егоров Илья Валерьевич, 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 пункта правил,
  19  Егоров Илья Валерьевич, 23 января 2020 г. 17:27:37
     На CPython — среди решений прошедшие имеются, но оно отчасти сомнительно, поскольку на CPython разница между использованием встроенных функций и велосипеда сильно заметна: велосипед, в силу особенностей интерпретации, медленнее. На PyPy3 с этим гораздо лучше: последнее мое решение использует read_byte из модуля mmap, что потребляет лишь чуть больше килобайта памяти, а по времени спокойно достигает 0.156 сек.
  20  Егоров Илья Валерьевич, 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 с половиной мегов.
 1 2 3

Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!

Красноярский краевой Дворец пионеров, (c)2006 - 2020, E-mail: admin@acmp.ru