|
|
|
|
|
|
|
| 41 Егоров Илья Валерьевич, 21 апреля 2018 г. 0:31:40 |
| Кирилл, вот только как это избавит от сохранения всей строки (без использования ctypes)?
|
|
|
| 42 Генералов Кирилл Витальевич, 20 апреля 2018 г. 12:05:00 |
| Илья, у меня появилась идея. Можно сделать подмассив, как срез, из 5 чисел (3 макс. и 2 мин.) и просто двигать его вправо посимвольно, тем самым ища нужные элементы, не взаимодействуя кучу раз со списком. Ну, к примеру, как ползунок на календаре будет работать, только из 5 ячеек.
|
|
|
| 43 Егоров Илья Валерьевич, 11 апреля 2018 г. 14:56:05 |
| По-хорошему, видимо, не следует на Python сохранять всю строку (иначе упирается в память). На уме пока что 3 варианта: 1) Считывать посимвольно (хранить только 1 символ); 2) Считывать частями (своим буфером); 3) Считывать токенами. Представляю лишь реализацию через ctypes, но пока что TLE на 48
|
|
|
| 44 Генералов Кирилл Витальевич, 10 апреля 2018 г. 18:47:43 |
| Да, Вы не ошиблись, именно .split(). Таким образом, нужно строку чисел посимвольно вбивать в список? Вручную,а не функцией?
|
|
|
| 45 Егоров Илья Валерьевич, 08 апреля 2018 г. 12:17:29 |
| Кирилл, вы наверняка используете split, да? Так вот, по сравнению с просто считыванием всего файла (и дальнейшим использованием регулярок или посимвольной обработки) это сугубо в 2 раза больше потребляет память: как ни как, сначала считали строку, а затем разбили на подстроки, и всё это вынуждено храниться в памяти
|
|
|
| 46 Генералов Кирилл Витальевич, 07 апреля 2018 г. 13:53:55 |
| Админ, что за веселье? :D. Вроде бы Питон и не может испытывать проблем из - за типов (int/int64), тогда почему у меня с 47 теста на 48 память прыгает с 2,5+-мб до 38мб. Что я делаю не так в этой жизни? Спасибо.
|
|
|
| 47 Харченко Кирилл Константинович, 29 марта 2018 г. 21:41:32 |
Одна из самых проблемных задач на сайте. Даже самая оптимизированная программа может не пройти по времени из-за загруженности системы. На личном компьютере результат равняется половины секунды, а здесь ставит 1.03 Но тем не менее, Accepted Ещё одна проблемная - задача №20 - Пилообразная последовательность.
Попробуйте освоить чтение через fread, о котором говорит автор ниже. Зайдёт быстрее чем за десятую долю секунды. А вообще stdio.h + scanf("%d" хватает, чтобы сдать не совсем вплотную к ограничению по времени.
|
|
|
| 48 Егоров Илья Валерьевич, 28 марта 2018 г. 17:34:53 |
| Комментарий к комментарию: Да, не идеальны. Тем не менее, статистика (не пара решений, а целое множество) обычно показывает действительность (колебание в пределах таких-то значений). У меня не одна !сотня! отправлений - ни одного 0.03. И всё оптимизируя да оптимизируя (уже почти некуда, подумываю об ассемблерных вставках), я улучшаю статистику. Раньше у меня, например, почти не было 0.062 - минимум 0.092. Теперь же 0.062 попадается значительно чаще
|
|
|
| 49 Егоров Илья Валерьевич, 28 марта 2018 г. 17:13:11 |
[продолжение] с оптимизацией 9) Если не уверены с выбором компилятора в тестирующей системе, опробуйте Visual C++. Ходят слухи, что он тут и жрёт меньше (доказано), и генерирует более эффективный код (под сомнением) 10) Указатели не панацея, бит'цы тоже. Их использование не ускорит магическим образом вашу программу: помните, что они могут сделать даже хуже; Эти рекомендации также годны для тех, кто не стремится выжать все соки, а у кого всего лишь с корректным алгоритмом не проходит по времени / памяти. Ну и добавочно для таких: 1) Если используете <iostream>, лучше всего отключить синхронизацию и автоматический flush, добавив эти 2 "магические строчки" в начало main: ios_base::sync_with_stdio(false); cin.tie(NULL); На данный момент мой рекорд для данной задачи - 0.062 сек. с 176 Кб потребления памяти при компиляторе Visual C++, но цель, ради которой я продолжаю оптимизацию, - 0.03; P.s. Да, я знаю, что лучшим решением тут считается кротчайшее решение, но мало ли кто тут бродит
Замеры времени на acmp не идеальны, можете попробовать несколько раз сдать одно решение, может повезёт и 0.062 превратится в 0.03.
|
|
|
| 50 Егоров Илья Валерьевич, 28 марта 2018 г. 17:12:47 |
| [продолжение], в собственной реализации парсинга). Причина: есть некий "модуль предсказания переходов", который, если не угадывает путь ветвления, отменяет инструкции, которые он заготовил для своей предсказанной версии, и загружает уже подходящие, на что тратит значительное (относительно) время. Замечание: см. пункт 7 6.1) Вычисление всяких == и т.п. не требует предсказателя (a == b, собственно, то же самое, что !(a ^ b)), так что этим можно воспользоваться для избавления от ветвления 7) Опираясь на пункт 0, замерять время работы после изменений (сугубо раз 7 хотя бы, т.к. из-за ветвления время получается разным: предсказатель то угадывает, то нет). Например, реализовав max через битовые операции, вы можете только ухудшить эффективность программы 7.1) Научитесь изучать получаемый ассемблерный код (хотя б на кол-во инструкций внимание обратите). Достаточно вбить в поисковик "compile explorer". Так вы можете провести достаточно тонкую оптимизацию 8) Вооружитесь const и static. Этим вы поможете компилятору
|
|
|
| 51 Егоров Илья Валерьевич, 28 марта 2018 г. 17:11:40 |
| -Для гиков и не только- Как достичь наилучших результатов по времени и памяти на C++: 0) Тестировать у себя (этак при N = 10^7). Проще всего под unix, используя time 1) Алгоритм за O(n) 2) Достаточно хранить, как проспойлерили ранее, только 5 чисел из последовательности 3) fread/fgets (<stdio.h>) (да, он быстрее всяких getchar) со своим парсингом. Можно и _unlocked/_nolock версию. При этом надо подобрать оптимальный размер буфера (желательно равный 2 в некой степени) 3.1) Знание Великого ASCII поможет в создании быстрого парсинга 4) Реализация своего буферизированного вывода может ухудшить ситуацию, поэтому лучше воспользоваться старым-добрым (f)printf (тот же <stdio.h>) 5) Использовать int и, при необходимости, его аналоги фиксированного размера (int64 и т.п.), но не long long. Помните, что лучше максимум операций производить именно над int, так как меньшие типы в случае арифметических операций всё равно приводятся к int, да и в случае бОльших тоже не так всё радужно 6) Избегать ветвления (например
|
|
|
| 52 Завгородний Михаил Сергеевич, 23 февраля 2018 г. 7:12:37 |
| Хорошая задача. Наконец-то ее решил
|
|
|
| 53 Юсупов Темиржан Нурланович, 11 марта 2017 г. 9:24:24 |
| Библиотека <stdio.h> видимо работает быстрее всех остальных, попробуйте ее
|
|
|
| 54 Давид Нигматуллин, 04 марта 2017 г. 11:15:44 |
48 тест:
1) Замените лонги на инты там, где можно
2) Замените iostream (cin, cout) на stdio.h (scanf, printf)
1 пункт, лонги менять не нужно, так как в С++, long == int, а вот long long и __int64, да, где можно замените на int
|
|
|
| 55 Давид Нигматуллин, 04 марта 2017 г. 11:14:06 |
| Либо можно не менять, используйте scanf, только первой библиотекой должна быть <stdio.h> а не cstdio или bits
|
|
|
| 56 Кирилл Карнаухов, 18 января 2017 г. 7:56:31 |
| У кого падает решение за O(N) на 48 тесте, поменяйте компилятор на MV C++
|
|
|
| 57 Васильев Алексей, 26 ноября 2016 г. 20:56:53 |
48 тест:
1) Замените лонги на инты там, где можно
2) Замените iostream (cin, cout) на stdio.h (scanf, printf)
|
|
|
| 58 Немцев Евгений Владимирович, 19 ноября 2016 г. 23:33:27 |
| Почему решение за O(N) валится с TL48 ? Это точно корректный тест??
|
|
|
| 59 Слуцкий Алексей, 10 апреля 2016 г. 7:39:25 |
| Ограничения должны быть N < 1e7, чтобы сортировка не проходила, иначе эта задача вообще ничему не учит.
|
|
|
| 60 Жавохир Мараимов, 03 января 2016 г. 6:47:22 |
не с первого решал но оказался изи!!! Сначала найдете мах1, мах2, мах3, мин1, мин2;
потом max((max1*max2*max3),(min1*min2*max1));
|
|
|
Чтобы оставить сообщение необходимо зарегистрироваться и авторизоваться!
| | | |
