วิธีคิดแบบนักวิทยาการคอมพิวเตอร์/Queues

บทที่ 19 Queues

ในบทนี้จะแสดงให้เห็นถึง ADT 2 ตัวคือ Queue และ Priority Queue ในชีวิตจริงลองนึกว่า queue คือการเข้าแถวรอรับบริการบางอย่าง ในกรณีส่วนใหญ่ลูกค้าคนแรกในแถวคือคนที่ได้รับบริการก่อน แต่ก็ยังมีข้อยกเว้นบางอย่าง เช่นที่สนามบินถ้ามีลูกค้าที่อยู่ในเที่ยวบินที่กำลังจะออกก็จะถูกเรียกจากกลางแถวมาก่อน หรือในซูเปอร์มาร์เก็ตก็จะมีลูกค้าที่สุภาพให้คนที่อยู่หลังได้รับบริการก่อน

กฎที่ใช้ในการตัดสินใจว่าใครจะได้ไปก่อนนั้นเรียกว่า queueing policy การเข้า queue แบบง่ายๆเราเรียกว่า FIFO คือเข้าก่อนออกก่อน และ queueing policy ทั่วๆไปที่พบมากคือ priority queueing ที่ลูกค้าจะถูกกำหนด priority และลูกค้าที่มี priority สูงสุดจะได้ไปก่อน โดยไม่คำนึงถึงลำดับการมาถึง ที่เราเรียกมันว่าเป็น policy ทั่วๆไปเพราะ priority สามารถกำหนดได้ว่าจะให้ขึ้นกับสิ่งใด เช่นเวลาที่เครื่องบินจะออก จำนวนสินค้าที่ลูกค้าถืออยู่ หรือความสำคัญของลูกค้า แน่นอนว่า queueing policy ไม่ทั้งหมดที่จะยุติธรรม แต่อาจดูแล้วลำเอียงบ้างในสายตาผู้ที่เฝ้ามอง

Queue ADT และ Priority Queue ADT มีชุดของ operations เหมือนกัน แต่ต่างกันใน semantics ของ operations โดย queue จะไช้ policy แบบ FIFO และ priority queue จะใช้ policy แบบ priority queueing

19.2 Linked Queue

Queue ADT จะถูกกำหนดโดย operations ตามนี้

__init__ : Initialize a new empty queue.

insert: Add a new item to the queue.

remove: Remove and return an item from the queue. The item that is returned is the first one that was added.

isEmpty: Check whether the queue is empty.

19.2 Linked Queue

Implementation ตัวแรกของ Queue ADT ที่เราจะมาดูกันก็คือ linked queue เพราะมันสร้าง linked เหมือน Node object การ definition คลาสทำได้ดังนี้

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:

# if list is empty the new node goes first

self.head = node

else:

# find the last node in the list

last = self.head

while last.next: last = last.next

# append the new node

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

Method isEmpty และ remove เป็นแบบเดียวกับ method isEmpty และ removeFirst ของ LinkedList โดยมี method ใหม่คือ insert

เราต้องการ insert ตัว items ลงไปเป็น item สุดท้ายของ list ถ้า queue ว่างเปล่าเราแค่ set ค่า head ให้อ้างอิงไปยัง node ใหม่

อีกอย่างหนึ่งคือเราจะเข้าไปใน list จาก node สุดท้ายและ tack ไปยัง node ใหม่ที่ตัวสุดท้าย เราสามารถรู้ได้ว่า node ใดเป็น node สุดท้ายได้โดยดูจาก next attribute ที่มีค่าเป็น None

และยังมีค่าคงที่อีก 2 ตัวที่แสดงถึงคุณลักษณะของ Queue object คือค่าของ length จะแสดงค่าของจำนวน nodes ใน queue และ node สุดท้ายต้องมีค่า next เป็น None คุณจะต้องเตือนตัวเองอยู่เสมอในการรักษาค่าคงทั้ง 2 ตัวที่นี้ให้ถูกต้อง

