Chương 11: Từ điển

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

Từ điển giống như một danh sách, nhưng khái quát hơn. Trong một danh sách, các chỉ số phải là số nguyên; trong từ điển chúng có thể thuộc về (gần như) bất kì kiểu dữ liệu nào.

Bạn có thể nghĩ về từ điển như một phép ánh xạ từ một tập hợp các chỉ số (cũng gọi là khóa) và một tập hợp các giá trị. Mỗi khóa được đánh cho một giá trị. Sự liên hệ giữa khóa và giá trị được gọi là một cặp khóa-trị và đôi khi được gọi là một mục.

Ví dụ như chúng ta lập một từ điển ánh xạ giữa các từ tiếng Anh và tiếng Tây Ban Nha, vì vậy tất cả các khóa và các giá trị đều là những chuỗi.

Hàm dict sẽ tạo ra một từ điển mới mà không có mục nào. Vì dict là tên của một hàm có sẵn, bạn không nên lấy tên này để đặt cho một biến.

>>> eng2sp = dict()

>>> print eng2sp
{}

Cặp ngoặc nhọn, {}, biểu thị một từ điển rỗng. Để thêm các mục vào trong một từ điển, ta có thể dùng cặp ngoặc vuông:

>>> eng2sp['one'] = 'uno'

Dòng lệnh này tạo ra một mục trong đó ánh xạ khóa 'one' đến giá trị 'uno'. Nếu in lại nội dung từ điển, ta sẽ thấy một cặp khóa-trị với dấu hai chấm ngăn cách giữa phần khóa và phần trị:

>>> print eng2sp
{'one': 'uno'}

Hình thức hiển thị kết quả như vậy cũng dùng được để nhập dữ liệu. Chẳng hạn, bạn có thể tạo một từ điển mới gồm ba mục:

>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}

Nhưng nếu in eng2sp, có thể bạn sẽ thấy ngạc nhiên:

>>> print eng2sp
{'one': 'uno', 'three': 'tres', 'two': 'dos'}

Thứ tự của các cặp khóa-trị không còn giữ nguyên nữa. Thật ra, nếu bạn gõ lại ví dụ trên vào máy tính của mình, có thể kết quả còn khác nữa. Nói chung, không thể biết trước thứ tự các mục trong một từ điển.

Tuy nhiên điều đó chẳng quan trọng vì các phần tử trong từ điển không bao giờ được chỉ định bởi các chỉ số nguyên. Thay vào đó, bạn dùng các khóa để tra tìm những giá trị tương ứng:

>>> print eng2sp['two']
'dos'

Khóa 'two' luôn được ánh xạ đến giá trị 'dos' vì vậy thứ tự của các mục không quan trọng.

Nếu như khóa cần tìm không xuất hiện trong từ điển, bạn sẽ nhận được một biệt lệ:

>>> print eng2sp['four']
KeyError: 'four'

Hàm len có tác dụng trên từ điển; nó trả lại số cặp khóa-trị:

>>> len(eng2sp)
3

Toán tử in cũng có tác dụng trên từ điển; nó cho chúng ta biết liệu có một khóa trong từ điển với tên gọi cho trước không (chứ không phải là có giá trị với tên gọi như vậy).

>>> 'one' in eng2sp
True
>>> 'uno' in eng2sp
False

Để xem rằng có một giá trị nào đó có trong từ điển với tên gọi cho trước không, bạn có thể dùng phương thức values, để trả về các giá trị như một danh sách, và sau đó dùng toán tử in:

>>> vals = eng2sp.values()
>>> 'uno' in vals
True

Toán tử in dùng các thuật toán khác nhau đối với danh sách và với từ điển. Đối với danh sách, nó dùng một thuật toán tìm kiếm, như trong Mục find. Khi danh sách dài hơn, thời gian tìm kiếm cũng tăng lên tỉ lệ thuận với độ dài. Đối với từ điển, Python dùng một thuật toán có tên là bảng băm (hashtable) với một tính chất ưu việt: toán tử in được thực hiện với thời gian gần như không đổi bất kể độ dài của từ điển là bao nhiêu. Tôi sẽ không giải thích làm thế nào để có được điều đó, nhưng bạn có thể xem thêm ở wikipedia.org/wiki/Hash_table.

Hãy viết một hàm để đọc vào các từ trong words.txt và lưu chúng như những khóa trong một từ điển. Các giá trị bằng bao nhiêu thì không quan trọng. Sau đó bạn có thể dùng toán tử in để kiểm tra nhanh xem một chuỗi cần tìm có trong từ điển hay không.

Nếu bạn đã làm Bài tập wordlist1, bạn có thể so sánh tốc độ của lời giải này với toán tử in dành cho danh sách cùng phép tìm kiếm nhị phân.

Từ điển như một tập hợp các biến đếm

Giả sử như bạn có một chuỗi và cần đến xem trong chuỗi đó, mỗi chữ cái xuất hiện bao nhiêu lần. Có một vài cách để làm điều đó:

1. Bạn có thể tạo ra 26 biến, mỗi biến cho một chữ cái trong bảng. Sau đó bạn duyệt chuỗi và với mỗi kí tự, tăng biến đếm tương ứng lên một đơn vị, có thể dùng một câu lệnh điều kiện nhiều nhánh.
2. Bạn có thể tạo ra một danh sách gồm 26 phần tử. Sau đó bạn chuyển đổi mỗi chữ cái thành một số (dùng hàm có sẵn ord), dùng số này như là một chỉ số trong danh sách, và tăng biến đếm tương ứng lên.
3. Bạn có thể tạo ra một từ điển với các kí tự như những khóa và biến đếm như những giá trị tương ứng. Lần đầu khi bắt gặp một kí tự, bạn thêm một mục vào từ điển. Những lần sau đó thì tăng dần biến đếm cho những mục đã có trong từ điển.

Các cách làm trên đây đều giống nhau về thao tác tính toán, nhưng khác nhau về cách thực hiện tính toán đó.

Cách thực hiện là một phương pháp tính toán; một số cách thực hiện tốt hơn số còn lại. Chẳng hạn, thực hiện kiểu từ điển có lợi rằng chúng ta không cần biết trước là chữ cái nào sẽ xuất hiện trong chuỗi và chỉ cần dành chỗ cho những chữ cái thực sự xuất hiện.

Đoạn mã có thể được viết như sau:

def histogram(s):
    d = dict()
    for c in s:
        if c not in d:
            d[c] = 1
        else:
            d[c] += 1
    return d

Tên của hàm là histogram, chính là một thuật ngữ ngành thống kê để chỉ tập hợp các tần số.

Dòng thứ nhất của hàm nhằm tạo ra một từ điển rỗng. Vòng lặp for làm nhiệm vụ duyệt chuỗi. Qua mỗi vòng lặp, nếu kí tự c không có trong từ điển, ta sẽ tạo ra một mục mới với khóa c và giá trị ban đầu bằng 1 (vì ta đã bắt gặp kí tự này một lần). Nếu c đã có trong từ điển thì ta sẽ tăng thêm 1 cho d[c].

Sau đây là tác dụng của nó:

>>> h = histogram('brontosaurus')

>>> print h
{'a': 1, 'b': 1, 'o': 2, 'n': 1, 's': 2, 'r': 2, 'u': 2, 't': 1}

Bảng phân bố tần số này cho thấy các chữ cái 'a' và 'b' xuất hiện một lần; 'o' xuất hiện hai lần, v.v.

Từ điển có một phương thức gọi là get nhận vào một khóa và một giá trị mặc định. Nếu khóa này có xuất hiện trong từ điển, get sẽ trả lại giá trị tương ứng; ngược lại nó sẽ trả về giá trị mặc định nói trên. Chẳng hạn:

>>> h = histogram('a')

>>> print h
{'a': 1}
>>> h.get('a', 0)
1
>>> h.get('b', 0)
0

Hãy dùng get để viết histogram theo cách gọn gàng hơn. Bạn cần loại bỏ bớt một lệnh if.

Thao tác lặp trong từ điển

Nếu bạn dùng một từ điển trong một lệnh for, nó sẽ duyệt các khóa của từ điển này. Chẳng hạn, print_hist sẽ in các khóa cùng với giá trị tương ứng:

def print_hist(h):
    for c in h:
        print c, h[c]

Và kết quả đầu ra sẽ có dạng sau:

>>> h = histogram('parrot')
>>> print_hist(h)
a 1
p 1
r 2
t 1
o 1

Một lần nữa ta thấy các khóa không xếp theo thứ tự cụ thể nào.

