Conversation started Nov 28, 2019 at 14:51.
Nov 28, 2019 2:51 PM
OK, the problem I thought would be interesting for to day is counting words in a string.
Not much. Solved the game of life problem at the workshop at FunctionalConf and solved couple of project euler problems after that.
and did see that there were some talks on using APL with threads etc
There are many ways to do that, but I'll show you how an array oriented approach can give tremendous speed-ups.
But first we have to generate some test data. Since actual letters don't matter, we'll just have a text consisting of XY,
@Adám sure, I am installing dyalog APL on my new mac machine, and would try to get started with that
, will be our "space" because it is easier to see that way.
Now a PERL programmer would of course jump to regex.
Dyalog APL has a really powerful support for PCRE.
⍞←≢'[^,]+'⎕S 3⊢',YYY,,YYYYYY,,XXXXXX,YYYYYYXXYYY,YYYXXYYYXX,XX,XXYYYXXXX,YYY'
Nov 28, 2019 2:55 PM
@Adám 8
⎕S is an operator which takes the regex on its left and what to return for each match on its right. 3 is a special code meaning the pattern number, which is just 0 because we only have one regex.
Then we tally (count) that with and we're done.
@user654303 @AnandChitipothu Can you think of another approach to counting the words?
I guess it might be easier to solve it first without using regular expressions. just split on delimiter.
@AnandChitipothu Yes, very good. So perfect here.
If you give it a Boolean mask as left argument, it isolates runs corresponding to runs of 1s, discarding the elements corresponding to 0s.
⍞←','≠',YYY,,YYYYYY,,XXXXXX,YYYYYYXXYYY,YYYXXYYYXX,XX,XXYYYXXXX,YYY'
@Adám 0 1 1 1 0 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 1 1 1 0 1 1 1
This is our mask, indicating non-spaces.
⍞←','(≠⊆⊢)',YYY,,YYYYYY,,XXXXXX,YYYYYYXXYYY,YYYXXYYYXX,XX,XXYYYXXXX,YYY'
Nov 28, 2019 2:59 PM
@Adám  YYY  YYYYYY  XXXXXX  YYYYYYXXYYY  YYYXXYYYXX  XX  XXYYYXXXX  YYY
Read ≠⊆⊢ as "the difference partitions the right argument"
And then we can count the partitions:
⍞←','(≢≠⊆⊢)',YYY,,YYYYYY,,XXXXXX,YYYYYYXXYYY,YYYXXYYYXX,XX,XXYYYXXXX,YYY'
@Adám 8
Can you see what the issue with this would be?
Actually, before that, let's compare performance of the "pure" APL solution to the regex solution.
still trying to understand it
@AnandChitipothu Did you learn about trains (tacit APL programming) at all?
Nov 28, 2019 3:03 PM
I don't think so.
I don't think that was taught in the workshop
Ah, I see. I'll switch to explicit code then. Is this better?
⍞←','{≢(⍺≠⍵)⊆⍵}',YYY,,YYYYYY,,XXXXXX,YYYYYYXXYYY,YYYXXYYYXX,XX,XXYYYXXXX,YYY'
@Adám 8
I'm trying to understand ≢≠⊆⊢. That looks very elegant solution. Can you help us understand what is going on?
actually I have forgotten much of the things from the workshop, it's been busy 2 weeks
Nov 28, 2019 3:04 PM
Have a look at {≢(⍺≠⍵)⊆⍵}
would the Dyalog APL book be the best place to start to learn independenlty?
@user654303 you are not alone.
*independently
@user654303 That's one possibility. You can also look at past chat lessons.
Do you understand the {≢(⍺≠⍵)⊆⍵} code?
and are left and right arguments.
Nov 28, 2019 3:06 PM
the chat lessons look much more accessible, let me go through those.
yes remember the ⍺ and ⍵ now
@Adám how bad is an idea to do +/0 1⍷','≠',',str instead?
So if we think not in terms of the arguments, but in terms of the functions that are being applied to them, then we have applied between the arguments, and on the right we have just the right argument.
⍺≠⍵ gives 0s and 1s, partitions into words and counts them. Is my understanding correct?
@lelf I'll get to that, but it has sever performance problems too, due to not being optimised.
@AnandChitipothu Yes, 100%
The right argument can be seen as the right-identity function applied between the arguments: ⍺⊢⍵
Now APL allows the "even/odd" syntax of three functions f g h such that A(f g h)B (where A and B are arrays) means (A f B) g (A h B)
Therefore, (≠⊆⊢) is equivalent to {(⍺≠⍵)⊆(⍺⊢⍵)}
The system continues from the right, so p q f g h is (A p B) q (A f B) g (A h B)
And if there's an even number of functions, then the leftmost is simply applied monadically to the result of everything on its right. Hence ≢≠⊆⊢
we used because we need an odd number of functions. Is that correct? Is there any other way of doing that without using ?
Nov 28, 2019 3:13 PM
@AnandChitipothu Not easily.
Interesting.
It isn't really because we need an odd number of functions, but more because we want to address the right argument.
And the right argument in terms of function application between the arguments is exactly
I kind of understand it but I think it requires some time to get used to that way of thinking.
Nov 28, 2019 3:15 PM
Sure, I'll go back to the explicit code then.
⎕←cmpx '≢''[^,]+''⎕S 3⊢t' 's{≢(⍺≠⍵)⊆⍵}t' ⊣ s←',' ⊣ ⎕←≢t←',XY'[/⍨?1e6⍴3] ⊣ 'cmpx'⎕CY'dfns'
@Adám
1998931
VALUE ERROR
Not sure if it's right APL way, but ain't there a way to do split on the space or delimiter and then just take the len of the resulting array?
@user654303 That's what we're doing. But it is problematic that we split the array to count the pieces, as this has to make a new (pointer!) array.
⎕←cmpx '≢''[^,]+''⎕S 3⊢t' 's{≢(⍺≠⍵)⊆⍵}t' ⊣ s←',' ⊣ ⎕←≢t←',XY'[/⍨?1e6⍴3] ⊣ 'cmpx'⎕CY'dfns'
@Adám
2000034
VALUE ERROR
@user654303 there could be more than one space between two words and we need to count that as a single space.
Nov 28, 2019 3:18 PM
Hm, I don't know what the bot doesn't like that :-(
Ah ok, we don't want to create a copy to count the number of words
@AnandChitipothu But are handling that. However, we can't just count spaces.
Anyway, this is what the comparison looks like:
  ≢'[^,]+'⎕S 3⊢t → 1.1E¯1 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  s{≢(⍺≠⍵)⊆⍵}t   → 3.6E¯2 | -67% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
On about 2 million characters we're saving two thirds of the running time by using the split and count approach over regex.
@AnandChitipothu @user654303 Any other ideas on how we can approach this?
@Adám did you see if there is any performance difference between explicit function approach and ≢≠⊆⊢ ?
@AnandChitipothu In most cases there's very little difference, but tacit can sometimes be faster due to not creating a stack frame for itself.
So our problem is that we need to ignore multiple spaces.
We actually need to do edge detection.
I thought the function handled that for us.
Nov 28, 2019 3:27 PM
@AnandChitipothu Indeed, but we want to avoid actually splitting the text, rather we want to analyse it to count the words.
Think about it. If we have a text, say ,YYY,,YYYYYY,, we want to see whenever we go from a non-space to a space (or the opposite).
The only gotcha is at the end, if there are no trailing spaces, we will miss the last word.
how about shift by one and see if we get 01 pattern?
@AnandChitipothu Ah, very good.
So APL has the "find" function
⍞←'ss'⍷'mississippi'
@Adám 0 0 1 0 0 1 0 0 0 0 0
Nov 28, 2019 3:30 PM
It indicates the beginning of its left argument ("the top-left corner") in its right argument.
So now we can create an is-space mask, and look for 0 1.
⍞←','=',YYY,,YYYYYY,,'
@Adám 1 0 0 0 1 1 0 0 0 0 0 0 1 1
⍞←0 1⍷','=',YYY,,YYYYYY,,'
@Adám 0 0 0 1 0 0 0 0 0 0 0 1 0 0
⍞←+/0 1⍷','=',YYY,,YYYYYY,,'
@AnandChitipothu 2
Nov 28, 2019 3:32 PM
@AnandChitipothu Perfect.
However, it counts wrong here:
⍞←+/0 1⍷','=',YYY,,YYYYYY'
@Adám 1
So we need to append a space first.
⍞←','{+/0 1⍷⍺=⍵,⍺}',YYY,,YYYYYY'
@Adám 2
how do they stack up, speed-wise?
  ≢'[^,]+'⎕S 3⊢t  → 1.1E¯1 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  s{≢(⍺≠⍵)⊆⍵}t    → 4.1E¯2 | -64% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  s{+/0 1⍷⍺=⍵,⍺}t → 3.5E¯2 | -69% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
That's better.
However, we can do even better.
Nov 28, 2019 3:37 PM
How about 2</?
Don't worry.
@Bubbler Exactly.
So what Bubbler is suggesting is doing a pair-wise comparison.
Since we're looking for 0 1, we can just insert < between elements.
this seems to work with very simple case - 1+ +/' '⍷'quick brown fox jumps over a lazy dog' -> and what I am able to grasp at this point of time
gives 8
You should use backticks to avoid markdown messing up your code.
oh ok, 1+ +/' '⍷'quick brown fox jumps over a lazy dog'
@user654303 Yes, but it only works when there's exactly one space between words, and no leading or trailing spaces.
Also, you could use = instead of
So while you're clearly familiar with f/ for reduction, note that it can also be used with a left argument indicating the window size.
Nov 28, 2019 3:41 PM
yes, we'd have to somehow coalesce the in-between spaces, or use some formulation such as regex '[ ]*' in other languages
⍞←2+/3 1 4 1 5
@Adám 4 5 5 6
⍞←','{+/2</⍺=⍵,⍺}'YYY,YYYYY'
@AnandChitipothu 2
@Adám @Bubbler did it get it right?
Nov 28, 2019 3:42 PM
@AnandChitipothu If you put four spaces before ⎕ it will look nicer in chat.
@AnandChitipothu Yes. There's just one more thing we can do.
@Adám will take care of that from now on.
Notice the performance now:
  ≢'[^,]+'⎕S 3⊢t  → 7.1E¯2 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  s{≢(⍺≠⍵)⊆⍵}t    → 3.4E¯2 |  -53% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  s{+/0 1⍷⍺=⍵,⍺}t → 2.1E¯2 |  -71% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  s{+/2</⍺=⍵,⍺}t  → 6.3E¯4 | -100%
@user654303 we are using the < operator to handle the duplicate cases.
@AnandChitipothu < is a function in APL lingo, but yes.
⍞←','{⍺=⍵,⍺}'YYY,,,,YYYYY'
⍞←2</','{⍺=⍵,⍺}'YYY,,,,YYYYY'
Nov 28, 2019 3:44 PM
@AnandChitipothu LENGTH ERROR
@AnandChitipothu You can't do multiple statements like that. (for the bot)
⎕←','{⍺=⍵,⍺}'YYY,,,,YYYYY' ⋄ ⎕←2</','{⍺=⍵,⍺}'YYY,,,,YYYYY'
@Adám
0 0 0 1 1 1 1 0 0 0 0 0 1
0 0 1 0 0 0 0 0 0 0 0 1
The unbreakable diamond is the statement separator.
Nov 28, 2019 3:45 PM
what is {⍺=⍵,⍺} part doing?
@Adám thanks.
@user654303 I was trying to show how `2</` takes care of the duplicate spaces.
@user654303 Remember that APl functions have long right scope, so it is ⍺=(⍵,⍺) Concatenate to the right of then compare that to .
@user654303 it is added a training space (or comma) and comparing with space.
@AnandChitipothu You did. You reduced runs of 1s to single 1s.
Let's think a bit about what's happening here.
When we concatenate the space to the string, APL has to create a copy of the string with one additional byte at the end.
However, since that's a space, we know that the comparison will have a trailing 1.
⎕←cmpx 's{+/2</⍺=⍵,⍺}t' 's(+/2</⊣=⊢,⊣)t' ⊣ s←',' ⊣ ⎕←≢t←',XY'[(/⍨?1e6⍴3)] ⊣ 'cmpx'⎕CY'dfns'
Nov 28, 2019 3:48 PM
@lelf
1999960
VALUE ERROR
@lelf Yeah, I'm not sure why this fails,. Maybe the copying of cmpx goes awry. Try it online!
Remember that APL uses bit Booleans!
@Adám is there a way to avoid that copy?
This means that we'd only need to write one eighths as many bits if we defer the copying until we have a Boolean array.
@Adám I thought it's about 'abc'[/⍨1] (syntax error, is it a bug?) so I tried to add [(..)], that works for me on 17.0
@lelf Yes, it has been fixed in 17.1 which the bot (=TIO) runs.
Instead of doing {+/2</⍺=⍵,⍺} we can do {+/2</(⍺=⍵),1}
Here we use the original text directly (without modification) to derive our Boolean mask, and then we simply add a single trailing bit in-place, as there are no other references to our newly created mask array.
Here's how they stack up with the "find" method:
  s{+/0 1⍷⍺=⍵,⍺}t  → 2.1E¯2 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  s{+/2</⍺=⍵,⍺}t   → 4.2E¯4 |  -98% ⎕
  s{+/2</(⍺=⍵),1}t → 1.4E¯4 | -100%
But we can hardly distinguish them, so let's zoom in:
Nov 28, 2019 3:53 PM
what if out bitmask not empty bit. Will it make a new copy then?
  s{+/2</⍺=⍵,⍺}t   → 4.2E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  s{+/2</(⍺=⍵),1}t → 1.5E¯4 | -65% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
That's very significant!
Or we could flip the direction and do {+/2>/1,⍺=⍵}
@AnandChitipothu I'm not sure I follow. What if our bitmask [what's missing here?] not empty bit??
@Bubbler Yes, but can you spot what would make a difference in performance there?
  s{+/2>/1,⍺=⍵}t   → 2.0E¯4 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  s{+/2</(⍺=⍵),1}t → 1.5E¯4 | -28% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
