Mục con


5. Cấu trúc dữ liệu

Chương này diễn giải kỹ hơn một vài điều bạn đã học được, và cũng nói thêm về một số điều mới.


5.1 Bàn thêm về danh sách

Kiểu dữ liệu danh sách (kiểu list) có một số phương thức khác. Đây là toàn bộ các phương thức của đối tượng danh sách:

append( x)
Thêm một phần tử vào cuối danh sách; tương đương với a[len(a):] = [x].

extend( L)
Nới rộng danh sách bằng cách chèn vào tất cả các phần tử của danh sách chỉ định; tương đương với a[len(a):] = L.

insert( i, x)
Chèn một phần tử vào vị trí chỉ định. Thông số đầu là chỉ mục của phần tử sẽ bị đẩy lùi, cho nên a.insert(0, x) chèn vào đầu danh sách, và a.insert(len(a), x) tương đương với a.append(x).

remove( x)
Bỏ ra khỏi danh sách phần tử đầu tiên có giá trị là x. Sẽ có lỗi nếu không có phần tử như vậy.

pop( [i])
Bỏ khỏi danh sách phần tử ở vị trí chỉ định, và trả về chính nó. Nếu không chỉ định vị trí, a.pop() bỏ và trả về phần tử cuối trong danh sách. (Ngoặc vuông xung quanh i trong khai báo hàm cho biết thông số đó là không bắt buộc, không có nghĩa là bạn cần gõ dấu ngoặc vuông ở vị trí đó. Bạn sẽ thấy cách viết này thường xuyên trong Tham khảo thư viện Python.)

index( x)
Trả về chỉ mục của phần tử trong danh sách mà có giá trị là x. Sẽ có lỗi nếu không có phần tử như vậy.

count( x)
Trả về số lần x xuất hiện trong danh sách.

sort( )
Sắp xếp các phần tử trong danh sách, ngay tại chỗ.

reverse( )
Đảo ngược thứ tự các phần tử trong danh sách, ngay tại chỗ.

Một ví dụ có sử dụng hầu hết các phương thức của danh sách:

>>> a = [66.25, 333, 333, 1, 1234.5]
>>> print a.count(333), a.count(66.25), a.count('x')
2 1 0
>>> a.insert(2, -1)
>>> a.append(333)
>>> a
[66.25, 333, -1, 333, 1, 1234.5, 333]
>>> a.index(333)
1
>>> a.remove(333)
>>> a
[66.25, -1, 333, 1, 1234.5, 333]
>>> a.reverse()
>>> a
[333, 1234.5, 1, 333, -1, 66.25]
>>> a.sort()
>>> a
[-1, 1, 66.25, 333, 333, 1234.5]


5.1.1 Dùng danh sách như ngăn xếp

Các phương thức của danh sách làm cho nó rất dễ sử dụng như là ngăn xếp (stack), là nơi mà phần tử cuối được thêm vào là phần tử đầu được lấy ra (``vào sau, ra trước'' hay ``last-in, first-out''). Để thêm phần tử vào đỉnh của ngăn xếp, dùng append(). Để lấy một phần tử từ đỉnh của ngăn xếp, dùng pop() mà không chỉ định chỉ mục. Ví dụ:

>>> stack = [3, 4, 5]
>>> stack.append(6)
>>> stack.append(7)
>>> stack
[3, 4, 5, 6, 7]
>>> stack.pop()
7
>>> stack
[3, 4, 5, 6]
>>> stack.pop()
6
>>> stack.pop()
5
>>> stack
[3, 4]


5.1.2 Dùng danh sách như hàng đợi

Bạn cũng có thể thuận tiện dùng danh sách như là hàng đợi (queue), nơi mà phần tử được thêm vào đầu tiên là phần tử được lấy ra đầu tiên (``vào trước, ra trước'' hay ``first-in, first-out''). Để thêm một phần tử vào cuối hàng đợi, dùng append(). Để lấy một phần tử từ đầu hàng đợi, dùng pop() với 0 là chỉ mục. Ví dụ:

>>> queue = ["Eric", "John", "Michael"]
>>> queue.append("Terry")           # Terry arrives
>>> queue.append("Graham")          # Graham arrives
>>> queue.pop(0)
'Eric'
>>> queue.pop(0)
'John'
>>> queue
['Michael', 'Terry', 'Graham']


