Chương 10: Danh sách

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

Danh sách là một dãy

Cũng như một chuỗi, danh sách cũng là một dãy các giá trị. Trong một chuỗi, các giá trị đó là những kí tự; trong một danh sách, chúng có thể thuộc kiểu bất kì. Các giá trị trong một danh sách được gọi là các phần tử.

Có một vài cách khác nhau để tạo ra một danh sách mới; cách đơn giản nhất là bao quanh các phần tử bằng một cặp ngoặc vuông ([ và ]):

[10, 20, 30, 40]
['crunchy frog', 'ram bladder', 'lark vomit']

Ở ví dụ thứ nhất bên trên, danh sách bao gồm 4 số nguyên. danh sách thứ hai thì có ba chuỗi. Các phần tử trong một danh sách không nhất thiết có cùng kiểu. danh sách sau đây bao gồm một chuỗi, một số có phần thập phân, một số nguyên, và (a ha!) một danh sách khác nữa:

['spam', 2.0, 5, [10, 20]]

Một danh sách nằm trong một danh sách khác thì được gọi là lồng ghép.

Một danh sách không chứa phần tử nào được gọi là danh sách trống; bạn có thể tạo ra một dánh sách trống bầng một cặp ngoặc kép liền nhau, [].

Đúng như bạn có thể nghĩ đến, ta có thể gán các giá trị trong danh sách cho các biến:

>>> cheeses = ['Cheddar', 'Edam', 'Gouda']

>>> numbers = [17, 123]
>>> empty = []
>>> print cheeses, numbers, empty
['Cheddar', 'Edam', 'Gouda'] [17, 123] []

Cú pháp để thực hiện việc truy cập từng phần tử của một danh sách cũng giống như truy cập từng kí tự trong một chuỗi—đó là dùng toán tử ngoặc vuông. Biểu thức bên trong cặp ngoặc vuông xác định chỉ số. Chú ý rằng chỉ số bắt đầu từ 0:

>>> print cheeses[0]
Cheddar

Khác với các chuỗi, danh sách là kiểu dữ liệu thay đổi được. Khi toán tử ngoặc vuông xuất hiện ở vế trái một lệnh gán, nó sẽ chỉ định phần tử của danh sách cần được gán.

>>> numbers = [17, 123]

>>> numbers[1] = 5
>>> print numbers
[17, 5]

Phần tử có chỉ số 1 của numbers, trước đó là phần tử 123, giờ đã được thay bằng 5.

Bạn có thể hình dung danh sách như là một mối quan hệ giữa các chỉ số và phần tử. Mối quan hệ này được gọi là đánh số; mỗi chỉ số được “đánh” cho mỗi phần tử. Sau đây là một biểu đồ trạng thái biểu thị cheeses, numbers và empty:

Các danh sách được biểu thị bởi những khối với từ “list” ghi bên ngoài và các phần tử ở bên trong nó. cheeses tương ứng với một danh sách với ba phần tử được đánh chỉ số 0, 1 và 2. numbers gồm có hai phần tử; và biểu đồ cho thấy rằng giá trị của phần tử thứ hai đã được gán lại từ 123 thành 5. empty ứng với một danh sách không chứa phần tử nào.

Các chỉ số trong dãy cũng có tác dụng như chỉ số của chuỗi:

• Bất kì một biểu thức số nguyên nào cũng có thể được dùng làm chỉ số.
• Nếu bạn cố gắng đọc hoặc ghi một phần tử mà bản thân nó không tồn tại, bạn sẽ gặp phải lỗi IndexError.
• Nếu một chỉ số có giá trị âm, nó sẽ được đếm ngược từ phía cuối danh sách.

Toán tử in cũng dùng được với các danh sách.

>>> cheeses = ['Cheddar', 'Edam', 'Gouda']

>>> 'Edam' in cheeses
True
>>> 'Brie' in cheeses
False

Duyệt danh sách

