Tạo ra kiểu dữ liệu mới

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

Các ngôn ngữ lập trình hướng đối tượng cho phép lập trình viên tạo nên những kiểu dữ liệu biểu hiện giống như những kiểu dữ liệu lập sẵn. Ta sẽ khám phá khả năng này bằng cách lập nên một lớp Fraction hoạt động rất giống với những kiểu dữ liệu số có sẵn như số nguyên, số nguyên dài và dạng dấu phẩy động.

Các phân số, còn gọi là số hữu tỉ, là những giá trị có thể được biểu diễn bằng tỉ số giữa hai số nguyên, như 5/6. Số ở trên được gọi là tử số còn số ở dưới là mẫu số.

Ta bắt đầu bằng việc định nghĩa một lớp Fraction với một phương thức khởi tạo để cung cấp các số nguyên là tử số và mẫu số:

class Fraction: 
  def __init__(self, numerator, denominator=1): 
    self.numerator = numerator 
    self.denominator = denominator 

Ở đây mẫu số có thể có hoặc không, tùy ý. Một Fraction với chỉ một tham số duy nhất sẽ biểu diễn một số nguyên. Nếu tử số bằng n, ta sẽ lập nên Fraction n/1.

Bước tiếp theo là viết một phương thức __str__ để hiển thị các phân số một cách hợp lý. Ở đây hình thức tự nhiên là viết “tử số/mẫu số”:

class Fraction: 
  ... 
  def __str__(self): 
    return "%d/%d" % (self.numerator, self.denominator) 

Để kiểm tra xem đến giờ ta đã có gì rồi, hãy đặt mã lệnh trên vào một tập tin mang tên Fraction.py rồi nhập nó từ trình thông dịch Python. Sau đó ta tạo ra một đối tượng phân số rồi in nó ra.

>>> from Fraction import Fraction 
>>> spam = Fraction(5,6) 
>>> print "The fraction is", spam 
The fraction is 5/6 

Như thường lệ, lệnh print đã ngầm kích hoạt phương thức __str__.

Phép nhân phân số

Ta muốn áp dụng được các phép tính thông thường như cộng, trừ, nhân, chia đối với phân số. Để làm điều này, ta có thể chồng chất (overload) các toán tử đối với những đối tượng Fraction.

Ta sẽ bắt đầu với phép nhân vì nó dễ thực hiện nhất. Để nhân hai phân số, ta tạo ra một phân số mới với tử số bằng tích của các tử số ban đầu và mẫu số bằng tích các mẫu số ban đầu. __mul__ là tên gọi mà Python dùng cho một phương thức để chồng chất toán tử *:

class Fraction:
  ...
  def __mul__(self, other):
    return Fraction(self.numerator*other.numerator,
                    self.denominator*other.denominator)

Ta có thể kiểm tra phương thức này bằng cách tính tích hai phân số:

>>> print Fraction(5,6) * Fraction(3,4)
 15/24

Như vậy phương thức này có tác dụng rồi; song ta có thể làm tốt hơn! Ta có thể mở rộng phương thức này để nhân một phân số với một số nguyên. Ta sẽ dùng hàm isinstance để kiểm tra xem liệu other có là số nguyên không và nếu đúng, thì chuyển đổi thành một phân số.

class Fraction:
  ...
  def __mul__(self, other):
    if isinstance(other, int):
      other = Fraction(other)
    return Fraction(self.numerator   * other.numerator,
                    self.denominator * other.denominator)

Bây giờ thì phép nhân giữa phân số và số nguyên đã hoạt động được, nhưng chỉ khi phân số đóng vai trò toán hạng bên trái:

>>> print Fraction(5,6) * 4
 20/6
>>> print 4 * Fraction(5,6)
 TypeError: __mul__ nor __rmul__ defined for these operands 

Để lượng giá được một toán tử nhị phân như toán tử nhân, trước hết Python kiểm tra toán hạng trái để xem liệu nó có cung cấp một phương thức __mul__ hỗ trợ được kiểu dữ liệu của toán hạng thứ hai hay không. Trong trường hợp này, toán tử lập sẵn cho số nguyên lại không hỗ trợ được phân số.

