Let’s talk about why I wrote this first. This was a tragic and terrible murder caused by an interview at Alibaba. When I went to the interview, I went to Alibaba’s designated interview city at 11 o’clock the day before the interview, and I found a hotel and stayed at around 1 o’clock. In addition, I didn’t sleep well at night, which directly led to the poor results of the interview the next day (for Those big shrimps who are looking for a job should not say a tragedy to the shrimps. It is still very important to prepare in advance). The interview lasted for about an hour (when I returned from the interview, I was almost asleep when I walked, sad!!) When the interview was about to end, the interviewer asked me the question about the Fibonacci sequence. At that time, my mind was completely confused and I only knew that I had to set three variables or initialize them with List. When I wrote to the for loop, my mind was simply sluggish. It can't be muddy anymore, and I haven't written it out. In the end, I can only write the following first method under the step-by-step induction of the interviewer. It's not appropriate; from now on, Alibaba just applies the whole thing in a rough way. The framework has been built, it is a golden period for reform and gold mining (you can go quickly if you have the ability). After all, 99% of the data in Alibaba's hands are important data, and 99% of the data that mainly promotes search for giants like Baidu are Compared with garbage, for data analysis, Alibaba can analyze the diverse user detailed data that it has mastered, and can better locate users' tastes and needs, providing better for accurate push and accurate advertising push. Serve. If Tencent’s future dream is to be the water, electricity and gas in users’ lives, then Alibaba’s possible future dream is the user’s food, clothing, housing and transportation, and water, electricity and gas collection, etc. O(∩_∩)O~ Let’s turn to the topic.
For excellent algorithm designers, there are only two things to care about on the basis of the implementation of the program function body: one is the time complexity of the design algorithm, and the other is the space complexity (to put it bluntly, it is the time and memory used to execute a program and the amount of memory occupied by it. Space); Based on different application scenarios, generally intelligent algorithm designers will seek a balance point in two relatively contradictory resources, such as systems with high real-time requirements, generally exchange space resources for Time or commonly used objects will generally reside in memory to improve response time (caching technology and most of the most popular NoSQL databases are used). For embedded systems with relatively valuable memory resources, time will generally be used for embedded systems. delay in exchange for time.
Let’s talk about the three implementations of the Febonasi series. How to truly design an excellent algorithm that truly conforms to practical application scenarios
First, let’s talk about the Febonasi Sequence:
From a textual point of view, the Fibonacci sequence starts with 0 and 1, and the subsequent Fibonacci coefficient is added by the previous two numbers, and the sequence form is as follows:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946，………………
In mathematics, it is defined by recursive methods:
F_0=0
F_1=1
F_n = F_{n-1}+ F_{n-2}
Implement the requirement: Enter the serial number n and return to get the corresponding Febonacci number
Program implementation 1 - function self-iteration
The code copy is as follows:
/**
* Function self-iteration
* @Title: fnType1
* @Description: TODO
* @param @param n
* @param @return
* @return int
* @throws Exception
*/
public int fnType1(int n)throws Exception{
if(n==0){
return 0;
}else if(n==1||n==2){
return 1;
}else if(n>2){
int temp=fnType1(n-1)+fnType1(n-2);
if(temp<0){
throw new Exception("Invalid value for int type, too large");
}else{
return temp;
}
}else{
throw new Exception("IllegalArgument value for n,please enter n>=0 ");
}
}
Disadvantages of this method: a large number of iterations continuously consume stack space (those who engage in web development, debugging and maintenance should know the value of server stack resources. If a large number of concurrent call iterations cause the server stack resources to be recycled for a long time, resulting in the web server crash). The efficiency is low, the function is relatively autistic (excellent interfaces should capture the possible error information of the input and output, and provide clear processing results), and errors are prone to occur and debugging is difficult. It is generally not recommended to use this in practical applications. In this way, the number of iterations cannot exceed 3 times when used;
Program implementation 2 - time to space
The code copy is as follows:
/**
* Time to change space
* @Title: fnType2
* @Description: TODO
* @param @param n
* @param @return
* @return int (n<0 return -1,beyond max int size return -2)
* @throws
*/
public int fnType2(int n){
int result=-1;
int temp1=0;
int temp2=1;
for(int index=0;index<=n;index++){
if(index==0){
result=temp1;
}else if(index==1){
result=temp2;
}else{
result=temp1+temp2;
if(result<0){
result=-2;
break;
}
temp1=temp2;
temp2=result;
}
}
return result;
}
This method is mainly used in: Scenario 1: For scenarios where objects or variables are used less often and will not be used again after use once; Scenario 2: For embedded systems with scarce memory resources, the real-time requirements are not too high. This method is often used in design;
Program Implementation 3 - Space for Time
The code copy is as follows:
private static List<Integer> fnData=new ArrayList<Integer>();
private static final int maxSize=50000;
/**
* Initializer
* @Title: setFnData
* @Description: TODO
* @param
* @return void
* @throws
*/
private static void setFnData(){
int result=-1;
int temp1=0;
int temp2=1;
for(int index=0;index<=maxSize;index++){
if(index==0){
result=temp1;
}else if(index==1){
result=temp2;
}else{
result=temp1+temp2;
if(result<0){
result=-2;
break;
}
temp1=temp2;
temp2=result;
}
fnData.add(result);
}
}
/**
* External interface
* @Title: getFnData
* @Description: TODO
* @param @param n
* @param @return
* @return int <span style="font-family: sans-serif;">(n beyond fnData.size() and n<0 return -1)</span>
* @throws
*/
public int getFnData(int n){
if(fnData.size()==0){
setFnData();
}
if(fnData.size()>n&&n>=0){
return fnData.get(n);
}else{
return -1;
}
}
This method is generally used in scenarios where objects or variables exist or are frequently called throughout the entire life cycle of the program, such as calling external WebService interface, abstraction persistence layer, commonly used configuration file parameter loading, etc.
Test cases:
The code copy is as follows:
package com.dbc.yangg.swing.test;
import java.util.ArrayList;
import java.util.List;
/**
* Enter the sequence number n and return to get the corresponding Febonacci number
* @ClassName: Init
* @Description: TODO
* @author [email protected]
* @date January 10, 2014 at 7:52:13 pm
*
*/
public class Init {
/**
* Function self-iteration
* @Title: fnType1
* @Description: TODO
* @param @param n
* @param @return
* @return int
* @throws Exception
*/
public int fnType1(int n)throws Exception{
if(n==0){
return 0;
}else if(n==1||n==2){
return 1;
}else if(n>2){
int temp=fnType1(n-1)+fnType1(n-2);
if(temp<0){
throw new Exception("Invalid value for int type, too large");
}else{
return temp;
}
}else{
throw new Exception("IllegalArgument value for n,please enter n>=0 ");
}
}
/**
* Time to change space
* @Title: fnType2
* @Description: TODO
* @param @param n
* @param @return
* @return int (n<0 return -1,beyond max int size return -2)
* @throws
*/
public int fnType2(int n){
int result=-1;
int temp1=0;
int temp2=1;
for(int index=0;index<=n;index++){
if(index==0){
result=temp1;
}else if(index==1){
result=temp2;
}else{
result=temp1+temp2;
if(result<0){
result=-2;
break;
}
temp1=temp2;
temp2=result;
}
}
return result;
}
private static List<Integer> fnData=new ArrayList<Integer>();
private static final int maxSize=50000;
/**
* Space to change time
* @Title: setFnData
* @Description: TODO
* @param
* @return void
* @throws
*/
private static void setFnData(){
int result=-1;
int temp1=0;
int temp2=1;
for(int index=0;index<=maxSize;index++){
if(index==0){
result=temp1;
}else if(index==1){
result=temp2;
}else{
result=temp1+temp2;
if(result<0){
result=-2;
break;
}
temp1=temp2;
temp2=result;
}
fnData.add(result);
}
}
/**
*
* @Title: getFnData
* @Description: TODO
* @param @param n
* @param @return
* @return int (n beyond fnData.size() and n<0 return -1)
* @throws
*/
public int getFnData(int n){
if(fnData.size()==0){
setFnData();
}
if(fnData.size()>n&&n>=0){
return fnData.get(n);
}else{
return -1;
}
}
/**
*
* @Title: main
* @Description: TODO
* @param @param argv
* @return void
* @throws
*/
public static void main(String[] argv){
Init init=new Init();
int n=46;
try {
System.out.println("Type1="+init.fnType1(n));
} catch (Exception e) {
// TODO Auto-generated catch block
System.out.println(e.getMessage());
}
System.out.println("Type2="+init.fnType2(n));
System.out.println("Type3="+init.getFnData(n));
}
}
Output result:
The code copy is as follows:
Type1=1836311903
Type2=1836311903
Type3=1836311903
When designing algorithms, do not blindly follow concepts. Concepts are dead and people live (in this era when crazy man is needed, having ideas is more advantageous than following rules). Only by combining specific application scenarios can excellent algorithms and structure.
Let me complain: I personally believe that excellent data structure design can simplify the complexity of algorithm design and improve code readability, program scalability and execution efficiency;
Let me complain again: three principles should be followed when doing demand analysis: 1. Analysis from the user's perspective and way of thinking; 2. What users say is not necessarily what they really want; 3. What users say is not necessarily right . The principles of program development are: actively improve one's own taste, and analyze functions from the user's usage perspective and usage scenarios; for example, when you are doing background interface development, your user is the interface caller, you should consider what the interface function is and what situation the user is in The following will be called, what exceptions may be caused by passing parameters, what exceptions may occur in your interface implementation and capture possible exceptions, clear output, good function autism; if you are in the foreground, then you On the basis of ensuring business implementation, you should design the UI as a user in terms of user usage habits and other aspects. It’s very interesting, right? If you have too many requirements and developments, you will naturally understand O(∩_∩)O~.