Cách thông dụng nhất để duyệt các phần tử trong một danh sách là dùng một vòng lặp for. Cú pháp cũng tương tự như với chuỗi:

for cheese in cheeses:
    print cheese

Cách này sẽ tốt nếu bạn chỉ cần đọc các phần tử trong danh sách. Nhưng nếu bạn cần ghi hoặc cập nhật các phần tử trong danh sách, bạn phải dùng đến chỉ số. Một cách làm hay dùng là kết hợp các hàm range và len:

for i in range(len(numbers)):
    numbers[i] = numbers[i] * 2

Vòng lặp này duyệt danh sách và cập nhật từng phần tử. len trả về số phần tử có trong danh sách. range trả về một danh sách các chỉ số từ 0 đến n - 1, trong đó n là chiều dài của danh sách. Mỗi lần đi qua vòng lặp, i sẽ nhận giá trị chỉ số của phần tử kế tiếp. Lệnh gán trong phần thân sẽ dùng i để đọc giá trị cũ của phần tử và gán giá trị mới.

Một vòng lặp for áp dụng với danh sách trống sẽ không bao giờ thực hiện phân thân câu lệnh:

for x in empty:
    print 'Không bao giờ được thực hiện.'

Mặc dù một danh sách có thể bao gồm một danh sách khác, danh sách được lồng ghép bên trong vẫn được tính như một phần tử đơn lẻ. Chiều dài của danh sách này là 4:

['spam', 1, ['Brie', 'Roquefort', 'Pol le Veq'], [1, 2, 3]]

Các phép toán với danh sách

Toán tử + có tác dụng ghép nối các danh sách:

>>> a = [1, 2, 3]
>>> b = [4, 5, 6]
>>> c = a + b
>>> print c
[1, 2, 3, 4, 5, 6]

Cũng tương tự như vậy, toán tử * lặp lại một danh sách với số lần định trước:

>>> [0] * 4
[0, 0, 0, 0]
>>> [1, 2, 3] * 3
[1, 2, 3, 1, 2, 3, 1, 2, 3]

Ví dụ thứ nhất lặp lại [0] bốn lần. Ví dụ thứ hai lặp lại danh sách [1, 2, 3] ba lần.

Lát cắt trong danh sách

Toán tử lát cắt cũng có tác dụng với các danh sách:

>>> t = ['a', 'b', 'c', 'd', 'e', 'f']
>>> t[1:3]
['b', 'c']

>>> t[:4]
['a', 'b', 'c', 'd']
>>> t[3:]
['d', 'e', 'f']

Nếu bạn bỏ qua chỉ số thứ nhất, lát cắt sẽ bắt đầu từ vị trí đầu tiên cảu danh sách. Nếu bạn bỏ qua chỉ số thứ hai, lát cắt sẽ kéo dài đến cuối danh sách. Vì vậy nếu bạn bỏ qua cả hai chỉ số, lát cắt sẽ là một bản sao của toàn bộ danh sách.

>>> t[:]
['a', 'b', 'c', 'd', 'e', 'f']

Vì các danh sách có tính thay đổi cho nên sao chép là việc ta nên làm trước khi thực hiện các thao tác gấp, xoay, hoặc chia nhỏ danh sách.

Một toán tử bên vế trái cảu phép gán có thể cập nhật cùng lúc nhiều phân tử:

>>> t = ['a', 'b', 'c', 'd', 'e', 'f']
>>> t[1:3] = ['x', 'y']

>>> print t
['a', 'x', 'y', 'd', 'e', 'f']

Python cung cấp các phương thức hoạt động với danh sách. Chẳng hạn, append thêm một phân tử mới vào cuối một danh sách:

>>> t = ['a', 'b', 'c']
>>> t.append('d')
>>> print t
['a', 'b', 'c', 'd']

extend nhận vào danh sách như một tham biến và tiếp nối tất cả các phần tử chứa trong danh sách đó:

