Как оптимизировать программу по памяти?

Question

Решаю задачу для контеста Яндекса, вылетает на одном тесте, пишет Memory Limited. Пытался делать решение через списки, но так получается что программа тратит еще больше памяти.

conf_num = int(input())

conf_dict = {}
conf_list = []
m = 1

for i in range(conf_num):
    conf = input()
    conf_list.append(conf)
    
    for s in range(len(conf) - 2):
        if conf[s:s + 3] not in conf_dict:
            conf_dict[conf[s:s + 3]] = m
            m += 1


    
conf_table = [[0] * len(conf_dict) for i in range(len(conf_dict))]

pairs_list = []
edge_num = 0

for i in conf_list:
    for s in range(len(i) - 3):
        conf_table[conf_dict[i[s:s + 3]] - 1][conf_dict[i[s + 1:s + 4]] - 1] += 1
        
        if [i[s:s + 3], i[s + 1:s + 4]] not in pairs_list:
            pairs_list.append([i[s:s + 3], i[s + 1:s + 4]])
        
        if conf_table[conf_dict[i[s:s + 3]] - 1][conf_dict[i[s + 1:s + 4]] - 1] == 1:
            edge_num += 1

# ВЫВОД

print(len(conf_dict)) # Кол-во вершин графа

print(edge_num) # Кол-во ребер графа

for i in pairs_list:
    print(f'{i[0]} {i[1]} {conf_table[conf_dict[i[0]] - 1][conf_dict[i[1]] - 1]}')

Answer 1

Заметьте, что существует максимум 456976=26^4 рёбер, поскольку каждое ребро соответствует комбинации S[i]S[i+1]S[i+2]S[i+3] четырех латинских символов, и при использовании ребра в качестве ключа, памяти требуется всего несколько мегабайт (можно ещё уменьшить, сопоставив последовательности символов число в указанном диапазоне, но и так пройти должно)

Можно сделать всего один проход по строкам, беря 4 символа за раз

from collections import Counter

s = 'abcdcdcdabcd'

e = Counter()
for i in range(len(s) - 3):
    t = s[i:i+4]
    e[t] += 1

for item in e:
    print(item[:3], item[1:], e[item])

abc bcd 2
bcd cdc 1
cdc dcd 2
dcd cdc 1
dcd cda 1
cda dab 1
dab abc 1

БЛОГ НА HUSL

Как оптимизировать программу по памяти?

Ответы (1 шт):