Ох уж эти анаграммы

@new-programmer · Регистрация: 24.01.2020

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

Задача
Анагра́мма (от греч. ανα- — «пере» и γράμμα — «буква») — литературный приём, состоящий в перестановке букв или звуков определённого слова (или словосочетания), что в результате даёт другое слово или словосочетание (Википедия).

Мы будем работать с набором слов. Ваша задача — выписать все слова, которые являются анаграммами друг для друга, например «замок» и «мазок». Проверка слов должна быть регистронезависимой. Слова, для которых анаграммой является только оно само, выписывать не нужно, даже если это слово встречается в тексте в разном регистре.

Формат ввода
В первой строке идёт целое число n (1 ≤ n ≤ 100 000), количество исходных слов.

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

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

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

вывод
окорок рококо
петлей плетей теплей
тишь шить
томно тоном
тонко тонок

Вот мой код

Python
1
2
3
4
5
6
7
8
9
10
11
import collections
 
d = collections.defaultdict(list)
n = int(input())
for _ in range(n):
    e = input()
    d[tuple(sorted(list(e.lower())))].append(e.lower())
v = d.values()
v = filter(lambda w: len(set(w)) > 1, v)
ans = map(lambda x: ' '.join(sorted(x)), v)
print('\n'.join(sorted(ans)))

У меня проблема. На втором тесте с входными данными в 100000 слов тестирующая программа выдает ошибку "memory-limit-exceeded".

Помогите пожалуйста оптимизировать этот код

@eaa · 12.02.2020, 17:45

Анаграммы

@new-programmer · 12.02.2020, 19:50 **[ТС]**

***
Нужно время 4 сек и память 64Mb, а у меня время 598ms и память 76.1 Mb

Рыжий Лис · 12.02.2020, 20:00

Python
1
2
3
4
e = input().lower()
#…
v = d.values()
del d

Добавлено через 40 секунд

Python
1
sorted(e)

@new-programmer · 13.02.2020, 17:14 **[ТС]**

Я попробовал ваш вариант:

Python
1
2
3
4
5
6
7
8
9
10
11
import collections
 
d = collections.defaultdict(list)
n = int(input())
for _ in range(n):
    e = input().lower()
    d[tuple(sorted(e))].append(e)
v = d.values()
v = filter(lambda w: len(set(w)) > 1, v)
ans = map(lambda x: ' '.join(sorted(x)), v)
print('\n'.join(sorted(ans)))

PS пробовал также, как вы написали, удалить словарь, но это только увеличивало расход памяти.

Теперь затрачиваемая память равна 68,9 Мб
Нужно что-то еще

Но все равно спасибо, память уменьшилась)))

@eaa · 13.02.2020, 17:53

попробуйте так
d = d.values()
и дальше работать с d

Рыжий Лис · 13.02.2020, 17:58

Тогда уж сборщик мусора вручную вызывать.

@new-programmer · 13.02.2020, 18:00 **[ТС]**

Вот

Python
1
2
3
4
5
6
7
8
9
10
11
import collections
 
d = collections.defaultdict(list)
n = int(input())
for _ in range(n):
    e = input().lower()
    d[tuple(sorted(e))].append(e)
d = d.values()
d = filter(lambda w: len(set(w)) > 1, d)
d = map(lambda x: ' '.join(sorted(x)), d)
print('\n'.join(sorted(d)))

Память теперь 68,2 мб - много

Спасибо))

Добавлено через 1 минуту
Сборщик мусора? Что это?

Рыжий Лис · 13.02.2020, 18:00

Ещё два последних sorted можно заменить на sort:

Python
1
2
3
ans.sort()
for i in ans:
    print(i)

@new-programmer · 13.02.2020, 18:00 **[ТС]**

Рыжий Лис, Что такое сборщик мусора? Как с ним работать?

Рыжий Лис · 13.02.2020, 18:01

https://docs.python.org/3/libr... gc.collect

@new-programmer · 13.02.2020, 18:14 **[ТС]**

Рыжий Лис,
Вот

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
import collections
 
d = collections.defaultdict(list)
n = int(input())
for _ in range(n):
    e = input().lower()
    d[tuple(sorted(e))].append(e)
d = d.values()
d = filter(lambda w: len(set(w)) > 1, d)
d = list(map(lambda x: ' '.join(sorted(x)), d))
d.sort()
for i in d:
    print(i)

Память не сильно изменилась 68,1 Мб
Спасибо)

Добавлено через 10 минут
Рыжий Лис,

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
import collections
import gc
 
d = collections.defaultdict(list)
n = int(input())
for _ in range(n):
    e = input().lower()
    d[tuple(sorted(e))].append(e)