>>> t1 = ['a', 'b', 'c']
>>> t2 = ['d', 'e']
>>> t1.extend(t2)
>>> print t1
['a', 'b', 'c', 'd', 'e']

Ở ví dụ trên, t2 không bị thay đổi.

sort sắp xếp các phần tử của danh sách từ thấp lên cao:

>>> t = ['d', 'c', 'e', 'b', 'a']
>>> t.sort()
>>> print t
['a', 'b', 'c', 'd', 'e']

Các phương thức với danh sách đều trống; chúng chỉ thay đổi danh sách và trả về None. Nếu bạn viết t = t.sort(), bạn sẽ thất vọng với kết quả nhận được.

Map, filter và reduce

Để cộng tất cả các số có trong một danh sách lại, bạn có thể dùng vòng lặp như sau:

def add_all(t):
    total = 0
    for x in t:
        total += x
    return total

total ban đầu được gán bằng 0. Mỗi lần chạy vòng lặp, x nhận một phần tử từ danh sách. Toán tử += giúp ta cập nhật biến theo cách viết gọn gàng nhất. Câu lệnh gán rút gọn sau:

    total += x

tương đương với:

    total = total + x

Khi vòng lặp được thực hiện, total sẽ tích lũy tổng của các phần tử; một biến được dùng theo cách này đôi khi còn được gọi là biến tích lũy.

Việc cộng các phần tử trong một danh sách là thao tác rất thường gặp, và vì vậy Python có sẵn một hàm sum:

>>> t = [1, 2, 3]
>>> sum(t)
6

Một thao tác như thế này, thực hiện dồn một dãy các phần tử vào một giá trị đơn lẻ, đôi khi còn được gọi là rút gọn.

Đôi khi bạn muốn duyệt một danh sách trong khi đồng thời lại tạo một danh sách khác. Chẳng hạn, hàm sau đây nhận vào một danh sách các chuỗi và trả về một danh sách mới bao gồm các chuỗi với kiểu chữ in:

def capitalize_all(t):
    res = []
    for s in t:
        res.append(s.capitalize())
    return res

res được khởi tạo với một danh sách trống; mỗi lần chạy qua vòng lặp, ta thêm vào đó phần tử tiếp theo. Vì vậy, res cũng là một kiểu biến tích lũy khác.

Một thao tác kiểu như capitalize_all (chuyển chữ in toàn bộ) đôi khi được coi tương đương như việc đánh số vì nó dùng một hàm (trong trường hợp này là phương thức capitalize) để “đánh” cho mỗi phần tử trong một dãy.

Một thao tác thường gặp khác là chọn một số các phần tử từ danh sách và trả về một danh sách con. Chẳng hạn, hàm sau đây nhận vào một danh sách các chuỗi và sau đó trả về một danh sách trong đó chỉ bao gồm các chuỗi viết bằng chữ in:

def only_upper(t):
    res = []
    for s in t:
        if s.isupper():
            res.append(s)
    return res

isupper là một phương thức chuỗi trả về True nếu như chuỗi chỉ bao gồm các chữ cái viết in.

Một thao tác kiểu như only_upper được gọi là lọc vì nó chọn ra một số các phần tử đồng thời lọc bỏ các phần tử khác.

Các thao tác thông dụng nhất với danh sách hầu như đều có thể biểu diễn được dưới dạng kết hợp của đánh số, lọc và rút gọn. Vì những thao tác này quá thông dụng nên Python cung cấp cho ta nhưng đặc điểm ngôn ngữ để hỗ trợ chúng, bao gồm hàm có sẵn map và một toán tử có tên là “list comprehension”.

Hãy viết một hàm trong đó nhận vào một danh sách các số và trả về tổng lũy tích, nghĩa là một danh sách mới trong đó phần tử thứ i chính là tổng của i + 1 phần tử đầu trong danh sách nhận vào. Chẳng hạn, tổng lũy tích của [1, 2, 3] là [1, 3, 6].

Xóa các phần tử

