python:analysis_algorithms

B. การวิเคราะห์อัลกอริทึม

ภาคผนวกนี้เป็นข้อความที่ตัดตอนมาจาก Think Complexity โดย Allen B. Downey ซึ่งจัดพิมพ์โดย O’Reilly Media (2012) ด้วย เมื่อคุณอ่านหนังสือเล่มนี้จบแล้ว คุณอาจต้องการไปยังหนังสือเล่มนั้นต่อไป

การวิเคราะห์อัลกอริธึมเป็นสาขาหนึ่งของวิทยาการคอมพิวเตอร์ที่ศึกษาประสิทธิภาพของอัลกอริธึม โดยเฉพาะเวลาในการทำงานและพื้นที่ที่ต้องการ ดูเพิ่มที่ http://en.wikipedia.org/wiki/Analysis_of_algorithms

เป้าหมายในทางปฏิบัติของการวิเคราะห์อัลกอริธึมคือการทำนายประสิทธิภาพของอัลกอริธึมต่างๆ เพื่อเป็นแนวทางในการตัดสินใจออกแบบ

ระหว่างการรณรงค์หาเสียงเลือกตั้งประธานาธิบดีสหรัฐฯ ปี 2008 ผู้สมัครรับเลือกตั้ง บารัค โอบามา ถูกขอให้ทำการวิเคราะห์อย่างกะทันหันเมื่อเขาไปที่ Google หัวหน้าผู้บริหาร Eric Schmidt พูดติดตลกถามเขาถึง “วิธีที่มีประสิทธิภาพที่สุดในการจัดเรียงจำนวนเต็ม 32 บิตจำนวน 1 ล้านจำนวน” เห็นได้ชัดว่าโอบามาถูกหลอกเพราะเขาตอบอย่างรวดเร็วว่า “ผมคิดว่าการเรียงแบบบับเบิ้ลจะเป็นวิธีที่ผิด ไป” ดู http://www.youtube.com/watch?v=k4RRi_ntQc8