5.1.3 Công cụ lập trình hướng hàm

Có sẵn ba hàm rất hữu dụng khi dùng với danh sách: filter(), map(), và reduce().

"filter(function, sequence)" trả về một dãy chứa các phần tử từ dãy mà function(item) có giá trị đúng. Nếu sequence là một string hoặc tuple, thì kết quả trả về sẽ có cùng kiểu; ngược lại, sẽ luôn luôn là một list. Ví dụ, để tìm một vài số nguyên tố:

>>> def f(x): return x % 2 != 0 and x % 3 != 0
...
>>> filter(f, range(2, 25))
[5, 7, 11, 13, 17, 19, 23]

"map(function, sequence)" gọi function(item) với mỗi phần tử trong dãy và trả về một danh sách các giá trị trả về. Ví dụ, để tính một vài số lập phương:

>>> def cube(x): return x*x*x
...
>>> map(cube, range(1, 11))
[1, 8, 27, 64, 125, 216, 343, 512, 729, 1000]

Có thể truyền vào nhiều dãy; hàm đó phải nhận từng ấy thông số với mỗi phần tử trong mỗi dãy là một thông số (hoặc None nếu dãy nào đó ngắn hơn dãy còn lại). Ví dụ:

>>> seq = range(8)
>>> def add(x, y): return x+y
...
>>> map(add, seq, seq)
[0, 2, 4, 6, 8, 10, 12, 14]

"reduce(function, sequence)" trả về giá trị duy nhất được tạo ra từ việc gọi hàm nhị phân function với thông số là hai phần tử đầu của dãy, rồi sau đó với giá trị trả về này với phần tử kế, và cứ thế. Ví dụ, để tính tổng của các số từ 1 đến 10:

>>> def add(x,y): return x+y
...
>>> reduce(add, range(1, 11))
55

Nếu chỉ có một phần tử trong dãy, giá trị của nó sẽ được trả về; nếu dãy rỗng, biệt lệ sẽ được nâng.

Có thể truyền thêm thông số thứ ba để cho biết giá trị ban đầu. Trong trường hợp đó, giá trị này sẽ được trả về nếu dãy rỗng, và hàm sẽ được áp dụng cho giá trị ban đầu, và giá trị của phần tử đầu của dãy, rồi với giá trị được trả về với giá trị của phần tử kế, và cứ thế. Ví dụ,

>>> def sum(seq):
...     def add(x,y): return x+y
...     return reduce(add, seq, 0)
... 
>>> sum(range(1, 11))
55
>>> sum([])
0

Đừng dùng định nghĩa của ví dụ này về sum(): vì việc cộng các con số là một nhu cầu chung, một hàm có sẵn sum(sequence) đã được cung cấp, và hoặc động y như vậy. Từ phiên bản 2.3.

5.1.4 Gộp danh sách

Việc gộp danh sách (list comprehension) cung cấp một cách xúc tích để tạo danh sách mà không cần dùng tới map(), filter() hoặc lambda. Kết quả là khai báo danh sách kiểu này thường dễ hiểu hơn những danh sách tạo ra từ những cách kia. Mỗi gộp danh sách chứa một biểu thức, theo sau bởi vế for , rồi không có hoặc có các vế for hoặc if . Kết quả sẽ là một danh sách được trả về từ việc định giá biểu thức trong ngữ cảnh của các vế forif theo sau nó. Nếu biểu thức trả về một tuple, nó phải được đặt trong ngoặc.

>>> freshfruit = ['  banana', '  loganberry ', 'passion fruit  ']
>>> [weapon.strip() for weapon in freshfruit]
['banana', 'loganberry', 'passion fruit']
>>> vec = [2, 4, 6]
>>> [3*x for x in vec]
[6, 12, 18]
>>> [3*x for x in vec if x > 3]
[12, 18]
>>> [3*x for x in vec if x < 2]
[]
>>> [[x,x**2] for x in vec]
[[2, 4], [4, 16], [6, 36]]
>>> [x, x**2 for x in vec]	# error - parens required for tuples
  File "<stdin>", line 1, in ?
    [x, x**2 for x in vec]
               ^