Tiếp theo, Python kiểm tra toán hạng phải để xem liệu nó cung cấp một phương thức __rmul__ để hỗ trợ kiểu dữ liệu của toán hạng thứ nhất không. Trong trường hợp này, ta vẫn chưa cung cấp phương thức __rmul__ nào, vì vậy mà phép nhân đã thất bại.

Mặt khác, có một cách đơn giản để cung cấp __rmul__:

class Fraction:
  ...
  __rmul__ = __mul__

Phép gán này phát biểu rằng __rmul__ cũng giống như __mul__. Bây giờ nếu lượng giá 4 * Fraction(5,6), Python sẽ kích hoạt __rmul__ lên đối tượng Fraction rồi truyên 4 làm tham số:

>>> print 4 * Fraction(5,6)
 20/6

Vì __rmul__ cũng giống như __mul__, mà __mul__ thì có thể xử lý được tham số là số nguyên, nên mọi chuyện đã xong xuôi.

Phép cộng phân số

Cộng phân số thì phức tạp hơn nhân, song cũng không quá khó. Tổng của các phân số a/b và c/d là phân số (a*d+c*b)/(b*d).

Lấy đoạn mã lệnh nhân phân số làm mẫu, ta có thể viết __add__ và __radd__:

class Fraction:
  ...
  def __add__(self, other):
    if isinstance(other, int):
    other = Fraction(other)
    return Fraction(self.numerator   * other.denominator +
                    self.denominator * other.numerator,
                    self.denominator * other.denominator)
  __radd__ = __add__

Ta có thể kiểm tra những phương thức này với các Fraction và những số nguyên.

>>> print Fraction(5,6) + Fraction(5,6)
 60/36
>>> print Fraction(5,6) + 3
 23/6
>>> print 2 + Fraction(5,6)
 17/6

Hai trường hợp đầu đã kích hoạt __add__; còn trường hợp thứ ba thì kích hoạt __radd__.

Thuật toán Euclid

Ở ví dụ trên, ta đã tính tổng 5/6 + 5/6 và được 60/36. Điều này đúng, nhưng không phải cách hay nhất để biểu diễn kết quả. Để rút gọn phân số về dạng tối giản, ta phải chia cả tử số lẫn mẫu số cho ước số chung lớn nhất (UCLN) của chúng, trong trường hợp này là 12. Kết quả sẽ là 5/3.

Nói chung, mỗi khi tạo nên một đối tượng Fraction mới, ta cần rút gọn nó bằng cách chia cả tử lẫn mẫu cho UCLN của nó. Nếu bản thân phân số đã được rút gọn rồi, UCLN sẽ là 1.

Euclid xứ Alexandria (khoảng 325–265 TCN) đã trình bày một thuật toán để tính UCLN cho hai số nguyên m và n:

Nếu m chia hết cho n, thì n sẽ là UCLN. Còn nếu không, UCLN sẽ là UCLN của n và phần dư trong phép chia của m cho n.

Định nghĩa đệ quy này có thể được biểu diễn gọn gàng dưới dạng một hàm:

def gcd (m, n):
  if m % n == 0:
    return n
  else:
    return gcd(n, m%n)

Ở dòng lệnh đầu tiên trong phần thân hàm, ta đã dùng toán tử mod để kiểm tra tính chia hết. Ở dòng cuối cùng, ta lại dùng nó để tính số dư sau phép chia.

Vì tất cả những phép tính mà ta đã viết đều tạo nên kết quả là những đối tượng Fraction mới, nên ta có thể rút gọn mọi kết quả bằng cách sửa lại phương thức khởi tạo.

class Fraction:
  def __init__(self, numerator, denominator=1):
    g = gcd (numerator, denominator)
    self.numerator   =   numerator / g
    self.denominator = denominator / g

Bây giờ mỗi khi ta tạo ra một Fraction, nó sẽ được rút gọn về dạng tối giản:

>>> Fraction(100,-36)
 -25/9

Một đặc điểm hay của gcd là với phân số âm, dấu trừ sẽ luôn được chuyển lên tử số.

So sánh phân số

