Assign unique slugs to set of people. Slugs are as short as possible. (New elements only added to ensure uniqueness.)

Question

I have a Python function that will terminate when some condition is fulfilled.
That could happen after the first (easy) step. But more steps (of increasing complexity) may follow.

Below is the simplified example function find_slugs.
For each person in database it finds a slug, which is unique and as short as possible.

To avoid code repetition it was necessary to create the subfunction maybe_finish.
It checks if the slugs are already unique, and returns the result if they are.
Otherwise it prepares the next step by creating blocks_to_refine, and returns None.

Between the steps are conditional returns, contracted to one line:

if maybe_result := maybe_finish(): return maybe_result

In three lines it would look like this:

maybe_result = maybe_finish()
if maybe_result is not None:
    return maybe_result

Repeating this line does not seem like an elegant solution to me.
(It is essentially repeating three lines of code again and again.)

I would be interested in different approaches to this example problem.

For the given list of people the result is {0: 'JohnSpam85a', 1: 'JohnSpam85b', 2: 'JohnEggs91', 3: 'JohnEggs92', 4: 'EmmaFish95a', 5: 'EmmaFish95b', 6: 'MaryBeer', 7: 'MaryWine', 8: 'Owen', 9: 'Ruth'}. For the first three it is {0: 'JohnSpam85a', 1: 'JohnSpam85b', 2: 'JohnEggs'}. For the last three {7: 'Mary', 8: 'Owen', 9: 'Ruth'}.

(There is a corresponding question on Stackoverflow.)

from collections import defaultdict


database = {
    0: {'name1': 'John', 'name2': 'Spam', 'born': '1985'},  # JohnSpam85a
    1: {'name1': 'John', 'name2': 'Spam', 'born': '1985'},  # JohnSpam85b
    2: {'name1': 'John', 'name2': 'Eggs', 'born': '1991'},  # JohnEggs91
    3: {'name1': 'John', 'name2': 'Eggs', 'born': '1992'},  # JohnEggs92
    4: {'name1': 'Emma', 'name2': 'Fish', 'born': '1995'},  # EmmaFish95a
    5: {'name1': 'Emma', 'name2': 'Fish', 'born': '1995'},  # EmmaFish95b
    6: {'name1': 'Mary', 'name2': 'Beer', 'born': '2000'},  # MaryBeer
    7: {'name1': 'Mary', 'name2': 'Wine', 'born': '2000'},  # MaryWine
    8: {'name1': 'Owen', 'name2': 'Wine', 'born': '2000'},  # Owen
    9: {'name1': 'Ruth', 'name2': 'Milk', 'born': '2000'}   # Ruth
}

alphabetical_letters = ['a', 'b', 'c', 'd']


def find_slugs():

    def maybe_finish():
        # A block is a list of numbers with (currently) the same slug.
        slug_to_block = defaultdict(list)
        for number, slug in number_to_slug.items():
            slug_to_block[slug].append(number)
        if len(slug_to_block) == len(database):
            return number_to_slug
        nonlocal blocks_to_refine
        blocks_to_refine = []
        for block in slug_to_block.values():
            if len(block) > 1:
                blocks_to_refine.append(block)

    ##################################################################

    blocks_to_refine = None  # created and updated in `maybe_finish`

    number_to_slug = dict()  # result

    # step 1: start with first name
    for number, table_row in database.items():
        number_to_slug[number] = table_row['name1']

    if maybe_result := maybe_finish(): return maybe_result

    # step 2: add last name
    for block in blocks_to_refine:
        for number in block:
            number_to_slug[number] += database[number]['name2']

    if maybe_result := maybe_finish(): return maybe_result

    # step 3: add year of birth
    for block in blocks_to_refine:
        for number in block:
            number_to_slug[number] += database[number]['born'][2:4]

    if maybe_result := maybe_finish(): return maybe_result

    # step 4: append letter to year of birth
    for block in blocks_to_refine:
        for i, number in enumerate(block):
            number_to_slug[number] += alphabetical_letters[i]

    return number_to_slug

Answer 1

maybe_finish building a list of list does not feel great here, also using the database variable only for a quick shortcut does not feel necessary either as the complexity is still \$O(2n)\$. Consider yielding your blocks instead and flatten them from the call site.

alphabetical_letters is not necessary either as it already exist in the string module. You also don't need to use a list here, strings are indexable too.

Consider passing database as a parameter to the find_slugs function, this ease reuse and testing. In fact, given your example input, using doctest here seems like a sensible thing to do.

Proposed improvements:

import itertools
from string import ascii_lowercase as alphabet
from collections import defaultdict


flatten = itertools.chain.from_iterable


def find_duplicates(slugs):
    similar_slugs = defaultdict(list)
    for number, slug in slugs.items():
        similar_slugs[slug].append(number)
    for same_slug in similar_slugs.values():
        if len(same_slug) > 1:
            yield same_slug


