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

@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

Сами делайте

Новые блоги и статьи Все статьи Все блоги /
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем	10 пpимет, которые всегда сбываются Maks 31.03.2026 1. Чтобы, наконец, пришла маршрутка, надо закурить. Если сигарета последняя, маршрутка придет еще до второй затяжки даже вопреки расписанию. 2. Нaдоели зима и снег? Не надо переезжать. Достаточно. . .	Перемещение выделенных строк ТЧ из одного документа в другой Maks 31.03.2026 Реализация из решения ниже выполнена на примере нетипового документа "ВыдачаОборудованияНаСпецтехнику" с единственной табличной частью "ОборудованиеИКомплектующие" разработанного в конфигурации КА2. . . .	Functional First Web Framework Suave DevAlt 30.03.2026 Sauve. IO Апнулись до NET10. Из зависимостей один пакет, работает одинаково хорошо как в режиме проекта так и в интерактивном режиме. из сложностей - чисто функциональный подход. Решил. . .
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .

@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