Unknown
Algorithms are like verbs and data structures are like nouns. An algorithm is just a method for doing something on a computer; a data structure is a layout for memory that represents some sort of data.
If you wanted to store thousands of English words along with their meanings in a way that you could later look them up whenever you needed, you could do that in multiple ways. Consider two:
You can see how it is advantageous to do it as 2. Not surprisingly, that's how dictionaries are arranged. So a dictionary is a data structure: it has both data AND a structure especially suitable for performing some action on that data (in this case, looking up words).
Now once you have the dictionary, how do you look a word up? Possibly like this:
This sequence of actions you take to look up a word is an algorithm: a general description of how to do something (in this case, looking up words), usually with the data from your data structure. This algorithm (let's call it LOOKUP) does not need to have the exact 4 steps I listed above. It could be anything as long as there is a sequence of steps that lead you unambiguously to the desired result. Because that is the primary purpose of algorithms: to make actionable knowledge portable. You are now free to compile your own dictionary of words from any language and send it over to me. If you've compiled it alphabetically and I know the alphabet order for that language (necessary for step 1 of algorithm), I can use your dictionary to look up words all day long without your help.
So data structures and algorithms work together to let you do stuff with your data. Data structure is where the structured data is, algorithm is how you do with it whatever it is you want to do. Notice that the design of the algorithm is guided by the data structure it will work on. The algorithm can only have actions licensed by the data structure it operates upon. Step 1 from our algorithm LOOKUP works only because the dictionary is arranged alphabetically - were it not, you wouldn't know where to open it. You would have to go through it page by page to look a word up. In fact, this is also an algorithm (Brute-force search) but it is not a very good one, is it? The fact that our data structure has a, well, structure helps us use a much faster algorithm (LOOKUP) to look for a word.
Now that I've mentioned speed, it might be interesting to think of how we can make our algorithm LOOKUP work faster (since that's what you almost always want). I believe by now you can see there are two things we could tweak to gain speed - the algorithm itself, as well as the data structure. Look at step 1 again. Can this be done faster? Yes. The letter S has the most words, followed by P, C, D, M etc. If you have some idea of the relative number of words per alphabet you can make a better guess about where to open a dictionary. This in turn will make step 2 faster (on average) because if you land in the vicinity of a target word more accurately, you need to flip fewer pages correcting for it later. Similarly, step 3 can become faster if you use the guide words at the top margin of every page.
The other way is to modify the data structure itself. You've probably seen dictionaries like this:
The notches, or tabs, let you immediately open the dictionary in the general area of a letter. This makes step 1 of our algorithm faster without us having to explicitly modify the algorithm. In essence, the basic idea is to inform either the algorithm or the data structure better to make the entire operation faster.
If you wanted to store thousands of English words along with their meanings in a way that you could later look them up whenever you needed, you could do that in multiple ways. Consider two:
- Write them down in any order.
- Write them down alphabetically.
You can see how it is advantageous to do it as 2. Not surprisingly, that's how dictionaries are arranged. So a dictionary is a data structure: it has both data AND a structure especially suitable for performing some action on that data (in this case, looking up words).
Now once you have the dictionary, how do you look a word up? Possibly like this:
- Open the dictionary roughly at the page where you think your word would be.
- Flip a few(or maybe many) pages back or forth depending on where you've landed in step 1.
- Scan page to find your word.
- Read the entry next to the word.
This sequence of actions you take to look up a word is an algorithm: a general description of how to do something (in this case, looking up words), usually with the data from your data structure. This algorithm (let's call it LOOKUP) does not need to have the exact 4 steps I listed above. It could be anything as long as there is a sequence of steps that lead you unambiguously to the desired result. Because that is the primary purpose of algorithms: to make actionable knowledge portable. You are now free to compile your own dictionary of words from any language and send it over to me. If you've compiled it alphabetically and I know the alphabet order for that language (necessary for step 1 of algorithm), I can use your dictionary to look up words all day long without your help.
So data structures and algorithms work together to let you do stuff with your data. Data structure is where the structured data is, algorithm is how you do with it whatever it is you want to do. Notice that the design of the algorithm is guided by the data structure it will work on. The algorithm can only have actions licensed by the data structure it operates upon. Step 1 from our algorithm LOOKUP works only because the dictionary is arranged alphabetically - were it not, you wouldn't know where to open it. You would have to go through it page by page to look a word up. In fact, this is also an algorithm (Brute-force search) but it is not a very good one, is it? The fact that our data structure has a, well, structure helps us use a much faster algorithm (LOOKUP) to look for a word.
Now that I've mentioned speed, it might be interesting to think of how we can make our algorithm LOOKUP work faster (since that's what you almost always want). I believe by now you can see there are two things we could tweak to gain speed - the algorithm itself, as well as the data structure. Look at step 1 again. Can this be done faster? Yes. The letter S has the most words, followed by P, C, D, M etc. If you have some idea of the relative number of words per alphabet you can make a better guess about where to open a dictionary. This in turn will make step 2 faster (on average) because if you land in the vicinity of a target word more accurately, you need to flip fewer pages correcting for it later. Similarly, step 3 can become faster if you use the guide words at the top margin of every page.
The other way is to modify the data structure itself. You've probably seen dictionaries like this:
The notches, or tabs, let you immediately open the dictionary in the general area of a letter. This makes step 1 of our algorithm faster without us having to explicitly modify the algorithm. In essence, the basic idea is to inform either the algorithm or the data structure better to make the entire operation faster.
Posted in: Algorithm/Data Structures
0 comments:
Post a Comment