def build_slugs(database):
    """Convert rows from the database into a unique slug
    as short as possible for each row.

    >>> database = {
    ...     0: {'name1': 'John', 'name2': 'Spam', 'born': '1985'},
    ...     1: {'name1': 'John', 'name2': 'Spam', 'born': '1985'},
    ...     2: {'name1': 'John', 'name2': 'Eggs', 'born': '1991'},
    ...     3: {'name1': 'John', 'name2': 'Eggs', 'born': '1992'},
    ...     4: {'name1': 'Emma', 'name2': 'Fish', 'born': '1995'},
    ...     5: {'name1': 'Emma', 'name2': 'Fish', 'born': '1995'},
    ...     6: {'name1': 'Mary', 'name2': 'Beer', 'born': '2000'},
    ...     7: {'name1': 'Mary', 'name2': 'Wine', 'born': '2000'},
    ...     8: {'name1': 'Owen', 'name2': 'Wine', 'born': '2000'},
    ...     9: {'name1': 'Ruth', 'name2': 'Milk', 'born': '2000'},
    ... }
    >>> build_slugs(database)
    {0: 'JohnSpam85a', 1: 'JohnSpam85b', 2: 'JohnEggs91', 3: 'JohnEggs92', 4: 'EmmaFish95a', 5: 'EmmaFish95b', 6: 'MaryBeer', 7: 'MaryWine', 8: 'Owen', 9: 'Ruth'}
    """
    number_to_slug = {}  # result

    # step 1: start with first name
    for number, table_row in database.items():
        number_to_slug[number] = table_row['name1']

    # step 2: add last name
    for number in flatten(find_duplicates(number_to_slug)):
        number_to_slug[number] += database[number]['name2']

    # step 3: add year of birth
    for number in flatten(find_duplicates(number_to_slug)):
        number_to_slug[number] += database[number]['born'][2:4]

    # step 4: append letter to year of birth
    for block in find_duplicates(number_to_slug):
        for letter, number in zip(alphabet, block):
            number_to_slug[number] += letter

    return number_to_slug


if __name__ == '__main__':
    import doctest
    print(doctest.testmod())

Answer 2

Clarify the real problem. Your question focuses on how to deal with the repeated if-finished checks. But that repetition is just a small part of a larger repetition across the four slug-creation steps. Steps 2 and 3 are already identical in form: iterate over blocks_to_refine and then over block, appending to the slugs as we go. Step 4 differs from 2 and 3 only because it uses enumerate(). Step 1 seems more different because we are setting number_to_slug values rather than appending to them. But all of those differences can be ironed away by (a) using enumerate() across all steps and (b) initializing variables differently so that even Step 1 operates by appending. In other words, we want every step to have the same structure:

for block in blocks_to_refine:
    for i, n in enumerate(block):
        number_to_slug[n] += ...

Define a list of slug functions to compute what needs to be appended. To execute the four steps, just iterate over those functions. After each step, check whether you are done and possibly return early. Since we have eliminated the code repetition, there's no need to resort to awkward inner functions and reliance on resetting nonlocal variables (whenever you find yourself feeling the need for the latter, take it as a sign that bigger refactoring might be needed).

def find_slugs():
    # Returns a dict mapping each DB number to a unique slug.

    # Initialize the return value and the DB numbers that need processing.
    slugs = {n : '' for n in database}
    todo = [list(slugs)]

    # Functions to compute each slug element.
    slug_funcs = [
        lambda _, n: database[n]['name1'],
        lambda _, n: database[n]['name2'],
        lambda _, n: database[n]['born'][2:4],
        lambda i, _: alphabetical_letters[i],
    ]

    # Build the slugs.
    for sf in slug_funcs:
        for block in todo:
            for i, n in enumerate(block):
                slugs[n] += sf(i, n)

        # Dict mapping each slug to its DB numbers.
        slug_to_nums = defaultdict(list)
        for n, slug in slugs.items():
            slug_to_nums[slug].append(n)

        # Return if all slugs unique.
        if len(slug_to_nums) == len(database):
            return slugs

        # DB numbers for slugs needing refinement.
        todo = [
            ns
            for ns in slug_to_nums.values()
            if len(ns) > 1
        ]

    return slugs

Answer 3

nested def

Sometimes I will diplomatically explain that nesting defs causes excessive coupling similar to global variables, and is a technique you should probably avoid. Plus it impacts testability. But here, I will just come right out and say it.

No. Do not nest maybe_finish() as you've done. Break it out as a separate helper, and use explicit parameters to communicate with it. Pass in number_to_slug.

As written, it is unclear what its single responsibility is, and it's hard to reason about its contracts.

Possibly it should be a pair of helpers: one that compares lengths and another that works on blocks to refine.

Do not implicitly return a value when dropping off the end of the function, since this is not a procedure that is strictly being evaluated for side effects. Prefer an explicit return None.

---

appropriate name

The single biggest thing wrong with def maybe_finish(): is that it is just a terrible name. It doesn't help the Gentle Reader to identify its purpose, and no """docstring""" or # comment linked "uniqueness" to the notion of being finished. Consider renaming this predicate to slugs_are_unique or slugs_unique.

