Použil jsem tři různé testovací adresáře. Jeden obsahoval jenom soubory, a to třicet tisíc, druhý obsahoval třicet tisíc adresářů a třetí po patnácti tisících od obojího. Počty v třetím případe nejsou naprosto přesné, adresářů tam může být o něco méně. Způsobené je to tím, že názvy jsou generovány skoro náhodně, aby se zajistilo náhodné pořadí.
Vygenerovat to jde dvěma jednoduchými cykly v Bashi.
for i in $(seq 1 30000); do
touch bench1/file-$i
mkdir bench2/dir-$i
done
for i in $(seq 1 15000); do
touch bench3/$(mkpasswd "file-$i" | sed "s@/@_@g")
mkdir bench3/$(mkpasswd "dir-$i" | sed "s@/@_@g")
done
První rozdíl v testovaných programech spočíval v tom, jak se zajistí, aby soubory byly vypsané dříve než adresáře. Nejjednodušší přístup spočívá v tom, že se adresář projde dvakrát, v prvním průchodu se ignorují adresáře, v druhém soubory.
Druhá a třetí metoda adresář procházejí jenom jednou a nalezené adresáře si pro pozdější zpracování ukládají buď do pole nebo spojového seznamu. Pole je po naplnění vždycky potřeba zvětšit, pokud se ale jeho velikost vždycky zdvojnásobí, složitost uložení nakonec vyjde konstantní. Každý uložený řetězec je taky potřeba naalokovat. Spojový seznam má sice taky konstantní složitost přidání prvku, ovšem vyžaduje na rozdíl od pole dvě alokace paměti.
Druhý rozdíl v testovaných programech spočívá v metodě určování typu položky. Použil jsem zase tři možnosti: pomocí funkce stat()
, pomocí položky d_type
ve struktuře dirent
a pomocí lehce uhozené heuristiky s opendir()
.
int is_dir(const char *path)
{
struct DIR *dir = opendir(path);
if (dir == NULL) {
return 0;
} else {
closedir(dir);
return 1;
}
}
Tato heuristika má ovšem zásadní problém v tom, že i adresáře, které se nepodařilo otevřít třeba kvůli oprávněním, nahlásí jako soubory.
Rozpoznávání pomocí d_type
je nejjednodušší, ale opět má nevýhody:
_DIRENT_HAVE_D_TYPE
)DT_UNKNOWN
a tedy je potřeba se s tím vyrovnatKaždý z devíti programů jsem spustil stokrát a výsledné časy zprůměroval. Metodika nic moc, ale nějaká představa se z toho udělat dá.
Soubory | Adresáře | Mix | |
---|---|---|---|
dvojitý průchod | |||
stat()
|
0,109 | 0,106 | 0.107 |
opendir()
|
0,133 | 0,177 | 0.155 |
d_type
|
0,043 | 0,040 | 0.042 |
Pole | |||
stat()
|
0,054 | 0,057 | 0.053 |
opendir()
|
0,067 | 0,091 | 0.080 |
d_type
|
0,021 | 0,021 | 0.020 |
Seznam | |||
stat()
|
0,053 | 0,060 | 0.058 |
opendir()
|
0,065 | 0,091 | 0.081 |
d_type
|
0,020 | 0,029 | 0.022 |
Ponaučení na závěr? Na metodě procházení příliš nezáleží. To, co se s nalezenými položkami bude dít, pravděpodobně zabere výrazně víc času, takže jinou metodou procházení se nedá nic ušetřit.
Všechny zdrojové soubory je možné si stáhnout včetně měřících skriptů. Skript prepare.sh
vytvoří testovací složky, measure.sh
spustí měření a test.sh
ověřuje, že všechny programy dávají stejný výstup na třetím testovacím adresáři.
První myslitelné kódování je klasický zápis čísla ve dvojkové soustavě. Jeho výhoda je velká úspornost, na druhou stranu každá posloupnost nul a jedniček se dá interpretovat jako číslo. My bychom ale chtěli poznat, kde jedno číslo končí a druhé začíná. Proto potřebujeme bezprefixový kód, tedy takový, aby žádné slovo nebylo prefixem jiného. Zároveň ale nechceme používat žádnou překladovou tabulku, takže Huffmanovo kódování je ze hry.
Nejjednodušší variantou, jak toho dosáhnout, je použít unární kódování. Číslo n zakóduje pomocí n nul následovaných jedničkou. Zřejmě je tedy bezprefixové, ale zároveň i paměťově neefektivní, protože délka kódu je lineární k velikosti kódovaného čísla.
Jako lepší nápad vypadá zapsání čísla binárně a přidání jeho délky pomocí nějakého bezprefixového kódu. To ale také není optimální, protože bychom nevyužili mnoho možností. Konkrétně jde o slova, která začínají nulami. V klasickém dvojkovém zápisu jsou čísla 00 a 0 stejná. Z našeho pohledu je ale užitečné je rozlišit. Proto pro každou délku kódu využijeme všechny možnosti, tedy pro slovem délky jedna budeme kódovat dvě čísla, délkou dvě čtyři atd.
Pro každé číslo tedy určíme délku slova, odečteme od něj nějakou hodnotu a převedeme do dvojkové soustavy. Délku určíme jako ⌊log2(n + 1)⌋. Zároveň z délky můžeme určit, o kolik zmenšit kódované číslo před převodem: 2l − 1.
Nejdříve tedy definice typů.
data Bit = Zero | One deriving (Eq)
instance Show Bit where
show Zero = "0"
show One = "1"
type Stream = [Bit]
Typy požadovaných funkcí vypadají následovně. Kódovací funkce pro číslo vrátí posloupnost bitů, dekódovací naopak z proudy bitů vytáhnou první číslo a vrátí ho společně se zbytkem proudu. Funkce fromBinary
se liší v tom, že zpracuje celý proud.
unary, binary, gamma, delta :: Int -> Stream
parseUnary, parseGamma, parseDelta :: Stream -> (Int, Stream)
fromBinary :: Stream -> Int
Unární kódování je velice jednoduché. Operátor (***) :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)
se nachází v modulu Control.Arrow
a jeho jediný účel je aplikace funkcí na složky dvojice.
unary n = replicate n Zero ++ [One]
parseUnary = (length *** tail) . span (== Zero)
Funkce pro binární kódování čísla jsou trošku složitější, ale pořád tam není žádná magie. Provádí klasický přepis čísla do dvojkové soustavy. Pomocná funkce binary'
navíc výsledný kód doplní zleva do požadované délky nulami. Také 0 při délce kódu 0 reprezentuje prázdným seznamem.
binary = bin []
where
bin acc 0 = Zero : acc
bin acc 1 = One : acc
bin acc n = bin ((if odd n then One else Zero) : acc) (n `div` 2)
binary' :: Int -> Int -> Stream
binary' 0 0 = []
binary' len n = padding ++ code
where code = binary n
padding = replicate (len - length code) Zero
fromBinary = foldl (\num x -> num * 2 + (if x == Zero then 0 else 1)) 0
Myšlenku popsanou na začátku realizují mimo jiné γ a δ kódy. γ-kód pro délku slova používá unární kódování, δ-kód jde ještě dál a používá pro zapsání délky γ-kód. Zřejmě jsou si tedy v mnohém podobná a má smysl nejdřív napsat obecnější funkci.
encodeWith :: (Int -> Stream) -> Int -> Stream
encodeWith f n = f len ++ binary' len (n - 2^len + 1)
where len = floor . logBase 2 . fromIntegral $ n + 1
parseWith :: (Stream -> (Int, Stream)) -> Stream -> (Int, Stream)
parseWith f s = (fromBinary bin + 2^len - 1, ss)
where (len, rest) = f s
(bin, ss) = splitAt len rest
S funkcemi encodeWith
, parseWith
je tedy implementace γ i δ kódování poměrně triviální.
gamma = encodeWith unary
parseGamma = parseWith parseUnary
delta = encodeWith gamma
parseDelta = parseWith parseGamma
Odtud už je jednoduché napsat funkci, které bude kódovat nebo dekódovat seznam čísel.
encode :: (Int -> Stream) -> [Int] -> Stream
encode = concatMap
decode :: (Stream -> (Int, Stream)) -> Stream -> [Int]
decode f s = let (n, ss) = f s
in case ss of
[] -> [n]
_ -> n : decode f ss
Upozornění: toto není úplně ideální implementace, protože umožňuje práci pouze s čísly omezené velikosti, navíc jsem se nesnažil o efektivitu, takže je to velice pomalé. Taky chybí jakákoli kontrola chyb.
]]>Poslední věc, na kterou jsem narazil a která mě donutila upravit xmonad.hs
bylo ne zrovna přátelské chování k oknům, která si nastavují nějakou požadovanou velikost. XMonad tyto rady totiž totálně ignoruje. Ve většině případů je to docela žádoucí chování, jediná výjimka jsou okna, u kterých nemá moc smysl měnit velikost. V mém případě šlo hlavně o Frozen Bubble a dosbox.
Jedna možnost řešení by bylo vyjmenovat dotyčné aplikace a přímo oknům nastavit režim floating. To se mi ale nelíbilo, protože by to nebylo ani pohodlné, ani spolehlivé, a často bych musel měnit konfiguraci.
Společným znakem oken, která mají fixní velikost, je nastavení minimální a maximální velikosti okna na stejnou hodnotu. Toto nastavení je v WM_NORMAL_HINTS
a dá se zjistit třeba přes xprop
. Toto pole má typ XSizeHints
a nejpřesnější popis, který jsem našel, vypadá takto:
typedef struct {
long flags; /* marks which fields in this
structure are defined */
int x, y; /* Obsolete */
int width, height; /* Obsolete */
int min_width, min_height;
int max_width, max_height;
int width_inc, height_inc;
struct {
int x; /* numerator */
int y; /* denominator */
} min_aspect, max_aspect;
int base_width, base_height;
int win_gravity;
/* this structure may be extended in the future */
} XSizeHints;
To jistě není žádný zázrak, ale už se s tím dá něco dělat. Zajímavé hodnoty jsou ty s prefixem min_
a max_
. Pokud jsou nastavené na jinou hodnotu než 0 a zároveň se rovnají odpovídající si hodnoty, okno má zřejmě nastavenou fixní velikost.
isFixed :: [CLong] -> Bool
isFixed h = minWidth h == maxWidth h
&& minHeight h == maxHeight h
&& all (>0) [minWidth h, maxWidth h, minHeight h, maxHeight h]
V modulu XMonad.Util.WindowProperties
je k dispozici funkce getProp32s :: String -> Window -> X (Maybe [CLong])
, s jejíž pomocí už se dá napsat potřebná funkce pro manage hook. Definice typu CLong
je v modulu Foreign.C.Types
.
isNonResizable :: Query Bool
isNonResizable = ask >>= \w -> liftX $ do
atom <- getProp32s "WM_NORMAL_HINTS" w
return $ case atom of
Just hints -> hasFixedSize hints
Nothing -> False
Poslední chybějící kus jsou funkce na vrácení požadovaných rozměrů. Vlastně jde jenom o čitelnější zápisy vytažení příslušné hodnoty ze seznamu:
minWidth = (!! 5) :: [CLong] -> CLong
minHeight = (!! 6) :: [CLong] -> CLong
maxWidth = (!! 7) :: [CLong] -> CLong
maxHeight = (!! 8) :: [CLong] -> CLong
A to je asi tak všechno. Zatím mám pocit, že to funguje, žádné chyby jsem nepozoroval. Kompletní soubor stačí nakopírovat do ~/.xmonad/lib/
, naimportovat do konfiguračního souboru a použít.
Já používám knihovnu UnitTest++, která je rozumným kompromisem mezi funkcionalitou a jednoduchostí.
Testy pomocí UnitTest++ je možné psát do libovolného souboru s příponou .cpp
i .cc
, jak je komu libo. Pro kompilaci je potřeba kompilátoru předat informace o tom, kde najde příslušné hlavičkové soubory a potom i knihovnu. Obojí jsem zkompiloval a je na Aise dostupné v adresáři /home/~xsedlar3/include
.
Na začátku testovacího souboru je pochopitelně třeba vložit hlavičky knihovny vlastního kódu, který je třeba testovat.
#include <unittest++/UnitTest++.h>
Ke spouštění testů je třeba přidat i funkci main
:
int main() {
return UnitTest::RunAllTests();
}
Jednotlivé testy se píšou pomocí maker TEST
, které má jeden parametr -- identifikátor, podle kterého půjde dohledávat, který test selhal. Následuje blok, ve kterém se provádí test.
TEST(Addition) {
CHECK(someFunction());
}
K usnadnění psaní testů je definováno několik šikovných maker jako je výše uvedené CHECK
. To jednoduše kontroluje, jestli se jeho argument vyhodnotí na true
. Další možnosti jsou třeba CHECK_EQUAL(co_cekam, testovany_vyraz)
, které ověří, že testovaný výraz vrací určenou hodnotu. Pořadí argumentů je tady docela důležité, pokud bude očekávaná hodnota jako druhá, případně chyby budou hlášené dost chaoticky. Další makra jsou popsána v dokumentaci.
Aby se i ve velkém souboru s testy dalo dobře orientovat, je možné jednotlivé testy dělit do sad pomocí makra SUITE(nazev)
, případně je rozdělit do více souborů.
Jednoduchý test tedy může vypadat takto:
TEST(InsertValueAtStart) {
List<int> list;
List<int>::ItemType *iter;
iter = list.push_front(10);
CHECK( ! list.empty());
CHECK_EQUAL(10, it->getValue());
CHECK_EQUAL(10, list.first()->getValue());
CHECK_EQUAL(10, list.last()->getValue());
}
Při psaní testů se dá velice rychle narazit na situaci, že se na začátku několika testů opakuje stejná část, která jenom chystá objekt na další testovaní, např. plní seznam daty. Toto se dá zjednodušit přesunutím takovéto inicializace do tzv. fixture.
V případě knihovny UnitTest++ se jedná o definici třídy, jejíž konstruktor se zavolá na začátku testu, kde je použitá, a celý test se potom vykonává tak, že má přímo přístup k členským prvkům dané třídy. Místo makra TEST
se potom použije TEST_FIXTURE
se dvěma argumenty. Prvním je právě název fixture.
Může to tedy vypadat takto:
struct LongList {
LongList() {
it1 = list.push_back(10);
it2 = list.push_back(20);
it3 = list.push_back(30);
it4 = list.push_back(40);
it5 = list.push_back(50);
it6 = list.push_back(60);
}
std::string to_str() { return list_to_str(list); }
List<int> list;
List<int>::ItemType *it1, *it2, *it3, *it4, *it5, *it6;
};
TEST_FIXTURE(LongList, SwapTwoDistinctIntervals) {
list.push_back(70);
list.swap(it2, it3, it5, it6);
CHECK_EQUAL("{ 10, 50, 60, 40, 20, 30, 70 }", to_str());
list.swap(it5, it6, it2, it3);
CHECK_EQUAL("{ 10, 20, 30, 40, 50, 60, 70 }", to_str());
}
Všechny testy se ukládají do speciálního adresáře. Já používám název tests
, ale prakticky na tom nezáleží. Každý tests se skládá alespoň ze dvou souborů s názvy třeba 01_valid_input.*
. Přípona souboru specifikuje, co soubor testuje.
*.in
*.args
*.out
*.err
*.ret
Pokud některý soubor neexistuje, tak se příslušná část netestuje.
Stáhněte si archiv s testovacím skriptem a pomocným souborem, který umožňuje vypisovat výsledky barevně. Skript stest
je dobré mít v cestě, .term_colors
může být buď přímo v domovském adresáři nebo na stejném místě jako stest
.
K testování stačí spustit příkaz stest ./NAZEV_BINARKY
, případně přidat ještě cestu k adresáři s testy. Další možnosti shrnuje nápověda stest --help
.
raw() a cbreak()
Normálně ovladač terminálu ukládá uživatelem zadané znaky do bufferu, dokud uživatel nestiskne enter. Většina programů ale potřebuje, aby byly znaky dostupné hned, když je uživatel zadá. Tyto dvě funkce zakazují bufferování řádků. Rozdíl mezi nimi je ve zpracování ovládacích znaků zadávaných z klávesnice (např. Ctrl-Z, Ctrl-C). Po zavolání raw() jsou tyto znaky předány programu a nevygenerují signál. V režimu cbreak() jsou tyto znaky interpretovány přímo ovladačem terminálu.
echo() a noecho()
Tyto funkce ovládají, jestli se znaky zadávané uživatelem zobrazují na obrazovku či nikoli. Většina interaktivních programů volá na začátku noecho() a pokud to potřebuje, tak znaky vypisuje kontrolovaně sama.
keypad()
Tato inicializační funkce umožňuje čtení funkčních kláves jako F1,, kurzorové klávesy atd. Téměř každý interaktivní program toto povoluje, protože šipky jsou zásadní částí každé uživatelského rozhraní. Abyste povolili tuto vlastnost pro standardní obrazovku (stdscr), zavolejte keypad(stdscr,TRUE)
.
halfdelay()
Přestože tato funkce není používaná příliš často, je občas velice užitečná. Vstup je okamžitě předán programu jako po zavolání cbreak()
s tím rozdílem, že čeká X desetin sekundy na vstup a jestliže potom není vstup dostupný, vrátí ERR. X je interval zadaný jako argument při volání halfdelay(). Tato funkce je užitečná, pokud potřebujete nějaký vstup, ale když uživatel neodpoví dostatečně rychle, chcete udělat něco jiného.
strcpy
se chová i free
.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int main (void)
{
const char * str1 = (char*) malloc(10*sizeof(char));
char * const str2 = (char*) malloc(10*sizeof(char));
const char * const str3 = (char*) malloc(10*sizeof(char));
str1 = NULL;
str2 = NULL;
str3 = NULL;
strcpy(str1, "a");
strcpy(str2, "a");
strcpy(str3, "a");
return 0;
}
x = NULL
|
strcpy(x, "a")
|
|
---|---|---|
const char *
|
OK |
error: invalid conversion from 'const char' to 'char'
|
char * const
|
error: assignment to read-only variable
|
OK |
const char * const
|
error: assignment to read-only variable
|
error: invalid conversion from 'const char' to 'char'
|
x = NULL
|
strcpy(x, "a")
|
|
---|---|---|
const char *
|
OK |
|
char * const
|
error: read-only variable is not assignable
|
OK |
const char * const
|
error: read-only variable is not assignable
|
|