SyntaxError: invalid syntax
>>> [(x, x**2) for x in vec]
[(2, 4), (4, 16), (6, 36)]
>>> vec1 = [2, 4, 6]
>>> vec2 = [4, 3, -9]
>>> [x*y for x in vec1 for y in vec2]
[8, 6, -18, 16, 12, -36, 24, 18, -54]
>>> [x+y for x in vec1 for y in vec2]
[6, 5, -7, 8, 7, -5, 10, 9, -3]
>>> [vec1[i]*vec2[i] for i in range(len(vec1))]
[8, 12, -54]

Cách gộp danh sách uyển chuyển hơn nhiều so với map() và có thể được áp dụng cho các biểu thức phức tạp và các hàm lồng nhau:

>>> [str(round(355/113.0, i)) for i in range(1,6)]
['3.1', '3.14', '3.142', '3.1416', '3.14159']


5.2 del câu lệnh

Có một cách để bỏ một phần tử ra khỏi danh sách dựa trên chỉ mục của nó, thay vì giá trị: câu lệnh del . Cách này khác với phương thức pop()trả về một giá trị. Câu lệnh del cũng có thể được sử dụng để bỏ các miếng cắt (slice) khỏi danh sách hoặc xóa toàn bộ danh sách (điều mà chúng ta đã làm trước đó bằng cách gán một danh sách rỗng vào miếng cắt). Ví dụ:

>>> a = [-1, 1, 66.25, 333, 333, 1234.5]
>>> del a[0]
>>> a
[1, 66.25, 333, 333, 1234.5]
>>> del a[2:4]
>>> a
[1, 66.25, 1234.5]
>>> del a[:]
>>> a
[]

del cũng có thể được dùng để xóa hoàn toàn các biến:

>>> del a

Tham chiếu tới tên a sau đó sẽ tạo ra lỗi (ít nhất cho đến khi một giá trị khác được gán vào cho nó). Chúng ta sẽ thấy các cách dùng khác với del sau này.


5.3 Bộ và dãy

Chúng ta đã thấy rằng danh sách và chuỗi có nhiều thuộc tính chung, như là có chỉ mục, và các toán tử cắt miếng. Chúng là hai ví dụ của dãy (sequence) kiểu dữ liệu. Vì Python là một ngôn ngữ đang phát triển, các kiểu dữ liệu dãy khác có thể được thêm vào. Có một kiểu dãy chuẩn khác: bộ (tuple).

Một tuple gồm một số các giá trị phân cách bởi dấu phẩy, ví dụ:

>>> t = 12345, 54321, 'hello!'
>>> t[0]
12345
>>> t
(12345, 54321, 'hello!')
>>> # Tuples may be nested:
... u = t, (1, 2, 3, 4, 5)
>>> u
((12345, 54321, 'hello!'), (1, 2, 3, 4, 5))

Khi xuất ra, tuple luôn luôn được kèm giữa hai dấu ngoặc nhằm để cho các tuple lồng nhau có thể được thông dịch chính xác; chúng có thể được nhập vào với ngoặc hoặc không, mặc dù thông thường chúng ta vẫn cần các dấu ngoặc (nếu tuple là một phần của một biểu thức lớn hơn).

Tuple được dùng nhiều. Ví dụ: cặp tọa độ (x, y), bản ghi nhân viên từ cơ sở dữ liệu, v.v... Giống như chuỗi, tuple không thể bị thay đổi: không thể gán giá trị mới cho từng phần tử của tuple (mặc dù bạn có thể đạt được cùng kết quả với cắt miếng và ghép dãy). Cũng có thể tạo tuple chứa các đối tượng khả biến ví dụ như danh sách.

Vấn đề đặc biệt là trong việc tạo nên tuple chứa 0 hoặc một phần tử: cú pháp ngôn ngữ có một vài điểm riêng để thực hiện việc này. Tuple rỗng được tạo nên bởi một cặp ngoặc rỗng; tuple một phần tử được tạo bởi một giá trị theo sau bởi một dấu phẩy (việc cho giá trị đơn lẻ vào trong ngoặc không đủ để tạo tuple). Xấu, nhưng hiệu quả. Ví dụ:

>>> empty = ()
>>> singleton = 'hello',    # <-- note trailing comma
>>> len(empty)
0
>>> len(singleton)
1
>>> singleton
('hello',)

Câu lệnh t = 12345, 54321, 'hello!' là một ví dụ của việc đóng gói tuple (tuple packing): các giá trị 12345, 54321'hello!' được gói lại vào trong một tuple. Và quá trình ngược:

>>> x, y, z = t

Và nó được gọi là tháo dãy. Việc tháo dãy yêu cầu danh sách các biến bên trái có cùng số phần tử như độ lớn của dãy. Chú ý rằng phép đa gán (multiple assignment) thật ra chỉ là sự tổng hợp của việc gói tuple và tháo dãy.

Có một điểm không đối xứng ở đây: việc gói nhiều giá trị luôn luôn tạo một tuple, nhưng phép tháo ra có thể được áp dụng cho mọi dãy (chuỗi, danh sách, tuple).


5.4 Tập hợp

Python cũng có một kiểu dữ liệu cho tập hợp (set). Một tập hợp là một nhóm các phần tử không lặp. Ứng dụng cơ bản bao gồm việc kiểm tra hội viên và bỏ các phần tử trùng lặp. Các đối tượng tập hợp cũng hỗ trợ các toán tử như hợp, giao, hiệu, và hiệu đối xứng.

Đây là một ví dụ ngắn:

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> fruit = set(basket)               # create a set without duplicates
>>> fruit
set(['orange', 'pear', 'apple', 'banana'])
>>> 'orange' in fruit                 # fast membership testing
True
>>> 'crabgrass' in fruit
False

>>> # Demonstrate set operations on unique letters from two words
...
>>> a = set('abracadabra')
>>> b = set('alacazam')
>>> a                                  # unique letters in a
set(['a', 'r', 'b', 'c', 'd'])
>>> a - b                              # letters in a but not in b
set(['r', 'd', 'b'])
>>> a | b                              # letters in either a or b
set(['a', 'c', 'r', 'd', 'b', 'm', 'z', 'l'])
>>> a & b                              # letters in both a and b
set(['a', 'c'])
>>> a ^ b                              # letters in a or b but not both
set(['r', 'd', 'b', 'm', 'z', 'l'])


5.5 Từ điển

Một kiểu dữ liệu hữu dụng khác được đưa vào Python là từ điển (dictionary). Từ điển được tìm thấy trong các ngôn ngữ khác như ``bộ nhớ kết hợp (associative memory)'' hoặc ``mảng kết hợp (associative array)''. Không như dãy được chia chỉ mục từ một khoảng số, từ điển được chia chỉ mục từ các khóa, có thể là bất kỳ kiểu không đổi nào; chuỗi và số luôn luôn có thể làm khóa. Tuple có thể được dùng làm khóa nếu nó chỉ chứa chuỗi, số, hoặc tuple; nếu tuple chứa bất kỳ một đối tượng khả biến nào thì nó không thể được dùng làm khóa. Bạn không thể dùng danh sách làm khóa, vì danh sách có thể được thay đổi ngay tại chỗ với phép gán vào chỉ mục, phép gán miếng cắt, hoặc các phương thức khác như append()extend().

Dễ nhất là nghĩ về từ điển như một tập hợp không thứ tự của các bộ khóa: giá trị , với điều kiện là khóa phải là duy nhất (trong cùng một từ điển). Một cặp ngoặc nhọn tạo một từ điển rỗng: {}. Đặt một loạt các cụm khóa:giá trị phân biệt bởi dấu phẩy vào trong ngoặc nhọn tạo nên các cặp khóa:giá trị ban đầu cho từ điển; đây cũng là cách mà từ điển được xuất ra.

Công việc chính của từ điển là chứa một giá trị vào một khóa nào đó và lấy lại giá trị từ khóa đó. Cũng có thể xóa một cặp khóa:giá trị với del. Nếu bạn chứa vào một khóa đã có sẵn, giá trị cũ sẽ bị mất. Lấy giá trị từ một khóa không tồn tại sẽ gây nên lỗi.

