Увеличить скорость кода

@Arseniy_Ch · Регистрация: 29.01.2022

Студворк — интернет-сервис помощи студентам

Есть вот такой код:

Python
1
2
3
4
5
6
7
8
9
x = input()
line = input()
count = 0
n = -1
while '><' in line:
    n = line.count('><')
    line = line.replace('><', '<>')
    count += n
print(count)

В некоторых тестах он не проходит по времени, как его ускорить?
Заранее всем спасибо!

@Gdez · 29.01.2023, 00:13

Arseniy_Ch,

В некоторых тестах он не проходит по времени, как его ускорить?

Выложить полное условие задачи…

@Red white socks · 29.01.2023, 00:50

Python
1
2
3
4
line = input()
n = line.count('<')
s = sum(i for i, v in enumerate(line) if v == '<')
print(s - n * (n-1) // 2)

Рыжий Лис · 29.01.2023, 08:19

Дай, угадаю: нужно посчитать сколько замен было произведено?

Добавлено через 2 минуты
Ну раза в два можно увеличить скорость, если не пользоваться str.count

@Red white socks · 29.01.2023, 08:36

Рыжий Лис, приведенный выше код уменьшает сложность алгоритма с квадратичного на линейный. И это вам не какие-то "в 2 раза"

@u235 · 29.01.2023, 08:55

Red white socks, ваш код и код ТС будут выдавать разные результаты, например, на строке '<<<<<<'. Так что нужна изначальная постановка задачи.

@Parramon · 29.01.2023, 08:59

Arseniy_Ch, Первое, что бросилось в глаза - а первая строчка кода, она зачем?

@eaa · 29.01.2023, 09:36

Arseniy_Ch, даю тебе подсказку.
при таком преобразовании количество символов '>' и '<' в строке не изменится.
после преобразования строка будет иметь вид <...<<>>...>

@Red white socks · 29.01.2023, 09:40

Сообщение от u235

Red white socks, ваш код и код ТС будут выдавать разные результаты, например, на строке '<<<<<<'. Так что нужна изначальная постановка задачи

u235, ????

Добавлено через 4 минуты
Ну запустил. Получил в обоих случаях ожидаемые нули. Какой еще "контрпример" будет?

@eaa · 29.01.2023, 09:50

Сообщение от u235

Так что нужна изначальная постановка задачи

тут и так все понятно.

@u235 · 29.01.2023, 10:02

Red white socks, например такой:"<N<N<"

@Red white socks · 29.01.2023, 10:05

u235, что с вашим шаром случилось?
Очевидно же, что в строке только 2 различных символа)

Добавлено через 1 минуту
Но претензия принимается. Ждем подтверждения

@u235 · 29.01.2023, 10:11

Сообщение от Red white socks

Очевидно же, что в строке только 2 различных символа

Для меня это совершенно не очевидно...

@Red white socks · 29.01.2023, 10:32

Сообщение от u235

Для меня это совершенно не очевидно...

Идея остается та же, только в задачу добавляется грязь, совершенно ненужная

@Parramon · 29.01.2023, 13:40

Сообщение от Red white socks

Очевидно же, что в строке только 2 различных символа)

Если было-бы так, то len(line) / 2 решило бы задачу...

@Red white socks · 29.01.2023, 17:54

Сообщение от Parramon

Если было-бы так, то len(line) / 2 решило бы задачу...

Parramon, а вы попробуйте. Тут же все просто

Python
1
2
3
from random import choices
 
line = ''.join(choices('<>', k=20))

И честно посчитайте. И посмотрим - решило бы или нет.

@Parramon · 29.01.2023, 18:46

Red white socks, Я написал "Еслт бы".

Python
1
2
3
4
5
6
7
8
9
10
11
12
line = '><<<<<<<<<<<<<<<<'
count = 0
n = -1
while '><' in line:
    n = line.count('><')
    line = line.replace('><', '<>')
    count += n
print(count)
line = '><<<<<<<<<<<<<<<<'
n = line.count('<')
s = sum(i for i, v in enumerate(line) if v == '<')
print(s - n * (n-1) // 2)

Bash
1
2
16
16

Сорри, сначала не заметил, что строка меняется

Новые блоги и статьи Все статьи Все блоги /
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .
Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .	Фото всей Земли с борта корабля Orion миссии Artemis II kumehtar 04.04.2026 Это первое подобное фото сделанное человеком за 50 лет. Снимок называют новым вариантом легендарной фотографии «The Blue Marble» 1972 года, сделанной с борта корабля «Аполлон-17». Новое фото. . .	Вывод диалогового окна перед закрытием, если документ не проведён Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать программный контроль на предмет проведения документа. . .	Программный контроль заполнения реквизитов табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: 1. Реализовать контроль заполнения реквизита. . .

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	29.01.2023, 08:19
	Дай, угадаю: нужно посчитать сколько замен было произведено? Добавлено через 2 минуты Ну раза в два можно увеличить скорость, если не пользоваться str.count 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	29.01.2023, 08:36
	Рыжий Лис, приведенный выше код уменьшает сложность алгоритма с квадратичного на линейный. И это вам не какие-то "в 2 раза" 1

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,761
	29.01.2023, 08:55
	Red white socks, ваш код и код ТС будут выдавать разные результаты, например, на строке '<<<<<<'. Так что нужна изначальная постановка задачи. 0

@Parramon 740 / 622 / 151 Регистрация: 04.03.2022 Сообщений: 1,272
	29.01.2023, 08:59
	Arseniy_Ch, Первое, что бросилось в глаза - а первая строчка кода, она зачем? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	29.01.2023, 09:36
	Arseniy_Ch, даю тебе подсказку. при таком преобразовании количество символов '>' и '<' в строке не изменится. после преобразования строка будет иметь вид <...<<>>...> 1

@u235 5516 / 2869 / 571 Регистрация: 07.11.2019 Сообщений: 4,761
	29.01.2023, 10:02
	Red white socks, например такой:"<N<N<" 0

@Red white socks 4523 / 1899 / 336 Регистрация: 18.01.2021 Сообщений: 3,489
	29.01.2023, 10:05
	u235, что с вашим шаром случилось? Очевидно же, что в строке только 2 различных символа) Добавлено через 1 минуту Но претензия принимается. Ждем подтверждения 0