Giả sử ta có hai đối tượng Fraction là a và b, được định lượng a == b. Cách tạo dựng mặc định của == chỉ kiểm tra bằng nhau kiểu “nông” (shallow equality), nên nó chỉ trả lại true nếu a và b cùng là một đối tượng.

Song đúng hơn là ta muốn nó phải trả lại true nếu a và b có cùng giá trị — đó là bằng nhau kiểu “sâu” (deep equality).

Ta phải dạy cho đối tượng phân số cách so sánh giữa chúng. Như đã thấy ở mục “So sánh các lá bài”, ta có thể chồng chất toàn bộ những toán tử so sánh một lượt bằng cách cung cấp một phương thức __cmp__.

Theo quy ước, phương thức __cmp__ trả lại một số âm nếu self nhỏ hơn other, bằng không nếu chúng bằng nhau, và một số âm nếu self is lớn hơn other.

Cách đơn giản nhất để so sánh phân số là nhân chéo. Nếu a/b > c/d, thì ad > bc. Theo tinh thần đó, sau đây là mã lệnh của __cmp__:

class Fraction:
  ...
  def __cmp__(self, other):
    diff = (self.numerator  * other.denominator -
            other.numerator * self.denominator)
  return diff

Nếu self lớn hơn other, thì diff sẽ dương. Nếu other lớn hơn, thì diff sẽ âm. Nếu chúng bằng nhau, thì diff bằng không.

Tiến xa hơn

Dĩ nhiên, mọi việc vẫn chưa kết thúc. Ta còn phải thực hiện phép trừ bằng cách viết mã lệnh đè lên __sub__ sẵn có, và phép chia bằng cách viết đè lên __div__.

Một cách để xử lý những phép tính trên là thực hiện phép đối (đổi dấu) bằng cách viết đè lên __neg__ và phép nghịch đảo bằng cách đè lên __invert__. Sau đó ta có thể tính trừ bằng cách đổi dấu toán hạng thứ hai trước khi cộng, và có thể tính chia bằng cách nghịch đảo toán hạng thứ hai trước khi nhân.

Tiếp theo, ta phải cung cấp các phương thức __rsub__ và __rdiv__. Không may là ta không thể dùng mẹo như với phép nhân và cộng, vì các phép trừ và chia đều không có tính giao hoán. Không thể đơn giản là đặt __rsub__ và __rdiv__ bằng với __sub__ và __div__. Trong những phép toán này, thứ tự của các toán hạng tạo nên sự khác biệt.

Để xử lý đổi dấu, vốn là cách dùng dấu trừ cho một toán hạng duy nhất, ta viết đè lên __neg__.

Ta có thể tính lũy thừa bằng cách viết đè lên __pow__, nhưng phần tạo dựng sẽ có chút mẹo. Nếu số mũ không phải là một số nguyên thì kết quả có khả năng sẽ không biểu diễn được dưới dạng Fraction. Chẳng hạn, Fraction(2) ** Fraction(1,2) là căn bậc hai của 2, vốn là một số vô tỉ (nó không biểu diễn được dưới dạng phân số). Bởi vậy sẽ không dễ viết được dạng tổng quát nhất cho __pow__.

Có thể còn cách mở rộng khác cho lớp Fraction mà bạn muốn phát kiến. Đến giờ ta mới giả sử rằng cả tử số và mẫu số đều là những số nguyên.

Bài tập: Hãy hoàn thiện phần tạo dựng của lớp Fraction để nó xử lý được các phép trừ, phép chia và lũy thừa.

Thuật ngữ

ước số chung lớn nhất (UCLN)
Số nguyên lớn nhất mà cả tử số và mẫu số của một phân số đều chia hết cho.
rút gọn
Biến đổi một phân số về dạng tương đương nhưng có UCLN bằng 1.
đổi dấu
Phép toán để tính ra một số đối trong phép cộng, thường được kí hiệu bằng dấu trừ đi trước. Gọi là “đối” để phân biệt với phép trừ có liên quan đến hai toán hạng.

1 Phản hồi

Filed under Think Python

One response to “Tạo ra kiểu dữ liệu mới

  1. Pingback: Cách nghĩ như nhà khoa học máy tính | Blog của Chiến

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s