asked 2015-11-17 21:36:42 +0100
Nemohu se dostat skrze Test číslo 3: Limity IP adresy. Můj script vypadá následovně:
#!/bin/bash
cat apache.log | grep -v "\[error\]" | tr -s ' ' | cut -d' ' -f6 | sort -t'.' -k1,4n | uniq -c | tr -s ' ' | cut -d' ' -f2 | sort -nr | head -1
V lokálním bashi vše funguje tak jak má. Zkoušel jsem jak příklady z ukázky tak soubor, který se nachází na fray1. Děkuji za rada.
answered 2015-11-17 21:59:33 +0100
Neznám zadání, ale v tom, co děláme v rámci PS1, je tr -s skoro vždy špatně. Soudě podle jeho umístění za uniq -c bych řekl, že se snažíte zbavit těch mezer před číslem, ale to nefunguje správně (ani v "lokálním bashi" - prostě svému programu nedáváte dostatečně záludné vstupy) - tr -s sice zlikviduje nadbytečné mezery, ale ve výstupu uniq -c vůbec žádná mezera být nemusí a následný cut -d' ' -f2 je pak samozřejmě blbě...
souhlas ;]
jinymi slovy: co kdyz se jedna IP adresa vyskytne v souboru 1000000 krat?
answered 2015-11-21 13:30:10 +0100
Důvod a vysvětlení chyby v Tvém řešení už zmínili ostatní, rád ukážů řešení mé:
awk '!/\[error\]/{a[$6]++}END{max=0;for(i in a){if(a[i]>max)max=a[i]} print max}' apache.log
Když jsem si zadání přečetl, hned mě napadlo awk. Jak je vidět, jde to hezky napsat pomocí jednoho awk, celkem jednoduše a snad i srozumitelně. A je to i rychlejší než 2x sort. Poprvé sort potřebuji, ale podruhé mi stačí jen najít maximální hodnotu (a kvůli tomu nepotřebuji vše řadit - O(n) vs. O(n log n))
Pár lidí ale namítalo, že jsme awk ještě nebrali. Proto se báli i obyčejného
awk '{print $1}'
Které ušetřilo spoustu trápení a je mnohem mocnější než cut. Cut (bohužel) nezvládá více oddělovačů jdoucích po sobě.
Viz rozdíl
echo " 3" | cut -d\ -f1
echo " 3" | awk '{print $1}'
Na odstranění přebytečných mezer bez awk máme více možností. Výše zmíněný sed, nebo třeba grep -o
tr -s ' ' <apache.log | grep -v '\[error\]' | cut -d\ -f6 | sort | uniq -c | sort -nr | head -1 | grep -o '[0-9]*' | head -1
Někdo vtipně neodstraňoval mezery, ale pomocí echo je tam naopak přidával :-D Takže v řešení se fantazii meze nekladou.
Ještě jeden na Babicu: Když nemáme sed, awk ani grep, tak tam dáme tr: (POZOR, NEFUNGUJE!)
tr -s ' ' <apache.log | grep -v '\[error\]' | cut -d\ -f6 | sort | uniq -c | sort -nr | head -1 | tr -s ' ' | cut -d\ -f-2 | tr -d ' '
čas:
Fray
[email protected]:~$ wc -l <apache.log
1000797
[email protected]:~$ du -sh apache.log
140M apache.log
[email protected]:~$ time awk '!/\[error\]/{a[$6]++}END{max=0;for(i in a){if(a[i]>max)max=a[i]} print max}' apache.log
375375
real 1m34.088s
user 1m33.637s
sys 0m0.405s
[email protected]:~$ time tr -s ' ' <apache.log | grep -v '\[error\]' | cut -d\ -f6 | sort | uniq -c | sort -nr | head -1 | ggrep -o '[0-9]*' | head -1
375375
real 1m15.272s
user 1m38.935s
sys 0m2.716s
Webdev
[email protected] ~ $ ll apache.log
-rw-r----- 1 bartimar users 145M Nov 21 20:52 apache.log
[email protected] ~ $ time awk '!/\[error\]/{a[$6]++}END{max=0;for(i in a){if(a[i]>max)max=a[i]} print max}' apache.log
375375
real 0m4.094s
user 0m1.820s
sys 0m0.756s
[email protected] ~ $ time tr -s ' ' <apache.log | grep -v '\[error\]' | cut -d\ -f6 | sort | uniq -c | sort -nr | head -1 | grep -o '[0-9]*' | head -1
375375
real 0m12.529s
user 0m11.272s
sys 0m7.916s
Obecně je možné použít kterékoliv řešení, které přinese správný výsledek. Takže ano, lze použít i awk, přestože ještě nebylo cvičeno. Dost možná to dokonce bude i výhodnější. Je však třeba si dát pozor, aby vás nepoškodilo nějaké specifické chování toho příkazu, které třeba ještě neznáte.
Josef Kokeš ( 2015-11-21 13:56:02 +0100 )editS tou rychlostí tedy moc nesouhlasím. Vlastně ani s jednou její částí: Nejpomalejší částí toho řešení přes sort/uniq je sort, tedy n*log n. V řešení přes awk je nejpomalejší částí použití asociativního pole, které může mít složitost cokoliv od n do n^2 - s tím, že n to bude dosahovat jen pro malé vstupy. Průměrně bych očekával taky něco kolem n*log n. Verze s řazením je podle mě jistější, jsou tam menší výkyvy - bude dobře pracovat i v případě, že je vstup (mnohem) větší než dostupná paměť.
Josef Kokeš ( 2015-11-21 13:57:49 +0100 )editPodotkl bych taky, že verze se sortem dokáže docela dobře vypsat i tu nejčastější IP adresu, zatímco awk verze je omezena jen na výpis počtu výskytů (respektive, šlo by to udělat taky, ale náročnost velmi podstatně stoupne, u sortu to je "zadarmo"). Neznám zadání, třeba to není relevantní, ale zadání se může v testu snadno změnit a pak najednou s awk zjistíte, že musíte všechno vymýšlet znovu.
Josef Kokeš ( 2015-11-21 13:57:55 +0100 )editVloni jsem meril rozdily mezi pouziti sort a awk (mam podobne reseni jako Marek). Sort je radove pomalejsi [s], awk zvlada v [ms].
Mas pravdu, ze sort je $O(n*log n)$, ale asociativni pole je -- rekl bych -- dost efektivni. Je to velmi nativni pristup v awk, tudiz bude optimalizovane.
Je ale pravda, ze na gigabajtovych datech jsem to nezkousel.
Dobrá poznámka. Nedíval jsem se, jak se sort implementovaný, očekával jsem nějaký bubble sort (aby to bylo n když bude vstup seřazený). Řešení se sortem tedy bude 2*složitost sortu (jsou tam dva). Co jsem tím chtěl říct, že druhý sort je v každém případě zbytečný. Jde mi o nalezení max, což je O(n) vždy, není tedy potřeba používat druhý sort, který to může výrazně zpomalit. V zadání chceme jen počet, ne IP adresu. Proto je to řešeno takhle. Ale je to tu zadarmo taky = print max, i. Nic víc.
Marek Bartík ( 2015-11-21 14:03:09 +0100 )editTaky jsem se nedíval, jak je sort implementovaný, ale pro obecnou utilitu, která si musí poradit s libovolně velkými daty (a poradí, někdo mi takhle řešil kolizi v hashi, kde sortoval myslím 16 GiB soubor), je vhodný hlavně mergesort.
Ano, druhý sort je zbytečný a lze efektivně řešit tím awk. Pokud bych chtěl velmi často zjišťovat nejčastější IP adresy, určitě bych to tak dělal (kdybych si vzpoměl :-)). V testu bych ale doporučoval spíš obětovat výkon a jít na minimalizaci možných chyb, tzn. používat co možná nejmíň různých příkazů a způsobů jejich kombinace (tzn. radši dvakrát sort než jednou sort a jednou awk).
Každopádně znovu zopakuju - není jediné správné řešení, cokoliv, co vede k správnému výsledku, je OK.
Josef Kokeš ( 2015-11-21 14:09:32 +0100 )editpozn. k "Babicu" -- co to je? :-) -- jsi si jisty, ze ... | cut -d " " -f -2 | ... udela to, co chces? Vzdyt je tam opet problem s tim, kdy tam buodu 2 a kdy 3 sloupce
Ještě mě napadlo, aby snad neměl někdo dojem, že nemám awk rád: Ano, pro toto zadání jde o asi nejlepší řešení. Pro spoustu jiných zadání taky. Jen se snažím varovat před jeho slepým používáním na všechno, ty slabší nástroje jsou někdy přece jenom lepší. (U awk to až takový problém nebývá, ale obdobně si studenti navyknou na find a s tím pak bývají v testech problémy).
Kdybych psal test, tak určitě použiju 2x sort. Kdybych si psal oneliner na jeden menší (řádově max pár MB), tak taky použiju asi spíš 2x sort. Je to i přehlednější a hezky to sedí na filozofii filtrů. Vojto, imho to je jedno kolik tam bude sloupců, pomocí tr -s budu mít na začátku nejvýše jednu mezeru, pak mi cut vrátí dva sloupce, takže mezera před nebo za, toho se zbavim posledním tr. Nemám teď možnost to vyzkoušet ale Echo -e " 3 10.0.0.1\n2 10.0.0.2\n 5\10.0.0.3" | tr -s ' '... Zbytek. Sry, na mobilu se to hrozně blbě píše, nenechá mě tam dát víc mezer
Marek Bartík ( 2015-11-21 14:31:17 +0100 )editanswered 2015-11-18 00:29:28 +0100
Pridam sem svoje netrivialne riesenie:
grep -v '\[error\]' ./apache.log | sed -e 's/^.*\]: //' -e 's/ .*$//' | sort | uniq -c | sed -e 's/ *//' | sort -k1,1rn | cut -d' ' -f1,1 | head -n 1
Posledny sed je tam preto, lebo uniq ma tendenciu zarovnat count pomocou mezdier, sed tie medzery pozere.
Ac to funguje, radeji bych tam strcil kotvu: ... | sed -e 's/^ *// | ...
Podle mě to bez kotvy nefunguje. Příkladem je opět záznam, který se vyskytuje milionkrát, pokud jeho první znak je číslo (což jestli dobře chápu, že se v úloze počítají IP adresy, asi platit bude).
Josef Kokeš ( 2015-11-18 07:31:38 +0100 )edit@Josef Kokeš muj GNU sed 4.2.2string="1234567 127.0.0.1"echo "$string" | sed -e 's/^ *//'
vystup: 1234567 127.0.0.1echo "$string" | sed -e 's/ *//'
vystup: 1234567 127.0.0.1
Stejne chovani pozoruji i na fray1 i fray3.
Evidentne pozice matchnuteho stringu (co nejvic na zacatku) ma prednost pred hladovosti hvezdicky. Nicmene to je -- rekl bych -- uz hlubsi znalost RE. Proto bych tam tu kotvu dal a hned je videt, co jsem tim zamyslel ;]
Asked: 2015-11-17 21:36:42 +0100
Seen: 420 times
Last updated: Nov 22 '15
Copyright students of FIT CTU and others, 2014. Content on this site is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.
btw:
VojtechMyslivec ( 2015-11-17 22:38:13 +0100 )editsort -t'.' -k1,4nnedela to, co bys asi chtel. Nicmene to se v teto uloze netestuje. Staci ti "nejak" seradit IP adresy, aby se stejne dostaly k sobe, aby je mohluniqspocitat.Cislo, ktere obsahuje 3 oddelovace (
.) asi neexistuje. Pokud bys chtel ciselne seradit IP adresu, musis pouzit-n -k1,1 -k2,2 ...-- jinymi slovy vypsat vsechny key, podle kterych chces radit.btw2: za trapeni kocky buh zabije kotatko ;]