Obsah
1. Podpora funkcionálního programování v jazyku Lua s využitím knihovny Moses (dokončení)
2. Krátké zopakování z minula – funkce sortedk a sortedv
3. Testy (predikáty) prováděné nad prvky tabulky
5. Test, zda všechny prvky pole odpovídají zadané podmínce
6. Zjištění, kolikrát se prvek v tabulce opakuje
7. Zjištění, kolik prvků odpovídá zadanému testu (predikátu)
8. Operace prováděné nad dvojicí tabulek
9. Test, jestli má dvojice tabulek prvky se shodnými klíči
10. Test, zda tabulka obsahuje prvky s klíči získanými z jiné tabulky
11. Test, jestli mají dvě tabulky shodné hodnoty prvků
12. Složitější operace prováděné nad polem
13. Operace interpose – proložení prvků tabulky zvolenou konstantou
14. Operace interleave – proložení dvou tabulek do tabulky jediné
15. Operace permutation – výpočet všech permutací množiny představované prvky tabulky
16. Operace powerset – výpočet potenční množiny z množiny prvků
17. Operace shuffle – náhodné zamíchání prvků v poli
18. Repositář s demonstračními příklady
19. Články o programovacím jazyce Lua i o technologii LuaJITu
1. Podpora funkcionálního programování v jazyku Lua s využitím knihovny Moses (dokončení)
Na předchozí dva články [1] [2] o knihovně Moses určené pro použití v programovacím jazyku Lua dnes navážeme. Popíšeme si totiž zbývající funkce a metody, které je možné použít při zpracování polí (array) a slovníků (dictionary). Z předchozích dvou článků již víme, že obě dvě zmíněné datové struktury, i když mají dosti odlišnou sémantiku, jsou v programovacím jazyku Lua reprezentovány jediným unifikovaným typem nazvaným tabulka (table). Interně je tabulka rozdělena na dvě části – na prvky indexované celočíselným indexem a na prvky, ke kterým se přistupuje s využitím klíče (mimochodem – operátor # vracející délku pracuje korektně pouze pro první část tabulky).
V dnešním článku si opět ukážeme množství demonstračních příkladů, které budou tvořit nejvíce obsahu. Ještě předtím si ale ukážeme tabulku se všemi funkcemi a metodami, které jsme si již popsali, nebo které budou popsány dnes. U každé funkce je pochopitelně uveden i odkaz na článek a konkrétní kapitolu, v níž byla daná funkce nebo metoda popsána:
# | Funkce | Význam | Článek | Kapitola |
---|---|---|---|---|
1 | zeros | pole obsahující nulové prvky | 1 | 4 |
2 | ones | pole obsahující prvky s hodnotou 1 | 1 | 4 |
3 | rep | pole obsahující prvky se shodnou hodnotou předanou do konstruktoru | 1 | 4 |
4 | vector | implementuje stejnou funkcionalitu, jako konstruktor rep | 1 | 4 |
5 | range | pole s aritmetickou posloupností zadané délky | 1 | 5 |
6 | reverse | získání otočeného pole | 1 | 6 |
7 | first | získání prvních N prvků z pole | 1 | 7 |
8 | last | získání posledních N prvků z pole | 1 | 7 |
9 | initial | získání prvků z pole kromě posledních N prvků | 1 | 8 |
10 | rest | získání všech prvků z pole za indexem N | 1 | 8 |
11 | union | sjednocení dvou či více množin | 1 | 9 |
12 | intersection | průnik dvou či více množin | 1 | 9 |
13 | difference | rozdíl množin | 1 | 9 |
14 | symmetricDifference | symetrická diference (negace průniku) | 1 | 9 |
15 | push | připojení nové hodnoty za konec pole | 1 | 10 |
16 | unshift | odstranění a vrácení posledního prvku pole | 1 | 10 |
17 | shift | odstranění a vrácení prvního prvku pole | 1 | 11 |
18 | pop | jmenný alias k funkci shift | 1 | 12 |
19 | slice | provedení řezu polem | 1 | 13 |
20 | unique | získání unikátních prvků z pole | 1 | 14 |
21 | take_while | získání prvků ze začátku sekvence na základě zadané podmínky | 1 | 15 |
22 | drop_while | získání nové sekvence získané přeskočením prvků na začátku základě podmínky | 1 | 16 |
23 | filter | výběr prvků ze sekvence na základě zadané podmínky | 1 | 17 |
24 | sum | výpočet součtu všech prvků v tabulce | 2 | 2 |
25 | product | výpočet součinu všech prvků v tabulce | 2 | 2 |
26 | mean | výpočet průměru všech prvků | 2 | 3 |
27 | median | výpočet mediánu všech prvků | 2 | 3 |
28 | min | výběr prvku s minimální hodnotou | 2 | 3 |
29 | max | výběr prvku s maximální hodnotou | 2 | 3 |
30 | flatten | zpoštění pole s rekurzivními poli | 2 | 4 |
31 | compact | odstranění nepravdivých prvků z pole | 2 | 4 |
32 | xprod | vytvoření párů hodnot | 2 | 5 |
33 | reduce | zpracování tabulky prvek po prvku s akumulací mezivýsledků | 2 | 6 |
34 | reduceRight | dtto, ovšem zpracování začne od konce tabulky | 2 | 7 |
35 | groupBy | rozdělení prvků tabulky na základě uživatelské funkce | 2 | 8 |
36 | each | iterace nad prvky slovníku | 2 | 9 |
37 | eachi | iterace nad prvky pole | 2 | 10 |
38 | map | aplikace zvolené funkce na všechny prvky tabulky | 2 | 11 |
39 | chain | zřetězení většího množství operací | 2 | 12 |
40 | mapReduce | kombinace map a reduce | 2 | 14 |
41 | mapReduceRight | kombinace map a reduceRight | 2 | 15 |
42 | sortedk | průchod prvky tabulky setříděnými podle klíče | 2 | 16 |
43 | sortedv | průchod prvky tabulky setříděnými podle své hodnoty | 2 | 16 |
44 | some | zjištění, jestli tabulka obsahuje alespoň jeden prvek splňující zadanou podmínku | 3 | 4 |
45 | all | zjištění, jestli všechny prvky tabulky splňují zadanou podmínku | 3 | 5 |
46 | count | zjištění, kolik prvků tabulky má specifikovanou hodnotu | 3 | 6 |
47 | countf | zjištění, kolik prvků tabulky splňuje zadanou podmínku | 3 | 7 |
48 | sameKeys | test, jestli dvě tabulky obsahují prvky se shodnými klíči | 3 | 9 |
49 | containsKeys | test, jestli prvky z jedné tabulky mají klíče shodné s prvky ze druhé tabulky | 3 | 10 |
50 | same | test, jestli dvě tabulky obsahují shodné hodnoty (i když uložené pod jinými klíči) | 3 | 11 |
51 | interpose | proložení prvků tabulky zvolenou konstantou | 3 | 13 |
52 | interleave | proložení dvou tabulek do tabulky jediné | 3 | 14 |
53 | permutation | výpočet všech permutací množiny představované prvky tabulky | 3 | 15 |
54 | powerset | výpočet potenční množiny představované prvky tabulky | 3 | 16 |
55 | shuffle | náhodné zamíchání prvků v poli | 3 | 17 |
2. Krátké zopakování z minula – funkce sortedk a sortedv
Na konci předchozího článku jsme se v krátkosti zmínili o funkcích nazvaných sortedk a sortedv. První z těchto funkcí umožňuje iterovat přes všechny prvky tabulky, a to takovým způsobem, jakoby prvky byly setříděny podle svého klíče. Obecně sice platí, že v tabulce není zachováno pořadí prvků, ovšem právě existence funkce sortedk nám umožňuje s tabulkou pracovat jako se slovníkem setříděným podle klíčů:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- oddělení obsahu function printSeparator() print("-------------------------------") end a = {} -- naplnění pole for i = 1, 9 do a[tostring(i)] = i end printSeparator() -- tisk pole for key, value in pairs(a) do print(key, value) end printSeparator() -- tisk pole setříděného podle klíčů for key, value in sortedk(a) do print(key, value) end
Z výsledků je patrné, že v prvním výpisu je pořadí z pohledu uživatele náhodné, kdežto ve druhém případě jsou prvky seřazeny podle klíčů (klíče jsou řetězci):
------------------------------- 5 5 4 4 3 3 2 2 9 9 8 8 7 7 6 6 1 1 ------------------------------- 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9
Setřídění podle hodnot zajišťuje funkce sortedv, což je v demonstračním příkladu ukázáno v poslední smyčce:
a = {} -- naplnění pole for i = 1, 9 do a[tostring(i)] = 1/i end printSeparator() -- tisk pole for key, value in pairs(a) do print(key, value) end printSeparator() -- tisk pole setříděného podle klíčů for key, value in sortedk(a) do print(key, value) end printSeparator() -- tisk pole setříděného podle hodnot for key, value in sortedv(a) do print(key, value) end
Výsledky:
------------------------------- 9 0.11111111111111 8 0.125 3 0.33333333333333 2 0.5 1 1.0 7 0.14285714285714 6 0.16666666666667 5 0.2 4 0.25 ------------------------------- 1 1.0 2 0.5 3 0.33333333333333 4 0.25 5 0.2 6 0.16666666666667 7 0.14285714285714 8 0.125 9 0.11111111111111 ------------------------------- 9 0.11111111111111 8 0.125 7 0.14285714285714 6 0.16666666666667 5 0.2 4 0.25 3 0.33333333333333 2 0.5 1 1.0
3. Testy (predikáty) prováděné nad prvky tabulky
Další čtveřice funkcí slouží ke zjištění vlastností prvků v tabulce (či mnohem častěji v poli). Jedná se o relativně jednoduché funkce, které ovšem v programovém kódu dokáží nahradit programové smyčky a podmínky za jediné zavolání funkce (což samozřejmě snižuje počet chyb, čas na vytvoření jednotkových testů apod.):
# | Test | Stručný popis |
---|---|---|
1 | some | test na existenci alespoň jednoho prvku s danou hodnotou či odpovídajícímu podmínce |
2 | all | test, jestli všechny prvky v poli odpovídají zadané podmínce |
3 | count | zjištění, kolikrát se prvek v tabulce opakuje |
4 | countf | Zjištění, kolik prvků odpovídá zadanému testu (predikátu) |
4. Vyhledání prvku v tabulce
Prvním z predikátů je funkce, která otestuje, zda pole obsahuje prvek se zadanou hodnotou. Tento predikát se jmenuje some a vrací pravdivostní hodnotu True v případě, že alespoň jeden prvek v poli odpovídá prvku hledanému. V opačném případě se vrací pravdivostní hodnota False. Užitečné ovšem je, že hledaný prvek nemusí být zadán pouze hodnotou, ale i funkcí s podmínkou. Například můžeme otestovat, jestli pole obsahuje alespoň jeden prvek větší než nula atd. Oba typy testů jsou použity v dalším demonstračním příkladu:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- oddělení obsahu function printSeparator() print("-------------------------------") end a = {} -- naplnění pole for i = 1, 9 do a[tostring(i)] = 1/i end printSeparator() -- tisk pole for key, value in pairs(a) do print(key, value) end printSeparator() -- několik testů na vlastnosti prvků tabulky print("some(a, 0.5):", some(a, 0.5)) print("some(a, 1.5):", some(a, 1.5)) print("some(a, lambda x: x < 0.2):", some(a, function (x) return x < 0.2 end)) print("some(a, lambda x: x > 2.0):", some(a, function (x) return x > 2.0 end)) printSeparator()
Po spuštění demonstračního příkladu se nejdříve vypíše původní pole a poté se zobrazí výsledek čtyř testů: zda pole obsahuje prvek rovný 0,5, zda pole obsahuje prvek rovný 1,5, zda pole obsahuje prvek větší než 0,2 a konečně jestli pole obsahuje prvek větší než 2,0:
------------------------------- 5 0.2 6 0.16666666666667 3 0.33333333333333 4 0.25 1 1.0 2 0.5 9 0.11111111111111 7 0.14285714285714 8 0.125 ------------------------------- some(a, 0.5): true some(a, 1.5): false some(a, lambda x: x < 0.2): true some(a, lambda x: x > 2.0): false -------------------------------
5. Test, zda všechny prvky pole odpovídají zadané podmínce
Dalším predikátem je test, jestli všechny prvky v poli odpovídají zadané podmínce. Tento predikát se jmenuje all a opět mu lze předat buď hodnotu prvku (testuje se, zda pole obsahuje všechny prvky s touto hodnotou) nebo funkce s podmínkou. Typicky se tato funkce zapisuje jako funkce anonymní, ovšem pochopitelně nám nic nebrání použít i běžnou pojmenovanou funkci. To je ukázáno na dalším demonstračním příkladu, který otestuje, jestli jsou všechny prvky menší než nula, větší než nula, v rozsahu od 0 do 1 (kromě) či v rozsahu od 0 do 1 (včetně):
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- oddělení obsahu function printSeparator() print("-------------------------------") end a = {} -- naplnění pole for i = 1, 9 do a[tostring(i)] = 1/i end printSeparator() -- tisk pole for key, value in pairs(a) do print(key, value) end printSeparator() -- několik testů na vlastnosti prvků tabulky print("all(a, lambda x: x < 0.0):", all(a, function (x) return x < 0.0 end)) print("all(a, lambda x: x > 0.0):", all(a, function (x) return x > 0.0 end)) print("all(a, lambda x: 0.0 < x < 1.0):", all(a, function (x) return 0.0 < x and x < 1.0 end)) print("all(a, lambda x: 0.0 <= x <= 1.0):", all(a, function (x) return 0.0 <= x and x <= 1.0 end)) printSeparator()
Po spuštění se opět nejdříve vypíše obsah původního pole a následně i výsledky všech čtyř testovaných podmínek:
------------------------------- 9 0.11111111111111 8 0.125 7 0.14285714285714 6 0.16666666666667 5 0.2 4 0.25 3 0.33333333333333 2 0.5 1 1.0 ------------------------------- all(a, lambda x: x < 0.0): false all(a, lambda x: x > 0.0): true all(a, lambda x: 0.0 < x < 1.0): false all(a, lambda x: 0.0 <= x <= 1.0): true -------------------------------
6. Zjištění, kolikrát se prvek v tabulce opakuje
Funkce some popř. all vracely pouze pravdivostní hodnoty na základě hodnot všech prvků v tabulce. Ovšem v některých případech je užitečné vědět, kolik prvků má zadanou hodnotu popř. kolik prvků odpovídá specifikované podmínce. A právě k tomuto účelu slouží funkce nazvané count a countf. První z těchto funkcí projde celou tabulkou (či častěji polem) a zjistí počet prvků s hodnotou, která je do funkce count předána (ve druhém parametru – prvním parametrem je samotná tabulka). Podívejme se nyní na jednoduchý demonstrační příklad:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArrayInLine(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do io.write(value) if i ~= #array then io.write(", ") end end print() end -- oddělení obsahu function printSeparator() print("-------------------------------") end -- vytvoření a naplnění pole o sto prvcích a={} for i = 1, 100 do -- náhodná hodnota v rozsahu 1 až 10 a[i] = math.random(10) end -- vytištění původního pole printSeparator() print("Original array") printArrayInLine(a) for i = 1, 10 do print("count(" .. i .. "): " .. count(a, i)) end
Demonstrační příklad nejdříve vypíše původní pole s náhodnými hodnotami v rozsahu 1 až 10 a následně zobrazí, kolik prvků má hodnotu 1, kolik 2 atd. (jedná se tedy o formu histogramu):
------------------------------- Original array 9, 4, 8, 8, 10, 2, 4, 8, 3, 6, 5, 7, 4, 6, 10, 10, 7, 8, 2, 7, 1, 3, 2, 9, 2, 5, 2, 2, 10, 3, 6, 9, 7, 3, 7, 6, 5, 10, 3, 8, 6, 8, 5, 9, 3, 4, 9, 10, 1, 10, 6, 1, 2, 7, 9, 4, 1, 1, 5, 1, 3, 10, 10, 9, 3, 6, 4, 8, 6, 7, 6, 1, 5, 10, 10, 8, 3, 8, 7, 4, 7, 2, 5, 9, 9, 4, 3, 9, 4, 7, 10, 6, 7, 9, 5, 10, 4, 9, 7, 10 count(1): 7 count(2): 8 count(3): 10 count(4): 10 count(5): 8 count(6): 10 count(7): 12 count(8): 9 count(9): 12 count(10): 14
Počet náhodných prvků v poli můžeme zvýšit až na 100000. Potom lze předpokládat, že histogram bude v každém svém bucketu obsahovat přibližně 10000 prvků, tedy 10% všech prvků:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- vytvoření a naplnění pole o sto tisících prvcích a={} for i = 1, 100000 do -- náhodná hodnota v rozsahu 1 až 10 a[i] = math.random(10) end for i = 1, 10 do print("count(" .. i .. "):\t" .. count(a, i) .. "\t== " .. 100.0 * count(a, i)/100000 .. "%") end
Výsledky získané příkladem odpovídají předpokladu:
count(1): 9993 == 9.993% count(2): 9932 == 9.932% count(3): 10189 == 10.189% count(4): 10016 == 10.016% count(5): 9908 == 9.908% count(6): 10044 == 10.044% count(7): 9959 == 9.959% count(8): 9925 == 9.925% count(9): 10017 == 10.017% count(10): 10017 == 10.017%
7. Zjištění, kolik prvků odpovídá zadanému testu (predikátu)
Funkce count dokáže zjistit počet prvků se specifikovanou hodnotou, ovšem mnohdy je nutné použít složitější podmínku než „je roven“. V tomto případě se namísto funkce count použije funkce countf, která ve svém druhém parametru akceptuje funkci – predikát – aplikovaný na každý prvek vstupního pole. Ukažme si opět demonstrační příklad, který do jisté míry analyzuje pole s prvky s náhodnou hodnotou:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArrayInLine(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do io.write(value) if i ~= #array then io.write(", ") end end print() end -- oddělení obsahu function printSeparator() print("-------------------------------") end -- vytvoření a naplnění pole o sto prvcích a={} for i = 1, 100 do -- náhodná hodnota v rozsahu 1 až 10 a[i] = math.random(10) end -- vytištění původního pole printSeparator() print("Original array") printArrayInLine(a) for i = 1, 11 do print("<" .. i .. "\t" .. countf(a, function(x) return x < i end)) end
Po spuštění se vypíše původní pole a následně počet prvků menších než zadaná hodnota. Na konci (poslední podmínka) se pochopitelně musí zobrazit počet prvků odpovídajících počtu prvků ve vstupním poli:
------------------------------- Original array 9, 4, 8, 8, 10, 2, 4, 8, 3, 6, 5, 7, 4, 6, 10, 10, 7, 8, 2, 7, 1, 3, 2, 9, 2, 5, 2, 2, 10, 3, 6, 9, 7, 3, 7, 6, 5, 10, 3, 8, 6, 8, 5, 9, 3, 4, 9, 10, 1, 10, 6, 1, 2, 7, 9, 4, 1, 1, 5, 1, 3, 10, 10, 9, 3, 6, 4, 8, 6, 7, 6, 1, 5, 10, 10, 8, 3, 8, 7, 4, 7, 2, 5, 9, 9, 4, 3, 9, 4, 7, 10, 6, 7, 9, 5, 10, 4, 9, 7, 10 <1 0 <2 7 <3 15 <4 25 <5 35 <6 43 <7 53 <8 65 <9 74 <10 86 <11 100
Lépe je rozložení hodnot v rozsahu 1 až 10 patrné na poli s mnohem větším počtem prvků:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- vytvoření a naplnění pole o sto tisících prvcích a={} for i = 1, 100000 do -- náhodná hodnota v rozsahu 1 až 10 a[i] = math.random(10) end for i = 1, 11 do print("<" .. i .. "\t" .. countf(a, function(x) return x < i end)) end
Nyní by jednotlivé podmínky měly platit pro přibližně 10000, 20000, 30000 atd. prvků, což lze snadno ověřit:
<1 0 <2 9993 <3 19925 <4 30114 <5 40130 <6 50038 <7 60082 <8 70041 <9 79966 <10 89983 <11 100000
8. Operace prováděné nad dvojicí tabulek
Další sada operací (a funkcí, které tyto operace implementují) bude prováděná nad dvojicí tabulek. Velmi často se totiž setkáme s požadavkem na zjištění, zda jsou dvě tabulky zcela shodné (mají stejný obsah), zda jedna tabulka obsahuje všechny klíče obsažené ve druhé tabulce nebo zda obě tabulky obsahují stejné hodnoty (ovšem ty mohou být uloženy pod různými klíči). Implementace těchto testů si při „ručním“ programování žádá použití vnořených smyček for a několika podmínek. Je tedy nepochybně dobré, že jsou tyto funkce již v knihovně Moses implementovány a otestovány. Jedná se o tyto funkce:
# | Funkce | Stručný popis |
---|---|---|
1 | sameKeys | test, jestli dvě tabulky obsahují prvky se shodnými klíči |
2 | containsKeys | test, jestli prvky z jedné tabulky mají klíče shodné s prvky ze druhé tabulky |
3 | same | test, jestli dvě tabulky obsahují shodné hodnoty (i když uložené pod jinými klíči) |
b={} b["Leden"] = 0 b["Únor"] = 0 b["Březen"] = 0 b["Duben"] = 100 b["Květen"] = 0 b["Červen"] = 0 b["Červenec"] = 60 b["Srpen"] = 70 b["Září"] = 0 b["Říjen"] = 0 b["Listopad"] = 90 b["Prosinec"] = 10 c={} c["a"] = 0 c["b"] = 0 c["c"] = 0 c["d"] = 100 c["e"] = 0 c["f"] = 0 c["g"] = 60 c["h"] = 70 c["i"] = 0 c["j"] = 0 c["k"] = 90 c["l"] = 10
9. Test, jestli má dvojice tabulek prvky se shodnými klíči
První testovací funkce se jmenuje sameKeys a jedná se o přiléhavý název, protože tato funkce skutečně zjišťuje, jestli dvě tabulky obsahují prvky se shodnými klíči (na pořadí samozřejmě nezáleží – to ostatně nijak neovlivníme), bez ohledu na konkrétní hodnoty těchto prvků. Demonstrační příklad ukazující chování této funkce bude jednoduchý a přímočarý:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk tabulky function printTable(table) for key, value in pairs(table) do print(key, value) end end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění první tabulky a={} a["Leden"] = 10 a["Únor"] = 20 a["Březen"] = 30 a["Duben"] = 0 a["Květen"] = 40 a["Červen"] = 50 a["Červenec"] = 60 a["Srpen"] = 0 a["Září"] = 70 a["Říjen"] = 80 a["Listopad"] = 90 a["Prosinec"] = 100 -- vytvoření a naplnění druhé tabulky b={} b["Leden"] = 0 b["Únor"] = 0 b["Březen"] = 0 b["Duben"] = 100 b["Květen"] = 0 b["Červen"] = 0 b["Červenec"] = 60 b["Srpen"] = 70 b["Září"] = 0 b["Říjen"] = 0 b["Listopad"] = 90 b["Prosinec"] = 10 -- vytvoření a naplnění druhé tabulky c={} c["Leden"] = 0 c["Únor"] = nil c["Březen"] = 0 c["Duben"] = 100 c["Květen"] = 0 c["Červen"] = 0 c["Červenec"] = 60 c["Srpen"] = 70 c["Září"] = nil c["Říjen"] = 0 c["Listopad"] = 90 c["Prosinec"] = 10 printSeparator() printTable(a) printSeparator() printTable(b) printSeparator() printTable(c) printSeparator() print("sameKeys(a, b):", sameKeys(a, b)) print("sameKeys(a, c):", sameKeys(a, c))
Ze zobrazených výsledků je patrné, že tabulky a a b skutečně mají stejné klíče, kdežto tabulka c nikoli (to je způsobeno použitím hodnoty nil, která prvek z tabulky de facto odstraní, což je poměrně problematická vlastnost programovacího jazyka Lua):
-------------------------------------------- Srpen 0 Září 70 Listopad 90 Březen 30 Leden 10 Prosinec 100 Červenec 60 Únor 20 Říjen 80 Červen 50 Duben 0 Květen 40 -------------------------------------------- Srpen 70 Září 0 Listopad 90 Březen 0 Leden 0 Prosinec 10 Červenec 60 Únor 0 Říjen 0 Červen 0 Duben 100 Květen 0 -------------------------------------------- Srpen 70 Listopad 90 Březen 0 Leden 0 Prosinec 10 Červenec 60 Říjen 0 Červen 0 Duben 100 Květen 0 -------------------------------------------- sameKeys(a, b): true sameKeys(a, c): false
10. Test, zda tabulka obsahuje prvky s klíči získanými z jiné tabulky
Druhá testovací funkce se jmenuje containsKeys. Tato funkce zjišťuje, jestli první tabulka obsahuje všechny klíče, které jsou v tabulce druhé. Jedná se tedy o nesymetrickou operaci, kdy containsKeys(a,b) může dát opačný výsledek než containsKeys(b,a). Opět si chování vyzkoušejme na demonstračním příkladu:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk tabulky function printTable(table) for key, value in pairs(table) do print(key, value) end end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění první tabulky a={} a["Leden"] = 10 a["Únor"] = 20 a["Březen"] = 30 a["Duben"] = 0 a["Květen"] = 40 a["Červen"] = 50 a["Červenec"] = 60 a["Srpen"] = 0 a["Září"] = 70 a["Říjen"] = 80 a["Listopad"] = 90 a["Prosinec"] = 100 -- vytvoření a naplnění druhé tabulky b={} b["Leden"] = 0 b["Únor"] = 0 b["Březen"] = 0 b["Duben"] = 100 b["Květen"] = 0 b["Červen"] = 0 b["Červenec"] = 60 b["Srpen"] = 70 b["Září"] = 0 b["Říjen"] = 0 b["Listopad"] = 90 b["Prosinec"] = 10 -- vytvoření a naplnění třetí tabulky c={} c["Leden"] = 0 c["Únor"] = nil c["Březen"] = 0 c["Duben"] = 100 c["Květen"] = 0 c["Červen"] = 0 c["Červenec"] = 60 c["Srpen"] = 70 c["Září"] = nil c["Říjen"] = 0 c["Listopad"] = 90 c["Prosinec"] = 10 printSeparator() printTable(a) printSeparator() printTable(b) printSeparator() printTable(c) printSeparator() print("containsKeys(a, b):", containsKeys(a, b)) print("containsKeys(b, a):", containsKeys(b, a)) print() print("containsKeys(a, c):", containsKeys(a, c)) print("containsKeys(c, a):", containsKeys(c, a))
Nyní si zobrazme výsledky:
-------------------------------------------- Červenec 60 Říjen 80 Květen 40 Červen 50 Srpen 0 Duben 0 Březen 30 Leden 10 Listopad 90 Září 70 Prosinec 100 Únor 20 -------------------------------------------- Červenec 60 Říjen 0 Květen 0 Červen 0 Srpen 70 Duben 100 Březen 0 Leden 0 Listopad 90 Září 0 Prosinec 10 Únor 0 -------------------------------------------- Červenec 60 Říjen 0 Květen 0 Červen 0 Srpen 70 Leden 0 Březen 0 Listopad 90 Prosinec 10 Duben 100 -------------------------------------------- containsKeys(a, b): true containsKeys(b, a): true containsKeys(a, c): true containsKeys(c, a): false
Na posledních pěti řádcích výstupu je patrná nesymetričnost tohoto testu, což je ovšem plně pochopitelné z vlastnosti, kterou testujeme.
11. Test, jestli mají dvě tabulky shodné hodnoty prvků
Poslední testovací operace se jmenuje same. Jedná se o poměrně zvláštní operaci (resp. přesněji řečeno její název může být matoucí), protože se testuje, zda dvě tabulky obsahují shodné hodnoty, ovšem bez ohledu na klíče. Operaci prováděnou funkcí same si opět otestujeme na příkladu, kde dvě tabulky obsahují hodnoty navázané na jména měsíců, kdežto tabulka poslední má zcela odlišné klíče:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk tabulky function printTable(table) for key, value in pairs(table) do print(key, value) end end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění první tabulky a={} a["Leden"] = 10 a["Únor"] = 20 a["Březen"] = 30 a["Duben"] = 0 a["Květen"] = 40 a["Červen"] = 50 a["Červenec"] = 60 a["Srpen"] = 0 a["Září"] = 70 a["Říjen"] = 80 a["Listopad"] = 90 a["Prosinec"] = 100 -- vytvoření a naplnění druhé tabulky b={} b["Leden"] = 0 b["Únor"] = 0 b["Březen"] = 0 b["Duben"] = 100 b["Květen"] = 0 b["Červen"] = 0 b["Červenec"] = 60 b["Srpen"] = 70 b["Září"] = 0 b["Říjen"] = 0 b["Listopad"] = 90 b["Prosinec"] = 10 -- vytvoření a naplnění třetí tabulky c={} c["a"] = 0 c["b"] = 0 c["c"] = 0 c["d"] = 100 c["e"] = 0 c["f"] = 0 c["g"] = 60 c["h"] = 70 c["i"] = 0 c["j"] = 0 c["k"] = 90 c["l"] = 10 printSeparator() printTable(a) printSeparator() printTable(b) printSeparator() printTable(c) printSeparator() print("same(a, b):", same(a, b)) print("same(b, a):", same(b, a)) print() print("same(b, c):", same(b, c)) print("same(c, b):", same(c, b))
Výsledky ukazují, že první dvě tabulky mají hodnoty odlišné, kdežto tabulky b a c shodné (i když klíče jsou naprosto jiné):
-------------------------------------------- Říjen 80 Listopad 90 Prosinec 100 Duben 0 Leden 10 Srpen 0 Březen 30 Červen 50 Září 70 Únor 20 Červenec 60 Květen 40 -------------------------------------------- Říjen 0 Listopad 90 Prosinec 10 Duben 100 Leden 0 Srpen 70 Březen 0 Červen 0 Září 0 Únor 0 Červenec 60 Květen 0 -------------------------------------------- a 0 b 0 k 90 l 10 i 0 j 0 g 60 h 70 e 0 f 0 c 0 d 100 -------------------------------------------- same(a, b): false same(b, a): false same(b, c): true same(c, b): true
12. Složitější operace prováděné nad polem
Ve druhé části článku si popíšeme některé složitější operace prováděné nad poli. Některé z těchto funkcí považují obsah pole, tedy jednotlivé prvky, za množinu. Týká se to především funkce powerset, která dokáže vypočítat potenční množinu vstupní množiny. Podobně funkce permutation určená pro výpočet všech permutací vstupní množiny (resp. jejich prvků).
13. Operace interpose – proložení prvků tabulky zvolenou konstantou
Další funkcí, s níž se v dnešním článku setkáme, je funkce nazvaná interpose (v knihovně Lua Fun se pro změnu jmenovala intersperse). Tato funkce slouží k vytvoření nové tabulky z tabulky zdrojové. Ovšem v nové tabulce budou prvky proloženy nějakou další hodnotou, což v praxi znamená, že nová tabulka bude mít dvojnásobnou délku v porovnání s tabulkou zdrojovou (ve skutečnosti bude délka kratší o jeden prvek, protože se jedná o proložení).
Pochopitelně si toto chování opět ověříme na jednoduchém demonstračním příkladu, v němž bude použito zdrojové pole s deseti numerickými prvky:
-- vytvoření a naplnění pole o deseti prvcích a={} for i = 1, 10 do a[i] = 1.0 / i end
Tyto prvky budou proloženy nulou, takže výsledkem bude pole, v němž bude každý sudý prvek nulový. Zdrojový kód tohoto příkladu naleznete na adrese https://github.com/tisnik/functional-lua/blob/master/moses/61_interpose.lua:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArray(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do print(value) end print() end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění pole o deseti prvcích a={} for i = 1, 10 do a[i] = 1.0 / i end -- vytištění původního pole printSeparator() print("Original array") printArray(a) printSeparator() print("Interposed array") b = interpose(a, 0) printArray(b)
Po spuštění tohoto demonstračního příkladu se vypíše:
-------------------------------------------- Original array 1.0 0.5 0.33333333333333 0.25 0.2 0.16666666666667 0.14285714285714 0.125 0.11111111111111 0.1 -------------------------------------------- Interposed array 1.0 0 0.5 0 0.33333333333333 0 0.25 0 0.2 0 0.16666666666667 0 0.14285714285714 0 0.125 0 0.11111111111111 0 0.1
Samozřejmě nám nic nebrání použít pole s řetězci a pro proložení použít další řetězec. Upravený demonstrační příklad, v němž se používají jména měsíců, je dostupný na adrese https://github.com/tisnik/functional-lua/blob/master/moses/62_interpose_string.lua:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArray(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do print(value) end print() end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění pole o dvanácti prvcích a={"Leden", "Únor", "Březen", "Duben", "Květen", "Červen", "Červenec", "Srpen", "Září", "Říjen", "Listopad", "Prosinec"} -- vytištění původního pole printSeparator() print("Original array") printArray(a) printSeparator() print("Interposed array") b = interpose(a, "") printArray(b)
S výsledky:
-------------------------------------------- Original array Leden Únor Březen Duben Květen Červen Červenec Srpen Září Říjen Listopad Prosinec -------------------------------------------- Interposed array Leden Únor Březen Duben Květen Červen Červenec Srpen Září Říjen Listopad Prosinec
14. Operace interleave – proložení dvou tabulek do tabulky jediné
Existuje ještě jedna podobná operace, která se jmenuje interleave. Tato operace dokáže provést proložení dvou tabulek (resp. přesněji řečeno prvků v těchto tabulkách) do tabulky jediné, přičemž se prvky v nové tabulce střídají: prvek z první tabulky, prvek ze druhé tabulky, další prvek z první tabulky… Tuto funkci je možné použít i ve chvíli, kdy vstupní tabulky mají rozdílný počet prvků. V tomto případě se zbytek delší tabulky po vyčerpání všech dvojic zkopíruje do tabulky výsledné.
V prvním demonstračním příkladu mají obě vstupní tabulky shodný počet prvků. Konkrétně první tabulka obsahuje sekvenci numerických hodnot 1 až 12 a tabulka druhá pak jména měsíců:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArray(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do print(value) end print() end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění prvního pole o dvanácti prvcích a=range(1, 12) -- vytvoření a naplnění druhého pole o dvanácti prvcích b={"Leden", "Únor", "Březen", "Duben", "Květen", "Červen", "Červenec", "Srpen", "Září", "Říjen", "Listopad", "Prosinec"} -- vytištění prvního původního pole printSeparator() print("Original array #1") printArray(a) -- vytištění druhého původního pole printSeparator() print("Original array #2") printArray(b) printSeparator() print("Interleaved arrays") c = interleave(a, b) printArray(c)
Po spuštění tohoto příkladu se nejdříve obě vstupní tabulky vypíšou a následně se vypíše i tabulka vzniklá jejich spojením a proložením:
-------------------------------------------- Original array #1 1 2 3 4 5 6 7 8 9 10 11 12 -------------------------------------------- Original array #2 Leden Únor Březen Duben Květen Červen Červenec Srpen Září Říjen Listopad Prosinec -------------------------------------------- Interleaved arrays 1 Leden 2 Únor 3 Březen 4 Duben 5 Květen 6 Červen 7 Červenec 8 Srpen 9 Září 10 Říjen 11 Listopad 12 Prosinec
Druhý příklad ukazuje chování ve chvíli, kdy mají tabulky rozdílný počet prvků, konkrétně když je první tabulka delší než tabulka druhá:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArray(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do print(value) end print() end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění prvního pole o dvanácti prvcích a=range(1, 24) -- vytvoření a naplnění druhého pole o dvanácti prvcích b={"Leden", "Únor", "Březen", "Duben", "Květen", "Červen", "Červenec", "Srpen", "Září", "Říjen", "Listopad", "Prosinec"} -- vytištění prvního původního pole printSeparator() print("Original array #1") printArray(a) -- vytištění druhého původního pole printSeparator() print("Original array #2") printArray(b) printSeparator() print("Interleaved arrays") c = interleave(a, b) printArray(c)
Výsledky po spuštění tohoto příkladu:
-------------------------------------------- Original array #1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 -------------------------------------------- Original array #2 Leden Únor Březen Duben Květen Červen Červenec Srpen Září Říjen Listopad Prosinec -------------------------------------------- Interleaved arrays 1 Leden 2 Únor 3 Březen 4 Duben 5 Květen 6 Červen 7 Červenec 8 Srpen 9 Září 10 Říjen 11 Listopad 12 Prosinec 13 14 15 16 17 18 19 20 21 22 23 24
15. Operace permutation – výpočet všech permutací množiny představované prvky tabulky
Další operací, se kterou se v dnešním článku ve stručnosti seznámíme, je permutace prvků množiny. Tato operace je implementována ve funkci nazvané permutation. Pro pole s n prvky se vypočte celkem n! permutací (prvky ve výběru se tedy neopakují). V prvním příkladu je permutována množina se čtyřmi prvky (řetězci):
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArrayInLine(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do io.write(value) if i ~= #array then io.write(", ") end end print() end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění pole o čtyřech prvcích a={"Leden", "Únor", "Březen", "Duben"} -- vytištění původního pole printSeparator() print("Original array #1") printArrayInLine(a) -- vytištění permutací původního pole printSeparator() print("Permutations") for permutation in permutation(a) do printArrayInLine(permutation) end
Po spuštění tohoto příkladu se nejdříve vypíše obsah vstupního pole a následně jeho 24 permutací:
-------------------------------------------- Original array #1 Leden, Únor, Březen, Duben -------------------------------------------- Permutations Únor, Březen, Duben, Leden Březen, Únor, Duben, Leden Březen, Duben, Únor, Leden Duben, Březen, Únor, Leden Únor, Duben, Březen, Leden Duben, Únor, Březen, Leden Duben, Březen, Leden, Únor Březen, Duben, Leden, Únor Březen, Leden, Duben, Únor Leden, Březen, Duben, Únor Duben, Leden, Březen, Únor Leden, Duben, Březen, Únor Únor, Duben, Leden, Březen Duben, Únor, Leden, Březen Duben, Leden, Únor, Březen Leden, Duben, Únor, Březen Únor, Leden, Duben, Březen Leden, Únor, Duben, Březen Únor, Březen, Leden, Duben Březen, Únor, Leden, Duben Březen, Leden, Únor, Duben Leden, Březen, Únor, Duben Únor, Leden, Březen, Duben Leden, Únor, Březen, Duben
Ve druhém demonstračním příkladu se mj. přesvědčíme, že pro vstupní pole s n prvky bude vypočteno celkem n! permutací, kde vykřičník značí faktoriál. Počet permutací totiž uložíme do čítače cnt a postupně budeme zvětšovat počet prvků vstupního pole:
cnt = 0 for permutation in permutation(a) do printArrayInLine(permutation) cnt = cnt + 1 end print("Permutations: " .. cnt)
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArrayInLine(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do io.write(value) if i ~= #array then io.write(", ") end end print() end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytištění permutací původního pole o různé délce for length = 1, 5 do -- vytvoření a naplnění pole o n prvcích a=range(length) print("Original array") printArrayInLine(a) -- tisk všech možných perutací pole print("Permutation for array with length " .. length) cnt = 0 for permutation in permutation(a) do printArrayInLine(permutation) cnt = cnt + 1 end print("Permutations: " .. cnt) print() end
Ve výsledcích je patrné, že se skutečně pro pole o n prvcích vrátí n! možných permutací pole:
Original array 1 Permutation for array with length 1 1 Permutations: 1 Original array 1, 2 Permutation for array with length 2 2, 1 1, 2 Permutations: 2 Original array 1, 2, 3 Permutation for array with length 3 2, 3, 1 3, 2, 1 3, 1, 2 1, 3, 2 2, 1, 3 1, 2, 3 Permutations: 6 Original array 1, 2, 3, 4 Permutation for array with length 4 2, 3, 4, 1 3, 2, 4, 1 3, 4, 2, 1 4, 3, 2, 1 2, 4, 3, 1 4, 2, 3, 1 4, 3, 1, 2 3, 4, 1, 2 3, 1, 4, 2 1, 3, 4, 2 4, 1, 3, 2 1, 4, 3, 2 2, 4, 1, 3 4, 2, 1, 3 4, 1, 2, 3 1, 4, 2, 3 2, 1, 4, 3 1, 2, 4, 3 2, 3, 1, 4 3, 2, 1, 4 3, 1, 2, 4 1, 3, 2, 4 2, 1, 3, 4 1, 2, 3, 4 Permutations: 24 Original array 1, 2, 3, 4, 5 Permutation for array with length 5 2, 3, 4, 5, 1 3, 2, 4, 5, 1 3, 4, 2, 5, 1 4, 3, 2, 5, 1 2, 4, 3, 5, 1 4, 2, 3, 5, 1 4, 3, 5, 2, 1 3, 4, 5, 2, 1 3, 5, 4, 2, 1 5, 3, 4, 2, 1 4, 5, 3, 2, 1 5, 4, 3, 2, 1 2, 4, 5, 3, 1 4, 2, 5, 3, 1 4, 5, 2, 3, 1 5, 4, 2, 3, 1 2, 5, 4, 3, 1 5, 2, 4, 3, 1 2, 3, 5, 4, 1 3, 2, 5, 4, 1 3, 5, 2, 4, 1 5, 3, 2, 4, 1 2, 5, 3, 4, 1 5, 2, 3, 4, 1 5, 3, 4, 1, 2 3, 5, 4, 1, 2 3, 4, 5, 1, 2 4, 3, 5, 1, 2 5, 4, 3, 1, 2 4, 5, 3, 1, 2 4, 3, 1, 5, 2 3, 4, 1, 5, 2 3, 1, 4, 5, 2 1, 3, 4, 5, 2 4, 1, 3, 5, 2 1, 4, 3, 5, 2 5, 4, 1, 3, 2 4, 5, 1, 3, 2 4, 1, 5, 3, 2 1, 4, 5, 3, 2 5, 1, 4, 3, 2 1, 5, 4, 3, 2 5, 3, 1, 4, 2 3, 5, 1, 4, 2 3, 1, 5, 4, 2 1, 3, 5, 4, 2 5, 1, 3, 4, 2 1, 5, 3, 4, 2 2, 5, 4, 1, 3 5, 2, 4, 1, 3 5, 4, 2, 1, 3 4, 5, 2, 1, 3 2, 4, 5, 1, 3 4, 2, 5, 1, 3 4, 5, 1, 2, 3 5, 4, 1, 2, 3 5, 1, 4, 2, 3 1, 5, 4, 2, 3 4, 1, 5, 2, 3 1, 4, 5, 2, 3 2, 4, 1, 5, 3 4, 2, 1, 5, 3 4, 1, 2, 5, 3 1, 4, 2, 5, 3 2, 1, 4, 5, 3 1, 2, 4, 5, 3 2, 5, 1, 4, 3 5, 2, 1, 4, 3 5, 1, 2, 4, 3 1, 5, 2, 4, 3 2, 1, 5, 4, 3 1, 2, 5, 4, 3 2, 3, 5, 1, 4 3, 2, 5, 1, 4 3, 5, 2, 1, 4 5, 3, 2, 1, 4 2, 5, 3, 1, 4 5, 2, 3, 1, 4 5, 3, 1, 2, 4 3, 5, 1, 2, 4 3, 1, 5, 2, 4 1, 3, 5, 2, 4 5, 1, 3, 2, 4 1, 5, 3, 2, 4 2, 5, 1, 3, 4 5, 2, 1, 3, 4 5, 1, 2, 3, 4 1, 5, 2, 3, 4 2, 1, 5, 3, 4 1, 2, 5, 3, 4 2, 3, 1, 5, 4 3, 2, 1, 5, 4 3, 1, 2, 5, 4 1, 3, 2, 5, 4 2, 1, 3, 5, 4 1, 2, 3, 5, 4 2, 3, 4, 1, 5 3, 2, 4, 1, 5 3, 4, 2, 1, 5 4, 3, 2, 1, 5 2, 4, 3, 1, 5 4, 2, 3, 1, 5 4, 3, 1, 2, 5 3, 4, 1, 2, 5 3, 1, 4, 2, 5 1, 3, 4, 2, 5 4, 1, 3, 2, 5 1, 4, 3, 2, 5 2, 4, 1, 3, 5 4, 2, 1, 3, 5 4, 1, 2, 3, 5 1, 4, 2, 3, 5 2, 1, 4, 3, 5 1, 2, 4, 3, 5 2, 3, 1, 4, 5 3, 2, 1, 4, 5 3, 1, 2, 4, 5 1, 3, 2, 4, 5 2, 1, 3, 4, 5 1, 2, 3, 4, 5 Permutations: 120
16. Operace powerset – výpočet potenční množiny z množiny prvků
Zajímavá a v některých algoritmech i užitečná může být funkce nazvaná powerset. Tato funkce vypočte potenční množinu z prvků vstupní tabulky.
Tuto operaci si můžeme otestovat na poli obsahujícím čtyři prvky 1, 2, 3 a 4:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArrayInLine(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do io.write(value) if i ~= #array then io.write(", ") end end print() end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění pole o čtyřech prvcích a=range(4) -- vytištění původního pole printSeparator() print("Original array #1") printArrayInLine(a) -- vytištění potenční množiny původního pole printSeparator() print("Powerset") p = powerset(a) for _, p in ipairs(p) do printArrayInLine(p) end
Výsledek získaný po spuštění tohoto demonstračního příkladu ukazuje celou potenční množinu (včetně prázdné množiny na konci):
-------------------------------------------- Original array #1 1, 2, 3, 4 -------------------------------------------- Powerset 1 1, 2 2 1, 3 1, 2, 3 2, 3 3 1, 4 1, 2, 4 2, 4 1, 3, 4 1, 2, 3, 4 2, 3, 4 3, 4 4 *empty*
Ve druhém příkladu otestujeme, zda skutečně platí, že potenční množina množiny s n prvky bude obsahovat 2n prvků. n budeme postupně zvyšovat a dívat se na získané výsledky:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArrayInLine(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do io.write(value) if i ~= #array then io.write(", ") end end print() end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end printSeparator() -- vytištění potenční množiny původního pole o různé délce for length = 0, 4 do -- vytvoření a naplnění pole o n prvcích if length == 0 then a = {} else a=range(length) end print("Original array") printArrayInLine(a) print() -- tisk potenční množiny pole print("Powerset") p = powerset(a) for _, p in ipairs(p) do printArrayInLine(p) end print() print("# of items: " .. #p) printSeparator() end
Z výsledků je patrné, že podmínka popsaná na začátku kapitoly je skutečně platná:
-------------------------------------------- Original array *empty* Powerset *empty* # of items: 1 -------------------------------------------- Original array 1 Powerset 1 *empty* # of items: 2 -------------------------------------------- Original array 1, 2 Powerset 1 1, 2 2 *empty* # of items: 4 -------------------------------------------- Original array 1, 2, 3 Powerset 1 1, 2 2 1, 3 1, 2, 3 2, 3 3 *empty* # of items: 8 -------------------------------------------- Original array 1, 2, 3, 4 Powerset 1 1, 2 2 1, 3 1, 2, 3 2, 3 3 1, 4 1, 2, 4 2, 4 1, 3, 4 1, 2, 3, 4 2, 3, 4 3, 4 4 *empty* # of items: 16 --------------------------------------------
17. Operace shuffle – náhodné zamíchání prvků v poli
Poslední operací, kterou si dnes popíšeme, je operace určená pro náhodné zamíchání prvků v poli, přesněji pro změnu pořadí prvků. Tato operace se jmenuje shuffle, tedy stejně, jako podobně pracující operace na hudebních přehrávačích. Zamíchání prvků je náhodné, ovšem lze ho ovlivnit nepovinným parametrem, kterým se specifikuje „semínko“ (seed) generátoru pseudonáhodných čísel. Podívejme se na příklad, který promíchá prvky pole se jmény měsíců:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArray(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do print(value) end print() end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění pole o dvanácti prvcích a={"Leden", "Únor", "Březen", "Duben", "Květen", "Červen", "Červenec", "Srpen", "Září", "Říjen", "Listopad", "Prosinec"} -- vytištění prvního původního pole printSeparator() print("Original array") printArray(a) -- reorganizace prvků pole printSeparator() print("Shuffled array") printArray(shuffle(a))
Výsledek jasně ukazuje výsledek zamíchání:
-------------------------------------------- Original array Leden Únor Březen Duben Květen Červen Červenec Srpen Září Říjen Listopad Prosinec -------------------------------------------- Shuffled array Únor Červen Září Duben Květen Listopad Srpen Prosinec Červenec Leden Říjen Březen
V dnešním posledním demonstračním příkladu je zamíchání prováděno postupně, což by ale nemělo zvýšit „úroveň náhodnosti“ získanou už po prvním zamíchání:
-- načtení knihovny Moses a současně import symbolů do globálního jmenného prostoru M = require "moses" M.import() -- tisk obsahu pole function printArray(array) -- test na prázdné pole if #array == 0 then print("*empty*") return end for i, value in ipairs(array) do print(value) end print() end -- oddělení obsahu function printSeparator() print("--------------------------------------------") end -- vytvoření a naplnění pole o dvanácti prvcích a={"Leden", "Únor", "Březen", "Duben", "Květen", "Červen", "Červenec", "Srpen", "Září", "Říjen", "Listopad", "Prosinec"} -- vytištění prvního původního pole printSeparator() print("Original array") printArray(a) -- reorganizace prvků pole printSeparator() print("Shuffled array") for i = 1, 10 do b = shuffle(a) printArray(b) a = b end
Výsledky:
-------------------------------------------- Original array Leden Únor Březen Duben Květen Červen Červenec Srpen Září Říjen Listopad Prosinec -------------------------------------------- Shuffled array Únor Červen Září Duben Květen Listopad Srpen Prosinec Červenec Leden Říjen Březen Červenec Říjen Leden Květen Prosinec Duben Únor Listopad Srpen Březen Červen Září Květen Duben Březen Únor Prosinec Srpen Září Červen Červenec Říjen Leden Listopad Březen Duben Červenec Říjen Srpen Květen Prosinec Červen Leden Únor Září Listopad Listopad Červenec Červen Květen Říjen Září Prosinec Duben Srpen Leden Březen Únor Únor Říjen Prosinec Září Srpen Březen Leden Červen Červenec Duben Květen Listopad Únor Duben Červen Prosinec Květen Říjen Červenec Září Březen Srpen Listopad Leden Červen Květen Duben Prosinec Listopad Březen Červenec Říjen Srpen Únor Září Leden Červen Srpen Listopad Prosinec Duben Leden Červenec Září Únor Březen Říjen Květen Srpen Říjen Září Červen Březen Únor Leden Duben Prosinec Listopad Květen Červenec
18. Repositář s demonstračními příklady
Zdrojové kódy všech dnes použitých demonstračních příkladů byly uloženy do nového Git repositáře, který je dostupný na adrese https://github.com/tisnik/functional-lua. V případě, že nebudete chtít klonovat celý repositář (ten je ovšem – alespoň prozatím – velmi malý, dnes má přibližně několik jednotek kilobajtů), můžete namísto toho použít odkazy na jednotlivé demonstrační příklady a jejich části, které naleznete v následující tabulce:
# | Příklad | Stručný popis | Cesta |
---|---|---|---|
1 | 50_sortedk.lua | příklad použití funkce sortedk | https://github.com/tisnik/functional-lua/tree/master/moses/50_sortedk.lua |
2 | 51_sortedv.lua | příklad použití funkce sortedv | https://github.com/tisnik/functional-lua/tree/master/moses/51_sortedv.lua |
3 | 52_some.lua | zjištění, jestli tabulka obsahuje alespoň jeden prvek splňující zadanou podmínku | https://github.com/tisnik/functional-lua/tree/master/moses/52_some.lua |
4 | 53_all.lua | zjištění, jestli všechny prvky tabulky splňují zadanou podmínku | https://github.com/tisnik/functional-lua/tree/master/moses/53_all.lua |
5 | 54_count.lua | zjištění, kolik prvků tabulky má specifikovanou hodnotu | https://github.com/tisnik/functional-lua/tree/master/moses/54_count.lua |
6 | 55_count_large_array.lua | dtto, ovšem provedeno nad mnohem rozsáhlejší tabulkou | https://github.com/tisnik/functional-lua/tree/master/moses/55_count_large_array.lua |
7 | 56_countf.lua | zjištění, kolik prvků tabulky splňuje zadanou podmínku | https://github.com/tisnik/functional-lua/tree/master/moses/56_countf.lua |
8 | 57_countf_large_array.lua | shodný příklad, ovšem používající mnohem větší vstupní pole | https://github.com/tisnik/functional-lua/tree/master/moses/57_countf_large_array.lua |
9 | 58_same_keys.lua | test, jestli dvě tabulky obsahují prvky se shodnými klíči | https://github.com/tisnik/functional-lua/tree/master/moses/58_same_keys.lua |
10 | 59_contains_keys.lua | test, jestli prvky z jedné tabulky mají klíče shodné s prvky ze druhé tabulky | https://github.com/tisnik/functional-lua/tree/master/moses/59_contains_keys.lua |
11 | 60_same_values.lua | test, jestli dvě tabulky obsahují shodné hodnoty (i když uložené pod jinými klíči) | https://github.com/tisnik/functional-lua/tree/master/moses/60_same_values.lua |
12 | 61_interpose.lua | operace interpose nad polem obsahujícím numerická data | https://github.com/tisnik/functional-lua/tree/master/moses/61_interpose.lua |
13 | 62_interpose_string.lua | operace interpose nad polem obsahujícím řetězce | https://github.com/tisnik/functional-lua/tree/master/moses/62_interpose_string.lua |
14 | 63_interleave.lua | proložení dvou tabulek do tabulky jediné | https://github.com/tisnik/functional-lua/tree/master/moses/63_interleave.lua |
15 | 64_interleave_different_sizes.lua | proložení dvou tabulek do tabulky jediné, postupné zvětšování zdrojové tabulky | https://github.com/tisnik/functional-lua/tree/master/moses/64_interleave_different_sizes.lua |
16 | 65_permutation.lua | výpočet všech permutací množiny představované prvky tabulky | https://github.com/tisnik/functional-lua/tree/master/moses/65_permutation.lua |
17 | 66_permutation2.lua | výpočet všech permutací množiny představované prvky tabulky | https://github.com/tisnik/functional-lua/tree/master/moses/66_permutation2.lua |
18 | 67_powerset.lua | výpočet potenční množiny z množiny prvků | https://github.com/tisnik/functional-lua/tree/master/moses/67_powerset.lua |
19 | 68_powerset_different_sizes.lua | výpočet potenční množiny z množiny prvků, postupné zvětšování zdrojové tabulky | https://github.com/tisnik/functional-lua/tree/master/moses/68_powerset_different_sizes.lua |
20 | 69_shuffle.lua | náhodné zamíchání prvků v poli | https://github.com/tisnik/functional-lua/tree/master/moses/69_shuffle.lua |
21 | 70_shuffle.lua | náhodné zamíchání prvků v poli, postupné zvětšování „náhodnosti“ míchání | https://github.com/tisnik/functional-lua/tree/master/moses/70_shuffle.lua |
19. Články o programovacím jazyce Lua i o technologii LuaJITu
Předchozí dva články o funkcionálním stylu programování podporovaného knihovnou Lua Fun a úvodní dva články o knihovně Moses:
- Lua Fun: knihovna pro zpracování konečných i nekonečných sekvencí v jazyce Lua
https://www.root.cz/clanky/lua-fun-knihovna-pro-zpracovani-konecnych-i-nekonecnych-sekvenci-v-jazyce-lua/ - Lua Fun: knihovna pro zpracování konečných i nekonečných sekvencí v jazyce Lua (dokončení)
https://www.root.cz/clanky/lua-fun-knihovna-pro-zpracovani-konecnych-i-nekonecnych-sekvenci-v-jazyce-lua-dokonceni/ - Podpora funkcionálního programovaní v jazyku Lua s využitím knihovny Moses
https://www.root.cz/clanky/podpora-funkcionalniho-programovani-v-jazyku-lua-s-vyuzitim-knihovny-moses/ - Podpora funkcionálního programovaní v jazyku Lua s využitím knihovny Moses (pokračování)
https://www.root.cz/clanky/podpora-funkcionalniho-programovani-v-jazyku-lua-s-vyuzitim-knihovny-moses-pokracovani/
Programovacím jazykem Lua jsme se již na stránkách Rootu poměrně podrobně zabývali v samostatném seriálu. Jedná se o snadno naučitelný jazyk, který je ovšem (mj. i díky konceptu metatabulek) rozšiřitelný a poměrně tvárný. Viz též následující odkazy na již vydané články (včetně odkazu na e-book, jenž na základě těchto článků později vznikl):
- Programovací jazyk Lua
https://www.root.cz/clanky/programovaci-jazyk-lua/ - Základní konstrukce v programovacím jazyku Lua
https://www.root.cz/clanky/zakladni-konstrukce-v-programovacim-jazyku-lua/ - Operátory a asociativní pole v jazyku Lua
https://www.root.cz/clanky/operatory-a-asociativni-pole-v-jazyku-lua/ - Funkce v programovacím jazyku Lua
https://www.root.cz/clanky/funkce-v-programovacim-jazyku-lua/ - Funkce v programovacím jazyku Lua – uzávěry
https://www.root.cz/clanky/funkce-v-programovacim-jazyku-lua-uzavery/ - Programovací jazyk Lua vestavěný do aplikací
https://www.root.cz/clanky/programovaci-jazyk-lua-vestaveny-do-aplikaci/ - Programovací jazyk Lua v aplikacích II
https://www.root.cz/clanky/programovaci-jazyk-lua-v-aplikacich-ii/ - Objektově orientované programování v Lua
https://www.root.cz/clanky/objektove-orientovane-programovani-v-lua/ - Objektově orientované programování v Lua II
https://www.root.cz/clanky/objektove-orientovane-programovani-v-lua-ii/ - Programovací jazyk Lua a koprogramy
https://www.root.cz/clanky/programovaci-jazyk-lua-a-koprogramy/ - Knihovny a frameworky pro programovací jazyk Lua
https://www.root.cz/clanky/knihovny-a-frameworky-pro-programovaci-jazyk-lua/ - Lua + LÖVE: vytvořte si vlastní hru
https://www.root.cz/clanky/lua-love-vytvorte-si-vlastni-hru/ - Hrátky se systémem LÖVE
https://www.root.cz/clanky/hratky-se-systemem-love/ - Vytváříme hru v systému LÖVE
https://www.root.cz/clanky/vytvarime-hru-v-systemu-love/ - Hrátky se systémem LÖVE – částicové systémy
https://www.root.cz/clanky/hratky-se-systemem-love-casticove-systemy/ - Hrátky se systémem LÖVE – kolize a odrazy těles
https://www.root.cz/clanky/hratky-se-systemem-love-ndash-kolize-a-odrazy-teles/ - Hrátky se systémem LÖVE – kolize a odrazy těles II
https://www.root.cz/clanky/hratky-se-systemem-love-kolize-a-odrazy-teles-ii/ - Hrátky se systémem LÖVE – pružné vazby mezi tělesy
https://www.root.cz/clanky/hratky-se-systemem-love-pruzne-vazby-mezi-telesy/ - Hrátky se systémem LÖVE – dokončení
https://www.root.cz/clanky/hratky-se-systemem-love-dokonceni/ - LuaJ – implementace jazyka Lua v Javě
https://www.root.cz/clanky/luaj-ndash-implementace-jazyka-lua-v-jave/ - LuaJ a skriptování podle specifikace JSR-223
https://www.root.cz/clanky/luaj-a-skriptovani-podle-specifikace-jsr-223/ - Metalua: programovatelné rozšíření sémantiky jazyka Lua
https://www.root.cz/clanky/metalua-programovatelne-rozsireni-semantiky-jazyka-lua/ - Metalua: užitečná rozšíření jazyka Lua
https://www.root.cz/clanky/metalua-uzitecna-rozsireni-jazyka-lua/ - Programovací jazyk Lua v roli skriptovacího jazyka pro WWW stránky
https://www.root.cz/clanky/programovaci-jazyk-lua-v-roli-skriptovaciho-jazyka-pro-www-stranky/ - Interpretry, překladače, JIT překladače a transpřekladače programovacího jazyka Lua
https://www.root.cz/clanky/interpretry-prekladace-jit-prekladace-a-transprekladace-programovaciho-jazyka-lua/ - Kooperace mezi jazykem Lua a nativním (céčkovým) kódem
https://www.root.cz/clanky/kooperace-mezi-jazykem-lua-a-nativnim-ceckovym-kodem/ - Kooperace mezi jazykem Lua a nativním (céčkovým) kódem: knihovna FFI
https://www.root.cz/clanky/kooperace-mezi-jazykem-lua-a-nativnim-ceckovym-kodem-knihovna-ffi/ - Profilery pro programovací jazyk Lua
https://www.root.cz/clanky/profilery-pro-programovaci-jazyk-lua/ - Využití knihovny debug v programovacím jazyku Lua
https://www.root.cz/clanky/vyuziti-knihovny-debug-v-programovacim-jazyku-lua/ - Programovací jazyk Lua (e-book)
https://www.knihydobrovsky.cz/e-kniha/programovaci-jazyk-lua-240253190
Původně byla Lua realizována jako klasický interpret – prováděl se automatický a prakticky okamžitý překlad do bajtkódu, který byl následně interpretován. Později byl vytvořen i plnohodnotný (a nutno podotknout, že až neobvykle dobrý) just-in-time (JIT) překladač nazvaný LuaJIT. Touto zajímavou technologií jsme se zabývali v následující sérii článků (které jsou poněkud paradoxně součástí seriálu o programovacím jazyku Java a JVM):
- LuaJIT – Just in Time překladač pro programovací jazyk Lua
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (2)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-2/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (3)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-3/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (4)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-4/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (5 – tabulky a pole)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-5-tabulky-a-pole/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (6 – překlad programových smyček do mezijazyka LuaJITu)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-6-preklad-programovych-smycek-do-mezijazyka-luajitu/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (7 – dokončení popisu mezijazyka LuaJITu)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-7-dokonceni-popisu-mezijazyka-luajitu/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (8 – základní vlastnosti trasovacího JITu)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-8-zakladni-vlastnosti-trasovaciho-jitu/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (9 – další vlastnosti trasovacího JITu)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-9-dalsi-vlastnosti-trasovaciho-jitu/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (10 – JIT překlad do nativního kódu)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-10-jit-preklad-do-nativniho-kodu/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (11 – JIT překlad do nativního kódu procesorů s architekturami x86 a ARM)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-11-jit-preklad-do-nativniho-kodu-procesoru-s-architekturami-x86-a-arm/ - LuaJIT – Just in Time překladač pro programovací jazyk Lua (12 – překlad operací s reálnými čísly)
https://www.root.cz/clanky/luajit-just-in-time-prekladac-pro-programovaci-jazyk-lua-12-preklad-operaci-s-realnymi-cisly/
A konečně nesmíme zapomenout na to, že kromě původní implementace interpretru a LuaJITu existuje celá řada dalších implementací tohoto programovacího jazyka. Některé z těchto implementací byly zmíněny v následujících článcích:
- Skriptovací jazyk Lua v aplikacích naprogramovaných v Go
https://www.root.cz/clanky/skriptovaci-jazyk-lua-v-aplikacich-naprogramovanych-v-go/ - Programovací jazyk Lua v roli skriptovacího jazyka pro WWW stránky
https://www.root.cz/clanky/programovaci-jazyk-lua-v-roli-skriptovaciho-jazyka-pro-www-stranky/ - LuaJ – implementace jazyka Lua v Javě
https://www.root.cz/clanky/luaj-ndash-implementace-jazyka-lua-v-jave/ - Tvorba pluginů pro Vim s využitím programovacího jazyka Lua
https://www.root.cz/clanky/tvorba-pluginu-pro-vim-s-vyuzitim-programovaciho-jazyka-lua/
20. Odkazy na Internetu
- Potenční množina
https://cs.wikipedia.org/wiki/Poten%C4%8Dn%C3%AD_mno%C5%BEina - Permutace
https://cs.wikipedia.org/wiki/Permutace - Mohutnost
https://cs.wikipedia.org/wiki/Mohutnost - Repositář projektu Lua Fun
https://github.com/luafun/luafun - Lua Functional 0.1.3 documentation
https://luafun.github.io/reference.html - Getting Started
https://luafun.github.io/getting_started.html - Rockspec knihovny Fun
https://raw.githubusercontent.com/luafun/luafun/master/fun-scm-1.rockspec - Awesome Lua – A curated list of quality Lua packages and resources.
https://github.com/LewisJEllis/awesome-lua - Repositář projektu Moses
https://github.com/Yonaba/Moses/ - Lambda the Ultimate: Coroutines in Lua
http://lambda-the-ultimate.org/node/438 - Coroutines Tutorial
http://lua-users.org/wiki/CoroutinesTutorial - Lua Coroutines Versus Python Generators
http://lua-users.org/wiki/LuaCoroutinesVersusPythonGenerators - Programming in Lua 9.1 – Coroutine Basics
http://www.lua.org/pil/9.1.html - Wikipedia CZ: Koprogram
http://cs.wikipedia.org/wiki/Koprogram - Wikipedia EN: Coroutine
http://en.wikipedia.org/wiki/Coroutine - Repositář knihovny Moses
https://github.com/Yonaba/Moses/ - Návod k použití knihovny Moses
https://github.com/Yonaba/Moses/blob/master/doc/tutorial.md - How to understand clojure's lazy-seq
https://stackoverflow.com/questions/44095400/how-to-understand-clojures-lazy-seq - Lua Implementations
http://lua-users.org/wiki/LuaImplementations - Generator (computer programming)
https://en.wikipedia.org/wiki/Generator_(computer_programming) - Lambda the Ultimate: Coroutines in Lua,
http://lambda-the-ultimate.org/node/438 - Coroutines Tutorial,
http://lua-users.org/wiki/CoroutinesTutorial - Lua Coroutines Versus Python Generators,
http://lua-users.org/wiki/LuaCoroutinesVersusPythonGenerators - Category:Lua na Rosetta code
https://rosettacode.org/wiki/Category:Lua - Programming in Lua: 23 – The Debug Library
http://www.lua.org/pil/23.html - Programming in Lua: 23.1 – Introspective Facilities
http://www.lua.org/pil/23.1.html - Programming in Lua: 23.2 – Hooks
http://www.lua.org/pil/23.2.html - Lua 5.2 Reference Manual: 6.10 – The Debug Library
http://www.lua.org/manual/5.2/manual.html#6.10 - Turtles all the way down
https://en.wikipedia.org/wiki/Turtles_all_the_way_down - Issues k projektu LuaFun
https://github.com/luafun/luafun/issues - Archived | Embed Lua for scriptable apps
https://developer.ibm.com/tutorials/l-embed-lua/ - Embedding Lua
https://www.oreilly.com/library/view/lua-quick-start/9781789343229/3a6f3daf-f74c-4a25-a125–584da58568e4.xhtml