Home>
spisok, dic, num_of_words= list(), dict(), int(input())
for i in range(num_of_words):
    spisok.append(input().lower())
def test(a,b):
    return len(a)== len(b) and all(t in b for t in a)
for element in list:
    for element1 in list:
        if test(element, element1):
            if element in dic:
                dic[element].append(element1)
            else:
                dic[element]= [element1]
spisok1, spisok2= list(), list()
for key, val in dic.items():
    spisok1.append(sorted({key, *val}))
for j in list1:
    if j not in list2:
        spisok2.append(j)
for elem in spisok2:
    print(*elem)

The fact is that I'm doing a word test for anagram (given n words and need to be divided into anagram groups, nested for loops run through all the elements completely (creates the same pairs several times), because of this, the limit is exceeded time, help optimize cycles)

create an array of word-sorted letter pairs in a word. Now, using the sorted letters as a key, group them together. The complexity will be n*log n, which is much faster than your approach

KoVadim2022-02-14 09:42:51

Could you demonstrate clearly, did not quite catch it?

fafadfadfda2022-02-14 09:45:30
  • Answer # 1

    More compact notation. Plus sorts anagrams lexicographically and outputs only them (words without anagrams are skipped).

    anagrams= {}
    for word in sorted(input().lower() for _ in range(int(input()))):
        sorted_word= ''.join(sorted(word))
        anagrams[sorted_word]= anagrams.get(sorted_word, []) + [word]
    for words in anagrams.values():
        uniq_words= set(words)
        if len(uniq_words) > one:
            print(*sorted(uniq_words))
    

    Writing via .get is cool, I love it myself, but doesn't copying lists happen in this case? This is very inefficient, .append would be faster I think.

    CrazyElf2022-02-14 10:32:33

    @CrazyElf I agree, this entry is significantly slower than the variant via anagrams.setdefault(sorted_word, []); anagrams.append(word) or via the classic existence check via the usual if sorted_word in anagrams:. But on small amounts of data, this is usually not critical.

    GrAnd2022-02-14 10:53:59

    If comments and some other lines (shangbang) are deleted in my code, then your code will not be so "compact". If you read the original question, then the problem is not in compactness, but in speed ...

    KoVadim2022-02-14 10:55:48

    @GrAnd The author has a time limit, which means that all code must be made as efficient as possible

    CrazyElf2022-02-14 11:29:54

    @CrazyElf the author has an implementation through an algorithm with quadratic complexity, so it does not pass in time. After the optimization of the algorithm, the remaining micro-optimizations already give a microscopic effect.

    insolor2022-02-14 11:57:32
  • Answer # 2

    I'm not a python programmer, so the code itself may not be quite pythonic. But ...

    #!/usr/bin/python3
    from collections import defaultdict
    # simply sorts the letters in a word
    def srt(w):
        t= sorted(w)
        return "".join(t)
    # source words
    ws= ["foo", "bar", "baz", "oof", "bra"]
    mr= defaultdict(list)
    # for each input word we are looking for a key -sorted characters
    for w in ws:
        sw= srt(w)
        # and add to the desired bucket
        mr[sw].append(w)
    # everything is ready, just display the result beautifully
    for w in mr:
        print(f"word {w}, count {len(mr[w])}")
        print("\t", end="")
        for cw in mr[w]:
            print(cw, end="")
        print()
    

    Thank you very much!

    fafadfadfda2022-02-14 10:15:08