Phương thức keys() của đối tượng từ điển trả về một danh sách các khóa đã được dùng trong từ điển, theo một thứ tự bất kỳ (nếu bạn muốn chúng được sắp xếp, chỉ cần áp dụng phương thức sort() vào danh sách các khóa). Để kiểm tra xem một khóa có trong từ điển hay không, có thể dùng phương thức has_key() hoặc từ khóa in .

Đây là một ví dụ nhỏ về cách dùng từ điển:

>>> tel = {'jack': 4098, 'sape': 4139}
>>> tel['guido'] = 4127
>>> tel
{'sape': 4139, 'guido': 4127, 'jack': 4098}
>>> tel['jack']
4098
>>> del tel['sape']
>>> tel['irv'] = 4127
>>> tel
{'guido': 4127, 'irv': 4127, 'jack': 4098}
>>> tel.keys()
['guido', 'irv', 'jack']
>>> tel.has_key('guido')
True
>>> 'guido' in tel
True

Phương thức dict() dùng để tạo từ điển trực tiếp từ các danh sách các cụm khóa-giá trị chứa trong tuple. Khi các cụm có một mẫu nào đó, việc gộp danh sách có thể chỉ ra ngắn gọn danh sách khóa-giá trị.

>>> dict([('sape', 4139), ('guido', 4127), ('jack', 4098)])
{'sape': 4139, 'jack': 4098, 'guido': 4127}
>>> dict([(x, x**2) for x in (2, 4, 6)])     # use a list comprehension
{2: 4, 4: 16, 6: 36}

Ở phần sau của bài chỉ dẫn chúng ta sẽ tìm hiểu về các biểu thức bộ tạo thích hợp hơn với việc cung cấp các cặp khóa-giá trị vào hàm khởi tạo dict() .

Khi mà khóa là những chuỗi đơn giản, đôi khi nó sẽ dễ hơn nếu chỉ định các cụm bằng thống số từ khóa:

>>> dict(sape=4139, guido=4127, jack=4098)
{'sape': 4139, 'jack': 4098, 'guido': 4127}


5.6 Kỹ thuật lặp

Khi lặp qua từ điển, khóa và giá trị tương ứng có thể được lấy ra cùng lúc bằng phương thức iteritems() .

>>> knights = {'gallahad': 'the pure', 'robin': 'the brave'}
>>> for k, v in knights.iteritems():
...     print k, v
...
gallahad the pure
robin the brave

Khi lặp qua một dãy, vị trí chỉ mục và giá trị tương ứng có thể được lấy ra cùng lúc bằng hàm enumerate() .

 
>>> for i, v in enumerate(['tic', 'tac', 'toe']):
...     print i, v
...
0 tic
1 tac
2 toe

Để lặp qua hai hoặc nhiều dãy cùng lúc, các phần tử có thể được ghép với nhau bằng hàm zip() .

>>> questions = ['name', 'quest', 'favorite color']
>>> answers = ['lancelot', 'the holy grail', 'blue']
>>> for q, a in zip(questions, answers):
...     print 'What is your %s?  It is %s.' % (q, a)
...	
What is your name?  It is lancelot.
What is your quest?  It is the holy grail.
What is your favorite color?  It is blue.

Để lặp qua một dãy theo thứ tự đảo, đầu tiên chỉ định dãy đó theo thứ tự xuôi, rồi gọi hàm reversed() .

>>> for i in reversed(xrange(1,10,2)):
...     print i
...
9
7
5
3
1

Để lặp qua một dãy theo thứ tự đã sắp xếp, dùng hàm sorted() và nó sẽ trả về một danh sách đã sắp xếp trong khi vẫn để danh sách gốc nguyên vẹn.

>>> basket = ['apple', 'orange', 'apple', 'pear', 'orange', 'banana']
>>> for f in sorted(set(basket)):
...     print f
... 	
apple
banana
orange
pear


5.7 Bàn thêm về điều kiện

Điều kiện dùng trong các câu lệnh whileif có thể chứa bất kỳ toán tử nào, không chỉ là phép so sánh.