19.3 Performance characteristics

ตามปกติแล้วเมื่อเราเรียกใช้ method เราไม่ต้องกังวลในเรื่องรายละเอียดของ implementation แต่มีอยู่รายละเอียดหนึ่งที่เราจะต้องรู้คือ the performance characteristics of the method ว่าสามารถรับได้ขนาดยาวเท่าไหร่ และเมื่อมีการทำงานแล้วมีการเพิ่มจำนวน items ใน collection อย่างไร

อันดับแรกมาดูที่ remove ซึ่งไม่มีการใช้ loop หรือการเรียกฟังก์ชันภายในนี้การทำงานของ method นี้เหมือนกันตลอดเวลา จึงเรียก method ประเภทนี้ว่า constant time operation ตัว method จะทำงานได้เร็วเมื่อ list นั้นว่างเปล่าโดยการทำงานมันจะข้ามส่วนตรวจสอบเงื่อนไขอื่นๆภายในไป แต่ความแตกต่างนี้ไม่ถือว่าสำคัญ

Performance ของ insert มีความแตกต่างกันมาก ในกรณีทั่วไปเราจะต้องเข้าไปใน list เพื่อหา element สุดท้ายของ list

การเข้าไปหานี้ใช้เวลามากหรือน้อยขึ้นอยู่กับ length ของ list โดยเวลาทำงานมันจะเรียกฟังก์ชันไปตาม length ของ list จึงเรียก method ประเภทนี้ว่า linear time เมื่อเปรียบเทียบกับ constant time แล้วถือว่าแย่มาก

19.4 Improved Linked Queue

เราชอบ implementation ของ Queue ADT ที่มันดำเนินการแบบ constant time ทางหนึ่งที่เราจะแก้ไขคลาส Queue ให้มันมีการอ้างอิงถึงส่วน node แรกและ node สุดท้ายดังแบบที่แสดงในรูป

ImprovedQueue implementation จะมีลักษณะดังนี้

class ImprovedQueue:

def __init__(self):

self.length = 0

self.head = None

self.last = None

def isEmpty(self):

return (self.length == 0)

สิ่งที่เปลี่ยนแปลงไปคือ attribute last ที่ใช้ใน insert และ remove method

โดย last จะเก็บ node สุดท้าย เราจึงไม่จำเป็นที่จะต้องค้นหามันจึงทำให้ method นี้เป็นแบบ constant time

นั่นทำให้เราสามารถซื้อความเร็วในการทำงานมาได้ เราก็แค่เพิ่มกรณีพิเศษที่ remove ในการกำหนดค่าให้ last มีค่าเป็น None ในกรณีที่ node สุดท้ายถูก remove ออกไป

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

Implementation นี้จะยุ่งยากกว่าของ Linked Queue และยากที่จะทำให้เห็นว่ามันถูกต้องแต่มันทำให้เราบรรลุถึงเป้าหมายที่วางไว้คือการทำให้ insert และ remove เป็นแบบ constant time

19.5 Priority queue

Priority Queue ADT มี interface ที่เหมือนกับ Queue ADT แต่ต่างกันที่ semantics ซึ่ง interface จะมีดังนี้

__init_ : Initialize a new empty queue.

insert: Add a new item to the queue.

remove: Remove and return an item from the queue. The item that is returned is the one with the highest priority.

isEmpty: Check whether the queue is empty.

Semantic ที่แตกต่างกันคือตรงการ remove ออกจาก Queue นั้นไม่จำเป็นที่จะต้องเป็นตัวแรกที่เพิ่งถูก add เข้าไป แต่เป็น item ใน queue ที่มีค่า priority สูงสุด อะไรคือ priorities และจะทำการเปรียบเทียบกันอย่างไร มันไม่ได้ถูกระบุไว้ไน Priority Queue implementation มันขึ้นอยู่กับ items ใน Queue