Có một vài cách làm khác nhau để xóa phần tử khỏi một danh sách. Nếu đã biết chỉ số của phần tử bạn cần xóa, bạn có thể dùng pop:

>>> t = ['a', 'b', 'c']
>>> x = t.pop(1)
>>> print t
['a', 'c']
>>> print x
b

pop thay đổi danh sách và trả lại phần tử mà ta vừa xóa khỏi danh sách. Nếu bạn không cung cấp chỉ số, nó sẽ xóa và trả lại phần tử cuối cùng.

Nếu không cần giá trị cần được loại khỏi danh sách, bạn có thể dùng toán tử del:

>>> t = ['a', 'b', 'c']
>>> del t[1]
>>> print t
['a', 'c']

Nếu bạn biết phần tử cần được xóa (nhưng không biết chỉ số), bạn có thể dùng remove:

>>> t = ['a', 'b', 'c']

>>> t.remove('b')
>>> print t
['a', 'c']

Giá trị trả về tử remove là None.

Để xóa nhiều hơn một phần tử, bạn có thể dùng del với một lát cắt chỉ số:

>>> t = ['a', 'b', 'c', 'd', 'e', 'f']
>>> del t[1:5]
>>> print t
['a', 'f']

Như thường lệ, lát cắt sẽ chọn ra tất cả những phần tử cho đến trước (không bao gồm) chỉ số thứ hai.

Danh sách và chuỗi

Một chuỗi là một dãy các kí tự và một danh sách là một dãy các giá trị, nhưng một danh sách các kí tự lại không giống như một chuỗi. Để chuyển từ một chuỗi sang một danh sách các kí tự, bạn có thể dùng list:

>>> s = 'spam'

>>> t = list(s)
>>> print t
['s', 'p', 'a', 'm']

Vì list cũng giống như tên của một hàm dựng sẵn, nên bạn cần tránh đặt nó làm tên một biến. Tôi cũng tránh dùng l vì nó trông rất giống như số 1. Vì vậy tôi thường dùng t.

Hàm list phá vỡ một chuỗi thành các kí tự riêng lẻ. Nếu muốn phá vỡ chuỗi thành các từ riêng lẻ, bạn có thẻ dùng phương thức split:

>>> s = 'pining for the fjords'
>>> t = s.split()
>>> print t
['pining', 'for', 'the', 'fjords']

Bạn có thể kèm theo một đối số là một dấu phân cách chính là kí tự được dùng để ngăn cách giữa các từ. Ví dụ sau đây có sử dụng dấu gạch nối để phân cách:

>>> s = 'spam-spam-spam'
>>> delimiter = '-'
>>> s.split(delimiter)
['spam', 'spam', 'spam']

join là hàm ngược của split. Nó nhận vào một dãy các chuỗi và nối chúng lại. join là một phương thức chuỗi, vì vậy bạn phải gọi nó từ biến là dấu phân cách và sau đó truyền vào tham biến là danh sách:

>>> t = ['pining', 'for', 'the', 'fjords']

>>> delimiter = ' '
>>> delimiter.join(t)
'pining for the fjords'

Trong trường hợp này, biến phân cách (delimiter) là một kí tự dấu cách, vì vậy join đặt dấu cách giữa hai từ liên tiếp. Để nối liền các chuỗi mà không bị ngăn cách, bạn có thể dùng chuỗi rỗng, '', vào vai trò của dấu phân cách.

Đối tượng và giá trị

Nếu ta thực hiện các lệnh gán sau:

a = 'banana'
b = 'banana'

Ta biết rằng cả a và b đều tham chiếu đến một chuỗi, nhưng ta không biết rằng liệu chúng có tham chiếu đến cùng một chuỗi không. Sau đây là hai trường hợp có thể xảy ra:

Trong một trường hợp, a và b tham chiếu đến hai đối tượng khác nhau nhưng có cùng giá trị. Trong trường hợp thứ hai, chúng cùng tham chiếu đến một đối tượng.

