Ребята, со мной творится что-то неладное! Собственно, в чём это выражается? А выражается это в моих тупейших багах при написании кода. Сейчас самая актуальная и самая обидная среди них — выделение малого количества памяти. Смешно же, правда?
Всё началось с Зимней школы этого года, где я долго не мог понять, почему же наше решение даёт WA#29. Оказалось, я перепутал выделение памяти в квадратной динамике (что-то вроде a[5010][10010] вместо a[10010][5010]). Сами понимаете, потерять задачу на такой глупости — очень обидно не только для меня, но и для всеё команды (благо они меня не запинали). Второй случай был на той же школе, ровно с той же самой ошибкой. Правда тестирование немного подзатянулось, поэтому я увидел ужасающий список из Access Violation (или что-то в этом роде) только за 2 минуты до конца контеста. Последние 2 случая были вчера, на 6-ом раунде COCI. У меня было приятнейшее идейное прозрение по 5-ой задаче, но к моему удивлению оно набрало 84 балла. Когда я открыл протокол, то увидел кучу обращений к несуществующей памяти. И что вы думаете? Я опять-таки выделил массив 1000*1000, когда надо было по 10 раз больше на каждое измерение (правда там нужна была линейная оптимизация по памяти, но это заняло у меня 3 минуты).
И вот, стоя сегодня в душе и обдумывая написание этого поста, я с ужасом осознал, что 4-ая задача упала по той же причине. Я вылетел из ванной, дописал двойку, отправил и получил свои заслуженные 80 баллов вместо 20 (хоть это и не спасло меня от лимита по времени на двух тестах). Это было последней каплей моего всего, вот я и решил обратиться к вам за помощью.
Я действительно не знаю, что мне надо сделать, чтобы эти тупобаги исчезли. У меня и раньше бывали с таким проблемы, но они постепенно исчезали — я становился более внимательным что-ли. А вот это вот ну уж совсем непостижимо для меня. Если идейная тупость зависит от опыта решения задач и участия в соревнованиях, то от чего зависит моя тупость?
Мне не страшно, если меня заминусуют или если я пишу какую-то глупость, потому что для меня это критично важно, ибо через неделю уже УОИ, а у меня такая трабла.
На Java такой фигни не бывает, инфа 100%
Конкретно от неверных размеров массивов может спасти
vector<vector<int> >Вектора спасают не всегда.
Чтобы vector всегда выдавал RE при выходе за границы, можно или пользоваться методом at, или переопределить operator[] :
…а при использовании GCC можно просто определить один макрос
_GLIBCXX_DEBUG.http://gcc.gnu.org/onlinedocs/gcc-4.7.2/libstdc++/manual/manual/bk01pt03ch17s03.html
Я мечтаю о подобном макросе для plain-массивов. Вот умеет же Delphi проверять подобное. И valgrind вроде умеет. Я поэтому долгое время писал TopCoder в Borland C++ Builder-е — у него есть режим Code Guard, который в рантайме проверяет все что можно.
На самом деле такая библиотека есть для GCC, называется Mudflap (
-fmudflap -lmudflap). Ловит, например, такие ошибки:Однако эта библиотека, увы, склонна давать ложные срабатывания.
При таком переопределении оператора обращение к элементу за O(size) будет происходить :) (Извините за некропостинг, просто тема актуальная))
Почему?
vector<T>::operator[]иvector<T>::size()оба работают за O(1).Странно... Всю жизнь считал, что вектор умеет считать размер только за O(size). Спасибо за инфу!
Уже сказали, что O(1). Можно даже уточнить, изнутри v.size() устроен так:
Поэтому в частности
быстрее, чем
P.S. Еще быстрее вот этот код:
Мне помогает такое: когда уже кажется, что задача написана и надо посылать, вместо посылки посидеть ещё минут пять и перечитать весь код. Надо натренировать себя за эти пять минут просмотреть (и не один раз) все, казалось бы, наименее значительные места, как-то: эти самые размеры массивов, индексы, использование именно тех переменных, что надо и т.п.
Для избежания завалов на размерах массивов можно ещё вначале определять все ограничения как именованные константы, и потом использовать только их. Ну и ещё хороший, но дорогой по времени приём — позвать товарища по команде и рассказать ему, как работает код.
хорошим способом является выделять не массив на maxN памяти, а динамически выделять (std::vector) ровно n памяти. Тогда решение не будет работать и на маленьких тестах (скорее всего) + если запустить в режиме debug, то будет выполняться проверка того, что индекс попадает в границы [0, size)
Вектора довольно временеёмкие и далеко не всегда удобные. Мне кажется, что речь не о конкретном баге с выделением памяти, а о банальных ошибках вообще.
По времени они почти никогда не мешают. За исключением случаев, когда нужно что-то упихнуть в TL.
"Вектора довольно временеёмкие и далеко не всегда удобные" — категорически не согласен, разве что если вы не пишите какую-нибудь 6-ти мерную динамику. У векторов медленная переаллокация, но если сразу заресайзить как надо, разницы нет.
Разница с массивом всё-таки есть, но очень маленькая (на практике незаметна).
Приведу другой пример. У нас есть разреженный ориентированный граф. У каждой вершины степень ровно два.
Первый способ хранить граф: список ребер.
Второй способ хранить граф: массив векторов, у каждого вектора сделали
.reserve(2)Результаты тестирования: у меня на компе вектор в ~7.5 раз медленней для графов от 106 до 107 вершин. По ссылке можно посмотреть, как я тестил.
UPD: Для степени вершины 1 получаем разницу в ~10 раз.
А массив [N][2] нельзя взять?
Можно :-) Я конкретизировал задачу, чтобы проще было тестировать, сравнивать время работы.
На самом деле имеется в виду ситуация, с которой все мы сталкивались на практике: дан произвольный орграф из 106 вершин и 2·106 ребер.
Ну тут же не в векторах проблема, а в способе хранения, http://pastie.org/private/enhuosaruijat5aavzefua так тоже быстро работать будет.
То есть логично, что выделение 10^6 кусков памяти в куче, а затем рандомный доступ к ним, будет медленнее :)
Да, ты прав, я не о том, что вектор устроен не оптимально.
Мой пример вот о чем. Есть два часто используемых способа хранить граф — "массив векторов" и "список ребер". И иногда люди сперва пишут "массив векторов" и получают TL, а потом "переписал без векторов, зашло".
Тут уж выбор ваш.
Если вы хотите автоматически избавиться от таких багов, используйте Java или вектора, научитесь писать оптимально. Это также помогает избавиться от других багов быстрее.
Если вы хотите быстро работающий код, нужно научиться не делать таких багов, а если уж сделали, не забывать их проверять, когда перечитываете код.
Просто не едь на УОИ.
Даже если я не поеду на УОИ, вряд ли это как-то повлияет на количество багов в коде.
P.S. А нетушки вам :Р
УФМЛ негодует :)
А если сгенерить рандомный макс-тест и проверить, что не падает по RE и что при увеличении размера массива в 2-3 раза, ответ не изменится? Мне вроде помогает :-)
Джедайство в том, чтоб после того, как увеличение размера массива привело к изменению ответа, показать, что на самом деле старый ответ был правильным, и надо отправлять без увеличения.
А по теме поста — правильно было указано ниже. На УОИ времени должно быть более чем достаточно даже для того, чтобы проверить "список ошибок". И это довольно неплохая идея.
Говорят, есть такой метод — решать, решать, еще решать, писать соревнования, после соревнований видеть у себя такие ошибки и думать "я идиот, как можно делать такие глупости, больше никогда не буду", снова решать, решать, писать очередные соревнования, снова допускать на них аналогичные ошибки и думать примерно то же, что и в предыдущем случае... Идея базируется на 2 предположениях:
1) Не ошибается только тот, кто ничего не делает. 2) Мы учимся на своих ошибках.
Спасибо огромное, это, пожалуй, именно то, что я хотел услышать в ответ. Я тоже думал об этих двух пунктах, они у меня постоянно в голове вертятся теперь, но мне казалось, что такая банальщина — это уж слишком. Что ж, буду 1)делать и 2)учиться. (:
У меня на NEERC был баг: локальная и глобальная переменная c одним и тем же именем s, но разным смыслом. Почему-то это давало далекий ВА, и поиск отнял кучу времени. Не уверен на 100%, но вроде мы таки сдали задачу, иначе я бы повесился. Выход в такой ситуации не в том, чтобы перечитывать код, а в том, чтобы уменьшить вероятность подобного рода ошибок. В данном примере правильнее приучить себя давать более осмысленные имена переменным, чем перечитывать сто раз. Каждый раз когда делаешь цикл, должна проходить проверка на невыход за границу, с опытом это происходит где-то в спинном мозге, без участия головного и без переключения на это внимания. Кроме того считаю правильным делать массивы с запасом. n <= 100 ? тогда пусть будет 107, 10^5? тогда (1 << 17). Ну и для борьбы с любыми багами описками полезнее писать с большей концентрацией, не торопясь настолько что допускаешь банальные ошибки на уровне описок.
Можно еще попробовать записывать все ошибки в список и перед сабмитом проверять их по списку. На IOI-style очень помогает.
Пробовал и такое когда-то делать — получился довольно внушительный список + не ясно толком, в каком порядке их лучше записывать, ибо всё время клинит на разных вещах. А проверять по такому громоздкому списку зачастую неудобно. Но я всё равно попробую ещё раз (:
А еще, есть клевый метод. Решать задачки на тимусе, или на CF (не во время контестов) и... не тестить у себя на компе. В качестве большего хардкора можно и не компилировать. Так можно неплохо приспособиться почти всегда писать с первого раза на АС.
Следующий level после "не компилить" — писать код с закрытыми глазами. Потом есть еще один — не читать условие (только название задачи и пример)... Всем удачи :-)
Вот вы смеётесь, а мы в Харькове в конце одного из контестов, когда ничего уже не могли решить поспорили с сокомандником, что я напишу код с выключенным монитором. У меня конечно не получилось, но это реальный случай. Я буду практиковаться и скоро смогу.
Т.е., все те, кто переходит к уровню "не читать условие" до того, как одолел уровень "писать с закрытыми глазами" — читеры и проходят не в том порядке?:)
А что делать если эти все level'ы идут в обратном порядке?
Быть Бенджамином Баттоном, радоваться жизни