Dotaz: Cyklus s více podmínkami; Python

[jsk]

Zdravím,

nemůžu se hnout z místa , mám soubor mesice, ze kterého potřebuji vyrobit několik dalších souborů. Ty budou, ideálně, pojmenovány podle položek v souboru jmena (Karel, Luboš, Jindra, Rebecca) tak, že do každého z nových souborů potřebuji vložit pouze ty řádky, které obsahuji prvek ze souboru jmena. V jednom řádku je vždy nejvýše jeden prvek ze souboru jmena. Takže výsledkem by mělo být soubory Karel, Luboš, Jindra, Rebecca, pokud by se v souboru jméno nevyskytovalo, soubor by se nevytvořil. Líbilo by se mi mít to ve vlastní funkci se vstupem jmena a mesice. Jsem to sice schopen udělat postupně, pro každé jméno zvlášť, ale to je takové nemotorné, ta funkce by asi byla nejlepší.

Předem děkuji všem za rady a nasměrování.

Pepa

---

---

Odpovědi

[Roman]

Co takhle poslat co už máš, kde ses sekl, chybové hlášení, příklad dat,... Nechci kecat, ale podle posledních zpráv křišťálové koule došli.

[jsk]

Přílohy:

• rozdel.py (294 bytů)
• jmena (43 bytů)
• mesice (16112 bytů)

Asi to tak bude, jak u nás přestal jezdit pojízdná prodejna, tak jsem křišťálové koule neviděl

Přikládám zdrojové soubory a pak jednu z variant. Jako začátečník v Pythonu si dost dobře nedovedu představit jak podle slov v jednom souboru vyberu řádky z jiného souboru. V souboru jmena jsou vlastně vzory pro grep, ale ten použít nemohu, potřebuji, aby to běhalo i pod W10.

Zdraví Pepa

[Bherzet]

Otevřeš soubor jmena, čteš z něj položky, zapisuješ je do patřičných souborů.

[jsk]

To jsem se nejspíš špatně vyjádřil. Podle položek v jmena vyberu řádky ze souboru mesice , které obsahují danou položku. Ty uložím do souboru např. Karel.txt, kde Karel je vzor podle něhož se ze souboru mesice kopírovaly řádky. A tak dále pro všechny položky ve jmena. Nebo jsem to nepochopil já.

Díky Pepa

[Bystroushaak]

#!/usr/bin/env python3

def names(filename):
    with open(filename, "r") as fin:
        return set(line.strip() for line in fin.readlines() if len(line.strip()))

def aggregate(input_filename, keys):
    fouts = dict((k, None) for k in keys)

    with open(input_filename, "r") as fin:
        for line in fin:
            for key in keys:
                if key in line:
                    if not fouts[key]:
                        fouts[key] = open(key + ".txt", "w")
                    fouts[key].write(line + "\n")

    for fout in fouts.values():
        if fout:
            fout.close()

if __name__ == "__main__":
    aggregate("mesice.txt", names("jmena.txt"))

[jsk]

Moc děkuji!! Budu se v tom muset zorientovat, kód obsahuje hodně věcí, které ještě neznám. Určitě se ještě ozvu.
Děkuje a zdraví
Pepa

[Bystroushaak]

Tady je moje řešení, které čte všechno na jediný průchod (bez ohledu na počet vzorů) a má ošetření chybových stavů.

Pokud uživatel skript spustí špatně, pokud nepůjde otevřít některý ze vstupních souborů nebo pokud nepůjde otevřít některý z výstupních souborů (třeba proto, že existuje a je read-only), ohlásí skript chybu (místo ošklivého backtrace) a korektně zavře všechny soubory, které případně byly otevřené — což se hodí, chce-li někdo tento kód přetvořit v opakovaně volanou funkci.

#!/usr/bin/env python3

import sys
import re

if len(sys.argv) != 3:
  sys.exit(f'Usage: {sys.argv[0]} <names> <months>')

