Оптимизация решения задачи python
Решил задачу, но необходимо немного оптимизировать время работы. Подскажите, как это возможно сделать?
- рост орков, стоящих в строю (1 ⩽ ⩽ n , a i n,a i ⩽ ⩽ 1 0 5 10 5 ). Во второй строке даны m m целых чисел x i x i
- предполагаемый рост Гримморхуса (1 ⩽ ⩽ m , x i m,x i ⩽ ⩽ 1 0 5 10 5 ).
Если пройти простым алгоритмом и посмотреть, когда обновляется максимум целевой функции для каждого значения роста, то это происходит только после того, как в шеренге встретилось это самое значение. Целевая функция для других значений роста тоже изменяется, однако только в меньшую сторону. Если в шеренге встретили значение 2, то для роста 2 первый множитель целевой функции увеличился, а второй не изменился. А для роста 3 или любого, отличного от 2, первый множитель не изменился, а вот второй уменьшился.
Таким образом, в каждой точке шеренги достаточно делать проверку целевой функции только один раз — для текущего значения, и для обработки всех данных требуется только один линейный проход.
А для быстрого расчета целевой функции нужно знать количество текущих значений слева — это накапливается в словаре currcnt, и количество отличных от текущего значений справа — это легко найти, зная длину куска справа, и разность количества текущего значения во всем списке (overcnt) и слева. Предобработка линейная, обеспечивается O(1) для каждого вычисления целевой функции.
Итого получается линейный алгоритм, работает не более 0.15 с при n,m<=100000
Представляю Вам одно из возможных решений по оптимизации Вашего алгоритма:
Предложенный оптимизированный код использует библиотеку NumPy для создания массивов, которые работают быстрее и используют меньше памяти, чем обычные списки в Python .
Было использовано булевую индексацию, чтобы найти элементы, которые не равны или равны определенному значению. Позже использовалась функция len() для подсчета количества таких элементов.
Далее были задействованы генераторы списков для оптимизации кода. Вместо того, чтобы создавать отдельный список для результата, формируется массив нулей, который в последствии заполняется значениями, используя цикл и функцию enumerate() , которая позволяет перебирать значения массива вместе с их индексами.
Также была изменена логика цикла. Вместо того, чтобы проходить по каждому элементу списка row для каждого элемента списка heights , мы проходим по каждому элементу списка row только один раз и вычисляем максимальное значение для каждого элемента списка heights .
Метод astype() добавлен для преобразования элементов массива в строковые значения.
Так же провел небольшой эксперимент с одинаковыми входящими данными. По его результат, выполнение алгоритма удалось ускорить более чем в 3 раза .
Результат Вашего алгоритма:
Результат оптимизированого алгоритма:
По просьбе автора доработал алгоритм, без использования Numpy . Вышло с минимальным, но действенным вмешательством в оригинальный алгоритм. Этот код использует словарь heights_dict для сохранения значений maxCount для каждой высоты, поэтому выполнение кода становится быстрее. Как результат новый оптимизированный алгоритм исполняется более чем в 135 раз быстрее , чем исходный. И в 38 раз быстрее , чем первый вариант оптимизации.
Новый адаптированный алгоритм без использования NumPy :
Результат оптимизированого алгоритма без NumPy :
Есть еще один вариант, это последняя модификация, где убраны повторяющиеся вычисления длин с помощью методов массива array[index:] и array[:index] , которые позволяют находить подмассивы с помощью срезов и тем самым еще больше ускоряют выполнение данного кода.
Задача «Частотный анализ»
Дан текст: в первой строке записано количество строк в тексте, а сами строки. Выведите все слова, встречающиеся в тексте, по одному на одну строку. Слова должны быть отсортированы по убыванию их количества появления в тексте, а при одинаковой появлении появления — в лексикографическом порядке.
Указание. После, как вы создадите словарь всех слов, вам захочется отсортировать его по частоте встречаемости слова. Желаемого можно добиться, если создать список элементов которого будут кортежи из двух элементов: частота встречаемости слова и само слово. Например, [(2, ‘hi’), (1, ‘what’), (3, ‘is’)] . Тогда стандартная сортировка будет сортировать список кортежей, при этом кортежи сравниваются по первому элементу, а если они равны — то по второму. Это почти то, что требуется в задаче.
[ Сборник задач ]
Тема 4. Работа со списками
Список – последовательность элементов, объединенных в один контейнер. Главная особенность – они изменяемы.
Элементы списка индексируются, состоят в основном из однотипных данных, перебираются, сохраняют порядок.
Для решения заданий необходимо повторить свойства и методы списков.
Читайте также
1. Перечислите характеристики типа данных «список», которые вы знаете.
2. Как проверить наличие элемента в списке?
Есть 2 очевидных способа:
1. При помощи конструкции in:
Пример – IDE
lst = [1, 2, 3, 14, 33, 1, 1]
if 1 in lst:
____print(‘Есть’)
Результат:
Есть
2. При помощи метода count:
Пример – IDE
lst = [1, 2, 3, 14, 33, 1, 1]
if lst.count(5):
____print(‘Есть’)
else:
____print(‘Нет’)
Результат:
Нет
3. Чем отличаются методы append() и extend()?
Метод append() добавляет в конец текущего списка новый элемент.
Метод extend() добавляет в конец текущего списка новые элементы в распакованном виде.
Посмотрим отличия на примере.
Пример – IDE
lst = [1, 2, 3, 14, 33, 1, 1]
lst.extend(‘Добавка’)
print(lst)
Результат:
[1, 2, 3, 14, 33, 1, 1, ‘Д’, ‘о’, ‘б’, ‘а’, ‘в’, ‘к’, ‘а’]
Пример – IDE
lst = [1, 2, 3, 14, 33, 1, 1]
lst.append(‘Добавка’)
print(lst)
Результат:
[1, 2, 3, 14, 33, 1, 1, ‘Добавка’]
4. Какие параметры можно передавать при срезах списков?
Для срезов можно пользоваться функцией slice() или специальным сокращением, куда входит 3 параметра: начало среза (по умолчанию – первый элемент), конец среза (конечный член списка, не включая его), шаг (по умолчанию – 1, т.е. выбираем все элементы без пропусков).
Пример – IDE
h = [1, 2, 3, 14, 33, 1, 9]
print(h[slice(2, 6, 2)])
Результат:
[3, 33]
Т.е. создаем новый список начиная с элемента с индексом 2 (в нашем случае это цифра 3) вплоть до 6 элемента (не включая его) с шагом 2 (пропускаем каждое второе значение).
Часть или все параметры можно опускать в специальных сокращениях.
Пример – IDE
h = [1, 2, 3, 14, 33, 1, 9]
print(h[2:6:2])
print(h[::2])
Результат:
[3, 33]
[1, 3, 33, 9]
5*. Что произойдет со списком lst1 в первом и втором случаях? Поясните результат.
Случай 1 – IDE
lst1 = [1, 2, 3, 14, 33, 1, 9]
lst2 = [1, 2, 3, 14, 33, 1, 9]
lst2.append(789)
Случай 2 – IDE
lst1 = [1, 2, 3, 14, 33, 1, 9]
lst2 = lst1
lst2.append(789)
В первом случае список lst1 не изменится, во втором – в нем появится новый элемент 789.
Первый пример показывает создание двух разных списков, хоть и являющихся равными. Тем не менее они занимают разные области в памяти. И изменение одного из списков не вызывает аналогичного поведения в другом.
Во втором примере обе переменные ссылаются на один список, поэтому модификация любой из них отразится на другой.
# Тест случая 1
lst1 = [1, 2, 3, 14, 33, 1, 9]
lst2 = [1, 2, 3, 14, 33, 1, 9]
lst2.append(789)
print(lst1, lst2, sep=’\n’)
Результат:
[1, 2, 3, 14, 33, 1, 9]
[1, 2, 3, 14, 33, 1, 9, 789]
# Тест случая 2
lst1 = [1, 2, 3, 14, 33, 1, 9]
lst2 = lst1
lst1.append(789)
print(lst1, lst2, sep=’\n’)
Результат:
[1, 2, 3, 14, 33, 1, 9, 789]
[1, 2, 3, 14, 33, 1, 9, 789]
Есть 3 часто применяемых варианта:
1. При помощи функции list():
Пример – IDE
text = ‘Строка’
print(list(text))
Результат:
[‘С’, ‘т’, ‘р’, ‘о’, ‘к’, ‘а’]
2. При помощи цикла for:
Пример – IDE
text = ‘Строка’
new_list = []
for i in text:
____new_list.append(i)
print(new_list)
Результат:
[‘С’, ‘т’, ‘р’, ‘о’, ‘к’, ‘а’]
3. При помощи генератора списков:
Пример – IDE
text = ‘Строка’
new_list = [i for i in text]
print(new_list)
Задачи по Python для начинающих от Tproger и GeekBrains
Вместе с факультетом Python-разработки GeekUniversity собрали для вас несколько простых задач по Python для обучения и тренировки. Их можно решать в любом порядке.
Обратите внимание, что у любой задачи по программированию может быть несколько способов решения. Чтобы посмотреть добавленный нами вариант решения, кликните по соответствующей кнопке. Все приведённые варианты написаны на Python 3.
Задача 1
Есть список a = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89] .
Выведите все элементы, которые меньше 5 .
Самый простой вариант, который первым приходит на ум — использовать цикл for :
Также можно воспользоваться функцией filter , которая фильтрует элементы согласно заданному условию:
И, вероятно, наиболее предпочтительный вариант решения этой задачи — списковое включение:
print([elem for elem in a if elem < 5])
Задача 2
a = [1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89] ;
b = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13] .
Нужно вернуть список, который состоит из элементов, общих для этих двух списков.
Можем воспользоваться функцией filter :
Или списковым включением:
result = [elem for elem in a if elem in b]
А можно привести оба списка к множествам и найти их пересечение:
result = list(set(a) & set(b))
Однако в таком случае каждый элемент встретится в результирующем списке лишь один раз, т.к. множество поддерживает уникальность входящих в него элементов. Первые два решения (с фильтрацией) оставят все дубли на своих местах.
Задача 3
Отсортируйте словарь по значению в порядке возрастания и убывания.
Импортируем нужный модуль и объявляем словарь:
Сортируем в порядке возрастания:
И в порядке убывания:
Задача 4
Напишите программу для слияния нескольких словарей в один.
Допустим, вот наши словари:
Объединить их можно вот так:
А можно с помощью «звёздочного» синтаксиса:
О звёздочном синтаксисе можно прочитать в нашей статье.
Задача 5
Найдите три ключа с самыми высокими значениями в словаре my_dict = <'a':500, 'b':5874, 'c': 560,'d':400, 'e':5874, 'f': 20>.
Можно воспользоваться функцией sorted :
Аналогичный результат можно получить с помощью функции nlargest из модуля heapq :
Задача 6
Напишите код, который переводит целое число в строку, при том что его можно применить в любой системе счисления.
Второй аргумент функции int отвечает за указание основания системы счисления:
Задача 7
Нужно вывести первые n строк треугольника Паскаля. В этом треугольнике на вершине и по бокам стоят единицы, а каждое число внутри равно сумме двух расположенных над ним чисел.
Задача 8
Напишите проверку на то, является ли строка палиндромом. Палиндром — это слово или фраза, которые одинаково читаются слева направо и справа налево.
Тут всё просто, достаточно сравнить строку с её обратной версией, для чего можно использовать встроенную функцию reversed:
Того же эффекта можно добиться с помощью срезов:
Задача 9
Сделайте так, чтобы число секунд отображалось в виде дни:часы:минуты:секунды .
Задача 10
Вы принимаете от пользователя последовательность чисел, разделённых запятой. Составьте список и кортеж с этими числами.
Задача 11
Выведите первый и последний элемент списка.
Задача 12
Напишите программу, которая принимает имя файла и выводит его расширение. Если расширение у файла определить невозможно, выбросите исключение.
Задача 13
При заданном целом числе n посчитайте n + nn + nnn.
Задача 14
Напишите программу, которая выводит чётные числа из заданного списка и останавливается, если встречает число 237.
Задача 15
Напишите программу, которая принимает два списка и выводит все элементы первого, которых нет во втором.
Задача 16
Выведите список файлов в указанной директории.
Задача 17
Сложите цифры целого числа.
Задача 18
Посчитайте, сколько раз символ встречается в строке.
Задача 19
Поменяйте значения переменных местами.
Можно написать монструозную конструкцию в стиле языка C:
Но в Python есть более удобный способ для решения этой задачи:
Задача 20
С помощью анонимной функции извлеките из списка числа, делимые на 15.
Задача 21
Нужно проверить, все ли числа в последовательности уникальны.
Задача 22
Напишите программу, которая принимает текст и выводит два слова: наиболее часто встречающееся и самое длинное.
Хотите вырасти от новичка до профессионала? Факультет Python-разработки GeekUniversity даёт год опыта для вашего резюме. Обучайтесь на практических заданиях, по-настоящему освойте Python и станьте ближе к профессии мечты.
Узнать больше