Code Optimization

Three fundamental principles:
    1. Don't optimize too early
        Many developers focus on performance optimization from the very beginning. However,
        "it is much easier to make a correct program fast than to make a fast program correct."
        The prerequisite for optimization is working code. Premature optimization may cause you
        to miss the overall performance picture — don't get the priorities backwards before you
        have a global view.
        
    2. Weigh the cost of optimization
        Optimization has a cost. Eliminating every performance issue is nearly impossible.
        The typical trade-off is time vs. space, or space vs. time. Development cost must also
        be considered.
        
    3. Don't optimize code that doesn't matter
        If you optimize every part of your code, those modifications will make the code hard
        to read and understand. If your code is slow, first find where it is slow — usually
        the inner loop — and focus optimization efforts there. A small time loss elsewhere
        has no meaningful impact.

# Not recommended. Runtime: 26.8 seconds
    import math

    size = 10000
    for x in range(size):
    for y in range(size):
    z = math.sqrt(x) + math.sqrt(y)
            
    Many developers who start writing Python scripts habitually write code at the global level,
    as in the example above. Because global and local variables are implemented differently,
    code defined at the global scope runs noticeably slower than code inside a function.
    Placing script statements inside a function typically yields a 15-30% speed improvement.
    
# Recommended. Runtime: 20.6 seconds
    import math

    def main():  # Define inside a function to reduce global variable usage
        size = 10000
        for x in range(size):
            for y in range(size):
                z = math.sqrt(x) + math.sqrt(y)

    main()

# Not recommended. Runtime: 14.5 seconds
    import math

    def computeSqrt(size: int):
        result = []
        for i in range(size):
            result.append(math.sqrt(i))
        return result

    def main():
        size = 10000
        for _ in range(size):
            result = computeSqrt(size)

    main()
    
    Every use of . (the attribute access operator) triggers special methods like __getattribute__()
    and __getattr__(), which perform dictionary operations and add overhead. Using a "from import"
    statement eliminates this attribute lookup.
    
# First optimization. Runtime: 10.9 seconds
    from math import sqrt

    def computeSqrt(size: int):
        result = []
        for i in range(size):
            result.append(sqrt(i))  # Avoids math.sqrt lookup
        return result

    def main():
        size = 10000
        for _ in range(size):
            result = computeSqrt(size)

    main()
    
    As noted in the section above, local variable lookups are faster than global ones.
    For the frequently accessed variable sqrt, assigning it to a local variable speeds things up.
    
# Second optimization. Runtime: 9.9 seconds
    import math

    def computeSqrt(size: int):
        result = []
        sqrt = math.sqrt  # Assign to a local variable
        for i in range(size):
            result.append(sqrt(i))  # Avoids math.sqrt lookup
        return result

    def main():
        size = 10000
        for _ in range(size):
            result = computeSqrt(size)

    main()
    
    Besides math.sqrt, the computeSqrt function also uses . for list's append method.
    Assigning that method to a local variable eliminates all . usage inside the for loop.
    
# Recommended. Runtime: 7.9 seconds
    import math

    def computeSqrt(size: int):
        result = []
        append = result.append
        sqrt = math.sqrt    # Assign to a local variable
        for i in range(size):
            append(sqrt(i))  # Avoids both result.append and math.sqrt lookups
        return result

    def main():
        size = 10000
        for _ in range(size):
            result = computeSqrt(size)

    main()

# Not recommended. Runtime: 10.4 seconds
    import math
    from typing import List

    class DemoClass:
        def __init__(self, value: int):
            self._value = value

        def computeSqrt(self, size: int) -> List[float]:
            result = []
            append = result.append
            sqrt = math.sqrt
            for _ in range(size):
                append(sqrt(self._value))
            return result

    def main():
        size = 10000
        for _ in range(size):
            demo_instance = DemoClass(size)
            result = demo_instance.computeSqrt(size)

    main()
    
    The same principle applies to class attributes. Accessing self._value is slower than
    accessing a local variable. Assigning a frequently accessed class attribute to a local
    variable improves speed.

# Recommended. Runtime: 8.0 seconds
    import math
    from typing import List

    class DemoClass:
        def __init__(self, value: int):
            self._value = value

        def computeSqrt(self, size: int) -> List[float]:
            result = []
            append = result.append
            sqrt = math.sqrt
            value = self._value
            for _ in range(size):
                append(sqrt(value))  # Avoids self._value lookup
            return result

    def main():
        size = 10000
        for _ in range(size):
            demo_instance = DemoClass(size)
            demo_instance.computeSqrt(size)

    main()

# Not recommended. Runtime: 0.55 seconds
    class DemoClass:
        def __init__(self, value: int):
            self.value = value

        @property
        def value(self) -> int:
            return self._value

        @value.setter
        def value(self, x: int):
            self._value = x

    def main():
        size = 1000000
        for i in range(size):
            demo_instance = DemoClass(size)
            value = demo_instance.value
            demo_instance.value = i

    main()
    
    Any time you wrap code with additional processing layers (decorators, property accessors,
    descriptors), you make it slower. In most cases, you should reconsider whether defining
    property accessors is necessary. Using getter/setter functions is often a habit carried
    over from C/C++ style. If it is truly unnecessary, use simple attributes instead.

# Recommended. Runtime: 0.33 seconds
    class DemoClass:
        def __init__(self, value: int):
            self.value = value  # Avoids unnecessary property accessors

    def main():
        size = 1000000
        for i in range(size):
            demo_instance = DemoClass(size)
            value = demo_instance.value
            demo_instance.value = i

    main()

# Not recommended. Runtime: 6.5 seconds
    def main():
        size = 10000
        for _ in range(size):
            value = range(size)
            value_list = [x for x in value]
            square_list = [x * x for x in value_list]

    main()
    value_list above is completely unnecessary and creates an unnecessary data structure or copy.
    
# Recommended. Runtime: 4.8 seconds
    def main():
        size = 10000
        for _ in range(size):
            value = range(size)
            square_list = [x * x for x in value]  # Avoids unnecessary copy

    main()
    Another situation is being overly paranoid about Python's data-sharing mechanism without
    truly understanding or trusting Python's memory model, and misusing functions like
    copy.deepcopy(). Usually such copy operations can be removed.
    
    Swapping values without a temporary variable:
    
# Not recommended. Runtime: 0.07 seconds
    def main():
        size = 1000000
        for _ in range(size):
            a = 3
            b = 5
            temp = a
            a = b
            b = temp

    main()
    The code above uses a temporary variable temp to swap values. Without an intermediate
    variable, the code is more concise and runs faster.
    
# Recommended. Runtime: 0.06 seconds
    def main():
        size = 1000000
        for _ in range(size):
            a = 3
            b = 5
            a, b = b, a  # No intermediate variable needed

    main()
    
    Use join instead of + for string concatenation:
    
# Not recommended. Runtime: 2.6 seconds
    import string
    from typing import List

    def concatString(string_list: List[str]) -> str:
        result = ''
        for str_i in string_list:
            result += str_i
        return result

    def main():
        string_list = list(string.ascii_letters * 100)
        for _ in range(10000):
            result = concatString(string_list)

    main()
    
    When using a + b for string concatenation, because Python strings are immutable objects,
    a new memory block is allocated and both a and b are copied into it. Concatenating N strings
    this way produces N-1 intermediate strings, each requiring a new memory allocation and copy.
    join(), by contrast, first calculates the total memory needed, allocates it once, then copies
    each string element in — far more efficient.

# Recommended. Runtime: 0.3 seconds
    import string
    from typing import List

    def concatString(string_list: List[str]) -> str:
        return ''.join(string_list)  # Use join instead of +

    def main():
        string_list = list(string.ascii_letters * 100)
        for _ in range(10000):
            result = concatString(string_list)

    main()

# Not recommended. Runtime: 0.05 seconds
    from typing import List

    def concatString(string_list: List[str]) -> str:
        abbreviations = {'cf.', 'e.g.', 'ex.', 'etc.', 'flg.', 'i.e.', 'Mr.', 'vs.'}
        abbr_count = 0
        result = ''
        for str_i in string_list:
            if str_i in abbreviations:
                result += str_i
        return result

    def main():
        for _ in range(10000):
            string_list = ['Mr.', 'Hat', 'is', 'Chasing', 'the', 'black', 'cat', '.']
            result = concatString(string_list)

    main()
    
    Short-circuit evaluation means: for "if a and b", if a is False, the expression returns
    immediately without evaluating b. For "if a or b", if a is True, the expression returns
    immediately without evaluating b. To save time, for "or" statements, place the variable
    more likely to be True first; for "and" statements, put conditions more likely to be False
    first.

