当前位置:网站首页>How to think in the way of computer

How to think in the way of computer

2020-11-07 20:19:02 ChaosYang1987

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 :

  1. 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 .
  2. 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 :

  1. 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
  2. adopt LOAD The instruction loads the number corresponding to the memory address into the register (r3)
  3. 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 :

  1. 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 .
  2. 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

版权声明
本文为[ChaosYang1987]所创,转载请带上原文链接,感谢