fds = {}
def maybe_open(name):
  output = fds.get(name)
  if output is None:
    output = open(name, 'w')
    fds[name] = output
  return output

try:
  with open(sys.argv[1], 'r') as names_file:
    names = tuple(line[:-1] for line in names_file)
  openers = {name: lambda name=name: maybe_open(name) for name in names}
  matcher = re.compile('|'.join(re.escape(name) for name in names))
  with open(sys.argv[2], 'r') as months_file:
    for line in months_file:
      for match in set(matcher.findall(line[:-1])):
        openers[match]().write(line)
except Exception as e:
  sys.exit(e)
finally:
  for fd in fds.values():
    fd.close()

Spouští se to například takto:

./jméno_skriptu.py jména.txt měsíce.txt

[Andrej]

V očekávání davu křičícího, že soubory není třeba zavírat, protože jakmile příslušný slovník s referencemi na ně přijde o svou poslední referenci, vše se zlikviduje a zavře, dodávám raději předem následující:

Ve většině implementací Pythonu tomu tak šťastnou náhodou je, ale rozhodně ne ve všech, protože jazykový standard takové chování sice umožňuje, ale nezaručuje. Korektní a portovatelný kód by tedy měl mít buď with (...):, nebo close().

[jsk]

Děkuji a skláním se!
Vidím, že řešení je mnohem náročnější než jsem si uměl představit a chvíli potrvá než kódu porozumím. Pokud se zadrhnu v chápání, dovolil bych si ještě položit otázku, díky.
Za kód a poučení děkuje
Pepa

[pete]

Super, lepsi nez ten predchozi skript, tohle psal zkuseny programator

[pedro]

Ano, blbe se to cte a je to cca 2x pomalejsi (a to jsem z toho pred testovanim vyrazil celkem zbytecne predavani argumentu z radky)...

[Andrej]

Tihle anonymní žvanilové… Těch kdyby bylo na ABCLinuxu méně (nebo 0), opravdu by to hodně pomohlo.

Žvanění je laciné. Show us the code. Soudě podle siláckých řečí, lze od tvého — zatím tajného — kódu očekávat, že:

• je prokazatelně (benchmark, prosím!) dvakrát rychlejší. Výborně. Jak přesně jsi to měřil?
• má srovnatelnou exception safety a kontrolu vstupu.
• se lépe čte, samozřejmě, jak jinak.

Když má někdo lepší řešení než předchozí, jistě se jím (místo prázdných keců) rád pochlubí. Takže? Kdepak je? Už se těším, na jakých krajních případech to řešení otestuju — hned jak ho uvidím.

Zbytečnost argumentů z příkazové řádky… Ehm… Už jsi někdy něco v praxi programoval? Na to se nic jiného říct nedá.

[_]

Spíše než anonymní žvanil to bude ublížený Bherzet, vyžívá se v trollování. Neřešil bych

[Bherzet]

Taky bych to s tebou mohl probrat osobně v Kohoutovicích.

[_]

To bys mohl, ale já tam za tebou nepojedu

[Bherzet]

Nepojedu? Výtahem možná tak, ne?

[pedro]

Presne takovou reakci jsem cekal. Pobavilo. Kazdy si muze sam vyzkouset, ktery z tech dvou reseni je vykonnejsi, hint knihovna time.

Chapu, Andrej, ze to boli

[Andrej]

Ale no tak, anonyme, tvoje vlastní hloupost tě musí bolet. Ty jsi žádné řešení neukázal, takže — kód, prosím. Nebo se můžeš přihlásit, naznačuješ-li, že jsi autorem předchozího pokusu.

Prý „vykonnější“. Jako když páťák mluví o autech.

Koho by asi tak tankovalo, kdyby to „řešení“ výše, které má vždy lineární složitost v počtu jmen (fujtajbl!) a ani nepozavírá soubory, když u jednoho dojde k chybě, bylo rychlejší pro triviální případy? Třeba fracka, který nikdy nic nenaprogramoval? Jo, toho by to možná zaujalo.

