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

@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, не помогает в плане уменьшения времени
Создание дополнительного списка перед циклом с теми же элементами, но в виде множества, занимает слишком много памяти
То есть, в цикле сравниваю элементы списка с множествами, а потом уже добавляю по индексу элемент из основного списка, чтобы порядок букв был верный
Как сделать без дополнительного списка, понятия не имею

Новые блоги и статьи Все статьи Все блоги /
Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	Киев стоит - украинская песня zorxor 28.01.2026 wfWdiRqdTxc О Господи, Вечный, Ты . . . Я помоги, Бесконечный. . . Я прошу Ты. . . Я погибаю, спаси. . . Я прошу Тебя Вечный. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .	Загрузка PNG с альфа-каналом на SDL3 для Android: с помощью SDL3_image 8Observer8 27.01.2026 Содержание блога SDL3_image - это библиотека для загрузки и работы с изображениями. Эта пошаговая инструкция покажет, как загрузить и вывести на экран смартфона картинку с альфа-каналом, то есть с. . .
влияние грибов на сукцессию anaschu 26.01.2026 Бифуркационные изменения массы гриба происходят тогда, когда мы уменьшаем массу компоста в 10 раз, а скорость прироста биомассы уменьшаем в три раза. Скорость прироста биомассы может уменьшаться за. . .	Воспроизведение звукового файла с помощью SDL3_mixer при касании экрана Android 8Observer8 26.01.2026 Содержание блога SDL3_mixer - это библиотека я для воспроизведения аудио. В отличие от инструкции по добавлению текста код по проигрыванию звука уже содержится в шаблоне примера. Нужно только. . .	Установка Android SDK, NDK, JDK, CMake и т.д. 8Observer8 25.01.2026 Содержание блога Перейдите по ссылке: https:/ / developer. android. com/ studio и в самом низу страницы кликните по архиву "commandlinetools-win-xxxxxx_latest. zip" Извлеките архив и вы увидите. . .	Вывод текста со шрифтом TTF на Android с помощью библиотеки SDL3_ttf 8Observer8 25.01.2026 Содержание блога Если у вас не установлены Android SDK, NDK, JDK, и т. д. то сделайте это по следующей инструкции: Установка Android SDK, NDK, JDK, CMake и т. д. Сборка примера Скачайте. . .

@Semen-Semenich 5222 / 3469 / 1173 Регистрация: 21.03.2016 Сообщений: 8,295
	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,928 Записей в блоге: 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