Programm ist viel zu langsam

[rogerb]

In diesem Fall macht eigentlich nur time.perf_counter() Sinn, da time.perf-counter() für kurze Zeitabstände wie hier, gedacht ist. So ist es ja auch in PEP 418 beschrieben.

Solche Aussagen finde ich bestens Falls verwirrend, in Bezug auf PEP 418 sogar eigentlich falsch:

Und ich habe `time.time()` mal durch `time.monotonic()` ersetzt, was man zum messen von Zeiten bevorzugen sollte.

[__blackjack__]

@rogerb: Finde ich nicht. Performance Counter sind für mich was zum messen um heraus zu finden ob was zu langsam ist/Lösungen zu vergleichen. Wenn mich nur die Laufzeit von einem Programm interessiert, dann ist `time()` eigentlich das Mittel der Wahl, wenn das halt nicht das Problem hätte nicht immer monoton zu sein. Deswegen gibt es ja `monotonic()`. Wofür wäre denn `monotonic()` denn sonst da?

[rogerb]

@__blackjack__,

Performance Counter sind für mich was zum messen um heraus zu finden ob was zu langsam ist/Lösungen zu vergleichen

Es geht doch hier um die Verbesserung der Laufzeit.

Auf meiner Ubuntu VM bekomme ich:

Code: Alles auswählen

import time                                                                                                                                                                                                

In [2]: time.get_clock_info("perf_counter")                                                                                                                                                                        
Out[2]: namespace(adjustable=False, implementation='clock_gettime(CLOCK_MONOTONIC)', monotonic=True, resolution=1e-09)

In [3]: time.get_clock_info("monotonic")                                                                                                                                                                           
Out[3]: namespace(adjustable=False, implementation='clock_gettime(CLOCK_MONOTONIC)', monotonic=True, resolution=1e-09)

Auf meinem W10 Rechner bekomme ich:

Code: Alles auswählen

In [1]: import time

In [2]: time.get_clock_info("perf_counter")
Out[2]:
namespace(implementation='QueryPerformanceCounter()',
          monotonic=True,
          adjustable=False,
          resolution=1e-07)

In [3]: time.get_clock_info("monotonic")
Out[3]:
namespace(implementation='GetTickCount64()',
          monotonic=True,
          adjustable=False,
          resolution=0.015625)

Da sowohl time.perf_counter() als auch time.monotonic() monton sind, muss man sich nur zwischen den beiden entscheiden.
Was man noch berücksichtigen könnte sind die zugrundeliegenden Implementierungen des jeweiligen Betriebssystems.

Da man aber wohl in den meisten Fällen time.perf_counter() Messungen mit vorherigen time.perf_counter() Messungen auf dem gleichen System vergleichen würde. Ist die entscheidende Frage: Bin ich mit meiner Änderung schneller oder langsamer geworden?
Das gleiche gilt für time.monotonic() Messungen. Schneller oder langsamer?


Also was nimmt man nun?
Unter Windows könnte man argumentieren, dass die Auflösung von time.per_counter() besser ist.
Dafür ist die Drift bei time.monotonic() aber geringer. Daher ja auch der Hinweis, dass man time.perf_counter() nur für kurze Messungen verwenden sollte. Aber was ist kurz?
Man sollte darauf achten, dass man Messungen der gleichen Funktion vergleicht.
Ansonsten denke ich, ist es technisch gesehen, egal.

Da aber time.perf_counter() als das ausgewiesene Werkzeug der Wahl für solche Aufgaben gilt, sollte man meiner Meinung nach auch dabei bleiben.

PEP 418 zu den Anwendungsfällen:

time.monotonic(): timeout and scheduling, not affected by system clock updates
time.perf_counter(): benchmarking, most precise clock for short period
time.process_time(): profiling, CPU time of the process

[bords0]

@bords0: Danke. Diese Teilmengen herauszuziehen, das wäre genau die Kunst. Geht das vielleicht mit einer Funktion der Bibliothek "collections"? Gruß, Strawk

itertools hat ein Rezept für powerset

[__blackjack__]

Was es im externen `more_itertools` dann schon fertig gibt, damit man sich das nicht immer selbst kochen muss.

[rogerb]

Ich hatte zwischenzeitlich __blackjacks__ Ansatz mit dem Dictionary um itertools.combinations erweitert.

Außerdem gibt es jetzt noch die Möglichkeit den Dictionary als Pickle zu speichern. Damit spart man ca. 50% der Zeit.

Code: Alles auswählen

#!/usr/bin/env python3
import time
from collections import defaultdict
from itertools import combinations
from pathlib import Path
import pickle

ROOTFOLDER = "scrabble"
PICKLE_PATH = Path(ROOTFOLDER, "lookup_table.p")

# https://gist.github.com/MarvinJWendt/2f4f4154b8ae218600eb091a5706b5f4
DICTIONARY_PATH = Path(ROOTFOLDER, "wordlist-german.txt")

def make_canonical_form(word):
    return "".join(sorted(word))


def write_lookup_table(pickle_object):
    with PICKLE_PATH.open("wb") as pickle_file:
        pickle.dump(pickle_object, pickle_file)


