Trong phần trước * Jerry, một tay cựu học việc yêu cầu Alphonse, một tay học việc, viết một chương trình tạo các số nguyên dùng "sieve of Etastosthenes". Jerry, nhận thấy Alphonse ứng dụng trọn bộ thuật toán vào một function "khổng tượng" nên đã yêu cầu Alphonse tách nó ra theo ba khái niệm: khởi động, ứng tạo và chuẩn xuất;... nhưng Alphonse không biết phải bắt đầu từ đâu...
Gã nhìn tôi một lúc, rõ ràng đang đợi tôi làm gì đó. Nhưng rốt cuộc gã thở dài, lắc đầu và tiếp tục. "Ðể mở rộng ba khái niệm rõ ràng hơn, tao muốn mày tách chúng ra thành ba methods riêng biệt. Ðồng thời vứt hết những cái phụ chú không cần thiết và đặt một cái tên khá hơn cho cái class. Mày làm xong những thứ đó rồi phải bảo đảm là mấy cái test vẫn còn chạy được."
Các bạn có thể thấy những điểm tôi đã làm trong mã dẫn 3. Tôi đã đánh dấu những thay đổi bằng chữ đậm, y hệt như Martin Fowler trình bày trong cuốn Refactoring của ông ta. Tôi đổi tên của cái class thành dạng danh từ, vứt hết những phụ chú về chuyện Eratosthenes và tạo ra ba methods từ ba khái niệm trong generatePrimes function.
Tách ra ba functions buộc tôi phải đưa ra một số biến hàm của function thành static fields của cái class. Jerry nói cách này làm rõ những biến hàm nào là local và những biến hàm nào có ảnh hưởng rộng lớn hơn.
Mã dẫn 3:
PrimeGenerator.java, version 2
/**
* This class generates prime numbers up to a user-specified
* maximum. The algorithm used is the Sieve of Eratosthenes.
* Given an array of integers starting at 2: Find the first
* uncrossed integer, and cross out all its multiples. Repeat
* until the first uncrossed integer exceeds the square root of
* the maximum value.
*/
import java.util.*;
public class PrimeGenerator {
private static int s;
private static boolean[] f;
private static int[] primes;
public static int[] generatePrimes(int maxValue) {
if (maxValue < 2)
return new int[0];
else {
initializeSieve(maxValue);
sieve();
loadPrimes();
return primes; // return the primes
}
}
private static void loadPrimes() {{{/b}
int i,j;
// how many primes are there?
int count = 0;
for (i = 0; i < s; i++) {
if (f[i])
count++; // bump count.
}
primes = new int[count];
// move the primes into the result
for (i = 0, j = 0; i < s; i++) {
if (f[i]) // if prime
primes[j++] = i;
}
}
private static void sieve() {{{/b}
int i,j;
for (i = 2; i < Math.sqrt(s) + 1; i++) {
// if i is uncrossed, cross out its multiples.
if (f[i]) {
for (j = 2 * i; j < s; j += i)
f[j] = false; // multiple is not prime
}
}
}
private static void initializeSieve(int maxValue) {{{/b}
// declarations
s = maxValue + 1; // size of array
f = new boolean[s];
// initialize array to true.
for (int i = 0; i < s; i++)
f[i] = true;
// get rid of known non-primes
f[0] = f[1] = false;
}
}
Jerry bảo tôi mã này hơi lộn xộn, nên gã giành lấy bàn đánh và chỉ tôi cách dọn dẹp. . Mã dẫn 4 minh hoạ những gì gã đã làm. Thoạt tiên gã vứt đi cái biến hàm s trong initializeSieve và thay thế nó bằng f.length. Sau đó gã đổi tên của ba functions (theo kiểu) gã cho là có ấn tượng hơn. Cuối cùng gã sắp xếp lại cái "bộ lòng" initializeArrayOfIntegers (từ initializeSieve) để cho dễ đọc hơn một chút. Các cái test vẫn chạy nhưng thường.
Mã dẫn 4:
PrimeGenerator.java, version 3 (partial)
public class PrimeGenerator {
private static boolean[] f;
private static int[] result;
public static int[] generatePrimes(int maxValue) {
if ((maxValue < 2)
return new int[0];
else {
initializeArrayOfIntegers(maxValue);
crossOutMultiples();
putUncrossedIntegersIntoResult();
return result;
}
}
private static void
initializeArrayOfIntegers(int maxValue) {
f = new boolean[an[maxValue + 1];
f[0] = f[1] = false; //neither primes nor multiples.
for (int i = 2; i < f.length; i++)
f[i] = true;
}
Tôi phải công nhận mã này rõ hơn một chút. Trước giờ tôi nghĩ tạo functions có tên sinh động là phí thời giờ , nhưng những chỉnh đổi của gã quả thật làm cho mã nguồn dễ đọc hơn.
Tiếp theo Jerry trỏ vào crossOutMultiples, nói là gã nghĩ cụm if(f[i] == true) có thể làm cho dễ đọc hơn nữa. Tôi nghĩ đến điểm này chừng một phút. Ý định của các cụm này dùng để kiểm tra xem i không bị loại trừ; thế là tôi đổi tên của f thành unCrossed.
Jerry nói mã này được hơn nhưng tôi vẫn chưa hài lòng với nó vì nó dẫn đến khả năng phủ định đôi (double negative) như unCrossed[i] = false. Bởi thế gã đổi tên của dãy số thành dãy isCrossed với chỉ số nhỏ hơn 2. Các cái test vẫn chạy được.
Jerry tách phần lặp bên trong (inner loop) của crossOutMultiples function và gọi nó là crossOutMultipleOf. Gã bảo rằng các cụm tương tự như if (isCrossed[i] == false) dễ nhầm lẫn nên gã tạo ra function có tên notCrossed và thay cụm if thành if (notCrossed(i)). Kết tiếp gã chạy thử mấy cái test lại.
Sau đó Jerry hỏi tôi ý nghĩa của phần số căn đó là gì. Tôi tốn ít thời giờ viết phụ chú giải thích tại sao cần phải lặp lại cho đến phần số căn của chiều dài dãy số. Tôi cố tranh đua với Jerry bằng cách tách phần tính toán thành một function, nơi tôi có thể đưa vào phần phụ giải. Trong khi viết phụ chú tôi nhận ra rằng căn số là phân tố cực đại của số nguyên trong một dãy số. Bởi thế để ứng phó, tôi chọn cách gọi đó (maxValue) cho các biến hàm. Cuối cùng tôi bảo đảm các tests vẫn chạy được. Kết quả của các thay đổi trong mã dẫn 5.
Mã dẫn 5:
PrimeGenerator.java version 4 (partial)
public class PrimeGenerator {
private static boolean[] isCrossed;
private static int[] result;
public static int[] generatePrimes(int maxValue) {
if (maxValue < 2)
return new int[0];
else {
initializeArrayOfIntegers(maxValue);
crossOutMultiples();
putUncrossedIntegersIntoResult();
return result; }
}
private static void
initializeArrayOfIntegers(int maxValue) {
isCrossed = new boolean[maxValue + 1];
for (int i = 2; i < isCrossed.length; i++)
isCrossed[i] = false;
}
private static void crossOutMultiples() {
int maxPrimeFactor = calcMaxPrimeFactor();
for (int i = 2; i <= maxPrimeFactor; i++)
if (notCrossed(i))
crossOutMultiplesOf(i);
}
private static int calcMaxPrimeFactor() {
// We cross out all multiples of primes. Thus, all crossed
// out multiples have p and q for factors. If p > sqrt of the
// size of the array, then q will never be greater than 1.
// Thus p is the largest prime factor in the array, and is
// also the iteration limit.
double maxPrimeFactor = Math.sqrt(isCrossed.length) + 1;
return (int) maxPrimeFactor;
}
private static void crossOutMultiplesOf(int i) {
for (int multiple = 2*i; multiple < isCrossed.length;
multiple += i)
isCrossed[multiple] = true;
}
private static boolean notCrossed(int i) {
return isCrossed[i] == false;
}
Tôi bắt đầu nắm bắt được vấn đề nên liền xét lại method xét lại method putUncrossedIntegersIntoResult. Tôi thấy rằng method này có hai phần. Phần thứ nhất đếm các số nguyên không bị loại trong dãy số, và tạo nên dãy kết quả (bằng chiều dài của dãy số). Phần thứ nhì dời các số nguyên không bị loại vào dãy kết quả này. Bởi thế, như bạn thấy trong mã dẫn 6, tôi tách phần thứ nhất ra để hình thành function cho chính nó và dọp dẹp lặt vặt đôi chút. Các tests vẫn chạy được. Jerry chỉ thoáng gật đầu. Gã có thật sự khoái những điều tôi đã thực hiện không?
Mã dẫn 6:
PrimeGenerator.java, version 5 (partial).
private static void putUncrossedIntegersIntoResult() {
result = new int[numberOfUncrossedIntegers()];
for (int j = 0, i = 2; i < isCrossed.length; i++)
if (notCrossed(i))
result[j++] = i;
}
private static int numberOfUncrossedIntegers() {
int count = 0;
for (int i = 2; i < isCrossed.length; i++)
if (notCrossed(i))
count++;
return count;
}
<đón xem phần kế tiếp>
* Trong nguyên bản là "In the last month's column..." nhưng ở đây tạm dịch thoáng ra là "trong phần trước" cho phù hợp với tinh thần các bài craftsman được post lên diễn đàn (không theo tháng mà theo... tùy hứng của người dịch ;)) ;))
No comments:
Post a Comment