Python-сообщество

условие задачи:

Число инверсий

Имя входного файла: inversions.in
Имя выходного файла: inversions.out
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

Инверсией в последовательности чисел A называется такая ситуация, когда i < j, а Ai > Aj.
Дан массив целых чисел. Ваша задача — подсчитать число инверсий в нем.
Подсказка: чтобы сделать это быстрее, можно воспользоваться модификацией сортировки слиянием.

Формат входного файла
В первой строке входного файла содержится число n (1<n<100 000) — число элементов в массиве. Во второй строке находятся n целых чисел, по модулю не превосходящих 109.

Формат выходного файла
В выходной файл надо вывести число инверсий в массиве.

Пример
inversions.in
inversions.out
10
1 8 2 1 4 7 3 2 3 6

17
моё решение задачи на github:
https://github.com/fizitra/OpenEdu_ITMO_Algorithms/blob/master/Week2_Comarisons_sort/week2_problem3_inversions.py

однако есть проблема: превышение предела времени работы программы на 7 тесте
https://courses.openedu.ru/courses/course-v1:ITMOUniversity+PADS+fall_2016/courseware/a59fe37ef4744951ab33fa6278dd20f9/70393a1a9f654ce88dfec1291933e75e/

Прошу помощи. Как еще можно ускорить код на питоне?!

Отредактировано fizitra (Сен. 30, 2016 23:57:26)

Проблема решена.
Если кому интересно, то вычисление длины списка len выполняется за линейное время. Заменил все len на константу в итоге прирост скорости в 18-25 раза.
Поскольку публиковать свои решения в сети пока идет курс не этично, окончательного варианта решения здесь не привожу, если кому очень нужно, найдет сам.

Отредактировано fizitra (Окт. 1, 2016 19:51:47)

fizitra
у всех стандартных типов данных len берется за O(1)
срезы медленные, доступ к глобальным переменным медленный, создание нового list и append к нему медленные

sander
fizitraу всех стандартных типов данных len берется за O(1)срезы медленные, доступ к глобальным переменным медленный, создание нового list и append к нему медленные

Да моя оплошность, пожалуй вы правы len за О(1) вся проблема была в самих срезах. Правда пока не ясно как, потому что формируемый в коде срез из len(list)//2 остался, и сохраняется какновый list. Этот новый list использовался для нахождения нового значения len(list). В новом варианте алгоритм работает запоминая начальное значение первого len(list), и дальше остальные значения вычисляются как const//2.
Т.е в некотором роде вопрос открыт: в каком месте происходит потеря времени в алгоритме?

fizitra
Подсказка: чтобы сделать это быстрее, можно воспользоваться модификацией сортировки слиянием.

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

Естественно, квадратный вариант будет слишком долгим (когда для каждого элемента перебирается всё справа), но есть линейный вариант (однопроходный), требующий немного дополнительной памяти.

Отредактировано py.user.next (Окт. 2, 2016 04:38:45)