Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: jpu 02. 08. 2017, 16:14:26
-
Zdravim vsetkych guru prispievatelov root.cz. Rad by som sa s nimi poradil ohladom jednej ulohy.
Mam velky(>3GB) textovy log subor. Ide o nejaky log subor, kam sa loguju veci pocas vykonavania programu. Zo suboru sa maju vycitat nejake veci, podla zadanych kriterii.
Povedzme ze mam vycitat vsetkych uzivatelov, ktori boli zadani na vstupe a potom k danym uzivatelom priradit veci, ktore sa ich tykaju.
Precitat samotne riadky suboru nie je zlozite a je to relativne rychle. Pouzivam na to File.ReadLines, ktora vracia IEnumerable. Horsie je to s vyhladavanim, to uz zaberie dlhsi cas, nakolko kazdy riadok sa musi porovnat voci trom regularnym vyrazom. Mne napadla taka varianta pouzit TPL Dataflow a implementacia producent/konzument.
Neviem o kolko by sa znizil vysledny cas oproti klasickemu rieseniu, ale za skusku clovek nic neda, akurat, ze toto riesenie mi bolo "zamietnute", resp. nedostal by som tolko casu realizovat to. Co si myslite?
-
nejlepšího zrychlení dosáhneš splitnutím toho souboru na několik bloků. Paralelizace na úrovni řádků nebývá moc účinná, tam je limitující IO.
na linuxu by to šlo treba takto
<big_file.txt parallel --pipe --block 200m ./tvuj_command
-
Lenze neviem ako to splitnut, pretoze moze sa stat, ze to utnem zle a nebudu mi potom pasovat veci/udaje
-
Lenze neviem ako to splitnut, pretoze moze sa stat, ze to utnem zle a nebudu mi potom pasovat veci/udaje
gnu parallel splitne soubor podle delimiterů, nerozpůlí řádku.
-
Pouzivam windows a robim to v C#. To na doplnenie :)
-
Pouzivam windows a robim to v C#. To na doplnenie :)
Dobře ti tak :)
-
Dobře ti tak :)
Dik za radu :)
-
Pouzivam windows a robim to v C#. To na doplnenie :)
zkusil jsi neco takoveho? Velikost chunku musí být menší, protože se musí vejít do paměti
using System;
using System.IO;
using System.Threading;
using System.Threading.Tasks;
using System.Linq;
using System.Collections.Generic;
public static class Hello3
{
public static IEnumerable<IEnumerable<TSource>> Batch<TSource>(
this IEnumerable<TSource> source,
int batchSize)
{
var batch = new List<TSource>();
foreach (var item in source)
{
batch.Add(item);
if (batch.Count == batchSize)
{
yield return batch;
batch = new List<TSource>();
}
}
if (batch.Any()) yield return batch;
}
public static void Main(string[] args)
{
int lc = 0;
Parallel.ForEach(File.ReadLines("big_file.txt").Batch(5000),
new ParallelOptions { MaxDegreeOfParallelism = 12 },
(chunk, _, chunkNum) =>
{
foreach(string line in chunk) {
// zpracuj radku
};
});
}
}
podle me tady jen trolis. Kdybys opravdu potreboval pomoc, tak se neptas na linuxovem foru.
-
Pro vyhledávání v celém souboru se jeho celému přečtení nevyhneš. Můžeš to nasypat do databáze a tam to pak vyhledávat.
Ale hádám, že nejčastější use-case bude vyhledávání dle času, nějaký interval od-do. Pak můžeš při prvním přečtení souboru si udělat vlastní index časových značek+offsetů v daném souboru. Tam můžeš jednoduše uložit jen offset začátku řádků. Potom vyhledáváš klasicky sekvenčně, ale pouze v požadovaném úseku offset1->offset2, ne v celém souboru.
Dokonce i update toho indexu, když přibudou další řádky můžeš dělat už jen přírustkově.
Pro vyhledávání regulárních výrazů v celém souboru se dá jednoduše ten celý soubor předzpracovat tak, aby to hledání pak mělo složitost pouze logaritmickou. Doporučuji něco o nich nastudovat.
PS: obejdeš se tak bez paralelního zpracování, bude to efektivnější
-
Pro vyhledávání v celém souboru se jeho celému přečtení nevyhneš. Můžeš to nasypat do databáze a tam to pak vyhledávat.
Ale hádám, že nejčastější use-case bude vyhledávání dle času, nějaký interval od-do. Pak můžeš při prvním přečtení souboru si udělat vlastní index časových značek+offsetů v daném souboru. Tam můžeš jednoduše uložit jen offset začátku řádků. Potom vyhledáváš klasicky sekvenčně, ale pouze v požadovaném úseku offset1->offset2, ne v celém souboru.
Dokonce i update toho indexu, když přibudou další řádky můžeš dělat už jen přírustkově.
Pro vyhledávání regulárních výrazů v celém souboru se dá jednoduše ten celý soubor předzpracovat tak, aby to hledání pak mělo složitost pouze logaritmickou. Doporučuji něco o nich nastudovat.
PS: obejdeš se tak bez paralelního zpracování, bude to efektivnější
Mluvit o logaritmické složitosti v souvisloslosti s paralelizací je nesmysl. Nejde o přečtení souboru, ale provádění operace s řádky. To se dá paralelizovat.
-
Mluvit o logaritmické složitosti
*asymptotické složitosti
-
gll:
preco by som trollil? normalne sa pytam. Chcel som sa len poradit...Myslim, ze je tu dost tem, kam sa chodi trollovat
-
Pro vyhledávání v celém souboru se jeho celému přečtení nevyhneš. Můžeš to nasypat do databáze a tam to pak vyhledávat.
Ale hádám, že nejčastější use-case bude vyhledávání dle času, nějaký interval od-do. Pak můžeš při prvním přečtení souboru si udělat vlastní index časových značek+offsetů v daném souboru. Tam můžeš jednoduše uložit jen offset začátku řádků. Potom vyhledáváš klasicky sekvenčně, ale pouze v požadovaném úseku offset1->offset2, ne v celém souboru.
Dokonce i update toho indexu, když přibudou další řádky můžeš dělat už jen přírustkově.
Pro vyhledávání regulárních výrazů v celém souboru se dá jednoduše ten celý soubor předzpracovat tak, aby to hledání pak mělo složitost pouze logaritmickou. Doporučuji něco o nich nastudovat.
PS: obejdeš se tak bez paralelního zpracování, bude to efektivnější
Mluvit o logaritmické složitosti v souvisloslosti s paralelizací je nesmysl. Nejde o přečtení souboru, ale provádění operace s řádky. To se dá paralelizovat.
ano, ide mi skor o operacie tykajuce sa spracovania riadkov, pretoze to trva najdlhsie
-
gll:
preco by som trollil? normalne sa pytam. Chcel som sa len poradit...Myslim, ze je tu dost tem, kam sa chodi trollovat
právě, že jsem často četl tvé příspěvky v tématech linux vs windows. Možná jsem tě neprávem podezříval z pokusu o založení dalšího flame tématu. V tom případě se omlouvám.
-
Mluvit o logaritmické složitosti v souvisloslosti s paralelizací je nesmysl. Nejde o přečtení souboru, ale provádění operace s řádky. To se dá paralelizovat.
Ale to bylo špatně pochopeno, měl jsem namysli, že to zpracování lze urychlit i bez té paralelizace, paralelní zpracování lze samozřejmě použít i potom...
-
Je také možné ty řádky seřadit podle nějakého hledaného pojmu, a vyhledávat až v těch seřazených řádcích, potom klidně půlením intervalu, nebo ten soubor rovnou podle toho rozdělit...
-
Je také možné ty řádky seřadit podle nějakého hledaného pojmu, a vyhledávat až v těch seřazených řádcích, potom klidně půlením intervalu, nebo ten soubor rovnou podle toho rozdělit...
To už rovnou můžeš ty logy nasypat do databáze, indexovat a pak se v tom přehrabovat dle libosti.
-
Pokud se jedna o jednorazovou ulohu, jako prvni pokus bych zkusil prekopirovat ten soubir na Linux a napsat skriprik v perlu 5.x.
Java nebo .Net bude na toto IMHO pomerne pomaly z duvodu jeji h zpusobu prace s pameti.
A ani bych se nebal v perlu si vyhledane udaje ruznych typu narvat do hashmaps a pak vzajemne korelovat.
Perl je na tyto ucelynprekvapivne rychly.
Chce to ale system se slusnou implementaci perlu a se slusnym memory mngmt, to wokenice rozhodne nejsou.
-
Mluvit o logaritmické složitosti v souvisloslosti s paralelizací je nesmysl. Nejde o přečtení souboru, ale provádění operace s řádky. To se dá paralelizovat.
Ale to bylo špatně pochopeno, měl jsem namysli, že to zpracování lze urychlit i bez té paralelizace, paralelní zpracování lze samozřejmě použít i potom...
obecný regulární výraz v databázi nejde hledat s logaritmickou složitostí. Index vám pomůže pouze u prefixu nebo přesné schody.
-
Mluvit o logaritmické složitosti v souvisloslosti s paralelizací je nesmysl. Nejde o přečtení souboru, ale provádění operace s řádky. To se dá paralelizovat.
Ale to bylo špatně pochopeno, měl jsem namysli, že to zpracování lze urychlit i bez té paralelizace, paralelní zpracování lze samozřejmě použít i potom...
obecný regulární výraz v databázi nejde hledat s logaritmickou složitostí. Index vám pomůže pouze u prefixu nebo přesné schody.
Zase chyba, toto nikde netvrdím, naopak, mám na mysli hledání v tom indexu, a pro konkrétní regulární výraz, ne pro obecný.
O databázi jsem se zmínil pouze mimochodem, protože ta je určena právě pro vyhledávání v nějakých datech, plain text soubor pro to vhodný není.
-
O databázi jsem se zmínil pouze mimochodem, protože ta je určena právě pro vyhledávání v nějakých datech, plain text soubor pro to vhodný není.
Plaintext se dá také indexovat, v daném případě by to mohlo být i výhodné.
-
O databázi jsem se zmínil pouze mimochodem, protože ta je určena právě pro vyhledávání v nějakých datech, plain text soubor pro to vhodný není.
Plaintext se dá také indexovat, v daném případě by to mohlo být i výhodné.
Achjo, to bude horkem... Však jo, plain text není vhodný pro vyhledávání v něm, hodil by se nějaký index, žeano? To tvrdím celou dobu...
-
obecný regulární výraz v databázi nejde hledat s logaritmickou složitostí. Index vám pomůže pouze u prefixu nebo přesné schody.
Jde: https://swtch.com/~rsc/regexp/regexp4.html
-
DB pouzit nemozno a linux tiez nie. Ti, ktori to budu pouzivat, tak maju windows stroje.
Na moje pocudovanie som zistil, ze aplikovat regex na kazdy riadok nie je spravne, lebo to strasne dlho trva. Pouzit string.contains a az potom aplikovat regex je rychlejsie. Bol som v domneni, ze regex su rychlejsie. Kazdy sa ucime :)
-
jsem laik ale nepomohlo by nejdriv ten log file nahrat do ramdisku a pak na nej teprve aplikovat ty prikazy ?
-
DB pouzit nemozno a linux tiez nie.
Však tu databázovou knihovnu můžeš zakompilovat do aplikace. Ani nebudou tušit, že tam nějaká DB je.
Můžeš si místo RE napsat vlastní regulární automat, který může být podstatně rychlejší.
-
DB pouzit nemozno a linux tiez nie. Ti, ktori to budu pouzivat, tak maju windows stroje.
Na moje pocudovanie som zistil, ze aplikovat regex na kazdy riadok nie je spravne, lebo to strasne dlho trva. Pouzit string.contains a az potom aplikovat regex je rychlejsie. Bol som v domneni, ze regex su rychlejsie. Kazdy sa ucime :)
Použijte SQLite je to jen knihovna.
-
DB pouzit nemozno a linux tiez nie.
Však tu databázovou knihovnu můžeš zakompilovat do aplikace. Ani nebudou tušit, že tam nějaká DB je.
Můžeš si místo RE napsat vlastní regulární automat, který může být podstatně rychlejší.
pisat si vlastny automat, ano je to moznost, ale cas na to nie je. vsak urcite viete, ako to funguje vo firmach :)
-
na profi parsování toho co píšeš (text) velké soubory sou nejlepší tyhle karty
http://www.mellanox.com/page/products_dyn?product_family=232&mtag=mtag_tilencore_gx36_q40_adapter
nebo
http://www.mellanox.com/page/products_dyn?product_family=231&mtag=tilencore_gx72_adapter
má to ale jednu nevýhodu musíš si je koupit za peníze :)
-
Můžeš si místo RE napsat vlastní regulární automat, který může být podstatně rychlejší.
pisat si vlastny automat, ano je to moznost, ale cas na to nie je. vsak urcite viete, ako to funguje vo firmach :)
Za dobu, co tady zkoumáš varianty, jsi ho už dávno mohl mít. Není to tak těžké a je na to dost nástrojů, kterým předhodíš gramatiku a vyleze ti z toho hotový parser.
-
Kite, cez vikendy urcite nerobim na praci, ktora sa tyka firmy. Taky workoholik nie som :D
-
Kite, cez vikendy urcite nerobim na praci, ktora sa tyka firmy. Taky workoholik nie som :D
2.8. byla středa.
-
Tak som to skusil pomerat a vyslo mi, ze najrychlejsie precitanie a spracovanie jednotlivych riadkov, je rychlejsie sekvencne ako paralelne. Skusal som pouzit Paralle.Foreach a v nom musim pouzivat ConcurrentDirectory, nakolko potrebujem vyuzivat takyto datovy typ a ConcurrentDirectory je pomalejsi oproti normalnemu Directory.
Normalnym foreachom a obycajnym Directory som sa dostal na cas 1:29min a pomocou Parallel.Foreach + ConcurrentDirectory som sa dostal na 1:38min.
Mozno by sa to dalo este nejako urychlit, ale neviem ci to ma zmysel, mozno pojde radovo o milisekundy. Kazdopadne dakujem Vam za rady.
-
Povedzme ze mam vycitat vsetkych uzivatelov, ktori boli zadani na vstupe a potom k danym uzivatelom priradit veci, ktore sa ich tykaju.
...
Horsie je to s vyhladavanim, to uz zaberie dlhsi cas, nakolko kazdy riadok sa musi porovnat voci trom regularnym vyrazom.
Ja by som si pri jednom precitani suboru vytvoril hash, napr. kde kluce by boli uzivatelia a hodnoty by boli zoznamy veci, ktore sa ich tykaju, t.j.:
aktivity_uzivatelov = {
user1 => [vec11, vec12, ..., vec1m]
user2 => [vec21, vec22, ..., vec2n]
...
}
a potom by som prehladaval podla kriterii tento hash.
Pouzivam windows a robim to v C#. To na doplnenie :)
Tak teda uprimnu sustrast. Na taketo veci sa pouziva perl alebo python a mozno by uplne postacilo aj awk 8)
-
Tiez mi napadlo awk, na skole sme s tym robili pod linuxami, ale windows myslim nieco take nema
-
Tiez mi napadlo awk, na skole sme s tym robili pod linuxami, ale windows myslim nieco take nema
Existuje awk skompilovane aj pre Windows, napr:
https://sourceforge.net/projects/gnuwin32/files/gawk/3.1.6-1/
alebo si nainstaluj MinGW-MSYS
http://www.mingw.org/wiki/msys
a tam mas vsetky bezne utility - zrejme aj novsia verzia awk
-
Cygwin?
https://www.cygwin.com/
Všechny ty báječné cli utility pod woknousama...
-
Hodne unix utils byla portovano pod Win
http://gnuwin32.sourceforge.net/packages.html
-
nebo pripadne zde:
http://unxutils.sourceforge.net/
-
IMHO, 3GB jsou nic, to schroustas ani nemrknes. Aplikovat na kazdy radek 3 regularni vyrazy, to by melo byt par vterin. (IMHO, pokud ten kompilator regularnich vyrazu umi trochu optimalizovat, a pokud jsou to podobne vyrazy, a jsou konstantni, tak by mohlo pomoci jejich slouceni do jednoho. Bohuzel u regexpu se to dela obecne blbe. To je v podstate ekvivalent tomu napsat si vlastni automat, jak tu nekdo navrhoval.)
Paralelizaci na takhle malo dat skoro ani nema smysl resit. Nez to rozchodis a ujistis se, ze to opravdu paralelizuje, tak to budes mit 100x spocitane.
-
Jo, a jeste - nejdriv bych zkusil neco jako prikaz time v Linuxu - zjistit, kolik casu CPU a realneho to sezralo. Pokud to sezralo vyrazne vic realneho nez CPU casu, pak to znamena, ze CPU se nudil, tudiz cela ta uloha je IO-bound a paralelizaci vubec nema smysl resit.
-
Je kouzelné sledovat tady diskuse o tom, jak je paralelizace náročná, že je to potřeba testovat atd... Přitom stačí použít odpovídající nástroj.
Vezmu Go, vstupní procedura čte soubor po řádcích a ty posílá na vstupní channel. Odhad cca 15-20 řádků i s ošetřením chyb. Samotná výkonná funkce čte v nekonečné smyčce řádky ze vstupního kanálu, provede ty 3 regulární výrazy a pokud to projde, data vytiskne nebo je pošle na výstupní channel. (Odhad dalších 15-20 řádků.) Na výstupní channel je připojena procedura která vyselektovaná data zpracuje. Main spustí ve smyčce paralelně 100x (nebo třeba 1000x) výkonnou proceduru, a paralelně spustí čtení souboru. (Odhad tak 25-30 řádků včetně všech deklarací a serepetiček okolo.) Celé to bude zhruba tak rychlé, jako přečtení toho souboru. Není potřeba nic testovat (ale kdybyste chtěl, benchmarking je součástí standardní knihovny a je triviální), maximálně tak vyzkoušet kolikanásobná paralelizace má ještě smysl.
Takže se bavíme o programu délky cca 70 řádků a jedná se o elementární pattern (pipeline => fan out - process - fan in). Za tu dobu co tady diskutujete to máte napsané, i když o Go nic nevíte. Navíc nepochybuji o tom, že v jiných jazycích včetně C# naleznete ekvivalentní prostředky, byť možná nebudou tak přímočaré a jednoduché k použití, jako u Go. Ale i kdyby měl ten Váš program 150 řádků, o čem se proboha bavíme? Jaké schválení potřebujete a kolik času si představujete, že budete potřebovat? A motat do toho ještě DB, jenom indexovování sežere spoustu času, a tady se jedná o jednorázový scan.
P.S.: U Go jako bonus zdarma dostanete multiplatformnost, takže vám to poběží ve Windows, *BSD, macOS i Linuxu, takže si můžete vybrat development platformu a na ostatní to kroskompilovat.
-
Na moje pocudovanie som zistil, ze aplikovat regex na kazdy riadok nie je spravne, lebo to strasne dlho trva. Pouzit string.contains a az potom aplikovat regex je rychlejsie. Bol som v domneni, ze regex su rychlejsie. Kazdy sa ucime :)
Nemohl by si sem postnout ten kod, ktery aplikoval regex pro kazdy radek? Ze zvedavosti