High Performance Python - Lists and Tuples (Part II)

Nếu các bạn tìm đến bài viết này tức là bạn đã viết ra được những chương trình chạy đúng và hiện tại bạn đang muốn cải thiện hiệu năng cho những chương trình đó.

Hiện tại tôi đang đọc một cuốn sách tên High Performance Python của hai tác giả Micha Gorelick và Ian Ozsvald. Có một số phần tôi thấy khá hay và dễ hiểu nên tôi quyết định sẽ chọn những phần này để dịch và truyền tải đến các bạn.

Chương 3 của cuốn sách nói về Lists và Tuples trong Python.

Lists Versus Tuples

Nếu list và tuple sử dụng cùng một cấu trúc dữ liệu cơ bản, điều gì là khác biệt giữa chúng? Có thể tổng kết lại, những khác biệt chính là:

1. List là các array động; chúng có thể thay đổi và cho phép resize (thay đổi số lượng phần tử)
2. Tuple là các array tĩnh; chúng không thể thay đổi, dữ liệu của chúng không thể thay đổi một khi đã được tạo ra
3. Các tuple được cache lại trong khi chạy chương trình, nghĩa là chúng ta không cần phải nói với kernel để dành trước bộ nhớ mỗi khi muốn sử dụng.

Những khác biệt này chỉ ra sự khác nhau về triết lý giữa hai cấu trúc dữ liệu: tuple dùng để mô tả các thuộc tính của một thứ không thay đổi và list được dùng để lưu các tập dữ liệu về các đối tượng khác nhau. Ví dụ, các phần của một số điện thoại rất hoàn hảo với một tuple: chúng không thay đổi. Tương tự, các hệ số của một đa thức phù hợp với một tuple, bởi vì các hệ số khác sẽ biểu diễn một đa thức khác. Mặt khác, tên của những người đọc cuốn sách sẽ phù hợp hơn với một list dữ liệu thay đổi thường xuyên cả về nội dung lẫn kích thước nhưng luôn mô tả cùng một ý niệm.

Chú ý rằng cả list và tuple đều nhận hỗn hợp các kiểu dữ liệu. Có thể thấy điều này sẽ dẫn đến một số chi phí (tính toán, bộ nhớ) và làm yếu đi một số giải thuật tối ưu. Những chi phí này có thể được loại bỏ nếu chúng ta sử dụng dữ liệu cùng loại cho list hay tuple. Trong chương 6 chúng ta sẽ nói về việc giảm cả memory lẫn chi phí tính toán bằng numpy. Hơn nữa, các package khác như là blist và array cũng có thể làm giảm những chi phí này đối với các trường hợp phi số (nonnumerical). Điều này bóng gió nói tới một điểm quan trọng trong lập trình hiệu năng mà chúng ta sẽ bàn đến trong những chương sau: code tổng quát (generic code) sẽ chậm hơn code được thiết kế đặc biệt để giải quyết một bài toán cụ thể.

Thêm vào đó, đặc tính không thể thay đổi của tuple lại đối nghịch với list làm cho nó trở thành một cấu trúc dữ liệu vô cùng nhẹ. Điều này có nghĩa rằng là sẽ không mất nhiều chi phí bộ nhớ khi lưu chúng và các thao tác với chúng là cực kỳ dễ dàng. Với list, như chúng ta biết, khả năng thay đổi của nó phải trả bằng việc cần thêm bộ nhớ để lưu trữ và các tính toán phụ cần thiết khi sử dụng chúng.

Câu hỏi: Đối với các tập dữ liệu sau, bạn sẽ sử dụng tuple hay list? Tại sao?

  1. 20 số nguyên tố đầu tiên
  2. Tên của các ngôn ngữ lập trình
  3. Tuổi, cân nặng và chiều cao của một người
  4. Sinh nhật và nơi sinh của một người
  5. Kết quả của một ván game bi-a
  6. Kết quả của một chuỗi các ván game bi-a

Trả lời:

  1. *tuple*, vì dữ liệu là tĩnh và sẽ không thay đổi
  2. *list*, vì tập dữ liệu sẽ tăng dần lên
  3. *list*, vì các giá trị sẽ cần được update theo thời gian
  4. *tuple*, vì thông tin là tĩnh và sẽ không thay đổi
  5. *tuple*, vì dữ liệu là tĩnh
  6. *list*, vì tập dữ liệu sẽ thay đổi

Lists as Dynamic Arrays

Một khi chúng ta tạo một list, chúng ta có thể thoải mái thay đổi nó khi cần:

>>> numbers = [5, 8, 1, 3, 2, 6]
>>> numbers[2] = 2*numbers[0]  # (1)
>>> numbers
[5, 8, 10, 3, 2, 6]

(1) Như mô tả trước đó, thao tác này tiêu tốn O(n) thời gian bởi vì chúng ta có thể tìm thấy được phần tử thứ 0 hoặc thứ 2 ngay lập tức.

Hơn nữa, chúng ta có thể thêm dữ liệu mới vào một list và tăng kích thước của nó:

>>> len(numbers)
6
>>> numbers.append(42)
>>> numbers
[5, 8, 10, 3, 2, 6, 42]
>>> len(numbers)
7

Điều này là có thể bởi vì array động hỗ trợ phương thức resize - làm tăng sức chứa của một array. Khi một list cỡ N được thêm vào, Python phải tạo một list mới đủ lớn để chứa N phần tử ban đầu cùng với một phần tử được thêm vào. Tuy nhiên, thay vì cấp phát N + 1 phần tử, M (M > N) phần tử sẽ được cấp phát để chuẩn bị trước cho việc append trong tương lai. Sau đó, dữ liệu từ list cũ sẽ được copy sang list mới và list cũ sẽ được hủy đi. Triết lý là một append có thể là khởi đầu của một chuỗi những append và việc request thêm không gian có thể làm giảm số lần cấp phát bộ nhớ cũng như là số lần copy bộ nhớ cần thiết. Điều này hoàn toàn quan trọng bởi vì việc copy bộ nhớ là rất đắt đỏ, đặc biệt là khi kích thước list lớn (Hình 3-2). Công thức cấp phát bộ nhớ cho list:

Ví dụ 3-5: Công thức cấp phát bộ nhớ cho list trong Python 2.7

if new_size > allocated:
    new_allocated = new_size + (new_size >> 3) + (new_size < 9 ? 3 : 6)

Ở trong cuốn sách thì nó viết thế này:

Theo mình thấy thì cái công thức này hơi khó hiểu và nghe có vẻ nó không đúng lắm thì phải. Vậy nên mình viết lại theo ý mình như thế kia. Tất nhiên là mình đã kiểm tra với Python shell và "hình như" là nó đúng