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

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

Новые блоги и статьи Все статьи Все блоги /
Символьное дифференцирование igorrr37 13.02.2026 / * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 12.02.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 11.02.2026 Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .	SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image 8Observer8 10.02.2026 Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .	Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .

@Semen-Semenich 5226 / 3472 / 1174 Регистрация: 21.03.2016 Сообщений: 8,300
	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

Опции темы