How to elegantly program FP with Groovy closures?

How to elegantly program FP with Groovy closures?

4. Closure

The popular interpretation of closure is that the internal state is isolated from the outside, and the high-order function that only interacts with the outside world through the parameter list and return value is used to protect the internal function from the outside influence. The concept is derived from Lambda expressions. For OOP languages such as Java, the concept of "closures" is replaced by "classes": the local variables of closures become "attributes", and internal functions become "methods". The result of the method often depends on the attribute, and the attribute is usually not open to the public (

private
).

Some basic concepts or terminology of FP, the author actually mainly cut in from the perspective of Scala. For details, see: In Scala: The Beginning of Functional Programming

4.1 Closures in Groovy

Groovy allows us to use closures in a functional style (at least it looks like that) and pass them around. In other words, Groovy also supports functional programming FP, and has all the features that FP should have. We have felt the simplicity of Lambda expressions in Java, but in Groovy, it has become commonplace. Suppose we want to customize a traversal operation on the array

foreach
Function, which operates on internal elements depends on the passed closure
action
:

nums = 1. .10 //This code does not declare any types at all, I seem to be writing javaScript....... void foreach(nums ,action){ for (i in nums){ //This incoming i is i-> print The i in "${i}". action(i) } } foreach(nums,{i -> print "${i} " }) copy the code

As mentioned in the previous article, if the last few parameters of the parameter list are closures, these closures can be selectively moved to the back of the function call. English teachers call this expression "post-attribute". Especially when the closure is longer, this way of expression is more elegant.

//Perform foreach operation on that array | How to operate foreach(nums) {i -> print "${i} " } foreach(nums) { i-> print i print "When the closure is very long, this way of writing seems more readable." print "This way of writing is very close to the for-each loop used in daily life. " print "This is the surprise brought by the post-closure. " } Copy code

It can even be a little more abstract,

nums
The array itself is also regarded as a
{()->nums}
The closure:

