I may be so bold as to say that everything we have done so far in this course has been about efficiency. The very nature of computing information is limited foremost by the resources you have to compute said information.
Hence, a computer which spends an hour doing something another computer can do in five minutes is going to be an inferior computer. However, a computer which can't run a code that another computer can run is perhaps not a question of better or worse computer, but of better or worse code.
And so we come to a question of efficiency, and one of the most important places for efficiency: sorting.
Once again I'm going to use a real-life analogy. If you have a bajillion eggs and you need one particular egg (probably because you're a crazy person), it would be horrible to look through each individual egg. However, if the eggs were, say, organized by colour or mass, then already you can discard any egg that isn't the colour or mass of the one you're looking for.
Heck, there are robots that do this for Lego bricks. But what of code, then?
Well, code is wonderful for coming up with ways to sort things because there are a lot of different ways you can create a code to sort things.
Nonetheless, if we are indeed searching through our eggs, what is the best way to organize a hodge-podge batch, barring Rube Goldberg-esque machinery antics (as seen above)?
Well let's say for convenience all the eggs are lined up. We can compare each egg and place smaller ones to the right of larger ones (bubblesort), but there's no way you would be willing to just swap two eggs every time until you cover all the eggs - that would take forever with a bajillion eggs!
On the other end of the spectrum, you could divide up the eggs around the most average egg (quicksort), and then find the most average egg in each division and sort out which eggs are larger and which eggs are smaller. That goes much faster since you are working with smaller and smaller values-- wait, something smells like recursion!
Yes, that beautiful aroma of recursion is back. While something like grabbing two eggs and swapping them is all fine and well, it requires many attempts, usually as many as there are eggs - hence eggs squared to get through the entire thing. Yuck.
Rather, with quicksort or mergesort, we can look at smaller and smaller sets of eggs. When we work backwards, we can compare the sets and quickly organize them again, thereby finishing with a big sorted line of eggs after much less time since we are dividing the eggs into smaller sets (logarithmically smaller sets!).
Thus, efficiency is perhaps the most crucial part of sorting giant amounts of information (smaller sets can, of course, use more performance if the information needs to be found more quickly). With well-crafted code, and often recursion, it is possible to vastly reduce the amount of work we need to do when sorting or looking at other problems which require high efficiency. And so we can sort our eggs so much faster than before.
Saturday, March 29, 2014
Monday, March 24, 2014
Assignment Two & Other Such Business
The assignments are now wrapped up, embalmed, buried. Good good.
This last one in particular was a bit of a struggle towards the end -- our code was developed very smoothly and efficiently, but with lots of clumsy extra parts, long strings of redundant code and a lack of polish despite the fact that it worked relatively well.
So we tore out its guts and rebuilt it. And there were a few scares when you realize a thing or two went missing during the process. One example was our implementation of regex_match, which took the longest of everything -- at one point, we were gathering every conceivable example which would work with a string, which led to exponential runtime for our niggling StarTree. We were able to fix that by taking out the helper function altogether and allowing regex_match to return recursive bools to answer other bools. Our StarTree ended up checking slices of the the indices of the string along the string's length until it found an example which conformed to the tree we were after, breaking it up into little pieces.
But then, horror of horrors, BarTree was returning True for things which should return False. Again, pen and paper had to leap to work to visualize what exactly was being done by the code to make it keep making this mistake. Lo and behold, there was an unnecessary line of code - a 'for' loop left over from the StarTree. What was lovely about BarTree is that the comparison was ultimately very simple: it's either one side of the bar, or the other side of the bar. Nothing else matters.
That, though it was a revelation within the final hours of our time with A2, proved exceptionally helpful in understanding the inner workings of the assignment and why the trees were an effective way of storing regex information.
Rather than relying on a string, which requires all manner of complicated indexing to break apart each time you want some information, a tree holds it all neatly and allows effective recursion. Checking the inside of another pair of brackets? Go a level deeper. Especially useful was the fact that the tree system made it easily visible what was or wasn't needed to investigate the code. You don't need to worry about a StarTree having a DotTree inside until you provide the answer to the DotTree. The StarTree cannot affect the DotTree's result. Understanding this albeit basic concept did greatly aid in contextualizing how our functions worked.
After the assignment is done, our sights are now turned to the midterm, and to runtime again. I can say that I understand the way runtime works, although I am not entirely sure that I can safely navigate it without a good bit of brain-training, which will undoubtedly be occurring for most of the week leading up to the midterm. I am sure I will have to revisit some 108 notes on sorting, but that should be a boon in and of itself anyway.
This last one in particular was a bit of a struggle towards the end -- our code was developed very smoothly and efficiently, but with lots of clumsy extra parts, long strings of redundant code and a lack of polish despite the fact that it worked relatively well.
So we tore out its guts and rebuilt it. And there were a few scares when you realize a thing or two went missing during the process. One example was our implementation of regex_match, which took the longest of everything -- at one point, we were gathering every conceivable example which would work with a string, which led to exponential runtime for our niggling StarTree. We were able to fix that by taking out the helper function altogether and allowing regex_match to return recursive bools to answer other bools. Our StarTree ended up checking slices of the the indices of the string along the string's length until it found an example which conformed to the tree we were after, breaking it up into little pieces.
But then, horror of horrors, BarTree was returning True for things which should return False. Again, pen and paper had to leap to work to visualize what exactly was being done by the code to make it keep making this mistake. Lo and behold, there was an unnecessary line of code - a 'for' loop left over from the StarTree. What was lovely about BarTree is that the comparison was ultimately very simple: it's either one side of the bar, or the other side of the bar. Nothing else matters.
That, though it was a revelation within the final hours of our time with A2, proved exceptionally helpful in understanding the inner workings of the assignment and why the trees were an effective way of storing regex information.
Rather than relying on a string, which requires all manner of complicated indexing to break apart each time you want some information, a tree holds it all neatly and allows effective recursion. Checking the inside of another pair of brackets? Go a level deeper. Especially useful was the fact that the tree system made it easily visible what was or wasn't needed to investigate the code. You don't need to worry about a StarTree having a DotTree inside until you provide the answer to the DotTree. The StarTree cannot affect the DotTree's result. Understanding this albeit basic concept did greatly aid in contextualizing how our functions worked.
After the assignment is done, our sights are now turned to the midterm, and to runtime again. I can say that I understand the way runtime works, although I am not entirely sure that I can safely navigate it without a good bit of brain-training, which will undoubtedly be occurring for most of the week leading up to the midterm. I am sure I will have to revisit some 108 notes on sorting, but that should be a boon in and of itself anyway.
Friday, March 14, 2014
Progress
I had another "I'm going to destroy this computer" moment while working on E3 this week (the exercise name makes me so happy - look everyone, I'm working on E3!)
After hours of working on the code without progress, I gave up and slept. One Eureka moment and eight hours earlier, I fixed the code.
The error was an early subscription. Just a tiny, tiny miniscule [0] in the wrong spot. Down falls the house of cards.
In the end, I feel like it was so obvious: my code was returning tuples, and I was supposed to compare all the tuples and then use part of the end result. Instead, I was comparing half of all the tuples and using the part as the end result. The answer was so delicately thwarted off course, like a paper boat, that it didn't even seem like a possible error at first.
I stand by my love for recursion. Brian has reminded me in a comment on a post two weeks back that passing lots of changing parameters like that can cause a lot of hidden arguments to appear, but I think part of the beauty of recursion is that it works like a human mind. Your own mind will skip steps and store only useful information - it's not going to keep every part clean and neat. Perhaps that is the advantage of a computer, but perhaps it also makes it work more like you do. Which makes it easier for you to understand.
I'm still making progress though. Breaks are lovely, and a real privilege to have - code can't always be set aside and worked on later. But to be able to stare at something, try one thing, fail, draw out exactly what you want to have done, and jingle with the parts until it works is something so ritualistic, so mystical and magical, that I truly believe it is one of the greatest, most beautiful things about human innovation and problem-solving. No matter how advanced the computer, there will always be some information that must be discovered by hand. Until the computer isn't a computer anymore - then it's just a human which computes and diagrams its plans.
The brain often seems a lot like a bunch of floating nodes: you access one piece to access another, to access another, to access another.
In fact, what makes the brain so fancy is that you can have multiple nodes in a web, like Jimmy Neutron's brain in his old TV show. This point connects to this point connects to this point.
The brain is just recursively running through its own sub-trees of information, but really really well. If I want to eat, I start at my "hungry" root and go through a whole bunch of options - when, where, for what amount of time, with whom. If I want to have fun, I start at my "bored" root and check where, for what amount of time, with whom, doing what, when, how.
And then I get a nice list back of possible suggestions based on which trees I go into: Thai food after 6 with my girlfriend; video games for an hour until class.
It's creepy, in the sense of unexpected, how much this course actually has to do with life. Or maybe just my life. Because I'm a big nerd.
After hours of working on the code without progress, I gave up and slept. One Eureka moment and eight hours earlier, I fixed the code.
The error was an early subscription. Just a tiny, tiny miniscule [0] in the wrong spot. Down falls the house of cards.
In the end, I feel like it was so obvious: my code was returning tuples, and I was supposed to compare all the tuples and then use part of the end result. Instead, I was comparing half of all the tuples and using the part as the end result. The answer was so delicately thwarted off course, like a paper boat, that it didn't even seem like a possible error at first.
I stand by my love for recursion. Brian has reminded me in a comment on a post two weeks back that passing lots of changing parameters like that can cause a lot of hidden arguments to appear, but I think part of the beauty of recursion is that it works like a human mind. Your own mind will skip steps and store only useful information - it's not going to keep every part clean and neat. Perhaps that is the advantage of a computer, but perhaps it also makes it work more like you do. Which makes it easier for you to understand.
I'm still making progress though. Breaks are lovely, and a real privilege to have - code can't always be set aside and worked on later. But to be able to stare at something, try one thing, fail, draw out exactly what you want to have done, and jingle with the parts until it works is something so ritualistic, so mystical and magical, that I truly believe it is one of the greatest, most beautiful things about human innovation and problem-solving. No matter how advanced the computer, there will always be some information that must be discovered by hand. Until the computer isn't a computer anymore - then it's just a human which computes and diagrams its plans.
The brain often seems a lot like a bunch of floating nodes: you access one piece to access another, to access another, to access another.
In fact, what makes the brain so fancy is that you can have multiple nodes in a web, like Jimmy Neutron's brain in his old TV show. This point connects to this point connects to this point.
The brain is just recursively running through its own sub-trees of information, but really really well. If I want to eat, I start at my "hungry" root and go through a whole bunch of options - when, where, for what amount of time, with whom. If I want to have fun, I start at my "bored" root and check where, for what amount of time, with whom, doing what, when, how.
And then I get a nice list back of possible suggestions based on which trees I go into: Thai food after 6 with my girlfriend; video games for an hour until class.
It's creepy, in the sense of unexpected, how much this course actually has to do with life. Or maybe just my life. Because I'm a big nerd.
Monday, March 10, 2014
Moving Along
I wasn't so sure about linked lists at first. I'm still a bit confused.
I mean logically they make plenty of sense. You have an item connected to another item. But when it comes to implementation, I feel a bit like my head's come off and I don't know what to do with the rest.
The nodes and wrapper concept helped. It seems like what is to be learned this year in computer science is that pictures really are worth a thousand words. And that brings me to __str__ in code, because we need more stuff like that.
String representations came up a little with the assignment as well, so let's talk about them. Far and away, the nicest thing you can do for a user is make what they do as clear as possible. I have seen the countless times with my older family members: it must be really obvious what you're doing, otherwise you're going to miss it and get confused.
If your program doesn't identify what is going on well enough for a 75 year-old to follow along perfectly, you need to work on user interface and graphics, and the baby steps of that are definitely found in __str__.
I had a similar problem when we did trees: it is so much easier to visualize a tree when you draw it like a tree. Shocking, yes.
Linked lists, on the other hand, are actually really easy: a beautiful example was given on a lab handout. Just do arrows between values until None.
1 --> 5 --> 3 --> 2 --> None
Voila! Your linked list is easy to visualize. Of course, it's missing the levels of indentation, but presumably there will be some kind of understanding for the user that the elements are each other's rests.
For trees, you need some fancy indents. There was an example given in class, but in all honesty it didn't look very clean and simple. There's a good spot to find a nice way to code that sort of information.
And now the assignment, which at least for part 1 seemed deceptively simple. No string representations yet, just class design.
There was a good bit of time spent wondering how specific the classes should be: how much information should the user need to provide? We settled on some restrictions, but the nice thing again about the regex classes is that they shouldn't screw up and fail to be represented correctly because the specific subclasses can all be represented as regular regexes.
And the best part is? There's a string representation, and it's sensible. Very sensible. Part of the advantage is that a leaf's parent will generally be a fancy operator-type element that looks nice between values in our ternary alphabet ((0.1) or (2|0*)).
So that's this week's lesson: make your code visually helpful.
I mean logically they make plenty of sense. You have an item connected to another item. But when it comes to implementation, I feel a bit like my head's come off and I don't know what to do with the rest.
The nodes and wrapper concept helped. It seems like what is to be learned this year in computer science is that pictures really are worth a thousand words. And that brings me to __str__ in code, because we need more stuff like that.
String representations came up a little with the assignment as well, so let's talk about them. Far and away, the nicest thing you can do for a user is make what they do as clear as possible. I have seen the countless times with my older family members: it must be really obvious what you're doing, otherwise you're going to miss it and get confused.
If your program doesn't identify what is going on well enough for a 75 year-old to follow along perfectly, you need to work on user interface and graphics, and the baby steps of that are definitely found in __str__.
I had a similar problem when we did trees: it is so much easier to visualize a tree when you draw it like a tree. Shocking, yes.
Linked lists, on the other hand, are actually really easy: a beautiful example was given on a lab handout. Just do arrows between values until None.
1 --> 5 --> 3 --> 2 --> None
Voila! Your linked list is easy to visualize. Of course, it's missing the levels of indentation, but presumably there will be some kind of understanding for the user that the elements are each other's rests.
For trees, you need some fancy indents. There was an example given in class, but in all honesty it didn't look very clean and simple. There's a good spot to find a nice way to code that sort of information.
And now the assignment, which at least for part 1 seemed deceptively simple. No string representations yet, just class design.
There was a good bit of time spent wondering how specific the classes should be: how much information should the user need to provide? We settled on some restrictions, but the nice thing again about the regex classes is that they shouldn't screw up and fail to be represented correctly because the specific subclasses can all be represented as regular regexes.
And the best part is? There's a string representation, and it's sensible. Very sensible. Part of the advantage is that a leaf's parent will generally be a fancy operator-type element that looks nice between values in our ternary alphabet ((0.1) or (2|0*)).
So that's this week's lesson: make your code visually helpful.
Sunday, March 2, 2014
Recursion Returns
More about recursion this week, after a very good midterm.
In all honesty, recursion is probably the biggest thing I will take away out of what we have examined so far in computer science, and the reason is twofold: it's really useful and it is a very regular occurrence in day-to-day life.
Picture this: every time you perform an action to complete the same action again on a different number of things, you are doing recursion. For instance, you have a pile of eight books, and you want a book towards the bottom. Because I'm in a good mood we can do this with a picture.
------ Book A ------
------ Book B ------
------ Book C ------
------ Book D ------
------ Book E ------
We'll start with five and see where that gets us. Let's say the books are really heavy. Like, biology textbook levels of heavy. You can't move a whole bunch at once, but you need that damn Book E.
You could shove the pile over, but most of the time that creates a mess and risks damaging your nice books, so instead you remove Book A and Book B (I realize at this point I am basically recreating Assignment 1, but this proves it actually was a sensible assignment to write).
------ Book C ------
------ Book D ------ ------ Book A ------
------ Book E ------ ------ Book B ------
Now presumably you don't need the books in a particular order so you can put C and D on top of A and B (although if they had different sizes you would). Cool. But we just did recursion, guys. The pile is smaller so that we can do the same thing again for a smaller parameter, in this case books C and D.
That's recursion in your life right now, being all sneaky and recursive. What makes it so useful is that it is a wired-into-your-head feature for completing an action. Doing similar things in multiple steps is often recursive. It's to make things more efficient: that's why in language you can have recursive statements in which an inner part is embedded in a larger one, rather than repeating yourself or making two sentences.
This is what makes computer science recursion really neat, because it's letting our computers be more like our brains (of course, Skynet and all, but live optimistically). And computers aren't quite as good as our brains (yet) so recursion is even more useful for them.
Better example: packaging. There's a fair amount of "packaging"-type stuff in computer science, and when I say "packaging" I mean putting things within things within things, like you've got something in a package in a package.
Let's pretend I am really awesome and built a robot to wrap presents for me because I am the worst at wrapping presents. And because the wrapping robot was lonely I built an unwrapping robot to hang out with it. And let's, just for the sake of the example, pretend they wrap things like so:
Wrapper sees an object 'book'
Wrapper computes how fragile 'book' is and determines the value 2 (out of 5) for a little fragile
Wrapper decides it will repeat its wrapping algorithm a number of times until the book's fragile value is equal to its wrapping value (i.e. it is wrapped enough that there's no danger in it being damaged).
Wrapper begins to run its algorithm on 'book':
Start:
object: 'book'
fragile value: 2
wrap value: 0
fragile value != wrap value
First run-through: (put object in a list)
object: ['book']
fragile value: 2
wrap value: 1 (determined based on number of lists - can be found with recursion!)
fragile value != wrap value
Second run-through: (as before)
object: [['book']]
fragile value: 2
wrap value: 2 (as before)
fragile value == wrap value
object wrapped
Now the 'book' is wrapped through recursive run-throughs, so Unwrapper can unwrap it!
Unwrapper works like Wrapper but reversed, and without a fragile value because Unwrapper gets a little crazy - it just unwraps until the object's wrap value is 0.
Start:
object: [['book']]
wrap value: 2 (again, determined recursively)
wrap value != 0
First run-through: (take object out of one list - you can just re-assign object to object[0])
object: ['book']
wrap value: 1 (as before)
wrap value != 0
Second run-through: (as before)
object: 'book'
wrap value: 0 (as before)
wrap value == 0
object unwrapped
Tadah! The book was on efficiency, which is Unwrapper's favourite subject! What good friends those two robots are.
Thus, a simple example of recursion. You can make a code that sums the number of nested lists; even one which can work for multiple objects in the same wrapping.
But to hammer the point home, this is what makes recursion so neat. It has the power to understand more tasks than, say, a for loop (recursion works for any depth of object - a for loop on its own requires a certain number of specified inner loops). You can even make recursion only go a certain number of times!
For instance, say you have a very deep nested list and you want to go to a certain point and have the computer show you how deep you are. Well you could make a function which takes recursive depth as a parameter, and then reduce the size of that parameter each time you recursively run the function! I.e.
rec_depth([[[[[[[['eight layers deep']]]]]]]], goto=4)
so the code starts by checking the number of lists in and comparing that to goto - it's not deep enough so it starts again
rec_depth([[[[[[['eight layers deep']]]]]]], goto=3)
why is the goto changed? because the list is smaller, so its position is actually further up - this would continue until you get a goto of 0
rec_depth([[[['eight layers deep']]]], goto=0)
at this point, you would stop and do something else. maybe, for instance, the computer prints the new list, or prepends 'you are here' inside (so it prints [[[['you are here', [[[['eight layers deep']]]]]]]]).
Anyway, I think I've gone a bit over the limit here - that's recursion though, in all its glory!
In all honesty, recursion is probably the biggest thing I will take away out of what we have examined so far in computer science, and the reason is twofold: it's really useful and it is a very regular occurrence in day-to-day life.
Picture this: every time you perform an action to complete the same action again on a different number of things, you are doing recursion. For instance, you have a pile of eight books, and you want a book towards the bottom. Because I'm in a good mood we can do this with a picture.
------ Book A ------
------ Book B ------
------ Book C ------
------ Book D ------
------ Book E ------
We'll start with five and see where that gets us. Let's say the books are really heavy. Like, biology textbook levels of heavy. You can't move a whole bunch at once, but you need that damn Book E.
You could shove the pile over, but most of the time that creates a mess and risks damaging your nice books, so instead you remove Book A and Book B (I realize at this point I am basically recreating Assignment 1, but this proves it actually was a sensible assignment to write).
------ Book C ------
------ Book D ------ ------ Book A ------
------ Book E ------ ------ Book B ------
Now presumably you don't need the books in a particular order so you can put C and D on top of A and B (although if they had different sizes you would). Cool. But we just did recursion, guys. The pile is smaller so that we can do the same thing again for a smaller parameter, in this case books C and D.
That's recursion in your life right now, being all sneaky and recursive. What makes it so useful is that it is a wired-into-your-head feature for completing an action. Doing similar things in multiple steps is often recursive. It's to make things more efficient: that's why in language you can have recursive statements in which an inner part is embedded in a larger one, rather than repeating yourself or making two sentences.
This is what makes computer science recursion really neat, because it's letting our computers be more like our brains (of course, Skynet and all, but live optimistically). And computers aren't quite as good as our brains (yet) so recursion is even more useful for them.
Better example: packaging. There's a fair amount of "packaging"-type stuff in computer science, and when I say "packaging" I mean putting things within things within things, like you've got something in a package in a package.
Let's pretend I am really awesome and built a robot to wrap presents for me because I am the worst at wrapping presents. And because the wrapping robot was lonely I built an unwrapping robot to hang out with it. And let's, just for the sake of the example, pretend they wrap things like so:
Wrapper sees an object 'book'
Wrapper computes how fragile 'book' is and determines the value 2 (out of 5) for a little fragile
Wrapper decides it will repeat its wrapping algorithm a number of times until the book's fragile value is equal to its wrapping value (i.e. it is wrapped enough that there's no danger in it being damaged).
Wrapper begins to run its algorithm on 'book':
Start:
object: 'book'
fragile value: 2
wrap value: 0
fragile value != wrap value
First run-through: (put object in a list)
object: ['book']
fragile value: 2
wrap value: 1 (determined based on number of lists - can be found with recursion!)
fragile value != wrap value
Second run-through: (as before)
object: [['book']]
fragile value: 2
wrap value: 2 (as before)
fragile value == wrap value
object wrapped
Now the 'book' is wrapped through recursive run-throughs, so Unwrapper can unwrap it!
Unwrapper works like Wrapper but reversed, and without a fragile value because Unwrapper gets a little crazy - it just unwraps until the object's wrap value is 0.
Start:
object: [['book']]
wrap value: 2 (again, determined recursively)
wrap value != 0
First run-through: (take object out of one list - you can just re-assign object to object[0])
object: ['book']
wrap value: 1 (as before)
wrap value != 0
Second run-through: (as before)
object: 'book'
wrap value: 0 (as before)
wrap value == 0
object unwrapped
Tadah! The book was on efficiency, which is Unwrapper's favourite subject! What good friends those two robots are.
Thus, a simple example of recursion. You can make a code that sums the number of nested lists; even one which can work for multiple objects in the same wrapping.
But to hammer the point home, this is what makes recursion so neat. It has the power to understand more tasks than, say, a for loop (recursion works for any depth of object - a for loop on its own requires a certain number of specified inner loops). You can even make recursion only go a certain number of times!
For instance, say you have a very deep nested list and you want to go to a certain point and have the computer show you how deep you are. Well you could make a function which takes recursive depth as a parameter, and then reduce the size of that parameter each time you recursively run the function! I.e.
rec_depth([[[[[[[['eight layers deep']]]]]]]], goto=4)
so the code starts by checking the number of lists in and comparing that to goto - it's not deep enough so it starts again
rec_depth([[[[[[['eight layers deep']]]]]]], goto=3)
why is the goto changed? because the list is smaller, so its position is actually further up - this would continue until you get a goto of 0
rec_depth([[[['eight layers deep']]]], goto=0)
at this point, you would stop and do something else. maybe, for instance, the computer prints the new list, or prepends 'you are here' inside (so it prints [[[['you are here', [[[['eight layers deep']]]]]]]]).
Anyway, I think I've gone a bit over the limit here - that's recursion though, in all its glory!
Subscribe to:
Posts (Atom)