ถึงตอนนี้ เราได้เรียนโครงสร้างข้อมูลหลักๆ ของไพธอนไปแล้ว และเราก็ได้เห็นอัลกอริทึมที่ใช้มันไปบ้างแล้วด้วย ถ้าอยากรู้เรื่องอัลกอริทึมมากขึ้น อาจถึงเวลาแล้วที่จะไปอ่าน บท B แต่ก็ไม่ได้จำเป็นว่าจะต้องอ่าน ก่อนจะเรียนบทนี้ จริงๆ จะอ่านตอนไหนก็ได้ที่สนใจ
บทนี้นำเสนอกรณีตัวอย่างด้วยแบบฝึกหัด ที่จะช่วยให้คิดเรื่องเลือกโครงสร้างข้อมูล และก็จะได้ฝึกใช้มันด้วย
เหมือนเคย ที่อย่างน้อย เราควรจะลองทำแบบฝึกหัดด้วยตัวเองก่อนที่จะไปเปิดดูเฉลย
แบบฝึกหัด 1
เขียนโปรแกรมให้อ่านไฟล์ แล้วแยกแต่ละบรรทัดออกเป็นคำๆ เอาช่องว่างต่างๆ (whitespace) และเครื่องหมายวรรคตอนต่างๆ (punctuation) ออกจากคำ และแปลงให้เป็นอักษรตัวเล็ก (lowercase)
คำใบ้: โมดูล string มีสายอักขระชื่อ whitespace และสายอักขระชื่อ punctuation. สายอักขระ whitespace มีอักขระช่องว่าง (space) อักขระตั้งระยะ (tab) อักขระขึ้นบรรทัดใหม่ (newline) เป็นต้น. สายอักขระ punctuation มีอักขระเครื่องหมายวรรคตอนต่างๆ. ลองดู
>>> import string >>> string.punctuation '!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~'
นอกจากนั้น อาจจะลองดูเมธอดของสายอักขระ เช่น เมธอด strip เมธอด replace และเมธอด translate
แบบฝึกหัด 2.
ลองดูโครงการกูเทินแบร์ค (http://gutenberg.org) และดาวน์โหลดหนังสือที่ชอบ ที่หมดลิขสิทธิ์ไปแล้ว ดาวน์โหลดไฟล์มาในรูป ข้อความธรรมดา (plain text) ดัดแปลงโปรแกรมจากแบบฝึกหัดที่แล้ว เพื่ออ่านหนังสือที่ดาวน์โหลดมา ข้ามพวกข้อมูลประกอบที่อยู่ตอนต้นของไฟล์ และประมวลผลส่วนที่เหลือ
จากนั้น ดัดแปลงโปรแกรมให้นับจำนวนคำทั้งหมดในหนังสือ และจำนวนครั้งที่แต่ละคำปรากฏ
พิมพ์จำนวนคำต่างๆ ที่พบในหนังสือ เปรียบเทียบหนังสือจากนักเขียนต่างๆ ที่เขียนคนละยุค นักเขียนคนไหนที่ใช้คำศัพท์ได้กว้างขวางหลากหลายที่สุด?
แบบฝึกหัด 3
ดัดแปลงโปรแกรมจากแบบฝึกหัดที่แล้ว เพื่อพิมพ์คำที่ใช้มากที่สุด 20 คำในหนังสือ
แบบฝึกหัด 4
ดัดแปลงโปรแกรมที่แล้ว เพื่อให้อ่านลิสต์ของคำ (ดูหัวข้อ 9.1) แล้วพิมพ์ทุกคำในหนังสือที่ไม่ได้อยู่ในลิสต์ของคำ มีกี่คำที่เจอที่พิมพ์ผิด? มีกี่คำที่เป็นคำทั่วๆ ไป ที่ควรจะอยู่ในลิสต์ของคำ และมีกี่คำที่คลุมเครือ?
ถ้าได้อินพุตเหมือนๆ กัน คอมพิวเตอร์(ส่วนใหญ่) จะให้เอาต์พุตออกมาเหมือนกันทุกครั้ง ลักษณะแบบนี้ เรียกว่า ลักษณะชี้เฉพาะ (deterministic) ลักษณะการชี้เฉพาะ โดยทั่วไปแล้วมันก็ดี เพราะว่า เรามั่นใจได้ว่า การคำนวณแบบเดียวกัน จะได้ผลออกมาแบบเดียวกัน แต่สำหรับงานบางลักษณะ เราต้องการให้คอมพิวเตอร์มีลักษณะที่เดาไม่ได้บ้าง เกมส์ก็เป็นตัวอย่างหนึ่ง แต่ยังมีตัวอย่างอื่นๆ อีกมาก ที่ต้องลักษณะเดาไม่ได้
การที่จะเขียนโปรแกรมให้ไม่เป็นลักษณะชี้เฉพาะ เลย คือเดาไม่ได้จริงๆ ทำยากมาก แต่ก็มีหลายวิธีที่ อย่างน้อย ก็ช่วยให้โปรแกรมดูเหมือนว่า ไม่เป็นลักษณะชี้เฉพาะ หนึ่งให้วิธีเหล่านั้นก็คือ ใช้อัลกอริทึมที่สร้างตัวเลขสุ่มเทียม (pseudorandom) ค่าของตัวเลขสุ่มเทียม ไม่ได้ถูกสุ่มขึ้นมาจริงๆ แต่มันจะสร้างมาจากการคำนวณลักษณะชี้เฉพาะ ที่ทำให้ ตัวเลขที่ได้ ถ้าดูเผินๆ มันจะดูเหมือนว่าถูกสุ่มมา
โมดูล random มีฟังก์ชันต่างๆ ที่สามารถสร้างตัวเลขสุ่มเทียมได้ (ซึ่งตั้งแต่นี้ไป เราจะแค่เรียกสั้นๆ ว่า “สุ่ม”)
ฟังก์ชัน random จะให้จำนวนจริงที่มีค่าสุ่มมาระหว่าง 0.0 ถึง 1.0 (รวม 0.0 แต่ไม่รวม 1.0) ทุกครั้งที่เราเรียก random เราจะได้เลขสุ่มใหม่ ซึ่งเป็นเลขถัดไป ในลำดับที่ยาวมาก เพื่อให้เห็นตัวอย่าง ลองรันลูปนี้:
import random for i in range(10): x = random.random() print(x)
ฟังก์ชัน randint รับพารามิเตอร์ low และ high แล้วให้ค่าสุ่มเลขจำนวนเต็มระหว่าง low และ high ออกมา (รวมค่า low และ high ด้วย)
>>> random.randint(5, 10) 5 >>> random.randint(5, 10) 9
เพื่อเลือกอิลิเมนต์จากลำดับแบบสุ่ม เราสามารถใช้ choice ได้:
>>> t = [1, 2, 3] >>> random.choice(t) 2 >>> random.choice(t) 3
โมดูล random ยังมีฟังก์ชันต่างๆ ที่สร้างค่าสุ่มจากการแจกแจงต่อเนื่อง (continuous distributions) รวมถึง การแจกแจงแบบเกาส์เซียน (Gaussian distribution) การแจกแจงแบบเลขชี้กำลัง (exponential distribution) การแจกแจงแกมมา (gamma distribution) เป็นต้น
แบบฝึกหัด 13.5
เขียนฟังก์ชันชื่อ choose_from_hist ที่รับฮิสโตแกรม (histogram) แบบที่กำหนดในหัวข้อ 11.2 และรีเทิร์นค่าสุ่มจากฮิสโตแกรม นั่นคือ เลือกค่าสุ่มด้วยความน่าจะเป็น ให้เป็นสัดส่วนตามความถี่ในฮิสโตแกรม ตัวอย่าง สำหรับฮิสโตแกรมนี้:
>>> t = ['a', 'a', 'b'] >>> hist = histogram(t) >>> hist {'a': 2, 'b': 1}
ฟังก์ชันควรจะให้ a ออกมาด้วยความน่าจะเป็น $2/3$ และให้ b ออกมาด้วยความน่าจะเป็น $1/3$
ควรจะลองทำแบบฝึกหัดที่แล้ว ก่อนจะอ่านเรื่องนี้ต่อ. โปรแกรมเฉลยดาวน์โหลดได้จาก http://thinkpython2.com/code/analyze_book1.py และก็อาจจะต้องการ อันนี้ด้วย http://thinkpython2.com/code/emma.txt
นี่เป็นโปรแกรม ที่อ่านไฟล์ และสร้างฮิสโตแกรมของคำต่างๆ ในไฟล์:
import string def process_file(filename): hist = dict() fp = open(filename) for line in fp: process_line(line, hist) return hist def process_line(line, hist): line = line.replace('-', ' ') for word in line.split(): word = word.strip(string.punctuation + string.whitespace) word = word.lower() hist[word] = hist.get(word, 0) + 1 hist = process_file('emma.txt')
โปรแกรมนี้อ่านไฟล์ emma.txt เป็นนิยายเรื่อง เอ็มม่า (Emma) เขียนโดน เจน ออสเทน (Jane Austen)
ฟังก์ชัน process_file ลูปวนทีละบรรทัดของไฟล์ ส่งแต่ละบรรทัดไปที่ process_line. ฮิสโตแกรม hist ถูกใช้เป็น ตัวสะสม (accumulator) สะสมค่าความถี่จากแต่ละบรรทัด
ฟังก์ชัน process_line ใช้เมธอดของสายอักขระ replace เพื่อแทนที่ เครื่องหมายยัติภังค์ (hyphen) ด้วยช่องว่าง ก่อนที่จะใช้เมธอด split เพื่อแยกบรรทัด ออกไปเป็นลิสต์ของสายอักขระ มันท่องสำรวจลิสต์ของคำ และใช้เมธอด strip และเมธอด lower เพื่อตัดเครื่องหมายวรรคตอน ต่างๆ และแปลงเป็นอักษรตัวเล็ก (อาจจะพูดสั้นๆ ว่า สายอักขระถูก“แปลง” แต่ถ้าจำได้ สายอักขระเป็นข้อมูลที่ไม่สามารถเปลี่ยนแปลงได้ ดังนั้น เมธอดพวก strip และ lower จะให้สายอักขระใหม่ออกมา)
สุดท้าย ฟังก์ชัน process_line ปรับค่าของฮิสโตแกรม โดยการสร้างรายการสำหรับคำใหม่ หรือเพิ่มค่าให้กับคำที่มีอยู่แล้ว
เพื่อจะนับจำนวนคำทั้งหมดในไฟล์ เราสามารถรวมความถี่ต่างๆ ในฮิสโตแกรมได้:
def total_words(hist): return sum(hist.values())
จำนวนคำศัพท์ ก็คือจำนวนรายการในดิกชันนารี:
def different_words(hist): return len(hist)
นี่เป็นโปรแกรมสำหรับพิมพ์ผลลัพธ์ออกมา:
print('Total number of words:', total_words(hist)) print('Number of different words:', different_words(hist))
และผลลัพธ์ที่ได้:
Total number of words: 161080 Number of different words: 7214
เพื่อจะหาคำศัพท์ที่ใช้บ่อยที่สุด เราสามารถสร้างลิสต์ของทูเพิล ที่แต่ละทูเพิลมีคำศัพท์และความถี่ของมัน แล้วก็จัดเรียงมัน
ฟังก์ชันต่อไปนี้รับฮิสโตแกรม และคืนค่า ลิสต์ของทูเพิล ที่ทูเพิลเป็นคู่ของคำกับความถี่:
def most_common(hist): t = [] for key, value in hist.items(): t.append((value, key)) t.sort(reverse=True) return t
ในแต่ละทูเพิล ความถี่แสดงก่อนคำ และผลลัพธ์ก็เรียงลำดับตามความถี่จากมากไปน้อย นี่เป็นลูปที่พิมพ์คำสิบคำที่พบบ่อยที่สุดออกมา:
t = most_common(hist) print('The most common words are:') for freq, word in t[:10]: print(word, freq, sep='\t')
อาร์กิวเมนต์ sep บอกคำสั่ง print ให้ใช้อักขระตั้งระยะ เป็น “ตัวแยก” แทนช่องว่าง ทำให้คอลัมน์ที่สองเรียงกันเป็นแนว นี่เป็นผลลัพธ์ที่ได้จากนิยายเอ็มม่า
The most common words are: to 5242 the 5205 and 4897 of 4295 i 3191 a 3130 it 2529 her 2483 was 2400 she 2364
โปรแกรมนี้จริงๆ สามารถเขียนให้ง่ายกว่านี้ได้ โดยใช้พารามิเตอร์ key ของฟังก์ชัน sort ถ้าสนใจ ลองศึกษาดูได้จาก https://wiki.python.org/moin/HowTo/Sorting
เราได้ดูฟังก์ชันสำเร็จรูป และเมธอดต่างๆ ที่รับพารามิเตอร์เสริมมาแล้ว เราเองก็เขียนฟังก์ชันที่รับพารามิเตอร์เสริมได้เหมือนกัน ตัวอย่าง นี่เป็นฟังก์ชันที่พิมพ์คำที่พบบ่อยที่สุดในฮิสโตแกรมออกมา
def print_most_common(hist, num=10): t = most_common(hist) print('The most common words are:') for freq, word in t[:num]: print(word, freq, sep='\t')
พารามิเตอร์แรกต้องใส่ แต่พารามิเตอร์ที่สองเป็นพารามิเตอร์เสริม ถ้าไม่ใส่ num จะใช้ค่าดีฟอลท์ (default) เป็น 10
ถ้าเรียกใช้ ด้วยหนึ่งอาร์กิวเมนต์:
print_most_common(hist)
ตัวแปร num จะใช้ค่าดีฟอลท์ แต่ถ้าเรียกใช้ ด้วยอาร์กิวเมนต์สองตัว:
print_most_common(hist, 20)
ตัวแปร num จะใช้ค่าของอาร์กิวเมนต์ พูดง่ายๆ คือ อาร์กิวเมนต์เสริมไปแทนที่ค่าดีฟอลท์.
ถ้าฟังก์ชันมีทั้งพารามิเตอร์บังคับ และพารามิเตอร์เสริม พารามิเตอร์บังคับทุกตัวต้องมาก่อน แล้วค่อยตามด้วยพารามิเตอร์เสริม
การหาคำที่มีในหนังสือ แต่ไม่มีในลิสต์ของคำศัพท์จาก words.txt ก็เหมือนกับปัญหาการลบของเซต นั่นคือ เราต้องการหาคำทุกคำจากเซตหนึ่ง (คำต่างๆ ในหนังสือ) ที่ไม่ได้อยู่ในอีกเซตหนึ่ง (คำต่างๆ ในลิสต์)
ฟังก์ชัน subtract รับดิกชันนารีสองตัว คือ d1 และ d2 แล้วรีเทิร์นดิกชันนารีใหม่ออกมา โดย ดิกชันนารีใหม่มีกุญแจทั้งหมดจาก d1 ที่ไม่มีใน d2 และเพราะเราไม่สนใจค่าของมัน เราจะให้ค่าในคู่กุญแจค่าทุกรายการเป็น None
def subtract(d1, d2): res = dict() for key in d1: if key not in d2: res[key] = None return res
เพื่อหาคำในหนังสือที่ไม่มีอยู่ใน words.txt เราก็สามารถใช้ฟังก์ชัน process_file เพื่อสร้างฮิสโตแกรมสำหรับ words.txt แล้วค่อยลบออกได้:
words = process_file('words.txt') diff = subtract(hist, words) print("Words in the book that aren't in the word list:") for word in diff: print(word, end=' ')
อันนี้เป็นผลลัพธ์ที่ได้จากนิยายเอ็มม่า:
Words in the book that aren't in the word list: rencontre jane's blanche woodhouses disingenuousness friend's venice apartment ...
เห็นได้ว่า บางคำเป็นชื่อและคำแสดงความเป็นเจ้าของต่างๆ คำอื่นๆ เช่น “rencontre” ก็เป็นคำที่ไม่ค่อยใช้เท่าไรแล้วในปัจจุบัน แต่ก็มีหลายๆ คำที่เป็นคำศัพท์ธรรมดา ที่จริงๆ แล้วควรจะมีอยู่ในลิสต์
แบบฝึกหัด 13.6. ไพธอนมีโครงสร้างข้อมูลที่เรียกว่า set ที่มีตัวดำเนินการของเซตอยู่หลายตัว ถ้าสนใจ ลองอ่านหัวข้อ 19.5 หรือศึกษาดูเอกสารที่ http://docs.python.org/3/library/stdtypes.html#types-set
เขียนโปรแกรมที่ใช้การลบเซต เพื่อหาคำต่างๆ ในหนังสือ ที่ไม่อยู่ในลิสต์ของคำ เฉลย: http://thinkpython2.com/code/analyze_book2.py
เพื่อเลือกสุ่มคำตามฮิสโตแกรม อัลกอริทึมที่ง่ายที่สุด คือสร้างลิสต์ที่มีหลายๆ สำเนาของแต่ละคำ โดยจำนวนสำเนาเป็นไปตามความถี่ แล้วก็สุ่มเลือกคำจากลิสต์:
def random_word(h): t = [] for word, freq in h.items(): t.extend([word] * freq) return random.choice(t)
นิพจน์ [word] * freq สร้างลิสต์ขึ้นมาด้วย สำเนาของสายอักขระ word เป็นจำนวน freq สำเนา เมธอด extend คล้ายกับ append เพียงแต่ อาร์กิวเมนต์เป็นข้อมูลลำดับ
อัลกอริทึมนี้ก็ทำงานได้ แต่ว่า มันไม่มีประสิทธิภาพ ทุกครั้งที่เราเลือกสุ่มคำออกมา มันก็ต้องสร้างลิสต์ขึ้นใหม่ ซึ่งลิสต์ก็ใหญ่พอๆ กับหนังสือเลย. วิธีปรับปรุงที่เห็นได้ชัดๆ เลย ก็คือ สร้างลิสต์ขึ้นมาทีเดียว และใช้มันหลายๆ ครั้ง แต่ลิสต์ก็ยังใหญ่อยู่ วิธีอื่นที่ดีกว่า ก็คือ
keys เพื่อเอาลิสต์ของคำต่างๆ (คำไม่ซ้ำ) จากหนังสือออกมา
แบบฝึกหัด 7
เขียนโปรแกมที่ใช้อัลกอริทึมนี้ เพื่อสุ่มคำขึ้นมาจากหนังสือ เฉลย: http://thinkpython2.com/code/analyze_book3.py
ถ้าเราสุ่มเลือกคำต่างๆ มาจากหนังสือ เราอาจจะได้เห็นคำศัพท์ต่างๆ แต่เราจะไม่ได้เห็นประโยค
this the small regard harriet which knightley's it most things
ลำดับของคำสุ่มๆ ยากที่จะทำให้รู้เรื่องอะไรได้ เพราะว่ามันไม่มีความสัมพันธ์ระหว่างคำต่างๆ ที่ต่อๆ กัน ตัวอย่างเช่น ในประโยคจริงๆ (ในภาษาอังกฤษ) เราน่าจะเห็นคำกำกับนาม (article) เช่น “the” แล้วน่าก็ตามด้วยคำคุณศัพท์ หรือคำนาม ไม่น่าตามด้วยคำกริยา หรือคำวิเศษณ์
วิธีหนึ่งที่ใช้อธิบายความสัมพันธ์ในลักษณะแบบนี้ คือ การวิเคราะห์มาร์คอฟ (Markov analysis) ที่ช่วยประมาณความน่าจะเป็นของคำต่อไป ของลำดับของคำ ตัวอย่าง เพลง Eric, the Half a Bee เริ่มด้วย:
Half a bee, philosophically,
Must, ipso facto, half not be.
But half the bee has got to be
Vis a vis, its entity. D’you see?
But can a bee be said to be
Or not to be an entire bee
When half the bee is not a bee
Due to some ancient injury?
ในเนื้อเพลงนี้ วลี “half the” จะตามด้วยคำว่า “bee” เสมอ แต่วลี “the bee” อาจจะตามด้วย “has” หรือ “is”
ผลลัพธ์จากการวิเคราะห์มาร์คอฟเป็นการแปลงจาก พรีฟิกซ์ (prefix) (เช่น “half the” และ “the bee”) ไปเป็นคำต่อมา หรือ ซับฟิกซ์ (suffix) ทุกๆ คำที่เป็นไปได้ (เช่น “has” และ “is”)
ด้วยการแปลงแบบนี้ เราสามารถสร้างข้อความสุ่มได้ เริ่มจาก พรีฟิกซ์ คำไหนก็ได้ แล้วเลือกคำต่อมาโดยสุ่มจากซับฟิกซ์ที่เป็นไปได้ จากนั้น เราก็สามารถใช้คำในพรีฟิกซ์กับคำต่อมาที่ได้ มาสร้างเป็นพรีฟิกซ์ใหม่ แล้วก็ทำต่อไปเรื่อยๆ
ตัวอย่างเช่น ถ้าเราเริ่มด้วยพรีฟิกซ์ คำว่า “Half a” และคำถัดมาจะเป็น “bee” เพราะว่าพรีฟิกซ์นี้ปรากฏแค่ครั้งเดียวในเนื้อเพลง (และมันตามด้วย “bee”) พรีฟิกซ์ใหม่จะเป็น “a bee” ดังนั้นซับฟิกซ์ต่อไปอาจจะเป็น “philosophically” หรือ “be” หรือ “due” ก็ได้
ตัวอย่างนี้ ใช้พรีฟิกซ์มีความยาวเป็น สองคำ เสมอ แต่จริงๆ แล้ว เราสามารถทำการวิเคราะห์มาร์คอฟกับพรีฟิกซ์ความยาวเท่าไรก็ได้
แบบฝึกหัด 8
การวิเคราะห์มาร์คอฟ:
เขียนโปรแกรม เพื่ออ่านข้อความจากไฟล์ และทำการวิเคราะห์มาร์คอฟ ผลลัพธ์ควรจะเป็นดิกชันนารีที่แปลงจากพรีฟิกซ์ ไปเป็นกลุ่มหมู่ของซับฟิกซ์ต่างๆ ที่เป็นไปได้ กลุ่มหมู่ที่ใช้ อาจจะทำเป็นลิสต์ หรือทูเพิล หรือดิกชันนารี ก็ได้ตามใจชอบ ตามที่เห็นสมควรเลย ทำเสร็จแล้ว ลองทดสอบโปรแกรมด้วย พรีฟิกซ์ความยาวสองก่อน และตัวโปรแกรมเองก็ควรจะเขียนแบบที่ทำให้ง่าย ถ้าต้องการจะเปลี่ยนพรีฟิกซ์เป็นความยาวอื่นๆ
เพิ่มฟังก์ชันเข้าไปในโปรแกรมที่แล้ว เพื่อสร้างข้อความสุ่ม โดยใช้การวิเคราะห์มาร์คอฟ ตัวอย่างนี้มาจากนิยายเอ็มม่า ที่ใช้พรีฟิกซ์ยาวสองคำ:
He was very clever, be it sweetness or be angry, ashamed or only amused, at such a stroke. She had never thought of Hannah till you were never meant for me?“ “I cannot make speeches, Emma:” he soon cut it all himself.
ตัวอย่างนี้ ปล่อยพวกเครื่องหมายวรรคตอนติดไปกับคำ ผลที่ได้เกือบถูกตามวากยสัมพันธ์ แต่ก็ยังไม่ถูก สำหรับความหมาย มันก็เกือบได้ แต่ก็ยังไม่ได้
จะเกิดอะไรขึ้น ถ้าเราเพิ่มความยาวของพรีฟิกซ์? ข้อความสุ่มจะฟังมีความหมายมากขึ้นหรือเปล่า?
ถ้าโปรแกรมทำงานได้แล้ว อาจจะลองผสมดู: ถ้าเราผสมข้อความจากหนังสือสองเล่มหรือมากกว่าเข้าด้วยกัน ข้อความสุ่มที่สร้างขึ้นมา จะผสมคำศัพท์หรือวลี จากแหล่งต่างๆ เข้าด้วยกัน
กรณีศึกษานี้ ดัดแปลงจากตัวอย่างของ การปฎิบัติของการเขียนโปรแกรม โดย เคอนิแกนและไพค์ (Kernighan and Pike, The Practice of Programming, Addison-Wesley, 1999.)
ควรจะไปลองทำแบบฝึกหัดนี้ ก่อนที่จะศึกษาเนื้อหาต่อไป สามารถดาวน์โหลดเฉลยได้จาก http://thinkpython2.com/code/markov.py และอาจจะต้องไฟล์ประกอบ http://thinkpython2.com/code/emma.txt
ตอนใช้การวิเคราะห์มาร์คอฟ เพื่อสร้างข้อความสุ่มก็สนุกดี แต่จริงๆ แล้ว มันมีประเด็นที่สำคัญของแบบฝึกหัดนี้ คือ การเลือกใช้โครงสร้างข้อมูล เวลาทำแบบฝึกหัดที่แล้ว เราต้องเลือก:
อันสุดท้ายอาจจะง่าย ดิกชันนารีเป็นตัวเลือกที่ชัดเจน สำหรับการแปลงกุญแจต่างๆ ไปหาค่าต่างๆ ที่คู่กัน
สำหรับพรีฟิกซ์ ตัวเลือกที่ชัดๆ ก็มี สายอักขระ หรือ ลิสต์ของสายอักขระ หรือ ทูเพิลของสายอักขระ
สำหรับซับฟิกซ์ ตัวเลือกหนึ่งคือ ลิสต์ อีกอันคือ ฮิสโตแกรม (ดิกชันนารี)
เราควรจะเลือกอย่างไร? ขั้นแรก คือ คิดถึงการดำเนินการต่างๆ ที่เราต้องเขียนสำหรับแต่ละโครงสร้างข้อมูล สำหรับซับฟิกซ์ เราต้องสามารถลบคำต้นๆ ออก และเพิ่มคำเข้าทางท้ายๆ ได้ ตัวอย่างเช่น ถ้าซับฟิกซ์ เป็น “Half a” และคำต่อไปเป็น “bee” เราต้องสามารถสร้างพรีฟิกซ์ต่อไปเป็น “a bee” ได้
ตัวเลือกแรกๆ ของเรา อาจจะเป็นลิสต์ เพราะว่า มันง่ายที่จะเพิ่ม หรือลบอิลิเมนต์ แต่เราก็ต้องการใช้พรีฟิกซ์เป็นกุญแจของดิกชันนารีด้วย ดังนั้นจึงใช้ลิสต์ไม่ได้ ถ้าใช้ทูเพิล เราจะเพิ่มหรือลบไม่ได้ แต่เราสามารถใช้ตัวดำเนินการบวก เพื่อสร้างทูเพิลใหม่ได้:
def shift(prefix, word): return prefix[1:] + (word,)
ฟังก์ชัน shift รับทูเพิลของคำต่างๆ ด้วยชื่อ prefix และรับสายอักขระ ด้วยชื่อ word แล้วสร้างทูเพิลใหม่ ที่มีทุกคำใน prefix ยกเว้นคำแรก และเพิ่มคำจาก word เข้าไปท้ายทูเพิลใหม่
สำหรับกลุ่มหมู่ของซับฟิกซ์ ตัวดำเนินการต่างๆ ที่เราต้องเขียน รวมถึงการเพิ่มซับฟิกซ์ใหม่ (หรือเพิ่มความถี่ของซับฟิกซ์ที่มีอยู่แล้ว) แล้วค่อยสุ่มเลือกซับฟิกซ์
การเพิ่มซับฟิกซ์ใหม่นั้น นั้นไม่ว่าใช้ลิสต์ หรือใช้ฮิสโตแกรม ก็ทำได้ง่ายพอๆ กัน แต่การสุ่มเลือกอิลิเมนต์จากลิสต์ทำได้ง่าย ในขณะที่การสุ่มเลือกจากฮิสโตแกรมอย่างมีประสิทธิภาพทำได้ยากทีเดียว (ดูแบบฝึกหัด แบบฝึกหัด 13.7)
ที่ผ่านมา เราได้พูดถึงแต่เรื่องของความง่ายในการอิมพลิเมนเตชั่น แต่มันยังมีปัจจัยอื่นๆ ที่ควรต้องพิจารณาในการเลือกโครงสร้างข้อมูลด้วย ปัจจัยหนึ่งคือ เวลาทำงาน (run time) บางครั้ง เรามีเหตุผล ในทางทฤษฎี ที่เชื่อว่า โครงสร้างข้อมูลชนิดหนึ่งจะทำงานได้เร็วกว่าชนิดอื่นๆ ตัวอย่างเช่น เราเคยอภิปรายกันว่า ตัวดำเนินการ in ทำงานกับดิกชันนารี ได้เร็วกว่า ทำงานกับลิสต์ (อย่างน้อยก็ในกรณีที่จำนวนอิลิเมนต์เยอะๆ)
แต่ส่วนใหญ่ เราไม่รู้ก่อนหรอกว่า การอิมพลิเมนเตชั่นแบบไหนจะเร็วกว่า แนวทางเลือกหนึ่งก็คือ ลองอิมพลิเมนเตชั่นทั้งสองแบบเลย แล้วค่อยดูว่าแบบไหนดีกว่า แนวทางแบบนี้ เรียกว่า การวัดเปรียบเทียบสมรรถนะ (benchmarking) อีกแนวทางเลือกที่นิยมในทางปฏิบัติคือ เลือกโครงสร้างข้อมูลที่ทำอิมพลิเมนเตชั่น หรือเขียนโปรแกรมได้ง่ายที่สุด แล้วค่อยดูว่า ผลลัพธ์เร็วพอ สำหรับงานที่ต้องการหรือเปล่า ถ้าเร็วพอแล้ว ก็ไม่มีความจำเป็นต้องทำอะไรอย่างอื่น แต่ถ้าไม่เร็วพอ มันก็มีเครื่องมือต่างๆ เช่น โมดูล profile ที่ช่วยระบุส่วนของโปรแกรมที่ใช้เวลามากที่สุด
ปัจจัยอื่นที่มักนำมาพิจารณาก็ เช่น พื้นที่เก็บข้อมูล (storage space) ตัวอย่างเช่น การใช้ฮิสโตแกรม สำหรับกลุ่มหมู่ของซับฟิกซ์ต่างๆ อาจจะใช้พื้นที่เก็บข้อมูลน้อยกว่า เพราะว่า เราเก็บแต่ละคำแค่ครั้งเดียว ไม่ว่าคำนั้นจะปรากฎในข้อความกี่ครั้งก็ตาม ในบางกรณี การประหยัดพื้นที่ อาจจะช่วยทำให้โปรแกรมรันได้เร็วขึ้นด้วย และถ้ากรณีที่สุดโต่งจริงๆ อาจจะเจอว่า โปรแกรมจะรับไม่ได้เลย ถ้าเราไม่มีหน่วยความจำเหลือ แต่โดยทั่วๆ ไป พื้นที่เก็บข้อมูล เป็นเรื่องรองจากเวลาทำงาน
สุดท้าย การอภิปรายนี้ อยู่บนความคิดที่ว่า เราควรจะใช้โครงสร้างข้อมูลเดียวกัน สำหรับทั้งการวิเคราะห์ข้อความต้นฉบับ และการสร้างข้อความสุ่ม แต่ จริงๆ แล้ว มันเป็นเรื่องที่แยกกัน เราอาจจะใช้โครงสร้างข้อมูลหนึ่ง สำหรับการวิเคราะห์ข้อความต้นฉบับ แล้วแปลงเป็นอีกโครงสร้าง เพื่อการสร้างข้อความสุ่ม ก็ย่อมได้ มันอาจจะได้ผลรวมๆ แล้วดีกว่า ถ้าเวลาที่สั้นลงตอนสร้างข้อความสุ่ม คุ้มกับเวลาที่ใช้ในการแปลงโครงสร้างข้อมูล
เวลาที่เราดีบัก หรือหาจุดผิดพลาดในโปรแกรม และโดยเฉพาะอย่างยิ่ง ถ้าเรากำลังเจอจุดผิดพลาดที่ยาก มีคำแนะนำห้าอย่างที่น่าจะลอง:
โปรแกรมเมอร์มือใหม่มักจะติดอยู่กับเทคนิคหนึ่ง ในห้าเทคนิคจากคำแนะนำข้างต้น และลืมเทคนิคอื่นๆ แต่ละเทคนิคมีจุดอ่อนของตัวเอง
ตัวอย่างเช่น การอ่านโค้ด อาจจะช่วย ถ้าปัญหาเป็นข้อผิดพลาดจากการพิมพ์ผิด (typographical error) แต่มันจะไม่ช่วย ถ้าเป็นปัญหาจากความเข้าใจผิดเชิงแนวคิด ถ้าเราไม่เข้าใจจริงๆ ว่า โปรแกรมทำอะไร เราอาจจะอ่านมันเป็นร้อยๆ ครั้ง แต่ไม่เห็นข้อผิดพลาดเลยก็ได้ เพราะว่า ข้อผิดพลาดมันอยู่ในหัวเราเอง
การลองเปลี่ยนโปรแกรม แล้วทดลองรัน อาจจะช่วย ถ้าเราทำการทดสอบเล็กๆ ง่ายๆ แต่ถ้าเราทดลอง โดยไม่ได้คิด หรือไม่ได้ตรวจสอบโค้ดดูก่อน เราอาจจะกลายเป็น แบบที่เรียกว่า “การเขียนโปรแกรมแบบเดินสุ่ม” (random walk programming) ที่แก้โปรแกรมแบบมั่วๆ ไปเรื่อยๆ จนกว่าโปรแกรมจะทำงานถูก ก็คงไม่ต้องพูดมาก การเขียนโปรแกรมแบบเดินสุ่ม มันจะใช้เวลานานมาก
เราต้องใช้เวลาคิด การดีบัก ก็เหมือนกับวิทยาศาสตร์เชิงการทดลอง อย่างน้อย เราควรจะมีข้อสันนิษฐาน บ้างว่า ปัญหาน่าจะคืออะไร ถ้ามีความเป็นไปได้หลายแบบ ลองคิดถึงการทดสอบของความเป็นไปได้แต่ละแบบ
แต่ แม้เทคนิคการดีบักที่ดีที่สุด ก็จะล้มเหลว ถ้าโปรแกรมมีข้อผิดพลาดมากเกินไป หรือ ถ้าโค้ดที่เรากำลังพยายามแก้ มันใหญ่เกินไป มันซับซ้อนเกินไป บางครั้ง วิธีที่ดีที่สุด คือ ถอย ทำโปรแกรมให้ง่ายๆ พื้นๆ จนมันเริ่มทำงานได้ และเราเข้าใจการทำงานของมันก่อน
โปรแกรมเมอร์มือใหม่ มักจะลังเล ไม่อยากจะถอย เพราะว่า เขารับไม่ได้ ที่จะต้องลบบรรทัดของโค้ดออก (ถึงแม้ มันจะผิดก็ตาม) ถ้ามันจะช่วยให้รู้สึกดีขึ้น อาจจะคัดลอกโปรแกรมไปอีกไฟล์หนึ่งก่อน แล้วค่อยเริ่มลบมันออก หลังจากนั้น ถ้าต้องการ ก็ค่อยสำเนาโค้ดที่เก็บไว้กลับมา โดยค่อยๆ เอากลับมาทีละน้อยๆ
เวลาหาบักที่ยาก ต้องทำทั้ง อ่าน รันและทดสอบ ไตร่ตรอง และบางครั้งก็ถอย ถ้าเทคนิคหนึ่งติด ให้ลองเทคนิคอื่นๆ ที่เหลือ
แบบฝึกหัด 9
“ลำดับที่” (rank) ของคำ คือ ตำแหน่งในลิสต์ของคำต่างๆ ที่เรียงลำดับตามความถี่ นั่นคือ คำที่พบบ่อยที่สุดจะเป็นลำดับที่หนึ่ง คำที่พบบ่อยที่สุดอันดับที่สอง จะเป็นลำดับที่สอง เป็นต้น
กฏของซิปฟ์ (Zipf’s law) อธิบายความสัมพันธ์ระหว่าง ลำดับที่ และความถี่ของคำในภาษาธรรมชาติ (http://en.wikipedia.org/wiki/Zipf's_law) นั่นคือ มันทำนายว่า ความถี่ $f$ ของคำที่มีลำดับที่ $r$ จะเป็น: $$f = c r^{-s}$$ เมื่อ $s$ และ $c$ เป็นพารามิเตอร์ที่ขึ้นกับภาษาและข้อความ ถ้าเราใส่ลอการิทึมเข้าไปทั้งสองฝั่ง เราจะได้: $$\log f = \log c - s \log r$$ ดังนั้น ถ้าเราวาดกราฟของ $\log f$ กับ $\log r$ เราจะได้เส้นตรง ที่มีความชันเป็น $-s$ และจุดตัดแกนเป็น $\log c$
เขียนโปรแกรมที่อ่านข้อความจากไฟล์ นับความถี่คำ พิมพ์ออกมา บรรทัดละหนึ่งคำ โดยเรียงลำดับตามความถี่ จากมากไปน้อย พร้อมค่า $\log f$ และ $\log r$ ใช้โปรแกรมวาดกราฟ ตามที่ชอบ เพื่อวาดกราฟของผลนี้ออกมา และตรวจสอบว่ามันเป็นเส้นตรงหรือไม่ จากผลลัพธ์ที่ได้ เราจะประมาณค่าของ $s$ ได้หรือไม่?
เฉลย: http://thinkpython2.com/code/zipf.py เพื่อจะรันโปรแกรมเฉลย เราต้องการโมดูลวาดกราฟ matplotlib ถ้าคุณติดตั้งไพธอนด้วย Anaconda คุณน่าจะมี matplotlib อยู่แล้ว ถ้าไม่ใช่อย่างนั้น คุณอาจจะต้องติดตั้งมันก่อน
https://greenteapress.com/thinkpython2/html/thinkpython2014.html