PyLadies - Praha - jaro 2024 - Lekce - Lineární a kvadratická časová složitost (2024-04-08)

01_pocet_znaku.py

# Osnova lekce - https://github.com/PetraVidnerova/PyLadies_pokr/tree/main/lesson_time

from pprint import pprint
from random import randrange
from time import time
# import string

retezec = 'skakal pes pres oves'

def vygeneruj_retezec(delka):
    ABECEDA = 'abcdefghiklmnopqrstuvwxyz'
    ABECEDA += ABECEDA.upper()
    ABECEDA += '0123456789'
    # Aternativně pomocí proměnných ze standardní knihovny
    # ABECEDA = string.ascii_letters + string.digits
    vysledek = []
    delka_abecedy = len(ABECEDA)
    for pismeno in range(delka):
        vysledek.append(ABECEDA[randrange(delka_abecedy)])
    return ''.join(vysledek)

def read_bible_lines(num=10):
    text = ""
    # stažení bible https://github.com/PetraVidnerova/PyLadies_pokr/blob/main/lesson_time/bible_part.txt.zip
    with open("bible_part.txt", "r", encoding="utf-8") as f:
        for i, line in enumerate(f):
            if i > num:
                return text
            text += line
    return text

def count_sequence(input_string, seq_len=2):
    result = {}
    for i in range(len(input_string)-seq_len+1):
        pismena = input_string[i:i+seq_len]
        if pismena in result:
            continue
        pocet = input_string.count(pismena)
        result[pismena] = pocet
    return result

def count_sequence_v2(input_string, seq_len=2):
    result = {}
    for i in range(len(input_string)-seq_len+1):
        pismena = input_string[i:i+seq_len]
        if pismena in result:
            result[pismena] += 1
        else:
            result[pismena] = 1
    return result


def count_letters(input_string):
    result = {}
    for pismeno in input_string:
        if pismeno in result:
            continue
        pocet = input_string.count(pismeno)
        result[pismeno] = pocet
    return result

def count_letters_v2(input_string):
    result = {}
    for pismeno in input_string:
        if pismeno in result:
            result[pismeno] += 1
        else:
            result[pismeno] = 1
    return result

# retezec = vygeneruj_retezec(50_000_000)

retezec = read_bible_lines(10_000)
# ukol nejčaštější a nejméně časté písmeno v bibli

def najdi_minimum(slovnik):
    min_znak = None
    minimum = None
    for znak in slovnik:
        if minimum is None:
            min_znak = znak
            minimum = slovnik[znak]
        if minimum > slovnik[znak]:
            min_znak = znak
            minimum = slovnik[znak]
    return min_znak

def najdi_maximim(slovnik):
    max_znak = None
    maximum = None
    for znak in slovnik:
        if znak in ' ':
            continue
        if maximum is None:
            max_znak = znak
            maximum = slovnik[znak]
        if maximum < slovnik[znak]:
            max_znak = znak
            maximum = slovnik[znak]
    return max_znak

start = time()
# print(retezec)

# Pro jeden znak obě funkce fungují stehně rychle
pocty_znaku = count_letters(retezec)
# pocty_znaku = count_letters_v2(retezec)

# Domácí úkol
# prohlédněte si funkce count_sequence a count_sequence_v2
# jsou prakticky stejné jako funkce z hodiny ale umí zjistit sekvenci několika znaků
# vyzkoušejte si, jak se situace změní pro seq_len = 1, 2 a 3
# pocty_znaku = count_sequence(retezec, seq_len=3)
# pocty_znaku = count_sequence_v2(retezec, seq_len=3)

pprint(pocty_znaku)

print(najdi_minimum(pocty_znaku))
print(najdi_maximim(pocty_znaku))

stop = time()
celkovy_cas = stop - start
print(celkovy_cas, 'sekund')