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_move 사용하여 프록시 반복자를 올바르게 처리합니다.operator() 에 대한 함수 포인터로 변환될 수 있습니다.사용 가능한 모든 도구에 대한 자세한 내용을 읽을 수 있으며 위키에서 cpp-sort 사용 및 확장에 대한 몇 가지 튜토리얼을 찾을 수 있습니다.
다음 그래프는 벤치마크 디렉터리에 있는 스크립트를 사용하여 생성되었습니다. heap_sort 가 조정되지 않고 백만 개의 요소를 정렬하는 데 필요한 시간을 보여주고, drop_merge_adapter 또는 split_adapter 로 조정될 때를 보여줍니다.
위에서 볼 수 있듯이 heap_sort 어댑터 중 하나로 래핑하면 방해가 되지 않는 방식으로 반전 횟수에 적응할 수 있습니다. 이를 적용하는 데 사용되는 알고리즘에는 서로 다른 장단점이 있으며, 둘 중 하나를 사용하는 것은 사용자에게 달려 있습니다.
이 벤치마크는 대부분 라이브러리가 제공하는 가능성을 보여주기 위한 것입니다. 전용 위키 페이지에서 더 많은 주석이 달린 벤치마크를 찾을 수 있습니다.
cpp-sort에는 C++14 지원이 필요하며 다음 컴파일러에서 작동해야 합니다.
/permissive- 만 사용 가능. 몇 가지 기능을 사용할 수 없습니다.위에 나열된 컴파일러는 CI 파이프라인에서 사용되는 컴파일러이며 라이브러리도 정기적으로 해당 컴파일러의 최신 버전으로 테스트됩니다. 그 사이에 있는 다른 모든 컴파일러 버전은 테스트되지 않았지만 작동할 것입니다. 그렇지 않은 경우 자유롭게 문제를 열어보세요.
라이브러리의 기능은 사용된 C++ 버전과 활성화된 컴파일러 확장에 따라 다를 수 있습니다. 이러한 변경 사항은 위키에 문서화되어 있습니다.
기본 저장소에는 CMake 또는 Conan과 같은 표준 도구에 대한 추가 지원이 포함되어 있습니다. 위키에서 이에 대한 자세한 내용을 읽을 수 있습니다.
나는 새 차를 샀다. 그냥 함께 넣어야 해요. 한 조각씩 훔치는 것이 더 쉽습니다. — Jarod Kintz, $3.33
라이브러리의 일부 부분은 독창적인 연구이고 일부는 표준 정렬 알고리즘의 사용자 정의 및 다소 순진한 구현에 해당하지만 cpp-sort는 오픈 소스 프로젝트의 많은 코드와 아이디어를 재사용하며 종종 완벽하게 통합되도록 변경됩니다. 도서관. 다음은 이 라이브러리를 만드는 데 사용된 외부 리소스 목록입니다. 다양한 라이센스가 호환되기를 바랍니다. 그렇지 않은 경우 저에게 연락(또는 문제를 제출)해 주시면 이에 대해 어떤 조치를 취할 수 있는지 알아보도록 하겠습니다.
insertion_sorter 및 pdq_sorter 에서 사용되는 일부 알고리즘은 Orson Peters의 패턴 패배 퀵 정렬에서 나왔습니다. 벤치마크의 일부도 거기에서 나왔습니다.
tim_sorter 가 사용하는 알고리즘은 Goro Fuji(gfx)의 Timsort 구현에서 나온 것입니다.
spread_sorter 가 사용하는 세 가지 알고리즘은 Steven Ross Boost.Sort 모듈에서 나왔습니다.
d_ary_spread_sorter 에서 사용하는 알고리즘은 Tim Blechmann의 Boost.Heap 모듈에서 가져온 것입니다.
spin_sorter 가 사용하는 알고리즘은 Boost.Sort에 구현된 시조 알고리즘에서 비롯됩니다. 프란시스코 호세 타피아 지음.
utility::as_function , utility::static_const 및 여러 투영 강화 도우미 알고리즘은 Eric Niebler의 Range v3 라이브러리에서 제공됩니다. 프록시 반복자, 사용자 정의 지점 및 프로젝션과 같은 여러 아이디어와 몇 가지 기타 유틸리티 기능도 해당 라이브러리나 관련 기사 및 표준 C++ 제안에서 나옵니다.
ska_sorter 가 사용하는 알고리즘은 Malte Skarupke가 자신의 ska_sort 알고리즘을 구현한 것에서 비롯되었습니다.
drop_merge_sorter 에서 사용하는 알고리즘은 Emil Ernerfeldt의 드롭-병합 정렬을 Adrian Wielgosik C++로 다시 구현한 것입니다.
많은 향상된 표준 알고리즘은 libc++의 해당 알고리즘에서 직접 적용되어 프로젝션과 프록시 반복자를 모두 처리하도록 향상되었습니다.
라이브러리는 내부적으로 정방향 반복기와 함께 작동하는 inplace_merge 함수를 사용합니다. 구현에서는 Dudziński와 Dydek이 제안하고 Alexander Stepanov와 Paul McJones가 저서 Elements of 프로그래밍 에서 구현한 병합 알고리즘을 사용합니다.
무작위 액세스 반복기에 대한 inplace_merge 오버로드는 잘못된 병합을 수행하는 데 사용할 수 있는 메모리가 충분하지 않은 경우 김복선과 Arne Kutzner가 대칭 비교에 의한 안정적인 최소 저장소 병합 에서 제안한 Symmerge 알고리즘을 사용합니다.
smooth_sorter 가 사용하는 Dijkstra의 Smoothsort 구현은 Keith Schwarz의 알고리즘 구현에서 직접 적용되었습니다.
wiki_sorter 에서 사용하는 알고리즘은 BonzaiThePenguin의 WikiSort에서 채택되었습니다.
grail_sorter 가 사용하는 알고리즘은 Mrrl의 GrailSort에서 채택되었습니다.
순방향 또는 양방향 반복자와 함께 indirect_adapter 가 사용하는 알고리즘은 Matthew Bentley의 indiesort를 약간 수정한 버전입니다.
일부 알고리즘에서 사용되는 nth_element 의 무작위 액세스 오버로드 구현은 Danila Kutenin의 miniselect 라이브러리에서 왔으며 Andrei Alexandrescu의 AdaptiveQuickselect 알고리즘을 사용합니다.
sorting_network_sorter 에서 사용하는 정렬 네트워크는 모두 Bert Dobbelaere가 관리하는 이 목록에서 나옵니다. 이 페이지에는 나열된 모든 정렬 네트워크의 소스에 대한 참조가 있습니다.
sorting_network_sorter 가 사용하는 최적화 중 일부는 StackOverflow에 대한 토론에서 나온 것이며 Applying Sorting Networks to Synthesize Optimized Sorting Libraries 문서에서 뒷받침됩니다.
테스트 모음은 원래 다음 위치에서 발견된 난수 알고리즘을 다시 구현합니다.
정렬 네트워크를 그리는 데 사용되는 LaTeX 스크립트는 kaayy의 sortingnetwork.tex 의 수정된 버전으로, 0 기반으로 약간 조정되어 위에서 아래로 네트워크를 그립니다.
프로젝트에 포함된 CMake 도구에는 RWTH-HPC/CMake-codecov 및 Crascit/DownloadProject의 스크립트가 포함되어 있습니다.
일부 벤치마크에서는 Thøger Rivera-Thorsen이 개발한 색맹 친화적인 팔레트를 사용합니다.
