11
\$\begingroup\$

I wrote this code to find opposites of words (i.e., words backwards). Input is a list of words. If this list contains a word + its opposite, then it should form a pair. The output should be a list of tuples (pairs).

The output should:

  • contain every pair of words only once - it should contain either ('reed', 'deer') or ('deer', 'reed'), but not both.
  • not contain palindromes (words which are opposite to themselves) - e.g. 'refer'
def find_opposites(lst):
    if lst == [] or len(lst) == 1:
        return []
    else:
        opposites = [] # contains all words backwards (except palindromes)
        result = []
        for word in lst: 
            if word != word[::-1]: # avoid palindromes
                opposites.append(word[::-1])

        for word in opposites:
            if word in lst: 
            # if word in both opposites list and original list,
            # then it should form a pair with its opposite

                tup = (word[::-1], word) # create tuple
                if tup[::-1] not in result: # append tuple only if its opposite in not already in result
                    result.append(tup)

        return result

I have tried to substitute the list opposites with a dictionary as I know lists are slower to process, but it still takes a very long time.

Please let me know if you have any ideas on how to make it run faster, as it takes ages when I run on my corpora which contains over 11.000 words. Thanks a lot :)

\$\endgroup\$
3
  • 2
    \$\begingroup\$ Please do not update the code in your question after receiving answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. Once a question has a first answer, that's the version all answers should be reviewing. \$\endgroup\$ – Mast Feb 11 at 17:22
  • \$\begingroup\$ I have tried to substitute the list opposites with a dictionary close, very close :/ I know lists are slower to process lists are simpler, and there are things (like iteration) they're faster at. Dictionaries are faster at membership tests, for one thing, but look at which "collection" you iterate and which you check membership in. \$\endgroup\$ – greybeard Feb 12 at 7:02
  • \$\begingroup\$ (If this was tagged algorithm (there is no tag data structure?!), I was tempted to suggest using ordering as an alternative to data structures supporting quasi-constant in.) \$\endgroup\$ – greybeard Feb 12 at 8:26
9
\$\begingroup\$

As others have mentioned, your program runs slowly because it is doing a lot of membership tests against fairly large lists, which is expensive. If you replace your lists with sets, that alone should improve performance by quite a bit.

Creating a set from the input list of words is also important to ensure the correctness of your algorithm. As @Tweakimp pointed out, we only want to find pairs of opposites within a collection of unique words, to avoid the possibility of duplicates of the same pair from showing up in the results.

Below is a simple algorithm which calculates all the pairs in one pass.

  • Create unique_words: set[str] from the input list of words.
  • Create results: list[tuple[str, str]] for our results. This will be our return value.
  • Create words_seen: set[str] to track which words from unique_words we've seen so far.
  • Iterate over unique_words; for each word, also calculate reversed_word.
    • If we haven't seen reversed_word yet, then we don't know if word has a matching pair (yet). So we add word to words_seen.
    • If we have seen reversed_word, then we just found a matching pair, so we append (word, reversed_word) to results.
  • Return results.
def find_opposites(words):
    unique_words = set(words)

    results = []
    words_seen = set()

    for word in unique_words:
        reversed_word = word[::-1]

        # if we have already seen reversed_word,
        # then we found a new pair of opposites: (word, reversed_word)
        if reversed_word in words_seen:
            results.append((word, reversed_word))
        else:
            words_seen.add(word)

    return results

Because we start with the set unique_words, we actually don't need to check explicitly for the palindrome case. This is because in order for a palindrome to end up in results, there would need to be at least two instances of the same palindrome in unique_words, which is impossible.

\$\endgroup\$
1
  • \$\begingroup\$ Simpler and also a bit faster than my solution, well done :) \$\endgroup\$ – Tweakimp Feb 12 at 5:41
7
\$\begingroup\$

Bug

Your function does not filter out duplicate pairs.

>>> words = ["test", "tset", "test", "tset"]
>>> find_opposites(words)
[('test', 'tset'), ('test', 'tset')]

Improvements

  • Comprehension:
# This part
opposites = [] # contains all words backwards (except palindromes)
result = []
for word in lst: 
    if word != word[::-1]: # avoid palindromes
        opposites.append(word[::-1])

# can be rewritten as
opposites = {word[::-1] for word in lst if word != word[::-1]}

word[::-1] reverses the word, as you already used it.
if word != word[::-1] ensures palindromes are removed.
{x for x in y} is a comprehension. More specifically, it is a set, which automatically removes duplicates.

  • Membership tests
    Membership tests like a in b are fast on data structures like sets or dictionaries because they use hash tables. On lists, every element is compared, which takes a lot of time.

  • Putting everything together
    Here is my solution:

def find_opposites_new(lst):
    # create a set of reversed words of the original words, without palindromes
    backwards = {word[::-1] for word in lst if word != word[::-1]}
    # initiate the result list we want to return
    result = []
    # initiate the set we use to check if a word or its reversed version is already
    # in the result list
    check_set = set()
    # loop over all words
    for word in lst:
        # if the word is also in the reversed words and not in the results already
        if word in backwards and word not in check_set:
            # reverse the word
            b_word = word[::-1]
            # add the word and its reversed version to the check set
            check_set.add(word)
            check_set.add(b_word)
            # add the tuple to the results
            result.append((word, b_word))
    return result
  • Test on random words
import random
import time
from string import ascii_lowercase

# list of 10000 random words of length 3 to 20, will probably have some reverse words
random_words = [
    "".join(random.choices(population=ascii_lowercase, k=random.randint(3, 20)))
    for _ in range(10000)
]

# measure time at starts and ends
start = time.time()
find_opposites(words)
end = time.time()

start_new = time.time()
find_opposites_new(words)
end_new = time.time()

# calculate times
print(f"old {end-start:} sec")
print(f"new {end_new-start_new:} sec")
# old 1.2763020992279053 sec
# new 0.00501561164855957 sec
\$\endgroup\$
1
  • 1
    \$\begingroup\$ While behaviour in presence of duplicate words in the input is unspecified (["test", "tset", "test"]), note that the original does not show a pair and its reverse. \$\endgroup\$ – greybeard Feb 12 at 7:34
5
\$\begingroup\$

The part if word in lst basically uses a for-loop to check the entire list again, which takes on average 11000/2=5500 tries. So you'll have 11000*5500 = 60.500.000 pairwise checks. That shouldn't take ages but still isn't efficient. There's also the checking of the result, which is a growing list so that takes longer after every result.

If you used a dictionary, you should be getting better results, but only if you search on the keys.

I think it would be clearer if you just convert lst and result to a set. Sets store unique values and are well-equipped to do fast searching.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ Not only are sets suited to fast searching, but set intersection (e.g. inputs & reversed) is the perfect tool for the exercise. \$\endgroup\$ – Toby Speight Feb 11 at 16:09
  • \$\begingroup\$ thanks for your answer. I tried with sets and it took even longer, but I am not used to using sets so I must have done something wrong. I then solved using a dictionary (I posted my solution as edit in the question) \$\endgroup\$ – planetx Feb 11 at 17:04
3
\$\begingroup\$

This code is fast and simple. It takes around 5ms to find 15-odd pairs in 10,000 words.

The speed comes from using a set lookup and comprehensions.

def find_opposites_set1(words):
    reversed_words = [word[::-1] for word in words]
    unique_reversed_words = set(reversed_words)
    return [
        (word, reversed_word) 
        for word, reversed_word
        in zip(words, reversed_words)
        if word in unique_reversed_words and word < reversed_word
    ]