นี่เป็นความจริง การเรียงลำดับแบบบับเบิ้ลตามแนวคิดนั้นเรียบง่าย แต่ช้าสำหรับชุดข้อมูลขนาดใหญ่ คำตอบที่ Schmidt กำลังมองหาคือ “radix sort” (http://en.wikipedia.org/wiki/Radix_sort) ¹⁾

เป้าหมายของการวิเคราะห์อัลกอริธึมคือการเปรียบเทียบอย่างมีความหมายระหว่างอัลกอริธึม แต่มีปัญหาบางประการ

ประสิทธิภาพสัมพัทธ์ของอัลกอริธึมอาจขึ้นอยู่กับคุณลักษณะของฮาร์ดแวร์ ดังนั้นอัลกอริธึมหนึ่งอาจเร็วกว่าในเครื่อง A แต่อีกอันเร็วกว่าบนเครื่อง B วิธีแก้ปัญหาโดยทั่วไปคือการระบุ โมเดลของเครื่องและวิเคราะห์จำนวนขั้นตอน หรือ การดำเนินการ ที่อัลกอริธึมต้องการภายใต้โมเดลที่กำหนด
ประสิทธิภาพสัมพัทธ์อาจขึ้นอยู่กับรายละเอียดของชุดข้อมูล ตัวอย่างเช่น อัลกอริธึมการเรียงลำดับบางอย่างจะทำงานเร็วขึ้นหากข้อมูลถูกจัดเรียงบางส่วนแล้ว อัลกอริทึมอื่นทำงานช้าลงในกรณีนี้ วิธีทั่วไปในการหลีกเลี่ยงปัญหานี้คือการวิเคราะห์สถานการณ์ กรณีที่เลวร้ายที่สุด (worst case) บางครั้งการวิเคราะห์ประสิทธิภาพของกรณีโดยเฉลี่ยก็มีประโยชน์แต่มักจะยากกว่า และอาจไม่ชัดเจนว่าควรจะเฉลี่ยบนชุดข้อมูลใด
ประสิทธิภาพสัมพัทธ์ยังขึ้นอยู่กับขนาดของปัญหาด้วย อัลกอริทึมการจัดเรียงที่รวดเร็วสำหรับลิสต์ขนาดเล็กอาจช้าสำหรับลิสต์ที่ยาว วิธีแก้ไขปัญหานี้ตามปกติคือการแสดงเวลาทำงาน (หรือจำนวนการดำเนินการ) เป็นฟังก์ชันของขนาดปัญหา และจัดกลุ่มฟังก์ชันเป็นหมวดหมู่ ขึ้นอยู่กับความเร็วในการเติบโตเมื่อขนาดปัญหาเพิ่มขึ้น

ข้อดีของการเปรียบเทียบประเภทนี้คือสามารถจำแนกอัลกอริทึมอย่างง่ายได้ ตัวอย่างเช่น ถ้าผมรู้ว่าเวลาการทำงานของอัลกอริทึม A มีแนวโน้มที่จะเป็นสัดส่วนกับขนาดของอินพุต $n$ และอัลกอริทึม B มีแนวโน้มที่จะเป็นสัดส่วนกับ $n^2$ ผมคาดว่า A จะเร็วกว่า B อย่างน้อยก็สำหรับค่าขนาดใหญ่ของ $n$

การวิเคราะห์ประเภทนี้มีข้อควรระวังบางประการ แต่เราจะพูดถึงเรื่องนี้ในภายหลัง

B.1 ลำดับการเติบโต

สมมติว่าคุณได้วิเคราะห์สองอัลกอริธึมและแสดงเวลาทำงานในแง่ของขนาดของอินพุต อัลกอริธึม A ใช้ $100n+1$ ขั้นตอนในการแก้ปัญหาด้วยขนาด $n$ อัลกอริทึม B ใช้ $n^2 + n + 1$ ขั้นตอน

ตารางต่อไปนี้แสดงเวลาทำงานของอัลกอริทึมเหล่านี้สำหรับปัญหาขนาดต่างๆ

ขนาดอินพุต	เวลาการทำงานของอัลกอริทึม A	เวลาการทำงานของอัลกอริทึม B
10	1 001	111
100	10 001	10 101
1 000	100 001	1 001 001
10 000	1 000 001	$> 10^{10}$

ที่ $n=10$ อัลกอริธึม A ค่อนข้างแย่ ใช้เวลานานกว่าอัลกอริทึม B เกือบ 10 เท่า แต่สำหรับ $n=100$ จะใกล้เคียงกัน และสำหรับค่าที่มากกว่า A จะดีกว่ามาก

เหตุผลพื้นฐานคือสำหรับค่าขนาดใหญ่ของ $n$ ฟังก์ชันใดๆ ที่มีพจน์ $n^2$ จะเติบโตเร็วกว่าฟังก์ชันที่มีพจน์นำเป็น $n$ พจน์นำ (leading term) คือพจน์ที่มีเลขชี้กำลังสูงสุด

สำหรับอัลกอริทึม A พจน์นำมีค่าสัมประสิทธิ์มากคือ 100 ซึ่งเป็นสาเหตุที่ B ทำได้ดีกว่า A สำหรับ $n$ ขนาดเล็ก แต่ถ้าไม่คำนึงถึงสัมประสิทธิ์ จะมีค่าของ $n$ โดยที่ $a n^2 > b n$ เสมอ สำหรับค่าใดๆ ของ $a$ และ $b$

เหตุผลเดียวกันนี้ใช้กับเงื่อนไขที่ไม่ใช่พจน์นำ แม้ว่าเวลารันของอัลกอริทึม A จะเป็น $n+1000000$ แต่ก็ยังดีกว่าอัลกอริทึม B สำหรับ $n$ ที่มีขนาดใหญ่เพียงพอ

โดยทั่วไป เราคาดว่าอัลกอริธึมที่มีพจน์นำน้อยกว่าจะเป็นอัลกอริธึมที่ดีกว่าสำหรับปัญหาใหญ่ แต่สำหรับปัญหาที่เล็กกว่า อาจมีจุดเปลี่ยนที่อัลกอริทึมอื่นดีกว่า ตำแหน่งของจุดเปลี่ยน (crossover point) ขึ้นอยู่กับรายละเอียดของอัลกอริธึม อินพุต และฮาร์ดแวร์ ดังนั้นจึงมักถูกละเว้นเพื่อวัตถุประสงค์ในการวิเคราะห์อัลกอริธึม แต่นั่นไม่ได้หมายความว่าคุณจะสามารถลืมมันได้

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

ลำดับการเติบโตเป็นกลุ่มของฟังก์ชันซึ่งพฤติกรรมการเติบโตเทียบเท่ากัน ตัวอย่างเช่น $2n$, $100n$ และ $n+1$ อยู่ในลำดับการเติบโตเดียวกัน ซึ่งเขียน $O(n)$ ใน สัญกรณ์บิ๊กโอ (Big-Oh notation) และมักเรียกว่า เชิงเส้น (linear) เนื่องจากทุกฟังก์ชันในชุดเติบโตเชิงเส้นเมื่อเทียบกับ $n$

ฟังก์ชันทั้งหมดที่มีพจน์นำ $n^2$ เป็นกลุ่ม $O(n^2)$ เรียกว่า กำลังสอง (quadratic)

ตารางต่อไปนี้แสดงลำดับการเติบโตบางส่วนที่ปรากฏบ่อยที่สุดในการวิเคราะห์อัลกอริธึม โดยเรียงตามลำดับความแย่เพิ่มขึ้น

ลำดับของ การเติบโต	ชื่อ
$O(1)$	constant
$O(\log_b n)$	logarithmic (for any $b$)
$O(n)$	linear
$O(n \log_b n)$	linearithmic
$O(n^2)$	quadratic
$O(n^3)$	cubic
$O(c^n)$	exponential (for any $c$)

สำหรับเทอมลอการิทึม ฐานของลอการิทึมไม่สำคัญ การเปลี่ยนฐานนั้นเทียบเท่ากับการคูณด้วยค่าคงที่ซึ่งไม่เปลี่ยนลำดับการเติบโต ในทำนองเดียวกัน ฟังก์ชันเอ็กซ์โปเนนเชียลทั้งหมดอยู่ในลำดับการเติบโตเดียวกันโดยไม่คำนึงถึงฐานของเอ็กซ์โปเนนเชียล ฟังก์ชันเอ็กซ์โปเนนเชียลเติบโตอย่างรวดเร็ว ดังนั้นอัลกอริธึมเอ็กซ์โปเนนเชียลจึงมีประโยชน์สำหรับปัญหาขนาดเล็กเท่านั้น

แบบฝึกหัด 1
อ่านหน้าเว็บ Wikipedia เกี่ยวกับสัญลักษณ์ Big-Oh ที่ http://en.wikipedia.org/wiki/Big_O_notation และตอบคำถามต่อไปนี้

ลำดับการเติบโตของ $n^3 + n^2$ คืออะไร? แล้ว $1000000 n^3 + n^2$ ล่ะคืออะไร? แล้ว $n^3 + 1000000 n^2$ ล่ะคืออะไร?
ลำดับการเติบโตของ $(n^2 + n) \cdot (n + 1)$ คืออะไร? ก่อนที่คุณจะเริ่มคูณ จำไว้ว่าคุณต้องการแค่พจน์นำเท่านั้น
ถ้า $f$ อยู่ใน $O(g)$ สำหรับฟังก์ชันที่ไม่ระบุ $g$ เราจะพูดอะไรเกี่ยวกับ $af+b$ ได้บ้าง?
ถ้า $f_1$ และ $f_2$ อยู่ใน $O(g)$ เราจะพูดอะไรเกี่ยวกับ $f_1 + f_2$ ได้บ้าง?
ถ้า $f_1$ อยู่ใน $O(g)$ และ $f_2$ อยู่ใน $O(h)$ เราจะพูดอะไรเกี่ยวกับ $f_1 + f_2$ ได้บ้าง?
ถ้า $f_1$ อยู่ใน $O(g)$ และ $f_2$ คือ O(h) เราจะพูดอะไรเกี่ยวกับ $f_1 \cdot f_2$ ได้บ้าง?

โปรแกรมเมอร์ที่ใส่ใจในประสิทธิภาพมักพบว่าการวิเคราะห์ประเภทนี้ยากที่จะกลืน พวกเขามีประเด็น บางครั้งสัมประสิทธิ์และพจน์ที่ไม่ใช่พจน์นำสร้างความแตกต่างอย่างแท้จริง บางครั้งรายละเอียดของฮาร์ดแวร์ ภาษาโปรแกรม และลักษณะของอินพุตสร้างความแตกต่างอย่างมาก และสำหรับปัญหาเล็กๆ น้อยๆ พฤติกรรมที่ไม่แสดงอาการนั้นไม่มีผล

แต่ถ้าคุณคำนึงถึงคำเตือนเหล่านั้น การวิเคราะห์อัลกอริธึมเป็นเครื่องมือที่มีประโยชน์ อย่างน้อยสำหรับปัญหาใหญ่ อัลกอริธึม “ดีกว่า” มักจะดีกว่า และบางครั้งก็ดีกว่ามาก ความแตกต่างระหว่างอัลกอริธึมสองอัลกอริธึมที่มีลำดับการเติบโตเท่ากันมักจะเป็นปัจจัยคงที่ แต่ความแตกต่างระหว่างอัลกอริธึมที่ดีและอัลกอริธึมที่ไม่ดีนั้นไม่มีขอบเขต!

B.2 การวิเคราะห์การทำงานพื้นฐานของไพธอน

ในไพธอนการดำเนินการทางคณิตศาสตร์ส่วนใหญ่จะเป็นเวลาคงที่ การคูณมักใช้เวลานานกว่าการบวกและการลบ และการหารใช้เวลานานกว่านั้นอีก แต่เวลาดำเนินการเหล่านี้ไม่ได้ขึ้นอยู่กับขนาดของตัวถูกดำเนินการ ยกเว้นจำนวนเต็มที่มีขนาดใหญ่มาก ในกรณีนั้นเวลาทำงานจะเพิ่มขึ้นตามจำนวนหลัก

คำสั่งเชิงดัชนีได้แก่การอ่านหรือการเขียนองค์ประกอบในลำดับ หรือดิกชันนารี เป็นเวลาคงที่เช่นกันโดยไม่คำนึงถึงขนาดของโครงสร้างข้อมูล

ลูป for ที่ข้ามผ่านซีเควนซ์หรือดิกชันนารีมักจะเป็นเชิงเส้น ตราบใดที่การดำเนินการทั้งหมดในเนื้อความของลูปเป็นเวลาคงที่ ตัวอย่างเช่น การเพิ่มองค์ประกอบของลิสต์เป็นแบบเชิงเส้น

    total = 0
    for x in t:
        total += x

ฟังก์ชันในตัว sum ยังเป็นแบบเชิงเส้นด้วยเพราะมันทำแบบเดียวกัน แต่มีแนวโน้มที่จะเร็วกว่าเพราะเป็นการใช้งานที่มีประสิทธิภาพมากกว่า ในภาษาของการวิเคราะห์อัลกอริธึม มีค่าสัมประสิทธิ์นำหน้าน้อยกว่า

ตามหลักการทั่วไป ถ้าเนื้อหาของลูปอยู่ใน $O(n^a)$ แล้วลูปทั้งหมดจะอยู่ใน $O(n^{a+1})$ ข้อยกเว้นคือถ้าคุณสามารถแสดงว่าลูปออกหลังจากวนซ้ำเป็นจำนวนคงที่ หากการวนซ้ำทำงาน $k$ ครั้งโดยไม่คำนึงถึง $n$ ดังนั้นการวนซ้ำจะอยู่ใน $O(n^a)$ แม้สำหรับ $k$ ขนาดใหญ่

การคูณด้วย $k$ ไม่ได้เปลี่ยนลำดับการเติบโต แม้แต่การหารด้วย ดังนั้นถ้าเนื้อความของลูปอยู่ใน $O(n^a)$ และรัน $n/k$ ครั้ง การวนซ้ำจะอยู่ใน $O(n^{a+1})$ แม้สำหรับ $k$ ขนาดใหญ่

การดำเนินการสตริงและทูเพิลส่วนใหญ่เป็นแบบเชิงเส้น ยกเว้นการเข้าถึงตำแหน่งตามดัชนีและการหาความยาว (len) ซึ่งเป็นเวลาคงที่ ฟังก์ชันในตัว min และ max เป็นแบบเชิงเส้น เวลาในการทำงานของการดำเนินการตัดช่วง เป็นสัดส่วนกับความยาวของเอาต์พุต แต่ไม่ขึ้นกับขนาดของอินพุต

การต่อสตริงเป็นแบบเชิงเส้น เวลาในการทำงานขึ้นอยู่กับผลรวมของความยาวของตัวถูกดำเนินการ

เมธอดสตริงทั้งหมดเป็นแบบเชิงเส้น แต่ถ้าความยาวของสตริงถูกจำกัดด้วยค่าคงที่ ตัวอย่างเช่น การดำเนินการกับอักขระตัวเดียว จะถือเป็นเวลาคงที่ สตริงเมธอด join เป็นแบบเชิงเส้น เวลาในการทำงานขึ้นอยู่กับความยาวทั้งหมดของสตริง

ลิสต์เมธอดส่วนใหญ่เป็นแบบเชิงเส้น แต่มีข้อยกเว้นบางประการ

การเพิ่มองค์ประกอบที่ส่วนท้ายของรายการเป็นเวลาโดยเฉลี่ยคงที่ เมื่อมันหมดที่ว่างบางครั้งจะถูกคัดลอกไปยังตำแหน่งที่ใหญ่กว่า แต่เวลาทั้งหมดสำหรับการดำเนินการ $n$ ครั้งคือ $O(n)$ ดังนั้นเวลาเฉลี่ยสำหรับการดำเนินการแต่ละครั้งคือ $O(1)$
การลบองค์ประกอบออกจากจุดสิ้นสุดของรายการเป็นเวลาคงที่
การจัดเรียงเป็น $O(n \log n)$

การดำเนินการและเมธอดสำหรับดิกชันนารีส่วนใหญ่เป็นเวลาที่คงที่ แต่มีข้อยกเว้นบางประการ

เวลาในการทำงานของการอัปเดตเป็นสัดส่วนกับขนาดของดิกชันนารีที่ส่งผ่านเป็นพารามิเตอร์ ไม่ใช่ดิกชันนารีที่กำลังอัปเดต
keys, values และ items เป็นเวลาคงที่เพราะมันส่งกลับตัววนซ้ำ แต่ถ้าคุณวนซ้ำผ่านตัววนซ้ำ การวนซ้ำจะเป็นแบบเชิงเส้น

การแสดงดิกชันนารีเป็นหนึ่งในปาฏิหาริย์เล็กๆ น้อยๆ ของวิทยาการคอมพิวเตอร์ เราจะดูว่ามันทำงานอย่างไรในหัวข้อ B.4

แบบฝึกหัด 2
อ่านหน้า Wikipedia เกี่ยวกับอัลกอริทึมการเรียงลำดับที่ http://en.wikipedia.org/wiki/Sorting_algorithm และตอบคำถามต่อไปนี้:

“การเรียงลำดับใช้การเปรียบเทียบ” คืออะไร อะไรคือลำดับการเติบโตที่แย่ที่สุดที่ดีที่สุดสำหรับการเรียงลำดับใช้การเปรียบเทียบ ลำดับการเติบโตของกรณีที่เลวร้ายที่สุด ที่ดีที่สุด สำหรับอัลกอริธึมการเรียงลำดับคืออะไร?
ลำดับการเติบโตของเรียงข้อมูลแบบบับเบิ้ล (Bubble Sort) คืออะไร และเหตุใดบารัค โอบามาจึงคิดว่า “ไปในทางที่ผิด”
ลำดับการเติบโตของการเรียงแบบเรดิก (Radix sort) คืออะไร? เราจำเป็นต้องใช้เงื่อนไขเบื้องต้นอะไรบ้าง?
การจัดเรียงที่มั่นคง (stable sort) คืออะไร และเหตุใดจึงอาจมีความสำคัญในทางปฏิบัติ
อัลกอริธึมใดที่มีการเรียงลำดับที่แย่ที่สุด (ที่มีชื่อ)
ไลบรารีภาษา C ใช้อัลกอริทึมการเรียงลำดับแบบใด ไพธอนใช้อัลกอริทึมการเรียงลำดับแบบใด อัลกอริธึมเหล่านี้เสถียรหรือไม่ คุณอาจต้องใช้ Google เพื่อค้นหาคำตอบเหล่านี้
การเรียงลำดับที่ไม่เปรียบเทียบจำนวนมากเป็นแบบเชิงเส้น ทำไมไพธอนจึงใช้การเรียงลำดับที่ใช้การเปรียบเทียบ ทำงานเป็น $O(n \log n)$

B.3 การวิเคราะห์อัลกอริธึมการค้นหา

การค้นหาคืออัลกอริธึมที่ใช้กลุ่มหมู่และรายการเป้าหมายแล้วหาว่าเป้าหมายอยู่ในกลุ่มหมู่หรือไม่ ซึ่งมักจะส่งคืนดัชนีของเป้าหมาย

อัลกอริธึมการค้นหาที่ง่ายที่สุดคือ “การค้นหาเชิงเส้น” ซึ่งสำรวจรายการในกลุ่มหมู่ตามลำดับ และหยุดหากพบเป้าหมาย ในกรณีที่เลวร้ายที่สุด จะต้องสำรวจกลุ่มหมู่ทั้งหมด ดังนั้นเวลาทำงานจึงเป็นแบบเส้นตรง

ตัวดำเนินการ in สำหรับซีเควนซ์ใช้การค้นหาเชิงเส้น เมธอดสตริงก็เช่นกัน เช่น find และ count

หากองค์ประกอบของลำดับอยู่ในลำดับ คุณสามารถใช้ การค้นหาแบบแบ่งสองส่วน (bisection search) ซึ่งเป็น $O(\log n)$ การค้นหาแบบสองส่วนคล้ายกับอัลกอริทึมที่คุณอาจใช้เพื่อค้นหาคำในดิกชันนารี (ดิกชันนารีกระดาษ ไม่ใช่โครงสร้างข้อมูล) แทนที่จะเริ่มต้นที่จุดเริ่มต้นและตรวจสอบแต่ละรายการตามลำดับ คุณเริ่มต้นด้วยรายการที่อยู่ตรงกลางและตรวจสอบว่าคำที่คุณกำลังมองหามาก่อนหรือหลัง ถ้ามันมาก่อน ให้ค้นหาครึ่งแรกของซีเควนซ์ มิฉะนั้นคุณจะค้นหาครึ่งหลัง ไม่ว่าจะด้วยวิธีใด คุณจะลดจำนวนรายการที่เหลือลงครึ่งหนึ่ง

ถ้าซีเควนซ์มี 1,000,000 ไอเท็ม จะใช้เวลาประมาณ 20 ขั้นในการหาคำหรือสรุปว่าไม่มี ซึ่งเร็วกว่าการค้นหาเชิงเส้นประมาณ 50,000 เท่า

การค้นหาแบบแบ่งสองส่วนอาจเร็วกว่าการค้นหาเชิงเส้นมาก แต่ต้องมีข้อมูลเรียงตามลำดับ ซึ่งอาจต้องมีการทำงานเพิ่มเติม

มีโครงสร้างข้อมูลอื่นซึ่งสามารถทำแฮชได้จะค้นหาได้เร็วยิ่งขึ้น สามารถค้นหาได้ในเวลาคงที่และไม่ต้องการรายการที่เรียงลำดับไว้ก่อน ดิกชันนารีของไพธอนถูกพัฒนาโดยใช้ตารางแฮชซึ่งเป็นสาเหตุที่การดำเนินการกับดิกชันนารีส่วนใหญ่ รวมถึงตัวดำเนินการ in เป็นเวลาคงที่

B.4 ตารางแฮช

เพื่ออธิบายว่าตารางแฮชทำงานอย่างไรและทำไมประสิทธิภาพของมันถึงดีมาก ผมเริ่มต้นด้วยการใช้งาน การแปลง (maps) อย่างง่าย และค่อยๆ ปรับปรุงจนกระทั่งเป็นตารางแฮช

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

add(k, v): เพิ่มรายการใหม่ที่แปลงจากคีย์ k ถึงค่า v ด้วยดิกชันนารี d การดำเนินการนี้จะถูกเขียน d[k] = v
get(k): ค้นหาและส่งกลับค่าที่สอดคล้องกับคีย์ k ด้วยดิกชันนารี d การดำเนินการนี้จะถูกเขียน d[k] หรือ d.get(k)

สำหรับตอนนี้ ผมคิดว่าแต่ละคีย์จะปรากฏเพียงครั้งเดียว การใช้งานอินเทอร์เฟซนี้อย่างง่ายที่สุดใช้รายการของทูเพิล โดยที่ทูเพิลแต่ละตัวเป็นคู่คีย์-ค่า

class LinearMap:
 
    def __init__(self):
        self.items = []
 
    def add(self, k, v):
        self.items.append((k, v))
 
    def get(self, k):
        for key, val in self.items:
            if key == k:
                return val
        raise KeyError

add ผนวกทูเพิลของคีย์-ค่าเข้ากับรายการซึ่งใช้เวลาคงที่

get ใช้ลูป for เพื่อค้นหารายการ หากพบคีย์เป้าหมาย จะส่งกลับค่าที่สอดคล้องกัน มิฉะนั้นจะทำให้เกิด KeyError ดังนั้น get จึงเป็นเชิงเส้น

อีกทางเลือกหนึ่งคือให้รายการเรียงตามคีย์ จากนั้น get สามารถใช้การค้นหาแบบแบ่งสองส่วนซึ่งก็เป็น $O(\log n)$ แต่การแทรกรายการใหม่ตรงกลางรายการเป็นแบบเชิงเส้น ดังนั้นนี่อาจไม่ใช่ตัวเลือกที่ดีที่สุด มีโครงสร้างข้อมูลอื่นๆ ที่สามารถใช้ add และ get เป็นเวลาลอการิทึม (log time) ได้ แต่ก็ยังไม่ดีเท่ากับเวลาคงที่ ดังนั้นไปต่อกัน

วิธีหนึ่งในการปรับปรุง LinearMap คือการแบ่งรายการคู่คีย์-ค่าออกเป็นรายการที่เล็กลง นี่คือการใช้งานที่เรียกว่า BetterMap ซึ่งเป็นรายการ 100 LinearMaps อย่างที่เราจะเห็น ลำดับการเติบโตสำหรับ get ยังคงเป็นเชิงเส้น แต่ BetterMap เป็นขั้นตอนบนเส้นทางสู่ตารางแฮช

class BetterMap:
 
    def __init__(self, n=100):
        self.maps = []
        for i in range(n):
            self.maps.append(LinearMap())
 
    def find_map(self, k):
        index = hash(k) % len(self.maps)
        return self.maps[index]
 
    def add(self, k, v):
        m = self.find_map(k)
        m.add(k, v)
 
    def get(self, k):
        m = self.find_map(k)
        return m.get(k)

__init__ สร้าง n ลิสต์ของ LinearMap

find_map ถูกใช้โดยการ add และ get ว่าการแปลงใดที่จะวางรายการใหม่ หรือการแปลงใดที่จะค้นหา

find_map ใช้ฟังก์ชันแฮชในตัว ซึ่งรับไพธอนออบเจ๊คต์เกือบทั้งหมดและคืนค่าจำนวนเต็ม ข้อจำกัดของการใช้งานนี้คือ ใช้งานได้กับคีย์ที่แฮชได้เท่านั้น ประเภทที่เปลี่ยนแปลงได้ เช่น ลิสต์และดิกชันนารีจะแฮชไม่ได้

ออบเจ็กต์ที่แฮชได้ซึ่งถือว่าเทียบเท่าจะคืนค่าแฮชเดียวกัน แต่ในทางกลับกันไม่จำเป็นต้องเป็นจริง เพราะออบเจ็กต์สองรายการที่มีค่าต่างกันสามารถคืนค่าแฮชเดียวกันได้

find_map ใช้ตัวดำเนินการโมดูลัสเพื่อรวมค่าแฮชในช่วงตั้งแต่ 0 ถึง len(self.maps) ดังนั้นผลลัพธ์จึงเป็นดัชนีที่ถูกต้องในลิสต์แน่นอน นี่หมายความว่าค่าแฮชที่แตกต่างกันจำนวนมากจะรวมไว้ในดัชนีเดียวกัน แต่ถ้าฟังก์ชันแฮชกระจายสิ่งต่างๆ ได้ค่อนข้างเท่ากัน (ซึ่งเป็นสิ่งที่ฟังก์ชันแฮชได้รับการออกแบบมาให้ทำ) เราก็คาดหวัง $n/100$ ไอเท็มต่อ LinearMap

เนื่องจากเวลารันของ LinearMap.get เป็นสัดส่วนกับจำนวนรายการ เราคาดว่า BetterMap จะเร็วกว่า LinearMap ประมาณ 100 เท่า ลำดับการเติบโตยังคงเป็นเส้นตรง แต่ค่าสัมประสิทธิ์นำหน้าจะน้อยกว่า นั่นเป็นสิ่งที่ดี แต่ก็ยังไม่ดีเท่าแฮชเทเบิล

ทีนี้ (สุดท้าย) เป็นแนวคิดสำคัญที่ทำให้ตารางแฮชเร็วขึ้น หากคุณสามารถรักษาความยาวสูงสุดของ LinearMaps ไว้ได้ LinearMap.get เป็นเวลาคงที่ สิ่งที่คุณต้องทำคือติดตามจำนวนไอเท็ม และเมื่อจำนวนรายการต่อ LinearMap เกินเกณฑ์ ให้ปรับขนาดตารางแฮชโดยเพิ่มจำนวน LinearMaps ให้มากขึ้น

นี่คือการใช้งานตารางแฮช

class HashMap:
 
    def __init__(self):
        self.maps = BetterMap(2)
        self.num = 0
 
    def get(self, k):
        return self.maps.get(k)
 
    def add(self, k, v):
        if self.num == len(self.maps.maps):
            self.resize()
 
        self.maps.add(k, v)
        self.num += 1
 
    def resize(self):
        new_maps = BetterMap(self.num * 2)
 
        for m in self.maps.maps:
            for k, v in m.items:
                new_maps.add(k, v)
 
        self.maps = new_maps

HashMap แต่ละอันมี BetterMap __init__ เริ่มต้นด้วย LinearMaps เพียง 2 รายการและกำหนดค่าเริ่มต้น num ซึ่งจะติดตามจำนวนรายการ

get เพียงแค่ส่งไปยัง BetterMap งานจริงเกิดขึ้นใน add ซึ่งจะตรวจสอบจำนวนรายการและขนาดของ BetterMap หากเท่ากันจำนวนเฉลี่ยของรายการต่อ LinearMap คือ 1 ดังนั้นจึงเรียกใช้ resize

resize สร้าง BetterMap ใหม่ ให้ใหญ่เป็นสองเท่าของแผนที่ก่อน จากนั้น “แฮชใหม่ (rehashes)” ไอเท็มจากการแปลงเก่าไปการแปลงใหม่

จำเป็นต้องมีการแฮชใหม่ เนื่องจากการเปลี่ยนจำนวน LinearMaps จะเปลี่ยนตัวหารของตัวดำเนินการโมดูลัสใน find_map นั่นหมายความว่าบางออบเจ๊คต์ที่เคยแฮชลงใน LinearMap เดียวกันจะถูกแยกออก (นั่นคือสิ่งที่เราต้องการ, จริงไหม?)

การแฮชใหม่เป็นแบบเชิงเส้น ดังนั้น resize จึงเป็นแบบเชิงเส้น ซึ่งอาจดูแย่ เนื่องจากผมสัญญาว่า add จะเป็นเวลาคงที่ แต่จำไว้ว่าเราไม่จำเป็นต้องปรับขนาดทุกครั้ง ดังนั้น add มักจะเป็นเวลาคงที่และเป็นเชิงเส้นในบางครั้งเท่านั้น จำนวนงานที่จะรันทั้งหมดบวก $n$ ครั้งเป็นสัดส่วนกับ $n$ ดังนั้นเวลาเฉลี่ยของ add แต่ละครั้งคือเวลาคงที่!

หากต้องการดูวิธีการทำงาน ให้นึกถึงการเริ่มต้นด้วย HashTable ที่ว่างเปล่าและเพิ่มลำดับของรายการ เราเริ่มต้นด้วย 2 LinearMaps ดังนั้นการเพิ่ม 2 รายการแรกนั้นรวดเร็ว (ไม่จำเป็นต้องปรับขนาด) สมมติว่าแต่ละครั้งทำงานหนึ่งหน่วย การเพิ่มครั้งต่อไปต้องมีการปรับขนาด ดังนั้นเราจึงต้องแฮชสองรายการแรก (ซึ๋งเรียกเพิ่มอีก 2 หน่วยทำงาน) แล้วเพิ่มรายการที่สาม (อีกหนึ่งหน่วย) การเพิ่มรายการถัดไปมีค่าใช้จ่าย 1 หน่วยดังนั้นยอดรวมคือ 6 หน่วยสำหรับ 4 รายการ

การเพิ่มครั้งต่อไปมีค่าใช้จ่าย 5 หน่วย แต่สามหน่วยถัดไปมีเพียงครั้งละหนึ่งหน่วย ดังนั้นยอดรวมคือ 14 หน่วยสำหรับการเพิ่ม 8 ครั้งแรก

การเพิ่มครั้งต่อไปมีค่าใช้จ่าย 9 หน่วย แต่จากนั้นเราสามารถเพิ่มอีก 7 ครั้งก่อนการปรับขนาดครั้งต่อไป ดังนั้นยอดรวมคือ 30 หน่วยสำหรับการเพิ่ม 16 รายการแรก

หลังจากเพิ่ม 32 รายการ ค่าใช้จ่ายทั้งหมดคือ 62 หน่วย และผมหวังว่าคุณจะเริ่มเห็นรูปแบบ หลังจากเพิ่ม $n$ ครั้ง โดยที่ $n$ เป็นยกกำลังของสอง ต้นทุนรวมคือ $2n-2$ หน่วย ดังนั้นงานเฉลี่ยต่อการเพิ่มจะน้อยกว่า 2 หน่วยเล็กน้อย เมื่อ $n$ เป็นกำลังสอง นั่นคือกรณีที่ดีที่สุด สำหรับค่าอื่นๆ ของ $n$ งานเฉลี่ยจะสูงขึ้นเล็กน้อย แต่นั่นไม่สำคัญ ที่สำคัญคือ $O(1)$

รูปที่ B.1 แสดงวิธีการทำงานแบบกราฟิก แต่ละบล็อกแสดงถึงหน่วยของงาน คอลัมน์แสดงงานทั้งหมดสำหรับการเพิ่มแต่ละรายการโดยเรียงลำดับจากซ้ายไปขวา สองรายการแรกเพิ่มต้นทุน 1 หน่วย รายการที่สามต้นทุน 3 หน่วย ฯลฯ

รูปที่ B.1 ค่าใช้จ่ายของการเพิ่มแฮชเทเบิล

งานพิเศษของการรีแฮชจะปรากฏเป็นลำดับของหอคอยที่สูงขึ้นเรื่อยๆ พร้อมช่องว่างระหว่างพวกเขาที่เพิ่มขึ้น ตอนนี้ถ้าคุณเคาะเหนือหอคอย กระจายค่าใช้จ่ายในการปรับขนาดไปยังการเพิ่มทั้งหมด คุณจะเห็นภาพกราฟิกว่าค่าใช้จ่ายทั้งหมดหลังจาก $n$ ครั้งเป็น $2n - 2$

คุณลักษณะที่สำคัญของอัลกอริธึมนี้คือเมื่อเราปรับขนาดตารางแฮชมันจะเติบโตในเชิงเรขาคณิต นั่นคือเราคูณขนาดด้วยค่าคงที่ หากคุณเพิ่มขนาดทางคณิตศาสตร์ คือการบวกจำนวนคงที่ในแต่ละครั้ง เวลาเฉลี่ยต่อการเพิ่มจึงเป็นเส้นตรง

คุณสามารถดาวน์โหลด HashMap ของผมได้จาก http://thinkpython2.com/code/Map.py แต่จำไว้ว่าไม่มีเหตุผลที่จะใช้มัน หากคุณต้องการ การแปลง ให้ใช้ดิกชันนารีของไพธอน

B.5 อภิธานศัพท์

การวิเคราะห์อัลกอริทึม (analysis of algorithms): วิธีเปรียบเทียบอัลกอริทึมในแง่ของเวลาใช้งานและ/หรือข้อกำหนดด้านพื้นที่
โมเดลของเครื่อง (machine model): การแทนอย่างง่ายสำหรับคอมพิวเตอร์เพื่อใช้อธิบายอัลกอริทึม
กรณีที่แย่ที่สุด (worst case): อินพุตที่ทำให้อัลกอริทึมที่สนใจทำงานช้าที่สุด (หรือต้องการพื้นที่มากที่สุด)
พจน์นำ (leading term): พจน์ที่มีเลขชี้กำลังสูงสุดในพหุนาม
จุดเปลี่ยน (crossover point): ขนาดปัญหาที่อัลกอริธึมสองตัวต้องใช้เวลาหรือพื้นที่ทำงานเท่ากัน
ลำดับการเติบโต (order of growth): ชุดของฟังก์ชันที่เติบโตในลักษณะที่เทียบเท่ากับวัตถุประสงค์ของการวิเคราะห์อัลกอริธึม ตัวอย่างเช่น ฟังก์ชันทั้งหมดที่เติบโตเชิงเส้นอยู่ในลำดับการเติบโตเดียวกัน
สัญกรณ์บิ๊กโอ (Big-Oh notation): สัญกรณ์สำหรับแสดงลำดับการเติบโต ตัวอย่างเช่น $O(n)$ แทนชุดของฟังก์ชันที่เติบโตเป็นเส้นตรง
เชิงเส้น (linear): อัลกอริธึมที่เวลาทำงานเป็นสัดส่วนกับขนาดของปัญหา อย่างน้อยก็สำหรับปัญหาขนาดใหญ่
กำลังสอง (quadratic): อัลกอริทึมที่มีเวลาทำงานเป็นสัดส่วนกับ $n^2$ โดยที่ $n$ คือขนาดของปัญหา
การค้นหา (search): ปัญหาในการหาตำแหน่งองค์ประกอบของกลุ่มหมู่ (เช่น ลิสต์หรือดิกชันนารี) หรือการพิจารณาว่าไม่มีองค์ประกอบนั้น
ตารางแฮช (hashtable): โครงสร้างข้อมูลที่แสดงถึงชุดของคู่คีย์-ค่าและทำการค้นหาในเวลาคงที่

https://greenteapress.com/thinkpython2/html/thinkpython2022.html

¹⁾

แต่ถ้าคุณได้รับคำถามแบบนี้ในการสัมภาษณ์ ผมคิดว่าคำตอบที่ดีกว่าคือ “วิธีที่เร็วที่สุดในการจัดเรียงจำนวนเต็มหนึ่งล้านตัวคือการใช้ฟังก์ชันการจัดเรียงใดๆ ก็ตามที่มีให้โดยภาษาที่ผมใช้ ประสิทธิภาพดีพอสำหรับแอปพลิเคชันส่วนใหญ่ แต่ถ้าปรากฏว่าแอปพลิเคชันของผมช้าเกินไป ผมจะใช้ตัวสร้างโปรไฟล์เพื่อดูว่าเวลาที่ใช้ไปอยู่ที่ใด หากดูเหมือนว่าอัลกอริธึมการจัดเรียงที่เร็วกว่าจะมีผลกระทบอย่างมากต่อประสิทธิภาพ ผมก็คงจะมองหาการเรียงลำดับแบบ radix ที่ดีๆ มาใช้”