véletlen kiválasztás

Szkriptek: Python, Perl, Bash, ...

Lenne pl egy fileban valamilyen szaparátorral (pl: '\n') elválasztott IP címek. Hogyan tudnék véletlenszrűen kiválasztani egyet egy bash script-tel.

  • 2283 megtekintés

( mozsaf | 2008. 10. 07., k – 23:22 )

Pontos megoldast hirtelen nem tudok, en igy jarnam be a fajlt...

cat iplista.txt | while read line;do
ip=`echo $line`;

done

Ebben az $ip valtozo egy ip, amivel barmit csinalhatunk most... csak kell valami random... agyalok, de gondoltam addig ideirom hatha masnak segit...

( apal v | 2008. 10. 07., k – 23:36 )

Pl igy: 


IPLIST=($(cat iplist.txt))
N=${#IPLIST[*]}
R=$RANDOM
x=$((R%N))

IP=${IPLIST[x]}

(az iplist.txt-ben sortoressel (megengedo") vagy szokozokkel vannak elvalasztva az ip-cimek)

A.

( egmont | 2008. 10. 07., k – 23:49 )

Erről jut eszembe, nagyon jópofa kis matek példa, és elég meglepő hogy meg lehet csinálni.

Jön egy baromi hosszú sorozat (mondjuk akár újsorral elválasztott IP-címek egy pipe-on keresztül), nem tudod előre hogy milyen hosszú, viszont sokkal hosszabb annál minthogy legyen esélyed eltárolni az egészet és utólag feldolgozni. Más szóval: baromi kevés memóriád van, és csak egyszer olvashatod el az inputot. A feladat ilyen körülmények között kiválasztani egy uniform random elemet.

Bónusz feladat: ha a matek példa megoldása megvan, akkor lekódolni bash-ben :)

1. Ha az elso" elemet olvasod be, beleteszed a kimeneti valtozoba.
2. Ha az N-ik elemet olvasod be, akkor 1/N valoszinuseggel beleteszed a kimeneti valtozoba (azaz dobsz egy 0 es N kozotti valos szamot, es ha 1-nel kisebb, akkor).
3. vege van a stream-nek: a kimeneti valtozo lesz a kivalasztott random elem.

Ez igy tul egyszerunek is hangzik ;) 


N=1
while read data ; do
        cat /dev/urandom | \
        head -c 8 | \
        hexdump -d | \
        head -n 1 | \
        awk -v N=$N \
        '{       x=0;
                 for ( i=2 ; i<=NF ; i++ ) 
                  { x=(x+$(i))/65536.0;  } 
                 if ( N*x<=1 )  exit(0);
                 else           exit(1);
         }' && OUT="$data"
        N=$((N+1))
done < data.txt
echo $OUT

Így van.

Nem semmi bash+awk mágiát dobtál össze :-) Azon gondolkodom, lehet-e lényegesen egyszerűbben, de nem hinném. Innen kezdve ízlések és pofonok... (Az eredeti elképzelésemben simán $RANDOM-ot használtam volna, de az bizony csak nagyon rövid inputokra jó.)

Vicces hogy a hexdump progit használod decimális szám kiírására, én pedig az od-t (octal dump) szoktam használni hexához. :D

Amit én tákolnék össze, az nagyjából úgy nézne ki, hogy a /dev/urandom byte-jait az
od -A n -t x1 | tr -d ' '
parancs hexásítja, amit még nagybetűssé kell alakítani, mert a bc-nek csak úgy lesz jó, sőt, akkor már helyette talán a egyszerűbb a
hexdump -v -e '1/1 "%02X"'
(hú, mire ezt összehoztam a manual alapján... nem csoda hogy nem szoktam hexdumpot használni), majd ha ez az érték a $K változóban van, az $N pedig az ami a te progidban is, akkor
echo "n=$N; ibase=16; k=$K; n%k" | bc -q
kimenetét kell megnézni hogy nulla-e, és ha igen, akkor frissíteni OUT-ot.

Valszeg ez az a feladat, amit józan ember nem bash-ben implementál :-)