Some explanations:

  1. set lookup for reversed words-- fast to create and much faster to check membership (if word in unique_reversed_words) than scanning a list

  2. if ... and word < reversed_word removes duplicates and palindromes from the results (thanks to Eric Duminil's answer for this idea.) This works so long as the original word list contains unique words

  3. Boolean and is a short-circuiting operator in Python so and word < reversed_word will only be executed 15 or so times, rather than 10,000 times if the palindromes are weeded out before the pairs are identified

  4. zip() pairs words and their reverse together to avoid recalculating word[::-1]

A slightly different method uses set intersection to find pairs quickly but needs to recalculate a few of the word reversals. In practice the two solutions seem to perform similarly:

def find_opposites_set2(words):
    reversed_words = (word[::-1] for word in words)
    paired = set(words).intersection(reversed_words)
    return [
        (word, reversed_word)
        for word, reversed_word
        in zip(paired, (word[::-1] for word in paired))
        if word < reversed_word
    ]

This second algorithm will work if the original word list contains duplicate words. So, for example, you could apply this function to the text of a book to see how many reversed words occur naturally in a text. Here's the result of applying it to 153,000 words from the Seneca Minor Dialogues on Project Gutenberg:

(runtime 0.3s for 153,000 words)

[('brag', 'garb'), ('now', 'won'), ('dog', 'god'), ('as', 'sa'), ('is', 'si'),
 ('NO', 'ON'), ('evil', 'live'), ('saw', 'was'), ('doom', 'mood'), ('en', 'ne'),
 ('draw', 'ward'), ('al', 'la'), ('pas', 'sap'), ('dam', 'mad'), ('no', 'on'), 
 ('are', 'era')]
\$\endgroup\$
1
\$\begingroup\$

You could simply compare the word and its reverse with word < word[::-1] in order to avoid palindromes and duplicate entries.

If words is a set containing all the possible words, you can create a set of results directly:

mirror_words = {w for w in words if w < w[::-1] and w[::-1] in words}

After initializing words with:

with open('/usr/share/dict/american-english') as wordbook:
    words = {word.strip() for word in wordbook}

The above line returns:

{'paws', 'buns', 'gut', 'rebut', 'maws', 'bus', 'pools', 'saw', 'bats', 'mar', 'naps', 'deer', 'spay', 'deeps', 'bat', 'flow', 'straw', 'but', 'abut', 'nuts', 'cod', 'diaper', 'eh', 'dray', 'keel', 'debut', 'pots', 'flog', 'sports', 'ergo', 'pot', 'pas', 'no', 'guns', 'spot', 'bard', 'keels', 'ho', 'may', 'dial', 'gals', 'don', 'agar', 'pat', 'dam', 'ajar', 'leper', 'lap', 'pets', 'dim', 'snips', 'lever', 'leer', 'sleets', 'mart', 'spit', 'now', 'sway', 'deliver', 'sprat', 'parts', 'gnat', 'buts', 'nap', 'bad', 'pis', 'are', 'gulp', 'nit', 'dew', 'way', 'smart', 'deep', 'raw', 'pus', 'peels', 'net', 'snot', 'sloops', 'girt', 'remit', 'got', 'ah', 'looter', 'loop', 'emit', 'redraw', 'not', 'emir', 'part', 'door', 'ares', 'lop', 'ate', 'eviler', 'dos', 'am', 'bin', 'decal', 'avid', 'brag', 'bud', 'meet', 'nips', 'mu', 'snaps', 'gal', 'loops', 'desserts', 'pans', 'nip', 'bag', 'pols', 'hoop', 'em', 'raps', 'denim', 'ports', 'bur', 'draws', 'saps', 'pit', 'tow', 'pees', 'bog', 'stew', 'ban', 'drawer', 'it', 'par', 'loots', 'doom', 'bun', 'denier', 'liar', 'draw', 'gnus', 'rat', 'bed', 'burg', 'dog', 'spots', 'pals', 'lager', 'gel', 'eel', 'keep', 'mat', 'snoops', 'dual', 'devil', 'gem', 'mils', 'edit', 'tort', 'rats', 'moor', 'pay', 'rot', 'new', 'per', 'pins', 'spat', 'snit', 'gum', 'loot', 'gums', 'decaf', 'gas', 'nut', 'fer', 'knits', 'evil'}

Note that 'paws' and 'evil' are included, but not 'swap' or 'live'.

If you want, you can sort it and show the pairs:

sorted((w, w[::-1]) for w in mirror_words)

[('abut', 'tuba'), ('agar', 'raga'), ('ah', 'ha'), ('ajar', 'raja'), ('am', 'ma'), ('are', 'era'), ('ares', 'sera'), ('ate', 'eta'), ('avid', 'diva'), ('bad', 'dab'), ('bag', 'gab'), ('ban', 'nab'), ('bard', 'drab'), ('bat', 'tab'), ('bats', 'stab'), ('bed', 'deb'), ('bin', 'nib'), ('bog', 'gob'), ('brag', 'garb'), ('bud', 'dub'), ('bun', 'nub'), ('buns', 'snub'), ('bur', 'rub'), ('burg', 'grub'), ('bus', 'sub'), ('but', 'tub'), ('buts', 'stub'), ('cod', 'doc'), ('dam', 'mad'), ('debut', 'tubed'), ('decaf', 'faced'), ('decal', 'laced'), ('deep', 'peed'), ('deeps', 'speed'), ('deer', 'reed'), ('deliver', 'reviled'), ('denier', 'reined'), ('denim', 'mined'), ('desserts', 'stressed'), ('devil', 'lived'), ('dew', 'wed'), ...

\$\endgroup\$
3
  • \$\begingroup\$ (To pick a nit, a set of words with differing reverse present isn't quite a list of tuples.) \$\endgroup\$ – greybeard Feb 13 at 4:08
  • \$\begingroup\$ @greybeard unless I'm missing something, my last line of code outputs the desired result, doesn't it? Mirror words is indeed a set and has a different format, but I still wanted to mention it because it's easy to create, it should be efficient and it doesn't require an "already seen" set. And it basically contains the exact same information as the desired output, just in a more compact format. \$\endgroup\$ – Eric Duminil Feb 13 at 9:13
  • \$\begingroup\$ Really nice solution-- simple and performs as well as any other answer here. \$\endgroup\$ – Nick Feb 18 at 18:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.