Každý si může sám vyzkoušet…? Ale ale ale. Takhle to na světě nechodí.

Takže, budou data nebo jenom další žvásty? Na kolika GB vstupních dat jsi to testoval? Klíčových slov ve vstupu jsi měl tisíc nebo milión? Jaké byly výsledky? S jakými konfidenčními intervaly?

Ach jo. ABCLinuxu, prosím, vyhoďte už ten anonymní póvl oknem ven.

[Bystroushaak]

a ani nepozavírá soubory, když u jednoho dojde k chybě, bylo rychlejší pro triviální případy?

Technická; Soubory se v pythonu zavřou automaticky na konci, i když to skončí chybou.

[Andrej]

Technická: Ne vždycky. To jsem koneckonců uváděl i výše.

Samozřejmě, že soubory v UNIXu se automaticky zavřou, bez ohledu na to, proč proces odletí. Nicméně výše odkazovaný blog ukazuje příklady, kdy se nezapsal obsah bufferu v některých implementacích Pythonu.

Ve většině implementací Pythonu je to opravdu tak, že při ukončení s otevřenými soubory (ať už normálním nebo kvůli neošetřené výjimce) se všechno správně flushne. Ale neplatí to obecně a nelze na to jednoduše spoléhat.

(Kromě toho je obecně dobrým zvykem psát kód tak, aby se mohl stát knihovní funkcí, která se dá opakovaně volat a která po sobě nenechá nedefinovaný stav, ani v případě, že skončí výjimkou.)

[Bystroushaak]

(Kromě toho je obecně dobrým zvykem psát kód tak, aby se mohl stát knihovní funkcí, která se dá opakovaně volat a která po sobě nenechá nedefinovaný stav, ani v případě, že skončí výjimkou.)

Souhlasím, ale co má za smysl tohle řešit v kontextu téhle diskuze, kde máš globální proměnné které nakonci nečistíš, a když ten kód importuješ, tak se hned začne provádět, načítat data z sys.argv a tak.

[Andrej]

Souhlasím, že celá tahle diskuse je na prd.

Globální proměnné v quick&dirty skriptu jsou v nejlepším pořádku a kdo z toho bude chtít knihovnu, ať si to celé zanoří do funkcí podle libosti.

[Bystroushaak]

Ve většině implementací Pythonu je to opravdu tak, že při ukončení s otevřenými soubory (ať už normálním nebo kvůli neošetřené výjimce) se všechno správně flushne. Ale neplatí to obecně a nelze na to jednoduše spoléhat.

Jeden z případů, kde na to imho nelze spoléhat je například kill -9. Jenže tam nepomůže ani finally:. Řešení by udělat nad filesystémem transakci pomocí atomického move odněkud z /tmp, ale to už se dostáváme fakt do ezoterie úplně odtržené od reality původního dotazu.

[Andrej]

Nejde přece o kill -9. Jde taky (kromě jiného) o to, že (jak uvádí výše odkazovaný blogpost), Jython a PyPy nezavírají automaticky soubory, když se ztratí poslední reference na ně, ale až při ukončení procesu.

Takže kdyby někdo například používal tento kód jako opakovaně volanou funkci, která by ale občas selhala, byl by to docela zajímavý leak a případně by mohl pozorovat nekonzistentní data, kdyby se mezitím (jinde v kódu) pokoušel vytvořené soubory číst.

Ano, tohle už je off-topic a vůbec jsem neměl v úmyslu na to tolik upozorňovat a/nebo to stavět do kontrastu s původním řešením. Tohle je prostě jedna z těch situací, ve kterých by zákaz anonymů prospěl.

[Bystroushaak]

Ach jo. ABCLinuxu, prosím, vyhoďte už ten anonymní póvl oknem ven.