Bónusz bónusz feladat igazi mazochistáknak: mind apal megoldása, mind az én megoldásom a rengeteg fork+exec miatt baromi lassú (minden bemeneti adatra jut több is). Normális programnyelven persze bárki le tudja kódolni ezt. Kódoljuk le bash-ben kizárólag beépített függvényekkel, külső program meghívása nélkül! :-)

Tenyleg szebb es gyorsabb igy :) 


cat data.txt | \
while read data ; do
        k=1
        o=0
        while true ; do
                M=$((32768))
                R=$RANDOM
                #M=$((32768*32768))
                #R=$((32768*RANDOM+RANDOM))
                d=$((k*M-N*R))
                if [ "$d" -ge $N ] ; then
                        o=1
                        break
                elif [ "$d" -lt 0 ] ; then
                        o=0
                        break
                else
                        k=$d
                fi
        done
        [ $o -gt 0 ] && echo "$data"
        N=$((N+1))
done | \
tail -n 1

(ha tobb mint 32k a varhato sorok szama, akkor a masodik M= es R= ertekadast kell hasznalni, bar igy is huzos a tulcsordulas, egesz szamoknal, persze azt is ki lehet hasznalni hogy a modern bash-oknal 64bites mar a $((...)) operacio).
Ja igen, es ez igy mar mukodik ugy is hogy pipe-rol, az elozo neme ment volna ugy :]

A.

Az a baj, hogy a $RANDOM egy nagyon primitív pszeudorandom: a következő érték egyértelműen megmondható az előző alapján. A /dev/(u)random szerintem nem hagyható ki a játékból.

Az első leküzdendő feladat: végtelen stream-ből véges hosszan olvasni tisztán bash-ben. A "read -r -d '' -n N" konstrukciónál jobbat nem találtam. Ez változóba teszi le az értéket, és változóban nullás byte nem lehet, ilyenkor ott megszakad az értéke, ezért ciklusba kell tenni és addig olvasni, amíg a kívánt mennyiségű adat meg nem jött. Tesztelendő, hogy az egyéb byte-okat mind jól kezeli-e, és a locale függvényében nem kezd-e el hülyeségeket csinálni (például UTF-8-ként értelmezni) - remélem nem.

Most jönne az a lépés, amikor egy byte-ot kellene átalakítani az ASCII kódjává, vagy bármely más módon egy random byteból vagy bytesorozatból egy számot előállítani. A tipikusan ord-nak hívott függvény bash megfelelőjére nem találtam rá. Nagyon gagyi megoldásként lehet valami iszonyú hosszú if-elif-elif-elif... ágat csinálni az átalakításra. Vagy spórolhatunk a kóddal ha pazaroljuk az inputot, például csak az A és B betűket vesszük figyelembe és ezekből építünk fel 2-es számrendszerben egy nagy számot, de a /dev/(u)random értékes entrópiából dolgozik, nem illik vele ilyen módon pazarolni.

Ha ez a lépés megvolna, akkor a többi már könnyedén megy.

Még egy apró megjegyzés: A generált véletlen egész lehetséges értékeinek száma aligha többszöröse az éppen aktuális N-nek. Ha teljesen pontos uniformot akarunk, akkor bizonyos esetekben új számot kell sorsolnunk. Példa: ha 0-2-ig kell véletlenszám, és egy 0-255-ig véletlenszámgenerárunk van, akkor mondhatjuk simán hogy modulo 3, de akkor a nullás valószínűsége icipicit nagyobb lesz. Erre nincs lényegesen jobb megoldás, mint jelen példában 255-ös érték esetén új véletlenszám sorsolása.

Az a baj, hogy a $RANDOM egy nagyon primitív pszeudorandom:
Akkor lehet irni egy viszonylag jobbat ;) A seed-et az elejen a /dev/[u]random-bol veszi (az lehet bonya, hexdump, awk) es kihasznaljuk hogy 64bites a $((...)). Ebbol igy mar teljesen jol tud dolgozni.
Pl az lrand48() manualja meg is adja hogy az a 48 bites randomgenerator milyen konstansokat hasznal. Oke, ez sem tokeletes, de egy bonyolultabb randomgenerator is hasonlo aritmetikakat tartalmaz, azt meg meg lehet irni shell-ben.