Từ điển có một phương thức gọi là keys để trả về các khóa của bản thân nó, dưới dạng một danh sách không xếp theo thứ tự.

Hãy sửa print_hist để in ra các khóa và giá trị theo thứ tự bảng chữ cái.

Tra ngược

Cho trước một từ điẻn d và khóa k, ta dễ dàng tìm được giá trị tương ứng v = d[k]. Thao tác này được gọi là tra.

Nhưng nếu bạn có v và muốn tìm k thì sao? Bạn gặp phải hai vấn đề: thứ nhất, có thể có nhiều khóa tương ứng với giá trị v. Tùy từng trường hợp cụ thể, bạn có thể chọn một hoặc lập một danh sách chứa tất cả các khóa đó. Thứ hai, không có một dạng cú pháp đơn giản nào giúp tra ngược; bạn phải thực hiện tìm kiếm.

Sau đây là một hàm nhận vào một giá trị và trả về khóa đầu tiên ánh xạ tới giá trị đó:

def reverse_lookup(d, v):
    for k in d:
        if d[k] == v:
            return k
    raise ValueError

Hàm này là một ví dụ nữa minh họa cho dạng mẫu tìm kiếm, nhưng nó có một đặc điểm mà trước đây ta chưa từng bắt gặp, đó là raise. Lệnh raise gây ra một biệt lệ; trong trường hợp này là ValueError, nói chung thường được dùng để chỉ rằng có điều gì đó không ổn với giá trị của một tham biến.

Nếu ta đến cuối vòng lặp, nghĩa là v không xuất hiện trong từ điển như một giá trị, thì ta sẽ gây ra một biệt lệ.

Sau đây là một ví dụ tra ngược thành công:

>>> h = histogram('parrot')
>>> k = reverse_lookup(h, 2)

>>> print k
r

Và một ví dụ không thành công:

>>> k = reverse_lookup(h, 3)
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "<stdin>", line 5, in reverse_lookup
ValueError

Kết quả nhận được khi bạn gây ra biệt lệ cũng giống như khi Python gây ra: sẽ có thông báo lỗi cùng việc dò ngược về vị trí xảy ra lỗi.

Lệnh raise nhận một tham biến tùy chọn là thông bào lỗi cụ thể. Chẳng hạn:

>>> raise ValueError, 'gia tri khong xuat hien trong tu dien'
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
ValueError: gia tri khong xuat hien trong tu dien

Việc tra ngược chậm hơn nhiều so với tra xuôi; nếu bạn phải thường xuyên thực hiện thao tác này, hoặc khi từ điển rất lớn, chương trình sẽ chạy chậm.

Hãy sửa reverse_lookup sao cho nó lập và trả về một danh sách của tất cả các khóa ánh xạ đến v, hoặc một danh sách rỗng nếu không có khóa nào như vậy.

Từ điển và danh sách

Danh sách có thể đóng vai trò làm giá trị trong từ điển. Chẳng hạn, nếu bạn có một từ điển ánh xạ những chữ cái đến tần số xuất hiện của chúng, một việc có thể làm là đảo ngược nó; nghĩa là tạo ra một từ điển ánh xạ từ tần số đến chữ cái. Vì một số chữ cái có thể có cùng tần số, nên mỗi giá trị trong từ điển ngược phải là một danh sách chữ cái.

Sau đây là một hàm để đảo ngược từ điển:

def invert_dict(d):
    inv = dict()
    for key in d:
        val = d[key]
        if val not in inv:
            inv[val] = [key]
        else:
            inv[val].append(key)
    return inv

Qua mỗi vòng lặp, key nhận một khóa từ d và val nhận giá trị tương ứng. Nếu val không có trong inv, nghĩa là chúng ta chưa từng bắt gặp nó, vì vậy chúng ta sẽ tạo ra một mục mới và khởi tạo nó là một danh sách đơn (một danh sách chỉ chứa một phần tử). Ngược lại nếu đã thấy giá trị này từ trước, ta sẽ điền thêm khóa tương ứng vào danh sách.

Sau đây là một ví dụ:

>>> hist = histogram('parrot')

>>> print hist
{'a': 1, 'p': 1, 'r': 2, 't': 1, 'o': 1}
>>> inv = invert_dict(hist)
>>> print inv
{1: ['a', 'p', 't', 'o'], 2: ['r']}