Já moc nechápu, proč se do tohohle necháváš vůbec zatáhnout. Všechny řešení tady jsou nedotažené kludges, kde bych našel deset způsobů jak to rozbít tobě i Bherzetovi.

Takže, budou data nebo jenom další žvásty? Na kolika GB vstupních dat jsi to testoval? Klíčových slov ve vstupu jsi měl tisíc nebo milión? Jaké byly výsledky? S jakými konfidenčními intervaly?

Má nějaký smysl se hádat o tom kdo to vyřeši líp, když jste oba prostě chtěli pomoci OPovi a nikdo z vás nedodal kód co by byl fakt hodný do produkce? Co má za smysl řešit ošetření chyb v takovém quick&dirty kódu, když tam je kopa dalších zásadních nedostatků, jako používání globálních proměnných, nemožnost ten tvůj kód vůbec importovat, chybějící dokumentace, nevhodná dekompozice a tak podobně. Třeba tam ani netestuješ, jestli soubory existují, než je otevíráš proč čtení.

Tím nechci říct, že Bherzetův kód je nějak výrazně lepší, trpí ostatně podobnými problémy, ale proč proboha vytahovat tyhle blbosti v diskuzi kde se snažíte pomoci tazateli rychlou ukázkou jak na to.

[Andrej]

Ach jo. ABCLinuxu, prosím, vyhoďte už ten anonymní póvl oknem ven.

Já moc nechápu, proč se do tohohle necháváš vůbec zatáhnout. Všechny řešení tady jsou nedotažené kludges, kde bych našel deset způsobů jak to rozbít tobě i Bherzetovi.

Výborně. Kód, prosím. Rád se poučím.

Je snadné si povšimnout, že já jsem tuhle hloupou debatu nezačal; jen mám silnou a stále sílící alergii na místní anonymy.

Má nějaký smysl se hádat o tom kdo to vyřeši líp, když jste oba prostě chtěli pomoci OPovi a nikdo z vás nedodal kód co by byl fakt hodný do produkce?

Toto^^^ tvrzení je ovšem bez ukázky kódu … jak to jen slušně říct … poněkud plané. Stejně jako řeči o "produkci". OP chtěl nějaké řešení. Jak si ho upraví a kam si ho začlení, to už je na něm.

Co má za smysl řešit ošetření chyb v takovém quick&dirty kódu, když tam je kopa dalších zásadních nedostatků, jako používání globálních proměnných

V této větě si odporuješ. Na jedné straně to má být quick&dirty — ano, od ukázky kódu někde na fóru se nic jiného čekat nedá. Na druhé straně jsou zrovna tady globální proměnné problém?

V quick&dirty skriptu, který se nevolá z jiného kódu, mi globální proměnné připadají naprosto v pořádku, zatímco odlet na neošetřenou výjimku není v pořádku, pokud za sebou nechá nedefinovaný stav (otevřené soubory).

Kdyby někdo chtěl tohle použít jako knihovnu, asi tak za 2 minuty by to mohl celé "zahnízdit" do funkce (nebo do instance objektu, podle chuti, podle použití) a globálním proměnným se vyhnout.

, nemožnost ten tvůj kód vůbec importovat, chybějící dokumentace, nevhodná dekompozice a tak podobně.

Takže, je to / má to být krátký a jednoduchý a názorný příklad nebo něco jiného?

Zmínka o dokumentaci je v tomto kontextu dost absurdní. Nejsem přece zaměstnancem OP, abych pro něj vytvářel kompletní knihovnu s dokumentací, testy atd. Sepsal jsem narychlo jednoduchý příklad, který splňuje zadání. Toť vše.

Třeba tam ani netestuješ, jestli soubory existují, než je otevíráš proč čtení.

Ale proč bych to dělal? Mám tam ošetření výjimek a neexistující soubor skončí výjimkou FileNotFoundError: [Errno 2] No such file or directory: ...

