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

บทที่ 9 Tuples

9.1 Mutability and tuples

ในตอนนี้ คุณได้เห็นสอง compound type: strings ซึ่งสร้างขึ้นจาก characters; และ lists ซึ่งสร้างขึ้นจาก elements ชนิดไหนก็ได้ หนึ่งในข้อแตกต่างที่เด่นชัดคือ elements ของ list สามารถเปลี่ยนแปลงแก้ไขได้, แต่ characters ใน string ไม่สามารถทำได้ ในอีกคำหนึ่งคือ strings คือ immutable(รูปแบบที่ซึ่งไม่สามารถแก้ไข elements ได้)และ lists คือ mutable(รูปแบบที่ซึ่งสามารถแก้ไข elements ได้)

มีรูปแบบอีกรูปแบบหนึ่งใน Python เรียกว่า tuple ซึ่งคล้ายกับ list เว้นแต่มันเป็น immutable การสร้างประโยค คือ คอมม่า-แยก list ของค่า:

>>> tuple = ‘a’, ‘b’, ‘c’, ‘d’, ‘e’

แม้ว่ามันจะไม่จำเป็น มันเป็นธรรมเนียมปฏิบัติที่จะต้องปิดล้อม tuples ไว้ในวงเล็บ:

>>> tuple = (‘a’, ‘b’, ‘c’, ‘d’, ‘e’)

การสร้าง tuple ด้วย element เพียงตัวเดียว เราต้องใส่คอมม่าตามด้วย:

>>> t1 = (‘a’ ,)

>>> type(t1)

<type ‘tuple’>

ถ้าไม่มีคอมม่า Python จะจัดการ (‘a’) เป็น string ในวงเล็บ:

>>> t2 = (‘a’ ,)

>>> type(t2)

<type ‘str’>

Operations บน tuples ใช้เหมือนกันกับของ lists Index operator เลือกขอบเขตของ elements

>>> tuple = (‘a’, ‘b’, ‘c’, ‘d’, ‘e’)

>>> tuple[0]

‘a’

และ slice operator เลือกขอบเขตของ elements

>>> tuple [1:3]

(‘b’, ‘c’)

แต่ถ้าเราพยายามแก้ไข elements ตัวใดตัวหนึ่งของ tuple เราจะได้รับข้อความ error:

>>> tuple[0] = ‘A’

TypeError: object doesn’t support item assignment

แน่นอน ถึงแม่เราไม่สามารถที่จะแก้ไข elements ของ tuple ได้ เราสามารถแทนที่มันด้วยอีก tuple หนึ่ง:

>>> tuple = (‘A’,) + tuple[1:]

>>> tuple

(‘A’, ‘b’, ‘c’, ‘d’, ‘e’)

9.2 Tuple assignment

ในช่วงหนึ่ง การสลับค่าของสองตัวแปรจะเป็นประโยชน์ ด้วย assignment statements เราต้องใช้ตัวแปรชั่วคราว. ตัวอย่าง การย้ายระหว่าง a และ b:

>>> temp = a

>>> a = b

>>> b = temp

ถ้าเราต้องกระทำแบบนี้บ่อยๆ มันกลายมาเป็นเรื่องที่ยุ่งยาก Python ได้จัดรูปแบบของ tuple assignments(การกำหนดค่าให้กับ tuple) เพื่อแก้ปัญหาเหล่านี้อย่างเรียบร้อย:

>>> a, b = b, a

ฝั่งซ้ายคือ tuple ของตัวแปร; ฝั่งขวาคือ tuple ของค่า แต่ละค่าได้กำหนดให้กับตัวแปรนั้นตามลำดับ expressions ทั้งหมดทางด้านขวาถูกประเมินก่อนที่จะทำการกำหนดค่าให้กับตัวแปรใดๆ ลักษณะดังนี้ทำให้การกำหนดค่าให้กับ tuple ค่อนข้างมีประโยชน์หลายอย่าง

โดยปรกติ จำนวนของตัวแปรทางด้านซ้ายและจำนวนของค่าทางด้านขวาจะต้องมีชื่อเดียวกัน:

>>> a, b, c, d = 1, 2, 3

ValueError: unpack tuple of wrong size

9.3 Tuples as return values

Functions สามารถ return tuple เช่นเดียวกับการ return ค่า ตัวอย่าง เราสามารถเขียน function ที่ทำการสลับค่า parameters:

def swap(x, y):

return y, x

หลังจากนั้นเราสามารถกำหนดการ return ค่า ใหกับ tuple ด้วยสองตัวแปร:

a, b = swap(a, b)

