1. Programming Abas notes at the beginning
In THE IT industry, if you don’t know how to program, then toad can only laugh.
Some people think of programming as typing, so they have always been code farmers. Some people recognize programming as COPY, so it has been a porter. We are not engineers, we are only IT porters ~
Programming can be different. It’s a collection of insights and creativity. It requires us to hone our programming skills and basic design principles.
Welcome to reprint, reprint please indicate the source: blog.csdn.net/notbaron/ar…
1, the opening
Is an external sorting problem, as shown in Figure 1:
And indeed, in general what we think about is merge sort.
The amount of memory that can be put into memory at one time is limited because of limited memory. That means more reads and writes to memory and more I/OS.
The author uses a bit representation method. A 10-bit string is used to represent a simple set of non-negative integers with all elements less than 10. Such as {1, 2, 3, 5, 8}
0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0
Left to right, 0,1,2,3,4,5,6,7,8,9. If it is 1, it is in the set, and if it is 0, it is not in the set.
This would have required a number of bytes to represent the number, through a bit to achieve, the space instantly left dozens of times?
So you can use 107 bits, which is about 1.19m long. But there are actually a lot of sparse bits that can be compressed. Pseudo-code implementation is shown in Figure 2:
The three phases are: 1, initialize the bit array, 2, check whether the value exists, and set it to 1. Sort files according to the bit array output.
2. Summary:
It’s really a good book and worth savoring. The subsequent comparison of Toad will be programmed abecas in each chapter to record, according to the need to delete some of the author’s “nonsense”, present the most concise and also the most core part.