Tím nechci říct, že Bherzetův kód je nějak výrazně lepší, trpí ostatně podobnými problémy, ale proč proboha vytahovat tyhle blbosti v diskuzi kde se snažíte pomoci tazateli rychlou ukázkou jak na to.

Můj kód je jistě sračka; to bezesporu. Je to rychlá a jednoduchá ukázka určená k základnímu předvedení, jak by se problém tazatele dal případně řešit. Neklade si za cíl být "produkční", "konzumační" ani jiný.

Znova podotýkám: Nejsem to já, kdo zahájil tuhle hloupou, pseudo-anonymní a ničím nepodloženou debatu.

[Bystroushaak]

Je snadné si povšimnout, že já jsem tuhle hloupou debatu nezačal; jen mám silnou a stále sílící alergii na místní anonymy.

Chápu no. Mám to do jisté míry podobně.

Takže, je to / má to být krátký a jednoduchý a názorný příklad nebo něco jiného?

Já bych byl spíš za ten krátký a jednoduchý, například je docela jedno že to padne. Prostě smázneš soubory a pustíš to upravené znova.

Znova podotýkám: Nejsem to já, kdo zahájil tuhle hloupou, pseudo-anonymní a ničím nepodloženou debatu.

Ok. Beru. Jen jsem spíš chtěl podotknout že nemá smysl se do ní zatahovat a proč, ale teď zpětně vidím, že tím jsme se jen zatáhli víc oba. Za to se omlouvám.

Za mě super že jsi poslal svoje řešení, to bylo konstruktivní.

[pedro]

Testovwl jsem to na zadani, ktery jsem dostal,ty gigabajte A davej si bacha,jaka volis slova vuci druhym.

[_]

Přesně, do Curychu je to coby kamenem (kohoutem?) dohodil xD

[Andrej]

Ale no tak, anonyme, ty ses nějak rozdurdil. No podívejme. Mám si dávat bacha — nebo jinak co?

Já nic testovat nemusím, protože nejsem autorem testovaného výroku. Znova si přečti, v čem spočívá problém tvé argumentace: Burden of Proof Fallacy A zkus to tentokrát pochopit.

Když přicházíš do debaty s nějakým tvrzením, důkazní břemeno je na tvé straně. Debata nefunguje tak, že řekneš: Já říkám tohle a vy ostatní to zkuste vyvrátit, protože jinak mám pravdu já.

[Andrej]

Ještě "technická" pro úplnost, burden of proof stranou:

Úsměvné na tom je, že pro počet jmen, který se dá spočítat na prstech, a pro relativně malá vstupní data máš (s pravděpodobností hraničící s jistotou) pravdu.

Pro milión "jmen" to ale dopadne úplně jinak, protože moje řešení nebude každou řádku testovat miliónkrát, ale projde ji jen jednou.

(Snad jsem to konečně vysvětlil dostatečně polopatě a po lopatě.)

Problém je, když tvrdíš cosi o "výkonnosti" u dat tak malých, že se dají napsat na papír, a navíc ještě nesmyslně konfrontačním tónem. Vykládat, že něco, co trvá milisekundu, je dvakrát rychlejší něž něco podobného, nemá smysl.

[pedro]

Ale to v zadani neni.

[Andrej]

Ale to neznamená, že řešení, které je náhodou na malinkých datech o milisekundu rychlejší, je "výkonnější".

[Bherzet]

Nebo se můžeš přihlásit, naznačuješ-li, že jsi autorem předchozího pokusu.

Andreji, pochop, prosím, že mám trolla, který nemá na práci nic lepšího než každý den v 11 dopoledne přijít na Abclinuxu, přidat pár štítků na blogy či jinam a poslat pár komentářů. Teď se právě dobře baví, že se mu podařilo diskuzi zbytečně rozhádat. Existuje přitom jednoduché řešení: Nekrmit. Reagovat jen na seriózní komentáře. V případě pochyb se řídíme identitou. Ta u neregistrovaných uživatelů chybí.

