หลามเรียงลำดับคอนเทนเนอร์

Python จัดเรียงคอนเทนเนอร์

Sorted Containers เป็นไลบรารีคอลเลกชั่นเรียงลำดับที่ได้รับลิขสิทธิ์ของ Apache2 เขียนด้วย Pure-Python และรวดเร็วเท่ากับส่วนขยาย C

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

ใน Python เราสามารถทำได้ดีกว่า และเราสามารถทำได้ใน pure-Python!

 > >> from sortedcontainers import SortedList
> >> sl = SortedList ([ 'e' , 'a' , 'c' , 'd' , 'b' ])
> >> sl
SortedList ([ 'a' , 'b' , 'c' , 'd' , 'e' ])
> >> sl *= 10_000_000
> >> sl . count ( 'c' )
10000000
> >> sl [ - 3 :]
[ 'e' , 'e' , 'e' ]
> >> from sortedcontainers import SortedDict
> >> sd = SortedDict ({ 'c' : - 3 , 'a' : 1 , 'b' : 2 })
> >> sd
SortedDict ({ 'a' : 1 , 'b' : 2 , 'c' : - 3 })
> >> sd . popitem ( index = - 1 )
( 'c' , - 3 )
> >> from sortedcontainers import SortedSet
> >> ss = SortedSet ( 'abracadabra' )
> >> ss
SortedSet ([ 'a' , 'b' , 'c' , 'd' , 'r' ])
> >> ss . bisect_left ( 'c' )
2

การดำเนินการทั้งหมดที่แสดงข้างต้นจะดำเนินการเร็วกว่าเวลาเชิงเส้น การสาธิตข้างต้นยังใช้หน่วยความจำเกือบหนึ่งกิกะไบต์ในการทำงาน เมื่อรายการที่เรียงลำดับถูกคูณด้วยสิบล้าน รายการจะจัดเก็บการอ้างอิงถึงสิบล้านรายการสำหรับแต่ละรายการของ "a" ถึง "e" การอ้างอิงแต่ละรายการต้องใช้แปดไบต์ในคอนเทนเนอร์ที่เรียงลำดับ มันค่อนข้างยากที่จะเอาชนะเพราะมันเป็นราคาของตัวชี้ไปยังแต่ละวัตถุ นอกจากนี้ยังมีค่าใช้จ่ายน้อยกว่าการใช้งานไบนารีทรีทั่วไปถึง 66% (เช่น Red-Black Tree, AVL-Tree, AA-Tree, Splay-Tree, Treap ฯลฯ ) ซึ่งทุกโหนดจะต้องเก็บตัวชี้สองตัวไปยังโหนดลูกด้วย

Sorted Containers นำงานทั้งหมดออกจากคอลเลกชันที่เรียงลำดับของ Python ทำให้การปรับใช้และการใช้งาน Python ของคุณเป็นเรื่องง่าย ไม่จำเป็นต้องติดตั้งคอมไพเลอร์ C หรือสร้างและแจกจ่ายส่วนขยายที่กำหนดเองล่วงหน้า ประสิทธิภาพเป็นคุณลักษณะและการทดสอบมีความครอบคลุม 100% พร้อมการทดสอบหน่วยและชั่วโมงแห่งความเครียด

ข้อความรับรอง

Alex Martelli สมาชิกของมูลนิธิซอฟต์แวร์ Python

"สิ่งดีๆ! ... ฉันชอบแนวคิดการใช้งานที่เรียบง่ายและมีประสิทธิภาพในการแบ่งคอนเทนเนอร์ที่จัดเรียงแล้วออกเป็น "ส่วน" ที่เล็กลงเพื่อหลีกเลี่ยงค่าใช้จ่ายในการแทรก O(N)

Jeff Knupp ผู้แต่ง Writing Idiomatic Python และ Python Trainer

"ส่วนสุดท้ายนั้น "เร็วเท่ากับส่วนขยาย C" เป็นเรื่องยากที่จะเชื่อ ฉันจำเป็นต้องมีการเปรียบเทียบประสิทธิภาพบางอย่างจึงจะมั่นใจได้ว่านี่เป็นเรื่องจริง ผู้เขียนรวมสิ่งนี้ไว้ในเอกสารด้วย มันคือเรื่องจริง"

เควิน ซามูเอล เทรนเนอร์ Python และ Django

ฉันค่อนข้างประหลาดใจ ไม่ใช่แค่คุณภาพของโค้ดเท่านั้น (สามารถอ่านได้อย่างไม่น่าเชื่อและมีความคิดเห็นมากกว่าโค้ด ว้าว) แต่ยังรวมถึงปริมาณงานจริงที่คุณทำกับสิ่งที่ ไม่ใช่ โค้ด เช่น เอกสารประกอบ การเปรียบเทียบ คำอธิบายการใช้งาน แม้แต่บันทึกคอมไพล์ก็ยังสะอาดและการทดสอบหน่วยก็หมดลงใน Python 2 และ 3