Még egy apró megjegyzés: A generált véletlen egész lehetséges értékeinek száma aligha többszöröse az éppen aktuális N-nek.
Ezt az esetet kezeli a szkript, azert van while true ... ; do kozott, es nem csak egy sima maradek (egyszeru" novekmenyes algoritmus, mint pl. az egyenes rajzolasa pixel-ra'csra). Ha az R tenyleg tok random akkor a sorok szama 1 es M-1 kozott barmi lehet, korrekt modon fog dolgozni, egyenletes eloszlast ad vissza akkor is.

A.

> Ezt az esetet kezeli a szkript

Jogos, nem néztem meg ennyire alaposan hogy mit csinálsz.

Közben megszületett az ord implementációm (képzeletben) bash-ben. Először csinálunk egy változót, aminek az értéke az 1-255 byte-ok egymás után. Ez mehet hard-coded módon: x=$'\001\002...@ABCD...\377', vagy generálható ciklusban a "printf %c $n" trükk használatával.

Ha ez megvan, akkor pedig jöhet a végéről lecsípő operátor: ha $c a karakter, akkor "${x%$c*}" lecsípi x végéről a $c-t és az azt követő részt, a maradékot adja vissza, aminek már csak a hosszát kell lekérdezni a ${#...} szintaxissal.

Még az sem kizárt, hogy ezzel a módszerrel a nullás input byte-ot sem kell eldobni. Ha $c-be olvasunk, akkor ez esetben ő nulla hosszú lesz, így a lecsípés+hosszszámítás után 255-öt kapunk, míg igazi karakter esetén 0-254-et (ord mínusz 1), szóval megvan a teljes 0..255 intervallum.

Szerk: printf-et félreismertem, visszavonom.

> Most jönne az a lépés, amikor egy byte-ot kellene átalakítani az ASCII kódjává, vagy bármely más módon egy random byteból vagy bytesorozatból egy számot előállítani. A tipikusan ord-nak hívott függvény bash megfelelőjére nem találtam rá. 


$ typeset -i x
$ x=36#abcd
$ echo $x
13368

Mondjuk nem teszteltem, hogy Ctrl-X meg egyéb (nem nyomtatható) karakter esetén mit csinál.

Hm, egyebkent erre a problemara deb alatt van egy `randomize-lines` csomag, 

rl

nevu" binarissal. Az `rl --count 1` ezt csinalja, pontosan, es nem zabal fel memoriat ;) Kerdes: hogyan kell az algoritmust modositani, hogy tetszoleges K db (K elore rogzitett) sort adjon vissza, 1/ mindegyiket max egyszer 2/ egy sor szerepelhet tobbszor is...

( NevemTeve | 2008. 10. 09., cs – 02:21 )

Nincs véletlenül egy 'random' nevű segédprogram épp erre a célra?

( axt v | 2008. 10. 09., cs – 16:59 )

Indokolja valami hogy bashban legyen az egész? Én tuti kiraknám a random generálást egy standalone alkalmazásba. Ha a fork-exec lassulás miatt aggodsz, sztem az megoldható valami named-pipe-on keresztül, amit a random process etet, a bash meg olvasgat.

A GSL-ben pl. van egy két pszeudórandom generátor, de ha nem akarsz dependency-t magaddal cipelni, akkor is ki lehet operálni valahonnan egy jó generátort. [ha kell el tudom küldeni a numercial_recipes ran0,ran1,ran2,ran3,ran4 generátorokat függőségek nélkül kioperálva, ha még megtalálom, mert régen használtam]

Vagy félreértettem valamit?

Indokolja valami hogy bashban legyen az egész
Az eredeti, felvetett problemara ez teljesen jo megoldas ;] (ha a $RANDOM nem elegge random akkor egy kis hexdump+/dev/random-mal ra lehet segiteni).

Egmont kollega altal felvetett problema mar mas kerdes, de ha csak egyedi esetekrol, nem massziv alkalmazasrol es relative rovid fileokrol van szo, akkor kis bash hax is tokeletesen megfelelo", arra a problemara is, szerintem.

A.