Và sau đây là một sơ đồ chỉ hist và inv:

Từ điển được biểu diễn bởi một khung vời kiểu dict phía trên nó và các cặp khóa-trị bên trong. Nếu như các giá trị là số nguyên, số có phần thập phân hoặc chuỗi, tôi thường vẽ chúng bên trong khung. Còn danh sách thì tôi thường vẽ bên ngoài khung, để giữ cho sơ đồ được đơn giản.

Danh sách có thể là giá trị trong từ điển, như trong ví dụ này, nhưng không thể là khóa. Sau đây là hậu quả nếu bạn thử điều này:

>>> t = [1, 2, 3]
>>> d = dict()
>>> d[t] = 'oops'
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
TypeError: list objects are unhashable

Trước đây tôi đã đề cập rằng một từ điển được thực hiện bằng cách dùng một mảng băm và điều đó có nghĩa là các khóa phải băm được.

Một hàm băm là một hàm nhận vào một giá trị (có kiểu bất kì) và trả lại một số nguyên. Từ điển sử dụng những số nguyên này, gọi là các giá trị hash, để lưu trữ và tra những cặp khóa-trị.

Hệ thống này làm việc tốt nếu các khóa không thay đổi được. Nhưng nếu các khóa thay đổi được, như danh sách, thì mọi việc tồi tệ có thể xảy ra. Chẳng hạn, khi bạn tạo ra một cặp khóa-trị, Python tính hàm băm cho các khóa và lưu trữ chúng ở những địa chỉ tương ứng. Nếu bạn thay đổi khóa và lại băm chúng thì sẽ đến những địa chỉ khác. Trong trường hợp đó bạn có thể có hai mục cho cùng một khóa, hoặc có thể không tìm được khóa; và dù thế nào thì từ điển cũng không hoạt động đúng.

Đó là lí do tại sao khóa phải băm được, và tại sao các kiểu dữ liệu thay đổi được như danh sách thì không dùng được làm khóa. Cách đơn giản nhất để khắc phục hạn chế này là dùng các bộ, mà ta sẽ xét đến trong chương sau.

Vì từ điển có tính thay đổi được, bản thân chúng không thể dùng làm khóa, nhưng chúng có thể dùng vào vai trò giá trị.

Hãy đọc tài liệu về phương thức setdefault của từ điển và dùng nó để viết một dạng gọn hơn cho invert_dict.

Giá trị nhớ

Nếu đã thử nghịch hàm fibonacci ở Mục one more example, bạn có thể nhận thấy đối số bạn nhập vào càng lớn thì chương trình chạy càng lâu. Hơn nữa, thời gian chạy của chương trình tăng vọt một cách đáng kể.

Để hiểu được tại sao, hãy xét đồ thị gọi này của hàm fibonacci với n=4:

Một đồ thị gọi cho thấy một loạt những khung biểu diễn hàm, với các đường nối giữa khung hàm này với các khung hàm mà nó gọi đến. Trên đỉnh của đồ thị, fibonacci với n=4 gọi fibonacci với n=3 và n=2. Đến lượt mình, fibonacci với n=3 lại gọi fibonacci với n=2 và n=1. Và cứ như vậy.

Hãy đến xem có bao nhiêu lần fibonacci(0) và fibonacci(1) được gọi đến. Đây là một lời giải rất kém hiệu quả, và càng tồi hơn khi đối số càng lớn.

Một cách giải quyết là theo dõi những giá trị đã được tính bằng cách lưu nó vào trong một từ điển. Một giá trị đã tính trước rồi được lưu để sau này dùng được gọi là một giá trị nhớ¹. Sau đây là một cách thực hiện fibonacci có dùng giá trị nhớ:

known = {0:0, 1:1}

def fibonacci(n):
    if n in known:
        return known[n]

    res = fibonacci(n-1) + fibonacci(n-2)
    known[n] = res
    return res

known là một từ điển theo dõi các số Fibonacci mà ta đã biết. Nó bắt đầu với hai mục: 0 ánh xạ đến 0 và 1 ánh xạ đến 1.

Mỗi khi fibonacci được gọi, nó sẽ kiểm tra known. Nếu kết quả đã có ở đấy rồi, nó có thể trả lại lập tức. Còn nếu không, nó phải tính giá trị mới, bổ sung vào từ điển, và trả lại giá trị này.

