SF Scala: How to survive algorithms in Scala

SF Scala: How to survive algorithms in Scala

Recording: SF Scala: How to survive algorithms in Scala

[Music] let me introduce you to william normantas uh talk on how to survive algorithms in smaller over to you believe perfect thank you so much uh you've organized so many amazing events and i'm glad to be one of in one of these uh so yeah i'm just gonna share my screen and start the slides so sharing my screen i don't know how much delay there is between twitch and okay i see it that's perfect uh so yeah hi um i'm william uh i've been programming with scala for over seven years now and more recently i got into algorithms in scala and came up with something called scala algorithms but i'll go uh go in a bit more on my uh background background on algorithms and and share some more about uh how to do this in scholar so this talk is for anybody in programming you don't have to be a scholar person but or you could be an algo is like completely i think it's completely accessible too to everybody i'm going to talk about some progressive motivations uh behind algorithms and scala and algorithms in general uh and then challenges with algorithms in scala because there are some uh also i'm going to talk about how to survive algorithms in scala in particular how scala helped do algorithms in some cases because it has some advantages that other programming languages don't have and and finally a short introduction to scala algorithms so one of the things that's really kind of pushed me towards uh learning algorithms more depth was bartosz milevski's talk at uh haskell confit replacing functions with data and this this you know this has been i think coming up quite a lot i found when you have recursive functions that you're dealing with and then the the you know get a stack overflow exception like what do you do like you reach a certain amount you know you reach 100 items 100 levels of recursion and then you get this you know really a frustrating stack overflow error which inspired the creation of stackoverflow.com so um yeah there is a way to do it and it is uh it is quite a quite an involved thing and it does connect to how compilers are done and it does it does have uh even day-to-day applications um and uh implications on how how to think about algorithms so that that was one of the things that uh you know really pushed me uh towards it but also i think i really wanted to build up my arsenal of different skills uh when dealing with scala i found there were times that uh you know i would think oh you know binary tree is so easy to do and then i'm like stuck on a question for hours uh so i thought you know that's you know let's tackle the bull head on so to speak so i'm going to go to the next slide also what was interesting was i couldn't really find a concrete explanation of what algorithms are uh so a lot of the time it's said that an algorithm is a set of instructions but that's not quite the case you can have any recipe a recipe a recipe is a set of instructions so what makes an algorithm distinct from a recipe and it's really about dealing with efficiency under constraints so one of the primary constraints is dealing with a lot of data under limited time so that includes cpu time and limited ram so in particular uh it becomes very important to uh to use high performance algorithms um when you have you know you have those limited resources you could have an algorithm running in iot devices you can have an algorithm running in a web application and you could have you know search that needs to respond you know within milliseconds so all of these things come through in algorithms and they give you you know there are some basic examples of algorithms uh but uh there are more complicated ones so you may you probably have heard of binary search as computing a streaming median of numbers so when you have data coming in continuously and you want to emit the median of that data for for whatever reason for example you know to see what is the most common uh request type for example checking balance parentheses how this is this is so important as program is we have different types of parentheses we deal with i guess not so much when we get into scholar three but nonetheless uh even in scala we have we have rounded brackets they have curly braces and in other languages like python we also have you know we have square brackets uh so really important something use every day and if it were slow your id experience would be would be much much worse uh merge sort and other types of slots uh they allow you to sort data sort data very very efficiently faster than what you would be able to do if you just did the naive sort run length encoding encryption compression decompression super important topics again these are optimizations that we benefit from every day so our computers are jam-packed with algorithms we just don't see it they're abstracted away and all we can say as users is wow this is so fast or if there isn't a good algorithm in place and you know you would say oh this is really slow so why why is it important to understand algorithms now the the there are many many engineers who work with web applications and in different situations and they they don't really uh come across the need for algorithms but that is typically more useful when you deal with a big amount big amounts of data and um things that where you really really need that that ability to just respond instantaneously there is a big difference between data results that you can get in 30 seconds versus 30 minutes and likewise between 30 seconds and one second and half a second it makes all of the difference so um even if you learned an algorithm by itself it doesn't mean that you would be able to necessarily deal with variations because i i found that actually there are quite a few variations in your specific programs that you deal with where if you didn't understand the algorithm it would be very very challenging to come up with a slight modification to your algorithm so this is where and that understanding is really really important in distributed computation of big data you may uh for example need to share the data across different uh devices or perhaps um one one interesting thing uh with algorithms is i faced this interview questions like how do you sort 100 gigabyte file uh given you have 16 gigabytes of ram that sort of question and and it does become a i have faced this as a real world problem uh when you have like millions of events like every day and then you want to sort these events across uh across you know multiple days maybe even a year worth of data and you need to do it fast the other use cases is high performance local optimization so you don't necessarily distribute but actually you just need to get a result out really quickly it could be like finding a shortest path and a sort of thing so challenges with algorithms when i started i was already quite experienced in scholar when starting algorithms and i hadn't really covered algorithms in the past so while i was studying i found that i couldn't really find many resources for doing it in scholar a lot of well pretty much all resources that i found would be uh written in python or java or c plus plus and they use a lot of mutability and array indices and that sort of thing and this was one of the things that i learned about scholar is you don't you don't need to go so level you can actually write your algorithms in a in a higher level way uh that you can't necessarily do so easily in in other languages uh so there was an issue of comprehension where uh trying to comprehend an algorithm that is uh silver both is well it's just time consuming and ideally you just like to get it done more quickly so you need something that is very readable thinking from the perspective not just you know you shouldn't have just write only code you should really think about you know is is your code comprehensible for for the next person to read correctness of one of the other challenges was correctness an algorithm may work for some data but may not necessarily work for other data so um you have to test and test and test like testing is actually really important because uh for example if you decided to you know you had only one test case or two test cases and you wrote a piece of code maybe you're submitting it to codility or something for your interview and after you submitted it you realize oh they're testing for this extremage case and suddenly now you don't have you know you don't have the 100 that you thought you would so um yeah test case is super important and obviously stack safety uh and recursion so this goes back to to that talk on functions as uh as data uh which is very very cool um and yeah when you when you're requesting especially like in a sorting algorithm uh you have to be mindful of how much data you can fit in and is there a way for you to do something non-recursively and um the basic answer yes there is uh is just not necessarily so so straightforward so i'll go to the next slide uh so after after quite a bit of pain in in in trying to uh figure things out uh scholar algorithms did become fun um namely because of the rich standard library uh which provides you with a lot of met a lot of uh utility methods that uh you you simply can't find in other programming languages i have a in my next slide i have i have some comparisons immutability so the thing with immutability really is and and with the way scala allows you to represent data types is you are far less likely to enter into a an invalid state so with immutability you kind of know you start thinking in terms of transformation rather than mutation or changes so your algorithm isn't so much like oh you know a mother he has an if statement and this modifies that other variable and then once i've modified that what is the effect on the next thing that the next on the next if statement and so forth you don't really have to think about that so you have you have this more compositional approach where you know that okay this is my initial view of the world and i've transformed it into the next view of the world and from this you get a composition and a lot of elegance which is absolutely fantastic so uh the standard library offers you some really really amazing things like when you do a binary search so this is an example from a reset the code of a python piece where you access the length of the list you minus one and then you set the load to zero and and uh which represents the first item in this list and then you do a while comparison and you constantly keep on changing the bounds which is basically a search range and amazing scala gives you a range so the way how do i initiate this range is well i just say a dot indices and this is all provided by scala and if i want to sort across a generic list of items scala gives you this ordering of t which then you can use immutability so this is another another piece of code this is from stack overflow it's i think one of the algorithms to compare uh sequences of three and typically in in a language like python you would uh well for example you would generate a range based off of length of a and then you would do a lot of mutations and it turns out that this algorithm which which was very much in the shape of like i'm going to mutate every single step of the way it can be written fully in completely in an immutable style and this is again where scala's oh sorry it's from a rosetta code and with scala you can really do some quite fantastic things like sliding um zip with index that gives you the index of the item and actually really really importantly uh your result types they can be optional so many algorithms have come across in python they would give you like -1 for example if no result has been found and obviously as a consumer of this algorithm you may not necessarily expect a minus one to come back uh yet um you will have to deal with it like it's a magic constant but if you can lift out this uh success or failure into an actual type in scala this uh gives the consumer of your function uh that much more confidence of you know what this is or what does the result contain basically uh so yeah how do you survive in this scholar algorithms um i i think a lot of it could be applicable to it to any other programming language but really test cases test cases is the number one thing that you need to do you need to think about the zero case think about the one case depending on the algorithm you may need to think about the you know five case and then obviously the n case and then uh infinity case let's say your inputs integers are perhaps could be in max value or something and then how to deal with those so the reason for an algorithm is really to find up a lot of the time is to find a faster way of doing something now there are some algorithms which are just figuring out how to do something but most of the time it's really about efficiency like how do you efficiently do this thing how do you efficiently compare two strings rather than uh doing it you know in a way that's five times as slow because in in the end it makes a difference like i've i've dealt with applications where if you use the naive way of do processing like a 10 gigabytes uh json file you you could end up taking like six minutes to process that file versus six seconds after optimizing it so um you have you have a brute force way which is always correct and that is it's really really important to have that uh because it allows you then to create an implementation of your algorithm that is optimized and then compare the brute force with your optimized version using scala check the beauty of scala check is that it will check different edges different uh cases and if it finds that your optimization is wrong it will also give you a reduced case so you don't have to worry about um you know ex uh dealing with a very complicated piece of input it just gives you the minimum case to it to reproduce that error and then from that you can figure out okay ah i see there's one case that i forgot about uh so this is uh scala check is uh i think it's inspired from another library in uh haskell so i think for you know for these two languages they have this amazing way of representing property checking while other languages they may have these things um i haven't actually checked but i'm sure they are a lot more verbose are more challenging to use um because just scala check alone pulls in so many scala features like type classes and and generators and so forth and the last thing uh really very specific to how you implement the algorithm and it's it's it's relevant to any programming language is allocating less so if you can stream your data and you can't do your comparisons or checks without creating a new data structure for example instead of saying list dot map something which would allocate a new list for you you may want to say list dot view which doesn't allocate it and it's only evaluated when it's needed so this whole idea of laser computation is extremely powerful again haskell and scala and of course a few other programming languages uh give you this ability so you you can really uh write your algorithm in in the most human readable way without having to suffer the performance cost so in terms of in terms of scala itself the most important concepts i found were tail recursion tail recursion is basically the whatever is tell recursive you can write in a while loop and whatever you can write in a while up you can make tail recursive so scala would compile it down eventually when it runs on a jvm it would still be a while loop but it is more readable and it is more obvious what is going on when you are doing a tail recursion as opposed to a while loop and uh one of the main tasks like in learning an algorithm uh for example you take it from a book um is really transforming from this while while loop while mutable loop in particular because it is very mutable um transforming from that into a purely functional way of doing something and it just has that huge huge benefit of readability and and deco decomposability where you kind of know exactly which parameters are changing over time into your next call of the function so it's super like it's it's really super clear when your algorithm will end and it's not always obvious in in you know in python where you let's say you would have a while something if this then break if something else then continue and all return so you have very clear isolation faults and scans uh hugely important uh some of the most commonly used things uh they basically for non-scholar people of folders uh effectively can do what a forage loop would do and give you a single result and then a scan it is it's a very close sibling uh would transform from a a sequence into another sequence using incremental results so for example a fold uh would be to sum all the numbers in a collection so one plus two plus three plus four that would be your fault and gives you a ten but if you did a scan what you could do is you can get a collection of let's say your input was one two three four you can get the incremental buildup so effectively you would start with zero then one then three then six and ten and this is your final result so with a scan you can do you can really do a lot you can do these uh prefix sums and a sort of thing um but there are other ways to do prefix sums um yeah the next thing collects um so i'll show a fizzbuzz example where collect is is really super cool collect is basically a filter plus a map so if you are looping over your collection so i'm just going to speak in imperative terms when you're looking for your collection and then you say if something give me something else based on that and and this this is collect and it's a it's a single method um it's a partial function so in scala partial function gives you a way to only extract the things that you're interested in and do a transformation on these things in a single call which is super powerful now the last important concept i think is the sliding concept quite important for algorithms especially when you are comparing pieces of data that are next to each other so you would you could end up using all of these concepts in one implementation on algorithm of course it depends on the specific algorithm but uh these are the ones i found the most of course as i mentioned previously that there is view but i'll go into a bit more depth on that a little bit later so yeah performance aspects uh it's not slow scala is not slow is really really fast i i know some people think immutability is is gonna cause issues but really it doesn't cause issues uh i've been able to achieve as i mentioned like reading a processing not just reading processing a uh you know six gigabyte file in three seconds you can do that in scala in an immutable way of all things typically is just um the biggest enemy is allocations so using choosing the wrong data structure maybe you should have been using a vector rather than a list or maybe you should you know you should make sure that you use dot view the real thing about algorithms is not comparing one language to another it's really about can you achieve huge gains in performance that are based on a data size so an algorithm in one language and then and the same algorithm in another language they will um the the the performance difference between them will pretty much remain constant but compared to a horror algorithm for the same problem this is what you're really looking at to optimize so yeah um any questions before i go into this let's see on the twitch crowd so somebody mentioned competitive programming i think for competitive programming i would love scala to get into that scala is currently i i haven't really seen scala very much on competitive programming uh it's typically c and c plus plus and python um but maybe one day i i hope to i hope my hope is that scala becomes a language that people do consider for doing you know those complicated algorithmic problems it's just there are there aren't many uh resources for that okay i think that would be all the questions that i see unless my twitch is a bit laggy uh do you have any any other questions uh seller i don't see any other questions at the moment all right perfect awesome so yeah i'll get on with a short demonstration someone just said they got a question i don't know if you want to wait before before doing that whether we should carry on to the next point will you give examples of sliding absolutely best way to transform an element at index great so um santa will achieve what do you mean transform elemented index and and um yeah well santa is answering um ah i see i see it depends on the data structure uh so with a scalar list uh it's it's really the the most i guess it's not updating a scalar list is not the most fast thing you can do because uh you would be creating a new list uh so typically you would say list dot um actually let's see if demographics are able to help us so um if we log on to the scala algorithms id so there is this id that gives you let's see if it works i'm just gonna need to are you able to see my screen from here uh you may need to share a different desktop on zoom yeah or if you share an entire so then you can switch back and forth between the two of course let's just share now okay should be able to see this perfect yeah so uh on scala algorithms we have this for some reason when i'm sharing i can't use my keyboard anymore which is very very odd yeah take your time you should be able to do it yeah okay cool cool okay cool yeah uh so in order to update something at an index uh depending on what other stages you have you would typically do something like uh list dot updated that is that is one way of course it's not necessarily the most efficient idx and then this idx and then you have an f of that now this is not efficient the reason why is because looking up in a list is an o of n operation and then updating a list also you have to go through this list so in scala the depending on what you are doing but typically i would do a view if your transformation has more than one stage i i would do dot view dot zip with index and then with that zip then you can map and then you can say case item you can say choose this particular index and then for that index you can update the item with your f and then for any other item you don't do that transformation and this would give you that transformation here but if if yeah you would need to do the zip with index because if you didn't do so if you didn't do the view what do you want to end up doing well you don't have to use view.2 list what you would end up doing is creating another list here and then creating yet another list as you map it so not necessarily the most efficient thing so this is where the view concept is very important so we had a question also from igor so in scala algorithms basically through my work with algorithms i i isolated some important concepts and some of them were one of them was view so if you have a an example to to work with you can basically see that okay you know if if i do my view you know how does it work what side effects does it have and so forth like here we have a proof that you know vue is mute um is lazy and the beauty of scala is that you can still do imperative programming or side effecting programming where you need to you don't need to do anything special so here um yeah you have the view you have a modification happening and then you have a you have a evaluation happening for eager if we go to another concept and that's the sliding window concept uh really really important and if i run it in the ide now you can do sliding window on on lists you can do it on iterators pretty much any scala any scholar collection and yeah you you get you know you get items that are basically next to each other you can choose two you can choose three if i change it to three then this test will fail the reason why is because instead of having these three items in a list now we got two of length three so yeah i i hope you i hope you have a look at this figure and yeah let's uh let's go into the scholar algorithms itself uh so yeah it's a collection of well i'm aiming towards 100 algorithms but basically right now we have 77 algorithms they most of them are published some of them are free so and the rest uh the rest basically have those test cases for you to deal with so i'll just log out to demonstrate how it looks to everyone so yeah you have uh you have algorithms that you have full solutions too and some of the more complicated ones for example the run run length encoding you get you get test cases so normally i have enough information for you to start with so the reason the main difficulty i found was that there are no test cases online for algorithms like you can't really verify your solution and this here allows you to to verify those test cases for yourself so if if uh for example i'm just gonna do one w as a result uh and we should see one of the tests pass i i know i had coded it but yeah you get a template that you can work with and then you get test cases and you can incrementally work out the solution and then be you know have confidence that it is indeed the right solution uh this id has a cool feature that it saves your work so you can just exit it and then come back to it later saves it in your browser though and if you want to have more runs just register it is it's free to register to get unlimited runs in the ide if if there is a an algorithm in particular interested you can just go for that but you're welcome also to sign up for the unlimited membership so yeah i think this is um what else should i go through yeah we have test cases explanations uh and the algorithm itself as well as all of the relevant concepts so for example if you go back to the maximum potential profit piece of code you have all of the different scholar concepts that you should be aware of when approaching this solution and this list of concepts is provided for everyone so yes scan left scan right you can see exactly what to do here um and what else do i like to share about this yeah i'm just gonna share the full screen now how can i shadow full screen i think i need to exit the sharing and then start a fresh okay for some reason i can't see a way to share a full screen um [Music] which is very very very unexpected um we click click the arrow next to the share screen button there's a little arrow and um actually no press when you press the uh let me just see you should be able to just like you did earlier yeah yeah yeah exactly yeah well very very strange but i'll just go back to sharing this this one screen uh yeah if if it's you know let me know if there's any algorithms that you're interested in uh publishing more quickly i have a schedule um but i'm happy to change that if there's any algorithm anybody's interested in i'm happy to work out work that out we have a calendar so if you have google calendars you click here or if you have uh iphone or a mac you can click here and it will show up immediately on your um on your local calendar so you know you can just uh you know what to expect when and yeah my my hope really with scala algorithms is that it's really brings scholar into this territory of you know how we want to do like complicated algorithmic trading and whatnot like uh i even spoke recently with a company who wants to migrate um some other code to c plus plus for performance reasons and i'm thinking well soon you won't have to because the scala um yeah so let's look at the questions how does the idea work what's actually running the code uh so it's using the scala reflect code um more specifically the scala compilot so it just compiles it and runs it in terms of dealing with in terms of the infrastructure it's a rabbit mq plus a dedicated scala app and yeah there's there's a there's a there's a small like a sessions framework that you can see um just just to pass what the accession does nice uh so so what this means actually that there's a huge advantage you don't like you can just copy paste this code straight away into your scholar apple if you want to you don't have you know you don't have to use this id so it's really portable like your assertions are portable between like you want to do scala test yeah just copy paste this you want to do it in the ruffle you can copy paste this like i in my time with scala i basically went from using all these uh fancy uh should be matches and everything just into plano sessions because you can the benefit of play-doh sessions is you can just analyze them so much more easily and they're just that much more uh consistent because you can you can literally pull your assertion into anywhere in in your scholar code and it's um this allows you to even have tests right next to your main code that you know a testing framework wouldn't necessarily give okay uh if most things are immutable data is in heap i believe this causes problem of performance and maybe there could be better options or using default gvm settings are okay are the defaults are okay um basically behind the scenes there may be a lot of stuff going on to make it fast i i really haven't come across performance issues like even updating a scala map is not slow and the jvm does an amazing job in optimizing stuff so if you find some something super unperformant actually just message me you can press contact here and just send me i would be quite curious um because i i think that this would um this would be interesting cases to look at uh and i'm always sure that there is a way to optimize it i really have like a dealt with some very high performance applications in scala and um you know you may have to go all the way to using like uh unsafe code but you can still be pure functional and it can still be immutable next question uh curious about how multi-core architecture overlaps with algorithms other techniques for increasing cache hits for example uh yes there are so really really good question uh with with lazy programming uh [Music] now i i don't know the details of how they do it but basically you get a whole stage fusion so if you had uh if you had a piece of code that has multiple stages so let's just see if we can find something yeah i think this one is is a good example if yeah if you have a piece of code that has multiple stages actually i think this one i can optimize a bit more uh if you have those multiple stages then each stage would be executed immediately one after another for every individual could be executed immediately one after another and then from that sense you could have you wouldn't have to even do like cash uh you wouldn't have to be populating your cash because of every stage in your transformation simply because you decide like to do that view on your collection uh yeah there are techniques for increasing cash hits i think it's it's quite a niche topic um if you can uh drop me a message on twitter or or from the scala algorithms website i would be more interested in in your use case um on on the aspect of multi-core architecture i found that if you try to make your code immutable and run really performantly in a single thread you may not you may actually have worse performance if you try to make it multi-core again it depends on a particular use case so yeah let's let me know i would be quite curious and you know to to come up with some material on that because um you can process like 20 gigabytes of data a second on scala if you want to what else uh juan g pablo one says is your goal to help people learn how to write high performance scala code or high performance functional code so high performance scholar code i think it's a little bit of a different topic it does intersect with algorithms but it's not exactly algorithms my goal is that scala does become a language in which you can do algorithms in a native scholar way at the moment uh many solutions i would find for algorithms in scholar they they may be either mutable or very inefficient or just just difficult to read and i think that's um to have this resource should uh encourage people more to just you know not not go back to python not go back to java it's really it's really like about other attention and also about uh you know bringing people in and sharing hey you can do this algorithm in a way more comprehensive way a comprehensible way like if i if i you know if i just google this stock by sell to maximize profit like this is the code that you're you know you're i'm gonna consent to that like this is this is a very different type of code that you're dealing with and you're doing immuta uh mutability you're comparing like you're dealing with indices uh making sure that you don't escape your array you don't get index out of bounds or incrementing stuff like um and yeah just just doing a lot of complicated stuff and you know the answer is do you really need to can you just separate your problem into multiple simple stages so yes and no but also from the aspect of actual applications um it's really it really depends on general performance optimization because algorithms are just one way to do performance optimization and yeah i love performance optimization and skull i can achieve amazing things but i will probably write separate resources for that okay i think um i think that would be all for the questions i don't know if there's anything you would like to ask seller i think we're just reached the 45 minutes well that's great and let's see does anyone have questions can you briefly did you look at the last one and um can you briefly share what your six gig gigabyte in three seconds example was and what sort of work did you have to do to get it to that point oh that's an amazing question yes so this is an online gaming platform uh that i was building called action fps is for a very very simple open source game and in there uh you are basically processing a lot of streaming data so it's just one big uh tsv plus json file which has all of the information what happened in in in many many games and yeah it was really it was really really interesting the first uh before i got to problems with reading full strings and splitting strings i had to first figure out all of my data structures so allocations and for that i would use the sbt jmh library so there's a nice tutorial and this is this is made by conrad and and team uh and this allows you to view let me see if there's a screenshot there isn't a screenshot but you can import the results in a nice into a nice gui and basically see where your performance bottlenecks are so uh if you can reduce your allocations and just doing unnecessary work when processing the data because the fastest thing you can do is reduce your allocations and skip over the data that you're not interested in that is a huge benefit the next thing is well again it's allocation related as you're reading data out you are creating strings for example but you what you can do instead of creating strings is to read this uh data uh byte by byte and and computing um on that and changing your code to deal with that can give you an amazing performance boost so how do you do that i have something called random file i forgot the exact name uh random file java reads memory basically it's a memory mapped file so random access file um yeah great question on stackoverflow does it read the whole file in memory uh no it doesn't read it in memory it's it just sticks very very uh very very quickly to the piece of um to the piece you're interested in and then from there you can read this whole file in in an immutable way like you you don't have to say like oh seek instead you you create an abstraction and then in scala that just says i want to seek this next and then you have a separate interpreter so this is where the whole idea of interpreters is really important um yeah so reducing allocations skipping over the stuff you're not interested in and and just getting down to the lowest level which is uh reading data directly you can read data directly from you know uh from a file and because it's memory mapped like you don't have to read the whole file in advance and you just you just get that reading straight from a wrap ram type of thing you can also do other cool things using the java io libraries but i think that would be a topic for another talk so i think uh that would be all for the questions i would like to yeah thank you sarah and thank you so much for the to the 50 viewers that are looking at this and also really really good questions i will i will save these questions and see if i can come up with something um to go into a bit more depth but yeah i i hope that um yeah i hope that scholar algorithms does does enhance scala as much as possible um and and yeah for those for those interested just if you have any questions or ideas or requests uh just let me know and yeah on twitter or through the contact form i have and then i'll be i'll be happy to i'll be have i'll be happy to have a look at it thank you so much thanks william really appreciate you doing this talk it was awesome