Programm ist viel zu langsam

[Strawk]

Hallo!
Dieses Programm ist eindeutig zu langsam; hat jemand eine zündende Beschleunigungsidee?

Code: Alles auswählen

#!/usr/bin/env python
# coding: utf-8 -*-
#-------------------------------------------------------------------------------
# Name:        scrabble.py
# Purpose:     create german words with 7 example letters
#
# Author:      Thomas Graeber
#
# Created:     12/28/2020
# License:     n/a
#-------------------------------------------------------------------------------
"""
    create german words with 7 example letters
    and print them out for use in the board game "Scrabble"
    
    contains functions:
        convert                    -       converts a list of letters to a word
        calc_permutations          -       calculates all possible orders of the letters
                                           and thus create possible words
"""
from itertools import chain, permutations

def convert(s): 
    """
    converts a list of letters to a word
       
    In:
    s - word-list
        
    Out:
    word
    """
    word = "" 
    for x in s: 
        word += x  
    return word 

def calc_permutations(example_letters):
    """
    calculates all possible orders of the letters
    and thus create possible words
       
    In:
    example_letters
        
    Out:
    all_permutations
    """
    all_permutations = list(
        chain.from_iterable(
            permutations(example_letters, length)
            for length in range(1, len(example_letters) + 1)
        )
    )
    return all_permutations

def main():
    all_permutations = calc_permutations(['a', 'e', 'b', 'k', 'l', 'm', 'e'])
    
    # initialize list to avoid double entries
    results = []
    # initialize counter to count the results
    counter = 0
    
    for item in all_permutations:
        possible_word = convert(item) 
        if possible_word[0] == 'a' or possible_word[0] == 'A':
            wordlist = open('wordbooks/german_a.dic', 'r')
        elif possible_word[0] == 'b' or possible_word[0] == 'B':
            wordlist = open('wordbooks/german_b.dic', 'r')
        elif possible_word[0] == 'c' or possible_word[0] == 'C':
            wordlist = open('wordbooks/german_c.dic', 'r')
        elif possible_word[0] == 'd' or possible_word[0] == 'D':
            wordlist = open('wordbooks/german_d.dic', 'r')
        elif possible_word[0] == 'e' or possible_word[0] == 'E':
            wordlist = open('wordbooks/german_e.dic', 'r')
        elif possible_word[0] == 'f' or possible_word[0] == 'F':
            wordlist = open('wordbooks/german_f.dic', 'r')
        elif possible_word[0] == 'g' or possible_word[0] == 'G':
            wordlist = open('wordbooks/german_g.dic', 'r')
        elif possible_word[0] == 'h' or possible_word[0] == 'H':
            wordlist = open('wordbooks/german_h.dic', 'r')
        elif possible_word[0] == 'i' or possible_word[0] == 'I':
            wordlist = open('wordbooks/german_i.dic', 'r')
        elif possible_word[0] == 'j' or possible_word[0] == 'J':
            wordlist = open('wordbooks/german_j.dic', 'r')
        elif possible_word[0] == 'k' or possible_word[0] == 'K':
            wordlist = open('wordbooks/german_k.dic', 'r')
        elif possible_word[0] == 'l' or possible_word[0] == 'L':
            wordlist = open('wordbooks/german_l.dic', 'r')
        elif possible_word[0] == 'm' or possible_word[0] == 'M':
            wordlist = open('wordbooks/german_m.dic', 'r')
        elif possible_word[0] == 'n' or possible_word[0] == 'N':
            wordlist = open('wordbooks/german_n.dic', 'r')
        elif possible_word[0] == 'o' or possible_word[0] == 'O':
            wordlist = open('wordbooks/german_o.dic', 'r')
        elif possible_word[0] == 'p' or possible_word[0] == 'P':
            wordlist = open('wordbooks/german_p.dic', 'r')
        elif possible_word[0] == 'q' or possible_word[0] == 'Q':
            wordlist = open('wordbooks/german_q.dic', 'r')
        elif possible_word[0] == 'r' or possible_word[0] == 'R':
            wordlist = open('wordbooks/german_r.dic', 'r')
        elif possible_word[0] == 's' or possible_word[0] == 'S':
            wordlist = open('wordbooks/german_s.dic', 'r')
        elif possible_word[0] == 't' or possible_word[0] == 'T':
            wordlist = open('wordbooks/german_t.dic', 'r')
        elif possible_word[0] == 'u' or possible_word[0] == 'U':
            wordlist = open('wordbooks/german_u.dic', 'r')
        elif possible_word[0] == 'v' or possible_word[0] == 'V':
            wordlist = open('wordbooks/german_v.dic', 'r')
        elif possible_word[0] == 'w' or possible_word[0] == 'W':
            wordlist = open('wordbooks/german_w.dic', 'r')
        elif possible_word[0] == 'x' or possible_word[0] == 'X':
            wordlist = open('wordbooks/german_x.dic', 'r')
        elif possible_word[0] == 'y' or possible_word[0] == 'Y':
            wordlist = open('wordbooks/german_y.dic', 'r')
        elif possible_word[0] == 'z' or possible_word[0] == 'Z':
            wordlist = open('wordbooks/german_z.dic', 'r')
        elif possible_word[0] == 'ä' or possible_word[0] == 'Ä':
            wordlist = open('wordbooks/german_ae.dic', 'r')
        elif possible_word[0] == 'ö' or possible_word[0] == 'Ö':
            wordlist = open('wordbooks/german_oe.dic', 'r')
        elif possible_word[0] == 'ü' or possible_word[0] == 'Ü':
            wordlist = open('wordbooks/german_ue.dic', 'r')
    
        for zeile in wordlist:
            # [:-1] erases the line feed
            if zeile[:-1] == possible_word or zeile[:-1] == possible_word.capitalize():
                # avoid double entries
                if zeile not in results:
                    counter += 1
                    print(str(counter) + ": " + zeile)
                    results.append(zeile)
    
        wordlist.close()
    
