У нас есть ИТ олимпиады в моей стране. Обычно они написаны на Java, C или C ++. Я рассчитываю на год или около того, они также включают в себя другие языки, такие как python. Я пытался решить задачу прошлых лет в Python под названием «Письма», и я постоянно терплю неудачу. Задача состоит в том, чтобы написать код, который подсчитывает минимальное количество сдвигов между соседними буквами, чтобы превратить одну строку в другую.
В качестве ввода вы получаете количество букв в одной строке и две строки с одинаковым количеством букв, но в другом порядке. Длина одной строки составляет от 2 до 1 000 000 букв. Есть только заглавные буквы, их можно, но не обязательно, сортировать и повторять.
Вот пример: 7 AABCDDD DDDBCAA
Правильный вывод должен быть 16
В качестве результата вы должны вернуть единственное значение, которое является минимальным количеством смен. Он должен рассчитать выход за 5 секунд. Я сделал это рассчитать правильный вывод, но в более длинных строках (например, 800 000 букв) он начинает замедляться. Самые длинные входы возвращают значение примерно через 30 секунд. Также есть один вход, подсчитывающий 900 000 букв на слово, который вычисляет 30 минут!
По ссылке вы можете найти все входные файлы для тестов: https://oi.edu.pl/l/19oi_ksiazeczka/
Нажмите на это ссылка на скачивание файлов для задания «Письма»: XIX О. И. testy i rozwiązania - zad. LIT (Itap) (3,5 МБ)
Ниже - мой код. Как я могу ускорить его?
# import time
import sys
# start = time.time()
def file_reader():
standard_input=""
try:
data = sys.stdin.readlines()
for line in data:
standard_input+=line
except:
print("An exception occurred")
return standard_input
def mergeSortInversions(arr):
if len(arr) == 1:
return arr, 0
else:
a = arr[:len(arr)//2]
b = arr[len(arr)//2:]
a, ai = mergeSortInversions(a)
b, bi = mergeSortInversions(b)
c = []
i = 0
j = 0
inversions = 0 + ai + bi
while i < len(a) and j < len(b):
if a[i] <= b[j]:
c.append(a[i])
i += 1
else:
c.append(b[j])
j += 1
inversions += (len(a)-i)
c += a[i:]
c += b[j:]
return c, inversions
def literki():
words=(file_reader()).replace("\n", "")
number = int("".join((map(str, ([int(i) for i in list(words) if i.isdigit()])))))
all_letters = [x for x in list(words) if x not in str(number)]
name = all_letters[:number]
anagram = all_letters[number:]
p=[]
index=list(range(len(anagram)))
anagram_dict = {index[i]: anagram[i] for i in range(len(index))}
new_dict = {}
anagram_counts={}
for key, value in anagram_dict.items():
if value in new_dict:
new_dict[value].append(key)
else:
new_dict[value]=[key]
for i in new_dict:
anagram_counts.update({i:new_dict[i]})
for letter in name:
a=anagram_counts[letter]
p.append(a.pop(0))
print(mergeSortInversions(p)[1])
#>>
literki()
# end = time.time()
# print(start-end)
Итак, чтобы объяснить, что он делает по частям: File_reader: просто читает входной файл из стандартного ввода. mergeSortInversions (arr): обычно это сортирует строку, но здесь я хотел, чтобы она возвращала сумму инверсий. Я не настолько умен, чтобы понять это сам, я нашел это в сети, но он делает свою работу. К сожалению, для 1 млн строк это происходит за 10 секунд или около того. В функции "literki": во-первых, я разделил ввод для количества знаков и двух, даже в виде длинных слов в виде списков.
Затем я сделал что-то похожее по функции на массив стеков (не shure если это называется так по-английски sh). в основном я создал словарь с каждой буквой в качестве ключа и индексами этих букв в виде списка значений (если буква встречается более одного раза, значение будет содержать список всех индексов для этой буквы). Последнее, что я сделал перед «медленной вещью», для каждой буквы в переменной «name» я извлек индекс соответствия. До этого момента все операции для каждого ввода занимали около 2 секунд. А теперь две строки, которые генерируют оставшееся время для вычисления результата: - Я добавляю индекс в список p = [] и в то же время выталкиваю его из списка в словаре, чтобы он не прочитал его снова для другой такой же буквы. - Я рассчитываю количество ходов (инверсий) с помощью mergeSortInversions (arr) на основе списка p = [...] и печатаю его как вывод.
Я знаю, что движение снизу идет медленно, но с другой стороны, я пришлось бы создавать списки индексов снизу (чтобы я мог вытолкнуть индекс сверху), но это заняло еще больше времени. Я также пытался преобразовать = [...] с deque, но это также было медленным.