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

บทที่ 10 Dictionaries

Types ที่เกิดจากการรวมกัน คุณได้เรียนมาแล้วเกี่ยวกับ strings lists และ tuples ถ้าคุณพยายามใช้ types อื่นๆ ตาม index คุณจะได้ error

Dictionaries เหมือนกับการยอมรับการรวมกันของหลายๆ types ซึ่งมันสามารถใช้โดยไม่เปลี่ยนรูปแบบ types ตาม index ตัวอย่างเช่น พวกเราจะสร้างdictionaryที่แปลจากภาษาอังกฤษเป็นภาษาสเปน สำหรับdictionaryนี้ index คือ strings

ทางหนึ่งที่จะสร้าง dictionary คือ เริ่มจากdictionaryที่ว่างเปล่า และเพิ่มelementเข้าไป dictionaryที่ว่างเปล่าถูกระบุโดยเครื่องหมาย {}

>>> eng2sp = {}

>>> eng2sp['one'] = 'uno'

>>> eng2sp['two'] = 'dos'

สิ่งแรกคือ ให้เราตั้งชื่อของ dictionary ว่า eng2sp สิ่งที่ทำต่อมาคือ เพิ่มelementต่างๆ เข้าไปในdictionary พวกเราสามารถแสดงค่าของdictionaryออกมาตามปกติ

>>> print eng2sp

{'one': 'uno', 'two': 'dos'}

Elementของdictionaryจะปรากฏโดยเรียงต่อกันและมีคอมม่าป็นตัวแยกจากกัน แต่ละทางเข้าจะบรรจุ index และ ค่าที่ถูกแยกกันโดยโคลอน ในdictionary index ถูกเรียกว่า keys ดังนั้น element จึงถูกเรียกว่า key-value pairs

อีกทางที่จะสร้างdictionary คือ ใช้ key-value pairs ซึ่งรูปแบบเหมือนกับผลลัพธ์ที่ออกมาก่อนหน้านี้

>>> eng2sp = {'one': 'uno', 'two': 'dos', 'three': 'tres'}

ถ้า print ค่าของ eng2sp อีกครั้ง พวกเราจะประหลาดใจ

>>> print eng2sp

{'one': 'uno', 'three': 'tres', 'two': 'dos'}

key-value pairs ไม่เป็นไปตามลำดับ แต่โชคดีที่เราไม่สนใจในเรื่องลำดับ ตั้งแต่elementของdictionaryไม่เคยบ่งชี้ว่ามี index ที่สมบูรณ์ แทนที่โดยพวกเราใช้ keys ในการค้นหาค่าที่เหมือนกัน

>>> print eng2sp['two']

'dos'

key ‘two’ ให้ค่า ‘dos’ ถึงแม้ว่ามันจะปรากฏเป็นตัวที่สามของ key-value pair

10.1 Dictioinary operations

del statement คือ การลบ key-value pair ออกจากdictionary ตัวย่างเช่น dictionaryจะบรรจุ ชื่อผลไม้ไว้มากมาย และเก็บค่าจำนวนของผลไม้แต่ละชนิดในคลัง

>>> inventory = {'apples': 430, 'bananas': 312, 'oranges': 525,

'pears': 217}

>>> print inventory

{'oranges': 525, 'apples': 430, 'pears': 217, 'bananas': 312}

ถ้ามีคนซื้อลูกแพร์ทั้งหมด พวกเราสามารถที่จะลบข้อมูลที่ใส่ไปออกจาก dictionary

>>> del inventory['pears']

>>> print inventory

{'oranges': 525, 'apples': 430, 'bananas': 312}

หรือถ้าพวกเราคาดว่าลูกแพร์จะมาในไม่ช้า เราอาจจะเปลี่ยนค่าให้มีความเชื่อมโยงกันดังนี้

>>> inventory['pears'] = 0

>>> print inventory

{'oranges': 525, 'apples': 430, 'pears': 0, 'bananas': 312}

การทำงานของ len function บน dictionaries มันจะให้ค่าจำนวนของ key-value pairs ออกมา

>>> len(inventory)

4

10.2 Dictionary methods

method จะเหมือนกับฟังก์ชันๆหนึ่ง มันจะรับค่าพารามิเตอร์เข้าไปและคืนค่ากลับมา แต่ syntax แตกต่างกัน สำหรับตัวอย่าง keys method รับค่า dictionary เข้าไปและคืนค่า keys ออกมาตามที่ปรากฏ แต่แทนที่ด้วยฟังก์ชัน syntax keys(eng2sp) พวกเราใช้ method syntax end2sp.keys()

>>> eng2sp.keys()

['one', 'three', 'two']

เครื่องหมายจุดของรูปแบบนี้ระบุถึงชื่อของฟังก์ชัน คือ keys และชื่อของ object ที่ประยุกต์ในฟังก์ชัน คือ eng2sp วงเล็บแสดงว่า method นี้ไม่ได้ใส่ค่าพารามิเตอร์

การเรียก method จะถูกเรียกว่า invocation ในลักษณะนี้เราจะพูดถึงการเริ่มต้นของ keys บน object eng2sp

ค่าของ method เหมือนกัน มันจะคืนค่าโดย list ค่าในdictionary ออกมา

>>> eng2sp.values()

['uno', 'tres', 'dos']

item method จะคืนค่าทั้งคู่ ในรูปแบบของ list แบบ tuples

>>> eng2sp.items()

[('one','uno'), ('three', 'tres'), ('two', 'dos')]

วงเล็บ [ ] แสดงว่านี้คือ list ส่วนวงเล็บ ( ) แสดงถึงelementของ list ซึ่งคือ tuples

ถ้า method มี argument มันใช้เหมือนกับ syntax เช่นเดียวกับการเรียกฟังก์ชัน ตัวอย่างเช่น method has_key ใส่ key และจะคืนค่าความจริงกลับมา ถ้า key ปรากฏใน dictionary

>>> eng2sp.has_key('one')

True

>>> eng2sp.has_key('deux')

False

ถ้าคุณลองเรียก method โดยไม่ได้ระบุถึง object คุณจะได้ error ในcase นี้ ข้อความ error ไม่มีข้อความช่วยเหลือให้มาก

>>> has_key('one')

NameError: has_key

10.3 Aliasing and copying

เพราะว่า dictionary มีการเปลี่ยนแปลงได้ เมื่อตัวแปร 2 ตัว อ้างอิงถึง object ที่เหมือนกัน การเปลี่ยนอันหนึ่งจะมีผลกับอีกอันหนึ่ง

ถ้าคุณต้องการแก้ไข dictionary และเก็บรักษาต้นฉบับของการ copy ใช้ copy method ตัวอย่างเช่น oppsites คือ dictionary ที่เก็บคำศัพท์ที่เป็นคำตรงข้ามกันไว้เป็นคู่

>>> opposites = {'up': 'down', 'right': 'wrong', 'true': 'false'}

>>> alias = opposites

>>> copy = opposites.copy()

alias และ opposites จะอ้างถึง object ที่เหมือนกัน การ copy dictionary ที่เหมือนกันขึ้นมาใหม่อีกอันหนึ่ง ถ้าพวกเราแก้ไข alias , opposites จะเปลี่ยนแปลงไปด้วย

>>> alias['right'] = 'left'

>>> opposites['right']

'left'

ถ้าพวกเราแก้ไข copy , opposites จะไม่เปลี่ยนแปลง

>>> copy['right'] = 'privilege'

>>> opposites['right']

'left'

10.4 Sparse matrices

ในหัวข้อ 8.14 พวกเราใช้ list แสดงตัวอย่างเกี่ยวกับ matrix เป็นทางเลือกที่ดีมากถ้า matrix ส่วนใหญ่ไม่มีค่า 0 แต่เมื่อพิจารณาแล้วมีน้อยมาก ดูได้จาก matrix นี้

list นี้แสดงถึงว่ามี 0 อยู่ใน matrix นี่จำนวนมาก

matrix = [ [0,0,0,1,0],

[0,0,0,0,0],

[0,2,0,0,0],

[0,0,0,0,0],

[0,0,0,3,0] ]

