Bổ sung Think Python: bảng số, histogram

Bài này trình bày những nội dung rải rác trong các chương của cuốn sách How to think like a computer scientist mà không có trong cuốn Think Python. Dĩ nhiên, nội dung bản dịch này cũng được phát hành theo Giấy phép tài liệu tự do GNU.

Bài post này gồm hai phần. Trước hết, ta áp dụng phép lặp để lập bảng tính nhân. Phần thứ hai là phát sinh một loạt số ngẫu nhiên rồi phân chia vào các nhóm.

Trở về Mục lục cuốn sách

Bảng số liệu

Một trong những công việc thích hợp với dùng vòng lặp, đó là phát sinh ra bảng số liệu. Trước khi máy tính trở nên phổ biến, mọi người đã phải tính tay các phép logarit, sin, cosin, và những hàm toán học khác. Để đơn giản hóa việc này, sách toán thường in kèm những bảng dài liệt kê giá trị các hàm nói trên. Việc tạo ra các bảng như vậy rất chậm và nhàm chán, và dễ mắc phải nhiều lỗi.

Khi máy tính xuất hiện, đã có những phản ứng ban đầu kiểu như: “Điều này thật tuyệt! Giờ ta có thể dùng máy tính để tạo ra các bảng, vì vậy sẽ không có lỗi.” Điều này trở nên (gần như là) sự thật nhưng vẫn chứa đựng tầm nhìn hạn hẹp. Không lâu sau đó, máy tính và máy bỏ túi đã xuất hiện tràn lan và bảng số trở nên lỗi thời.

Ừ, gần như vậy. Có những phép tính mà máy tính lấy con số từ bảng để có giá trị gần đúng, rồi thực hiện tính toán nhằm cải thiện kết quả gần đúng này. Ở trường hợp khác, có những lỗi nằm ngay ở bảng số, được biết đến nhiều nhất là bảng mà máy Intel Pentium đã dùng để thực hiện phép chia với số có dấu phẩy động.

Mặc dù bảng loga không còn hữu dụng như xưa, song nó vẫn dùng được làm ví dụ về tính lặp. Chương trình sau in ra một dãy các số ở cột bên trái cùng với giá trị logarit của chúng ở cột phải:

x = 1.0
 while x < 10.0:
     print x, '\t', math.log(x)
    x = x + 1.0

Chuỗi '\t' biểu diễn một kí tự tab.

Vì các kí tự và chuỗi được xuất hiện trên màn hình, có một con trỏ tàng hình dùng để theo dõi vị trí xuất hiện của kí tự tiếp theo. Sau mỗi lệnh print, thông thường con trỏ sẽ nhảy đến đầu dòng kế tiếp.

Kí tự tab đẩy con trỏ về bên phải cho đến khi nó đụng phải một điểm dừng (tab stop). Kí tự này rất có ích để tạo nên các cột chữ, như kết quả đầu ra của chương trình nói trên:

 1.0     0.0
 2.0     0.69314718056
 3.0     1.09861228867
 4.0     1.38629436112
 5.0     1.60943791243
 6.0     1.79175946923
 7.0     1.94591014906
 8.0     2.07944154168
 9.0     2.19722457734

Nếu như các giá trị này có vẻ lạ, hãy nhớ rằng hàm log tính theo cơ số e. Vì các số mũ của 2 rất quan trọng đối với khoa học máy tính, ta thường phải tìm logarit với cơ số 2. Để làm điều này, có thể dùng công thức sau:

log2 x = loge x / loge 2

Hãy đổi câu lệnh in kết quả thành

print x, '\t',  math.log(x)/math.log(2.0)

và ta được:

 1.0     0.0
 2.0     1.0
 3.0     1.58496250072
 4.0     2.0
 5.0     2.32192809489
 6.0     2.58496250072
 7.0     2.80735492206
 8.0     3.0
 9.0     3.16992500144

Có thể thấy rằng 1, 2, 4, và 8 là các lũy thừa của 2 vì các giá trị logarit cơ số 2 của chúng đều là những số nguyên. Nếu muốn tìm logarit của những lũy thừa khác của 2, ta có thể sửa chương trình trên thành:

x = 1.0
while x < 100.0:
    print x, '\t', math.log(x)/math.log(2.0)
    x = x * 2.0

Bây giờ thay vì cộng thêm một số với x trong mỗi vòng lặp (điều này cho ra dãy cấp số cộng), ta đem nhân một giá trị với x (thu được cấp số nhân). Kết quả là:

 1.0     0.0
 2.0     1.0
 4.0     2.0
 8.0     3.0
 16.0    4.0
 32.0    5.0
 64.0    6.0

Nhờ các kí tự tab giữa hai cột mà vị trí của cột thứ hai không phụ thuộc vào việc cột thứ nhất có bao nhiêu chữ số.

Bảng logarit có thể không còn có ích nữa, nhưng với nhà khoa học máy tính, việc nhớ được các lũy thừa của hai nhất thiết có ích!

Bài tập: Hãy sửa đổi chương trình nói trên để nó tính ra các lũy thừa của 2 cho đến 65536 (chính là 216). In kết quả và ghi nhớ chúng. 

Dấu gạch ngược ở '\t' cho biết đây điểm khởi đầu của một chuỗi thoát. Có thể dùng chuỗi thoát để biểu diễn những kí tự tàng hình như tab và xuống dòng (newline). Chuỗi \n biểu diễn dấu xuống dòng.

Một chuỗi thoát có thể xuất hiện bất cứ đâu trong một chuỗi. Ở ví dụ trên, trong chuỗi chỉ có chuỗi thoát.

Theo bạn, có thể biểu diễn dấu gạch ngược trong chuỗi như thế nào?

Bài tập: hãy viết một chuỗi mà nó 

cho ra

kết quả

này.

Bảng hai chiều

Trong một bảng hai chiều, bạn đọc giá trị ở điểm giao cắt giữa một hàng với một cột. Bảng cửu chương là một ví dụ điển hình. Giả sử bạn muốn in ra một bảng tính nhân với các giá trị từ 1 đến 6.

Một cách bắt đầu ổn thỏa là viết một vòng lặp để in ra các bội số của 2 trên cùng một dòng:

i = 1
while i <= 6:
     print 2*i, '   ',
    i = i + 1 
print

Dòng đầu tiên khởi tạo một biến có tên là i; nó đóng vai trò một biến đếm hoặc biến vòng lặp. Khi vòng lặp được thực thi, giá trị của i tăng từ 1 lên 6. Khi i bằng 7, vòng lặp kết thúc. Mỗi lần lặp, chương trình sẽ in ra giá trị của 2*i, theo sau là ba dấu cách.

Một lần nữa, dấu phẩy trong câu lệnh print ngăn không cho xuống dòng. Sau khi vòng lặp kết thúc, lệnh print thứ hai bắt đầu một dòng mới.

Kết quả của chương trình là:

2      4      6      8      10     12

Mọi việc đến giờ tiến triển tốt. Bước tiếp theo là bao bọc và khái quát hóa.

Bao bọc và khái quát hóa

Bao bọc là quá trình đặt một đoạn mã lệnh vào trong một hàm; việc này cho phép ta tận dụng được những ưu điểm của hàm.

Khái quát hóa nghĩa là chọn lấy một điều cụ thể, như công việc in ra các bội số của 2, rồi làm cho nó trở thành khái quát hơn, chẳng hạn như in ra các bội số của một số nguyên bất kì.

Hàm sau đây bao bọc đoạn mã lệnh nói trên rồi khái quát hóa nó để in ra các bội số của n:

def printMultiples(n):
i = 1
    while i <= 6:
        print n*i, '\t',
i = i + 1
    print

Để bao bọc, ta chỉ cần viết thêm dòng thứ nhất, tức là khai báo tên của hàm và danh sách các tham số. Để khái quát hóa, ta chỉ cần thay thế giá trị 2 bởi tham số n.

Nếu ta gọi hàm này với đối số bằng 2, ta sẽ nhận được kết quả giống như trước. Với đối số bằng 3, kết quả sẽ là:

3      6      9      12     15     18

Với đối số bằng 4, kết quả là:

4      8      12     16     20     24

Bây giờ có thể bạn đã đoán được cách in một bảng tính nhân     bằng cách gọi printMultiples lặp lại với những đối số khác nhau. Thực ra, ta có thể dùng một vòng lặp khác:

i = 1
 while i <= 6:
    printMultiples(i)
    i = i + 1

Lưu ý sự giống nhau của vòng lặp này với vòng lặp bên trong printMultiples. Tất cả những gì ta đã làm chỉ là việc thay lệnh print bằng một lời gọi hàm.

Kết quả của chương trình này là một bảng tính nhân:

1      2      3      4      5      6
2      4      6      8      10     12
3      6      9      12     15     18
4      8      12     16     20     24
5      10     15     20     25     30
6      12     18     24     30     36

Thực hành thêm về bao bọc

Để biểu diễn tiếp kĩ thuật bao bọc, ta hãy lấy đoạn mã lệnh ở cuối mục trước rồi bọc nó vào trong một hàm:

def printMultTable():
    i = 1
    while i <= 6:
        printMultiples(i)
        i = i + 1

Quá tình này là một kế hoạch phát triển thường gặp. Ta phát triển mã lệnh bằng cách viết riêng những dòng lệnh bên ngoài hàm, hoặc gõ thẳng vào trình thông dịch. Khi mã lệnh này thực hiện được, ta lấy lại nó rồi bọc vào một hàm.

Kế hoạch phát triển như vậy đặc biệt có ích nếu bạn mới bắt đầu và không biết cách chia chương trình thành các hàm. Phương pháp này giúp bạn thiết kế trong khi lập trình.

Biến địa phương

Có thể bạn tự hỏi bằng cách nào mà ta dùng được cùng một biếni, cả trong printMultiples lẫn printMultTable. Chẳng phải nó sẽ gây rắc rối khi một trong hai hàm thay đổi giá trị của biến sao?

Câu trả là không, vì i trong printMultiples và i trong printMultTable không phải cùng một biến.

Những biến được tạo ra bên trong phần định nghĩa hàm đều là biến địa phương; bạn không thể truy cập biến địa phương từ ngoài hàm “chủ” của nó. Điều này có nghĩa là bạn có thể tùy ý đặt nhiều biến cùng tên, miễn là chúng không phải trong cùng một hàm.

Biểu đồ ngăn xếp cho chương trình này thể hiện hai biến có tên i không phải là một. Chúng có thể chỉ đến những giá trị khác nhau, và việc thay đổi biến này không ảnh hưởng tới biến kia.

Giá trị của i trong printMultTable chạy từ 1 đến 6. Ở biểu đồ này thì nó bằng 3. Lần lặp tiếp theo nó sẽ bằng 4. Mỗi lần lặp, printMultTable gọi printMultiples với đối số là giá trị hiện thời của i. Giá trị đó được gán cho tham số n.

Bên trong printMultiples, giá trị của i chạy từ 1 đến 6. Ở biểu đồ này thì nó bằng 2. Việc thay đổi biến này không có ảnh hưởng gì đến giá trị của i trong printMultTable.

Việc có nhiều biến cùng tên là hoàn toàn hợp lệ và cũng thường gặp. Đặc biệt, những cái tên như i và j đều dược dùng thường xuyên làm biến lặp. Nếu vì lí do đã dùng chúng ở chỗ khác mà bạn tránh dùng lại chúng trong phạm vi một hàm, thì có lẽ bạn sẽ làm cho chương trình trở nên khó đọc hơn.

Thực hành thêm về khái quát hóa

Xét một ví dụ khác về khái quát hóa. Hãy hình dung rằng bạn  muốn có một chương trình để in ra bảng tính nhân với kích thước bất kì, chứ không chỉ 6 × 6. Bạn có thể thêm một tham số vào printMultTable:

def printMultTable(high):
    i = 1
    while i <= high:
        printMultiples(i)
        i = i + 1

Chúng ta đã thay giá trị 6 bởi tham số high. Nếu ta gọi printMultTable với đối số 7, nó hiển thị:

1      2      3      4      5      6
2      4      6      8      10     12
3      6      9      12     15     18
4      8      12     16     20     24
5      10     15     20     25     30
6      12     18     24     30     36
7      14     21     28     35     42

Thế này tạm được, nhưng có lẽ ta muốn nhận được một bảng hình vuông hơn     số cột và số hàng phải bằng nhau. Để làm điều này, ta thêm một tham số nữa vào printMultiples để cụ thể hóa xem bảng có bao nhiêu cột.

Để thêm phần khó chịu, ta gọi tham số này là high, nhằm cho thấy các hàm khác nhau hoàn toàn có thể chứa những tham biến có cùng tên (cũng như các biến địa phương). Sau đây là toàn bộ chương trình:

def printMultiples(n, high):
    i = 1
    while i <= high:
        print n*i, '\t',
        i = i + 1
        print
def printMultTable(high):
    i = 1
    while i <= high:
        printMultiples(i, high)
        i = i + 1

Lưu ý rằng khi thêm một tham số mới, ta phải sửa lại dòng đầu tiên của hàm (tiêu đề hàm), đồng thời ta cũng phải sửa chỗ hàm được gọi trong  printMultTable.

Đúng như dự kiến, chương trình này phát sinh ra bảng vuông 7 × 7:

1      2      3      4      5      6      7
2      4      6      8      10     12     14
3      6      9      12     15     18     21
4      8      12     16     20     24     28
5      10     15     20     25     30     35
6      12     18     24     30     36     42
7      14     21     28     35     42     49

Khi bạn khái quát quá một hàm theo cách thích hợp, thường bạn sẽ thu được chương trình với những tính năng mà bạn chưa lường trước. Chẳng hạn, có thể bạn nhận thấy rằng, vì ab = ba, nên tất cả những con số trong bảng đều xuất hiện lặp hai lần. Lẽ ra bạn có thể tiết kiệm mực bằng cách chỉ  in ra nửa bảng thôi. Để làm điều này, chỉ cần thay đổi một dòng lệnh trong printMultTable. Hãy sửa lệnh

    printMultiples(i, high)

thành

    printMultiples(i, i)

và bạn thu được

1
2      4
3      6      9
4      8      12     16
5      10     15     20     25
6      12     18     24     30     36
7      14     21     28     35     42     49

Bài tập: dõi theo trình tự thực hiện của phiên bản printMultTable này rồi hình dung cách hoạt động của nó.


Lập một danh sách các số ngẫu nhiên

Bước đầu tiên là phát sinh một danh sách các giá trị số. randomList nhận một đối số nguyên và trả lại một danh sách các số ngẫu nhiên với chiều dài cho trước đó. Danh sách này bắt đầu với một dãy gồm n số không. Mỗi lần lặp, nó thay thế một phần tử bởi một số ngẫu nhiên. Giá trị được trả lại là một tham chiếu đến toàn bộ danh sách:

def randomList(n): 
  s = [0] * n 
  for i in range(n): 
    s[i] = random.random() 
  return s 

Ta sẽ kiểm tra hàm này bằng một danh sách gồm 8 phân tử. Để phục vụ việc gỡ lỗi, nên bắt đầu thực hiện công việc với khối lượng nhỏ.

>>> randomList(8) 
0.15156642489 
0.498048560109 
0.810894847068 
0.360371157682 
0.275119183077 
0.328578797631 
0.759199803101 
0.800367163582

Các số phát sinh bởi random được dự kiến là tuân theo phân phối đều; nghĩa là từng giá trị đều có khả năng xuất hiện ngang bằng nhau.

Nếu ta chia khoảng giá trị khả dĩ thành những “ngăn” có chiều rộng đều nhau, rồi đếm số lần mà một giá trị ngẫu nhiên rơi vào từng ngăn, thì chắc hẳn sẽ thu được các số đếm gần bằng nhau.

Ta có thể kiểm tra lí thuyết này bằng cách viết chương trình để chia khoảng thành các ngăn rồi đếm số giá trị trong từng ngăn.

Đếm số

Một cách làm hợp lí để giải quyết bài toán kiểu như thế này là chia bài toán thành những bài toán nhỏ rồi tìm kiếm những bài toán nhỏ nào hợp với một dạng mẫu tính toán mà ta đã từng gặp.

Trong trường hợp này, ta muốn duyệt một dãy số và tính số lần mà một giá trị rơi vào một khoảng cho trước. Điều này nghe rất quen. Trước đây ta đã từng viết một chương trình để duyệt một chuỗi rồi đếm số lần xuất hiện của một chữ cái cho trước.

Vì vậy, ta có thể tiến hành sao chép đoạn chương trình cũ rồi sửa đổi cho phù hợp bài toán hiện giờ. Chương trình gốc ban đầu là:

count = 0 
for char in fruit: 
  if char == 'a': 
    count = count + 1 
print count 

Bước đầu tiên là thay thế fruit bởi t và char bởi num. Làm vậy sẽ không thay đổi chương trình, mà chỉ khiến nó dễ đọc hơn.

Bước thứ hai là sửa lại phép kiểm tra. Ta không quan tâm đến việc tìm kiếm chữ cái. Ta muốn xem rằng liệu num có nằm giữa hai giá trị low và high cho trước hay không.

def inBucket(t, low, high): 
  count = 0 
  for num in t: 
    if low < num < high: 
      count = count + 1 
  return count 

Bằng cách sao chép và sửa đổi một chương trình có sẵn, ta đã có thể viest hàm này nhanh chóng và tiết kiệm được nhiều thời gian gỡ lỗi. Kế hoạch phát triển này có tên gọi là khớp mẫu. Nếu bạn bắt gặp một bài toán nào mà bản thân đã từng giải rồi, thì hãy tận dụng lại lời giải.

Nhiều ngăn

Khi số các ngăn tăng lên, inBucket trở nên cồng kềnh. Với hai ngăn, tình hình còn chưa tệ:

low = inBucket(a, 0.0, 0.5) 
high = inBucket(a, 0.5, 1) 

Nhưng với bốn ngăn thì đã hơi phiền:

bucket1 = inBucket(a, 0.0, 0.25) 
bucket2 = inBucket(a, 0.25, 0.5) 
bucket3 = inBucket(a, 0.5, 0.75) 
bucket4 = inBucket(a, 0.75, 1.0) 

Ở đây có hai vấn đề. Một là, ta phải tự đặt những tên biến mới cho từng kết quả. Hai là, phải tự tính khoảng cho từng ngăn.

Ta sẽ giải quyết vấn đề thứ hai trước. Nếu như số các ngăn là numBuckets, thì bề rộng của từng ngăn sẽ là 1.0 / numBuckets.

Ta sẽ dùng một vòng lặp để tính ra khoảng cho từng ngăn. Biến vòng lặp, i, chạy từ 0 tới numBuckets-1:

bucketWidth = 1.0 / numBuckets 
for i in range(numBuckets): 
  low = i * bucketWidth 
  high = low + bucketWidth 
  print low, "to", high 

Để tính giới hạn dưới của từng ngăn, ta đem nhân biến lặp với bề rộng ngăn. Giới hạn trên thì hơn giới hạn dưới là bucketWidth.

Với numBuckets = 8, kết quả là:

0.0 to 0.125 
0.125 to 0.25 
0.25 to 0.375 
0.375 to 0.5 
0.5 to 0.625 
0.625 to 0.75 
0.75 to 0.875 
0.875 to 1.0 

Bạn có thể kiểm tra để khẳng định rằng các ngăn đều có bề rộng bằng nhau, và chúng không gối lên nhau, đồng thời các ngăn phải phủ kín phạm vi từ 0.0 tới 1.0.

Bây giờ quay trở lại vấn đề thứ nhất. Ta cần một cách để lưu tám số nguyên, bằng biến vòng lặp để chỉ định từng số một. Đến giờ thì bạn có lẽ bạn đã nghĩ, “Danh sách!”

Chúng ta sẽ tạo ra danh sách các ngăn bên ngoài vòng lặp, bởi ta chỉ muốn làm 1 lần. Bên trong vòng lặp, ta sẽ gọi inBucket liên tục rồi cập nhật phần tử thứ của danh sách:

numBuckets = 8 
buckets = [0] * numBuckets 
bucketWidth = 1.0 / numBuckets 
for i in range(numBuckets): 
  low = i * bucketWidth 
  high = low + bucketWidth 
  buckets[i] = inBucket(t, low, high) 
print buckets 

Với một danh sách 1000 giá trị, thì mã lệnh này sẽ tạo ra danh sách các ngăn:

[138, 124, 128, 118, 130, 117, 114, 131]

Những con số này rất sát với 125, vốn là giá trị dự kiến. Ít nhất là chúng cũng đủ sát với 125 khiến ta tin được rằng bộ phát sinh số ngẫu nhiên đã hoạt động đúng.

Bài tập: Hãy kiểm tra hàm này với một số danh sách dài hơn, và xem liệu số các giá trị trong mỗi ngăn có xu hướng đều nhau không.

Giải pháp duyệt một lượt

Mặc dù chương trình này hoạt động được, nhưng lẽ ra nó có thể hiệu quả hơn. Hiện giờ mỗi lần gọi inBucket, chương trình lại duyệt toàn bộ danh sách. Khi số ngăn tăng lên, điều này sẽ dẫn đến rất nhiều lần duyệt.

Tốt hơn là nên làm một lượt duyệt qua danh sách rồi ứng với mỗi giá trị thì tìm ra chỉ số của ngăn mà nó rơi vào. Sau đó ta có thể tăng biến đếm tương ứng.

Ở mục trước ta đã đem nhân chỉ số i với bucketWidth để được giới hạn dưới của một ngăn cho trước. Bây giờ ta muốn lấy một giá trị trong khoảng từ 0.0 đến 1.0 rồi tìm chỉ số của ngăn mà nó rơi vào.

Vì bài toán này là dạng đảo ngược của bài toán trước, nên ta có thể đoán rằng cần phải chia bucketWidth thay vì nhân với nó. Điều này là đúng.

Vì bucketWidth = 1.0 / numBuckets, nên việc chia cho bucketWidth thì cũng giống như là nhân với numBuckets. Nếu ta đem nhân một số trong khoảng từ 0.0 đến 1.0 với numBuckets, thì ta nhận được một số trong khoảng từ 0.0 đến numBuckets. Nếu làm tròn số đó lên tới số nguyên gần nhất, ta sẽ được chính kết quả mong muốn     chỉ số của ngăn:

numBuckets = 8 
buckets = [0] * numBuckets 
for i in t: 
  index = int(i * numBuckets) 
  buckets[index] = buckets[index] + 1 

Ta đã dùng hàm int để chuyển đổi một số dạng dấu phẩy động sang số nguyên.

Liệu cách tính này có thể cho ra một chỉ số nằm ngoài khoảng (nghĩa là âm hoặc lớn hơn len(buckets)-1 hay không?

Một danh sách như buckets có chứa các số đếm những giá trị nằm trong từng ngăn được gọi là một histogram.

Bài tập: Hãy viết một hàm gọi đến histogram ; hàm này nhận các đối số gồm một danh sách và số các ngăn rồi trả lại một histogram với số ngăn cho trước.

1 Phản hồi

Filed under Think Python

One response to “Bổ sung Think Python: bảng số, histogram

  1. Pingback: Cách nghĩ như nhà khoa học máy tính | Blog của Chiến

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s