cpp sort
1.16.0 — Taxonomics
คงจะดีไม่น้อยหากวิธีการเรียงลำดับเพียงหนึ่งหรือสองวิธีจะครอบงำวิธีอื่นๆ ทั้งหมด โดยไม่คำนึงถึงแอปพลิเคชันหรือคอมพิวเตอร์ที่ใช้งานอยู่ แต่ในความเป็นจริง แต่ละวิธีก็มีข้อดีเฉพาะของตัวเอง [...] ดังนั้นเราจึงพบว่าอัลกอริธึมเกือบทั้งหมดสมควรได้รับการจดจำ เนื่องจากมีแอปพลิเคชั่นบางตัวที่พวกมันกลายเป็นสิ่งที่ดีที่สุด — Donald Knuth ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์ เล่มที่ 3
cpp-sort เป็นไลบรารีการเรียงลำดับเฉพาะส่วนหัว C ++ 14 ทั่วไป มันหมุนรอบอินเทอร์เฟซการเรียงลำดับหลักเดียวและมีเครื่องมือขนาดเล็กหลายอย่างในการเลือกและ/หรือออกแบบอัลกอริธึมการเรียงลำดับ การใช้คุณสมบัติการเรียงลำดับขั้นพื้นฐานควรเป็นเรื่องเล็กน้อยเพียงพอ:
# include < array >
# include < iostream >
# include < cpp-sort/sorters/smooth_sorter.h >
int main ()
{
std::array< int , 5 > arr = { 5 , 8 , 3 , 2 , 9 };
cppsort::smooth_sort (arr);
// prints 2 3 5 8 9
for ( int val: arr) {
std::cout << val << ' ' ;
}
}cpp-sort มีฟีเจอร์ที่เกี่ยวข้องกับการเรียงลำดับครบชุด ต่อไปนี้เป็นองค์ประกอบหลักของห้องสมุด:
นี่คือตัวอย่างที่สมบูรณ์ยิ่งขึ้นของสิ่งที่สามารถทำได้ด้วยห้องสมุด:
# include < algorithm >
# include < cassert >
# include < forward_list >
# include < functional >
# include < vector >
# include < cpp-sort/adapters.h >
# include < cpp-sort/sorters.h >
int main ()
{
struct wrapper { int value; };
std::forward_list<wrapper> li = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
std::vector<wrapper> vec = { { 5 }, { 8 }, { 3 }, { 2 }, { 9 } };
// When used, this sorter will use a pattern-defeating quicksort
// to sort random-access collections, and a mergesort otherwise
cppsort::hybrid_adapter<
cppsort::pdq_sorter,
cppsort::merge_sorter
> sorter;
// Sort li and vec in reverse order using their value member
sorter (li, std::greater<>{}, &wrapper::value);
sorter (vec, std::greater<>{}, &wrapper::value);
assert ( std::equal (
li. begin (), li. end (),
vec. begin (), vec. end (),
[]( const auto & lhs, const auto & rhs) { return lhs. value == rhs. value ; }
));
}แม้ว่าฟังก์ชันการเรียงลำดับจะถูกใช้โดยไม่มีฟีเจอร์พิเศษ แต่ก็ยังให้การรับประกันที่น่าสนใจอยู่บ้าง (แนวคิดที่มักนำมาจาก Ranges TS):
iter_swap และ iter_moveoperator()คุณสามารถอ่านเพิ่มเติมเกี่ยวกับเครื่องมือที่มีอยู่ทั้งหมด และค้นหาบทช่วยสอนเกี่ยวกับการใช้และการขยายการ เรียงลำดับ cpp ในวิกิ
กราฟต่อไปนี้สร้างขึ้นด้วยสคริปต์ที่พบในไดเร็กทอรีการวัดประสิทธิภาพ โดยจะแสดงเวลาที่ต้องใช้สำหรับ heap_sort ในการจัดเรียงองค์ประกอบหนึ่งล้านองค์ประกอบโดยไม่ต้องมีการปรับเปลี่ยน จากนั้นเมื่อมีการปรับด้วย drop_merge_adapter หรือ split_adapter
ดังที่เห็นข้างต้น การล้อม heap_sort ด้วยอะแด็ปเตอร์ตัวใดตัวหนึ่งทำให้ สามารถปรับให้เข้า กับจำนวนการกลับรายการในลักษณะที่ไม่เป็นการรบกวน อัลกอริธึมที่ใช้ในการปรับใช้มีข้อดีและข้อเสียที่แตกต่างกัน ขึ้นอยู่กับคุณที่จะใช้อย่างใดอย่างหนึ่ง
เกณฑ์มาตรฐานนี้มีไว้เพื่อแสดงความเป็นไปได้ที่ห้องสมุดนำเสนอเป็นส่วนใหญ่ คุณสามารถค้นหาเกณฑ์มาตรฐานที่มีความคิดเห็นเพิ่มเติมได้ในหน้าวิกิเฉพาะ
cpp-sort ต้องการการสนับสนุน C ++ 14 และควรทำงานร่วมกับคอมไพเลอร์ต่อไปนี้:
/permissive- คุณสมบัติบางอย่างไม่พร้อมใช้งานคอมไพเลอร์ที่ระบุไว้ข้างต้นคือตัวที่ใช้โดยไปป์ไลน์ CI และไลบรารียังได้รับการทดสอบกับคอมไพเลอร์เวอร์ชันล่าสุดเป็นประจำอีกด้วย เวอร์ชันคอมไพเลอร์อื่นๆ ทั้งหมดที่อยู่ระหว่างนั้นยังไม่ผ่านการทดสอบ แต่ก็ควรใช้งานได้เช่นกัน อย่าลังเลที่จะเปิดประเด็นหากไม่เป็นเช่นนั้น
คุณลักษณะในไลบรารีอาจแตกต่างกันไปขึ้นอยู่กับเวอร์ชัน C++ ที่ใช้และส่วนขยายของคอมไพเลอร์ที่เปิดใช้งาน การเปลี่ยนแปลงเหล่านั้นได้รับการบันทึกไว้ในวิกิ
พื้นที่เก็บข้อมูลหลักมีการรองรับเพิ่มเติมสำหรับเครื่องมือมาตรฐาน เช่น CMake หรือ Conan คุณสามารถอ่านเพิ่มเติมเกี่ยวกับสิ่งเหล่านั้นได้ในวิกิ
ฉันได้รถใหม่ ฉันแค่ต้องรวบรวมมันเข้าด้วยกัน ขโมยทีละชิ้นง่ายกว่า — จารอด คินตซ์, 3.33 ดอลลาร์
แม้ว่าบางส่วนของห้องสมุดเป็นการวิจัยดั้งเดิมและบางส่วนสอดคล้องกับการใช้งานที่กำหนดเองและค่อนข้างไร้เดียงสาของอัลกอริธึมการเรียงลำดับมาตรฐาน cpp-sort ยังนำโค้ดและแนวคิดจำนวนมากกลับมาใช้ซ้ำจากโครงการโอเพ่นซอร์ส ซึ่งมักจะได้รับการเปลี่ยนแปลงเพื่อรวมเข้ากับ ห้องสมุด. นี่คือรายการทรัพยากรภายนอกที่ใช้ในการสร้างไลบรารีนี้ ฉันหวังว่าใบอนุญาตที่แตกต่างกันจำนวนมากจะเข้ากันได้ หากไม่เป็นเช่นนั้น โปรดติดต่อฉัน (หรือส่งปัญหา) แล้วเราจะดูว่าสามารถทำอะไรได้บ้าง:
อัลกอริธึมบางตัวที่ใช้โดย insertion_sorter และ pdq_sorter มาจากการเรียงลำดับแบบรวดเร็วที่เอาชนะรูปแบบของ Orson Peters การวัดประสิทธิภาพบางส่วนก็มาจากที่นั่นเช่นกัน
อัลกอริทึมที่ใช้โดย tim_sorter มาจากการนำ Timsort ไปใช้ของ Goro Fuji (gfx)
อัลกอริธึมทั้งสามที่ใช้โดย spread_sorter มาจากโมดูล Steven Ross Boost.Sort
อัลกอริทึมที่ใช้โดย d_ary_spread_sorter มาจากโมดูล Boost.Heap ของ Tim Blechmann
อัลกอริทึมที่ใช้โดย spin_sorter มาจากอัลกอริทึมที่ใช้ใน Boost.Sort โดย ฟรานซิสโก โฮเซ่ ทาเปีย
utility::as_function , utility::static_const และอัลกอริธึมตัวช่วยที่ปรับปรุงการฉายภาพหลายตัวมาจากไลบรารี Range v3 ของ Eric Niebler แนวคิดหลายประการ เช่น ตัววนซ้ำพร็อกซี จุดการปรับแต่งและการฉายภาพ ตลอดจนฟังก์ชันยูทิลิตี้อื่นๆ บางส่วนก็มาจากไลบรารีนั้นหรือจากบทความที่เกี่ยวข้องและข้อเสนอ C++ มาตรฐาน
อัลกอริทึมที่ใช้โดย ska_sorter มาจากการนำอัลกอริทึม ska_sort ไปใช้ของ Malte Skarupke
อัลกอริธึมที่ใช้โดย drop_merge_sorter มาจากการนำ Adrian Wielgosik C++ มาใช้งานใหม่ของการเรียงลำดับแบบหล่นผสานของ Emil Ernerfeldt
อัลกอริธึมมาตรฐานที่ได้รับการปรับปรุงจำนวนมากได้รับการดัดแปลงโดยตรงจากอัลกอริธึมใน libc++ ซึ่งได้รับการปรับปรุงเพื่อรองรับทั้งการฉายภาพและตัววนซ้ำพร็อกซี
ไลบรารีภายในใช้ฟังก์ชัน inplace_merge ที่ทำงานร่วมกับตัววนซ้ำไปข้างหน้า การใช้งานใช้อัลกอริธึมผสานที่เสนอโดย Dudziński และ Dydek และดำเนินการโดย Alexander Stepanov และ Paul McJones ในหนังสือ Elements of Programming
การโอเวอร์โหลด inplace_merge สำหรับตัววนซ้ำการเข้าถึงแบบสุ่มใช้อัลกอริธึม Symmerge ที่เสนอโดย Pok-Son Kim และ Arne Kutzner ใน การผสานพื้นที่เก็บข้อมูลขั้นต่ำที่เสถียรโดยการเปรียบเทียบแบบสมมาตร เมื่อมีหน่วยความจำไม่เพียงพอที่จะดำเนินการผสานนอกสถานที่
การใช้งาน Smoothsort ของ Dijkstra ที่ใช้โดย smooth_sorter ได้รับการดัดแปลงโดยตรงจากการนำอัลกอริทึมของ Keith Schwarz ไปใช้
อัลกอริธึมที่ใช้โดย wiki_sorter ได้รับการดัดแปลงมาจาก WikiSort ของ BonzaiThePenguin
อัลกอริทึมที่ใช้โดย grail_sorter ได้รับการดัดแปลงมาจาก GrailSort ของ Mrrl
อัลกอริธึมที่ใช้โดย indirect_adapter กับตัววนซ้ำไปข้างหน้าหรือแบบสองทิศทางเป็นเวอร์ชัน indiesort ของ Matthew Bentley ที่ได้รับการแก้ไขเล็กน้อย
การใช้งานโอเวอร์โหลดการเข้าถึงแบบสุ่มของ nth_element ที่ใช้โดยอัลกอริทึมบางตัวนั้นมาจากไลบรารีการเลือกขนาดเล็กของ Danila Kutenin และใช้อัลกอริทึม AdaptiveQuickselect ของ Andrei Alexandrescu
เครือข่ายการเรียงลำดับที่ใช้โดย sorting_network_sorter ทั้งหมดมาจากรายการนี้ที่ดูแลโดย Bert Dobbelaere หน้านี้อ้างอิงถึงแหล่งที่มาของเครือข่ายการเรียงลำดับทั้งหมดที่อยู่ในรายการ
การเพิ่มประสิทธิภาพบางส่วนที่ใช้โดย sorting_network_sorter มาจากการสนทนานี้ใน StackOverflow และได้รับการสนับสนุนจากบทความ การใช้เครือข่ายการเรียงลำดับเพื่อสังเคราะห์ไลบรารีการเรียงลำดับที่ปรับให้เหมาะสมที่สุด
ชุดทดสอบนำอัลกอริธึมตัวเลขสุ่มมาใช้ใหม่ซึ่งเดิมพบในตำแหน่งต่อไปนี้:
สคริปต์ LaTeX ที่ใช้ในการวาดเครือข่ายการเรียงลำดับเป็นเวอร์ชันแก้ไขของ sortingnetwork.tex ของ kaayy ซึ่งปรับให้เป็น 0 เล็กน้อย และวาดเครือข่ายจากบนลงล่าง
เครื่องมือ CMake ที่ฝังอยู่ในโปรเจ็กต์ประกอบด้วยสคริปต์จาก RWTH-HPC/CMake-codecov และ Crascit/DownloadProject
เกณฑ์มาตรฐานบางส่วนใช้ชุดสีที่เหมาะกับคนตาบอดสี ซึ่งพัฒนาโดย Thøger Rivera-Thorsen