ทางเลือกคือใช้ dictionary สำหรับ keys พวกเราสามารถใช้ tuples ซึ่งใส่ค่าตัวเลขในแถว และ คอลัมภ์ นี้คือ dictionary ที่แสดงถึงความเหมือนกันกับ matrix

matrix = {(0,3): 1, (2, 1): 2, (4, 3): 3}

พวกเราต้องการเพียง 3 key – value pairs แต่ละอันelementของ matrix ต้องไม่ใช่ 0 ทั้งหมด แต่ละ key คือ 1 tuple และแต่ละค่าเป็น integer

การเข้าไปยังelementของ matrix เราสามารถใช้เครื่องหมาย [ ]

matrix[0,3]

1

สังเกตว่า syntax ของ dictionary มีความต่างกับ syntax ของ nested list แทนที่ด้วย 2 integer index พวกเราใช้ 1 index ซึ่งคือ tuple ของ integers

มีอยู่ปัญหาหนึ่ง ถ้าเราระบุ element ว่าเป็น 0 พวกเราจะได้ error เพรามะว่าไม่มีค่านี้ที่ตรงกับ key ใน dictionary

>>> matrix[1,3]

KeyError: (1, 3)

Get method คือวิธีการแก้ปัญหานี้

>>> matrix.get((0,3), 0)

1

argument คือ key argument ที่สอง คือ ค่าที่ควรจะได้ออกมาถ้า key ไม่อยู่ใน dictionary

>>> matrix.get((1,3), 0)

0

10.5 Hints

ถ้าคุณได้เล่นเกี่ยวกับฟังก์ชัน fibonacci จากหัวข้อ 5.7 คุณอาจจะสังเกตว่า เป็น argument ที่ใหญ่กว่าที่คุณได้เตรียมไว้ เป็นฟังก์ชันที่ยาวกว่าเวลานำไป run นอกจากนี้ run time ยังเพิ่มขึ้นอย่างรวดเร็ว หนึ่งในเครื่องของพวกเรา fibonacci(20) จะเสร็จอย่างรวดเร็ว fibonacci(30) จะเป็นอันดับสอง และ fibonacci(40) จะเสร็จอย่างอยากลำบากตลอด

เรียกกราฟที่แสดงว่าเป็นกลุ่มของฟังก์ชันที่อยู่เป็นเฟรม โดยจะมีเส้นเชื่อมต่อแต่ละเฟรมเข้าด้วยกันเป็นฟังก์ชัน ด้านบนสุดของกราฟ คือ fibonacci มี n = 4 จะมาจาก fibonacci มี n = 3 และ n = 2 ในทางย้อนกลับ fibonacci มี n = 3 มาจาก fibonacci มี n = 2 และ n = 1

การนับจำนวนของ fibonacci(0) และ fibonacci(1) ที่ถูกเรียก นี้คือวิธีการแก้ปัญหาที่ไม่มีประสิทธิภาพ และทำให้ argument มีขนาดที่ใหญ่กว่า

previous = {0:1, 1:1}

def fibonacci(n):

if previous.has_key(n):

return previous[n]

else:

newValue = fibonacci(n-1) + fibonacci(n-2)

previous[n] = newValue

return newValue

ชื่อของ dictionary ก่อนหน้านี้ถูกเก็บไว้ที่ track ของตัวเลข fibonacci โดยเราจะเริ่มเพียง 2 คู่ คือ 0 ไปยัง 1 และ 1 ไปยัง 1

เมื่อ fibonacci ถูกเรียก มันจะตรวจสอบ dictionary เพื่อค้นหาถ้ามันเก็บค่าผลลัพธ์ไว้ ถ้ามันอยู่ที่นี่ ฟังก์ชันสามารถแสดงค่าออกมาได้ทันทีโดยไม่ต้องเรียก recursive แต่ถ้าไม่ มันจะคำนวณค่าใหม่ออกมา ค่าใหม่จะถูกเพิ่มเข้าไปใน dictionary ก่อนฟังก์ชันจะแสดงค่า

การใช้ fibonacci เวอร์ชันนี้ เครื่องพวกเราสามารถคำนวณ fibonacci(40) ภายในพริบตา แต่เมื่อเราลองคำนวณ fibonacci(50) พวกเราจะเห็นดังนี้

