Оптимизация программы

@bulk_bulk · Регистрация: 15.02.2020

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

Добрый день, поставлена следующая задача:

Выписать все слова, которые являются анаграммами друг для друга, например «замок» и «мазок». Проверка слов должна быть регистронезависимой. Слова, для которых анаграммой является только оно само, выписывать не нужно, даже если это слово встречается в тексте в разном регистре.
Формат ввода
В первой строке идёт целое число n (1 ≤ n ≤ 100 000), количество исходных слов.

Далее следует n слов, по одному слову в строке, слова могут идти в разном регистре!

Формат вывода
В одной строке должны идти слова, которые являются анаграммами друг для друга, в нижнем регистре, через пробел. Порядок слов — лексикографический (как в словаре). Порядок строк так же лексикографический.

Пример
Ввод
11
окорок
петлей
Плетей
рококо
теплей
Тишь
ТОМНО
тонко
тонок
тоном
шить
Вывод
окорок рококо
петлей плетей теплей
тишь шить
томно тоном
тонко тонок

Имеется следующий полностью рабочий код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
same = []
for i in range(n):
    a = input()
    strings.append(a.lower())
for i in range(len(strings)):
    same1 = []
    for j in range(len(strings)):
        if set(strings[i]).intersection(set(strings[j])) == set(strings[i]):
            same1.append(strings[j])
    same.append(' '.join(same1))
same = list(set(same))
same.sort()
for string in same:
    print(''.join(string))

Но существует проблема в виде ограничений по времени в 4 секунды и по памяти в 64 мегабайта: при создании дополнительного списка, равному strings, но с элементами в виде множеств, и дальнейшее сравнение его элементов в цикле, занимает 85мб памяти, но при этом 400мс времени
Даю свой код, который тратит меньше всего времени из всех попыток(4025мс)
Буду очень рад, если вы поможете оптимизировать код. Также знаю, что можно решить задачу через словари, но я не представляю, как это сделать

@Semen-Semenich · 15.02.2020, 16:11

bulk_bulk,
Нужно сократить время работы программы
Ох уж эти анаграммы

@bulk_bulk · 15.02.2020, 16:19 **[ТС]**

Semen-Semenich, спасибо, но мне нужно оптимизировать именно этот код, иначе от предпода прилетит за списывание

@palva · 15.02.2020, 16:42

А разве

Python
1
set(strings[i]).intersection(set(strings[j])) == set(strings[i])

Не эквивалентно этому?

Python
1
set(strings[i]) <= set(strings[j])

Это могло бы послужить тупым ответом на ваш вопрос -- оптимизация же! Но возникают сомнения, что такое анаграмма. Раньше я думал, что должны использоваться ровно те же самые буквы и каждая из них ровно в том же количестве. Может, я не прав.

@bulk_bulk · 15.02.2020, 16:44 **[ТС]**

Эквивалентно, но, к сожалению, не помогает

@eaa · 15.02.2020, 16:46

bulk_bulk, "n квадрат" бесполезно, алгоритмическая сложность не поменяется.
Смотрите темы которые вам указали.

@bulk_bulk · 15.02.2020, 16:50 **[ТС]**

Только что заметил, что часть кода не скопировалась: в начале должно быть также n = int (input())

@palva · 15.02.2020, 16:54

Относительно словарей -- информация к размышлению. Код

Python
1
2
3
d1 = {'a' : 5, 'b' : 7, 'c' : 2}
d2 = {'c' : 2, 'b' : 7, 'a' : 5}
print(d1 == d2)

печатает True. Так что я бы пользовался словарями. Насчет времени -- не знаю, но алгоритм был бы правильным.

@bulk_bulk · 15.02.2020, 16:59 **[ТС]**

Если не получится увеличить скорость того кода, то придется со словарями пытаться что-то делать. Взялся бы сразу, если бы умел с ними работать)

@palva · 15.02.2020, 16:59

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

не помогает

Не помогает в каком смысле? Код не стал работать быстрее? Удивлюсь, но поверю, мало ли какие оптимизации делает питон. Код не стал правильным? Так я этого и не обещал. Или вы считаете, что код был правильным, просто я не знаю, что такое анаграмма, тогда я просто отпишусь от темы с извинениями.

