Essays/Kadane Algorithm; J Tutorial
Kadane Algorithm as a J Tutorial
Introduction
Through the ArrayCast podcasts I became aware of this interesting algorithm. https://www.arraycast.com/episode-8-show-notes
The problem statement is relatively simple:
Given a list of numbers, find the largest sum produced by any of the possible contiguous subsequences
The test case:
Given: _2 1 _3 4 _1 2 1 _5 4
Find: the maximum partial sum
Answer: 6 (if your program works properly)
Conor Hoekstra a C++ developer and one of the hosts of ArrayCast. He had become interested in APL. On his twitter account he Tweeted about an elegant solution in APL (link available at the show notes link above). If it worked it was rather elegant, however, it turned out to be incorrect.
This is the combination that looked as though it would implement the Kadane algorithm:
myvec←¯2 1 ¯3 4 ¯1 2 1 ¯5 4
myvec
¯2 1 ¯3 4 ¯1 2 1 ¯5 4
⌈/(⊢⌈+)\ myvec
12
⍝ In APL the +\ operator performs a scan reduce
⍝ it produces prefixes of its arguments and automatically
⍝ does a + reduce on that prefix
⍝ ⍳5 will produce the vector 1 2 3 4 5
+\⍳5
1 3 6 10 15
⍝ By the answer alone you may come up with the false
⍝ impression that an accumulate function is occuring.
⍝ In the '+' case that would be 'current element' + 'previous sum' as
⍝ the vector is traversed.
⍝ In fact no such accumulate occurs for each answer it sums the partial vector so far
⍝ In J this same scan-reduce functionality is accomplished by '+/\'
The simple problem statement makes it a great example to use for a J tutorial. The rest of this essay is just that, a tutorial using simple easy to understand operators (called verbs in J) that morphed into an introduction of an advanced features of J known as "tacit" programming. Tacit programming is the combining of verbs (operators) together in various ways to form powerful programs. This is part of a more general concept of function combinators used in combinatory logic (see https://en.wikipedia.org/wiki/Combinatory_logic).
J Symbols Used/Needed
The following is the subset of J verbs and adverbs (built in functions ) used to program a solution to the maximum sum problem and the Kadane Algorithm. There are also symbols used as support operators. Some to investigate how combinations of operators behave. Others to select an intermediate solution to verify that the J code is processing the numbers correctly.
A brief description of each symbol and its web page from the J NuVoc (the J vocabulary webpage) are provided. NuVoc is not so new any more. It's probably one of the best language references for any programming language that I have seen. The main NuVoc page is here: https://code.jsoftware.com/wiki/NuVoc
A quick word about the J code provided: be sure to read the comments (lines with 'NB.' the comment delimiter in J). I use programming comments to explain "in-line" within the source code, rather than to come back out into wiki media text.
=: - assignment
https://code.jsoftware.com/wiki/Vocabulary/eqco
Just like any other programming language you can assign values to a variable. In J numbers in the form of a space separated list are the basis for the language. I tend to use list, array, and vector interchangably.
myvec =: _2 1 _3 4 _1 2 1 _5 4 myvec _2 1 _3 4 _1 2 1 _5 4
+ - plus/addition
https://code.jsoftware.com/wiki/Vocabulary/plus
NB. Monadic plus is the complex conjugate of a value. NB. For real numbers it just returns the number (there is no complex value involved) NB. I mention this because I mistakenly ended up apply NB. the monadic form of plus. In my case its due to NB. previous APL knowledge and forgetting that J is not NB. a direct rewrite of APL and some operators that look NB. the same operate differently. + 4.5 4.5 + 4.5j6 4.5j_6 NB. dydactic case it works the way you would expect 1 + 2 3 1 + 2 3 4 3 4 5 1 2 3 + 4 5 6 5 7 9 NB. addition works for scalar + vector NB. but vector + vector must have the same length and/or shape 1 2 + 3 4 5 |length error | 1 2 +3 4 5
The other base arithmetic operators have the expected dyadic usage. I won't introduce in a separate heading as they are used only as examples and are not used in the direct calculation of the Maximum sum problem.
NB. like other programming languages * and - are multiplication and subtraction respectively
5 - 2
3
5 * 2
10
NB. division uses the ascii percent sign ('%') as the major difference to most other languages
10 % 2
5
>. - ceiling/maximum
https://code.jsoftware.com/wiki/Vocabulary/gtdot
NB. Only the dyadic case is used for >. 3 >. 5 5 5 >. 3 5
# - tally/vector length
https://code.jsoftware.com/wiki/Vocabulary/number
NB. myvec has 9 elements defined myvec _2 1 _3 4 _1 2 1 _5 4 NB. # returns the length/count/'tally' of the number of elements # myvec 9
< - box/less than
https://code.jsoftware.com/wiki/Vocabulary/lt
<1 ┌─┐ │1│ └─┘ < 1 3 4 ┌─────┐ │1 3 4│ └─────┘ <'hello' ┌─────┐ │hello│ └─────┘
I am only using the monadic boxing functionality it also represents mathematical less than operator when used in its dyadic form
; - another box operator
https://code.jsoftware.com/wiki/Vocabulary/semi
'hello';1 3 4 ┌─────┬─────┐ │hello│1 3 4│ └─────┴─────┘ NB. monadic case it removes boxes 1;2;3 ┌─┬─┬─┐ │1│2│3│ └─┴─┴─┘ ;(1;2;3) 1 2 3 1 2 3; 1 2 3 4;5 4 3 2 1 ┌─────┬───────┬─────────┐ │1 2 3│1 2 3 4│5 4 3 2 1│ └─────┴───────┴─────────┘
Boxing allows you to concatenate different data types into a single array/vector. It also allows different length arrays to be collected into a single array. The latter is the functionality utilized in this investigation.
] - display right operator
https://code.jsoftware.com/wiki/Vocabulary/squarert
The right bracket is an operator that will return the value of its right operand. It may seem a like a silly operator to those familiar with other languages. But it plays an important role as a short hand for displaying results from an assignment and when we want to use complex combinations of operators and move the right hand operand into various portions of a sequence of operations. It is also helpful for finding out how adverbs act on a list of numbers. Below I show the simple usage of the operator (verb).
myvec _2 1 _3 4 _1 2 1 _5 4 ]myvec =: _2 1 _3 4 _1 2 1 _5 4 _2 1 _3 4 _1 2 1 _5 4 2 ] 4 4
[ - display left operator
https://code.jsoftware.com/wiki/Vocabulary/squarert
The same as the display right but operates on the left hand side value/operand.
1 [ 2 1
{ - select
https://code.jsoftware.com/wiki/Vocabulary/curlylf
J does not use brackets to select array/vector elements. Brackets to select elements of arrays do not fit the operator-operand or operand-operator-operand style of J. So instead of using brackets like other languages element selection has its own verb '{' the left brace.
0 { 2 4 6 8
2
1 { 2 4 6 8
4
2 { 2 4 6 8
6
3 { 2 4 6 8
8
/ - reduce adverb
https://code.jsoftware.com/wiki/Vocabulary/slash
The reduce adverb inserts the verb on the left of the '/'(slash) in between each of the elements and then evaluates. This is very handy way of summing all the elements of an array/vector using '+/'. It is a very powerful short hand and saves you from writing functions with loops to obtain simple functionality with verbs(operators) already defined in J.
1 + 2 + 3 + 4 + 5 15 +/ 1 2 3 4 5 NB. J actually inserts the operator then evaluates 15 NB. the above are effectively equivalent forms NB. it works with the maximum/ceiling operator as well 5 >. 6 >. 8 >. 2 >.3 8 >./ 5 6 8 2 3 8
\ - prefix adverb
https://code.jsoftware.com/wiki/Vocabulary/bslash
NB. prefix operator needs a verb to operate with NB. lets use the ] right display just to see how NB. it divies up the array argument ]\ 1 2 3 4 5 1 0 0 0 0 1 2 0 0 0 1 2 3 0 0 1 2 3 4 0 1 2 3 4 5 NB. it pads with 0s to make the output regular which NB. is why I usually use the box operator to give a NB. a more acurate accounting of the output <\ 1 2 3 4 5 ┌─┬───┬─────┬───────┬─────────┐ │1│1 2│1 2 3│1 2 3 4│1 2 3 4 5│ └─┴───┴─────┴───────┴─────────┘
This operator is the same symbol as the scan operator in APL and while the functionality is similar the J implementation only provides prefixes. It is up to the programmer to choose how to process those prefixes. In APL the operator combines prefixes with a reduce operation. More on this where I make my mistake with this operator.
\. - suffix adverb
https://code.jsoftware.com/wiki/Vocabulary/bslashdot
NB. the suffixes operator works similarly ]\. 1 2 3 4 5 1 2 3 4 5 2 3 4 5 0 3 4 5 0 0 4 5 0 0 0 5 0 0 0 0 <\. 1 2 3 4 5 ┌─────────┬───────┬─────┬───┬─┐ │1 2 3 4 5│2 3 4 5│3 4 5│4 5│5│ └─────────┴───────┴─────┴───┴─┘
? - roll operator
https://code.jsoftware.com/wiki/Vocabulary/query
?10 NB. returns a random number from the 10 number range 0 - 9 6 ?10 3 ?10 10 10 NB. works on arrays too 9 0 3
$ - shape operator
https://code.jsoftware.com/wiki/Vocabulary/dollar
NB. shape lets me create arrays from a single value 10$5 5 5 5 5 5 5 5 5 5 5 5$10 10 10 10 10 10
There is much more to this operator but this simple dyadic usage is all I need for creating a large test case to get runtime timings of the routines developed here.
each (&.>) - each conjunction
https://code.jsoftware.com/wiki/Vocabulary/ampdot
The 'each' conjunction is fairly self explanatory. It takes an operator and applies it to the elements of each boxed item. Most of the functionality has to do with the under conjunction '&.'. 'each' will unbox an item apply the operator on the left hand side and rebox the result. It will reform the result keeping the same number of boxes as were in the original right hand operand. An example reveals the functionality better than my explanation.
1 2 3; 1 2 3 4;5 4 3 2 1 ┌─────┬───────┬─────────┐ │1 2 3│1 2 3 4│5 4 3 2 1│ └─────┴───────┴─────────┘ +/ each 1 2 3; 1 2 3 4;5 4 3 2 1 ┌─┬──┬──┐ │6│10│15│ └─┴──┴──┘
& - bond conjunction
https://code.jsoftware.com/wiki/Vocabulary/ampm
This conjunction enables the 'bonding' of a constant or variable ('noun' in J parlance) to an operator
2&+ 1 2 3 3 4 5 myvec&+ 5 3 6 2 9 4 7 6 0 9 myvec+5 3 6 2 9 4 7 6 0 9
This will come in handy when creating other combinators such as the fork which is used to solve the maximum sum problem.
@ - atop conjunction
https://code.jsoftware.com/wiki/Vocabulary/at
This conjunction places one function 'atop' of another. It enforces the order in which the operators will process an argument. It will apply the right most operator to the operand first and then apply the left operator to the answer.
NB. to demonstrate '@' with a trivial example NB. demonstrate '@' with a trivial example 4 4$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 NB. to sum the columns just use '+/' the sum conjunction +/4 4$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 28 32 36 40 NB. to find the highest sum of the columns use NB. the maximum conjunction '>./' >./ +/4 4$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 40 NB. '@' (atop) is needed to tell J the specific order of NB. of applying these operators (>./)@(+/)4 4$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 40 NB. Here there is no difference really but if this NB. combination were to be saved in a variable to NB. provide easy reuse and give it a name '@' (atop) NB. becomes important maxcol =: >./ +/ maxcol 4 4$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 28 32 36 40 NB. J interprets this as a combinator called a hook NB. this will be left to the reader to research since NB. this feature is not used further. NB. to force J to turn off the hook interpretation NB. maxcol is defined as follows: maxcol =: (>./)@(+/) maxcol 4 4$1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 40 NB. atop has a certain enforcement in the order of NB. operations that is different than just stringing NB. operators together
J has many ways of combining operations to help simplify function definition. Therefore it also has ways such as '@' atop to allow the user to control how the operators are used in combination with the operands. This is both part of the elegance of J and a source of its complexity. This combinator functionality is introduced because it highlights how many different ways you can accomplish a simple task in J using a relatively small number of J operators while taking advantage of J's more complex features
fork combinator
https://code.jsoftware.com/wiki/Vocabulary/fork
The fork combinator allows the user to combine 3 operators in a certain way. There are 2 basic forms, a monadic and dyadic form:
NB. Monadic form of fork: NB. (f g h) myvec <==> (f myvec) g (g myvec) NB. NB. Dyadic form: NB. x (f g h) myvec <==> (x f myvec) g (x h myvec)
This may seem quite arbitrary but it turns out that it helps to concisely express certain simple functions. The most common example is an average function:
NB. example of dyadic fork (5 + 3) * (5 - 3) 16 5 (+ * -)3 16 NB. The most famous fork is for averaging numbers (+/ % #) it uses the monadic form of each verb NB. to create a monadic fork NB. In English pseudocode it does the following: (sum a list of numbers) and divide by (length of list of numbers) (+/ % #) 1 2 3 4 5 3 (+/ 1 2 3 4 5) % (# 1 2 3 4 5) 3
J function definition
https://code.jsoftware.com/wiki/Vocabulary/com https://code.jsoftware.com/wiki/Vocabulary/DirectDefinition J allows explicit definition of nouns, verbs and adverbs. Only monadic verb definition is used here. The typical ways to define a monadic verb (i.e. takes only a right hand side argument) are shown. J has a cryptic single line and multiline method: 3 : '<J statement here with a y argument>' or 3 : 0 <followed by multiline J statements> ). The right parenthesis ')' signifies the end of a multiline definition.
It is easier to show than to explain:
myfunc =: 3 : 0
NB. place J statements in here to define function
NB. the variable 'y' is the right hand argument to this
NB. function
)
myfunc
3 : 0
NB. place J statements in here to define function
NB. the variable 'y' is the right hand argument to this
NB. function
)
myfunc1 =: monad define
NB. variables defined to represent the 3 : 0 base definition
NB. for a monadic function
)
myfunc1 NB. end up with same type of definition
3 : 0
NB. variables defined to represent the 3 : 0 base definition
NB. for a monadic function
)
myOneLineFunc =: 3 : 'y'
myOneLineFunc
3 : (,'y')
myOneLineFunc 3
3
NB. the new dnfs way of function definition
myfunc2 =: {{y}}
myfunc2
3 : (,'y')
myfunc2 3
3
Naive brute force solution of the problem
Before addressing the Kadane algorithm specifically, the following is a brute force solution. This generates all the possible subsequences and sums them and then picks out the maximum sum.
NB. First I thought to box suffixes of myvec
myvec =: _2 1 _3 4 _1 2 1 _5 4
<\.myvec
┌─────────────────────┬──────────────────┬────────────────┬─────────────┬───────────┬────────┬──────┬────┬─┐
│_2 1 _3 4 _1 2 1 _5 4│1 _3 4 _1 2 1 _5 4│_3 4 _1 2 1 _5 4│4 _1 2 1 _5 4│_1 2 1 _5 4│2 1 _5 4│1 _5 4│_5 4│4│
└─────────────────────┴──────────────────┴────────────────┴─────────────┴───────────┴────────┴──────┴────┴─┘
NB. then run partial sums on each of the suffixes
+\ each <\.myvec
┌─────────────────────┬──────────────────┬────────────────┬─────────────┬───────────┬────────┬──────┬────┬─┐
│_2 0 0 0 0 0 0 0 0│1 0 0 0 0 0 0 0│_3 0 0 0 0 0 0│4 0 0 0 0 0│_1 0 0 0 0│2 0 0 0│1 0 0│_5 0│4│
│_2 1 0 0 0 0 0 0 0│1 _3 0 0 0 0 0 0│_3 4 0 0 0 0 0│4 _1 0 0 0 0│_1 2 0 0 0│2 1 0 0│1 _5 0│_5 4│ │
│_2 1 _3 0 0 0 0 0 0│1 _3 4 0 0 0 0 0│_3 4 _1 0 0 0 0│4 _1 2 0 0 0│_1 2 1 0 0│2 1 _5 0│1 _5 4│ │ │
│_2 1 _3 4 0 0 0 0 0│1 _3 4 _1 0 0 0 0│_3 4 _1 2 0 0 0│4 _1 2 1 0 0│_1 2 1 _5 0│2 1 _5 4│ │ │ │
│_2 1 _3 4 _1 0 0 0 0│1 _3 4 _1 2 0 0 0│_3 4 _1 2 1 0 0│4 _1 2 1 _5 0│_1 2 1 _5 4│ │ │ │ │
│_2 1 _3 4 _1 2 0 0 0│1 _3 4 _1 2 1 0 0│_3 4 _1 2 1 _5 0│4 _1 2 1 _5 4│ │ │ │ │ │
│_2 1 _3 4 _1 2 1 0 0│1 _3 4 _1 2 1 _5 0│_3 4 _1 2 1 _5 4│ │ │ │ │ │ │
│_2 1 _3 4 _1 2 1 _5 0│1 _3 4 _1 2 1 _5 4│ │ │ │ │ │ │ │
│_2 1 _3 4 _1 2 1 _5 4│ │ │ │ │ │ │ │ │
└─────────────────────┴──────────────────┴────────────────┴─────────────┴───────────┴────────┴──────┴────┴─┘
NB. This didn't work the way I expected
NB. +\ is not producing partial sums it appears to display just the subsequences
NB. this is because the monadic '+' is being applied which performs a complex conjugate
NB. that returns just the integer in question
NB. +/ (summation of a vector in J) is the operator that needs to be used
NB. this will sum prefixes of each of the suffixes generated
+/\each <\.myvec
┌──────────────────────┬─────────────────┬───────────────┬───────────┬───────────┬────────┬──────┬─────┬─┐
│_2 _1 _4 0 _1 1 2 _3 1│1 _2 2 1 3 4 _1 3│_3 1 0 2 3 _2 2│4 3 5 6 1 5│_1 1 2 _3 1│2 3 _2 2│1 _4 0│_5 _1│4│
└──────────────────────┴─────────────────┴───────────────┴───────────┴───────────┴────────┴──────┴─────┴─┘
NB. You can verify by hand that each of these is the partial sum for each
NB. subsequence I generated when I obtained the suffixes
NB. for example taking the 3rd suffix (indexed from 0 we select index 2)
2 { <\.myvec
┌────────────────┐
│_3 4 _1 2 1 _5 4│
└────────────────┘
NB. select out the 2 index from the partial sums
2 { +/\each <\.myvec
┌───────────────┐
│_3 1 0 2 3 _2 2│
└───────────────┘
NB. _3 is the first element of the partial sum
NB. 1 is the next (_3 + 4)
NB. 0 is next (_3 + 4 + 1)
NB. 2 (_3 + 4 + 1 + 2)
NB. 3 (_3 + 4 + 1 + 2 + 1)
NB. _2 (_3 + 4 + 1 + 2 + 1 + _5)
NB. finally 2 (_3 + 4 + 1 + 2 + 1 + _5 + 4)
NB. To get to a final answer I need to unbox this at some point
NB. so why not just unbox everything right away then I can
NB. find the Maximum of the combined sums and have my answer
NB. applying ; monadically removes the boxes and appends all the contents together
; +/\each <\.myvec
_2 _1 _4 0 _1 1 2 _3 1 1 _2 2 1 3 4 _1 3 _3 1 0 2 3 _2 2 4 3 5 6 1 5 _1 1 2 _3 1 2 3 _2 2 1 _4 0 _5 _1 4
NB. applying the >./ verb/adverb combination finds the greatest sum calculated
>./ ; +/\each <\.myvec
6
Refactoring
I tend to use boxing to help step through a problem especially with operators that I know will return different length answers. The boxing preserves the individual lengths as J will 'pad' answers to form them into a single matrix format.
When programming in J in this fashion (over boxed elements) one of the "smell" tests that the code can be condensed is when there are serial each statements applying one operator at a time. Intuitively why would J go through all the trouble to provide these operators if boxing has to be done on simple array/lists? The answer is it wouldn't. The boxing is now getting in the way of more basic J array processing. The next step is to remove boxing from this J code.
NB. the other way I thought of doing this was as follows: >./ each +/\each <\.myvec ┌─┬─┬─┬─┬─┬─┬─┬──┬─┐ │2│4│3│6│2│3│1│_1│4│ └─┴─┴─┴─┴─┴─┴─┴──┴─┘ NB. apply max on each of the boxed answers and then unbox and perform the NB. final maximum. >./ ; >./ each +/\each <\.myvec 6 NB. once I see 2 'each's applied serially I know I should be able to start NB. combining operations: (>./@(+/\)) each <\.myvec ┌─┬─┬─┬─┬─┬─┬─┬──┬─┐ │2│4│3│6│2│3│1│_1│4│ └─┴─┴─┴─┴─┴─┴─┴──┴─┘ NB. In hind sight it would seem obvious that you can just remove the boxing NB. since the intermediate answers are all the same size. However for some reason NB. it took me quite a while to realize this. Rather than bore you with my NB. feeble attempts. Just delete the each and the box operator and let the NB. combined operations work directly on the suffixes (>./@(+/\))\.myvec 2 4 3 6 2 3 1 _1 4 NB. Now apply the >./ (maximum reduction) >./(>./@(+/\))\.myvec 6 NB. as I was editing this write up I realized there is a fork implementation NB. of the above J code >./([: >./ (+/\))\.myvec 6 NB. I was using the atop '@' to force the order of the applied operators NB. in a monadic fashion. NB. It hit me this is just a fork with a cap '[:' to make sure the NB. right hand argument is not fed in as a dydactic operand NB. I believe they went over all this in an Array Cast episode but I NB. had to code it before it all came together in my head
The Kadane Algorithm
The Kadane Algorithm calculates local maximums (for lack of a better term). As the array is traversed either the number or the currently running sum will be the new maximum. If the actual element is the greater than the newly calculated local maximum (current element + previous calculated local maximum), then the current element is chosen. This resets the running sum to start from this latest element. In essence the algorithm has located a start of a new subsequence that could potentially be the maximum sum subsequence.
For example, in a sequence of all negative numbers except 1 number that is positive. That single positive number will be the highest sum of any of the subsequences calculated from 2 or more values. None of the numbers around that number are going to improve the sum to make it greater than the single element.
The Kadane algorithm is able to pin point the subsequence of interest without generating a complete enumeration of all the contiguous subsequences.
The kadane algorithm is able to find this maximum sum with 1 pass on the array (O(n) in big O notation). My brute force implementation generating the subsequences and summing them is on the order of O(n^2) maybe a little less.
Kadane in J
The previous local maximums need to be saved then at each element a decision can be made to continue summing or to start a new possible sum with the current element. Henry Rich's J for C programmers is a store house of J programming idioms. It is available online here: https://www.jsoftware.com/help/jforc/contents.htm
or in print form here: https://www.lulu.com/shop/henry-rich/j-for-c-programmers/paperback/product-4669553.html?page=1&pageSize=4
Henry Rich's Chapter 25. Loopless Code VI (https://www.jsoftware.com/help/jforc/loopless_code_vi_temporary_v.htm#_Toc191734469) shows how to use a global variable for these purposes. In J this variable can be set to minus infinity and will be lower than any element that would begin the array. Therefore it will be replaced on the first step of the algorithm. The test case is small it was easy to step through the process by hand as shown below:
NB. call the global 'locmax' for local maximum.
locmax =: __
myvec
_2 1 _3 4 _1 2 1 _5 4
NB. add the current element to locmax (this is the current candidate partial sum)
NB. pick the higher of the sum or the current element to be the next locmax.
]locmax =: _2 >. _2 + locmax NB. processing first element
_2
]locmax =: 1 >. 1 + locmax NB. processing second element, sum rest to element since it is higher than sum
1
]locmax =: _3 >. _3 + locmax NB. processing third element
_2
]locmax =: 4 >. 4 + locmax NB. processing fourth element
4
]locmax =: _1 >. _1 + locmax NB. processing fifth element
3
]locmax =: 2 >. 2 + locmax NB. processing sixth element
5
]locmax =: 1 >. 1 + locmax NB. processing seventh element
6
]locmax =: _5 >. _5 + locmax NB. processing eighth element
1
]locmax =: 4 >. 4 + locmax NB. processing ninth element
5
NB. scanning the answers 6 is the largest sum of a subsequence
NB. the same answer as our naive brute force approach.
NB. if I define a Kadane function
kadane =: 3 : 'locmax =: y >. locmax + y'
NB. Use the prefix operator \ to step that function through each element
NB. the 1 is part of the prefix operator telling it to go one element at a time
locmax =: __
1 kadane\myvec
_2
1
_2
4
3
5
6
1
5
NB. the '\' just automates what I peformed manually above
NB. the only thing left is to pick out the maximum from this answer
locmax =: __
>./ 1 kadane\myvec
6
NB. if you look at the code for 'kadane' a fork becomes apparent
kadane1 =: 3 : 'locmax =: (] >. locmax&+) y'
NB. it indeed works the same way as the first kadane
locmax =: __
>./ 1 kadane1\myvec
6
NB. We can use the new function definition in J to use an anonymous function
NB. for this
locmax =: __
>./ 1 {{locmax =: (] >. locmax&+) y}}\myvec
6
NB. This now has the similar structure to Conor's attempt in APL.
NB. But wait there's more
NB. Henry's book was written before 'Fold' was added to J
NB. I forget at times that Fold is in the language. As I
NB. was editing this document it dawned on me Henry Rich's idiom is a Fold.
NB. Fold will traverse the Array applying the previous calculated value
NB. into the next calculation in the chain
__ ] F:. ([ >. +) myvec
_2 1 _2 4 3 5 6 1 5 NB. this is the intermediate answer to Kadane
NB. now just apply the maximum reduce '>./' to the list
>./ __ ] F:. ([ >. +) myvec
6
Further Discussion
An interesting side note. The fork used in the fold is essentially Conor Hoekstra's fork in APL with a slight difference. The Fold implementation in J takes the y argument (which is the right argument of the dyadic Fold) and uses it as the left argument internally to the fold implementation.
In Conor's APL he uses the '⊢' operator (same/right operator) which has the J equivalent ']'. This is taking the current right hand element and using it as an operand into the maximum operator.
The Fold in J will set up the fork as
(myvec [ __) >. (myvec + __) NB. pseudo code of the first Fold step
Hence the use of the same/left operator '[' in the final J implementation
programming@jsoftware.com - J programming mailing list
I had some questions about the memory usage of some of the methods for the maximal sum of the subsequences (brute force and kadane).
I posted to the jsoftware programming mailing list.
Elijah Stone
Elijah gave me a simple change to the use of 'kadane'. It turns out that by using the J advanced feature of verb rank, we can direct the 'kadane' verb to work over individual elements without the use of the '\' scan adverb. Verbs can be directed to work over the different ranks of a noun: for example individual cells or applied to individual rows in a table. I won't go into an in-depth treatment of rank here. the double quote '"' is the operator that gets tacked on to the verb name and specifies the rank the verb should use. Elijah also used the display left operator/verb to turn this into a 1 liner. Remember J interprets from right to left, so below locmax will get initialized first and '[' will display the result from the left hand portion.
]myvec =: _2 1 _3 4 _1 2 1 _5 4 _2 1 _3 4 _1 2 1 _5 4 >./ kadane"0 myvec [ locmax=: __ 6
This is pretty good improvement. We drop one operator for another and save some memory space.
Jose Mario Quintana
The memory usage became secondary when Jose Mario Quintana posted the following pearl:
kad=. >./@:(([ >. +)/\.) kad myvec 6
Raul Miller, Henry Rich and Jose Mario Quintana
The rest of the thread on the mailing list were these 3 trying to get it through my thick skull that this
indeed was a full Kadane Algorithm that operates on each value in the array only once. Producing a linear time algorithm. The best part of J and the most frustrating, is that you dance around an elegant form of an algorithm (such as 'kad'). Yet, it's elusive, then someone points it out and you think of course! Like the arrow in the FedEx logo you can't unsee it. Half the fun of programming in J are these enlightening moments where you understand an elegant piece of code.
I won't go in depth on how the 'kad' algorithm works, other than to say does it indeed accomplish this in linear time. When the reduce operator '/' is used in conjunction with the suffix operator '\.' the J interpreter recognizes this as a special case. Raul Miller pointed out you need to know where to look in the documentation:
https://wiki.jsoftware.com/wiki/Vocabulary/SpecialCombinations#Virtual_Nouns
This lists the J idioms that take advantage of specialized processing through the use of "virtual nouns". The take away being (as complex as virtual nouns sound) it speeds up processing in a number of J related situations.
Timings
The following are time and space calculations for the various versions of this problem. Timings were accomplished on 2019 era MacBook Pro with 2.3 GHz Intel I9 8-core processor. The version of J is the latest 9.4 release for MacOs.
The routines have been reproduced here so this is self contained and you won't have to refer back to the text of this essay to understand what is being tested.
timespacex
6!:2 , 7!:2@]
ranvec =: _5 + ?10000$10
kadane =: 3 : 'locmax =: y >. locmax + y'
kadane1 =: 3 : 'locmax =: (] >. locmax&+) y'
kad=. >./@:(([ >. +)/\.)
timespacex '>./(>./@(+/\))\.ranvec' NB. first brute force implementation
0.032948 396448
timespacex '>./([: >./ (+/\))\. ranvec' NB. fork version brute force
0.034208 396448
locmax =: __
timespacex '>./ 1 kadane\ranvec' NB. first kadane implementation
0.004034 1.41251e6
locmax =: __
timespacex '>./ 1 kadane1\ranvec' NB. fork kadane version
0.005267 1.41277e6
locmax =: __
timespacex '>./ 1 {{locmax =: y >. locmax + y}}\ranvec' NB. new dnfs anonymous kadane function
0.003625 1.41347e6
locmax =: __
timespacex '>./ 1 {{locmax =: (] >. locmax&+) y}}\ranvec' NB. fork dnfs anonymous kadane function
0.004776 1.41386e6
timespacex '>./ __ ] F:. ([ >. +) ranvec' NB. Fold kadane implementation
0.017393 905792
timespacex '<./ kadane"0 ranvec' [ locmax=:__ NB. kadane with rank 0 processing
0.003909 772960
timespacex 'kad ranvec' NB. Best of Breed about 5 times faster
0.000802 132256
The brute force implementations are slower as expected, but they are quick enough that you may not have ever needed to go any farther to obtain the correct answer. The 'kad' algorithm is best by far (almost 5 times as fast). Many times in J the most elegant way of performing a task turns out to be the fastest way.
Contributed by Tom McGuire.