Do it in place. What does that mean?
This is a common expression for programmers and I’ll explain what it means and what the alternatives are.
If the size of the data you’re working with is large compared to the memory available, then you just may not be able to perform some operations on the data unless you can do this in place.
When programmers talk about doing something in place, this means that you need to use the memory that some data already occupies and maybe a small amount extra. That’s it.
Let’s say that you need to rearrange some characters in a word. Maybe you want the characters to be in a random order or maybe just backwards. Instead of allocating more memory for a copy of the word that you’ll build from the original based on how you need the characters rearranged, an in place algorithm will swap two characters at a time right in the original word until you are done.
This has the advantage of not requiring any extra memory beyond a reasonable and fixed amount of memory. But it also has the downside that once you begin, then the original word is no longer available unless you reverse the work done. Listen to the full episode for more or you can also read the full transcript below.
Transcript
This is a common expression for programmers and I’ll explain what it means and what the alternatives are.
First of all, just think of what it means to run in place. Your legs and arms are moving but you don’t move around. When you have a bunch of people who are running in place in a small room, they don’t interfere with each other. Imagine how many people would fall down if they were all running around the room.
That brings us to one of the main reasons why you might need to do something in place in your code. If the size of the data you’re working with is large compared to the memory available, then you just may not be able to perform some operations on the data unless you can do this in place.
When programmers talk about doing something in place, this means that you need to use the memory that some data already occupies and maybe a small amount extra. That’s it.
Let me give you an example. Let’s say that you need to rearrange the letters in a word so they’re in a random order. This would be good for a word guessing game. If you’re building this game for a modern computer, then it’s not going to matter really how you rearrange the letters as long as your technique is correct. You don’t need to worry about if your algorithm is an in place or out of place algorithm.
An algorithm is just the steps you take to accomplish something. It’s the rules you follow no matter what the word happens to be.
But maybe you’re writing this program to run on a small microcontroller with very limited memory. Even then, a single word at a time isn’t going to make much of a difference. I’m just using the example of randomly rearranging the letters in a word because it’s a simple example to explain even though it’s not the best example to show the need for an in place algorithm.
So to fix that, let’s momentarily consider something where an in place algorithm really could make all the difference. Instead of scrambling the letters in a word, maybe you need to scramble the pieces of a large puzzle. It’s common to find cardboard puzzles in stores with a thousand pieces and I’m sure there are much more challenging puzzles available. Even a puzzle with a million pieces though would fit in a modern computer many thousands of times over with no problems. At least it would start to stress a small embedded control board.
So what kinds of problems would this really be an issue then? For that, think about a server computer that regularly handles requests for millions of users. Now you can see that it doesn’t take a very large problem to cause difficulty when that problem is being solved in slightly different variations thousands of times simultaneously. In a situation like this, maybe those extra memory locations that you thought were in abundance are now rather scarce. If there’s a way for you to reduce the amount of memory needed to perform the same operation, then why not consider it?
That’s why knowing how to perform some action in place is so important. It allows your program to run with the data it’s already using without needing to go get more. At least within reason.
I’ll get back to the specifics of how to rearrange the letters in a word right after this message from our sponsor.
( Message from Sponsor )
One way to rearrange the letters in a word is to first reserve room in memory for a copy. Why would you want to do that? This lets you refer to the original word while building a scrambled version. If the word is plastic, then you just allocate 8 bytes somewhere in memory. Plastic has 7 letters. Why should you allocate 8 bytes for what should only need 7? Don’t forget the terminating null character. Even though we don’t see it and it can’t be printed, that null character is super important because that’s what lets almost every string manipulation method know when it’s reached the end of a string of characters.
By the way, depending on what character encoding you’re using, you might need 2 bytes per character or even 4 bytes. Or maybe even a variable number so that some characters require a single byte while others might need up to 5 bytes. Can a single character really need up to 5 bytes? Sometimes, yes. It depends on the character and on the encoding being used. Listen to the Q&A Friday episode from 2016, Feb-05 for more information about characters and encoding.
Alright, so you have the extra memory. Go ahead and put a null value in the last position. You might as well do this now. That’s the one character in the word that we don’t want to move. It has to remain at the end.
Then start up a random number generator and randomly copy characters from the source word to the destination. Check out episode 35 for more information about random numbers.
That will give you a scrambled word and it uses the same amount of memory that the word itself uses. For a simple operation like this, we can do better.
Let me explain how to accomplish the same thing in place.
We’ll need just a little extra memory but this can actually just be some variables on the stack. We’re already saving not just space but time since we don’t need to allocate some amount of memory that changes based on the length of the word provided. We only need a variable to hold a single temporary character as well as an integer counter. We’ll use the counter to keep track of how many times we shuffle characters around. the longer the word, the more times we’ll need to move things around.
And we’ll use the temporary character variable over and over as we swap characters. that’s how we’re going to scramble the letters in the word. But just swapping two letters at a time. Each time, we’ll pick two random characters for the swap. We could end up swapping the same character multiple times but that’s okay. That’s part of what makes it random.
This is a very common technique in programming. It would probably be a pattern if it wasn’t so simple. Anytime you have two variables of any type. As long as they’re the same type, then you can use this technique to swap them. Just copy the first item to the temporary variable. This doesn’t change anything yet. It just let’s us remember what the value of the first item is. and by first item, I don’t mean it has to literally be the very first character in the word. Although it could be. I’m just one of the two items to be swapped the first item and the other one will be the second item. This has no relationship to the actual positions of the items. It’s possible that the second item might come before the first. That doesn’t matter. The algorithm just needs to refer to one of them as the first and the other as the second.
Once you’ve saved the value of the first item in the temporary variable, then copy the value from the second into the first. At this point, instead of swapping the values, all we’ve done is made two copies of the second value. But we’ll fix that. Then take the temporary variable that has the first value and write it to the second item. Now we’ve swapped the items. Sure, we’ve still got a copy of the first item sitting in the temporary variable. But that’s why it’s temporary. We’ll use the temporary variable for the next swap.
Because this technique just keeps using the same temporary variable no matter how long the word is or how many swaps we perform, this technique is said to be in place. Because most of the operations were performed directly on the memory that was already being used.