ในกรณีนี้ ไม่มีข้อดีในการทำ swap function ที่จริง มันไม่ปลอดภัยที่จะทำการ encapsulate swap ซึ่งการทำดังต่อไปนี้จะทำให้เกิดข้อผิดพลาด:

def swap(x, y): # incorrect version

x, y = y, x

ถ้าเราเรียก function ดังเช่นนี้:

swap(a, b)

ดังนั้น a และ x เป็น alias สำหรับค่าเดียวกัน การเปลี่ยน x ภายใน swap ทำให้ x อ้างอิงถึงค่าที่ต่างกัน แต่มันไม่ส่งผลกระทบต่อ a ใน __main__ เหมือนกันกับ, การเปลี่ยน y จะไม่ส่งผลกระทบต่อ b

function นี้จะรันโดยไม่เกิดข้อความผิดพลาด แต่มันไม่สามารถทำงานตามที่เราต้องการได้ นี่คือตัวอย่าของ semantic error

9.4 Random numbers

โปรแกรมคอมพิวเตอร์ส่วนใหญ่กระทำอย่างเดียวกันทุกครั้งที่มันดำเนินการ ดังนั้นมันกล่าวได้ว่าเป็น deterministic(โปรแกรมซึ่งทำอย่างเดียวกันในแต่ละครั้งที่มันถูกเรียก) ตามปรกติเป็นสิ่งที่ดี ตั้งแต่ที่เราคาดหวังการคำนวณเดียวกันจะให้ผลที่เหมือนกัน สำหรับบาง applications อย่างไรก็ตามแม้ว่า เราต้องการคอมพิวเตอร์ไม่ให้ทำนายได้ เกมส์คือตัวอย่างที่ชัดเจน แต่มีมากกว่านั้น การทำโปรแกรมโดยไม่เป็น nondeterministic กลายมาเป็นเรื่องที่ยาก แต่มีหลายทางที่ทำให้มันดูเหมือนเป็น nondeterministic หนึ่งในนั้นคือการสร้าง การสุ่มตัวเลขและใช้มันในการกำหนดผลลัพธ์ของโปรแกรม Python ได้เตรียม function ภายในไว้ที่สร้างตัวเลข pseudorandom(ลำดับของตัวเลขที่ปรากฏขึ้นแบบสุ่มแต่ที่จริงแล้วเป็นผลลัพธ์ของการตำนวณแบบ deterministic) ซึ่งไม่ได้สุ่มอย่างแท้จริงในความหมายทางคณิตศาสตร์ แต่สำหรับวัตถุประสงค์ของเรามันทำได้

Random module ประกอบด้วย function ที่เรียกว่า random ที่ return เลขทศนิยมระหว่าง 0.0 และ 1.0 แต่ละครั้งที่คุณเรียก random, คุณจะได้ตัวเลขถัดไปในชนิดข้อมูลที่เป็น long. เพื่อจะดูตัวอย่าง, run loop นี้:

import random

for i in range(10):

x = random.random()

print x

การสร้างจำนวนสุ่มระหว่าง 0.0 และระดับความสูงเช่น high คูณ x ด้วย high

9.5 List of random numbers

ขั้นแรกคือการสร้าง list ของการสุ่มจำนวน randomList รับเอา integer parameter และ return list ของ การสุ่มจำนวน ด้วยกำหนดความยาว มันเริ่มต้นด้วย list ของศูนย์ n ตัว แต่ละครั้งที่เข้าใน loop มันทำการแทนที่ หนึ่งใน elements ด้วย จำนวนสุ่ม return ค่าคือการอ้างอิง list ที่สมบูรณ์;

def randomList(n):

s = [0] * n

for i in range(n):

s[i] = random.random()

return s

เราจะทดสอบ function นี้ list ที่มีแปด elements. สำหรับจุดประสงค์ในการ debug เป็นความคิดที่ดีที่เริ่มต้นด้วยจำนวนน้อยๆ.

>>> randomList(8)

0.15156642489

0.498048560109

0.810894847068

0.360371157682

0.275119183077

0.328578797631

0.759199803101

0.800367163582

จำนวนที่สร้างขึ้นด้วย random คิดว่ามันถูกกระจายอย่างเป็นรูปแบบเดียวกัน ซึ่งหมายถึงทุกๆค่าดูเหมือนว่าเท่ากันหมด

ถ้าเราแบ่งขอบเขตของค่าที่เป็นไปได้ใน “buckets” ที่มีขนาดเท่ากันและนับจำนวนของครั้งในการสุ่มค่าในแต่ละ bucket เราจะได้จำนวนเดียวกันโดยคร่าวๆในแต่ละ bucket