lineární složitost v počtu jmen (fujtajbl!)

Ano, jde to udělat líp: Naparsovat ze řádku jméno a ověřit, že se nachází v setu hledaných jmen. A nebo jako to děláš ty tou FSM, ta to také matchne na jediný průchod. Ale to, stejně jako moje řešení, selhává na případné kolizi s jinými sloupci. Zde by bylo potřeba upřesnit zadání.

Já vycházel z předpokladu, že jmen bude málo. Působí to na mě totiž dojmem, že skript je určen na v podstatě prohledávání jakýchsi objemnějších dat. Kdyby jmen bylo hodně, asi by neexistoval ani žádný soubor jmena.txt, resp. by jej někdo musel generovat. Pak by asi nevznikla ani takto zadaná úloha. Spíš by už existoval skript, který udělá kompletní agregaci jmen ze souboru mesice.txt.

Proto jsem upřednostnil jednoduchost. Přiznávám nicméně, že řešení s FSM mě ani nenapadlo a přijde mi dobré.

ani nepozavírá soubory, když u jednoho dojde k chybě

To mi přišlo úplně zbytečné u takovéto úlohy řešit, protože reálně by k tomu došlo asi tak jedině při vyčerpání volného místa na disku. Ale jinak máš samozřejmě pravdu.

ad rychlost) Na dodaných datech jsou obě naše řešení stejně rychlá (tři spuštění, rozdíl mezi nimi ± 1 ms; vzal jsem střední hodnotu):

$ time ./Andrej.py jmena.txt mesice.txt 

real	0m0.037s
user	0m0.030s
sys	0m0.007s

$ time ./prasarnicka.py 

real	0m0.029s
user	0m0.022s
sys	0m0.007s

$ python3 --version
Python 3.6.7

To ale nemá smysl řešit. Jak jsme si vyjasnili, oba kódy se liší po funkční stránce věci (a ano, tvůj kód je korektnější). S rostoucím počtem jmen by navíc moje řešení bylo výrazně pomalější.

Jinak tvůj kód je pro mě na hranici čitelnosti, ale to je dílem záležitost coding-stylu, dílem toho, že to pravděpodobně nebylo tvojí prioritou (stejně jako nebylo mou prioritou ošetřit všechny chybové stavy, implementovat CLI apod.).

[pedro]

V případě pochyb se řídíme identitou

[Andrej]

Díky za reakci.

Tím je tedy vyvrácena také spekulace anonyma „podtržítko“.

Máš pravdu — nekrmit je nejlepší varianta. Dlužno taky dodat, že jsem neměl vůbec v úmyslu nějak kritizovat tvůj kód.

Uf. Taková zbytečná a únavná debata kvůli pár anonymním kecům.

[Bherzet]

Jen BTW, pete, pedro a _ jsou jeden člověk (jestli ho tak můžeš nazývat).

[Andrej]

Což mi bohužel docvaklo až teď.

[Bherzet]

V pohodě, stane se. :)

[Bystroushaak]

Jaký to je pocit mít osobního trolla? Mi to tu Jenda pořád záviděl dřív.

[Andrej]

Vím, že ABCLinuxu nikdo aktivně nevyvíjí a že ten kód třeba není (z dnešního pohledu) v dobře udržovatelném stavu, ALE [toto slovo většinou předznamenává nejdůležitější část sdělení], nedalo by se přece jen zakázat anonymní komentování? Všechna tahle individua by to aspoň trochu omezilo. Nedávno zavedená captcha (po opakovaných DOS útocích spočívajících v anonymním zaplevelování poradny) stála podle mě víc úsilí, než kolik by stálo tohle.

[pedro]

Sorry za vyvraceni hypotezy, ale nejsou

[Bherzet]

Tak se zaregistruj a nebudou ti krást nick.

