Ask Your Question
2

Selftest 2: počítání klientů (demo)

asked 2015-11-17 21:36:42 +0100

uhlajs gravatar image

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.

edit retag flag offensive close delete

Comments

btw: sort -t'.' -k1,4n nedela 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 mohl uniq spocitat.
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 ;]

VojtechMyslivec ( 2015-11-17 22:38:13 +0100 )edit

3 Answers

Sort by » oldest newest most voted
2

answered 2015-11-17 21:59:33 +0100

Josef Kokeš gravatar image

updated 2015-11-17 22:00:05 +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ě...

edit flag offensive delete publish link more

Comments

souhlas ;]
jinymi slovy: co kdyz se jedna IP adresa vyskytne v souboru 1000000 krat?

VojtechMyslivec ( 2015-11-17 22:32:38 +0100 )edit
3

answered 2015-11-21 13:30:10 +0100

updated 2015-11-21 20:59:47 +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
edit flag offensive delete publish link more

Comments

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 )edit

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š ( 2015-11-21 13:57:49 +0100 )edit

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š ( 2015-11-21 13:57:55 +0100 )edit

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.

VojtechMyslivec ( 2015-11-21 14:02:39 +0100 )edit

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 )edit

Taky 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 )edit

pozn. 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

VojtechMyslivec ( 2015-11-21 14:17:59 +0100 )edit

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).

Josef Kokeš ( 2015-11-21 14:18:11 +0100 )edit

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 )edit
1

answered 2015-11-18 00:29:28 +0100

PeterBocan gravatar image

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.

edit flag offensive delete publish link more

Comments

aj ked viem, ze sa ho da zbavit prehodenim prikazov :D

PeterBocan ( 2015-11-18 00:35:03 +0100 )edit

Ac to funguje, radeji bych tam strcil kotvu: ... | sed -e 's/^ *// | ...

VojtechMyslivec ( 2015-11-18 00:45:37 +0100 )edit

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

No ano, ano... to by bol spravnejsi postup.

PeterBocan ( 2015-11-18 09:05:34 +0100 )edit

@Josef Kokeš muj GNU sed 4.2.2
string="1234567 127.0.0.1"
echo "$string" | sed -e 's/^ *//'
vystup: 1234567 127.0.0.1
echo "$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 ;]

VojtechMyslivec ( 2015-11-18 10:46:32 +0100 )edit

Your answer

Please start posting your answer anonymously - your answer will be saved within the current session and published after you log in or create a new account. Please try to give a substantial answer, for discussions, please use comments and please do remember to vote (after you log in)!

Add answer

[hide preview]

Question tools

Follow
2 followers

Stats

Asked: 2015-11-17 21:36:42 +0100

Seen: 420 times

Last updated: Nov 22 '15