Program Optimization Miscellaneous - Application of the Optimal Binary Tree in Procedure
(Author: mikespook | Date: 2003-4-13 | Views: 180)
Keywords: program, optimization, hafman, the best two fork, first, I want to discuss a very simple question with everyone: Classification. Suppose there is 100 items here. There are 20 items that belong to Class A; 10 Class B; 45 Class C; 15 D 15; 10 E class. Now ask a program to classify this 100 items. what! Is this question not very simple? You should also write your eyes. Here I use the pseudo C language to write this program. First agreed: x [0] ~ x [99] is the 100 items. "IN" operation determines if the item belongs to this class. "PUT" operation is to place items in this classification. Procedure: 10 for (i = 0; i <100; i ) 20 {30 IF (x [i] in a) 40 x [i] PUT A; 50 else60 IF (x [i] in b) 70 x [i ] PUT B; 80 ELSE90 IF (x [i] in c) 100 x [i] PUT C; 110 else120 IF (x [i] in d) 130 x [i] PUT D; 140 else150 x [i] PUT E 160} "Ah! How beautiful procedure." Indeed, this code is very nice from an aspect. Very work. But this is the best? Let's calculate it. No matter how "X [i] Put X;" this sentence is sure to perform 100 times, because one item must be put into a classification. And can only be placed once. Then the changes can be compared. First look at the following, a tree type structure of the above program: We can easily calculate this structure when comparing, you need to perform 275 comparisons. So how can you reduce the number of comparisons? In fact, this is a problem with weight. There are 20 items that belong to Class A; 10 Class B; 45 Class C; 15 D. Type C. Then we don't prevent A value of 0.2, B weight is 0.1, and the weight of C is 0.45, and the weight value of D is 0.15, and the weight value is 0.1. Then, according to the concept of the best binary tree, the depth of weight should be minimized (see the data structure "published by Tsinghua University, regarding the part of Hafman coding). According to this principle, we should adjust B, E down, and C is adjusted upward. So the following new structure: According to this structure, you will try it again. The number of comparisons was reduced to 210 times. Is it very interesting? 10 for (i = 0; i <100; i ) 20 {30 IF (x [i] IN C) 40 x [i] PUT C; 50 else60 IF (x [i] in a) 70 x [i] PUT A; 80 else90 IF (x [i] in d) 100 x [i] PUT D; 110 else120 IF (x [i] IN b) 130 x [i] PUT B; 140 else150 x [i] PUT E; 160 } Why is this so? I only said how to do it in front, didn't say this. Below I have a simple analysis with everyone. First, look at the difference between these two programs. The only difference between the first program and the second program is the order of judgment. The order of the first program judgment is A, B, C, D, E. The order of judgment of the second program is C, A, D, B, E. Strange order is not? In fact, it is not surprising. If you write the weight when you are arranged in the second order, you will find the mystery: C | a | d | b | E0.45 | 0.2 | 0.15 | 0.1 | 0.1 Yes, Its weight is from large to small. To illustrate more thorough, the process of running the program is then analyzed. The procedure of the line 30 is always to run 100 times. Whether the following procedures are executed by the results of the previous program conditions.
