Забавный баг с переполнением int в C++

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

Я прохожу один отличный курс по алгоритмам и структурам данных. Формат курса — как в coursera. Есть всё: теоретические задачи, задачи на имплементацию стандартных алгоритмов, хорошие видео-лекции, а также тесты.

После лекции, посвящённой сортировке слиянием, меня ждала довольно интересная задача. Позволю процитировать текст задачи, надеюсь, никто не будет против.

Первая строка ввода содержит число n (1 ≤ n ≤ 100000), вторая — массив A[1…n], содержащий натуральные числа, не превосходящих 1000000000. Необходимо посчитать число пар индексов 1 ≤ i < j ≤ n, для которых A[i]>A[j].

Грубо говоря, требуется найти количество инверсий в массиве. Наивная реализация крайне проста. Сравниваем все пары чисел массива, считаем количество инверсий. А-ля, так:

 int counter = 0;
 
 for (int i = 0; i < n; i++) {
   for (int j = i + 1; j < n; j++) {
     if (A[i] > A[j]) {
        counter++;
     }   
   }
 }

 cout << counter << endl;

Этот код, наверное, хорош. Он понятен любому. Даже джуниору. Но есть одна проблема. У такой имплементации алгоритма временная асимптотика O(n*n).

Естественно, в курсе, посвящённом алгоритмам и структурам данных такой код не прошёл (провален тест по времени). Нужен алгоритм, работающий хотя бы за O(n * log(n)).

Так как я только что прошёл лекцию по сортировке с помощью слияния, то, подумал, что она тут как-то причастна. И правда: существует стандартный алгоритм нахождения числа инверсий в массиве за O(n * log(n)).

Не долго думая, я нашёл описание алгоритма и реализовал его на C++. Закидываю код на сайт для автоматической проверки — код падает. Неверное решение на 6-й набор данных.

В себе я не сомневаюсь, а поэтому сразу подумал, что ошибка где-то у меня в коде. Однако это совершенно не страшно: ведь у меня уже была в кармане наивная реализация задачи, а значит я смогу довольно быстро найти проблему.

Пишу простенький генератор, который генерирует случайные массивы. Для каждого из них считаю два раза число инверсий: с помощью наивного алгоритма и с помощью алгоритма с применением сортировки слиянием.

Запускаю 1000 итераций, ухожу пить чай. Прихожу — вижу, что все тесты успешно прошли. Вот тут я уже озадачился: в наивной реализации ошибиться сложно, а тут получается, что я ещё сделал ошибку и в нормальной реализации.

Пошёл гуглить, искать уже существующие реализации алгоритма. Видимо, задача эта крайне распространённая на курсах по алгоритмам. Я нашёл, как минимум, 5 разных имплементаций поиска числа инверсий в массиве. Примечательно, что все они падали на 6-м наборе данных.

Я уже подумал, что ошибка в тесте. Пишу создателям курса, узнаю, что ошибка на моей стороне: уже есть люди, которые решили эту задачу.

Вот тут-то я уже и озадачился, что делать. Наивная реализация крайне простая, чтобы там допустить ошибку. Входных данных теста у меня нет: тоже не смогу, получается, отследить ошибку.

И тут меня осенило: может в России кто-то пишет что-то на этот счёт (раньше я искал информацию только в eng). Оказывается, что и в РУ есть кое какая информация.

Я совсем случайно попал на блог к какому-то разработчику, кто рассказывает 20 минут о том, как реализовать этот алгоритм на Руби. Я, от нечего делать, смотрю видео. Смотрю, у этого человека есть интересный тестовый набор данных: как раз таки массив из ста тысяч элементов. Ну, и ответ, конечно же, есть.

Я, не долго думая, запускаю этот тест. И, что же я вижу? Отрицательный ответ (это, очевидно, абсурд). И тут я понимаю всю свою глупость. Я считал количество инверсий и складывал результат в int.

Почему это глупость? Максимальное число инверсий достигает при входном массиве, отсортированном по убыванию. Число инверсий в этом случае равно 100000*99999/2 = 4,999,950,000 — почти 5 миллиардов. А в int у нас влезает 2,147,483,647. Вот такая вот Беда.

Моя ошибка была в том, что я сразу не подумал о том, какой может получится результат. Я даже не задумывался о том, что тут возможно переполнение. Ведь на данных, на которых я тестировал, таких проблем не было даже близко. Как говорится, нужно тестировать программу на всех возможных входных данных.

Категории: Программирование

Метки: