15-12-2011 · 18:01
↓ Jump to Comments

Chương 13: Nghiên cứu cụ thể: lựa chọn cấu trúc dữ liệu

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

Phân tích tần số của từ vựng

Như thường lệ, ít nhất là bạn phải cố gắng làm các bài tập sau đây trước khi đọc lời giải của tôi.

Hãy viết một chương trình đọc vào một file, tách mỗi dòng thành các từ riêng lẻ, cắt bỏ các dấu trắng và dấu câu, rồi chuyển chúng về dạng chữ thường.

Gợi ý: module string cho ta hai chuỗi, whitespace chứa dấu cách, dấu tab, dấu xuống dòng, v.v., và punctuation chứa các kí tự dấu câu. Hãy thử làm Python chửi thề xem:

>>> import string
>>> print string.punctuation
!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~

Có thể bạn cũng muốn dùng các phương thức chuỗi strip, replace và translate.

Hãy thăm dự án Gutenberg (gutenberg.net) và tải về cuốn sách ưa thích của bạn dưới dạng file chữ.

Sửa chương trình trong bài tập trước để đọc được quyến sách vừa tải về, bỏ qua đoạn thông tin ở đầu file, và xử lý phần còn lại như bài trước.

Sau đó sửa chương trình để đếm số từ trong quyển sách, và số lần mỗi từ được dùng đến.

In ra số từ khác nhau được dùng trong cuốn sách. So sánh những cuốn sách viết bởi các tác giả khác nhau, viết trong những giai đoạn khác nhau. Tác giả nào dùng lượng từ vựng nhiều nhất?

Hãy sửa chương trình ở bài tập trước để in ra 20 từ được dùng thường xuyên nhất trong cuốn sách.

Hãy sửa chương trình trước để đọc vào một dánh sách các từ (xem Mục {wordlist}) rồi in ra tất cả các từ trong cuốn sách mà không nằm trong danh sách từ. Trong số đó có bao nhiêu lỗi in? Có bao nhiêu từ thông dụng mà đáng ra phải có trong danh sách, và bao nhiêu từ thực sự ít gặp?

Số ngẫu nhiên

Với cùng dữ liệu đầu vào, phần lớn các chương trình máy tính đều cho ra kết quả giống hệt sau mỗi lần chạy, vì vậy ta nói chúng có tính tất định. Tất định là một đặc tính tốt, vì ta thường trông đợi những kết quả tính toán phải giống nhau. Tuy nhiên, ở một số ứng dụng, ta muốn việc tính toán phải không định trước được. Các trò chơi trên máy là ví dụ dễ thấy, ngoài ra còn những chương trình khác.

Để làm chương trình hoàn toàn không định trước hóa ra lại là một việc không dễ dàng gì, nhưng có những cách làm cho chúng ít nhất là dường như không định trước. Một trong số đó là dùng những thuật toán phát sinh ra số giả ngẫu nhiên. Số giả ngẫu nhiên không phải ngẫu nhiên thực sự vì được phát sinh từ một phép toán tất định, nhưng chỉ nhìn vào những con số thì chúng ta không thể phân biệt chúng với những số ngẫu nhiên thực sự.

Module random có các hàm phát sinh ra những số giả ngẫu nhiên (để cho tiện, từ đây tôi sẽ gọi là “ngẫu nhiên”).

Hàm random trả lại một số có phần thập phân, nằm giữa 0.0 và 1.0 (tính cả 0.0 nhưng không kể 1.0). Mỗi khi gọi random, bạn thu được số tiếp theo trong một dãy số dài. Để xem một ví dụ, hãy chạy vòng lặp sau:

import random

for i in range(10):
    x = random.random()
    print x

Hàm randint nhận các tham biến low và high rồi trả lại một số nguyên nằm trong khoảng từ low đến high (kể cả hai đầu).

>>> random.randint(5, 10)
5
>>> random.randint(5, 10)
9

Để chọn ngẫu nhiên một phần tử từ một dãy, bạn có thể dùng choice:

>>> t = [1, 2, 3]
>>> random.choice(t)
2
>>> random.choice(t)
3

Module random cũng có các hàm để phát sinh những giá trị ngẫu nhiên từ những dạng phân bố liên tục bao gồm phân bố chuẩn, lũy thừa, gamma và một số dạng khác.

Hãy viết một hàm có tên choose_from_hist nhận vào một histogram như đã đề cập trong Mục {tần số} và trả lại một giá trị ngẫu nhiên từ histogram, được chọn với xác suất tỉ lệ với tần suất xuất hiện. Chẳng hạn, với histogram sau:

>>> t = ['a', 'a', 'b']
>>> h = histogram(t)
>>> print h
{'a': 2, 'b': 1}

hàm bạn viết cần trả lại 'a' với xác suất 2 / 3 và 'b' với xác suất 1 / 3.

Bảng tần số của từ vựng

Sau đây là một chương trình để đọc vào một file và lập một bảng tần số các từ xuất hiện trong file đó:

import string

def process_file(filename):
    h = dict()
    fp = open(filename)
    for line in fp:
        process_line(line, h)
    return h

def process_line(line, h):
    line = line.replace('-', ' ')

    for word in line.split():
        word = word.strip(string.punctuation + string.whitespace)
        word = word.lower()

        h[word] = h.get(word, 0) + 1

hist = process_file('emma.txt')

Chương trình này đọc file emma.txt, vốn có nội dung là truyện Emma của Jane Austen.

process_file lặp qua các dòng trong file, lần lượt chuyển từng dòng vào process_line. Bảng tần số h được dùng như một biến tích lũy.

process_line dùng phương thức chuỗi replace để thay thế dấu gạch nối từ với dấu cách trước khi dùng split để tách một dòng thành một danh sách các chuỗi. Nó duyệt một dãy các từ và dùng strip và lower để bỏ các dấu câu và chuyển về dạng chữ thường. (Ở đây ta chỉ nói tắt là “chuyển đổi” chuỗi; hãy nhớ rằng kiểu chuỗi không thể thay đổi được, vì vậy các phương thức như strip và lower đều trả về chuỗi mới.)

Cuối cùng, process_line cập nhật bảng tần số bằng cách tạo ra một mục mới hoặc tăng thêm 1 cho mục sẵn có.

Để đếm tổng số từ trong file, ta cần cộng các tần số trong bảng lại:

def total_words(h):
    return sum(h.values())

Số các từ khác nhau chính bằng số các mục trong từ điển:

def different_words(h):
    return len(h)

Sau đây là đoạn mã để in kết quả:

print 'Total number of words:', total_words(hist)
print 'Number of different words:', different_words(hist)

Và kết quả:

Total number of words: 161073
Number of different words: 7212

Để tìm những từ thông dụng nhất, ta có thể áp dụng dạng mẫu DSU; most_common nhận một bảng tần số và trả lại một danh sách các bộ từ-tần số, được sắp xếp theo thứ tự tần số giảm dần:

def most_common(h):
    t = []
    for key, value in h.items():
        t.append((value, key))

    t.sort(reverse=True)
    return t

Sau đây là một vòng lặp in ra mười từ thông dụng nhất:

t = most_common(hist)
print 'The most common words are:'
for freq, word in t[0:10]:
    print word, '\t', freq

Và đây là kết quả thu được từ truyện Emma:

The most common words are:
to      5242
the     5204
and     4897
of      4293
i       3191
a       3130
it      2529
her     2483
was     2400
she     2364

Ta đã thấy các hàm và phương thức có sẵn, chúng nhận vào một số lượng các đối số thay đổi. Ta còn có thể viết những hàm có đối số tùy chọn. Chẳng hạn, sau đây là một hàm để in ra những từ thông dụng nhất dựa theo bảng tần số

def print_most_common(hist, num=10)
    t = most_common(hist)
    print 'The most common words are:'
    for freq, word in t[0:num]:
        print word, '\t', freq

Tham biến thứ nhất là bắt buộc; tham biến thứ hai có thể tùy chọn. Giá trị mặc định của num là 10.

Nếu bạn chỉ cung cấp một đối số:

print_most_common(hist)

thì num sẽ nhận giá trị mặc định. Nếu bạn cung cấp hai đối số:

print_most_common(hist, 20)

thì thay vào đó num sẽ lấy giá trị từ đối số. Nói cách khác, đối số tùy chọn sẽ chiếm chỗ giá trị mặc định.

Nếu như một hàm có cả tham số bắt buộc và tham số tùy chọn thì tất cả tham số bắt buộc phải được viết trước, rồi mới đến tham số tùy chọn.

Phép trừ các từ điển

Việc tìm những từ trong cuốn sách mà không có trong danh sách từ words.txt là một bài toán có thể bạn nhận ra đó chính là phép trừ tập hợp; nghĩa là ta muốn tìm tất cả các từ trong một tập hợp (các từ trong cuốn sách) mà không có trong tập hợp kia (các từ trong từ điển).

subtract nhận vào hai từ điển d1 và d2 rồi trả về một tử điển mới bao gồm tất cả các khóa của d1 mà không có trong d2. Vì chúng ta không thực sụ quan tâm đến các giá trị, ta gán chúng đều bằng None.

def subtract(d1, d2):
    res = dict()
    for key in d1:
        if key not in d2:
            res[key] = None
    return res

Để tìm những từ trong cuốn sách mà không có trong words.txt, ta có thể dùng process_file để lập một bảng tần số cho words.txt, rồi sau đó thực hiện phép trừ:

words = process_file('words.txt')
diff = subtract(hist, words)

print "The words in the book that aren't in the word list are:"
for word in diff.keys():
    print word,

Sau đây là một đoạn kết quả tìm được từ Emma:

The words in the book that aren't in the word list are:
 rencontre jane's blanche woodhouses disingenuousness 
friend's venice apartment ...

Một số từ trong đó là các tên riêng và sở hữu cách. Các từ khác, như “rencontre”, hiện tại ít được dùng. Nhưng vẫn có một số ít từ thông dụng mà đáng ra phải có trong danh sách!

Python có một cấu trúc dữ liệu tên là set trong đó có chứa nhiều phép toán thông dụng với tập hợp. Hãy đọc tài liệu tại docs.python.org/lib/types-set.html và viết một chương trình trong đó dùng phép trừ tập hợp để tìm những từ trong cuốn sách mà không có trong danh sách từ.

Những từ ngẫu nhiên

Để chọn một từ ngẫu nhiên từ bảng tần số, thuật toán đơn giản nhất là lập một danh sách với mỗi từ lặp lại nhiều lần, dựa theo tần số quan sát được, và sau đó thì lựa chọn từ danh sách:

def random_word(h):
    t = []
    for word, freq in h.items():
        t.extend([word] * freq)

    return random.choice(t)

Biểu thức [word] * freq tạo ra một danh sách chứa freq lần lặp lại chuỗi word. Phương thức extend cũng tương tự như append ngoại trừ rằng đối số là một dãy.

Thuật toán này hoạt động được, nhưng không hiệu quả lắm; mỗi khi bạn chọn một từ ngẫu nhiên, nó lại lập lại danh sách, mà danh sách này lớn bằng cuốn sách ban đầu. Một cách cải thiện dễ thấy là lập danh sách một lafn và sau đó chọn nhiều lần, nhưng danh sách vẫn còn lớn.

Một cách làm khác là:

  1. Dùng keys để lấy một danh sách các từ trong cuốn sách.
  2. Lập một danh sách có chứa tổng lũy tích của các tần số từ (xem Bài tập {lũy tích}). Mục từ cuối trong danh sách này là số từ trong cuốn sách này, n.
  3. Chọn một số ngẫu nhiên từ 1 đến n. Dùng cách tìm kiếm nhị phân (Xem Bài tập {phân đôi}) để tìm chỉ số mà tại đó số ngẫu nhiên cần được điền vào cho tổng lũy tích.
  4. Dùng chỉ số để tìm ra từ tương ứng trong danh sách các từ

Hãy viết một chương trình dùng thuật toán này để chọn một từ ngẫu nhiên từ cuốn sách.

Phép phân tích Markov

Nếu bạn chọn các từ trong cuốn sách một cách ngẫu nhiên, bạn chỉ có thể có những từ đúng, nhưng không thể có một câu đúng:

this the small regard harriet which knightley's it most things

Một loạt các từ ngẫu nhiên hiếm khi có nghĩa vì không có mối liên hệ nào giữa những từ kế tiếp. Chẳng hạn, trong một câu thực sự bạn sẽ mong đợi một mạo từ như “the” đi trước một tính từ hoặc danh từ, và có lẽ không đi trước một động từ hoặc trạng từ.

Một cách lượng hóa những mối liên hệ như vậy là phép phân tích Markov1, trong đó cho trước một dãy các từ, ta phải tìm xác suất của từ đi kế tiếp. Chẳng hạn, bài hát Eric, the Half a Bee bắt đầu với:

Half a bee, philosophically,
Must, ipso facto, half not be.
But half the bee has got to be
Vis a vis, its entity. D’you see?

But can a bee be said to be
Or not to be an entire bee
When half the bee is not a bee
Due to some ancient injury?

Trong bài này, cụm từ “half the” luôn được tiếp nối bởi từ “bee”, nhưng cụm từ “the bee” có thể được nối tiếp bởi “has” hoặc “is”.

Kết quả của việc phân tích Markov là một quy tắc ánh xạ từ mỗi tiền tố (như “half the” và “the bee”) đến tất cả những hậu tố có thể có (như “has” và “is”).

Cho trước quy tắc ánh xạ này, bạn có thể phát sinh một văn bản ngẫu nhiên bằng cách bắt đầu với một tiền tố bất kì và chọn một hậu tố khả dĩ một cách ngẫu nhiên. Sau đó, bạn có thể kết hợp đoạn cuối của tiền tố và hậu tố mới tìm được để hình thành một tiền tố mới cho bước tính toán tiếp theo.

Chẳng hạn, nếu bạn bắt đầu với tiền tố “Half a”, thì từ tiếp theo phải là “bee”, bởi vì tiền tố này chỉ xuất hiện một lần duy nhất trong văn bản. Tiền tố tiếp theo là “a bee”, vì vậy hậu tố tiếp theo có thể là “philosophically”, “be” hoặc “due”.

Trong ví dụ này độ dài của tiền tố luôn là hai, nhưng bạn có thể phân tích Markov với tiền tố dài bất kì. Độ dài của tiền tố được gọi là “bậc” của phân tích.

Phép phân tích Markov:

  1. Hãy viết một chương trình đọc một văn bản từ một file và thực hiện phân tích Markov. Kết quả cần thu được là một từ điển với ánh xạ từ các tiền tố đến một tập hợp các hậu tố có thể có. Tập hợp này có thể là danh sách, bộ, hoặc từ điển, tùy bạn chọn. Bạn có thể chạy thử chương trình với tiền tố có độ dài bằng 2, nhưng bạn nên viết chương trình sao cho dễ thử được với những độ dài khác.
  2. Hãy thêm một hàm vào chương trình trên để phát sinh một văn bản ngẫu nhiên dựa trên phép phân tích Markov. Sau đây là một ví dụ từ truyện Emma với độ dài tiền tố bằng 2:

    He was very clever, be it sweetness or be angry, ashamed or only amused, at such a stroke. She had never thought of Hannah till you were never meant for me?” “I cannot make speeches, Emma:” he soon cut it all himself.

    Ở ví dụ này, tôi để nguyên dấu câu đi liền với các từ. Kết quả tương đối đúng về mặt ngữ pháp, nhưng không hoàn toàn. Về ngữ nghĩa nó dường như có nghĩa, nhưng cũng không hoàn toàn.

    Điều gì sẽ xảy ra nếu tôi tăng chiều dài tiền tố? Liệu văn bản ngẫu nhiên lần này có nghĩa hơn không?

  3. Một khi chương trình của bạn chạy được, có thể bạn muốn thử trộn lẫn: nếu bạn phân tích văn bản từ nhiều cuốn sách khác nhau, văn bản ngẫu nhiên được phát sinh sẽ hòa trộn từ và cụm từ những cuốn sách ban đầu theo cách khá thú vị.

Cấu trúc dữ liệu

Việc dùng phép phân tích Markov để phát sinh văn bản ngẫu nhiên thật thú vị, nhưng cũng có một mục đích để luyện tập lập trình: kĩ năng chọn cấu trúc dữ liệu. Trong lời giải của bạn cho các bài tập trước, bạn đã phải chọn:

  • Cách biểu diễn các tiền tố.
  • Cách biểu diễn tập hợp các hậu tố có thể có.
  • Cách biểu diễn quy tắc ánh xạ giữa mỗi tiền tố với tập hợp các hậu tố có thể.

Được rồi, điều cuối cùng rất dễ dàng; dạng ánh xạ duy nhất mà chúng ta biết chính là từ điển, và đây là cách lựa chọn rất tự nhiên.

Với các tiền tố, lựa chọn dễ thấy nhất là dùng chuỗi, danh sách các chuỗi, hoặc bộ các chuỗi. Với các hậu tố, một lựa chọn là danh sách; lựa chọn khác là bảng tần số (từ điển).

Bạn lựa chọn bằng cách nào đây? Bước đầu tiên là nghĩ về những phép thao tác cần thực hiện trên từng cấu trúc dữ liệu. Với các tiền tố, ta cần có khả năng bỏ được những từ ở phía đầu và thêm vào những từ ở phía cuối. Chẳng hạn, nếu tiền tố hiện tại là “Half a”, và từ tiếp theo là “bee”, bạn cần có khả năng tạo thành tiền tố thiếp theo là “a bee”.

Lựa chọn ban đầu của bạn có thể là danh sách, vì ta dễ dàng thêm và bỏ các phần tử của nó, nhưng ta cũng cần dùng được các tiền tố như các khóa trong từ điển; vì vậy mà ta phải loại bỏ khả năng dùng danh sách. Khi dùng bộ, bạn không thể thêm vào hoặc xóa đi, nhưng có thể dùng toán tử cộng để hình thành một bộ mới:

def shift(prefix, word):
    return prefix[1:] + (word,)

shift nhận vào một bộ các từ, prefix, và một chuỗi, word, rồi hình thành một bộ mới chứa tất cả những từ trong prefix ngoại trừ từ thứ nhất, và thêm word vào cuối.

Với tập hợp các hậu tố, những phép thao tác cần thực hiện gồm có thêm vào một hậu tố mới (hoặc tăng tần số của một hậu tố sẵn có), và chọn một hậu tố ngẫu nhiên.

Việc thêm một hậu tố mới cũng dễ thực hiện trên danh sách như trên bảng tần số. Việc chọn một phần tử ngẫu nhiên từ danh sách thì dễ; chọn từ bảng tần số một cách hiệu quả thì khó thực hiện hơn (xem Bài tập {tần số ngẫu nhiên}).

Đến đây chúng ta mới chỉ chủ yếu bàn về độ khó dễ khi thực hiện, nhưng còn những yếu tố khác cần tính đến khi chọn các cấu trúc dữ liệu. Một trong số đó là thời gian chạy. Đôi khi có một nguyên nhân về mặt lí thuyết khiến ta mong đợi rằng một cấu trúc dữ liệu này nhanh hơn cấu trúc khác; chẳng hạn, tôi đã đề cập rằng toán tử in dùng với từ điển thì nhanh hơn dùng với danh sách, ít nhất là khi có rất nhiều phần tử.

Nhưng thường thì bạn sẽ không biết trước được là cách thực hiện nào sẽ nhanh hơn. Một lựa chọn là thực hiện cả hai và xem cách nào tốt hơn. Cách tiếp cận này được gọi là đánh giá bằng so sánh. Một cách làm thực tiễn khác là chọn cấu trúc dữ liệu dễ thực hiện nhất, vá sau đó xem nó có đủ nhanh khi dùng trong ứng dụng được viết hay không. Nếu đủ nhanh thì không cần phải sửa nữa. Nếu không thì có những công cụ, như module profile, có thể chỉ ra những chỗ trong chương trình mà chạy mất nhiều thời gian nhất.

Yếu tố khác cần tính đến là dung lượng lưu trữ. Chẳng hạn, việc dùng một bảng tần số để tập hợp các hậu tố có thể sẽ chiếm ít dung lượng hơn vì bạn chỉ cần lưu mỗi từ một lần, bất kể từ đó được dùng bao nhiêu lần trong văn bản. Trong một số trường hợp khác, việc tiết kiệm dung lượng cũng có thể làm chương trình của bạn chạy nhanh hơn, và ngược lại, có thể làm chương trình của bạn không chạy được do hết bộ nhớ. Tuy nhiên, với nhiều ứng dụng, dung lượng là vấn đề thứ yếu sau bộ nhớ.

Một suy nghĩ sau cùng: với nội dung thảo luận ở trên, tôi có ngụ ý là chúng ta nên dùng một cấu trúc dữ liệu chung cho cả việc phân tích và phát sinh. Nhưng vì đây là hai khâu riêng biệt, ta cũng có thể dùng một cấu trúc dữ liệu để phân tích sau đó chuyển đổi sang một cấu trúc khác cho việc phát sinh. Cách này tính ra sẽ có lợi nếu như khoảng thời gian tiết kiệm được khi phát sinh lớn hơn thời gian để chuyển đổi.

Gỡ lỗi

Khi gỡ lỗi một chương trình, đặc biệt là khi bạn cố gắng gỡ một lỗi hóc búa, có bốn việc mà bạn nên thử như sau:

đọc:
Xem xét mã lệnh, tự đọc và diễn giải nó, và kiểm tra xem nó có thực hiện đúng ý định của bạn không.

chạy:
Thử nghiệm bằng cách thay đổi và chạy các bản mã lệnh khác nhau. Thường khi bạn hiển thị đúng thứ cần thiết ở một vị trí đúng trong chương trình thì bài toán đã rõ ràng, nhưng đôi khi bạn phải dành thời gian để dựng dàn giáo.

tư duy:
Hãy dành thời gian để suy nghĩ! Lỗi xảy ra thuộc loại gì: cú pháp, thực thi, hay ngữ nghĩa? Bạn rút được thông tin gì từ thông báo lỗi, từ kết quả đầu ra của chương trình? Loại lỗi gì có thể gây ra vấn đề mà bạn thấy được? Trước khi có vấn đề xảy ra, bạn đã sửa đổi mã lệnh ở chỗ nào?

rút lui:
Sẽ có lúc nhất định, cách làm tốt nhất là rút lui, thu lại những thay đổi gần nhất, đến khi bạn trở về trạng thái của chương trình chạy được mà bạn cũng hiểu được. Sau đó bạn có thể bắt đầu phát triển lại chương trình.

Các lập trình viên mới đôi khi cũng bị lún sâu vào một trong những cách làm sau mà quên mất những cách còn lại. Mỗi cách gắn liền với một kiểu nhược điểm riêng.

Chẳng hạn, việc đọc mã lệnh có thể giúp bạn nếu như vấn đề xảy ra thuộc về lỗi chính tả, nhưng sẽ không ích gì nếu như vấn đề ở chỗ hiểu sai khái niệm. Nếu bạn không hiểu chương trình làm việc gì, có thể bạn sẽ phải đọc nó 100 lần mà vẫn không thấy lỗi, vì lỗi nằm ngay trong đầu bạn.

Việc chạy các thử nghiệm có thể sẽ giúp bạn, đặc biệt khi bạn chạy những bài kiểm tra ngắn, đơn giản. Nhưng nếu bạn chạy thử nghiệm mà không nghĩ hoặc đọc mã lệnh, có thể bạn sẽ rơi vào trường hợp mà tôi gọi là “lập trình theo bước ngẫu nhiên”, tức là quá trình tạo ra những thay đổi ngẫu nhiên đến khi chương trình chạy đúng. Khỏi cần phải nói, việc lập trình theo ngẫu nhiên có thể sẽ rất tốn thời gian.