Để kiểm tra xem liệu hai biến có cùng tham chiếu đến một đối tượng hay không, bạn có thể dùng toán tử is.

>>> a = 'banana'
>>> b = 'banana'
>>> a is b
True

Ở ví d này, Python chỉ tạo ra một đối tượng chuỗi, và cả a và b đều tham chiếu đến nó.

Nhưng khi bạn tạo ra hai danh sách, bạn sẽ thu được hai đối tượng riêng biệt:

>>> a = [1, 2, 3]
>>> b = [1, 2, 3]
>>> a is b
False

Vì vậy sơ đồ trạng thái sẽ trông như thế này:

Trong trường hợp này ta nói rằng hai danh sách là tương đương nhau, vì chúng có những phần tử giống nhau, nhưng không đồng nhất, vì chúng không cùng là một đối tượng. Nếu hai đối tượng đồng nhất nhau thì đồng thời cũng tương đương nhau, nhưng ngược lại nếu chúng tương đương thì không nhất thiết phải đồng nhất.

Đến giờ, ta đã dùng các khái niệm “đối tượng” và “giá trị” để thay thế được cho nhau, nhưng sẽ chính xác hơn nếu nói rằng mỗi đối tượng có một giá trị. Nếu bạn thực hiện biểu thức [1,2,3], bạn sẽ có một đối tượng mà giá trị của nó là một chuỗi các số nguyên. Nếu một danh sách khác có những phần tử như vậy, ta nói rằng chúng có cùng giá trị, nhưng hai danh sách này vẫn là những đối tượng khác nhau.

Tham chiếu bội

Nếu a tham chiếu đến một đối tượng và bạn gán b = a, thì cả hai biến sẽ cùng chỉ đến một đối tượng:

>>> a = [1, 2, 3]
>>> b = a

>>> b is a
True

Sơ đồ trạng thái sẽ trông như thế này:

Việc gắn một biến với một đối tượng được gọi là tham chiếu. Ở ví dụ này, có hai tham chiếu đến cùng một đối tượng

Một đối tượng có nhiều tham chiếu thì cũng có nhiều tên, và chúng ta nói rằng đối tượng này được tham chiếu bội.

Nếu như đối tượng được tham chiếu bội có thể thay đổi được, thì những thay đổi thực hiện với tham chiếu này cũng sẽ ảnh hưởng với tham chiếu kia:

>>> b[0] = 17
>>> print a
[17, 2, 3]

Mặc dù tính chất này có thể hữu dụng nhưng chắc chắn rất dễ gây lỗi. Nhìn chung, để an toàn ta nên tránh tham chiếu bội khi thao tác với các đối tượng thay đổi được.

Với các đối tượng không thay đổi như chuỗi, tham chiếu bội không còn là vấn đề. Trong ví dụ này:

a = 'banana'
b = 'banana'

Hầu như không có khác biệt nào trong việc liệu a và b có tham chiếu đến cùng một chuỗi hay không.

Danh sách với vai trò như đối số

Khi bạn truyền một danh sách vào trong hàm, thì hàm sẽ nhận được một tham chiếu đến danh sách đó. Nếu hàm thay đổi một tham biến danh sách, thì đoạn chương trình gọi sẽ thấy được sự thay đổi đó. Chẳng hạn, delete_head xóa phần tử đầu khỏi danh sách:

def delete_head(t):
    del t[0]

Đây là khi hàm này được dùng:

>>> letters = ['a', 'b', 'c']
>>> delete_head(letters)
>>> print letters
['b', 'c']

Tham biến t và biến letters là các tham chiếu bội đến cùng một đối tượng. Sơ đồ ngăn xếp sẽ trông như sau:

Vì danh sách được dùng chung bởi hai khung riêng biệt nên tôi đã vẽ nó giữa hai khung này.

