Divide and conquer algorithms скачать в хорошем качестве

Divide and conquer algorithms

►► Audio, Video, and Transcript available: https://lispcast.com/divide-and-conqu... ►► Subscribe on iTunes: https://itunes.apple.com/us/podcast/t... The divide and conquer pattern is a widely used #functionalprogramming pattern. It lets you turn potentially hard problems into trivial problems and then recombine the answers. Transcript What is the Divide and Conquer pattern? Hello. My name is Eric Normand and these are my thoughts on Functional Programming. There's a common pattern for implementing algorithms in Functional Programming called Divide and Conquer. I'll give you an example. If you're going to calculate the length of a linked list, the recursive way of defining that, the standard functional way, is you check if the list is empty. If it's empty, the length is obviously zero and if it's not empty, the length is one plus the length of the rest of the list. Notice how in both cases, all you have to do is determine if it's empty or not. In both cases, the operation is trivial. There's no decisions to make after that. There's no looping, there's nothing. It's just a simple case analysis and then a trivial return. In the first case when it's empty, trivial return is zero. In the second case, it's one plus the calculation over the rest of the list. This is the first principle that needs to be true to apply this pattern. That is that the small cases need to be easy because you're dividing the problem. That's where the Divide and Conquer comes from, the divide. You're dividing the problem up into small problems that are each easy to calculate. Often, they're trivial to calculate, there's almost no calculation. The second part that you need is you have to be able to combine the answers of those trivial problems in some way. In this example, we're combining them with plus. We're doing one, which is the length of the head of the list, and then plus, and then the length of the rest of the list. If you have some operation that happens to be associative, which means that the grouping doesn't matter. It means you can actually split the problem up arbitrarily. In this example I just gave, the list was split into two but two in a very specific place, which was it's split in two right after the head. But you could split it in two right in the middle if that is better for your particular data structure. In this data structure, a linked list, it is the best way to split one off at a time. Let's look at another algorithm and then apply these principles to see how we can do that. We've got this divide, get to an easy problem where it's trivial, and then put the answers back together. Let's say we're looking for a value in a list. We just want to know yes or no, is this value in this list? Let's say we can break up a list arbitrarily. It's more like an array with random access. We want to find the trivial cases where it's almost no decision to make. In this case, we want to handle the...Obviously, we need to handle the empty array. If it's an empty array, the answer is obviously this value is not in the array so it's going to be a false. In the case of an array of one element, all we have to do is compare the value we're looking for with the element. If they're equal, we return true, if they're not equal, we return false. A tiny little decision there. It's still trivial. There's no logic about searching or anything like that. We have one thing. We're comparing it to another. We're done. In the other case, it's going to be where we have not zero, not one but more than one, we're just going to split. We're not going to do any real logic. We're just going to split. We're going to divide. Divide the problem and then recombine the answers. How do we divide the problem? One thing we could do is split the array in two. We'll just figure out where the middle is. Take the length of the array. Cut the array in two, two separate arrays and then recursively find the element, the value in that list on the left, recursively do it on the right, and then we'll recombine them. When we recombine them, we have to figure out what operation we're going to use. In this case, it's going to be OR. Did we find it in the left? Yes? Great, we're done. OR we didn't find it, let's look in the right. It's an OR. An OR, as we know, is associative. The grouping doesn't matter. If there's any true anywhere, regardless of how you group, it's going to give you the same answer, true. Otherwise, it'll give you a false. In that algorithm, those are the three cases. The empty array, trivially false, the one element array, which is trivially just compare the value to that one element, and the more than one array, which is simply split it in two, recursively call it, and OR them together. #Clojure #FunctionalLanguages