Finding reversed word pairs

Question

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 :)

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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')]

Answer 5

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'), ...