v = d.values()
gc.collect()
v = filter(lambda w: len(set(w)) > 1, v)
ans = list(map(lambda x: ' '.join(sorted(x)), v))
ans.sort()
for i in ans:
    print(i)

Я не совсем понял как с этим работать... Я правильно сделал?
Память не изменилась 68,2 Мб

Рыжий Лис · 13.02.2020, 18:18

Чтобы помять освободилась, нужно, чтобы на данные в программе не оставалось ссылок:

Python
1
2
3
4
v = d.values()
d = None
del d
gc.collect()

И даже это не гарантирует, что интерпретатор отдаст свободную память обратно ОС.

@new-programmer · 13.02.2020, 18:21 **[ТС]**

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import collections
import gc
 
d = collections.defaultdict(list)
n = int(input())
for _ in range(n):
    e = input().lower()
    d[tuple(sorted(e))].append(e)
v = d.values()
d = None
del d
gc.collect()
v = filter(lambda w: len(set(w)) > 1, v)
ans = list(map(lambda x: ' '.join(sorted(x)), v))
ans.sort()
for i in ans:
    print(i)

Память 68 Мб
Видимо не сработало
Спасибо))

@new-programmer · 13.03.2020, 18:45 **[ТС]**

Эта проблема реши я тем, что вместо массивов в словаре я использовал множества. По времени все прошло.

@z0nGG · 31.03.2020, 11:38

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
words = sorted([input().lower() for _ in range(int(input()))])
 
 
def sorted_string(s):
    return ''.join(sorted(s))
 
 
anagram = {}
for word in words:
    sorted_word = sorted_string(word)
    anagram.setdefault(sorted_word, [])
    anagram[sorted_word].append(word)
for w, a in anagram.items():
    if len(set(a)) > 1:
        print(*sorted(set(a)))

@tuizk · 12.05.2020, 11:07

new-programmer, скинешь программу? Пытаюсь решить третий день, никак не могу сделать. Даже тему создал, но так и не решил

@new-programmer · 12.05.2020, 12:16 **[ТС]**

tuizk, Лови

Python
1
2
3
4
5
6
7
8
9
dic = {}
n = int(input())
for i in range(n):
    e = input().lower()
    s = ''.join(sorted(e))
    dic[s] = dic.get(s, set())
    dic[s].add(e)
new_words = [' '.join(sorted(i)) for i in dic.values() if len(i) > 1]
print('\n'.join(sorted(new_words)))

@Povlin228 · 15.03.2021, 15:12

Пожалуйста, можешь рассказать как работает этот код! Заранее спасибо!

@Dolor- · 13.04.2021, 13:42

Сами делайте

Новые блоги и статьи Все статьи Все блоги /
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .	Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .	Отображение реквизитов в документе по условию и контроль их заполнения Maks 04.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеСпецтехники", разработанного в конфигурации КА2. Данный документ берёт данные из другого нетипового документа. . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	12.02.2020, 17:45
	Анаграммы 0

@new-programmer 11 / 10 / 1 Регистрация: 24.01.2020 Сообщений: 48
	12.02.2020, 19:50 [ТС]
	*** Нужно время 4 сек и память 64Mb, а у меня время 598ms и память 76.1 Mb 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.02.2020, 17:53
	попробуйте так d = d.values() и дальше работать с d 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	13.02.2020, 17:58
	Тогда уж сборщик мусора вручную вызывать. 0

@new-programmer 11 / 10 / 1 Регистрация: 24.01.2020 Сообщений: 48
	13.02.2020, 18:00 [ТС]
	Рыжий Лис, Что такое сборщик мусора? Как с ним работать? 0

Рыжий Лис Просто Лис 5973 / 3735 / 1099 Регистрация: 17.05.2012 Сообщений: 10,791 Записей в блоге: 9
	13.02.2020, 18:01
	https://docs.python.org/3/libr... gc.collect 0

@new-programmer 11 / 10 / 1 Регистрация: 24.01.2020 Сообщений: 48
	13.03.2020, 18:45 [ТС]
	Эта проблема реши я тем, что вместо массивов в словаре я использовал множества. По времени все прошло. 0

@tuizk 0 / 0 / 0 Регистрация: 11.05.2020 Сообщений: 31
	12.05.2020, 11:07
	new-programmer, скинешь программу? Пытаюсь решить третий день, никак не могу сделать. Даже тему создал, но так и не решил 0

@Povlin228 0 / 0 / 0 Регистрация: 15.03.2021 Сообщений: 2
	15.03.2021, 15:12
	Пожалуйста, можешь рассказать как работает этот код! Заранее спасибо! 0

@Dolor- 0 / 0 / 0 Регистрация: 11.01.2021 Сообщений: 1
	13.04.2021, 13:42
	Сами делайте 0