Trở về Mục lục cuốn sách
Bộ là kiểu dữ liệu không thay đổi
Bộ là một dãy các giá trị. Các giá trị có thể thuộc kiểu dữ liệu bất kì, và chúng đánh thứ tự bởi các số nguyên, và vì vậy bộ khá giống với danh sách. Điểm khác nhau quan trọng là ở chỗ bộ có tính không thay đổi.
Về mặt cú pháp, một bộ là một dãy các giá trị được phân cách bởi dấu phẩy:
>>> t = 'a', 'b', 'c', 'd', 'e'
Mặc dù không cần thiết, nhưng người ta thường dùng cặp ngoặc tròn để bao lại phần nội dung của một bộ:
>>> t = ('a', 'b', 'c', 'd', 'e')
Để tạo ra một bộ với một phần tử duy nhất, bạn phải viết thêm một dấu phẩy ở phía cuối:
>>> t1 = 'a',
>>> type(t1)
<type 'tuple'>
Một giá trị ở trong cặp ngoặc tròn không phải là một bộ:
>>> t2 = ('a')
>>> type(t2)
<type 'str'>
Một cách làm khác để tạo ra một bộ là dùng hàm có sẵn tuple. Khi không có đối số, nó sẽ tạo ra một bộ rỗng:
>>> t = tuple()
>>> print t
()
Nếu đối số là một dãy (như chuỗi, danh sách hoặc bộ), thì kết quả sẽ là một bộ có chứa các phần tử của dãy đó:
>>> t = tuple('lupins')
>>> print t
('l', 'u', 'p', 'i', 'n', 's')
Vì tuple là tên của một hàm có sẵn, bạn cần tránh lấy nó đặt cho tên biến.
Hầu hết các toán tử với danh sách cũng có tác dụng đối với bộ. Toán tử ngoặc vuông để chỉ định một phần tử:
>>> t = ('a', 'b', 'c', 'd', 'e')
>>> print t[0]
'a'
Và toán tử lát cắt để chọn một khoảng các phần tử.
>>> print t[1:3]
('b', 'c')
Nhưng nếu bạn thử thay đổi một phần tử trong bộ, bạn sẽ bị báo lỗi:
>>> t[0] = 'A'
TypeError: object doesn't support item assignment
Bạn không thể sửa đổi được các phần tử của bộ, nhưng có thể thay thế một bộ với một bộ khác:
>>> t = ('A',) + t[1:]
>>> print t
('A', 'b', 'c', 'd', 'e')
Ta thường gặp tình huống cần tráo đổi giá trị của hai biến. Với câu lệnh gán truyền thống, bạn phải dùng một biến tạm thời. Chẳng hạn, để tráo đổi a với b:
>>> temp = a
>>> a = b
>>> b = temp
Cách giải này lủng củng; và phép gán với bộ sẽ đẹp hơn:
>>> a, b = b, a
Vế trái là một bộ các biến; vế phải là một bộ các biểu thức. Mỗi giá trị được gán cho biến tương ứng với nó. Tất cả các biểu thức ở vế phải đều được định lượng trước khi thực hiện gán.
Số các biến ở vế trái và số các giá trị ở vế phải cần phải bằng nhau:
>>> a, b = 1, 2, 3
ValueError: too many values to unpack
Tổng quát hơn, vế phải có thể là bất cứ dạng dãy nào (chuỗi, danh sách hoặc bộ). Chẳng hạn, để tách một địa chỉ email thành các phần tên người dùng và tên miền, bạn có thể viết:
>>> addr = 'monty@python.org'
>>> uname, domain = addr.split('@')
Giá trị trả về từ split là một dãy gồm hai phần tử; phần tử đầu được gán cho uname, phần tử thứ hai cho domain.
>>> print uname
monty
>>> print domain
python.org
Chặt chẽ mà nói, một hàm chỉ có thể trả về một giá trị, nhưng nếu giá trị đó là một bộ, thì tác dụng này cũng như là trả về nhiều giá trị. Chẳng hạn, nếu bạn muốn chia hai số tự nhiên để tìm ra thương và số dư, việc tính x/y trước rồi đến x%y là không hiệu quả. Cách tốt hơn là đồng thời tính chúng.
Hàm có sẵn divmod nhận vào hai đối số và trả về một bộ hai giá trị, là thương và số dư. Bạn có thể lưu kết quả dưới dạng một bộ:
>>> t = divmod(7, 3)
>>> print t
(2, 1)
Hoặc dùng phép gán với bộ để lưu các phần tử một cách riêng rẽ:
>>> quot, rem = divmod(7, 3)
>>> print quot
2
>>> print rem
1
Sau đây là ví dụ một hàm trả lại một bộ:
def min_max(t):
return min(t), max(t)
max và min là các hàm có sẵn để tìm các phần tử lớn nhất và nhỏ nhất trong một dãy. min_max tính cả hai và trả lại một bộ hai giá trị.
Bộ đối số có độ dài thay đổi
Số lượng các đối số cho một hàm là thay đổi được. Một tham biến mà tên bắt đầu bởi * sẽ thu gom các đối số vào trong một bộ. Chẳng hạn, printall nhận vào một số lượng đối số tùy ý và in chúng ra:
def printall(*args):
print args
Bạn có thể đặt tên tham biến dùng để thu gom là gì cũng được, nhưng args là một cái tên quy ước. Sau đây là cách dùng hàm này:
>>> printall(1, 2.0, '3')
(1, 2.0, '3')
Thao tác bổ sung cho thu gom là phát tán. Nếu bạn có một dãy các giá trị và muốn truyền cho một hàm dưới dạng nhiều đối số, bạn có thể dùng toán tử *. Chẳng hạn, divmod nhận vào đúng hai tham số; nó sẽ không hoạt động với một bộ:
>>> t = (7, 3)
>>> divmod(t)
TypeError: divmod expected 2 arguments, got 1
Nhưng nếu bạn phát tán bộ đó thì câu lệnh sẽ có tác dụng:
>>> divmod(*t)
(2, 1)
Rất nhiều hàm có sẵn sử dụng bộ đối số có chiều dài thay đổi. Chẳng hạn,
maxvàmincó thể nhận bao nhiêu đối số cũng được:>>> max(1,2,3) 3Nhưng
sumthì không thể.>>> sum(1,2,3) TypeError: sum expected at most 2 arguments, got 3Hãy viết một hàm có tên
sumallnhận vào bao nhiêu đối số cũng được và trả về tổng của chúng.
Danh sách và bộ
zip là một hàm có sẵn; nó nhận vào nhiều dãy và đan cài chúng vào một danh sách duy nhất1 chứa các bộ trong đó mỗi bộ có một phần tử của mỗi dãy. (zip là tên gọi của phéc-mơ-tuya có hình ảnh giống với thao tác đan cài này.) Ví dụ sau đan cài một chuỗi và một danh sách:
>>> s = 'abc'
>>> t = [0, 1, 2]
>>> zip(s, t)
[('a', 0), ('b', 1), ('c', 2)]
Kết quả là một danh sách các bộ trong đó mỗi bộ chứa một kí tự của chuỗi và phần tử tương ứng của danh sách ban đầu.
Nếu các dãy không có cùng độ dài thì kết quả sẽ dài bằng dãy ngắn hơn.
>>> zip('Anne', 'Elk')
[('A', 'E'), ('n', 'l'), ('n', 'k')]
Bạn có thể dùng phép gán bộ trong vòng lặp for để duyệt một danh sách các bộ:
t = [('a', 0), ('b', 1), ('c', 2)]
for letter, number in t:
print number, letter
Mỗi lần lặp, Python sẽ chọn ra bộ tiếp theo trong danh sách và gán các phần tử của nó cho letter và number. Kết quả đầu ra của vòng lặp này là:
0 a
1 b
2 c
Nếu kết hợp zip, for và phép gán bộ, bạn sẽ có một cách viết rất hữu ích để duyệt hai (hoặc nhiều) dãy cùng lúc. Chẳng hạn, has_match nhận vào hai dãy, t1 và t2, rồi trả lại True nếu có một chỉ số i sao cho t1[i] == t2[i]:
def has_match(t1, t2):
for x, y in zip(t1, t2):
if x == y:
return True
return False
Nếu cần duyệt các phần tử trong một dãy và các chỉ số của chúng, bạn có thể dùng hàm có sẵn enumerate:
for index, element in enumerate('abc'):
print index, element
Kết quả đầu ra của vòng lặp này là:
0 a
1 b
2 c
Một lần nữa.
Từ điển và bộ
Từ điển có một phương thức tên là items để trả lại một danh sách các bộ, trong đó mỗi bộ là một cặp khóa-trị2.
>>> d = {'a':0, 'b':1, 'c':2}
>>> t = d.items()
>>> print t
[('a', 0), ('c', 2), ('b', 1)]
Với từ điển, như bạn có thể đoán được, các mục đều không có một thứ tự nào.
Ngược lại, bạn có thể dùng danh sách các bộ để khởi tạo một từ điển mới:
>>> t = [('a', 0), ('c', 2), ('b', 1)]
>>> d = dict(t)
>>> print d
{'a': 0, 'c': 2, 'b': 1}
Kết hợp dict với zip ta được một cách nhanh gọn để tạo ra một từ điển:
>>> d = dict(zip('abc', range(3)))
>>> print d
{'a': 0, 'c': 2, 'b': 1}
Phương thức update của từ điển cũng nhận vào một danh sách các bộ và gộp chúng lại, theo các cặp khóa-trị, vào từ điển sẵn có.
Kết hợp items, phép gán bộ và for lại với nhau, bạn có một cách viết chương trình duyệt các khóa và trị của từ điển:
for key, val in d.items():
print val, key
Kết quả đầu ra của vòng lặp này là:
0 a
2 c
1 b
Giống như trước.
Bộ thường được dùng làm khóa trong từ điển (chủ yếu là vì bạn không thể dùng danh sách). Chẳng hạn, một danh bạ điện thoại có thể ánh xạ từ cặp họ, tên đến số điện thoại. Giả sử rằng ta đã định nghĩa ho, ten và so, ta có thể viết:
danhba[ho,ten] = so
Biểu thức trong ngoặc vuông là một bộ. Chúng ta có thể dùng phép gán cho bộ để duyệt từ điển này.
for ho,ten in danhba:
print ho, ten, danhba[ho,ten]
Vòng lặp này duyệt các khóa trong danhba, vốn là các bộ. Nó gán các phần tử của từng bộ cho ho và ten, sau đó in ra họ tên và số điện thoại tương ứng.
Có hai cách biểu diễn bộ trong một sơ đồ trạng thái. Cách chi tiết hơn chỉ rõ các chỉ số và phần tử giống như với danh sách. Chẳng hạn, bộ ('Cleese', 'John') sẽ được biểu diễn như sau:
Nhưng trong một sơ đồ lớn hơn bạn có thể muốn bỏ qua các chi tiết. Chẳng hạn, sơ đồ của một danh bạ điện thoại có thể như sau:
Ở đây các bộ được ghi dưới dạng cú pháp Python, cũng để ghi tắt trên sơ đồ.
Số điện thoại trong sơ đồ là đường dây góp ý cho đài phát thanh BBC, vậy nên bạn đừng gọi số đó.
So sách các bộ
Các toán tử quan hệ cũng có tác dụng với bộ và các dãy khác; Python bắt đầu với việc so sánh phần tử thứ nhất của từng dãy. Nếu chúng bằng nhau thì việc so sánh tiếp tục với các phần tiếp kế sau, và cứ như vậy, cho đến khi tìm được phần tử khác nhau. Các phần tử còn lại thì không được xét đến nữa (dù chúng có lớn đến đâu).
>>> (0, 1, 2) < (0, 3, 4)
True
>>> (0, 1, 2000000) < (0, 3, 4)
True
Hàm sort cũng hoạt động theo cách tương tự. Nó sắp xếp theo phần tử thứ nhất, nhưng nếu chúng bằng nhau thì xếp theo phần tử thứ hai, và cứ như vậy.
Đặc điểm này dựa trên một dạng mẫu có tên DSU, vốn là viết tắt của
- Decorate
- (“trang trí”) một dãy bằng cách tạo dựng một danh sách các bộ với một hoặc nhiều khóa sắp xếp đi trước những phần tử của dãy,
- Sort
- (sắp xếp) danh sách các bộ, và
- Undecorate
- (“gỡ bỏ trang trí”) bằng cách kết xuất các phần tử đã được sắp xếp của dãy.
Chẳng hạn, nếu bạn có một danh sách những từ cần sắp xếp từ dài đến ngắn:
def sort_by_length(words):
t = []
for word in words:
t.append((len(word), word))
t.sort(reverse=True)
res = []
for length, word in t:
res.append(word)
return res
Vòng lặp thứ nhất tạo dựng một danh sách các bộ, trong đó mỗi bộ là một từ và trước đó là chiều dài của từ đó.
sort thực hiện so sánh phần tử thứ nhất (tức độ dài) trước, và chỉ khi độ dài như nhau thì mới xét đến phần tử thứ hai. Từ khóa đối số reverse=True báo cho sort thực hiện theo chiều giảm dần.
Vòn lặp thứ hai duyệt danh sách các bộ và tạo dựng một danh sách các từ theo thứ tự giảm dần về độ dài.
Ở ví dụ này, để phân định thứ tự giữa các từ cùng độ dài sẽ dựa vào thứ tự của từ đó xếp trong bảng chữ cái. Trong trường hợp khác bạn có thể phân định theo tiêu chí ngẫu nhiên. Hãy sửa lại ví dụ này sao cho những từ cùng độ dài được xếp theo thứ tự ngẫu nhiên. Gợi ý: dùng hàm
randomtrong modulerandom.
Dãy chứa các dãy
Đến giờ tôi mới tập trung vào danh sách các bộ, nhưng hầu hết các ví dụ trong chương này cũng thực hiện được với danh sách chứa các danh sách, bộ chứa các bộ, và bộ chứa các danh sách. Để tránh phải liệt kê tất cả những sự kết hợp có thể, ta sẽ nói gọn là dãy chứa các dãy.
Trong nhiều trường hợp, những dạng khác nhau của dãy (chuỗi, danh sách và bộ) có thể được dùng hoán đổi cho nhau được. Vì vậy tại sao và bằng cách nào mà bạn lựa chọn dạng này thay vì dạng kia?
Bắt đầu với điều hiển nhiên, chuỗi thì có tính năng hạn chế rất nhiều so với các loại dãy khác vì những phần tử của nó chỉ có thể là kí tự. Chuỗi cũng là kiểu không thay đổi được. Nếu bạn muốn có tính năng thay đổi những kí tự trong chuỗi mà không muốn tạo ra một chuỗi mới, có lẽ bạn sẽ phải dùng một danh sách các kí tự để thay thế.
Danh sách thì thông dụng hơn bộ, chủ yếu là vì chúng thay đổi được. Nhưng cũng có một vài trường hợp bạn muốn dùng bộ hơn:
- Trong một số trường hợp, như trong câu lệnh
return, việc tạo ra một bộ thì đơn giản hơn một danh sách, về hình thức cú pháp. Trong những trường hợp khác, có thể bạn nên dùng danh sách. - Nếu muốn tạo một dãy để làm khóa cho từ điển, bạn phải dùng một kiểu dữ liệu không thay đổi như bộ hoặc chuỗi.
- Nếu bạn chuyển một dãy với vài trò đối số cho một hàm, việc dùng bộ sẽ làm giảm khả năng gây lỗi bắt nguồn từ tham chiếu bội.
Vì bộ là kiểu không thay đỏi được, chúng không có những phương thức như sort và reverse, vốn để sửa đổi một danh sách sẵn có. Nhưng Python lại cung cấp các hàm có sẵn sorted và reversed để nhận vào một chuỗi bất kì làm tham biến và trả lại một danh sách mới với cùng các phần tử theo một thứ tự khác.
Gỡ lỗi
Danh sách, từ điển và bộ thường được gọi chung là cấu trúc dữ liệu; trong chương này ta bắt đầu thấy những cấu trúc dữ liệu phứ hợp, như danh sách các bộ, và từ điển có khóa là các bộ và trị là các danh sách. Cấu trúc dữ liệu phức hợp rất có ích, nhưng chúng dễ mắc phải vấn đề mà tôi gọi là lỗi hình dạng; nghĩa là những lỗi phát sinh khi một cấu trúc dữ liệu có kiểu, kích thước hoặc cấu trúc sai. Chẳng hạn, nếu bạn trông đợi một danh sách có chứa một số nguyên mà tôi lại cho bạn một số nguyên (không phải danh sách) thì chương trình không hoạt động.
Để giúp cho việc gỡ lỗi kiểu như vậy, tôi đã viết một module có tên structshape trong đó có một hàm cùng tên structshape, nhận vào bất kì một cấu trúc dữ liệu nào làm đối số và trả về một chuỗi làm nhiệm vụ tóm lược lại hình dạng của nó. Bạn có thể tải nó về từ thinkpython.com/code/structshape.py
Sau đây là kết quả cho một dãy đơn giản:
>>> from structshape import structshape
>>> t = [1,2,3]
>>> print structshape(t)
list of 3 int
Một chương trình đẹp hơn có thể in ra “list of 3 ints”, nhưng không tính đến danh từ số nhiều thì sẽ dễ hơn. Sau đây là một danh sách các danh sách:
>>> t2 = [[1,2], [3,4], [5,6]]
>>> print structshape(t2)
list of 3 list of 2 int
Nếu các phần tử của danh sách không có cùng kiểu thì structshape sẽ nhóm chúng lại theo dạng, đúng theo thứ tự:
>>> t3 = [1, 2, 3, 4.0, '5', '6', [7], [8], 9]
>>> print structshape(t3)
list of (3 int, float, 2 str, 2 list of int, int)
Sau đây là một danh sách các bộ:
>>> s = 'abc'
>>> lt = zip(t, s)
>>> print structshape(lt)
list of 3 tuple of (int, str)
Và sau đây là một từ điển có 3 mục trong đó ánh xạ số nguyên đến chuỗi.
>>> d = dict(lt)
>>> print structshape(d)
dict of 3 int->str
Nêu bạn vẫn vướng mắc trong việc theo dõi các cấu trúc dữ liệu thì structshape có thể sẽ hữu ích.
Thuật ngữ
- bộ:
- Dãy các phần tử không thể thay đổi được.
- phép gán bộ:
- Phép gán với một dãy ở vế phải và một bộ các biến ở vế trái. Vế phải được định lượng và sau đó các phần tử của nó được gán cho các biến ở vế trái.
- thu gom:
- Thao tác tập hợp một bộ các đối số có độ dài thay đổi.
- phát tán:
- Thao tác xử lý dãy như một danh sách các đối số.
- DSU:
- Viết tắt của “decorate-sort-undecorate”, một dạng mẫu bao gồm tạo dựng một danh sách các bộ, sắp xếp, và kết xuất một phần của kết quả.
- cấu trúc dữ liệu:
- Tập hợp các giá trị có liên hệ với nhau, thường được tổ chức dưới dạng danh sách, từ điển, bộ, v.v.
- hình dạng (của cấu trúc dữ liệu):
- Dạng tóm lược của kiểu, hình dạng và thành phần của một cấu trúc dữ liệu.
Bài tập
Hãy viết một hàm có tên
most_frequentnhận vào một chuỗi và in ra các chữ cái theo thứ tự tần số xuất hiện giảm dần. Hãy tìm những đoạn văn viết bằng vài thứ tiếng khác nhau và xem tần số chữ cái của chúng khác nhau thế nào. So sách kết quả bạn tìm được với bảng thống kê tạiwikipedia.org/wiki/Letter_frequencies.
Thêm bài về đảo chữ!
- Hãy viết một chương trình đọc vào danh sách các từ trong một file (xem Mục {wordlist}) và in ra tất cả tập hợp các từ gồm những chữ cái đảo nhau.
Sau đây là một ví dụ kết quả có thể tìm được:
['deltas', 'desalt', 'lasted', 'salted', 'slated', 'staled'] ['retainers', 'ternaries'] ['generating', 'greatening'] ['resmelts', 'smelters', 'termless']Gợi ý: có thể bạn muốn lập một từ điển trong đó ánh xạ từ một tập hợp những chữ cái đến một danh sách những từ viết được từ những chữ cái đó. Câu hỏi là, bạn biểu diễn tập hợp chữ cái đó như thế nào để chúng có thể làm khóa của từ điển?
- Sửa chương trình trên để in ra tập hợp các từ đảo lớn nhất trước, sau đến tập hợp lớn thứ hai, và cứ như vậy.
- Trong trò chơi Scrabble, “bingo” là trường hợp khi bạn dùng hết toàn bộ bảy mảnh chữ trên khay của mình, cùng với một mảnh chữ sẵn có trên bảng, để tạo thành một từ gồm tám chữ cái. Tập hợp 8 chữ cái nào có nhiều khả năng hình thành bingo nhất? Gợi ý: tập hợp này tạo thành được 7 từ.
- Hai từ tạo thành một “cặp hoán đổi” nếu bạn có thể chuyển từ này thành từ kia chỉ bằng cách đổi chỗ hai chữ cái3; chẳng hạn, “converse” và “conserve”. Hãy viết một chương trình để tìm tất cả các cặp hoán đổi trong từ điển. Gợi ý: đừng kiểm tra tất cả những cặp hai từ, cũng đừng kiểm tra tất cả các khả năng hoán đổi.
Bạn có thể tải về một lời giải ở
thinkpython.com/code/anagram_sets.py.
Sau đây là một câu đố Car Talk khác4:
Từ tiếng Anh nào dài nhất có đặc điểm sau, mỗi khi ta lần lượt bỏ bớt một chữ cái thì nó vẫn còn có nghĩa?
Cụ thể, chữ cái bỏ đi có thể ở đầu, cuối, hoặc giữa từ, nhưng sau khi bỏ không được sắp xếp lại vị trí các chữ còn lại. Mỗi khi bỏ đi một chữ, bạn giữ lại một từ tiếng Anh khác. Cứ tiếp tục như vậy, cuối cùng bạn sẽ còn một chữ cái và chữ cái này cũng phải là một từ tiếng Anh có nghĩa— tức là có trong từ điển. Tôi muốn biết rằng từ dài nhất như vậy là gì và nó có mấy chữ cái?
Tôi sẽ cho bạn một từ ngắn làm ví dụ: Sprite. Được chứ? Bắt đầu với sprite, bạn bỏ bớt một chữ cái trong từ đó, bỏ chữ r đi, và chúng ta còn lại từ spite, sau đó ta bỏ chữ cái e ở cuối, ta còn lại từ spit, ta bỏ đi chữ s, ta còn lại từ pit, it, và I.
Hãy viết một chương trình để tìm tất cả những từ có thể lược đi kiểu này, và sau đó tìm ra từ dài nhất trong số đó.
Bài tập này khó hơn một chút so với các bài khác trong cuốn sách này, và tôi có một số gợi ý sau:
- Bạn có thể sẽ muốn viết một hàm nhận vào một từ và tìm ra danh sách của tất cả các từ có thể hình thành được sau khi bỏ một chữ cái. Đó là những “từ con” của từ ban đầu.
- Theo cách đệ quy, một từ được gọi là lược bớt được nếu như mọi từ con của nó đều lược bớt được. Ở trường hợp cơ bản, có thể coi rằng một chuỗi rỗng là lược bớt được.
- Danh sách từ mà tôi cung cấp,
words.txt, không chứa các từ có một chữ cái. Vì vậy bạn có thể muốn thêm vào “I”, “a”, và chuỗi rỗng.- Để cải thiện tốc độ của chương trình, bạn có thể sẽ cần phải ghi nhớ những từ đã xác định là lược bỏ được.
Bạn có thể xem lời giải của tôi ở
thinkpython.com/code/reducible.py.
- Trong Python 3.0,
ziptrả lại một nguồn lặp các bộ, nhưng thường thì người ta vẫn coi một nguồn lặp tựa như một danh sách. ↩ - Điều này sẽ hơi khác trong Python 3.0. ↩
- Bài tập này được hình thành từ một ví dụ tại
puzzlers.org. ↩ www.cartalk.com/content/puzzler/transcripts/200651. ↩
Blog của Chiến 
Pingback: Think Python: Cách tư duy như nhà khoa học máy tính | Blog của Chiến
Pingback: Phụ lục: Lumpy | Blog của Chiến