Hàng đợi

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

Chương này trình bày hai kiểu dữ liệu trừu tượng (ADT), đó là Hàng đợi và Hàng đợi Ưu tiên. Ngoài đời thực, hàng đợi là một dòng người chờ được phục vụ. Đa số các trường hợp thì đứng đầu hàng sẽ là người kế tiếp được phụ vụ. Tuy nhiên vẫn còn những ngoại lệ. Ở sân bày, những người lên chuyến bay sắp cất cánh đôi khi được làm thủ tục dù họ đứng ở giữa hàng. Ở siêu thị, một người mua hàng lịch sự có thể nhường người mua hàng có ít món đồ được thanh toán trước.

Quy tắc để phân định tiếp theo đến lượt ai được gọi là chính sách xếp hàng. Chính sách xếp hàng đơn giản nhất được gọi là FIFO, (“first-in-first-out”, vào trước ra trước). Chính sách xếp hàng tổng quát là xếp hàng ưu tiên, trong đó từng khách hàng được gán cho một quyền ưu tiên và người khác mang quyền ưu tiên cao nhất sẽ đi trước, bất kể họ đến xếp hàng lúc nào. Ta nói rằng đây là chính sách tổng quát nhất vì quyền ưu tiên có thể được dựa vào bất kì điều gì: chuyến bay khởi hành lúc nào; lượng hàng người đang mua; hoặc người khách quan trọng đến mức nào. Dĩ nhiên, không phải mọi chính sách xếp hàng đều “công bằng”, nhưng sự công bằng là dưới cái nhìn của người quan sát.

Các ADT hàng đợi và hàng đợi ưu tiên đều có cùng bộ các phép tính. Khác nhau là về nghĩa của các phép tính: một hàng đợi thì dùng chính sách FIFO; còn một hàng đợi ưu tiên (thì từ tên gọi của nó, bạn có thể đoán ra) sử dụng một chính sách xếp hàng ưu tiên.

ADT hàng đợi

ADT hàng đợi được xác định bằng những phép thao tác sau:

__init__
Khởi tạo một hàng đợi mới, còn trống.
insert
Thêm một phần tử vào hàng đợi.
remove
Gỡ bỏ đồng thời trả lại một phần tử từ hàng đợi. Phần tử được trả lại là phần tử được thêm vào sớm nhất.
isEmpty
Kiểm tra xem liệu hàng đợi còn trống không.

Hàng đợi liên kết

Cách tạo lập thứ nhất cho ADT hàng đợi mà ta xét đến là một hàng đợi liên kết; cái tên này là do nó được hợp thành từ những đối tượng Node kết nối với nhau. Sau đây là lời định nghĩa lớp:

class Queue: 
  def __init__(self): 
    self.length = 0 
    self.head = None 

  def isEmpty(self): 
    return (self.length == 0) 

  def insert(self, cargo): 
    node = Node(cargo) 
    node.next = None 
    if self.head == None: 
      # nếu danh sách rỗng thì nút mới xếp trước
      self.head = node 
    else: 
      # tìm nút cuối trong danh sách
      last = self.head 
      while last.next: last = last.next 
      # têm vào 
      last.next = node 
    self.length = self.length + 1 

  def remove(self): 
    cargo = self.head.cargo 
    self.head = self.head.next 
    self.length = self.length - 1 
    return cargo 

Các phương thức bao gồm isEmpty và remove đều giống như các phương thức isEmpty và removeFirst trong  LinkedList. Phương thức insert thì mới và phức tạp hơn đôi chút.

Ta muốn chèn thêm những phần tử mới vào cuối danh sách. Nếu danh sách trống, ta chỉ việc đặt head để tham chiếu đến nút mới.

Còn không thì ta duyệt danh sách đến nút cuối cùng và rồi đính nút mới ở điểm cuối. Ta có thể nhận ra nút cuối này vì thuộc tính next của nó là None.