ตัวอย่างเช่นถ้า items ใน queue มีชื่อเราอาจเลือกตามลำดับอักษร ถ้ามันใช้การให้คะแนนแบบเกม Bowling เราก็อาจเลือกจากคะแนนสูงสุดมาต่ำสุด ถ้ามีการให้คะแนนแบบเกม Golf ก็ต้องเลือกจากคะแนนต่ำสุดมาสูงสุด มีอยู่หลายวิธีที่จะทำการเปรียบเทียบ items ใน queue เราจะต้องทำการหาและ remove ตัวที่มี priority สูงสุด

Implementation นี้ของ Priority Queue มี attribute ของ Python list ที่บรรจุ items ใน queue

class PriorityQueue:

def __init__(self):

self.items = []

def isEmpty(self):

return self.items == []

def insert(self, item):

self.items.append(item)

Initialization method, isEmpty และ insert ทั้งหมด veneer โดย list operations และ method ที่น่าสนใจคือ 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

เริ่มต้นจาก maxi ที่เก็บค่า index ของ item ที่มีค่ามากที่สุด (priority สูงสุด) ในการวนซ้ำแต่ละรอบจะทำการเปรียบเทียบ i-eth item กับค่าสูงสุดถ้า item ใหม่มีค่าสูงกว่าค่าของ maxi ก็จะถูกเปลี่ยนค่าเป็น i

เมื่อ for ทำงานเสร็จสิ้น maxi ก็จะเป็น index ของ item ที่มีค่ามากที่สุด item นั้นจะถูก remove ออกจาก list และ return ค่าออกมา

ลองทดสอบการ implementation ดู

>>> 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

ถ้า Queue มีการเก็บค่าของตัวเลขหรือตัวอักษรแบบง่ายๆ มันก็จะถูก remove ตามลำดับของตัวเลขหรืออักษรจากสูงสุดไปต่ำสุด Python สามารถหาค่าตัวเลขที่สูงสุดหรืออักษรได้เพราะมันเปรียบเทียบโดยใช้ built-in comparison operators

ถ้า Queue เก็บค่าที่เป็น object type มันจะต้องมี __cmp__ method เมื่อ remove ให้ใช้ > operator เพื่อเปรียบเทียบ items มันจะเรียก __cmp__ สำหรับหนึ่ง items และส่งผ่านค่าไปยังตัวอื่นโดยผ่าน parameter ถ้า __cmp__ method ทำงานได้ถุกต้อง Priority Queue ก็สามารถทำงานได้

19.6 The Golfer class

เพื่อเป็นตัวอย่างของการใช้ priority ที่พบได้ไม่บ่อย เรามา implement คลาสซึ่งเรียกว่า Golfer ที่ทำการเก็บค่า name และ score ของนักกอล์ฟเราเริ่มต้นจากการ define __init__ และ __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__ ใช้รูปแบบ operator เพื่อใส่ค่า names และ scores ใน column ที่ดูเรียบร้อยต่อมาก็ define __cmp__ ใช้ค่า score น้อยมีค่า priority สูงโดยปกติแล้ว __cmp__ จะ return ค่า 1 ถ้ามันมีค่ามากกว่า -1 ถ้ามีค่าน้อยกว่า และ 0 เมิอมีค่าเท่ากัน

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

ตอนนี้เราพร้อมที่จะทดสอบ priority queue ด้วยคลาส 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

19.7 Glossary

queue: An ordered set of objects waiting for a service of some kind.

Queue: An ADT that performs the operations one might perform on a queue.

queueing policy: The rules that determine which member of a queue is removed next.

FIFO: “First In, First Out,” a queueing policy in which the first member to arrive is the first to be removed.

priority queue: A queueing policy in which each member has a priority determined by external factors. The member with the highest priority is the first to be removed.

Priority Queue: An ADT that defines the operations one might perform on a priority queue.

linked queue: An implementation of a queue using a linked list.

constant time: An operation whose runtime does not depend on the size of the data structure.

linear time: An operation whose runtime is a linear function of the size of the data structure.