asked Nov 17 '15
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 -1V 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 Nov 17 '15
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 Nov 21 '15
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.logKdyž 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 -1Ně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
bartimar@fray1:~$ wc -l <apache.log
1000797
bartimar@fray1:~$ du -sh apache.log
140M apache.log
bartimar@fray1:~$ 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
bartimar@fray1:~$ 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.716sWebdev
bartimar@webdev-fit-01 ~ $ ll apache.log
-rw-r----- 1 bartimar users 145M Nov 21 20:52 apache.log
bartimar@webdev-fit-01 ~ $ 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
bartimar@webdev-fit-01 ~ $ 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.916sObecně 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š (Nov 21 '15)S 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š (Nov 21 '15)Podotkl 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š (Nov 21 '15)Vloni 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 (Nov 21 '15)answered Nov 17 '15
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 1Posledny 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š (Nov 18 '15)@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: Nov 17 '15
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 (Nov 17 '15)sort -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 ;]