Có hai bất biến với một đối tượng Queue được thiết lập chuẩn. Giá trị của length cần là số nút trong hàng đợi, và nút cuối cùng cần có thuộc tính next bằng None. Hãy tự kiểm tra để khẳng định rằng phương thức này bảo tồn cả hai bất biến trên.

Đặc tính về hiệu năng

Thông thường khi kích hoạt một phương thức, ta không quan tâm đến những chi tiết trong phần tạo dựng (implementation) của nó. Song có một “chi tiết” mà có thể ta muốn biết     đặc tính hiệu năng của phương thức này. Thời gian thực hiện sẽ kéo dài bao lâu, và thời gian này thay đổi như thế nào khi số phần tử trong tập hợp tăng lên?

Trước tiên hãy nhìn vào remove. Ở đây không có vòng lặp hay lời gọi hàm nào, điều đó ngụ ý rằng thời gian thực thi của phương thức này lần nào cũng như nhau. Một phương thức như vậy được gọi là thao tác tính toán có thời gian không đổi. Thực tế, phương thức này có thể nhanh hơn một chút nếu danh sách đã rỗng vì khi đó bỏ qua phần thân của câu lệnh điều kiện, song sự khác biệt này là không đáng kể.

Hiệu năng của insert thì rất khác. Trong trường hợp chung, ta phải duyệt qua danh sách để tìm phần tử cuối.

Công việc duyệt này mất một thời gian tỉ lệ thuận với chiều dài danh sách. Vì thời gian thực thi là một hàm tuyến tính của chiều dài nên phương thức này thuộc loại thời gian tuyến tính. So với loại thời gian không đổi, cách này rất tệ.

Hàng đợi liên kết được cải tiến

Ta muốn có cách tạo dựng ADT hàng đợi để có thể thực hiện tất cả những thao tác trong thời gian không đổi. Một cách làm là sửa lại lớp Queue để nó có thể duy trì được tham chiếu đến cả nút đầu và nút cuối, như trên hình vẽ sau:

Cách tạo dựng ImprovedQueue sẽ như sau:

class ImprovedQueue: 
  def __init__(self): 
    self.length = 0 
    self.head   = None 
    self.last   = None 

  def isEmpty(self): 
    return (self.length == 0) 

Đến giờ, thay đổi duy nhất chỉ là thuộc tính last. Nó được dùng trong các phương thức insert và remove:

class ImprovedQueue: 
  ... 
  def insert(self, cargo): 
    node = Node(cargo) 
    node.next = None 
    if self.length == 0: 
      # nếu danh sách rỗng thì nút mới đồng thời là đầu và cuối 
      self.head = self.last = node 
    else: 
      # tìm nút cuối 
      last = self.last 
      # thêm nút mới 
      last.next = node 
      self.last = node 
    self.length = self.length + 1 

Vì last theo dõi nút cuối nên ta không cần tìm kiến nó. Do vậy, phương thức này có tính chất của thời gian không đổi.

Phải trả một cái giá mới đạt được tốc độ như trên. Ta cần bổ sung một trường hợp đặc biệt  vào remove để đặt last thành None khi nút cuối cùng bị gỡ bỏ:

class ImprovedQueue: 
  ... 
  def remove(self): 
    cargo     = self.head.cargo 
    self.head = self.head.next 
    self.length = self.length - 1 
    if self.length == 0: 
      self.last = None 
    return cargo 

Cách tạo dựng này phức tạp hơn tạo dựng danh sách kết nối, và khó cho thấy rằng nó đúng đắn. Ưu điểm là ta đã đạt được mục tiêu     cả insert lẫn remove đều là thao tác có thời gian không đổi.

Bài tập: Hãy viết phần tạo dựng một ADT hàng đợi bằng một danh sách Python. So sánh hiệu năng của cách tạo dựng này với ImprovedQueue theo một khoảng những độ dài dãy khác nhau.

Hàng đợi ưu tiên