[pedro]

$ time ./Andrej.py jmena.txt mesice.txt

real 0m0.037s user 0m0.030s sys 0m0.007s

$ time ./prasarnicka.py

real 0m0.029s user 0m0.022s sys 0m0.007s

$ python3 --version Python 3.6.7

Mno, lepsi by to bylo testovat primo v interpretu, ne?

[pedro]

Treba takto, ma to zajimavy vysledek a jeste zajimavejsi zaver pro tuto diskusi

import re
import time

def hledej(string, text):
    if text in string:
       pass

def hledej_regex(string, text):
    if re.match(text, string):
        pass

start = time.time()
hledej("toto je nějaký řetězec pro testování", "řetězec")
end = time.time()
print(end - start)

start = time.time()
hledej_regex("toto je nějaký řetězec pro testování", "řetězec")
end = time.time()
print(end - start)

[Bherzet]

To nemyslíš vážně, že ne?

[pedro]

hledej_regex("toto je nějaký řetězec pro testování", "toto")

Myslim to naprosto vazne a jestli to je blbost, tak zcela vazne si to necham vysvetlit.

[Bherzet]

Blbost je volat re.match. Tak si ten regulární výraz ve tvaru "abc|def|..." zkus zkompilovat ručně (tzn. napsat efektivně stejný automat, který jinak generuje ten re.compile – a který generuje i ten re.match, akorát ho použije jen jednou a zahodí) a pochopíš to.

[Andrej]

Uf. Co třeba zkusit něco … většího? Mám-li "parafrázovat" původní kód:

#!/usr/bin/env python3

import random
import re
import string
import time

def hledej(input, pattern_list):
  for pattern in pattern_list:
    if pattern in input:
      pass

def hledej_regex(input, pattern_list):
  re.match('|'.join(pattern for pattern in pattern_list), input)

def random_string(length):
  return ''.join(random.choice(string.ascii_letters + string.digits)
                 for _ in range(0, length))

long_input = random_string(1000000)
patterns = [random_string(n % 10 + 10) for n in range(0, 10000)]

for _ in range(0, 10):
  start = time.time()
  hledej(long_input, patterns)
  end = time.time()
  print(f'"in": {end - start}')

  start = time.time()
  hledej_regex(long_input, patterns)
  end = time.time()
  print(f'regex: {end - start}')

[Andrej]

Opravdu? To by jistě nikoho nenapadlo.</sarkasmus>

Stating the obvious: Zajímavé by bylo třeba otestovat, jak se změní doba běhu, když se vstupem o velikosti 1 GB přejdu od tisíce jmen k miliónu jmen. Jestli to poběží 20 milisekund nebo 40 milisekund na takhle malých datech, to je opravdu naprosto nepodstatné.

[pedro]

A co by se stalo, kdyby jmen zustalo malo a naopak by narostl pocet radku v souboru mesice?

[Andrej]

Ideálně by to mělo být lineární v počtu řádků v souboru měsíce a konstantní v počtu jmen. Řešení, které iteruje přes všechna jména na každé řádce, není konstantní v počtu jmen, nýbrž lineární. Ještě jinak: Když zdvojnásobím počet jmen, doba běhu (pro dostatečně dlouhé měsíce a rozumně krátká jména) by měla zůstat stejná, neměla by se zdvojnásobit. (Například algoritmus Aho-Corasick něco takového umožňuje, mimo jiné.)

[Bherzet]

Když vezmu ten můj test, tak pro 10**6 iterací (tedy počet řádků v souboru mesice.txt) platí, že pokud je počet jmen ≤ 9, pak je rychlejší operátor in. Při cca 10 jsou obě metody identické, poté jasně vítězí regex. Při 10**7 iteracích a 20 jménech je regex 2x rychlejší.

[Bherzet]