if __name__ == "__main__":
    main()

Grüße, Strawk

[Sirius3]

`convert` ist einfach nur ein "".join(s).
Eine if-Kaskade mit 29 quasi gleichen Blöcken ist unsinnig kompliziert. Erstens würde man nur den Dateinamen ermitteln und das open ordentlich in einen with-Block zu packen. Zweitens würde man den Dateinamen nach dem offensichtlichen Muster generieren.
Schneller ist es, einfach alles einzulesen und in ein Set zu verwandeln.
Das zeile[:-1] ist fehlerhaft, falls die letzte Zeile nicht mit einem Zeileendezeichen abgeschlossen wird.
`counter` ist doch nichts anderes als die Länge von `result`. Strings setzt man nicht mit + zusammen, sondern benutzt Formatstrings.

Code: Alles auswählen

from pathlib import Path
WORDBOOKS = Path('wordbooks')

def main():
    all_permutations = calc_permutations(['a', 'e', 'b', 'k', 'l', 'm', 'e'])
    all_words = set()
    for filename in WORDBOOKS.glob('german_*,dic'):
        with filename.open(encoding="utf8") as lines:
            all_words.update(line.strip() for line in lines)

    results = set()
    for item in all_permutations:
        word = "".join(item)
        for possible_word in [word, word.capitalize()]:
            if possible_word in all_words:
                if possible_word not in results:
                    results.add(possible_word)
                    print(f"{len(results}: possible_word")

[__blackjack__]

@Strawk: Das mit den Permutationen ist ziemlich unsinnig ineffizient. Ich würde die Worte beim einlesen auch gleich in Kleinbuchstaben wandeln und in ein Wörterbuch stecken wo das ”sortierte” Wort, also dessen Buchstaben, auf eine Menge mit Worten abgebildet wird die ”sortiert” den Schlüssel ergeben. Dann sortiert man die vorgegebenen Buchstaben auch so und kann über den Schlüssel auf alle Worte zugreifen die aus diesen Buchstaben gebildet werden können.

[Strawk]

@Sirius3: Ein paar Flüchtigkeitsfehler deinerseits habe ich glattgebügelt; möglicherweise hattest du den Code bei dir nicht getestet. Aber das Ergebnis ist überzeugend: 0,021 Minuten statt 8 Minuten. Der Code sieht bei mir jetzt so aus:

Code: Alles auswählen

# coding: utf-8 -*-
"""
Created on Mon Dec 28 19:49:51 2020

@author: User
"""

import time
from pathlib import Path
from itertools import chain, permutations

WORDBOOKS = Path('wordbooks')