Các toán tử so sánh innot in kiểm tra xem giá trị có mặt (hoặc không có mặt) trong một dãy. Toán tử isis not so sánh xem hai đối tượng có phải cùng là một đối tượng hay không; việc này chỉ quan trọng đối với các đối tượng khả biến như danh sách. Mọi toán tử so sánh có cùng độ ưu tiên, thấp hơn của các toán tử số.

So sánh có thể được nối với nhau. Ví dụ như, a < b == c kiểm tra xem a nhỏ hơn b và hơn nữa b bằng với c.

Phép so sánh có thể được ghép với nhau bằng toán tử Boolean andor, và kết quả của phép so sánh (hoặc của mọi biểu thức Boolean) có thể được đảo ngược với not. Các toán tử này có độ ưu tiên thấp hơn các toán tử so sánh; giữa chúng, not có độ ưu tiên cao nhất và or thấp nhất, để cho A and not B or C tương đương với (A and (not B)) or C. Như mọi khi, dấu ngoặc đơn có thể được dùng để cho biết kết cấu đúng ý.

Các toán tử Boolean andor còn được gọi là đoản mạch (short-circuit) toán tử: toán hạng của chúng được đánh giá từ trái qua phải, và việc định giá dừng lại ngay khi kết quả được xác định. Ví dụ như, nếu AC là đúng nhưng B là sai, A and B and C không định giá biểu thức C. Khi dùng như một giá trị chung chung và không phải như một Boolean, giá trị trả về của một toán tử đoản mạch là thông số được định giá cuối cùng.

Có thể gán kết quả của một phép so sánh hoặc một biểu thức Boolean vào một biến. Ví dụ,

>>> string1, string2, string3 = '', 'Trondheim', 'Hammer Dance'
>>> non_null = string1 or string2 or string3
>>> non_null
'Trondheim'

Chú ý rằng trong Python, khác với C, phép gán không thể có mặt trong biểu thức. Các lập trình viên C sẽ không hài lòng với việc này, nhưng nó tránh một nhóm lớn các lỗi thường gặp trong chương trình C: nhập vào = trong một biểu thức khi mà == được nhằm tới.


5.8 So sánh dãy và các kiểu khác

Đối tượng dãy có thể được so sánh với đối tượng khác cùng kiểu dãy. Sự so sánh dùng từ điển thứ tự: đầu tiên hai phần tử đâu được so sánh, và nếu chúng khác nhau thì kết quả được xác định; nếu chúng bằng nhau thì hai phần tử kế sẽ được so sánh và cứ thế, cho đến cuối một trong hai dãy. Nếu hai phần tử được so sánh lại là hai phần dãy cùng kiểu, phép so sánh từ điển lại được thực hiện đệ quy như vậy. Nếu mọi phần tử trong hai dãy đều bằng nhau thì chúng được coi là bằng nhau. Nếu một dãy là dãy con ban đầu của dãy kia, thì dãy ngắn hơn sẽ là dãy bé hơn. Thứ tự từ điển đối với chuỗi sử dụng thứ tự ASCII cho từng ký tự. Một vài ví dụ về việc so sánh dãy cùng kiểu:

(1, 2, 3)              < (1, 2, 4)
[1, 2, 3]              < [1, 2, 4]
'ABC' < 'C' < 'Pascal' < 'Python'
(1, 2, 3, 4)           < (1, 2, 4)
(1, 2)                 < (1, 2, -1)
(1, 2, 3)             == (1.0, 2.0, 3.0)
(1, 2, ('aa', 'ab'))   < (1, 2, ('abc', 'a'), 4)

Lưu ý rằng so sánh các đối tượng khác kiểu cũng được chấp nhận. Kết quả có thể đoán được nhưng ngoài ý muốn: các kiểu được xếp theo thứ tự tên của chúng. Do đó, một danh sách (list) luôn nhỏ hơn một chuỗi (string), và một chuỗi luôn nhỏ hơn một tuple, v.v.... 5.1 Các kiểu số lẫn lộn được so sánh theo giá trị của chúng, do đó 0 bằng 0.0, v.v...



Chú thích

... v.v...5.1
Không nên dựa vào luật so sánh các đối tượng khác kiểu vì nó có thể bị thay đổi ở phiên bản tương lai của ngôn ngữ.
Xem Về tài liệu này... về cách đề nghị thay đổi.