[Из песочницы] Как я олимпиаду на Java писал или почему лучше не пользоваться Scanner

Вчера завершился Региональный этап Всероссийской олимпиады школьников. Я участвовал в нем и выбрал для этого язык Java. Основной причиной, почему я решил писать олимпиаду именно на Java заключался в том, что на тот момент я довольно хорошо ее знал и понимал то, как в ней реализовано большинство основных структур данных и функций. Также IntellijIDEA очень сильно способствовала плодотворному кодингу, в ситуациях, когда время является решающим фактором. Да, среды разработки от JetBrains есть и для многих других языков, но среди этих языков нет тех, что обычно используются в спортивном программировании, не считая Python, но использовать здесь его я побаивался из-за того, что этот язык известен прожорливостью.

Однако наш друг, носящий имя индонезийского острова, оказался в некоторых ситуациях еще медленнее, чем прожорливый змей.
Не буду сильно вникать в условия задачи, в решении которой я столкнулся с тем, что программа не успевает справится с задачей за предоставленное время, но отмечу один факт: то решение, которое я написал, являлось эталонным (то есть судьи в пакете с тестами предоставили идентичное решение, но на C), не имело бесконечных циклов и прочего, а его сложность была O(n).

При ограничениях, что n <= 20000, а для работы программы доступна одна секунда, встал вопрос о том, кто же съел время.

И по итогу можно с точностью сказать, что виновником являлся Scanner и его функция nextInt().

А теперь более подробно разберемся с тем, как же эта функция работает.

Сама функция состоит всего из одной строчки return nextInt(defaultRadix);.
А вот то, что творится уже внутри этой функции нам гораздо интереснее.

Первым делом идет проверка if ((typeCache != null) && (typeCache instanceof Integer)
&& this.radix == radix) и здесь очень важно понять, чем же является typeCache и откуда он берется. И тут все вполне просто. Он является ничем иным, как строкой нашей консоли, записанной в форме Object и если этот объект (читать как строка, которую мы ввели) является инстансом Integer, то Scanner делает вывод о том, что введенная строка это и есть искомое число и возвращает его.
Тут все хорошо и сложность этой операции О(1). Отсюда можно заключить, что вводя в строчку только одно число мы практически не тратим время на преобразование ввода в число.
Значит едем дальше.

А вот тут-то и появляется виновник торжества.

Если в строке, которую получил Scanner не int или же если там несколько таковых, то вызывается вот такая строка кода:

String s = next(integerPattern());

А под ней скрыто вот что:

public String next(Pattern pattern) {
        ensureOpen();
        if (pattern == null)
            throw new NullPointerException();

        // Did we already find this pattern?
        if (hasNextPattern == pattern)
            return getCachedResult();
        clearCaches();

        // Search for the pattern
        while (true) {
            String token = getCompleteTokenInBuffer(pattern);
            if (token != null) {
                matchValid = true;
                skipped = false;
                return token;
            }
            if (needInput)
                readInput();
            else
                throwFor();
        }
    }

До этого я не видел смысла вставлять полный код, но теперь, когда мы дошли до сути, думаю самое время разобраться подробно.

Первые три строчки это просто защита от дурака.

А дальше, как нам подсказывают комментарии тех, кто писал этот код идет проверка «а мы случаем не нашли уже такой паттерн?», но в нашем случае эта проверка всегда будет возвращать ложь, поскольку мы на прошлом этапе уже проверили, что полученная нами строка не int.

И что мы видим в конце? Понимая, что быстрых способов поиска больше нет, Scanner сдается и запускает бесконечный цикл который завершится только, если перебором будет найдено что-то, что нам подходит.

А какая у нас сложность у такого перебора? Там вроде бы используется конечно метод двух указателей или что-то на него похожее, но это в любом случае не спасает от множества проверок.

Можете меня поправить, но я вижу там О(n^2), поскольку иначе я не могу объяснить куда могло уйти столько времени.

Итог: в случае, когда вам нужно, чтобы программа действительно быстро считала целые числа из консоли, не доверяйте это делоScanner.nextInt(). Даже банальное Scanner.nextLine и разбиение String в String[] и превращение каждого из членов данного массива в int окажется значительно быстрее.

Let's block ads! (Why?)