From the first day of college, I began to contact programming , The teacher told us all kinds of algorithms . Search from all kinds of 、 Sort , To recursion 、 Greedy algorithm , I've been fighting with these algorithms since I was a freshman . Until after work , In order to cope with the interview , Still have to go back to nibble algorithm book or brush some algorithm exercises , To be able to pick up some memories of school . Why is the algorithm so hard to remember ？ Or say , Why can't computer algorithms be more intuitive ？
Because computer algorithms are anti human , essentially , This is caused by the difference between the way of thinking of computer and that of human brain .
There is no definite theory about the mechanism of human brain thinking , For the time being, it is thought that chemical substances and electrical signals play a role . Although there is no scientific explanation , But each of us has a brain , Each of us can feel our own way of thinking .
And computers are created by humans , It was not designed to simulate the human brain , So it has its own way of working , Only by understanding how computers work , Can learn to think in its way , Can write the most suitable program code for the computer to run .
Look for a specific number in the sort array —— The human brain vs Computer round 1
Let's take a concrete example , To show that the way of thinking of human brain and computer is different , Let's say we want to find a specific number from an array that's already in order .
It is known that the sorted array is 1 2 3 5 7 13 34 67 90 127 308, We hope to find out if 13 This number is in the array .
How does the human brain accomplish tasks ？
The human brain deals with such problems almost “ cheat ” Of , We can go at a glance , We found out when we scanned our glasses 13, So if I ask myself how I found 13 Of , I can only say that I “ See ” 了 .
And how does the computer accomplish this task ？
The simplest and stupidest algorithm is to read the array one by one , I believe that every student who has learned the basics of programming can write code similar to the following .
boolean isNumInArray(int num, int[] array) {
for (int i = 0; i < array.length; i++) {
if (array[i] == num) {
return true;
}
}
return false;
}
The computer needs to start with the first element of the array , Check the elements of the current array one by one , and 13 comparison , See if it's equal . To find out 13 The number of , Computers do 6 Sub cycle operation , And people see the answer almost instantaneously .
Why do computers solve problems in such a way “ stupid ” Well ？ Let's start with how computers work .
CPU How it works
CPU As the core part of computer , It is also the main carrier of the algorithm .
CPU Don't think like a person , It only knows some basic instructions . every last CPU All have their instruction sets , The instruction set is stored in CPU Inside , Yes CPU A hardware program that guides and optimizes operations . to put it bluntly , The instruction set is CPU All the ways of thinking . For example, common instruction sets have ADD Instructions , This instruction can add the values in two registers , And will be stored in another register ; There will also be SUB Instructions , Used to subtract two register values . If you look up all kinds of CPU Instruction set manual , It will be found that the basic addition, subtraction, multiplication and division instructions are basically included , And storing it in memory 、 Instructions for fetching data . And common CPU Instruction set , Hundreds of instructions at most . in other words CPU Only a few hundred orders .
And the human brain is relative to CPU, Have strong memory and association ability , For example, you see 1+1, Think of 2, See the red light , I'll think of stopping , See the door , Just go to the door handle , These are things that you can immediately reflect without thinking .
therefore ,CPU Yes （ Instructions ） Less than people , that CPU Isn't it stupid ？ you 're right ,CPU It's just stupid , however CPU The advantages of human brain are incomparable ：
- although CPU I can only do simple things （ Hundreds of instructions ）, But it can be at a fixed time （ Command execution time ） To ensure the correct calculation results . And the human brain can't guarantee to produce in a fixed time “ Again ” The result of our thinking .
- Modern CPU The process can execute more than a million instructions in a second , And the thinking speed of human brain can't compare with , One of us “ idea ” The shortest reaction time is a few seconds .
in summary ,CPU It's a stupid and quick guy .
Computer storage
The common memory of a computer is a register 、 Cache 、 Memory 、 Hard disk, etc. .
Register is equivalent to something that can be remembered immediately in human brain ,CPU All operations are performed on the data in the register . Registers store what the computer is currently doing （ Instruction register ）, Data to be calculated （ Data register ）, Calculate which step （ Segment register ） Etc . Whether it's the first one with registers CPU It's the latest and strongest CPU, They only have dozens of registers at most （ There are hundreds of special cases ）, in other words CPU The information that can be used immediately at the same time is dozens of numbers .
Memory is the main storage facility of computer , It can store information about running programs , The memory is equivalent to the bookshelf of the library ,CPU Need to use a certain segment of memory data is , Need to pass through LOAD Instructions , Also attach a shelf number （ Memory address ）, Then the memory controller can transmit the data of the corresponding address to CPU,CPU Then put the loaded result into the register . Memory access is much faster than registers , But the speed of accessing the data distributed in the memory is basically the same .
Because most of the time CPU It needs to read a continuous section of memory for operation , So usually CPU There will be a cache to cache the whole block of recently used memory , And make CPU You don't have to read memory every step of the way . Cache speed is between register and memory , But much higher than memory . The size of the cache is usually between a few megabytes and a dozen megabytes .
Hard disk belongs to external storage , There will be a rotating head in the old mechanical hard disk , When reading the disk file, you need to turn the head to the corresponding position , Disk speed is much slower than memory , And if the head of the disk stays in a certain position , Information from different locations on random disks , It will be limited by the physical speed of the movement of the magnetic head, resulting in uneven speed . The new SSDs use memory like storage media , The performance of random access is greatly improved .
therefore , A computer has a small brain that can only remember a little bit of things （ register ）, But can have relatively large fast memory （ cache ）, Have far more knowledge than human reserve （ Memory ）, And I have a huge mobile library with me （ Hard disk ）, So in terms of storage , Computer is like a rainman with congenital defects （Rain Man）.
therefore , Let's analyze round 1 Why does the computer operate in the end ？
First let's look at the definition of our function
boolean isNumInArray(int num, int[] array)
In the underlying implementation of the calling function , The parameter is assigned to two registers .isNumInArray This function , When called , The first parameter num Value 13 Will be loaded into the register （r1）, Second parameter of array, Pass in CPU When it's just array Address information in memory , Is stored in another register （r2）.
And on the fourth line array[i] == num when ,CPU Three things need to be done to finish the work ：
- adopt ADD Instructions , according to array The address of （r2） and i（r4） The number of , Calculate the memory address that needs to be read
- adopt LOAD The instruction loads the number corresponding to the memory address into the register （r3）
- adopt CMP Command comparison num（r1） and r3 Value , The result is stored in the result memory
And according to the operation 3 Result , If the results are not equal , be CPU Cycle counter needs to be set i add 1 Storage register r4, Do the above calculation again . The difference is , Second to second N The second step will be much faster than the first one , Because the contents of the entire array have been captured by the cache .
therefore , We can see why computers seem so stupid in solving this problem ：
- Computer input is limited . A computer can only read a single value at a time （ It's not too bad to have cache help ）, And put a limited number of values in the register , And human beings can read multiple values in one time and store them in their minds through vision and so on .
- There are restrictions on the instructions of the computer , Only basic operation instructions can be supported . And the human brain can have a wealth of instructions , For example, directly through a bunch of just seen numbers in the visual pattern matching out 13 This number .
Look for a specific number in the sort array —— The human brain vs Computer round 2
Computer in the last round and human brain PK Defeat in the battle , But it's not very fair , Because the number of arrays is only a few , And computers can store more than that . So we started the second competition . This time we will expand the input
1 2 3 5 7 13 34 67 90 127 308 502 ... 2341245 ... （100 m
The number of searches becomes 2341245.
How about the performance of human brain and computer this time ？
For an ordinary person , Let's assume that 100 Ten thousand numbers are printed in a dictionary , So how does he find out 100 A number in ten thousand ordered arrays ？
At this time, human beings are proud of “ read ten lines at one glance ” The ability to do so is very small , When the number of digits increases , It is difficult to compare a number with the target number at a glance , Even if you really have the ability to do at a glance , stay 100 The number of thousands is very small .
So , Let's compare the numbers from the beginning to the end , Turn page by page , See if there are any numbers on the current page , If not, go to the next page .
Is this idea familiar ？ you 're right , This is the thinking of computers , It's almost the same as the computer code we described in the previous section , Except that people can see more data at a glance .
However , We are comparing the speed of large numbers , And the speed of turning over a dictionary is far less than that of a computer reading it 100 Ten thousand speed , The same is “ Stupid bird ”, The computing power of a computer can accomplish such tasks almost instantaneously .
in other words , In the case of large-scale input , The way of thinking of the human brain “ degeneration ” Like a computer , But defeated by the overwhelming power of computers .
Look for a specific number in the sort array —— The human brain vs Computer round 3
In the second round , The human brain lost to the computer , But it's no doubt that the competition is faster between two stupid birds . Is there a smarter way ？
you 're right , We've learned binary search （Binary Search） The algorithm can be used .
Step one ： There is such a printed book 100 The dictionary of ten thousand numbers is in front of us , We don't know where the numbers are going to be , Let's open the dictionary in half （ It doesn't matter if you don't have to be so precise ）, Look at the first and last numbers on the current page , Is the number we are looking for in this range , If so, we can continue to find this number on the current page .
Step two ： If the first number on the current page is still larger than the number we are looking for , Then we can tear up the second half of the dictionary （ Because the number we're looking for can't be in the second half ）, Continue with the above steps .
Step three ： If the last number on the current page is smaller than the number we are looking for , Then we can tear up the first half of the dictionary （ For the same reason ）, Continue with step one .
In this way, we will say that the dictionary is getting thinner and thinner , In the worst case, we'll tear it to the last page , This page either has this number , Or there's no number , But we promise to follow the above steps and we will not miss any page that may contain this number .
This logic is the same as the binary search principle in computer algorithm , Let's see how the actual algorithm code is implemented
boolean isNumInArray(int num, int[] array, int start, int end) {
if(num < arr[start] || key > arr[end] || start > end){
return false;
}
int middle = (start + end) / 2; // Find a break in half
if(array[middle] > num) {
return isNumInArray(arr, key, start, middle - 1); // Tear off the second half
} else if(array[middle] < num){
return isNumInArray(arr, key, middle + 1, end); // Tear off the first half
}else {
return middle;
}
}
We can see that , Compared with the human way of thinking , Computers don't flip “ One page ”, It only looks at one number , As like as two peas, the other way of thinking is the same . Using this algorithm , Human beings are still slower than computers in the result , But both sides have found the best way , To achieve the greatest improvement in self efficiency .
Look for a specific number in the sort array —— More thinking
So let's look back , Why should I assume that 100 Ten thousand figures are printed on the dictionary ？ Because the dictionary and the computer memory model are very similar .
The computer can directly access the memory through the memory address , This point and turn to a certain page through the page number of the dictionary , This point is approximate .
In computer coding we can know the length of the array , And find the middle number by half , The dictionary has thickness , We can find the middle page number by halving the thickness , This is also similar .
Imagine the same , If 100 Ten thousand numbers are not printed in the dictionary , It's printed on a highway , Whether we can also use the algorithm in the previous section to search for human flesh ？ The answer is no , Because half the way to the road takes a lot of energy , If you use dichotomy to find the comparison round 1 The dumbest way to do this is to use more energy . Because the concept of highway storage , It's not the memory model , It's tape （Tape） Model of , So for a model like this , I believe that whether it's people or computers , We need to adjust the algorithm , To achieve maximum efficiency .
summary
Through the above example , We can see , Computer algorithms are anti human , Because the computer is not a “ normal person ”, It has its own flaws , It also has its own advantages . Most of the time, our algorithm is not intuitive , It's not because our thinking ability is worse than computer , And it's precisely because as human beings we are exposed to too much information at the same time , There are too many things that block our thinking . Then this time , You may as well “ fallen ” Into a “ shortsighted ” and “ Little is known ” The computer , There may be a clearer way of thinking .
This article has been exclusively licensed to script house （ID:jb51net） The official account is issued