def read_lookup_table():
    if PICKLE_PATH.exists():
        with PICKLE_PATH.open("rb") as pickle_file:
            return pickle.load(pickle_file)
    else:
        return dict()


def make_lookup_table():
    sorted_characters_to_words = defaultdict(set)
    with DICTIONARY_PATH.open(encoding="utf-8") as lines:
        for line in lines:
            word = line.strip().lower()
            sorted_characters_to_words[make_canonical_form(word)].add(word)
    return sorted_characters_to_words


def get_lookup_table():
    lookup_table = read_lookup_table()
    if not lookup_table:
        lookup_table = make_lookup_table()
        write_lookup_table(lookup_table)
    return lookup_table


def main():
    needle = "qwertz"
    look_up_table = get_lookup_table()

    word_parts = {
        make_canonical_form("".join(part))
        for n in range(2, len(needle) + 1)
        for part in combinations(needle, n)
    }

    results = [word for part in word_parts for word in look_up_table[part]]
    print(results)


if __name__ == "__main__":
    start = time.perf_counter()
    main()
    runtime = time.perf_counter() - start
    print(f"program took {runtime:5.3f} seconds")


"""
Ausgabe vor dem pickeln:
['er', 're', 'wert', 'rtw', 'wz', 'qwertz', 'wez', 'we', 'qr', 'terz', 'rwe', 'wer', 'erz']
program took 8.625 seconds

Ausgaben nach dem pickeln:
['qr', 'erz', 'wez', 'rtw', 'we', 're', 'er', 'wz', 'wert', 'wer', 'rwe', 'terz', 'qwertz']
program took 4.265 seconds
"""

[LukeNukem]

In diesem Fall macht eigentlich nur time.perf_counter() Sinn, da time.perf-counter() für kurze Zeitabstände wie hier, gedacht ist. So ist es ja auch in PEP 418 beschrieben.

Das steht in PEP 418, ja. Aber ich habe Probleme mit solchen Heckenausdrücken. Was genau ist ein "kurzer Zeitabstand"?

[rogerb]

@LukeNukem,

wenn ich die PEP richtig verstanden habe, stellt sie einen Leitfaden dar und spricht Empfehlungen aus. Sie erinnert mich daran, dass die gemessene Zeit mehr und mehr von der real verstrichenen Zeit abweicht. Dann gibt sie mir die Freiheit selbst zu entscheiden ob das bei meinem Vorhaben eine Rolle spielt oder nicht. Ich finde diese Wortwahl erfrischend, ungenau.

[__deets__]

Ich fände einen Hinweis darauf, dass das lediglich unter Windows relevant ist, durchaus angebracht. Sonst ist das alles der gleiche Aufruf. Und auch eine Einordnung, bei welchen Größenordnungen man den einsetzen sollte, und ab wann er Probleme macht. Warum muss ich das erst selbst rausfinden? Und komme im Zweifel erst nach Stunden drauf?

[rogerb]

@__deets__, ich verstehe nicht was du meinst. Die PEP 418 liefert eine Menge an Informationen zum Verhalten der Timer in Bezug auf das jeweilige Betriebssystem.

[LukeNukem]

wenn ich die PEP richtig verstanden habe, stellt sie einen Leitfaden dar und spricht Empfehlungen aus. Sie erinnert mich daran, dass die gemessene Zeit mehr und mehr von der real verstrichenen Zeit abweicht. Dann gibt sie mir die Freiheit selbst zu entscheiden ob das bei meinem Vorhaben eine Rolle spielt oder nicht. Ich finde diese Wortwahl erfrischend, ungenau.

Hallo Rogerb,

hm, ich weiß nicht Recht, es gibt ja zwei Möglichkeiten: entweder, die gemessene Zeit hat eine (mehr oder weniger konstante) Drift. Dann bin ich in vielen Fällen, insbesondere beim Profiling, fein 'raus, denn dabei geht es ja eher darum, die langsamsten Codeabschnitte zu finden. Wenn es um die Einhaltung von SLAs geht, sieht die Sache natürlich anders aus... Die andere Möglichkeit ist, daß der Counter irgendwann überläuft und wieder bei 0 startet, was für beide Anwendungsfälle ein No-Go wäre. Aber was ist der Grund für diese Einschränkung "short", die zwar im PEP 418 und in der Internet-Dokumentation, nicht aber in der lokalen Dokumentation steht? Und wie lange ist "short"? Wenn ich als Vergleich das Alter des Universums nehme, dann sind 10.000 und sogar 100.000 Jahre sicherlich noch "short".

Nun, im Endeffekt macht es zumindest unter Nicht-Windows-Systemen keinen Unterschied, denn sowohl time.monotonic() als auch time.perf_counter() geben genau dasselbe zurück und unterscheiden sich daher in technischer Hinsich kein bisschen. Trotzdem würde ich aus Gründen der Lesbar- und Verständlichkeit für Zeitmessungen immer time.perf_counter() nehmen, aber das ist wohl Geschmacks- und Gewohnheitssache...

[rogerb]

@LukeNukem,

Trotzdem würde ich aus Gründen der Lesbar- und Verständlichkeit für Zeitmessungen immer time.perf_counter() nehmen,

Genau, das war ja auch mein Fazit.
Besonders, wenn man seinen Code mit anderen teilt, ist es eine gute Idee.