Bạn cần phải dành thời gian suy nghĩ. Gỡ lỗi cũng giống như một ngành khoa học thực nghiệm. Bạn cần phải có ít nhất một giả thiết về vấn đề cần giải quyết là gì. Nếu có hai hay nhiều khả năng xảy ra, cố gắng nghỉ ra một phép thử để loại bỏ một khả năng trong số đó.

Việc nghỉ ngơi cũng giúp ích cho suy nghĩ. Việc nói năng cũng vậy. Nếu bạn giải thích vấn đề cho một người khác (hoặc thậm chí cho chính bạn), có thể đôi khi bạn sẽ tìm được lời giải ngay trước lúc kết thúc lời nói.

Nhưng ngay cả những kĩ thuật gỡ lỗi tốt nhất cũng thất bại khi có quá nhiều lỗi, hoặc khi mã lệnh bạn cần sửa quá lớn và phức tạp. Đôi lúc giải pháp tốt nhất là rút lui, làm đơn giản chương trình cho đến khi bạn có được phiên bản chương trình hoạt động được và bạn hiểu được nó.

Các lập trình viên mới thường miễn cưỡng trong việc rút lui vì họ không thể chịu được khi xóa một dòng lệnh (ngay cả khi nó sai). Nếu bạn cảm thấy tiện thì có thể sao chép chương trình ra một file khác trước khi bắt tay vào việc lược bỏ nó. Sau đó bạn có thể dán các phần cũ trở lại, mỗi lúc một ít.

Để tìm ra một lỗi hóc búa đòi hỏi phải đọc, chạy mã lệnh, suy nghĩ, và đôi khi rút lui. Nếu bạn bị sa lầy vào một trong những việc trên thì hãy thử các việc còn lại.

Thuật ngữ

tất định:
Tính chất của chương trình thực hiện công việc giống nhau ở mỗi lần chạy và cho ra kết quả như nhau.

giả ngẫu nhiên:
Tính chất của dãy số nhìn có vẻ ngẫu nhiên, nhưng được phát sinh bởi một chương trình tất định.

giá trị mặc định:
Giá trị được gán cho tham biến tùy chọn nếu không nhập vào đối số.

chiếm chỗ:
Sự thay thế giá trị mặc định bởi một đối số.

đánh giá bằng so sánh:
Quá trình chọn lựa giữa các cấu trúc dữ liệu bằng cách thực hiện các phương án rồi kiểm thử chúng theo một mẫu số liệu có thể.

Bài tập

“Hạng” của một từ là vị trí của nó trong một danh sách các từ xếp theo tần số: từ thường gặp nhất có hạng 1, từ thường gặp thứ nhì có hạng 2, v.v.

Định luật Zipf mô tả mối liện hệ giữa hạng và tần số của từ trong ngôn ngữ tự nhiên2. Đặc biệt hơn, nó còn dự đoán rằng tần số f của từ có hạng r là:

f = cr - s
trong đó s và c là các tham số phụ thuộc vào ngôn ngữ và văn bản. Nếu lấy logarit hai vế của phương trình trên, bạn sẽ thu được:

logf = logc - slogr
Vì vậy khi vẽ đồ thị logf theo logr, bạn sẽ được một đường thẳng với độ dốc  - s và giao điểm logc với trục tung.

Hãy viết một chương trình để đọc văn bản vào từ một file, đếm tần số các từ, và in ra mỗi từ trên một dòng, theo thứ tự giảm dần của tần số, cùng với logf và logr. Hãy dùng chương trình vẽ biểu đồ mà bạn chọn để vẽ đồ thị kết quả và kiểm tra xem liệu nó có hình thành một đường thẳng không. Bạn có thể ước tính giá trị của s không?

  1. Nghiên cứu cụ thể này được dựa vào một ví dụ của Kernighan and Pike trong cuốn The Practice of Programming, 1999. ↩
  2. Xem wikipedia.org/wiki/Zipf's_law. ↩

1 bình luận

Filed under Think Python

Tagged as , , ,

1 responses to “Chương 13: Nghiên cứu cụ thể: lựa chọn cấu trúc dữ liệu”

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

Bình luận về bài viết này