Divide-and-conquer the GoF design patterns with a DRY KISS?

You learned some programming skills and can write code in one or maybe even two programming languages? Congratulations, this is amazing and a very useful skill! But as you continue on your journey, you may find yourself wondering how to find “better” solutions to a coding problem - depending on the context, this means shorter, faster, more easily reusable or more readable code.

Or you may stumble across concepts about how to write code - and they are often hidden behind acronyms such as “DRY” or “KISS”. While no single concept will help you in every situation, they can be good guardrails for your coding journey. So let’s take a look at some very popular ones!

Helpful concepts and starting points for writing better code

DRY

Writing DRY code means “Don’t Repeat Yourself”. Thomas and Hunt (1999/2019), who coined the term, applied this not only to code itself, but also to databases or documentation. The key is that each piece of information is stated once and only once, e.g. in a variable, a function, or through data normalisation.

KISS

The KISS principle is even older and comes from the US Navy: Keep It Simple, Stupid. Simplicity is the main design principle here, often easier said than done.

Divide and conquer

Literally ancient is the maxim of “divide and conquer” (often attributed to Philip II of Macedon or Julius Caesar). In the programming world, the term describes an algorithm that breaks down a given problem into smaller, more manageable parts, solving them individually, and then combining the solutions to solve the overall problem. This approach is widely used in algorithm design and is known for its efficiency and scalability.

Here’s a classic example of divide and conquer in action with binary search. Binary search is used to find the position of a target value within a sorted array. Here’s how it works:

Divide: Start with the entire array and divide it into two halves.
Conquer: Compare the target value with the middle element of the array. If they match, the search is complete. If the target value is less than the middle element, search the left half; otherwise, search the right half.
Combine: Repeat the process on the selected half until the target value is found or the array is empty.

def binary_search(data, target):
    """Find the index of an element in a collection of data.

    Args:
        data:
            A collection of data that is indexable by position.
            Its elements must be comparable, 
            and the data is assumed to be sorted in ascending order
        target: the element to look for
    Returns:
        The index of the target or `None` if the target is not present.
    """

    # Base case: if there is no data,
    # the target will not be there
    if not data:
        return None
    
    # Base case: if there is only one element
    # it either is the target or it isn't
    if len(data) == 1:
        return (
            0 if data[0] == target
            else None
        )
    
    # Find the middle index
    middle_index = len(data) // 2
    
    # Check if the middle element is the target
    if data[middle_index] == target:
        return middle_index

    elif data[middle_index] > target:
        # If the target is smaller, search the left half
        return binary_search(data[:middle_index], target)
    else:
        # If the target is larger, search the right half
        # Do not forget to account for the return value of the recursion
        # being offset by the middle index
        offset_index = binary_search(data[middle_index:], target)
        return (
            None if offset_index is None
            else offset_index + middle_index
        )

# Example usage
sorted_array = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
for target_value in [1, 7, 99]:
    result = binary_search(sorted_array, target_value)

    if result is not None:
        print(f"Element {target_value} found at index {result}.")
    else:
        print(f"Element {target_value} not found in the array.")

In this example one could also add in parallelization and would end up with another famous approach: Map-Reduce.

While binary search is a common divide and conquer application at the algorithmic level, the concept also works at a higher architectural level. For example: I need to build a multi-day population simulation with statistical evaluation Instead of trying to build the whole multi-day population simulation at once, I solve the smaller tasks:

simulate one day
collect and store the data from a one day simulation
extend it to several days by repeating 1. and 2.
figure out independently how to do a statistical analysis of a dataset
put all the pieces together

This is - what were the odds? - the example we use in the First Steps in Python course.

GoF design patterns

A more detailed approach comes with the 23 design patterns by the four authors Gamma, Helm, Johnson and Vlissides (1994), hence the name Gang of Four or GoF for short. They describe three categories of design patterns that are still valid today: Creational, structural and behavioral patterns. Very common in Java is the Factory (Method) Design Pattern - you may even be using it without realising its origin.

Intrigued? You can find a lot more resources for research software engineering in this awesome RSE GitHub repository curated by our consulting team. You can also check for past and future training courses in our Education & Training page, like the first steps in Python we mentioned earlier.

Helmholtz Software Engineering Consulting

Still need support with a concrete code project? HIFIS offers free-of-charge consulting as a service to research groups under the Helmholtz umbrella. Submit your request through a short questionnaire or find out more about the process in the HIFIS Consulting Handbook.

Questions? Comments? Suggestions?

Feel free to contact us!

Better Coding: some starting points

Authors:

Posted on:

Categories:

Tags: