Quersumme Performance

[rogerb]

Welcher Algorithmus ist performanter, um die Quersumme einer Zahl zu bilden?
Anders als bei der Ursprungsidee geht es hier nur darum die tatsächliche Quersumme einer Zahl zu bilden.

Nach dem Motto: Trau keiner Statistik die du nicht selbst gefälscht hast: Man muss die Anzahl der Ziffern nur genügend groß werden lassen um den bevorzugten Algorithmus gewinnen zu lassen.
Eigentlich ist der Unterschied aber sowieso nicht so gravierend.


testcode:
Beginnend mit einer einstelligen Zahl, werden für immer länger werdende Zahlen, werden wiederholt die Quersummen berechnet.

Code: Alles auswählen

import random
import string
import matplotlib.pyplot as plt

ITERATIONS = 10000
MAX_DIGITS = 40


def crosssum(number):
    return sum(map(int, str(number)))


def checksum(number):
    result = 0
    while number:
        number, remain = divmod(number, 10)
        result += remain
    return result


def generate_digits(length):
    test_digits = ""
    for _ in range(length):
        test_digits += random.choice(string.digits)
        yield int(test_digits)


def main():
    import timeit

    fig, ax = plt.subplots()
    ax.set_title(f"Testrun with {ITERATIONS} iterations and\na growing number of up to {MAX_DIGITS} digits")
    ax.set_xlabel("digits in number")
    ax.set_ylabel("time")
    ax.grid()

    for test_func in ["crosssum", "checksum"]:
        time_data = [
            timeit.timeit(f"{test_func}({test_number})", setup=f"from __main__ import {test_func}", number=ITERATIONS)
            for test_number in generate_digits(MAX_DIGITS)
        ]
        ax.plot(time_data, label=test_func)
    ax.legend()

    plt.show()


if __name__ == "__main__":
    main()

[imonbln]

@rogerb Super Arbeit und danke fürs Teilen. Auf meiner Maschine sehen die Zahlen ähnlich aus. Beide Varianten scheinen ungefähr gleich performant zu sein. Mir ist noch die Idee gekommen einen rekursiven Ansatz ins
Rennen zu schicken, der ist zwar wie erwartet erstmal langsam, kann aber mit Caching punkten, wenn oft Quersummen berechnet werden.

Code: Alles auswählen

import random
import functools
import string
import matplotlib.pyplot as plt

ITERATIONS = 10000
MAX_DIGITS = 40


def crosssum(number):
    return sum(map(int, str(number)))

    
def checksum(number):
    result = 0 
    while number:
        number, remain = divmod(number, 10)
        result += remain
    return result


def recursive(number):
    if number:
        number, remain = divmod(number, 10)
        return remain + recursive(number)
    return 0


@functools.lru_cache()
def recursive_cache(number):
    if number:
        number, remain = divmod(number, 10)
        return remain + recursive_cache(number)
    return 0


def generate_digits(length):
    test_digits = ""
    for _ in range(length):
        test_digits += random.choice(string.digits)
        yield int(test_digits)


def main():
    import timeit

    fig, ax = plt.subplots()
    ax.set_title(f"Testrun with {ITERATIONS} iterations and\na shuffled number of up to {MAX_DIGITS} digits")
    ax.set_xlabel("digits in number")
    ax.set_ylabel("time")
    ax.grid()

    for test_func in ["crosssum", "checksum", "recursive", "recursive_cache"]:
        time_data = [
            timeit.timeit(f"{test_func}({test_number})", setup=f"from __main__ import {test_func}", number=ITERATIONS)
            for test_number in generate_digits(MAX_DIGITS)
        ]
        ax.plot(time_data, label=test_func)
    ax.legend()

    plt.show()


if __name__ == "__main__":
    main()

[rogerb]

@Imonbln,

wow, das macht viel aus.
Dann kann auch noch mal nachlegen, aber wenn ich meine Variante recursiv umbaue, gefällt sie mir nicht mehr so gut.
Die Perfomance ist aber tatsächlich bei beiden recursiven Ansätzen identisch:

Code: Alles auswählen

import random
import functools
import string
import matplotlib.pyplot as plt

ITERATIONS = 10000
MAX_DIGITS = 40


def crosssum(number):
    return sum(map(int, str(number)))

@functools.lru_cache
def recursive_crosssum(number):
    if number < 10:
        return number
    number_str = str(number)
    return int(number_str[0]) + recursive_crosssum(int(number_str[1:]))

    
def checksum(number):
    result = 0 
    while number:
        number, remain = divmod(number, 10)
        result += remain
    return result


def recursive(number):
    if number:
        number, remain = divmod(number, 10)
        return remain + recursive(number)
    return 0


@functools.lru_cache()
def recursive_cache(number):
    if number:
        number, remain = divmod(number, 10)
        return remain + recursive_cache(number)
    return 0


def generate_digits(length):
    test_digits = ""
    for _ in range(length):
        test_digits += random.choice(string.digits)
        yield int(test_digits)


def main():
    import timeit

    fig, ax = plt.subplots()
    ax.set_title(f"Testrun with {ITERATIONS} iterations and\na shuffled number of up to {MAX_DIGITS} digits")
    ax.set_xlabel("digits in number")
    ax.set_ylabel("time")
    ax.grid()

    test_digits = list(generate_digits(MAX_DIGITS))
    test_funcs = ["crosssum", "recursive_crosssum", "checksum", "recursive", "recursive_cache"]
    for test_func in test_funcs:
        time_data = [
            timeit.timeit(f"{test_func}({test_number})", setup=f"from __main__ import {test_func}", number=ITERATIONS)
            for test_number in test_digits
        ]
        ax.plot(time_data, label=test_func)
    ax.legend()

    plt.show()


if __name__ == "__main__":
    main()

[imonbln]

@rogerb,

Die Quersumme scheint gut von Caching profitieren zu können, wenn man einen rekursiven Ansatz nimmt.

Was deine Implementierung angeht, erst dachte ich das es vermutlich besser ist, mit negativen Indexen zu arbeiten, da die Zahlen an der rechten Seite schneller rotieren, aber nachdem ich es ausprobiert habe, stellte ich fest das nichts ändert. Interessant finde ich die Grafik, der beiden rekursiven Algorithmen ohne Caching, hier hat die checksum, ein besseres Verhalten, was vielleicht ein Anzeichen ist, dass Sie bei einem Cache miss ein kleines bisschen schneller ist.

[bords0]

Wenn man 10.000 mal die Quersumme der gleichen Zahl berechnet, ist das immer schnell, wenn man einen cache benutzt. Egal bei welcher der Funktionen.

Es wird immer nur das erste Mal gerechnet, dann nicht mehr.

Wenn man jedesmal mit einer anderen zufälligen Zahl rechnet, ändert sich das.

(Zusätzlich führt die spezielle Konstruktion der "zufälligen" Zahlen dazu, dass der zweite Aufruf (mit der um eine Stelle kürzeren Zahl) schon im Cache liegt. Das ist aber irrelevant ggü. dem Effekt, 10.000 mal die gleiche Zahl zu berechnen.)