Android programmer interview:
Android programmer interview will encounter algorithm (part 1 about binary tree that thing) attached Offer situation
Android Programmer Interview Algorithms (Part 2 Breadth-First Search)
Android Programmer Interview algorithms (Part 3 depth-first Search – Backtracking)
Android Programmer interview algorithms (Part 4 Message queue applications)
Algorithms encountered by Android Programmers (Part 5 Dictionary Tree)
Algorithms encountered by Android programmers (Part 6 PriorityQueue)
Algorithms encountered by Android Programmers (Part 7 Topological Sorting)
I haven’t updated it for a long time. Recently, I was very upset about the visa issue, so I didn’t write anything.
Although there is still no good news today, and according to the data of previous years, now I still can’t draw H1b estimate is out of the question, and maybe my silicon Valley dream will be shattered.
But after thinking about it, life must continue, learning can not stop. I’m going to go at the normal pace.
This installment will focus on one of the most common designs in Android apps or wheels: message queues.
I will this time with a simple example to demonstrate the application of this design is the message queue step by step, finally will draw lessons from Java and android source code to the message queue implementation instance for a simplified version of the code, I hope you after read this article in your app development in the future, or the wheel development can use the message queue design to optimize the structure of the code, Make your code more readable.
1. Network Request (Volley)
Most Android developers have used the Volley network request library. The underlying network request is actually made using the HttpUrlConnection class or HttpClient library. Volley encapsulates these base libraries, such as thread control, caching, and callbacks. Here we detail the processing of most network request queues.
One of the most basic and simple designs is to use a thread (not the main thread) that continuously fetches requests from a queue, then throws them from the queue and emits callbacks that are guaranteed to run on the main thread.
Implementation is very simple, here draw on Volley source code design, simplify:
/** A simplified version of the request class, containing the request Url and a Runnable callback **/
class Request{
public String requestUrl;
public Runnable callback;
public Request(String url, Runnable callback)
{
this.requestUrl = url;
this.callback = callback; }}// Message queue
Queue<Request> requestQueue = new LinkedList<Request>();
new Thread( new Runnable(){
public void run(a){
// Start a new thread and use a True while loop to retrieve the first request from the queue and process it
while(true) {if( !requestQueue.isEmpty() ){
Request request = requestQueue.poll();
String response = // Process the REQUEST URL. This step will be a time-consuming operation, leaving out the details
new Handler( Looper.getMainLooper() ).post( request.callback )
}
}
}
}).start();
Copy the codeThis set of code gets us ready. It’s easy to add a request to the dumb wheel.
requestQueue.add( new Request("http.....".new Runnable( -> //do something )) );
Copy the codeIn this way, a simplified version of the wheels of the network request is completed, is very simple, although we did not consider the synchronization, the cache, but actually seen Volley source friend should also be clear, the core of the Volley is such a queue, just not a queue, but two queue (a queue requests for network real One is to try to find the return of the corresponding request from the cache.)
The core of the code is a while loop that keeps popping up requests and processing them.
2. Send delayed messages
Message queues are a kind of game is sending message delay, such as I want to control the current messages sent in three seconds after treatment, that such should be how to write our code, after all, in the case of network requests, we completely don’t care about the news execution order, threw the request into the queue and then began to wait for the callback.
Instead of queues, a linked list can be used as an instance of a queue in Java, sorting each request or message by its execution time.
Without further ado, let’s start with the simplified code.
// The class structure of a Message, in addition to runnable, has a time execTime for the Message to be executed, and two references to the previous and subsequent nodes of the Message in the list.
public class Message{
public long execTime = -1;
public Runnable task;
public Message prev;
public Message next;
public Message(Runnable runnable, long milliSec){
this.task = runnable;
this.execTime = milliSec; }}public class MessageQueue{
// Maintain two dummy heads as the head and tail of our list of messages. The advantage of this is that we do not need to worry about Null heads and tails when inserting new messages, which makes the code simpler and a small trick.
// The execution time of the header is set to -1, and the end is the maximum value of the Long, so that other normal messages are guaranteed to fall between the two points.
private Message head = new Message(null, -1);
private Message tail = new Message(null,Long.MAX_VALUE);
public void run(a){
new Thread( new Runnable(){
public void run(a){
// Use an infinite loop to process messages continuously
while(true) {// If the head is not dummy and the current time is greater than or equal to the execution time of the head node, we can execute the head node task.
if( head.next ! = tail && System.currentTimeMillis()>= head.next.execTime ){// The execution procedure needs to remove the header and remove it from the list structure
Message current = head.next;
Message next = current.next;
current.task.run();
current.next = null;
current.prev =null;
head.next = next;
next.prev = head;
}
}
}
}).start();
}
public void post(Runnable task){
// If it is pure POST, put the message at the end
Message message = new Message( task, System.currentMilliSec() );
Message prev = tail.prev;
prev.next = message;
message.prev = prev;
message.next = tail;
tail.prev = message;
}
public void postDelay(Runnable task, long milliSec){
// If it is a delayed Message, the execution time of the generated Message is the current time + the number of seconds delayed.
Message message = new Message( task, System.currentMilliSec()+milliSec);
// We use a while loop to find the first Message whose execution time is before the newly created Message, which is inserted after it.
Message target = tail;
while(target.execTime>= message.execTime){ target = target.prev; } Message next = target.next; message.prev = target; target.next = message; message.next = next; next.prev = message; }}Copy the codeThe code above has a few key points.
- Messages are stored in linked lists to facilitate insertion of new messages. The time complexity of each insertion at the tail is O(1), and the complexity of each insertion in the middle is O(n). You can imagine what the complexity would be if it were an array.
- We can use two Dummy Nodes as head and tail, so that we do not need to check for null Pointers every time we insert a new Message. If the head is empty, we still need to insert Message
if(head == null){ head = message } else if( tail == null ){head.next = message; tail = message}Such an examination. 3. Each time a delay message is sent, the traversal loop finds the first time that is smaller than the current message to be inserted. Take the picture below for example.
When the current insertion time is 3, it needs to be inserted between 1 and 5, so 1 is the final Target in our code loop above.
So we’ve completed a delayed message wheel! Haha, the calling code is very simple.
MessageQueue queue = new MessageQueue();
// Start the while loop for queue
queue.run();
queue.post( new Runnable(....) )
// Execute after 3 seconds
queue.postDelay( newRunnable(...) .3*1000 )
Copy the codeYou might think that post and postDelay look very familiar, and yes, this is the classic Handler method in Android
In the Android source code, postDelay uses this principle, but Android has an additional processing for retrieving messages. However, for delayed message sending, Android Handler is to process the message linked list in its corresponding Looper, and compare the execution time to achieve delayed message sending.
Finally, think about whether the three-second delay in the code example above is accurate enough to run three seconds after the current time
Of course the answer is NO!
Under this design, we can only guarantee:
If message A is delayed for X seconds and the current time is Y, the system guarantees that A will not be executed before X+Y. This makes sense, because if you use queues to execute code, you never know what the execution time of the previous Message is, and if the previous Message is unusually long… When the current Message is executed, it must be behind its own execTime. But it’s acceptable.
If we want each Message to execute strictly at its designed time, we need an Alarm, similar to the design of an Alarm clock. And if you’re interested, you can think about how to do that with a very basic data structure.
3. Implementation of thread pool
When it comes to thread pools, I’ve had a lot of confusion. Many articles on the web will be titled “The most complete analysis of thread pools,” or “The most detailed Java thread pool principle ever,” but they will mainly focus on how to operate the Java thread pool API.
For a qualified Java developer, if you don’t know how to check the API, you need to write an article explaining how to use the API. I’ve been asking myself why people aren’t interested in source code…
In this section I’ll show you the thread pool implementation using a simple version of the code.
In fact, the implementation of Thread pool is very simple, using a queue of several threads on the line.
public class ThreadPool{
// Use a Set or other data structure to store the created thread in order to obtain the handle of the thread later and perform other operations.
Set<WorkerThread> set = null;
private Queue<Runnable> queue;
// Initialize the thread pool, create the inner class WorkerThread and start it
public ThreadPool(int size){
for( int i = 0; i < size ; i++ ){ WorkerThread t =new WorkerThread();
t.start();
set.add( t );
}
queue = new LinkedList<Runnable>();
}
//submit a runnable to the thread pool
public void submit(Runnable runnable){
synchronized(queue){ queue.add(runnable); }}//WorkerThread executes a Runnable queue in an endless loop.
public class WorkerThread extends Thread{
@Override
public void run(a) {
super.run();
while(true) {synchronized (queue){
Runnable current = queue.poll();
current.run();
}
}
}
}
}
Copy the codeThus, a simple version of the thread pool is complete… Use a set of threads to continuously fetch Runnable execution from the Runnable queue… It looks completely untechnical. But this is the rationale behind Java’s thread pool. You can take a look at the source code. There are a lot of details I haven’t written down, such as how to shutdown the thread pool, or how to handle exceptions for workerthreads inside the thread pool. How to set the maximum number of threads and so on.
Note the few points, is to use synchronized on the concurrent part of the code to do a good synchronization.
Simple calling code
ThreadPool pool = new ThreadPool(5);
pool.submit(newRunnable(...) )Copy the codeA beautiful dividing line
Afterword.
That’s it. The above three examples are the ones most Android developers will come across, and if you have a little interest and patience you can see how they work, using the simplest data structures and the most “naive” designs.
Finally, I want to say that I hope that every Android developer will have a question in their mind, for example, Thread pool, java-based Thread class, how to implement a Thread pool, if you can ask yourself every time you use these apis, why, keep an open mind to ask questions, these things can be learned. May you all have and maintain this enthusiasm.
I also need to remind myself that whether I can go to Silicon Valley or not, I should always have this passion and never slack off for a moment. If my passion was crushed because I couldn’t go to Silicon Valley, my persistence was too fragile.