การเรียงลำดับเพชันส์
ในด้านวิทยาศาสตร์คอมพิวเตอร์ patience sorting เป็นขั้นตอนวิธีการจัดเรียงที่ได้รับแรงบันดาลใจจากและตั้งชื่อตามการถอดไพ่ของเกมการ์ด ตัวแปรของอัลกอริทึมมีประสิทธิภาพคำนวณความยาวของบันไดที่ยาวที่สุดเพิ่มมาในอาร์เรย์ที่ระบุ
| ประเภท | Sorting algorithm |
|---|---|
| โครงสร้างข้อมูล | Array |
| ประสิทธิภาพเมื่อเกิดกรณีแย่ที่สุด | O(n log n) |
| ประสิทธิภาพเมื่อเกิดกรณีดีที่สุด | O(n); occurs when the input is pre-sorted |
ภาพรวม
ชื่อของอัลกอริทึมมาจากรูปแบบที่เรียบง่ายของเกมการ์ดการถอดไพ่ เกมนี้เริ่มต้นด้วยไพ่สับไพ่ การ์ดเหล่านี้จะถูกแจกเป็นลำดับกองบนโต๊ะตามกฎต่อไปนี้
1. เริ่มแรกไม่มีกองไพ่ ไพ่ใบแรกที่แจกให้เป็นกองใหม่ประกอบด้วยไพ่ใบเดียว
2. การ์ดใบต่อ ๆ ไปจะอยู่บนกองที่มีอยู่ด้านซ้ายสุดซึ่งการ์ดด้านบนมีค่ามากกว่าหรือเท่ากับค่าของบัตรใหม่หรือด้านขวาของกองไพ่ทั้งหมดที่มีอยู่แล้วจึงเป็นกองใหม่
3. เมื่อไม่มีไพ่เหลืออยู่อีกต่อไปเกมจะสิ้นสุดลง
เกมการ์ดใบนี้ถูกเปลี่ยนเป็นอัลกอริทึมการจัดเรียงแบบสองเฟสดังนี้ ให้อาร์เรย์ขององค์ประกอบ n จากโดเมนทั้งหมด ให้พิจารณาอาร์เรย์นี้เป็นชุดของการ์ดและจำลอง patience sorting ในการเรียงลำดับเกม เมื่อเกมเสร็จสิ้นแล้วให้กู้คืนลำดับที่เรียงลำดับโดยการเลือกการ์ดที่มองเห็นได้น้อย ๆ กล่าวคือให้ทำการรวม k วิธี ของ p กอง ซึ่งแต่ละอันจะเรียงลำดับกันภายใน
การวิเคราะห์
ขั้นตอนแรกของ patience sort การจำลองเกมการ์ดสามารถใช้เพื่อเปรียบเทียบ O (n log n) ในกรณีที่เลวร้ายที่สุดสำหรับอาร์เรย์ข้อมูล n-element: จะมีกอง n ส่วนใหญ่และโดยการก่อสร้างด้านบน ไพ่ของกองแบบฟอร์มลำดับที่เพิ่มขึ้นจากซ้ายไปขวาดังนั้นกองที่ต้องการสามารถพบได้โดยการค้นหาแบบไบนารี ระยะที่สองการรวมกองสามารถทำได้ในเวลา O (n log n) ด้วยการใช้การเข้าคิวลำดับความสำคัญ
เมื่อข้อมูลอินพุตมีข้อมูล "ทำงาน" ตามธรรมชาติเช่นโครงสร้างย่อยที่ไม่ลดลงประสิทธิภาพจะดีขึ้นอย่างเห็นได้ชัด ในความเป็นจริงเมื่ออาร์เรย์อินพุตถูกจัดเรียงเรียบร้อยแล้วค่าทั้งหมดจะเป็นแบบกองเดียวและทั้งสองเฟสจะทำงานในเวลา O (n) ความซับซ้อนของกรณีโดยเฉลี่ยยังคงเป็น O (n log n): ลำดับสุ่มของค่าใด ๆ จะให้จำนวน O (√n) ที่คาดหวังไว้, ซึ่งใช้เวลา O (n log √n) = O (n log n) เวลาในการผลิตและผสาน
การประเมินผลการปฏิบัติงานของ patience sort คือ Chandramouli และ Goldstein ผู้แสดงให้เห็นว่า naive version ช้ากว่า quicksort เป็นเวลาประมาณสิบถึงยี่สิบนาที quicksort บนปัญหามาตรฐานของพวกเขา พวกเขาให้เหตุผลว่าเป็นการวิจัยเชิงปริมาณเพียงเล็กน้อยของ patience sort และพัฒนาการเพิ่มประสิทธิภาพหลายอย่างซึ่งจะทำให้ประสิทธิภาพการทำงานของมันอยู่ในระดับที่สองของ quicksort
ถ้าค่าของการ์ดอยู่ในช่วง 1,....,n, มีการใช้งานที่มีประสิทธิภาพด้วย O (n log log n) เวลาทำงานที่เลวร้ายที่สุด (worst-case) สำหรับการใส่ไพ่ลงกองโดยใช้ต้นไม้ Van Emde Boas
ความสัมพันธ์กับปัญหาอื่นธ์
Patience sorting มีความเกี่ยวข้องกับเกมไพ่ที่เรียกว่าเกม Floyd เกมนี้มีความคล้ายคลึงกับเกมที่ร่างไว้ก่อนหน้านี้:
1. บัตรแรกที่แจกให้เป็นกองใหม่ประกอบด้วยการ์ดใบเดียว
2. การ์ดใบใดก็ตามที่มีอยู่จะถูกวางลงบนกองที่มีอยู่ซึ่งการ์ดด้านบนมีค่าไม่เกินมูลค่าของบัตรใหม่หรือด้านขวาของไพ่ทั้งหมดที่มีอยู่แล้วจึงเป็นกองใหม่
3. เมื่อไม่มีไพ่เหลืออยู่อีกแล้วเกมจะสิ้นสุดลง
เป้าหมายของเกมคือการจบด้วยกองน้อยที่สุดเท่าที่จะเป็นไปได้ ความแตกต่างกับอัลกอริธึม Patience sorting คือไม่จำเป็นต้องวางการ์ดใบใหม่ไว้ที่กองซ้ายสุดซึ่งจะได้รับอนุญาต การเรียงลำดับความอดทนถือเป็นกลยุทธ์ greedy ในการเล่นเกมนี้
Aldous และ Diaconis แนะนำให้กำหนดกอง 9 หรือน้อยกว่าเป็นผลลัพธ์ที่ดีสำหรับ n = 52 ซึ่งเกิดขึ้นได้ด้วยความน่าจะเป็นประมาณ 5%
อัลกอริทึมสำหรับการหาลำดับชั้นที่ยาวที่สุดที่เพิ่มขึ้น
ขั้นแรกให้รันอัลกอริทึมการเรียงลำดับตามที่อธิบายไว้ด้านบน จำนวนกองเป็นความยาวของบันไดที่ยาวที่สุด เมื่อใดก็ตามที่มีการวางไพ่ขึ้นด้านบนของกองให้วางตัวชี้กลับไปที่ด้านบนของไพ่ในกองก่อนหน้านี้ (ที่โดยสมมติฐานมีค่าต่ำกว่าการ์ดใบใหม่มี) ในตอนท้ายให้ทำตามตัวชี้ด้านหลังจากด้านบนของไพ่ในกองสุดท้ายเพื่อกู้คืนความยาวที่ลดลงของความยาวที่ยาวที่สุด ย้อนกลับของมันคือคำตอบของอัลกอริธึมย่อยที่เพิ่มขึ้นที่ยาวที่สุด
S. Bespamyatnikh และ M. Segal ให้คำอธิบายเกี่ยวกับการใช้อัลกอริธึมที่มีประสิทธิภาพโดยไม่ก่อให้เกิดค่าใช้จ่ายเพิ่มเติมในการจัดเรียง (เนื่องจากการจัดเก็บข้อมูลการสร้างและการข้ามผ่านแบบย้อนหลังต้องใช้เวลาและพื้นที่เชิงเส้น) พวกเขายังแสดงวิธีการรายงานข้อมูลที่ยาวที่สุดทั้งหมดที่เพิ่มขึ้นจากโครงสร้างข้อมูลผลลัพธ์ที่เหมือนกัน
หลักการทำงาน
Coding
Python
import bisect, heapq def sort(seq): piles = [] for x in seq: new_pile = [x] i = bisect.bisect_left(piles, new_pile) if i != len(piles): piles[i].insert(0, x) else: piles.append(new_pile) print "longest increasing subsequence has length =", len(piles) # priority queue allows us to retrieve least pile efficiently for i in xrange(len(seq)): small_pile = piles[0] seq[i] = small_pile.pop(0) if small_pile: heapq.heapreplace(piles, small_pile) else: heapq.heappop(piles) assert not piles foo = [4, 65, 2, 4, -31, 0, 99, 1, 83, 782, 1] sort(foo) print foo ประวัติ
Patience sorting ได้รับการตั้งชื่อโดย C. L. Mallows ผู้ที่คิดค้นสิ่งประดิษฐ์ให้กับ A.S.C. Ross ในต้นปี 1960 ตามที่ Aldous และ Diaconis Patience sorting เป็นที่รู้จักเป็นอันดับแรกในฐานะอัลกอริทึมในการคำนวณความยาวที่ยาวที่สุดโดย Hammersley และโดย A.S.C. Ross และ Robert W. Floyd เป็นขั้นตอนการจัดเรียง การวิเคราะห์ครั้งแรกทำโดย Mallows เกม Floyd ได้รับการพัฒนาโดย Floyd ในการติดต่อกับ Donald Knuth
นำไปใช้
อัลกอริทึม patience sorting สามารถใช้กับการควบคุมกระบวนการ ในชุดของการวัดการดำรงอยู่ของการเพิ่มระยะยาวที่สามารถใช้เป็นเครื่องหมายแนวโน้ม บทความ 2002 ในนิตยสาร SQL Server มีการใช้ SQL ในบริบทนี้ของอัลกอริธึมการจัดเรียงความอดทนสำหรับระยะเวลาที่ยาวที่สุดที่มีการเพิ่มขึ้น
- Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors (PDF). SIGMOD/PODS.