Điều quan trọng là phân biết được các phép thao tác nhằm thay đổi danh sách và thao tác nhằm tạo những danh sách mới. Chẳng hạn, phương thức append thay đổi một danh sách, nhưng toán tử + lại tạo ra một danh sách mới:

>>> t1 = [1, 2]
>>> t2 = t1.append(3)
>>> print t1
[1, 2, 3]
>>> print t2
None

>>> t3 = t1 + [3]
>>> print t3
[1, 2, 3]
>>> t2 is t3
False

Khác biệt này có thể trở nên quan trọng khi bạn viết những hàm lẽ ra được dùng để thay đổi danh sách. Chẳng hạn, hàm sau đây không xóa được phần tử đầu của danh sách:

def bad_delete_head(t):
    t = t[1:]              # SAI!

Toán tử lát cắt sẽ tạo ra một danh sách mới và lệnh gán làm cho t tham chiếu đến đó, nhưng tất cả những điều này đều không thay đổi gì đến danh sách vốn được truyền vào với vai trò như một đối số.

Một cách làm khác là viết một hàm để tạo ra và trả lại một danh sách mới. Chẳng hạn, tail trả lại toàn bộ danh sách chỉ trừ phần tử đầu tiên:

def tail(t):
    return t[1:]

Hàm này sẽ giữ nguyên, không làm thay đổi danh sách ban đầu. Sau đây là một cách dùng nó:

>>> letters = ['a', 'b', 'c']

>>> rest = tail(letters)
>>> print rest
['b', 'c']

Hãy viết một hàm có tên là chop trong đó nhận vào một danh sách và thay đổi nó, xóa đi các phần tử đầu và phần tử cuối, rồi trả về None.

Sau đó viết một hàm có tên là middle trong đó nhận vào một danh sách và trả về một danh sách mới bao gồm tất cả những phần tử chỉ trừ hai phần tử đầu và cuối của danh sách gốc.

Gỡ lỗi

Sự bất cẩn khi dùng danh sách (và các đối tượng thay đổi được khác) có thể dẫn đến mất thời gian hàng giờ đồng hồ để gỡ lỗi. Sau đây là một số lỗi thường gặp và cách phòng tránh:

1. Đừng quên rằng hầu hết các phương thức làm việc với danh sách đều thay đổi danh sách (trong vai trò đối số) và trả về None. Điều này ngược lại với các phương thức chuỗi trong đó trả về một chuỗi mới và giữ nguyên chuỗi cũ.

   Nếu bạn quen viết mã lệnh với chuỗi như sau:

   word = word.strip()
   

   thì cũng rất dễ bị hấp dẫn bởi cách viết mã lệnh này đối với danh sách:

   t = t.sort()           # SAI!
   

   Vì sort trả về None nên thao tác tiếp theo thực hiện với t dường như sẽ bị hỏng.

   Trước khi dùng những phương thức và toán tử thực hiện trên danh sách, bạn cần đọc kĩ tài liệu và sau đó thử chúng ở chế độ tương tác lệnh. Các phương thức và toán tử có chung giữa danh sách và những kiểu dãy khác (như chuỗi) được mô tả ở docs.python.org/lib/typesseq.html. Các phương thức và toán tử chỉ áp dụng được cho những dãy thay đổi được có ở docs.python.org/lib/typesseq-mutable.html.

2. Chọn một cách viết mã lệnh và dùng nó một cách thống nhất.

   Một trong số các nguyên nhân gây ra rắc rối liên quan đến danh sách là có quá nhiều cách thực hiện cùng một công việc. Chẳng hạn để xóa một phần tử khỏi một danh sách, bạn có thể dùng pop, remove, del, hoặc thậm chí một câu lệnh gán với lát cắt.

   Để thêm vào một phần tử, bạn có thể dùng phương thức append hoặc toán tử + Nhưng đừng quên rằng hai cách sau đây là đúng:

   t.append(x)
   t = t + [x]
   

   và tất cả những cách viết sau đều sai:

   t.append([x])          # SAI!
   t = t.append(x)        # SAI!
   t + [x]                # SAI!
   t = t + x              # SAI!
   

   Hãy thử lại tất cả những ví dụ trên trong chế độ tương tác lệnh và nắm vững được tác dụng của chúng. Lưu ý rằng chỉ có lệnh cuối cùng mới gây ra một lỗi thực thi; còn ba lệnh trên nó đều hợp lệ, nhưng thực hiện việc mà chúng ta không cần đến.