def calc_permutations(example_letters):
    """
    calculates all possible orders of the letters
    and thus create possible words
       
    In:
    example_letters
        
    Out:
    all_permutations
    """
    all_permutations = list(
        chain.from_iterable(
            permutations(example_letters, length)
            for length in range(1, len(example_letters) + 1)
        )
    )
    return all_permutations

def main():
    all_permutations = calc_permutations(['a', 'e', 'b', 'k', 'l', 'm', 'e'])
    all_words = set()
    for filename in WORDBOOKS.glob('german_*.dic'):
        with filename.open() as lines:
            all_words.update(line.strip() for line in lines)

    results = set()
    for item in all_permutations:
        word = "".join(item)
        for possible_word in [word, word.capitalize()]:
            if possible_word in all_words:
                if possible_word not in results:
                    results.add(possible_word)
                    print((f"{len(results)}:"), possible_word)

if __name__ == "__main__":
    start = time.time()
    main()
    ende = time.time()
    print('program took {:5.3f} minutes'.format((ende-start)/60))

Danke vielmals! Grüße, Strawk

[Strawk]

@__blackjack__: Ich verstehe deinen Ansatz noch nicht. Was meinst du mit "Schlüssel"?

[__blackjack__]

Wörterbücher speichern Werte zu Schlüsseln. Das sind Python-Grundlagen. Statt einem normalen Wörterbuch kann man hier `collections.defaultdict` verwenden um sich Code zu sparen.

Ungetestet:

Code: Alles auswählen

#!/usr/bin/env python3
"""
Created on Mon Dec 28 19:49:51 2020

@author: User
"""
import time
from collections import defaultdict
from pathlib import Path

WORDBOOKS = Path("wordbooks")


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


def main():
    needle = "aebklme"

    sorted_characters_to_words = defaultdict(set)
    for file_path in WORDBOOKS.glob("german_*.dic"):
        with file_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)

    result = sorted_characters_to_words[make_canonical_form(needle)]
    print(len(result), sorted(result))


if __name__ == "__main__":
    start = time.time()
    main()
    ende = time.time()
    print("program took {:5.3f} minutes".format((ende - start) / 60))

[Strawk]

@__blackjack__: Wenn ich deinen Code vom Montag 28. Dezember 2020, 23:51 Uhr ausführe, erhalte ich:

UnicodeDecodeError: 'utf-8' codec can't decode byte 0xe4 in position 165: invalid continuation byte

Grüße, Strawk
Habe die Coddierungsangabe entfernt.
Es sollten Wörter wie diese herauskommen.

ab
2: am
3: km
4: ml
5: Abk
6: Alb
7: Alk
8: Alm
9: Elm
10: Bea
11: kam
12: Kea
13: Lab
14: Lea
15: leb
16: Lee
17: mal
18: Abel
19: Albe
20: ekle
21: ekel
22: Elba
23: Elbe
24: Elke
25: Bake
26: Bela
27: Kalb
28: kleb
29: Klee
30: labe
31: Lake
32: Leak
33: lebe
34: male
35: Melk
36: beame
37: bekam
38: Blake
39: Kabel
40: kable
41: Kaleb
42: kalbe
43: Kalme
44: Kamel
45: Kamee
46: Kemal
47: klebe
48: Lamee
49: Makel
50: Melba
51: melke
52: bemale
53: kabele
54: Kamele
55: abmelke

Grüße, Strawk

[Strawk]

@__blackjack__: Bei deinem Programm kommt nur ein einziges Wort heraus, das letzte der Liste oben. Ist das zu Demonstrationszwecken beabsichtigt? Bitte erläutere den Code ein wenig; ich verstehe den Sinn und den Benefit nicht. Danke.
Strawk

[Strawk]

@__blackjack__: Es ist schade, dass du dich hierzu noch nicht äußern konntest. Auf Urlaub?

[bords0]

__blackjack__s Programm zeigt alle Wörter an, die alle vorgegebenen Buchstaben enthalten.

Wenn man statt needle alle "Teilmengen" von needle ausprobiert, kann man alle Wörter finden, die man legen kann. Dazu muss man die vorletzte Zeile von main() ersetzen durch etwas deutlich längeres (was eben alle Teilmengen von needle verwendet und im Wörterbuch nachschlägt).

[Strawk]

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

[__blackjack__]

@Strawk: Statt die Kodierung beim öffnen der Datei aus dem Quelltext zu entfernen, sollte man da besser die tatsächliche Kodierung angeben. Sonst hängt das vom Betriebssystem und dessen Einstellungen ab, ob das Programm funktioniert oder nicht.