ADT hàng đợi ưu tiên có cùng giao diện như ADT hàng đợi, song có ngữ nghĩa khác. Một lần nữa, giao diện là:

__init__
Khởi tạo một hàng đợi mới.
insert
Thêm một phần tử vào hàng đợi. 
remove
Gỡ bỏ đồng thời trả lại một phần tử từ một hàng đợi. Phần tử được trả lại là phần tử có quyền ưu tiên cao nhất.
isEmpty
Kiểm tra xem hàng đợi có rỗng hay không.

Sự khác biệt về ngữ nghĩa bây giờ là ở chỗ  phần tử bị gỡ bỏ khỏi hàng đợi không nhất thiết là phần tử được thêm vào sớm nhất. Mà nó là phần tử trong danh sách có quyền ưu tiên cao nhất. Còn những quyền ưu tiên là gì và cách chúng so sánh với nhau thế nào thì lại không được quy định trong cách tạo dựng hàng đợi ưu tiên. Nó tùy thuộc vào việc có những phần tử nào trong danh sách.

Chẳng hạn, nếu các phần tử trong danh sách có tên, thì ta có thể chọn chúng theo thứ tự bảng chữ cái. Nếu đó là những kết quả thi đấu bowling, ta có thể đi từ cao nhất xuống thấp nhất; nhưng nếu là kết quả thi đấu golf, thì ta sẽ đi từ thấp lên cao. Miễn là có thể so sánh được những phần tử trong hàng đợi thì ta có thể tìm thấy và gỡ bỏ phần tử có độ ưu tiên cao nhất.

Cách tạo lập này của danh sách ưu tiên có một thuộc tính là một danh sách Python có chứa các phần tử trong hàng đợi.

class PriorityQueue: 
  def __init__(self): 
    self.items = [] 

  def isEmpty(self): 
    return self.items == [] 

  def insert(self, item): 
    self.items.append(item) 

Phương thức khởi tạo, isEmpty, và insert đều là các véc-ni cho những thao tác đối với danh sách. Duy nhất có một phương thức đáng quan tâm, đó là remove:

class PriorityQueue: 
  ... 
  def remove(self): 
    maxi = 0 
    for i in range(1,len(self.items)): 
      if self.items[i] > self.items[maxi]: 
        maxi = i 
    item = self.items[maxi] 
    self.items[maxi:maxi+1] = [] 
    return item 

Ở đầu mỗi vòng lặp,  maxi chứa chỉ số của phần tử lớn nhất (có quyền ưu tiên cao nhất) mà ta đã thấy cho đến giờ. Mỗi lần lặp, chương trình lại so sánh phần tử thứ i với phần tử hiện đang là lớn nhất. Nếu phần tử mới còn lớn hơn, thì giá trị maxi sẽ được đặt bằng i.

Khi lệnh for hoàn thành, maxi là chỉ số của phần tử lớn nhất. Phần tử này được gỡ bỏ khỏi danh sách đồng thời được trả lại.

Ta hãy kiểm tra cách tạo dựng trên:

>>> q = PriorityQueue()
>>> q.insert(11)
>>> q.insert(12)
>>> q.insert(14)
>>> q.insert(13)
>>> while not q.isEmpty(): print q.remove()
 14
 13
 12
 11

Nếu hàng đợi chỉ gồm những số hoặc chuỗi đơn giản, thì chúng được gỡ bỏ theo thứ tự độ lớn hoặc thứ tự bảng chữ cái, từ cao xuống thấp. Python có thể tìm ra số nguyên hoặc chuỗi “lớn” nhất vì nó có thể so sánh chúng bằng những toán tử so sánh sẵn có.

Nếu hàng đợi chứa một kiểu đối tượng thì hàng đợi này phải có một phương thức __cmp__. Khi remove dùng toán tử > để so sánh các phần tử, hàng đợi này kích hoạt __cmp__ cho một trong các phần tử đồng thời truyền phần tử còn lại làm đối số. Miễn là phương thức __cmp__ hoạt động đúng thì Priority Queue cũng sẽ hoạt động được.