เราสามารถทดสอบทฤษฎีนี้โดยการเขียนโปรแกรมเพื่อแบ่งขอบเขตใน buckets และนับจำนวนของค่าในแต่ละ bucket 9.6 Counting การเข้าใกล้ปัญหาที่ดีเช่นนี้นั้นคือการแยกปัญหาเป็นหัวข้อย่อยและมองดูปัญาเหล่านี้ที่เหมาะสม กับรูปแบบการคำนวณที่คุณได้เห็นมาก่อนหน้านี้. ในกรณีนี้ เราต้อง traverse list ของจำนวนและนับจำนวนของครั้งที่ค่าตกอยู่ในขอบเขตที่ได้ให้ไว้ ฟังดูคล้ายกัน ในหมวดที่ 7.8 เราได้เขียนโปรแกรมที่ได้ traverse stringและได้นับจำนวนของครั้งที่ตัวอักษรที่ได้กำหนดไว้ปรากฏ

ดังนั้น เราสามารถดำเนินการโดยทำการ copy โปรแกรมตัวเก่าและทำการปรับมันสำหรับปัญหาในปัจจุบัน โปรแกรมดั้งเดิมคือ:

count = 0

for char in fruit:

if char == ‘a’:

count = count + 1

print count

ขั้นแรกคือแทน fruit ด้วย list และ char ด้วย num. มันไม่ทำให้โปรแกรมเปลี่ยน; มันแค่ทำให้อ่านง่ายมากขึ้น

ขั้นที่สองคือเปลี่ยนการทดสอบ เราไม่ได้สนใจมรการหาตัวอักษร เราต้องการดูว่าถ้า num อยู่ระหว่างค่า low และ high ที่ได้ให้ไว้

count = 0

for num in list

if low < num < high:

count = count + 1

print count

ขั้นตอนสุดท้ายคือ encapsulate code นี้ใน function ที่เรียกว่า inBucket ค่า parameter คือ list และค่า low และ high

def inBucket(list, low, high):

count = 0

for num in list:

if low < num < high:

count = count + 1

return count

ด้วยการ copy และการแก้ไขโปรแกรมที่มีอยู่ เราสามารถเขียน function นี้เร็วขึ้นและช่วยรักษาเวลาในการ debug. แผนพัฒนานี้เรียกว่า pattern matching ถ้าคุณพบว่าตัวคุณกำลังทำงานอยู่บนปัญหาคุณต้องแก้ไขมันก่อน นำวิธีแก้ปัญหามาใช้ใหม่

9.7 Many buckets

ขณะที่จำนวนของ bucket เพิ่มขึ้น, inBucket ก็จะจัดการได้ยาก. ด้วยสอง bucket, มันไม่เลวร้าย:

low = inBucket(a, 0.0, 0.5)

high = inBucket(a, 0.5, 1)

หากเป็นสี่ bucket มันก็จะเริ่มยุ่งยากขึ้น.

bucket1 = inBucket(a, 0.0, 0.25)

bucket2 = inBucket(a, 0.25, 0.5)

bucket3 = inBucket(a, 0.5, 0.75)

bucket4 = inBucket(a, 0.75, 1.0)

มีสองปัญหา ปัญหาแรกคือ ที่เราต้องสร้างชื่อตัวแปรขึ้นมาใหม่สำหรับแต่ละผลลัพธ์. อีกปัญหาคือ เราต้องคำนวณขอบเขตสำหรับแต่ละ bucket เราจะแก้ไขปัญหาที่สองเป็นอย่างแรก. ถ้าจำนวนของ buckets คือ numBuckets แล้วความกว้างของแต่ละ bucket คือ 1.0 / numBuckets เราจะใช้ loop เพื่อคำนวณของเขตของแต่ละ bucket. ตัวแปร loop, i นับจาก 0 ถึง numBuckets-1:

bucketWidth = 1.0 / numBuckets

for i in range(numBuckets):

low = i * bucketWidth

high = low + bucketWidth

print low, “to”, high

การคำนวณต่ำสุดของแถวของแต่ละ bucket เราคูณตัวแปร loop ด้วยความกว้างของ bucket สูงสุดก็แค่เป็น bucketWidth.

ด้วย numBuckets = 8 ผลลัพธ์คือ:

0 to 0.125

0.125 to 0.25

0.25 to 0.375

0.375 to 0.50

0.5 to 0.625

0.625 to 0.75

0.75 to 0.875

0.875 to 1.0

คุณสามารถยืนยันแต่ละ bucket กว้างเท่ากัน ซึ่งมันจะไม่คาบเกี่ยวกันและครอบคลุมขอบเขตทั้งหมด จาก 0.0 ถึง 1.0

