(Filippo Scognamiglio) ( 20. září 2019)
Zkusme něco jiného! V tomto příspěvku budeme řešit slavný problém „nalití vody“ pomocí Kotlin dvakrát: procedurální a funkční.
Problém
Ve standardní skládačce„ nalití vody “dostanete brýle * n * s různými známými kapacitami a budete požádáni, abyste v jedné nebo více sklenicích našli seznam akcí, které vedou k požadovanému množství. Máte povoleno provádět pouze tři druhy akcí:
- Naplňte úplně sklenici
- Naprosto vyprázdněte sklenici
- Nalijte jednu sklenici do druhé, dokud první je prázdný nebo druhý plný
(Vím, co si myslíte … Nelze podvádět naplněním „půl“ sklenice … vidím vás).
Doména
Začněme charakterizováním domény. Budeme reprezentovat stav s následujícími datovými třídami:
data class Glass(val capacity: Int, val value: Int)
data class State(val glasses: List)
Dále definujeme tah pomocí abstraktní třídy metodou, která transformuje aktuální stav na upravená:
sealed class Move {
abstract fun update(state: State): State
}
Uzavřená třída bude mít tři možné implementace:
data class Fill(val index: Int): Move() {
override fun update(state: State): State =
State(state.glasses.mapAtIndex(index) {
it.copy(value = it.capacity)
})
}
data class Empty(val index: Int): Move() {
override fun update(state: State): State =
State(state.glasses.mapAtIndex(index) {
it.copy(value = 0)
})
}
data class Pour(val from: Int, val to: Int): Move() {
override fun update(state: State): State {
val fromGlass = state.glasses[from]
val toGlass = state.glasses[to] val maxFromQuantity = fromGlass.value
val maxToQuantity = toGlass.capacity - toGlass.value val quantity = min(maxFromQuantity, maxToQuantity)
return State(
state.glasses
.mapAtIndex(from) {
it.copy(value = it.value - quantity)
}
.mapAtIndex(to) {
it.copy(value = it.value + quantity)
}
)
}
}// Utility extension function
private fun List.mapAtIndex(index: Int, f: (T) -> T) =
this.mapIndexed { i, t -> if (i == index) f(t) else t }
Budeme také potřebovat datovou strukturu, která bude představovat seznam tahů, které se dostanou do konečného stavu:
data class Path(val finalState: State, val moves: List) {
fun extend(move: Move): Path {
val nextState = move.update(finalState)
val nextMoves = moves + move
return copy(finalState = nextState, moves = nextMoves)
}
}
Všechny tyto třídy jsou podle návrhu neměnné, a využijeme to v následujících implementacích.
Procedurální implementace
Tento problém lze reprezentovat jako graf, kde každý stav je uzel a každý pohyb je hrana spojující dva sousední státy. Chystáme se najít řešení prozkoumáním pomocí algoritmu Breath First Search.
Začněme generováním všech možných tahů; můžeme naplnit každou sklenici, vyprázdnit každou sklenici a nalít každou sklenici do jiné:
private fun generateMoves(): List{
val result = mutableListOf()
val indices = initialState.glasses.indices
for (i in indices) {
result.add(Move.Fill(i))
result.add(Move.Empty(i))
}
for (i in indices) {
for (j in indices) {
if (i != j)
result.add(Move.Pour(i, j))
}
}
return result
}
Nyní můžeme vytvořit metoda řešení , která vezme požadované množství a vrátí nejkratší seznam tahů, které definují řešení.
Shromažďujeme všechny neprozkoumané stavy do a MutableList , který na začátku obsahuje pouze počáteční stav.
Pak začneme iterovat , v každém kroku:
- Pop hlavu od hranice. Pokud je tento stav řešením, jsme hotovi. Pokud je stav již prozkoumán, přeskočíme ho.
- Přidejte tento stav do sady prozkoumaných (zabráníte tak jakémukoli cyklování).
- Vypočítat všechny možné sousední státy pomocí každý možný pohyb a přidáme je na konec hranice.
Dokončení je zaručeno, buď najdeme řešení, nebo prozkoumáme celý prostor hledání.
fun solve(amount: Int): Path? {
val explored = mutableSetOf()
val frontier = mutableListOf(Path(initialState, listOf()))
while (frontier.isNotEmpty()) {
val currentPath = frontier.removeAt(0)
if (isSolution(amount, currentPath.finalState)) {
return currentPath
}
if (explored.contains(currentPath.finalState)) {
continue
}
explored.add(currentPath.finalState)
for (move in moves) {
val nextPath = currentPath.extend(move)
frontier.add(nextPath)
}
}
return null
}
Funkční implementace
Přejdeme k implementaci funkce. Celková struktura bude podobná a začneme změnou metody generateMoves :
private fun generateMoves(): List{
val indices = initialState.glasses.indices
val fillMoves = indices.map { Move.Fill(it) }
val emptyMoves = indices.map { Move.Empty(it) }
val pourMoves = indices
.flatMap { i -> indices.map { j -> i to j } }
.filter { (i, j) -> i != j }
.map { (i, j) -> Move.Pour(i, j) }
return fillMoves + emptyMoves + pourMoves
}
Pro funkční řešení se budeme inspirovat Martin Odersky .
Definujeme rekurzivní funkci nextPaths který zadal seznam cest s délkou n vrací posloupnost seznamů obsahujících cesty délky n+1.
To se provádí volání metody extend na každé ze vstupních cest se všemi možnými pohyby (odfiltrování prozkoumaných stavů).
Tímto způsobem máme zaručeno, že budou nejprve zpracovány nejkratší cesty, což povede k další implementaci vyhledávání dechu první algoritmus.
Protože jsou Kotlinovy sekvence líně hodnoceny , víme, že delší cesty se počítají pouze v případě, že nejkratší cesty a Nejsme řešením problému.
fun solve(amount: Int): Path? {
val firstPath = Path(initialState, listOf()) return nextPaths(listOf(firstPath), setOf())
.flatten()
.filter { isSolution(amount, it.finalState) }
.firstOrNull()
}
fun nextPaths(paths: List, explored: Set): Sequence> {
return if (paths.isEmpty()) emptySequence()
else {
sequence {
val nextPaths = paths.flatMap {
extendWithMoves(it, explored)
}
val nextExplored = explored + paths.map {
it.finalState
}
yield(nextPaths)
yieldAll(nextPaths(nextPaths, nextExplored))
}
}
}
fun extendWithMoves(path: Path, explored: Set): List {
return moves
.map { path.extend(it) }
.filter { !explored.contains(it.finalState) }
}
Závěry
Pokusme se zdůraznit výhody tohoto krátkého příspěvku:
- Obě implementace fungovaly na daných testovacích případech
- Procedurální implementace byla 2–3krát rychlejší na stejném vstupu
- Funkční implementace byla stručnější a pravděpodobně čistší
- Funkční implementaci lze snadno optimalizovat, aby bylo možné využívat výhod více jader
Často není snadné zjistit, který je nejlepší přístup, a funkční programování není tím pravým bullet of coding.
Dobrou zprávou je, že nepotřebujete stříbrnou kulku (pokud nepotřebujete porazit starodávného tvora, který vypadá jako klaun): musíme použít luxus, abychom mohli použít programování s více paradigmy jazyk, takže si můžete snadno vybrat ten správný nástroj pro danou úlohu.