# Recommended. Runtime: 0.03 seconds
    from typing import List

    def concatString(string_list: List[str]) -> str:
        abbreviations = {'cf.', 'e.g.', 'ex.', 'etc.', 'flg.', 'i.e.', 'Mr.', 'vs.'}
        abbr_count = 0
        result = ''
        for str_i in string_list:
            if str_i[-1] == '.' and str_i in abbreviations:  # Exploit short-circuit evaluation
                result += str_i
        return result

    def main():
        for _ in range(10000):
            string_list = ['Mr.', 'Hat', 'is', 'Chasing', 'the', 'black', 'cat', '.']
            result = concatString(string_list)

    main()

Use for loops instead of while loops:
# Not recommended. Runtime: 6.7 seconds
    def computeSum(size: int) -> int:
        sum_ = 0
        i = 0
        while i < size:
            sum_ += i
            i += 1
        return sum_

    def main():
        size = 10000
        for _ in range(size):
            sum_ = computeSum(size)

    main()
   
    Python's for loop is noticeably faster than while loops.
    
# Recommended. Runtime: 4.3 seconds
    def computeSum(size: int) -> int:
        sum_ = 0
        for i in range(size):  # Use for loop instead of while
            sum_ += i
        return sum_

    def main():
        size = 10000
        for _ in range(size):
            sum_ = computeSum(size)

    main()
    
Use implicit for loops instead of explicit for loops:
Taking the above example further, an implicit for loop replaces the explicit one:
# Recommended. Runtime: 1.7 seconds
    def computeSum(size: int) -> int:
        return sum(range(size))  # Implicit for loop replaces explicit for loop

    def main():
        size = 10000
        for _ in range(size):
            sum = computeSum(size)

    main()
    
Reduce computation in the inner for loop:
# Not recommended. Runtime: 12.8 seconds
    import math

    def main():
        size = 10000
        sqrt = math.sqrt
        for x in range(size):
            for y in range(size):
                z = sqrt(x) + sqrt(y)

    main()
    In the code above, sqrt(x) is inside the inner loop and gets recomputed on every iteration,
    adding unnecessary overhead.
    
# Recommended. Runtime: 7.0 seconds
    import math

    def main():
        size = 10000
        sqrt = math.sqrt
        for x in range(size):
            sqrt_x = sqrt(x)  # Reduce computation inside the inner loop
            for y in range(size):
                z = sqrt_x + sqrt(y)

    main()

    numba can JIT-compile Python functions to machine code, dramatically improving execution speed.
    More information about numba: http://numba.pydata.org/


# Recommended. Runtime: 0.62 seconds
    import numba

    @numba.jit
    def computeSum(size: float) -> int:
        sum = 0
        for i in range(size):
            sum += i
        return sum

    def main():
        size = 10000
        for _ in range(size):
            sum = computeSum(size)

    main()

    Python's built-in data structures — str, tuple, list, set, dict — are all implemented in C
    and are very fast. Writing your own data structure to match their performance is nearly
    impossible.

    list is similar to std::vector in C++: a dynamic array. It pre-allocates memory; when the
    pre-allocated space is exhausted and new elements are added, it allocates a larger block,
    copies all existing elements, destroys the old block, then inserts the new element. Deletion
    works similarly. If there are frequent additions and deletions involving large numbers of
    elements, list efficiency is low. Consider using collections.deque — a double-ended queue
    that supports O(1) insertions and deletions at both ends.

    list's search operation is also expensive. If you frequently search for elements in a list
    or need ordered access, use the bisect module to maintain a sorted list and perform binary
    search for better lookup efficiency.

    Another common need is finding the minimum or maximum value. The heapq module converts a
    list into a heap so that getting the minimum value takes O(1) time.

    The time complexities for common Python data structure operations are listed here:
        TimeComplexity - Python Wiki
        wiki.python.org