ตอนนี้กลับไปที่ปัญหาแรก เราต้องการวิธีที่เก็บแปด integers โดยใช้ตัวแปร loop บ่งชี้ต่อหนึ่งครั้ง แล้วคุณควรจะคิด “List!”

เ ราต้องสร้าง bucket list นอก loop เพราะว่าเราต้องการกระทำเพียงครั้งเดียว ภายใน loop เราจะเรียก inBucket หลายๆครั้งและอัพเดท i-eth element ของ list:

numBuckets = 8

buckets = [0] * numBuckets

bucketWidth = 1.0 / numBuckets

for i in range(numBuckets):

low = i * bucketWidth

high = low + bucketWidth

buckets[i] = inBucket(list, low, high)

print buckets

กับ list ของ 1000 ค่า, code นี้สร้าง bucket list นี้:

[138, 124, 128, 118, 130, 117, 114, 131]

จำนวนเหล่านี้ใกล้ 125 พอสมควร ซึ่งตามที่เราได้คาดไว้ ในที่สุด มันใกล้กันพอสมควรซึ่งเราสามารถเชื่อได้ว่าการสุ่มจำนวนทำงานได้ผล

9.8 A single-pass solution

แม้ว่าโปรแกรมนี้ทำงานได้ มันยังไม่มีประสิทธิภาพอย่างที่มันควรเป็น ทุกครั้งที่มันเรียก inBucket มัน traverses list ทั้งหมด เมื่อจำนวนของ buckets เพิ่มขึ้น ทำให้เกิด traversals จำนวนมาก

มันจะดีกว่าที่จะทำเพียงครั้งเดียวในการส่งเข้าไปใน list และ คำนวณสำหรับแต่ละค่า index ของ bucket ในอันซึ่งลดลง หลังจากนั้นเราสามารถเพิ่มตัวนับที่จัดสรรไว้

ในหมวดที่ผ่านมาเราเอา index, i และคูณมันด้วย bucketWidth เพื่อหาขอบเขตที่ต่ำของ bucket ที่ให้ไว้. ตอนนี้เราต้องการนำค่าในขอบเขต 0.0 ถึง 1.0 และหา index ของ bucket ที่มันลดลง

เมื่อปัญหานี้เป็นปัญหาที่ตรงกันข้ามกับปัญหาที่แล้ว เราอาจคิดว่าเราควรหารด้วย bucketWidth แทนที่จะทำการคูณ ความคิดนั้นถูกต้อง

เมื่อ bucketWidth = 1.0 / numBuckets, การหารด้วย bucketWidth เท่ากันกับการคูณด้วย numBuckets ถ้าเราคูณจำนวนใน 0.0 ถึง 1.0 ด้วย numBuckets เราได้จำนวนในขอบเขต 0.0 ถึง numBuckets ถ้าเราหมุนเวียนจำนวนนั้นไปยัง integer ตัวต่ำกว่าที่ถัดไป เราจะได้สิ่งที่เรากังมองหาอย่างถูกต้อง-bucket index:

numBucket = 8

buckets = [0] * numBuckets

for i in list:

index = int(i * numbuckets)

buckets[index] = buckets[index] + 1

เราเคยใช้ int finction เพื่อเปลี่ยนตัวเลข floating-point เป็น integer

มันเป็นไปได้รึปล่าวสำหรับการคำนวณนี้ที่สร้าง index ที่ซึ่งอยู่นอกขอบเขต(จำนวนลบ หรือ มากกว่า len(buckets)-1)?

list ที่เหมือน bucket ที่ประกอบด้วยการนับจำนวนของค่าในแต่ละขอบเขต เรียกว่า histogram

9.9 Glossary

immutable type: A type in which the elements cannot be modified. Assignments to elements or slices of immutable types cause an error.

mutable type: A data type in which the elements can be modified. All mutable types are compound types. Lists and dictionaries are mutable data types; strings and tuples are not.

tuple: A sequence type that is similar to a list except that it is immutable. Tuples can be used wherever an immutable type is required, such as a key in a dictionary.

tuple assignment: An assignment to all of the elements in a tuple using a single assignment statement. Tuple assignment occurs in parallel rather than in sequence, making it useful for swapping values.

deterministic: A program that does the same thing each time it is called.

pseudorandom: A sequence of numbers that appear to be random but that are actually the result of a deterministic computation.

histogram: A list of integers in which each element counts the number of times something happens.

pattern matching: A program development plan that involves identifying a familiar computational pattern and copying the solution to a similar problem.