Režie na spuštění je cca stejná, takže tohle měření je pro orientační představu dostatečné (hrubé přešlapy jako re.match místo re.compile) by to odhalilo. Jinak ale nemá vůbec smysl se tím zabývat, protože náš čas je asi jaksi dražší než desítky strojových milisekund – proto netvrdím, že je můj kód o nějakých 8 milisekund rychlejší. Kdyby skrz to tekly gigabajty dat a na výkonu začalo záležet, tak:

(I.) S algoritmem použitým v mém kódu při zvýšení počtu jmen o řád rychlost klesne také o řád. Andrejův ne, ale při hodně velkém počtu jmen (a nebo příliš dlouhých jménech) se to vykvrdlá na něčem jako internal error in regular expression engine, pokud daná implementace nebude zvládat neomezené regexy (ta moje to, zdá se, zvládá), a nebo spotřebě paměti, protože kompilace o 10 milionech jednoznakových členů mi spotřebovala asi 15 GB RAM a pak to odstřelilo systém.

(II.) Proč používat CPython, který nemá JIT? A ani můj, ani Andrejův kód asi není psán tak, aby byl kompatibilní třeba s Pypy. Netestoval jsem to, možná by to fungovalo, ale rozhodně na to nelze spoléhat.

OPovi to (snad) vyřešilo problém, dohadovat se o tom, jestli je něčí kód o pár milisekund rychlejší, je velká hloupost.

[pedro]

Budiz, pro tento pripad. Nicmene si proste trvam na tom, ze z hlediska strojovyho casu a taky z hlediska citelnosti kodu nema smysl v Pythonu pouzivat regex, kdyz funkce hledani v retezci je nejenom vic citelna, ale taky o dost rychlejsi.

[Bherzet]

Jenže ona není rychlejší. Ne teoreticky (slyšel jsi někdy o časové složitosti a automatech?) a ne prakticky.

#!/usr/bin/env python3

import re
import time
import logging

def search1(line, strs, iterations):
    for _ in range(iterations):
        for s in strs:
            if s in line:
                pass

def search2(line, strs, iterations):
    m = re.compile("|".join(re.escape(s) for s in strs))

    for _ in range(iterations):
        if m.findall(line):
            pass

def test(fn, iterations, names):
    t0 = time.time()
    fn("neobsahuje zadne z jmen", ("karel",) * names, iterations)
    print("Funkce {} probehla za: {} s.".format(fn.__name__, time.time() - t0))

test(search1, 10 ** 6, 10 ** 3)
test(search2, 10 ** 6, 10 ** 3)

[Bherzet]

Zapomněl jsem na výsledek. U mě (verzi Pythonu už jsem posílal, 3.6.7, klasický CPython):

Funkce search1 probehla za: 29.30871868133545 s.
Funkce search2 probehla za: 0.18523097038269043 s.

[Bherzet]

Úplně korektní by tedy bylo dávat tam různá jména, protože takhle by to ten regex (resp. výsledný automat) teoreticky mohlo zoptimalizovat. Takže místo ("karel",) * names si dejte třeba [str(i) for i in range(names)]. Výsledek je stejný.

[pedro]

Te prvni casti kodu by dost pomohlo any.

[pedro]

Funkce search1 probehla za: 0.42887043952941895 s.

Funkce search2 probehla za: 0.17212176322937012 s.

Po uprave s any. Ale jinak samozrejme beru ze s narustajici slozitosti se zacne projevovat vyhodnost regexu.

[Andrej]

To by byla pravda pro jeden string.

Tady bylo úkolem matchovat několik stringů zároveň.

Máš možnost je matchovat

• buď v čase lineárním vůči počtu vzorů i vstupu, tj. zeptat se na každý pomocí in,
• nebo třeba v čase konstantním vůči počtu vzorů a lineárním vůči vstupu, například něčím jako Aho-Corasick nebo zkrátka jedním z mnoha algoritmů, které dovedou implementovat jednoduchý regexp se svislítky.

Tak… Už?