>>> fibonacci(50)

20365011074L

L ด้านหลังผลลัพธ์แสดงให้รู้ว่าคำตอบมีขนาดที่ใหญ่เกินไปสำหรับ integer ใน python

Python จะเปลี่ยนผลลัพธ์ที่ได้เป็น long integer โดยอัตโนมัติ

10.6 Long integers

python จะเรียก long มาใช้เพื่อจัดการกับขนาดของ integer มี 2 ทาง คือ สร้าง long value โดยเขียน integer ที่มี L อยู่ด้านหลัง

>>> type(1L)

<type 'long'>

อีกอันคือใช้ long function เพื่อเปลี่ยนค่า long long สามารถยอมรับชนิดที่เป็นตัวเลข และตัวเลขที่เป็น strings

>>> long(1)

1L

>>> long(3.9)

3L

>>> long('57')

57L

การคำนวณทางคณิตศาสตร์จะทำงานบน longs โดยทั่วไปการทำงานของ integer กับ long integer ทำงานด้วยกัน แต่เวลาการคำนวณและค่าที่ออกมามีขนาดที่ใหญ่เกินไป python จะตรวจสอบและแสดงผลลัพธ์ออกมาเป็น long integer ดังตัวอย่าง

>>> 1000 * 1000

1000000

>>> 100000 * 100000

10000000000L

ใน case แรก ผลลัพธ์จะเป็น int ส่วนใน case ที่สองผลลัพธ์เป็น long

10.7 Counting letters

ในบทที่ 7 พวกเราเขียนฟังก์ชันการนับจำนวนตัวเลขของตัวอักษรใน string เวอร์ชันทั่วไปของปัญหานี้คือ รูปแบบของกราฟซึ่งแสดงความถี่ของตัวอักษรใน string คือนานเท่าไหร่ที่แต่ละตัวอักษรจะปรากฏ

เช่นกราฟอาจจะใช้ประโยชน์สำหรับการบีบอัดไฟล์ที่เป็นตัวอักษร เพราะตัวอักษรจะปรากฏในความถี่ที่ต่างกัน พวกเราสามารถบีบอัดไฟล์ โดยการใช้โค้ดสั้นๆ สำหรับ ตัวอักษรที่ใช้บ่อยๆ และ โค้ดที่ยาวสำหรับตัวอักษรที่ไม่ค่อยปรากฏบ่อย

>>> letterCounts = {}

>>> for letter in "Mississippi":

... letterCounts[letter] = letterCounts.get (letter, 0) + 1

... >>> letterCounts

{'M': 1, 's': 4, 'p': 2, 'i': 4}

พวกเราจะเริ่มจาก dictionary ที่ว่างเปล่า สำหรับตัวอักษรแต่ละตัวใน string พวกเราหาการนับตอนปัจจุบันและการเพิ่มขึ้นของมัน ในที่สุด dictionary จะบรรจุคู่ของตัวอักษรและความบ่อยที่ปรากฏออกมา

มันอาจจะน่าสนใจกว่าถ้าให้แสดงกราฟออกมาโดยสั่งให้เรียงตามลำดับตัวอักษร พวกเรสามารถทำโดยใช้ item และ sort methods

>>> letterItems = letterCounts.items()

>>> letterItems.sort()

>>> print letterItems

[('M', 1), ('i', 4), ('p', 2), ('s', 4)]

คุณจะเห็น item method ก่อน แต่ sort จะเป็น method แรกที่คุณได้เจอกับการประยุกต์ของ list มี list methods อื่นๆ มากมาย รวมถึง append, extend และ reverse

10.8 Glossary

dictionary: A collection of key-value pairs that maps from keys to values. The keys can be any immutable type, and the values can be any type.

key: A value that is used to look up an entry in a dictionary.

key-value pair: One of the items in a dictionary.

method: A kind of function that is called with a different syntax and invoked “on” an object.

invoke: To call a method.

hint: Temporary storage of a precomputed value to avoid redundant computation.

overfow: A numerical result that is too large to be represented in a numerical format.