@eaa · 15.02.2020, 17:02

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

Относительно словарей -- информация к размышлению

памяти наверное много уйдет.
лучше свою хэш-функцию написать. там всего 26 первых простых чисел нужно.

@palva · 15.02.2020, 17:14

bulk_bulk, Если вас не учили словарям и знать их вы не обязаны, то зачем же использовать словари. Я бы попробовал вычислять множества к каждому слову вне цикла, а потом заходить в цикл и сравнивать уже готовые множества. По-моему, работало бы быстрее. Хотя после моей предыдущей неудачной оптимизации я уже сомневаюсь.

@bulk_bulk · 15.02.2020, 17:30 **[ТС]**

palva, не помогает в плане уменьшения времени
Создание дополнительного списка перед циклом с теми же элементами, но в виде множества, занимает слишком много памяти
То есть, в цикле сравниваю элементы списка с множествами, а потом уже добавляю по индексу элемент из основного списка, чтобы порядок букв был верный
Как сделать без дополнительного списка, понятия не имею

Новые блоги и статьи Все статьи Все блоги /
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .
Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .	Управление камерой с помощью скрипта OrbitControls.js на Three.js: Вращение, зум и панорамирование 8Observer8 05.03.2026 Содержание блога Финальная демка в браузере работает на Desktop и мобильных браузерах. Итоговый код: orbit-controls-threejs-js. zip. Сканируйте QR-код на мобильном. Вращайте камеру одним пальцем,. . .

@Semen-Semenich 5234 / 3479 / 1175 Регистрация: 21.03.2016 Сообщений: 8,306
	15.02.2020, 16:11
	bulk_bulk, Нужно сократить время работы программы Ох уж эти анаграммы 0

@bulk_bulk 3 / 3 / 0 Регистрация: 15.02.2020 Сообщений: 9
	15.02.2020, 16:19 [ТС]
	Semen-Semenich, спасибо, но мне нужно оптимизировать именно этот код, иначе от предпода прилетит за списывание 0

@bulk_bulk 3 / 3 / 0 Регистрация: 15.02.2020 Сообщений: 9
	15.02.2020, 16:44 [ТС]
	Эквивалентно, но, к сожалению, не помогает 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	15.02.2020, 16:46
	bulk_bulk, "n квадрат" бесполезно, алгоритмическая сложность не поменяется. Смотрите темы которые вам указали. 0

@bulk_bulk 3 / 3 / 0 Регистрация: 15.02.2020 Сообщений: 9
	15.02.2020, 16:50 [ТС]
	Только что заметил, что часть кода не скопировалась: в начале должно быть также n = int (input()) 0

@bulk_bulk 3 / 3 / 0 Регистрация: 15.02.2020 Сообщений: 9
	15.02.2020, 16:59 [ТС]
	Если не получится увеличить скорость того кода, то придется со словарями пытаться что-то делать. Взялся бы сразу, если бы умел с ними работать) 0

@palva 4278 / 2970 / 693 Регистрация: 08.06.2007 Сообщений: 9,930 Записей в блоге: 5
	15.02.2020, 17:14
	bulk_bulk, Если вас не учили словарям и знать их вы не обязаны, то зачем же использовать словари. Я бы попробовал вычислять множества к каждому слову вне цикла, а потом заходить в цикл и сравнивать уже готовые множества. По-моему, работало бы быстрее. Хотя после моей предыдущей неудачной оптимизации я уже сомневаюсь. 0

@bulk_bulk 3 / 3 / 0 Регистрация: 15.02.2020 Сообщений: 9
	15.02.2020, 17:30 [ТС]
	palva, не помогает в плане уменьшения времени Создание дополнительного списка перед циклом с теми же элементами, но в виде множества, занимает слишком много памяти То есть, в цикле сравниваю элементы списка с множествами, а потом уже добавляю по индексу элемент из основного списка, чтобы порядок букв был верный Как сделать без дополнительного списка, понятия не имею 0