static foreach(nums,action){ //nums() means it is a supplier of ()->nums. def seq = nums() for (i in seq) {action(i)} } //{nums} is actually {->nums}, and the -> arrow can be omitted here. I- {} {the nums the foreach> Print ( "$ {I}" )} copy the code

In this example, we can vaguely feel how elegant and powerful the DSL created by Groovy will be. among them,

foreach
receive
action
Closures (also called functions), so
foreach
Also called a higher-order function . A more direct explanation of higher-order functions is: a receiving function, or a function that returns another function.

In Java, a Lambda expression is written like this:

(...) -> {...}
, Even without any parameters, it has to be written as
()->{...}
form. In Groovy, the parameters of the closure do not need to be enclosed in parentheses, and the form is similar
{p1,p2 ->...}
.

When this closure does not require any parameters, it is written like

{-> ...}
, Or omit the arrow symbol and write it directly
{...}
.

A small special case: if the closure only needs one parameter, we can use it internally

it
Call it, and then ignore the parameter names and small arrows. such as:

//{i -> print{"${i}"} =====> {print "${it}"} //foreach nums, print it. foreach {nums} {print( "${it} " )} Copy code

It should be noted that if the closure does not receive parameters, but it is written like

{...}
, Then Groovy will still implicitly assign a value to this closure
null
of
it
parameter. This will affect the dynamic judgment of the closure during the runtime of the program, see the dynamic closure below.

The parameters of the closure can declare strict types, such as:

{} {Integer the nums the foreach I -> Print "{I} $" } copy the code

4.2 Execute Around Method & AOP

In the JVM language, as long as we can mark unreachable objects as unreachable, they can be collected by the GC at an appropriate time. But in I/O intensive tasks, we hope that InputStream and OutputStream will be closed immediately after completing the task , otherwise the file handles they occupy will remain open until the GC actively reclaims them.

This is why Java (and other languages) I/O tools are designed

close()
or
destroy()
Such a method. However, occasionally we may focus too much on the functional business and forget to call these methods proactively...

This kind of trivial labor is better to be solved by the program. Assume that all resources that need to be actively closed are implemented

MustClosed()
interface:

interface MustClosed { def close() } Copy code

Then, define a higher-order function, which receives

MustClosed
Implementation class, and ensure that it is always called at the end
close()
The method closes the resource, regardless of whether an exception occurs during use. As for using this
MustClosed
The specific details of the resource, encapsulate it in another closure
action
among.

//r refers to Resource, which refers to I/O type resources that must be actively closed. def static safeUse(MustClosed r, action) { try { action(r) } catch (Exception e){ e.printStackTrace() } finally { r.close() print "${r.getClass().typeName} instance has been closed." } } Copy code

A simple test: customize one

MustClosed
Simple implementation, pass in
safeUse
Observe the printing order of the console in the function:

MustClosed resource = [ close: {println "doing close()..." } ] as MustClosed def action = {MustClosed r -> println "use resource r to do something..." } //demonstrates how to call a closure variable safeUse(re) {action(re)} /* It is equivalent to... where re and r actually refer to a reference. safeUse(re){ MustClosed r -> println "use resource r to do something..." } */ Copy code

A more realistic test: the Java provided

OutputStream
Regarded as a
MustClosed
Pass in the implementation class, and then feel it:

fos = new FileOutputStream( new File( "README.md" )) //depends on the type judgment Groovy dynamic safeUse (fos AS MustClosed) R & lt {- (> r.write "! Groovy" .bytes)} copy the code

Now, we no longer need to manually close various incoming I/O resources,

safeUse
Will help get everything done. The usage style of such closures is the Execute Around Method mode. If we diverge our thinking a little bit, assuming that we always have to do some repetitive processing before and after completing a series of businesses, we can use this model to design a template that only needs to replace the different businesses in the middle.

This approach is a bit familiar... Intuition is correct. Its design philosophy is no different from the aspect-oriented programming AOP in the Spring framework. Any language that supports FP can implement aspect-oriented programming through the surround execution mode.

4.3 Closures can be used to automatically clean up resources

Groovy gives a pretty decent implementation in view of these "pain points" of I/O resource tools: it has made some packaging on the basis of the original I/O tools, we can call it directly in the FileOutputStream/FileInputStream tools

withWriter
or
withReader
(Character operation),
withStream
(Byte operation) method, and directly inform FileOutputStream or FileInputStream as a Reader/Writer/Stream to process data in the form of a closure, and avoid a side effect brought by the original decorator pattern-constantly creating packaging objects. After execution, the I/O stream will close itself.

f = new File( "README.md" ) assert f.exists() fos = new FileOutputStream(f) String data = """{ status:200, msg: "ok" } """ //need no more fuxking close() and flush() fos.withWriter { //In fact, w -> w.write(data) can write all long strings at once. //This is mainly to demonstrate the nested call of closures. w -> data.eachLine { w.write( "${it}\n" ) } } Copy code

Especially when using a buffered output stream , we no longer have to worry about forgetting

close()
or
flush()
And cause the problem of content loss.

4.4 Closure Currying

Any language involving functional programming can be Curryed. Our purpose of currying a function (or closure) is twofold: either we want to memorize (cache) some parameters, or we want to postpone the execution of a certain closure. For example, the following is a plain expression:

Closure <Integer> expr = {x , y, z -> (x + y) * z} copy the code

Assuming that in actual operation, we found that the parameters

z
Compare
x
with
y
In terms of it, its value does not always seem to change:

//z does not always change expr( 2 , 3 , 3 ) expr( 1 , 6 , 3 ) expr( 1 , 5 , 3 ) expr ( . 5 , . 9 , . 3 ) copying the code

Therefore, we want the closure

expr
Remember for a while
z
The value of, in order to avoid boring repeated parameter transfer. then
expr
It was first rewritten like this:

Closure<Closure<Integer>> expr = { z -> //For this closure, z is a free variable. return {x, y -> (x + y) * z } } Copy code

right now,

expr
First ask for
z
, And then return another parameter is
x
with
y
According to the description, the assignment process is obviously divided into two steps. Simultaneously,
expr
Evolved into a higher-order function (high-order closure). If the evaluation process is compared to opening a box, then the value operation that originally only needed to open the box once becomes two.

Before//: expr (2,3,3) then//: DEF Result expr = ( . 3 ) ( 2 , . 3 ) copying the code

Has things gotten more troublesome? Not so. If we are the first to get

expr(3)
, You can get the saved
z
status. Therefore, in subsequent calls, we just pass in a different
x
with
y
That's it.

//(x + y) * 3 def memoried_z = expr 3 memoried_z( 2 , 3 ) //expr(2,3,3) memoried_z( 1 , 6 ) //expr(1,6,3) memoried_z( 1 , . 5 ) //expr (1,5,3) memoried_z ( . 5 , . 9 ) //expr (5,9,3) copying the code

For deeper curried functions, as the function parameters continue to be memorized, subsequent calls will become easier and fewer parameters required. The more complex the parameters passed, or the more items passed, the greater the advantage of function currying. Before all the parameters are obtained, the currying function always returns a closure instead of actual execution, so we also say that the currying function is called deferred.

4.4.1 Convenient currying conversion method

If the function of the function is more complicated, it may take a little time to refactor a currying implementation manually (more of a confusion of thoughts). Fortunately, Groovy provides a series of convenient methods to replace us to complete the currying conversion. For a function with n parameters, if you want to curry the first k parameters, you can call

curry()
Method to complete, where
0 <= k <= n
.

expr = (x, y, z -> (x + y) * z) //Return a new expression: (3 + 2) * z => 5z expr1 = expr.curry( 3 , 2 ) //10 println expr1( 2 ) //Returns a new expression: (. 1 + 2) *. 9. 3 = the println expr.curry ( . 1 , 2 , . 3 ) () Copy the code

If you want to start currying from back to front, you need to use

rcurry()
method:

expr = (x, y, z -> (x + y) * z) //expr = (x + 3) * 2 expr1 = expr.rcurry( 3 , 2 ) 12 is// the println exprl ( . 3 ) copying the code

If you want to start currying from the previous kth parameter, you need to use

ncurry()
Method, where
0 <= k <= n
, when
k = 0
When, refers to currying from the first parameter, which is equivalent to
curry()
method.

expr = {x,y,z -> (x + y) * z} //expr1 = (x + 3) * 2 expr1 = expr.ncurry( 1 , 3 , 2 ) 10// the println exprl ( 2 ) copying the code

4.5 Dynamic closure

Groovy can dynamically determine the length of the parameter list passed into the closure when the program is running, and even the parameter type. We can use this feature to give the program the ability to make dynamic decisions. For example: Suppose the company wants to calculate the tax amount based on the revenue. We want to pass the tax calculation method to a higher-order function in the form of a closure for calculation. However, this closure may not need to provide the tax rate (the user directly gives the calculation formula), or it may need (the user only provides the calculation method, at this time the higher-order function provides a default value):

def tax(Double amount,Closure computer){ switch (computer.maximumNumberOfParameters){ case 1 : return computer(amount) case 2 : return computer(amount, 15 ) default: throw new Exception( "need 1 or 2 args." ) } } //This closure passes in the tax rate calculation method and the tax rate, only 1 parameter println tax( 14000.0 ) { amount -> amount * 0.13 } //This closure does not actively pass in the tax rate rate, there are 2 parameters println tax( 14000.0 ) { amount,rage -> amount * (rage/100 ) } Copy code

If Groovy can determine that a parameter is a closure, you can access it

.maxinumNumberOfParameters
Attribute to determine the actual number of parameters when the closure is passed in. If the user does not provide a tax rate, the tax amount will be calculated directly according to the user's formula. Otherwise, a default tax rate is given by the higher-order function and calculated.

In addition to dynamically determining the number of parameters, you can also use

parameterTypes
Property to dynamically obtain the actual type of the parameter. such as:

def check(Closure cls){ int i = 1 for (args in cls.parameterTypes) {println "type[${i}] = ${args.typeName}" ;i++} //.. do nothing } //type[1] = java.lang.String check { String i -> //.. do nothing } //type[1] = java.lang,Integer check { Integer i -> //.. Still do nothing } //type[1] = java.lang.Integer //type[2] = java.lang.String check { Integer i, String s -> //.. still do nothing } Copy code

Note that as mentioned earlier, if the closure does not require any parameters, it can be written as

{...}
or
{-> ...}
, The difference between the two is: Groovy will still give an implicit parameter to the former
it
, But this value is
null
. But for the latter, Groovy considers this to be a strict no-parameter closure.

4.6 Closure execution context and closure delegation

Suppose this is a closure:

def closure = { func() } Copy code

Obviously, if there are no other clues, then it s hard to tell

func()
Where did the call come from. Putting this issue aside, we have more important concepts to mention.

Groovy defines three properties for each closure:

thisObject
,
owner
,
delegate
. All closures are bound to the instance of the class it is in, and will be compiled by Groovy into an instance of the inner class. For general closures,
this == owner == delegate
, Such as external
out
Closure.

class _Example_ { def out = { //This is a relatively internal closure. def inner = {} //------test of thisObject, owner, delegate----------// println out.thisObject.getClass().name //_Example_ println out.owner. getClass().name //_Example_ println out.delegate.getClass().name //_Example_ } } new _Example_().out() Copy code

But it is different for some special cases: the first case is the case of nested closures. For example

out
Defined inside the closure
inner
Closure. If visit the
inner
Closed
owner
, It will point to the outer closure
out
Instance.

class _Example_ { def out = { //This is a relatively internal closure. def inner = {} //------test of thisObject, owner, delegate----------// println out.thisObject.getClass().name //_Example_ println out.thisObject.hashCode() //== inner.thisObject.hashCode println out.owner.getClass().name //_Example_ println out.delegate.getClass().name //_Example_ println inner.thisObject.getClass().name //_Example_ println inner.thisObject.hashCode() //== out.thisObject.hashCode println inner.owner.getClass().name //_Example_$_closure1 (refers to external closure The compiled inner class) println inner.delegate.getClass().name //_Example_$_closure1 (refers to the inner class where the outer closure is compiled) } } new _Example_().out() Copy code

In the second special case,

delegate
Will no longer point to
owner
, And that is the case of performing closure delegation . To summarize it in simple words, some of the methods called inside the closure may come from an instance of another delegate class. The statement is as follows:

//"Proxy class" class _Proxy_ { } class _Example_ { def out = { def inner = {} inner.delegate = new _Proxy_() //thisObject, owner, delegate are different. println inner.thisObject.getClass().name println inner.owner.getClass().name println inner.delegate.getClass().name } } _ Example_// //_ Example _ $ _ closure1 //_ Proxy_ new new _example _ (). OUT () Copy the code

After understanding the basic properties of these three closures, it is much easier to explain the problem at the beginning of this section: If a method or variable used inside a closure is not in a local block, then Groovy will give priority to

thisObject
or
owner
Domain lookup; otherwise, try to search from
delegate
Find it there; otherwise, it will report an error and return. If you can find suitable content in the first two domains, then Groovy will never "disturb"
delegate
.

Observe the complete code below. due to

_Example_
Class defined
func1
,
out
The closure defines
func2
, So even
inner
The closure proxy is set, and Groovy does not perform routing.

class _Proxy_ { def func1 = {println "this [func1] is from the instance of Class: _Proxy_" } def func2 = {println "this [func2] is still from the instance of Class: _Proxy_" } } class _Example_ { def func1 = {println "this [func1] is from the instance of Class:_Example_." } def out = { def func2 = {println "this [func2] is from the instance of closure:out" } def inner = { func1() func2() } inner.delegate = new _Proxy_() inner() } } the this//[func1] The instance of Class IS from:. _Example_ //the this [func2] The instance of closure from IS: OUT new new . _example _ () OUT () to copy the code

Once commented out

_Example_
Internal
func1
or
func2
Closure, Groovy will start from
_Proxy_
Try to make up for the missing content there to give different results. such as:

class _Proxy_ { def func1 = {println "this [func1] is from the instance of Class: _Proxy_" } def func2 = {println "this [func2] is still from the instance of Class: _Proxy_" } } class _Example_ { def out = { def inner = { func1() func2() } inner.delegate = new _Proxy_() inner() } } the this//[func1] The instance of IS from Class: _Proxy_ //the this [func2] The instance of IS Still from Class: _Proxy_ new new . _example _ () OUT () to copy the code

Another way of declaring closure delegates will make Groovy invert the search order: that is, the preferred choice

delegate
Method, followed by
owner
or
thisObejct
. The specific method is to call an object
.with
Method "plugin" closure. As follows:

class _Proxy_ { def func1 = {println "this [func1] is from the instance of Class: _Proxy_" } def func2 = {println "this [func2] is still from the instance of Class: _Proxy_" } } class _Example_ { def func1 = {println "this [func1] is from the instance of Class: _Example_" } def func2 = {println "this [func2] is still from the instance of Class: _Example_" } def out = { def inner = { func1() func2() } new _Proxy_().with inner } } //this [func1] is from the instance of Class: _Proxy_ //this [func2] is still from the instance of Class: _Proxy_ new . _example _ () OUT () to copy the code

Note,

delegate
It becomes very useful when it comes to DSL.

4.7 Tail recursion

Recursive code is often regarded as a typical "tasteful but difficult to control". Compared with iteration, recursion may be more obscure in expression, so most programmers avoid it. One of the troubles often encountered is: when the level of recursion is too deep, the JVM will be unable to withstand it and throw a

StackOverFlowError
. We all know that each thread of the JVM uses a stack space to manage the functions it calls and allocates a stack frame for each function. If this stack has been in a state of "only in and not out", then the JVM is theoretically in danger of crashing.

The idea of solving stack overflow is very simple: as long as the stack maintains the "in-and-out" state. The specific method is to improve the general recursive function into tail recursion. Tail recursion means that when the next function is called, the current call directly passes the return value to it, and there is no subsequent calculation, the thread naturally thinks that there is no need to save the stack frame of the current call.

It may be more practical to illustrate with an example: the factorial of n.

/** * Why is this method not tail recursion? * If its return value is n * factorial(n-1), then this call needs to wait for the next call to factorial(n-1) to calculate the return value. * Therefore, assuming n == 3, the thread needs 3 layers of stack space to solve it. * Assuming that n takes a larger value, then the JVM will groan. * @param n * @return */ int factorial( int n){ return n <= 1 ? 1 :n * factorial(n -1 ) } import groovy.transform.TailRecursive /** * Why is this method tail recursive? * Regardless of the branch, the recursive function always returns a value or initiates a new call, and there are no subsequent operations to wait for the current call. * The intermediate results of the recursive process will be continuously loaded into the acc parameter and passed. * So, after the current call is over, it can safely "pass on the ancestry without worries". * Regardless of the value of n, this tail recursion always only occupies one layer of stack space. * The only inconvenient thing is that users need to actively pass an initial value for acc to call this function, and we generally rely on wrapper functions to solve this defect. * @param n * @return */ @TailRecursive int factorial_t( int n, int acc){ return n <= 1 ? Acc: factorial_t(n -1 ,acc * n) } //good println factorial_t( 10000 , 1 ) //bad, 99.99% error println factorial ( 10000 ) Copy the code

among them,

@TailRecursive
The annotation is responsible for checking the function, if it is not strictly tail-recursive, then an error will be reported during the compiler. The tail recursion of the closure version is different from the function version, and the tail recursion needs the help of
trampoline
(Meaning "spring bed") method to achieve.

//For recursive closures, we must first define a variable as its name before calling itself inside the closure. def f f = { i, BigInteger n -> i <= 1 ? n: f.trampoline(i- 1 , n * i) }.trampoline() F ( 1000 ) copying the code

In addition, considering the user experience, you may wish to add the closure

acc
The parameter is set to the default value of 1 (because it is the last parameter), so this parameter can be transparent to the user. It needs to be pointed out that with the same algorithm logic and input parameters, the execution speed of the function is much faster than the closure.

BigInteger factorial_func( int i, BigInteger n) { i <= 1 ? n: factorial_func(i- 1 , n * i) } factorial_closure = { i, BigInteger n = 1 -> i <= 1 ? n: factorial_closure.trampoline(i- 1 , n * i) }.trampoline() l1 = System.currentTimeMillis() println factorial_closure( 1000 ) //250 ~ 300 millis println System.currentTimeMillis()-l1 l1 = System.currentTimeMillis() println factorial_func( 1000 , 1 as BigInteger) //4 ~ 10 millis println System.currentTimeMillis()-l1 Copy code

4.8 Discuss recursive optimization from the problem of steel bar cutting

This question is referenced from: Dynamic Programming-Steel Rod Cutting Problem-RunningSnail- (cnblogs.com)

Assuming that we are a seller of steel rods (or steel bars), the price of steel rods of different lengths is different, and the length and price of steel rods are not linearly related (this means that the whole sale is not necessarily profitable) *. Now given a long steel rod, we hope to make some cuts on it to get the maximum profit. Length is

n
Steel rod, its price is recorded as
rodPrices[n]
:

Integer[] rodPrices = [0, 1, 3, 4, 5, 8, 9, 11, 12, 14, 15, 15, 16, 18, 19, 15, 20, 21, 22, 24, 25, 24, 26, 28, 29, 35, 37, 38, 39, 40] copy the code

For example, a steel rod with a length of 2 costs 3, while a steel rod with a length of 5 costs only 8 (the price/performance ratio seems to be "increased"). In addition, in order to eliminate the "dislocation" effect of the 0 subscript, let

rodPrices[0] == 0
. The first question: 1. find the maximum profit that a steel rod with a length of 27 can obtain.

The simplest idea is to list all the cutting schemes and choose the best ones. When it comes to exhaustion, we naturally think of iteration, or recursion, or both .

Thinking further, each time a long shot

l
Cutting will produce two short rods
s1
,
s2
. Let the length be
n
The maximum profit of the steel rod is
max(n)
, Then obviously we only ask for
max(s1)
with
max(s2)
, Then it can be calculated
max(l) = max(s1) + max(p2)
. that
max(s1)
How can I ask for it? It must be able to separate shorter shots
ss1
with
ss2
, We continue to ask
max(ss1)
with
max(ss2)
Enough......

From this description, we can extract four main points:

  1. The purpose of the big problem is to find the optimal solution.
  2. Big problems can be broken down into smaller problems.
  3. The optimal solution of the big problem depends on the optimal solution of the small problem.
  4. We are now continuously breaking down big problems into smaller ones "from top to bottom".

Therefore, the problem of steel rod (steel bar) cutting is essentially a dynamic programming problem. In the following description, we will "find the length as

length
The maximum profit of the steel rod" is encapsulated as a function
rodCut(length)
.

Let the incoming length be

length
Long rod, one of the two cut rods is
s1
, The length is recorded as
i
; And the other
s2
The length is
length-i
. We are in an iteration dynamically balance the length of the two bars , and within each iteration, keep
s1
The length of is unchanged, assuming that its current optimal solution is
max'(s1)
. On this premise
s2
Performed recursively cutting , that is, call
rodCut(s2)
.

We are sure

rodCut
Always return correctly
max(s2)
, So each iteration
max'(length) = max'(s1) + rodCut(s2)
. After the iteration is completed, you only need to take the actual maximum value from these result values as the current
rodCut(length)
The return value of the call is fine.

rodCut(length)=Max{maxi(s1)+rodCut(s2)   1 i length}length=s1+s2rodCut(length) = Max\{max_i(s1) + rodCut(s2)\space|\space1 i length\}/length = s1 + s2

There is another detail: if in a certain iteration

s1
length
i == length
, So obviously
s2 == 0
. At this time, it means wrong length
length
The rod for cutting, at this time
max(length) == rodPrices[length]
.

Based on the above ideas, we quickly gave the first version of the solution:

Integer rodCut(Integer[] rodPrices, length) { //Although length[0] is 0, we want the call to short-circuit and return instead of continuing. //This if cannot be omitted. if (length == 0 ) return 0 def max = -1 //The length of the "left stick" s1 is at least 1, otherwise it is meaningless. //When length = 1, length -1 = 0, the call will enter a critical condition. for (i in 1. .length) { def p = rodPrices[i] + rodCut(rodPrices, length-i) if (p> max) max = p } return max } Copy code

Now put forward a new requirement: not only ask for the maximum profit, but also give a detailed cutting plan. For example: the length is

27
The bar, its maximum profit is
43
, The cutting plan is:
[5,5,5,5,5,2]
, Each element in the array is the length of the short bar.

At this time, not only should we seek the optimal solution in the iterative process, but also record the length of the short rod each time the optimal solution is obtained. For this purpose, we designed the following data structure:

@Canonical final class Plan { Integer amount ArrayList splits } Copy code

Plan represents a cutting plan, such as

new Plan(amount: 4, splits:[1,2])
It means that there are two sub-rods of length 1 and 2 in this cutting plan, and the total income of this plan is 4.

splits
It is a linear meter, used to record the length of the short rod. It is foreseeable that the creation of the long plan is based on the short plan, and the new
splits
Always plan before
splits
Then insert a new element, and the linked list can calmly deal with the occasions of constantly adding elements, so
splits
Is set to the ArrayList class.

The second version of the solution is also released:

@Newify (Plan) def rodCut(rodPrices, length) { if (length == 0 ) return Plan( amount: 0 , splits: []) def max = Plan( amount: -1 , splits: []) //At least cut into (1, length-1), otherwise it is meaningless. //When length = 1, length-1 = 0, the boundary conditions must be considered. for (i in 1. .length) { //left: here is the meaning of "left". //Get the optimal Plan for "right rod" s2 def leftRod = rodCut(rodPrices, length-i) //Calculate the "optimal" in the current iteration Plan = "Left Rod" Plan + "Right Rod" Plan def try_ = Plan( amount: rodPrices[i] + leftRod.amount, splits: leftRod.splits + i) if (try_.amount> max.amount) max = try_ } //Return the optimal Plan corresponding to the actual length Length rod. return max } Copy code

Note that there is Groovy's syntactic sugar: that is

leftRod.split + i
. This is an operator overload, which can actually be understood as
leftRod.splits.add(i)
. The Groovy closure version of the algorithm is:

def rodCuts rodCut = { rod_prices, length -> if (length == 0 ) return new Plan( amount: 0 , splits: []) def max = new Plan( amount: -1 , splits: []) for (i in 1. .length) { def leftRod = rodCut (rodPrices, length-i) def try_ = new Plan( amount: rodPrices[i] + leftRod.amount, splits: leftRod.splits + i) if (try_.amount> max.amount) max = try_ } return max } Copy code

4.8.1 Improve performance with memoization

It is often said that premature optimization is the root of all evil. So the author deliberately avoided

rodCut
The operating efficiency of the function. To run the second version of the function/closure, the program needs to run for about 1 to 2 minutes to give the answer.

Why is this happening? In fact, we have overlooked the fifth point: that is, when decomposing big problems into small problems, we should avoid solving repetitive small problems. For example, the two cases of "dividing a rod length of 10 into two 5" and "dividing a rod length of 8 into 3 and 5" both involve "finding the optimal solution for a rod length of 5". Unfortunately, in the current recursive process,

rodCut
Function pair passed in
length
Almost all those who come are not rejected, but never review whether this calculation is necessary or not.

A simple but very effective way is to pass in a sufficiently long

cache
The array is used as a cache. among them,
cache[n]
Stored length as
n
The best solution for the bar, but at the very beginning, all positions are
null
. But every time
rodCut
Before returning the calculation result, it will be written to the corresponding location of the cache.

In subsequent recursive calls, the program first searches the corresponding location in the cache: if the location is

null
, It means that the current call can return the calculation result immediately instead of recalculating.

def rodCuts_cached rodCuts_cached = { Integer[] rod_prices, Integer length, Plan[] cache -> if (cache[length] != null ) return cache[length] if (length == 0 ) return new Plan( amount: 0 , splits: []) def max = new Plan( amount: 0 , splits: []) for (i in 1. .length) { def leftRod = rodCuts_cached(rod_prices, length-i, cache) def try_ = new Plan( amount: rod_prices[i] + leftRod.amount, splits: leftRod.splits + i) if ( try_.amount> max.amount) { max = try_ } } //Record the current optimal solution. //Note that the incoming cache is a reference, which means that any recursion can be aware of cache changes at any time. cache[length] = max return max } Copy code

In accordance with this idea, we re-given the third version of the code. Under the same operating conditions, its computing time is only equivalent to 1% of the second edition.

This routine is actually very similar to the previous optimization idea of n factorial, which is to find ways to save intermediate results to save the workload of subsequent recursion, whether it is to pass a calculation result by value or pass a cache by reference. If the name from a professional point of this routine, it is the memory of (Memoization).

4.8.2 The finishing touch memoize()

We have understood and experienced the performance leap brought by function memorization from examples, and considerate Groovy also understands us better. In other languages, we may write a piece of logic code (like the third edition code) in order to implement caching. But at least in Groovy, the actual workload is to add another one on top of the original closure

momonize()
Method call.

def rodCuts rodCut = { rod_prices, length -> if (length == 0 ) return new Plan( amount: 0 , splits: []) def max = new Plan( amount: -1 , splits: []) for (i in 1. .length) { def leftRod = rodCuts (rod_prices, length-i) def try_ = new Plan( amount: rodPrices[i] + leftRod.amount, splits: leftRod.splits + i) if (try_.amount> max.amount) max = try_ } return max }.memoize() Copy code

Groovy will create a closure with its own cache space for this purpose, and then just like what we did, the closure will preferentially read the result of the operation from the cache when recursing itself. In addition, Groovy also considers some threads Safe content. Because the mechanism is roughly the same, the operating efficiency of this version is almost the same as that of the third version, but the difference is that "we have less work to worry about."

According to the world there is no free lunch theorem, the price of gaining computing time will be the sacrifice of more or less space. If the scale of the problem becomes exaggerated, then the space occupation cannot be ignored (especially in this case, Plan is still a class that carries a linked list). Groovy gave us the right to choose, so

memonized()
Also derived
memonizeAtMost()
Methods and other variants. When the cache reaches a critical state, Groovy adopts the LRU (Least Last Used) strategy to replace the cached content.