[ EDIT: After my review the question's title was updated to give exactly the help I sought from a docstring as I was trying to read the code: "Assign unique slugs to set of people. Slugs are as short as possible. (New elements only added to ensure uniqueness.)" ]

---

mixed type

    blocks_to_refine = None  # created and updated in `maybe_finish`

No. Initialize to [] the empty list, rather than telling mypy it is an Optional[list]. Or perhaps this could be entirely local to maybe_finish()?

---

Kudos, the number_to_slug return variable is well named.

---

conventional loop variable

    for number, table_row in ...

The identifier number is accurate, but rather vague. I was left wondering if it was some summary statistic over the row data. And then I saw what it was being used for.

Prefer the index variable i for simple loops such as this.

---

iterate over functions

There are four steps. Consider adding four unit tests which trigger each of the four returns.

Define four helpers:

• set_first_name()
• add_last_name()
• add_birth_year()
• append_letter()

Now you no longer need four tests for early return, as writing it once suffices:

steps = [set_first_name, add_last_name, add_birth_year, append_letter]
for step in steps:
    step(number_to_slug)
    if maybe_result := maybe_finish(number_to_slug):
        return maybe_result

Answer 4

The following is my improvement of the code by 301_Moved_Permanently. The crucial feature in that answer was the return of a generator by find_duplicates. But (as mentioned by Matthieu M.) it is not efficient, to check all slugs for duplicates. Instead, the function should refine the duplicates from the last step. That requires using the generator twice: First in the for-loop to append the slugs, and then in the next call of find_duplicates. As generators can only be used once, it is doubled with itertools.tee.

import itertools
from collections import defaultdict
from string import ascii_lowercase as alphabet

flatten = itertools.chain.from_iterable

def double_generator(gen): return itertools.tee(gen, 2)


def find_duplicates(number_to_slug, dup_gen_to_refine=None):
    slug_to_numbers = defaultdict(list)
    if dup_gen_to_refine is not None:
        for number in flatten(dup_gen_to_refine):
            slug = number_to_slug[number]
            slug_to_numbers[slug].append(number)
    else:
        for number, slug in number_to_slug.items():
            slug_to_numbers[slug].append(number)
    for block in slug_to_numbers.values():
        if len(block) > 1:
            yield block


def find_slugs(database):
    number_to_slug = {}  # result

    # step 1: start with first name
    for number, table_row in database.items():
        number_to_slug[number] = table_row['name1']

    # step 2: add last name
    dup_gen = find_duplicates(number_to_slug)
    dup_gen_to_append, dup_gen_to_refine = double_generator(dup_gen)
    for number in flatten(dup_gen_to_append):
        number_to_slug[number] += database[number]['name2']

    # step 3: add year of birth
    dup_gen = find_duplicates(number_to_slug, dup_gen_to_refine)
    dup_gen_to_append, dup_gen_to_refine = double_generator(dup_gen)
    for number in flatten(dup_gen_to_append):
        number_to_slug[number] += database[number]['born'][2:4]

    # step 4: append letter to year of birth
    dup_gen = find_duplicates(number_to_slug, dup_gen_to_refine)
    dup_gen_to_append, dup_gen_to_refine = double_generator(dup_gen)
    for block in dup_gen_to_append:
        for letter, number in zip(alphabet, block):
            number_to_slug[number] += letter

    return number_to_slug

This does not look very elegant, as there is some code duplication in each step. I tried looping through a list of functions, as suggested by FMc, but for some reason that comes with some cost in performance. (That code is not shown here, but on Pastebin.)

I used the following code to generate a database with 112750 rows:

from string import ascii_uppercase as alphabet

db_list = []

for a, b in product(range(5), range(5)):
    row = {'name1': alphabet[a], 'name2': alphabet[b], 'born': '2000'}
    for _ in range(10):
        db_list.append(row)

for a, b, c in product(range(5, 20), range(5, 20), range(100)):
    row = {'name1': alphabet[a], 'name2': alphabet[b], 'born': str(1900 + c)}
    db_list.append(row)

for i, j in product(range(300), range(300)):
    row = {'name1': str(i) + 'x', 'name2': str(j) + 'y', 'born': '2000'}
    db_list.append(row)

long_database = {}
for i, row in enumerate(db_list):
    long_database[i] = row

The following code is to measure the performance of each approach:
(I modified all functions to take database as an argument, and to use ascii_lowercase.)

import time

for i, fun in enumerate([fun0, fun1, fun2, fun3, fun4]):
    start = process_time()
    result = fun(database)
    end = process_time()
    print(f'fun{i} took {end - start} seconds')
    if i == 0:
        first_result = result
    else:
        assert result == first_result

The results look always something like this:

fun0 took 0.147413774 seconds              # my initial code
fun1 took 0.20480099000000002 seconds      # by FMc
fun2 took 0.14875496700000002 seconds      # by 301_Moved_Permanently
fun3 took 0.09883650700000002 seconds      # this answer
fun4 took 0.13451846199999995 seconds      # like fun1 and fun3