3. Tạo ra các bản sao để tránh tham chiếu bội.

   Nếu muốn dùng một phương thức như sort để thay đổi đối số (là danh sách) nhưng cũng cần giữ cả danh sách ban đầu, bạn có thể tạo một bản sao.

   orig = t[:]
   t.sort()
   

   Ở ví dụ này bạn cũng có thẻ dùng hàm có sẵn sorted, với trả lại một danh sách mới, được sắp xếp, đồng thời giữ nguyên danh sách ban đầu. Nhưng trong trường hợp đó bạn cần tránh lấy sorted để đặt cho tên biến!

Thuật ngữ

danh sách:

Một dãy các giá trị.

phần tử:

Một trong số các giá trị của danh sách (hoặc một dãy nói chung).

chỉ số:

Một giá trị số nguyên để chỉ định một phần tử trong danh sách.

danh sách lồng ghép:

Một danh sách đóng vai trò là phần tử trong một danh sách khác.

duyệt danh sách:

Cách truy cập tuần tự từng phần tử trong danh sách.

đánh số:

Mối quan hệ trong đó từng phần tử của một tập hợp tương ứng với một phần tử trong tập hợp khác. Chẳng hạn, một danh sách là một phép đánh số giữa các chỉ số với các phần tử.

biến tích lũy:

Một biến được dùng trong vòng lặp để cộng dồn hoặc, nói chung là tích lũy để thu được một kết quả.

gán rút gọn:

Một lệnh nhằm cập nhật giá trị của một biến bằng cách dùng toán tử kiểu như +=.

rút gọn:

Một dạng mẫu xử lý trong đó bao gồm duyệt một dãy và tính tích lũy với từng phần tử để gộp thành một kết quả cuối cùng.

map:

Một dạng mẫu xử lý duyệt chuỗi và thực hiện thao tác tính toán với từng phần tử.

lọc:

Một dạng mẫu xử lý duyệt chuỗi và lựa chọn những phần tử thỏa mãn một điều kiện nào đó.

đối tượng:

Thứ mà biến có thể tham chiếu đến được. Một đối tượng có kiểu và giá trị riêng của nó.

tương đương:

Có cùng giá trị.

đồng nhất:

Cùng là một đố tượng (và mặc nhiên là tương đương).

tham chiếu:

Sự liên hệ giữa một biến và giá trị của nó.

tham chiếu bội:

Trường hợp trong đó hai hoặc nhiều biến cùng tham chiếu đến một đối tượng.

dấu phân cách:

Một kí tự hoặc chuỗi được dùng để chỉ định những chỗ mà chuỗi cho trước cần được tách.

Bài tập

Hãy viết một hàm có tên là is_sorted trong đó nhận vào tham biến là một danh sách và trả về True nếu danh sách đã được xếp teho thứ tự tăng dần và False trong trường hợp còn lại. Bạn có thể giả sử rằng (qua khâu xử lý sơ bộ) danh sách chứa các phần tử có thể so sánh được bằng các toán tử quan hệ <, >, v.v.

Chẳng hạn, is_sorted([1,2,2]) sẽ trả về True và is_sorted(['b','a']) trả về False.

Hai từ là đảo của nhau nếu bạn có thể đảo các chữ cái trong từ này để hình thành nên từ kia. Hãy viết một hàm có tên là is_anagram nhận vào hai chuỗi và trả về True nếu chúng là đảo của nhau.

Nghịch lý “Ngày sinh nhật”:

Hãy viết một hàm có tên là has_duplicates trong đó nhận vào một danh sách và trả về True nếu có bất kì phần tử nào xuất hiện nhiều hơn một lần. Danh sách ban đầu không được thay đổi.

Nếu như có 23 sinh viên trong lớp học của bạn, khả năng có được hai người trùng ngày sinh với nhau là bao nhiêu? Bạn có thể ước lượng khả năng (xác suất) này bằng cách phát sinh ra mẫu ngẫu nhiên gồm 23 ngày sinh rồi kiểm tra sự trùng lặp. Gợi ý: Bạn có thể phát sinh những ngày sinh ngẫu nhiên bằng hàm randint trong module random.

Bạn có thể tìm hiểu thêm về bài toán này tại wikipedia.org/wiki/Birthday_paradox, và có thể xem lời giải của tôi tại thinkpython.com/code/birthday.py.

Hãy viết một hàm có tên là remove_duplicates trong đó nhận vào một danh sách và trả về một danh sách mới chỉ gồm các phần tử duy nhất (theo nghĩa không trùng nhau) từ danh sách gốc. Gợi ý: chúng không nhất thiết phải xếp theo cùng thứ tự.

Hãy viết một hàm để đọc file words.txt và tạo nên một danh sách với mỗi phần tử cho một từ. Hãy viết hai dạng khác nhau của hàm này, một dạng dùng phương thức append và dạng kia dùng cách viết t = t + [x]. Dạng nào chạy tốn thời gian hơn? Tại sao?

Bạn có thể xem lời giải của tôi tại thinkpython.com/code/wordlist.py.

Để kiểm tra xem một từ có trong danh sách các từ hay không, bạn có thể dùng toán tử in, nhưng cách này sẽ rất chậm vì nó phải tìm qua danh sách theo đúng thứ tự.

Vì các từ đã được xếp theo thứ tự ABC, nên chúng ta có thể tăng tốc bằng cách tìm kiếm nhị phân, điều này cũng hơi giống với cách ta tra từ điển. Ta bắt đầu bằng việc mở giữa quyển từ điển và kiểm tra xem liệu từ cần tra có đứng trước từ nằm giữa trong danh sách hay không. Nếu đúng vậy, ta tìm kiếm nửa đầu của từ điển theo cách tương tự. Còn nếu không đúng, ta sẽ tìm kiếm nửa cuối.

Dù trường hợp nào xảy ra đi nữa, phạm vi tìm kiếm đã giảm xuống chỉ còn một nửa. Nếu danh sách từ ban đầu có 113.809 từ, thì chỉ cần khoảng 17 bước là tìm ra được từ hoặc kết luận rằng từ cần tìm không có trong danh sách.

Hãy viết một hàm có tên là bisect nhận vào một danh sách đã được sắp xếp và giá trị cần tìm, sau đó trả lại chỉ số của giá trị trong danh sách nếu có, hoặc là None nếu không.

Hoặc bạn cũng có thể đọc tài liệu viết về module bisect rồi áp dụng nó!

Hai từ được gọi là một “cặp đảo” nếu như từ này là dạng viết dảo ngược của từ kia. Hãy viết một chương trình để tìm ra tất cả những cặp từ dảo có trong danh sách từ.

Hai từ được gọi là “đan cài” nhau nếu như lần lượt lấy mỗi chữ cái của từng từ ta xếp lại được một từ mới¹. Chẳng hạn, “shoe” và “cold” đan cài nhau để tạo ra “schooled”.

1. Hãy viết một chương trình tìm ra tất cả những cặp từ đan cài. Gợi ý: đừng phát sinh đầy đủ tất cả các cặp từ để kiểm tra!
2. Bạn có thể tìm được từ đan cài ba lần; nghĩa là chia lần lượt các chữ cái thành ba nhóm theo đúng thứ tự thì ta được ba từ khác nhau?

---

1. Bài tập này được bắt ngưồn từ một ví dụ trong trang puzzlers.org. ↩