Write Better Code with Swift Algorithms

[Music] the swift standard library comes packed with lots of functions and types to help us solve most common coding problems but it can't do everything and so for more advanced usages you want to turn to apple's swift algorithms package an open source swift package packed with useful things tuned for maximum performance and flexibility now right now is the advent of code 2021 so now is a great time to look at ways algorithms can help make you write better code faster code and safer code this thing comes packed with functionality for things like unique objects compacting objects choosing random elements and many many more things it's really really useful but even better apple has said that this thing here the algorithms package will give them an opportunity to iterately explore the problem space and learn how these algorithms connect and interact before getting them into the swift standard library and so if you use these things today you get better code today and perhaps also a look in what the standard library might be in a year or more as they get merged in best of all adding this thing into an xcode project is really really easy go to the file menu choose add packages choose apple swift packages then select swift algorithms now choose add package then select your target here and press add package and it'll be imported and now when you're ready just go ahead and add import algorithms here and it'll pull that in inside that swift file to go ahead and start using straight away now in this video i want to explore nine or so of my favorite pieces of swift algorithms but there's so much more it can do let's look at some code now now if you have two arrays of data and you want to loop over them both somehow and do some work with them you might write code like this let names one be an array of jane elizabeth mary and kitty and names two be an array of uh daphne then eloisa then oops francesca and finally hyacinth to loop over them both and print them both out you might say for name in names one plus names two print name and when that runs it'll print out jane elizabeth mary kitty daphne louisa francesca hyacinth um which is great but in order for this to work we have to create a new temporary array that merges names one and names two in this case there's four and four in each one of these arrays it's pretty small a fairly low cost but if you arrays are much larger this would be quite wasteful now swift algorithms has a solution called chain it creates a new sequence by joining two together concatenating them but does so without performing any additional allocation so it's extremely efficient and to use it you just say for name in chain names one names two like that and we got the same result so no additional allocations that's the massive performance boost here what happens is behind the scenes uh chain basically stores references to your two existing sequences names one names two in this case and it just just ties together the iterators basically so as one iterates through and reaches the end it starts the next one instead so it doesn't do any extra copying here it's amazing and it works with other sequence types too so we can say for example uh does a value lie within two different ranges we could say our two low range is zero through 20 and our two high range is 80 through 100 and then we'll say let out of bounds be chaining too low and too high and now we can use contains on that we could say here's a new value 35 print does out of bounds contain that value of course the answer will be false because it's not inside either of those two ranges even better it works across any kind of sequence and so you can actually even chain a range and an array together into one sequence so you might say let our reserved seats be the range of zero through 50 and that our unavailable seats be an exact number of uh 61 68 75 76 77 and 92 for example and then make a whole disallowed group the chain of reserved seats and unavailable seats and then you can say we're requesting a new seat of number 39 does disallowed contain that somewhere so even though it's two different sequences it'll still work it'll still say yes that does indeed contain that seed number so that's chain next up chunking if you ever want us to break up a sequence into equal chunks or perhaps based on some criteria swift algorithms is ready for you because it provides a few variants of chunky functions to do just that and they turn complex error prone work into one-liners with extreme efficiency which is amazing as an example we could make a student struct with a name string and a grade string for example so we've got a name and a grade letter a through f and then make a bunch of students so i'll say our result is an array with uh student and we'll do name and grade of let's do that for a set temporarily let's make a bunch of these things two three four whatever a bunch of these things uh we'll say we've got uh taylor had an a of course because she's brilliant uh sophie uh slophy sophie had also a grade of a uh let's say bella had a grade of b we'll say rajesh had a gate grade of c and then let's do some more tony grade of c we'll say teresa had a grade of d and at the very end we'll say boris had a grade of f so a bunch of students there with varying grades and using algorithms from the swift algorithms package we can chunk this results array based on grades and then print them out as we go so we could say give me students chunked by their grade using results dot chunked on and i'm going to ask for backslash dot grade so chunk them based on their grade and now i can loop over that together i can say uh for grade students in students by grade i'll print out what the grade was so i'll be like all the a grade students first for example and then loop over all the students in the student's array and print out a little tab and then do student.name with interpolation and print empty line at the end like that and now we should see all being well so our a grade students were taylor and sophie then b was better and c was right here and d and f down here so it automatically made a new chunk for us automatically as you can see based on the grades we had however what it's doing is it's basically looking through the array or this case a sequence generally and looking for when the value changes so when grade changes it makes a chunk break so here we have a and a one chunk b one chunk c and c one chunk d one chunk and f one chunk you gotta be careful therefore if your grade jumps around for example if you add a then b then c then a again it have two different a chunks now in our code it's not a problem because the a's are grouped together as are the two c's um but if we try to chunk by name we have a problem because uh taylor um is up here t now two more t's down here they'd be chunked separately and so really what you want to do is get your results array sort it first in our case we'll sort by name like that and then chunked based on their um name so we'll do chunked on let's do uh dot name dot first so the first letter of their name for example and now we could say down here uh for first letter and students in students by not grade by name makes more sense now i think call that by name there we go by name uh print the first letter out and then do again for student in students in students print the little tab sign again and then string interpolation student.name like that and then print an empty line at the end and we should now have them chunked by name by the first letter of their name so you can see here uh the b's bella and boris are rajesh s sophie and then three t's at the bottom but sorting matters because we didn't have that sort would have different groups of t's like remove the sort here you'll see what i mean so i do that for example just sort it chunky immediately now we have taylor first then a break sophie bella rajesh and then tony and theresa and then boris at the end by himself where he deserves to be um there is also an alternative chunking method let us uh group sequences by the number of items in them so we could say i want to have uh pairs now break my student class of the pairs i'll do results chunks uh of count two so put two students in each chunk is what we're saying here and i can do four pair in pairs i'll do let names be list formatter dot localize string by joining pair dot map backslash name so convert the student just the student name and then put that into list format so we get an array of uh a and b for example and then uh print names so we should now get taylor and sophie bellerin radish and so forth boom like that and then boris sadly by himself at the end um but that illustrates an important factor of the way chunks of count works if you have an uneven end for the last chunk it's fine you'll have one item by itself at the end the rest are paired up nicely be careful because this is very very carefully optimized it's going to return an array slice rather than array because that's more efficient so won't copy a new rage time it'll just store the bits of the original array at their indices uh this means if you try and read indices in there like zero and one because it's pairs um you'll have a problem and so code like this is bad don't do this um if pair.count is two there's two of us in there not ie not boris we'll print out uh let's do pair zero dot name and uh pair one dot name i'm just missing our prince there um are working together but if you only have one person in our not pair uh we'll just print out print uh pair zero dot name is working alone and uh that might look like it's correct you know we've got two items in the array we'll read zero and one uh don't do that it will not work if i run this code back it's gonna just crash on me bang i'm trying to read zero in an array that contains two items because it's not an array it's an array slice and so the items won't be at zero and one they'll be at their original indices in the original array if you desperately need that if you want an array rather than array slice that's fine just go ahead and convert your result using map to an array of stuff instead so it'll convert from a very slice to full arrays and that'll work the way you expect that's chunky let's delete some of this code next up let's look at a random sampling of items because one of my favorite pieces of code from swift algorithms is a new random sample count method and this thing has a counterpart called random stable sample and they're both enhanced forms of the regular random element method on sequences that picks a random element but they instead select n random elements give me three random elements that are not duplicate now of the two using random sample count is the fastest and it'll work on all sequences however it does not retain the order of your sequence so you'll get things back shuffled up but you will get back still n random non-duplicate elements in any order for example we could say let lottery balls uh be one through 50 as a range and then let winning numbers the lottery balls dot random sample of count seven give me seven bowls from that that are all different and then print winning numbers and let's give that a try and in case you are feeling lucky those are your numbers for the week ahead um if they win by the way yeah obviously i'm just magical if you specify a counting here that is greater than or equal to the number of items in your sequence you'll get back the entire sequence if i said 70 here for example i'll get back the entire sequence 1 through 50. it'll still be randomized so it'll be an unknown order like that there um but it won't break because that's too many an alternative is called random stable sample and this works a little bit differently because it works only on collections it has to know ahead of time how many items it's choosing from to get a nice stable consistent thing here but it also runs a little bit slower than a random sample because it has to do more work but it does retain the order which is important sometimes so we could say uh let people equals let's say chidi let's say elena eleanor jason and tahani and then let's select it for the bad place be people dot random stable sample with count of two and then print selected so i'll pick two random people from that array non-duplicate but retain their order so it turns out cheating into honey who knew and that is random sampling and random stable sampling next up let's give us some code swift algorithms has a new striding by method that will move over a sequence by a step of your choosing again and again again similar to the stride from through or stride from to free function except it works directly on sequences and therefore it's a lot more efficient first the simple examples you can see a direct comparison of old versus new uh we could write some code to get a uh range of one through 100 and then give me the odd numbers from that by doing numbers dot striding by two and now for odd number in odd numbers uh we'll just print out odd number here that should be a thousand sorry not a hundred thousand much more interesting now print out all the numbers from one to a thousand like that which is fine um in comparison though we can get the same thing using stride from through or um or stride from through by that's what it is from two i'm gonna confuse myself from two buy from through buy that's the one um we could say here um use stride from through buy that's the one from through buy we could say give me dot lower bound and numbers dot upper bound uh by two and get the same result so how is it any better well the answer is that uh this striding by version from swift algorithms works on more complex collections and so it'll work with uh strings or race slices where the indices don't match up or they're hard to calculate so we can officially pull out parts of a string for example we could say let input string b a1 b2 c3 d4 e5 and then let letters be input string dot striding by two and now for letter in letters print letter letter there we go so it prints out hopefully abcde is going over the string through the way now if you did that with striding from through by that's the right one um you'd get an integer out each time and you have to use that to index into the string which is very very slow this is much much faster in fact i use this recently because i was um decrypting a columnar transposition cipher with my daughter uh and there plain text letters are scattered across the word so you know 1 6 11 16 21 are the first letters of your first word and then two seven and so forth throughout the way so you've got to stride through strings a lot so that's striding next up uniqueing because it has a whole bunch of swift algorithms functionality of handling unique elements in a sequence either based on their natural uniqueness if they conform to hashable already or using a function you specify so simple example you ask a bunch of folks with numbers they consider lucky maybe the ones i showed you a minute ago in our lottery balls but you get a range of answers through and so you want to find out uh which ones are the unique numbers that were chosen and we can do that now by saying uh let all numbers be let's say uh three seven let's do eight eight seven sixty seven eight 7 bunch of numbers 8 3 7 31. those are the ones you were given as answers we can now say let unique numbers be all numbers dot unique give me just the unique numbers coming back and then let's sort those as well and then say for number in unique numbers ah print out number is a lucky number like that boom and that previously might have been done with you know converting the array into a set then back to an array again then sorting it this is just more efficient and built right in now thanks to algorithms now if you want something more advanced there's a second version of uniqt where we can pass in a function that accepts one element from our sequence and it return any kind of hashable data from that that'll then be used for unique you have to choose what it is that makes your thing unique for example we could use that plus key paths as functions we could say there's a struct called city which has a name string and a country string or country string and then make a bunch of places we could say a destinations array which is going to be a city with the name of let's make a few of these one two three four five will do we have a name of hamburg which is in germany a little geography test view here kyoto in japan osaka in japan then we'll do two more naples in italy and then florence in italy now with that in place we can unique that based on one of those values so we could say let our selected cities be our destinations uniqueing it on backslash dot country so give me one city from each of those possible ones based on a unique country value and now if i do for city in selected cities and print let's say uh visit city.name in city.country when that runs it's going to print out visit hamburg was it kyoto and was it naples because in this situation unique dom will automatically always return the first unique element of several options and so naples appears first for italy so it's chosen and kyoto appears first for japan so that's chosen first too so that's unique i love it next up stripping out optionality now swift standard library has always had compact map for doing uh transformation of items in an array using some kind of function of our choosing and then unwrapping the optional result and discarding any nils however it's common to have code like this at numbers equals 10 nil 20 nil 30. this is an array of optional integers for example i've obviously hard coded it here but you'd have one made some other way um you'd see code like let's save numbers be those numbers compact map dollar zero like that and we're saying here is basically skip the transformation step and just give me the optional unwrapped behavior so if i have print safe numbers dot count in here we should get back three numbers which will be 10 20 and 30. so all we're doing is saying there's no transformation just just compact them basically that works but swift algorithms of course has a better solution we can now just say compacted like that and again we'll still get three because it's removing the nils removing the optionality for us and yes of course that is fractionally fewer characters a type but has an important benefit which is compacted is always lazy as opposed to it being lazy when you actually ask for it and so the work of unwrapping and removing will only happen when you actually use the thing which makes it a lot more efficient when you chain operations together next up there's a new way to handle nested loops it's quite beautiful of course nested loops let's loop over one sequence every time we loop over another sequence so for i in 1 through 10 inside there 4 j and 1 through 10 whatever you want to right and swift algorithms has a function for this called product that gives us extra control over that same situation for example if we have two arrays of people and games five people is sophie and then uh charlotte and then maddie and then seven and then i say there's also an array of games and we'll say they want to play mario kart and boomerang foo which i absolutely adore brilliant game um we want to say uh sophie will play mario kart so if you play boomerang foo charlotte will play mario kart shout out to play boomerang foo mario play america i'm gonna go through every possible combination there and that's normally a nested loop but we can now use product we can say let all options equals the product of people and games and now we can do for option in all options print we'll get a tuple back here by the way we'll say option 0 will play option option.one and that'll give us all possible combinations so sophie plays america sorry boomerang food charlotte mario kart sharp boom prank which is great right and that's nice now the first parameter here can be any kind of sequence because it's looped over only once so sophie charlotte maddie 7 only once sequence is fine the second one has to be a collection that's gone over multiple times so you can see mario kart appears here then here then here then here but you could also provide the same collection to both parameters if you want to for example you could say i want to make a complete set of multiplication tables in the range of 1 through 12. i'll do let all multiples be a product of range and range so same thing twice and now i can say for pair in all multiples i want to print out let's say oops pair dot zero x pair dot one is and then do pair dot zero star pair dot one to multiply inline in the uh interpolation there when that runs out we're gonna get back the full set of multiples from 1 times 1 up to 12 times 12. now you might be seeing this and thinking wait a minute this is just the same as using a a nested for loop why would i want this but the magic is that product gives us back a new collection we can then manipulate further for example we might want to say actually i want to only have some questions from there i could say i want to have a question count of 20 and for the multiples i want to have product range and range but then shuffle those and then prefix question count give me that many questions from the thing and now get back a completely random multiplication test so you can see it's uh 20 random multiples like that which is harder to do of course if you're doing it in a nested for loop and of course if you were listening carefully to my video you can wind back a little bit you might recognize we can use a random sample here to get even less work rather than shuffling and prefix and we could say give me a random sample from there or count question count even better even more optimized i love it boom and now one downside to using uh product at least right now is it only works with two parameters that sequence in a collection uh meaning if you want to have multiple loops now for i in 1 through 10 for j and 1 through 10 4k and 1 through 10 and who knows what you want to nest your product calls and it gets a little bit messy and so we could make uh the world's most tedious game of cluedo or clue if you're in north america we could say uh let our suspect be an array of uh colonel mustard and let's do professor capital p professor plum and then mrs white then let locations be an array of kitchen and library and then study and then haul and then let weapons our third thing to loop over will be candlestick and dagger knife something in the american version not sure um lead pipe and rope and now we want to combine all of those together to have nested arrays all the way down and that's where we want to use product and product together messy as i said so our guesses will be the product of the product of suspects and locations and then weapons as well and now we have one super thing and you've got now tuples inside tuples to work with like i said it's tedious but there you go uh for guess in guesses uh we'll say print was it guest.0.0 that's going to be the suspect's name in the guest.0.1 that'll be our location uh with the guest.one that'll be our weapon so it's the same order suspects locations weapons we provided in their creator like that and that will print out every possible guess for our little game of clue or cluedo there we go um yeah i said it is a fairly tedious game of the game but that's basically how my eight-year-old plays it quite frankly so that's not a bad result for only a handful of lines of swift algorithms code that is product next up let's look at sliding windows of sequences because it's another one of my favorite editions of swift algorithms it's the ability to read overlapping subsequences in a larger sequence which is great for doing things like uh calculating moving averages across a whole sequence of dates and numbers or whatever now if you just want all neighboring pairs then you can use a special method adjacent pairs you could say let numbers be uh 1 through 100 dot adjacent pairs and then for pair and numbers print will say pair is pair.0 and pair.1 and that will print out all possible pairs all the way up and it's it's a sliding window you get 1 and 2 first then two and three then three and four then four and five all the way down to ninety nine hundred at the very end um so it's not just like one two three four five six not chunking it it's one two then two three then three four and so forth so reuse each one each time for more advanced usages here you can actually ask for an exact window size you can say i want to have a window of count how big your window should be unless you control how big your sliding window should be so we could say i want groups of five windows of count five and let's say uh inside there i'll get group in numbers and then inside there all my strings will be group mapped to strings and then print out again list formatter.localize string by joining those strings and now get all being well boom one two three four and five two three four five and six three four five six and seven and so forth so if those were you know a hundred days of temperatures you could find out uh get each window of temperatures each one of days average them out and say oh this these five days here had the highest lump in the whole thing it's really really nice for that kind of code here but brilliantly again it gives us subsequences we're looping over here this is a subsequence of the original sequence and so it's extremely efficient i actually again used it recently doing some code cracking i was decoding a visionnaire cipher it allows me to look through a huge string of letters to find all the repeating substrings very very easily finally finally so i've tried to go very fast there's lots to get through i know you can watch it again if you want to swift algorithms comes with enhanced methods for calculating the minimum and maximum values in a sequence you can provide a custom test if you want to but if your sequence conforms to comparable you can just use the default of less than i could say for example let names equals john and paul and george and ringo and then if i can read the first and last names from there using names.min and max then print the first and print the last when that code runs it'll figure out which name comes first in case george and which name comes past the last ringo in one operation which is faster than doing min first then doing max later because you're doing in one pass rather than two passes it also provides values for reading multiples of the highest and lowest values at the same time so i could say uh my scores array are numbers like 42 and then 4 and then 23 and then 8 16 and 15. and i'll do let three lowest equals scores.min give me a count of three give me the three lowest scores inside that array and now print three lowest and that'll print out being well four eight fifteen now internally that will sort the sequence and then prefix or suffix based on max or min to get the result but if using less than 10 percent so your count is less than temp in the total sequence it'll use an optimized version instead so it'll automatically just do the right thing for you for maximum performance like so much of the rest of swift algorithms wow okay i have just touched on a handful of my personal favorites from swift algorithms it's so much fun to dig around with there's a whole lot more functionality out there if you just dig through and it's all as powerful as the examples we looked at here to find out more i recommend you do check out the repository on algorithms on github it is right here boom github.com apple swift algorithms go and check it out that one there uh it's all open source you just dig through it you can just go ahead and read their code and see how they do stuff and learn why their versions are so fast here's a chunking code here there's lots and lots of work going into this to make it as efficient and flexible as possible to find out how they squeeze so much efficiency from their code there's also a amazing wbc21 talk here's kyle maycomber um was there as uh carol lontorey as well was there um go and check the video meet the swift algorithms and collections packages for more information it's only half bits on algorithms as you can tell they'll have collections but it's still packed with lots of information to help you write better code so now i'm done over to you go and bring in the package to your project go and write better code thanks to swift algorithms and if you want more videos like this one subscribe to my channel i make lots of videos lots and lots of videos teaching folks swift swift ui and much more completely free subscribe now

Channel: Paul Hudson

Views: 11,400

Keywords: swift, algorithms, Xcode, performance

Id: pUYw9D0aq6g

Length: 34min 34sec (2074 seconds)

Published: Thu Dec 02 2021