Mark Summerfield คำวิงวอนสั้น ๆ สำหรับ Python Sorted Collections

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

Sorted Containers ใช้ในโครงการโอเพ่นซอร์สยอดนิยม เช่น: Zipline ซึ่งเป็นไลบรารีการซื้อขายแบบอัลกอริทึมจาก Quantopian; Angr ซึ่งเป็นแพลตฟอร์มการวิเคราะห์แบบไบนารีจาก UC Santa Barbara; Trio ซึ่งเป็นไลบรารี I/O แบบอะซิงก์ และ Dask Distributed ซึ่งเป็นไลบรารีการคำนวณแบบกระจายที่รองรับโดย Continuum Analytics

คุณสมบัติ

• เพียวหลาม
• เอกสารครบถ้วน
• การเปรียบเทียบเกณฑ์มาตรฐาน (ทางเลือก รันไทม์ ปัจจัยโหลด)
• ครอบคลุมการทดสอบ 100%
• ชั่วโมงแห่งการทดสอบความเครียด
• ประสิทธิภาพมีความสำคัญ (มักจะเร็วกว่าการใช้งาน C)
• API ที่เข้ากันได้ (เกือบจะเหมือนกับโมดูล blist และ bintrees รุ่นเก่า)
• มีคุณสมบัติหลากหลาย (เช่น รับคีย์ที่ใหญ่ที่สุดห้าคีย์ในคำสั่งที่เรียงลำดับ: d.keys()[-5:])
• การออกแบบเชิงปฏิบัติ (เช่น SortedSet เป็นชุด Python ที่มีดัชนี SortedList)
• พัฒนาบน Python 3.10
• ทดสอบด้วย CPython 3.7, 3.8, 3.9, 3.10, 3.11, 3.12 และ PyPy3
• ทดสอบบน Linux, Mac OSX และ Windows

เริ่มต้นอย่างรวดเร็ว

การติดตั้ง Sorted Containers นั้นง่ายดายด้วย pip:

 $ pip ติดตั้งคอนเทนเนอร์เรียงลำดับ

คุณสามารถเข้าถึงเอกสารในล่ามด้วยฟังก์ชันช่วยเหลือในตัวของ Python วิธีใช้นี้ใช้ได้กับโมดูล คลาส และวิธีการใน Sorted Containers

 > >> import sortedcontainers
> >> help ( sortedcontainers )
> >> from sortedcontainers import SortedDict
> >> help ( SortedDict )
> >> help ( SortedDict . popitem )

เอกสารประกอบ

เอกสารฉบับสมบูรณ์สำหรับ Sorted Containers มีอยู่ที่ http://www.grantjenks.com/docs/sortedcontainers/

คู่มือการใช้งาน

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

• การแนะนำ
• การเปรียบเทียบประสิทธิภาพ
• การเปรียบเทียบประสิทธิภาพของปัจจัยโหลด
• การเปรียบเทียบประสิทธิภาพรันไทม์
• การเปรียบเทียบประสิทธิภาพเวิร์กโหลดจำลอง
• ประสิทธิภาพตามขนาด

คู่มือชุมชน

คู่มือชุมชนให้ข้อมูลเกี่ยวกับการพัฒนา Sorted Containers พร้อมด้วยรายละเอียดการสนับสนุน การนำไปปฏิบัติ และประวัติ

• การพัฒนาและการสนับสนุน
• รายละเอียดการดำเนินการ
• ประวัติการเผยแพร่

เอกสาร API

เอกสารประกอบ API ให้ข้อมูลเกี่ยวกับฟังก์ชัน คลาส และโมดูลเฉพาะในแพ็คเกจ Sorted Containers

• รายการที่เรียงลำดับ
• เรียงตามคำบอก
• ชุดเรียง

พูดคุย

• Python เรียงลำดับคอลเลกชัน | พูดคุย PyCon 2016
• SF Python Holiday Party 2015 ไลท์นิ่งทอล์ค
• DjangoCon 2015 ไลท์นิ่งทอล์ค

ทรัพยากร

• เอกสารประกอบการจัดเรียงคอนเทนเนอร์
• จัดเรียงคอนเทนเนอร์ที่ PyPI
• จัดเรียงคอนเทนเนอร์ที่ Github
• ตัวติดตามปัญหาการเรียงลำดับคอนเทนเนอร์

ใบอนุญาตการจัดเรียงคอนเทนเนอร์

ลิขสิทธิ์ 2014-2024 Grant Jenks

ได้รับอนุญาตภายใต้ Apache License เวอร์ชัน 2.0 ("ใบอนุญาต"); คุณไม่สามารถใช้ไฟล์นี้ได้เว้นแต่จะเป็นไปตามใบอนุญาต คุณสามารถขอรับสำเนาใบอนุญาตได้ที่

http://www.apache.org/licenses/LICENSE-2.0

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