Lớp Golfer

Xét một ví dụ về đối tượng với cách định nghĩa bất thường đối với quyền ưu tiên. Ta hãy tạo dựng một lớp có tên Golfer để theo dõi tên và điểm số của những người chơi golf. Như thường lệ, ta bắt đầu bằng việc định nghĩa __init__ và __str__:

class Golfer:
  def __init__(self, name, score):
    self.name = name
    self.score= score
  def __str__(self):
    return "%-16s: %d" % (self.name, self.score)

__str__ có sử dụng toán tử định dạng để căn chỉnh các tên và số điểm ngay ngắn theo cột.

Tiếp theo ta định nghĩa một dạng của __cmp__ trong đó điểm thấp nhất ứng với quyền ưu tiên cao nhất. Như thường lệ, __cmp__ trả lại 1 nếu self “lớn hơn” other, -1 nếu self “nhở hơn” other, và 0 trong trường hợp chúng bằng nhau.

class Golfer:
  ...
  def __cmp__(self, other):
    if self.score < other.score: return  1   # less is more 
    if self.score > other.score: return -1
    return 0

Bây giờ ta đã sẵn sàng kiểm tra hàng đợi ưu tiên này bằng cách dùng lớp Golfer:

>>> tiger = Golfer("Tiger Woods",    61)
>>> phil  = Golfer("Phil Mickelson", 72)
>>> hal   = Golfer("Hal Sutton",     69)
>>>
>>> pq = PriorityQueue()
>>> pq.insert(tiger)
>>> pq.insert(phil)
>>> pq.insert(hal)
>>> while not pq.isEmpty(): print pq.remove()
 Tiger Woods    : 61
 Hal Sutton     : 69
 Phil Mickelson : 72

Bài tập: Hãy viết một cách tạo lập ADT Hàng đợi Ưu tiên bằng cách dùng danh sách liên kết. Bạn cần đảm bảo cho danh sách được sắp xếp để thao tác gỡ bỏ được thực hiện trong thời gian không đổi. Hãy so sánh hiệu năng của cách tạo dựng này với cách tạo dựng của danh sách trong Python.

Thuật ngữ

hàng đợi (nghĩa đen)
Một tập hợp những đối tượng đang chờ một hình thức dịch vụ nào đó.
Hàng đợi
Một kiểu dữ liệu trừu tượng (ADT) nhằm thực hiện các thao tác đối với hàng đợi (nghĩa đen).
chính sách xếp hàng
Quy tắc để phân định xem phần tử nào trong hàng đợi sẽ được tách khỏi hàng tiếp đó.
FIFO
“First In, First Out,” (vào trước, ra trước), một chính sách xếp hàng trong đó phần tử đầu tiên vào hàng cũng là phần tử đầu tiên tách khỏi hàng.
hàng đợi ưu tiên
Chính sách xếp hàng trong đó từng phần tử có một quyền ưu tiên chi phối bởi những nhân tố bên ngoài. Phần tử nào có quyền ưu tiên cao nhất sẽ được tách khỏi hàng trước tiên.
Hàng đợi Ưu tiên
Một ADT trong đó quy định những phép thao tác được thực hiện trên hàng đợi ưu tiên (vừa định nghĩa).
hàng đợi liên kết 
Một cách tạo dựng nên hàng đợi có dùng danh sách liên kết.
thời gian không đổi
Một thao tác tính toán trong đó thời gian thực thi không phụ thuộc vào kích thước của cấu trúc dữ liệu.
thời gian tuyến tính
Một thao tác tính toán trong đó thời gian thực thi là một hàm số tuyến tính của kích thước cấu trúc dữ liệu.

1 Phản hồi

Filed under Think Python

One response to “Hàng đợ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