Sortowanie w PostgreSQL
Jarek napisał ciekawy artykuł o sortowaniu napisów w PostgreSQL (i nie tylko, w zasadzie rzecz dotyczy localesów w glibc).
skrypty powłoki w Windows
Ciekawostka dla administratorów systemów z serii win2k/xp/itd itp.
Mamy sobie jakiegoś batcha:
C:\Temp>more test.cmd
@echo off
echo before sleep
c:\cygwin\bin\sleep 60
echo after sleep
I sobie go uruchamiamy.
C:\Temp>test.cmd
before sleep
Otwieramy drugi terminal, a w nim
C:\Temp>echo echo this was added after script was started >> test.cmd
Wracamy do pierwszego okienka i czekamy cierpliwie.
C:\Temp>test.cmd
before sleep
after sleep
this was added after script was started
życie jest pełne niespodzianek.
aha. jako ćwiczenie dla chętnych zostawiam sprawdzenie co się stanie, jesli zamiast dopisywać na koniec, dopiszemy np. 10 pustych linijek w środku skryptu :)
Sekretów zabójcy część druga
bluszcz napisał ciekawy opis kodu linuksowego OOM killera.
Zaciekawiony tematem pokopałem trochę i okazuje się co następuje:
W jednej ze starszych wersji jądra można było go w ogóle wyłączyć.
W 2.6.x z tego co widzę nie ma takiej możliwości.
Za to można wyłączać oom killer per proces!!!
Są sobie albowiem (przynajmniej w 2.6.21 które akurat mam pod ręką) pseudopliki:
/proc/<pid>/oom_score -- tu można podejrzeć aktualny badness score dla procesu,
oraz
/proc/<pid>/oom_adj - tu można sterować wysokością badness score :)
Dozwolone wartości to liczby całkowite z zakresu [-17,+15]. Wysoka wartość to większe prawdopodobieństwo zabicia.
/*
* Adjust the score by oomkilladj.
*/
if (p->oomkilladj) {
if (p->oomkilladj > 0)
points <<= p->oomkilladj;
else
points >>= -(p->oomkilladj);
}
Wartość -17 jest magiczna o tyle że blokuje w ogóle możliwość zabicia procesu przez oom killer.
if (p->oomkilladj == OOM_DISABLE)
continue;
Zatem nasz zabójca ma słaby punkt.
Stosować z umiarem!
Średnica zbioru
( Próba rozwiązania problemu który podsunął depesz )
Mamy dany na wejściu zbiór A punktów (powiedzmy że 2D), należy jak najefektywniej znaleźć parę punktów najbardziej odległą od siebie.
- Znajdujemy maksymalny wypukły podzbiór C zbioru A. Można spróbować powszechnie znanych algorytmów (tu, tu i tu). Jest nawet prezentacja (applet w Javie).
Można też wykorzystać gotową bibliotekę napisaną w C.
apt-get install libqhull5 libqhull-dev qhull-bin - C będzie istotnie mniejszy od A. W przybliżeniu:
|C| = O(log |A|)
(po polsku: liczba elementów C będzie proporcjonalna do logarytmu naturalnego z liczby elementów A)
Można to empirycznie sprawdzić następującym testem (rbox generuje zbiór losowych punktów, a qhull liczy dla nich maksymalny podzbiór wypukły):
for n in `seq 10 10 100 ; seq 5000 5000 100000`; do
vertices=`rbox $n D2 n z | qhull p | wc -l`
vertices=$[ vertices - 2 ]
logn=`echo "scale=2; l( $n ) " | bc -ql`
wsp=`echo "scale=2; $vertices / $logn " | bc -q`
echo -e "n=$n \t vertices=$vertices \t logn=$logn \t (vertices/logn)=$wsp"
done
- Dla znalezionego zbioru C stosujemy prosty algorytm do znalezienia najdłuższej odległości. Prosty czyli taki "każdy z każdym", który działa w O( n2 ).
- W sumie uzyskamy program działający w O( log2|A| ).
Nie liczę czasu spędzonego na wyliczaniu C. Wg autorów qhull jest to O( |A| log |C| ).
Pozostaje jeszcze zakodowanie tego w SQL... ale to chyba tylko takie zboczenie bazodanowca :)