Hãy chạy hàm fibonacci trên và phiên bản ban đầu của hàm này với một loạt các tham số rồi so sánh thời gian thực hiện của chúng.

Biến toàn cục

Trong ví dụ trước, known được tạo ra bên ngoài hàm, vì vậy nó thuộc về một khung đặc biệt có tên là __main__. Các biến trong __main__ đôi khi được gọi là toàn cục vì chúng có thể được truy cập từ bất kì hàm nào. Khác với các biến địa phương, mà sẽ biến mất ngay sau khi hàm kết thúc, các biến toàn cục vẫn tồn tại từ một lần gọi hàm sang đến lần gọi tiếp theo.

Các biến toàn cục thường được dùng làm cờ; tức là các biến kiểu boole để chỉ định (như “lá cờ”) xem môt điều kiện có đúng hay không. Chẳng hạn, một số chương trình dùng một cờ có tên là verbose để điều khiển mức độ chi tiết của kết quả được xuất ra:

verbose = True

def example1():
    if verbose:
        print 'Running example1'

Nếu bạn thử gán lại giá trị cho một biến toàn cục, bạn có thể sẽ ngạc nhiên. Ví dụ sau đây vốn được viết với ý định theo dõi xem hàm có được gọi hay chưa:

been_called = False

def example2():
    been_called = True         # SAI

Nhưng nếu chạy nó, bạn sẽ thấy giá trị của been_called không hề thay đổi. Vấn đề là hàm example2 tạo ra một biến địa phương khác có tên là been_called. Biến địa phương sẽ biến mất ngay khi hàm kết thúc và không ảnh hưởng gì đến biến toàn cục.

Để gán lại giá trị cho một biến toàn cục bên trong một hàm, bạn phải khai báo biến toàn cục trước khi sử dụng nó:

been_called = False

def example2():
    global been_called 
    been_called = True

Lệnh global báo cho trình thông dịch biết một thông tin kiểu như, “Trong hàm này, khi nói đến been_called, ý của tôi là biến toàn cục; đừng tạo ra một biến địa phương”.

Sau đây là một ví dụ cố gắng cập nhật một biến toàn cục:

count = 0

def example3():
    count = count + 1          # SAI

Nếu chạy nó bạn sẽ thu được:

UnboundLocalError: local variable 'count' referenced before assignment

Python coi rằng count là biến địa phương, nghĩa là bạn sẽ đọc biến này trước khi ghi giá trị vào nò. Để sửa lỗi sai này, một lần nữa bạn phải khai báo count là biến toàn cục.

def example3():
    global count
    count += 1

Nesu biến toàn cục thuộc kiểu thay đổi được, bạn có thể sửa nó mà không phải khai báo:

known = {0:0, 1:1}

def example4():
    known[2] = 1

Như vậy bạn có thể thêm vào, bỏ bớt, và thay thế các phần tử của một danh sách hoặc từ điển toàn cục, nhưng nếu bạn muốn gán lại giá trị cho biến, bạn phải khai báo nó:

def example5():
    global known
    known = dict()

Số nguyên dài

Nếu tính fibonacci(50), bạn sẽ thu được:

>>> fibonacci(50)
12586269025L

Chữ L ở cuối chỉ định rằng kết quả có dạng số nguyên dài ², hoặc kiểu long.

Các giá trị thuộc kiểu int bị giới hạn về độ lớn; các số nguyên dài có thể lớn tùy ý, nhưng khi lớn lên chúng sẽ chiếm nhiều dung lượng bộ nhớ và cần nhiều thời gian xử lý.

Các toán tử số học và các hàm trong module math cũng dùng được với số nguyên dài, vì vậy nói chung bất kì đoạn mã nào chạy được với số nguyên int cũng chạy được với long.

Bất cứ khi nào kết quả tính toán quá lớn không thể biểu diễn được bởi số nguyên thường, Python sẽ tự chuyển sang dạng số nguyên dài:

>>> 1000 * 1000
1000000

>>> 100000 * 100000
10000000000L

Trong trường hợp đầu, kết quả có kiểu int; ở trường hợp thứ hai là kiểu long.