Statt die Teilmengen zu generieren, könnte man auch versuchen mit einem Multi-Set- oder Bag-Datentyp zu prüfen ob die Nadel als Bag eine Obermenge oder gleich der kanonischen Form eines Wortes ist. Dann ist die Laufzeit abhängig von der Anzahl der kanonischen Formen der eingelesenen Daten und nicht von der Anzahl der Teilmengen.

Code: Alles auswählen

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

from multiset import FrozenMultiset

WORDBOOK_ENCODING = "?"
WORDBOOKS = Path("wordbooks")
WORDBOOK_FILENAME_PATTERN = "german_*.dic"

# WORDBOOK_ENCODING = "utf-8"
# WORDBOOKS = Path("/usr/share/dict")
# WORDBOOK_FILENAME_PATTERN = "ngerman"


def make_canonical_form(word):
    return FrozenMultiset(word.lower())


def main():
    needle = "aebklme"

    canonical_form_to_words = defaultdict(set)
    for file_path in WORDBOOKS.glob(WORDBOOK_FILENAME_PATTERN):
        with file_path.open(encoding=WORDBOOK_ENCODING) as lines:
            for line in lines:
                word = line.strip()
                canonical_form_to_words[make_canonical_form(word)].add(word)

    canonical_needle = make_canonical_form(needle)
    result = []
    for canonical_form, words in canonical_form_to_words.items():
        if canonical_needle >= canonical_form:
            result.extend(words)

    result.sort(key=lambda word: (word.lower(), word))
    for number, word in enumerate(result, 1):
        print(f"{number:3d}: {word}")


if __name__ == "__main__":
    start = time.monotonic()
    main()
    ende = time.monotonic()
    print("program took {:5.3f} minutes".format((ende - start) / 60))

Das benutzt das externe `multiset`-Modul. Und ich habe `time.time()` mal durch `time.monotonic()` ersetzt, was man zum messen von Zeiten bevorzugen sollte.

[LukeNukem]

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

Das Builtin-Modul "time" bietet eigens die Funktionen perf_counter() und perf_counter_ns() für Zeitmessungen an.

[__blackjack__]

@LukeNukem: Für etwas, das am Ende in Minuten ausgegeben wird, würde ich keine Funktion verwenden, die explizit für kurze Zeitspannen gedacht ist. Den würde ich eher bei (Mikro)Benchmarks verwenden. Und da dann auch über das `timeit`-Modul, bevor man sich das selber nachbaut.

Ist halt eine Systemfrage ob/wann so ein `perf_counter()` einen Überlauf haben kann, oder ob es dafür überhaupt was eigenes gibt – hier unter Linux auf einem Intel-System benutzt `perf_counter()` genau wie `monotonic()` die `CLOCK_MONOTONIC`-Konstante für den C-Aufruf.

[LukeNukem]

@LukeNukem: Für etwas, das am Ende in Minuten ausgegeben wird, würde ich keine Funktion verwenden, die explizit für kurze Zeitspannen gedacht ist. Den würde ich eher bei (Mikro)Benchmarks verwenden. Und da dann auch über das `timeit`-Modul, bevor man sich das selber nachbaut.

Ist halt eine Systemfrage ob/wann so ein `perf_counter()` einen Überlauf haben kann, oder ob es dafür überhaupt was eigenes gibt – hier unter Linux auf einem Intel-System benutzt `perf_counter()` genau wie `monotonic()` die `CLOCK_MONOTONIC`-Konstante für den C-Aufruf.

Das ist technisch zwar absolut korrekt, mein Einwand ist jedoch ein fachlicher. Mindestens 98% der mir bekannten Entwickler haben eher wenig Ahnung von den Zeitquellen in so einem System. Denen ist nicht gleich ersichtlich, warum es eine CLOCK_MONOTONIC überhaupt gibt und warum Du time.monotonic() aufrufst. Bei time.perf_counter() oder time.perf_counter_ns() können sich die meisten -- okay: die Klügeren -- aber sofort selbst zusammen reimen, daß es um einen Performance Counter und damit also um eine Laufzeitmessung des betreffenden Codeabschnitts geht. Da sich die Implementierung im Kern nicht unterscheidet, ist das natürlich Geschmackssache... und halt eine der Lesbarkeit.

[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.