sorry, what if out bitmask has not empty bit? If the number of characters is multiple of 8 then the bitmark will occupy all the bits in the bit mark and there won't be any free bits available to set it. Is my understanding correct?
Nov 28, 2019 3:56 PM
@AnandChitipothu If it has no empty bit? No 0 bit you mean?
@Bubbler The reason is that the concatenation of a single bit to the end of the big mask can happen in-place, as we simply extend the memory pocket by a bit (7 times out of 8 doesn't even need a pocket extension), but putting a bit at the front requires copying the entire mask.
is @Bubbler's version slower because it is prepending ,?
ah
Makes sense
@AnandChitipothu Ah, now I get it. Yes, correct, then we have to extend the memory pocket, but we reserve extra space for arrays to grow.
Hi Guys, i'd have to step out for dinner now, but i'd try to catchup on the chat later..and also experiment a bit on my own
@lelf Yes, since that forces a copy.
And that's it for today. Here's our final speed comparison of our initial and final solution:
  ≢'[^,]+'⎕S 3⊢t   → 7.3E¯2 |    0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
  s{+/2</(⍺=⍵),1}t → 1.9E¯4 | -100%
That's a 100% reduction in run time. Not bad, eh? :-D
Nov 28, 2019 3:59 PM
nice!
 
Conversation ended Nov 28, 2019 at 15:59.