PHép lũy thừa các số nguyên lớn là cơ sở của các thuật toán thông dụng để mã hóa khóa công khai. Hãy đọc trang web Wikipedia về thuật toán RSA³ và viết các hàm thực hiện mã hóa và giải mã một đoạn tin.

Gỡ lỗi

Khi bạn làm việc với các bộ dữ liệu lớn, việc gỡ lỗi bằng cách in ra và kiểm tra dữ liệu thủ công là việc không tưởng. Sau đây là một số gơi ý cho việc gỡ lỗi các bộ dữ liệu lớn:

Thu nhỏ dữ liệu đầu vào:

Nếu có thể, hãy thu gọn kích thước của bộ dữ liệu. Chẳng hạn, nếu chương trình cần đọc một file kí tự, hãy bắt đầu bằng việc đọc 10 dòng đầu tiên, hoặc với một ví dụ nhỏ nhất mà bạn có thể kiếm được. Bạn có thể tự tạo ra file, hoặc (tốt hơn là) sửa đổi chương trình để nó chỉ đọc n dòng đầu tiên.

Nếu có lỗi xảy ra, bạn có thể giảm n xuống đến giá trị nhỏ nhất mà còn có lỗi, sau đó tăng dần lên đồng thời tiến hành tìm kiếm và sửa các lỗi.

Kiểm tra các kết quả tóm tắt và kiểu các biến:

Thay vì in và kiểm tra toàn bộ dữ liệu, bạn có thể cân nhắc in ra phần tóm lược cho dữ liệu thôi; chẳng hạn, số các mục trong một từ điển hoặc tổng của các số trong một danh sách.

Một nguyên nhân thường gây ra lỗi thực thi là khi một giá trị không nhận được kiểu đúng. Để gỡ những lỗi dạng này, thường ta chỉ cần in ra kiểu của một giá trị.

Viết chương trình kiểm tra:

Đôi khi bạn có thể viết đoạn mã lệnh để tự động kiểm tra lỗi. Chẳng hạn, nếu bạn tính trị trung bình của một dãy các số, bạn có thể kiểm tra rằng kết quả không lớn hơn giá trị lớn nhất trong dãy hoặc không nhỏ hơn giá trị nhỏ nhất. Đây được gọi là “kiểm tra độ lành mạnh” vì nó phát hiện được các kết quả vô lí hết mức.

Một dạng kiểm tra nữa nhằm so sánh kết quả giữa hai lần tính khác nhau để xem chúng có nhất quán không. Đây được gọi là “kiểm tra độ nhất quán”.

In đẹp kết quả đầu ra:

Việc định dạng kết qủa đầu ra khi gỡ lỗi có thể đơn giản hóa việc phát hiện lỗi. Ta đã thấy một ví dụ trong Mục factdebug. Module pprint cho ta một hàm pprint để hiển thị thông tin về các kiểu có sẵn theo hình thức dễ đọc hơn.

Một lần nữa, thời gian mà bạn dành cho việc dựng dàn giáo có thể giúp giảm bớt thời gian mất để gỡ lỗi.

Thuật ngữ

từ điển:

Dạng ánh xạ từ một tập hợp các khóa đến các giá trị tương ứng của chúng.

cặp khóa-trị:

Dạng biểu diễn ánh xạ từ một khóa đến một giá trị.

mục:

Tên gọi khác cho cặp khóa-trị.

khóa:

Một đối tượng xuất hiện trong từ điển với vai trò bộ phận đầu của một cặp khóa-trị.

trị:

Một đối tượng xuất hiện trong từ điển với vai trò bộ phận thứ hai của một cặp khóa-trị. Khái niệm này đặc thù hơn so với “giá trị” mà ta dùng trước đây.

thực thi:

Một cách tiến hành tính toán.

bảng băm:

Thuật toán được dùng để thực thi các từ điển trong Python.

hàm băm:

Hàm được dùng bởi một bảng băm để tính ra vị trí cho một khóa.

băm được:

Kiểu dữ liệu có hàm băm. Các kiểu không thay đổi được như số nguyên, số có phần thập phân, và chuỗi đều băm được; các kiểu thay đổi được như danh sách và từ điển thì không.

tra:

Thao tác trên từ điển, nhận vào một khóa và tìm ra trị tương ứng.

tra ngược:

Thao tác trên từ điển, nhận vào một trị và tìm ra một hoặc nhiều khóa có ánh xạ đến nó.

danh sách đơn:

Danh sách (hoặc một dãy nói chung) có một phần tử duy nhất.

biểu đồ gọi:

Đồ thị biểu diễn tất cả các khung được tạo ra khi chạy một chương trình, với một mũi tên chỉ từ khung gọi đến khung được gọi.

histogram:

Tập hợp các biến đếm.

giá trị nhớ:

Giá trị sau khi tính toán được lưu trữ để tránh phải tính lại sau này.

biến toàn cục:

Biến dược định nghĩa bên ngoài mọt hàm. Các biến toàn cục có thể được truy cập từ bất kì hàm nào.

cờ:

Biến kiểu boole được dùng để chỉ định một điều kiện có đúng hay không.

khai báo:

Lệnh kiểu như global để báo cho trình thông dịch biết thông tin về một biến.

Bài tập

Nếu bạn đã làm Bài tập duplicate, bạn đã có một hàm có tên has_duplicates để nhận vào một danh sách với vai trò tham biến và trả lại True nếu có bất kì đối tượng nào trong danh sách xuất hiện nhiều hơn một lần.

Hãy dùng một từ điển để viết một dạng nhanh hơn và đơn giản hơn cho has_duplicates.

Hai từ tạo thành một “cặp xoay” nếu như bạn xoay từ này để được từu kia (xem rotate_word ở Bài tập exrotate).

Hãy viết một chương trình đọc vào một danh sách các từ và tìm tất cả những cặp xoay.

Sau đây là một câu đố khác từ chương trình Car Talk: ⁴

Câu đố này được ông Dan O’Leary gửi đến. Ông bắt gặp một từ rất thông dụng; từ này có 5 chữ cái và chỉ một âm tiết, với đặc tính riêng như sau. Khi bạn bỏ đi chữ cái thứ nhất, các chữ cái còn lại sẽ hình thành một từ đồng âm với từ gốc. Bây giờ trả lại chữ cái thứ nhất và bỏ đi chữ cái thứ hai, một lần nữa ta lại thu được từ đồng âm với từ gốc. Câu hỏi là, từ gốc là gì?

Bây giờ tôi sẽ lấy thí dụ một từ chưa đạt yêu cầu. Hãy xét từ gồm 5 chữ cái sau, ‘wrack.’ W-R-A-C-K. Nếu tôi bỏ đi chữ cái thứ nhất, tôi được một từ bốn chữ cái ’R-A-C-K.’ À đó là một từ đồng âm, theo tiếng Anh. Bây giờ nếu bạn hoàn trả lại chữ ‘w’, và bỏ đi chữ ‘r’, bạn sẽ còn lại từ ‘wack’, cũng là một từ có nghĩa, chỉ có điều là không đồng âm với hai từ trước.

Tuy nhiên vẫn có ít nhất một từ mà Dan và chúng ta đều biết đến, một từ mà sẽ cho ra hai từ đồng âm khác gồm bốn chữ cái, khi ta bỏ đi lần lượt chữ cái thứ nhất và chữ cái thứ hai của từ gốc. Câu hỏi là, từ đó là gì?

Bạn có thể dùng từ điển trong Bài tập wordlist2 để kiểm tra xem một chuỗi có ở trong danh sách các từ hay không.

Để kiểm tra xem hai từ có đồng âm hay không, bạn có thể dùng Từ điển Phát âm CMU. Bạn có thể tải về từ www.speech.cs.cmu.edu/cgi-bin/cmudict hoặc thinkpython.com/code/c06d và bạn cũng có thẻ tải về thinkpython.com/code/pronounce.py, trong đó có hàm tên là read_dictionary. Hàm này đọc vào một từ điển phát âm và trả về một từ điển Python ánh xạ từ mỗi mục từ đến một chuỗi mô tả cách phát âm của nó.

Hãy viết một chương trình liệt kê tất cả các từ thỏa mãn yêu cầu của câu đố. Bạn có thể xem lời giải của tôi tại thinkpython.com/code/homophone.py.

---

1. Xem wikipedia.org/wiki/Memoization. ↩
2. Ở Python 3.0, kiểu long bị rút bỏ, tất cả số nguyên dù lớn đến đâu đều có kiểu int. ↩
3. en.wikipedia.org/wiki/RSA. ↩
4. www.cartalk.com/content/puzzler/transcripts/200717. ↩