[Counting Sort, Radix Sort] 計數排序, 基數排序

 Counting Sort是一種效率很高的排序方式，複雜度為$\ord{n+k}$，其中$k$是Bucket的大小，由此可知僅限於整數且數字範圍不能太大。根據觀察在很多應用中會有對物件以編號大小進行排序的行為，在這方面應該能做到很大的加速。

另外一個問題是Counting Sort雖然簡單，很多人甚至可以自己想到實作方法，但這也導致了標準的作法常常被人忽略。因此這裡就來給大家展示標準的Counting sort：

	#include <algorithm>
	#include <numeric>
	template <typename InputIter, typename OutputIter, typename BucketIter,
	typename KeyFunction>
	void counting_sort(InputIter First, InputIter Last, BucketIter BucketFirst,
	BucketIter BucketLast, OutputIter OutputFirst,
	KeyFunction Key) {
	std::fill(BucketFirst, BucketLast, 0);
	for (auto Iter = First; Iter != Last; ++Iter)
	++(*(BucketFirst + Key(*Iter)));
	std::partial_sum(BucketFirst, BucketLast, BucketFirst);
	do {
	--Last;
	*(OutputFirst + --(*(BucketFirst + Key(*Last)))) = std::move(*Last);
	} while (Last != First);
	}

view raw CountingSort.hpp hosted with ❤ by GitHub

參數的解釋如下：

• First, Last:
  和std::sort的定義一樣，需要排序的範圍，注意不一定要是random access iterator。
• BucketFirst, BucketLast:
  Counting Sort正統的實作方式會有一個正整數陣列作為Bucket，考量到各種應用所以這裡接傳Bucket的範圍進來能做的優化會比較多，必須要是random access iterator。
• OutputFirst:
  Counting Sort的output是直接將input存到另一個陣列中，因此OutputFirst指的是Output陣列的開頭，必須要是random access iteator，且要注意output的空間是足夠的。這邊將input存進output時是用std::move的方式，如果想要保留原本input的話可以將其拿掉。
• Key:
  這是一個函數，Key(x)必須要回傳一個0~(BucketLast-BucketFirst-1)的正整數作為被排序物件x的關鍵值。

有了Counting sort，Radix Sort就比較好解釋了。首先正統的Counting sort是stable sort，所以Key值相同的東西排序前後的先後順序是不變的。因此可以透過多次的Counting Sort來完成一些原本Counting Sort無法完成的事情。

以整數(int, -2147483648~2147483647)排序為例，可以先針對第十億位做為Key進行排序，接著再對第一億位做為Key、第一千萬位做為Key...直到十位數、個位數作為Key，最後再以正負號最為Key進行排序，這樣就可以完成一般範圍的整數排序。

實際上一般不會這樣用，通常是用在有多個Key值的情況，以下面的程式碼來說，可以自行執行看看花費的時間有多少：

	#include "CountingSort.hpp"
	#include <cassert>
	#include <chrono>
	#include <iostream>
	#include <random>
	#include <vector>
	using namespace std;
	int main() {
	vector<pair<int, int>> V1;
	mt19937 MT(7122);
	const int N = 10000000, A = 1000, B = 10000;
	for (int i = 0; i < N; ++i) {
	V1.emplace_back(MT() % A, MT() % B);
	}
	decltype(V1) V2 = V1;
	auto Begin = chrono::high_resolution_clock::now();
	sort(V2.begin(), V2.end());
	auto End = chrono::high_resolution_clock::now();
	cout << "std::sort: "
	<< chrono::duration_cast<chrono::milliseconds>(End - Begin).count()
	<< "ms\n";
	Begin = chrono::high_resolution_clock::now();
	decltype(V2) Tmp(V1.size());
	vector<int> Bucket(max(A, B), 0);
	counting_sort(V1.begin(), V1.end(), Bucket.begin(), Bucket.begin() + B,
	Tmp.begin(), [&](const auto &P) -> int { return P.second; });
	counting_sort(Tmp.begin(), Tmp.end(), Bucket.begin(), Bucket.begin() + A,
	V1.begin(), [&](const auto &P) -> int { return P.first; });
	End = chrono::high_resolution_clock::now();
	cout << "radix_sort: "
	<< chrono::duration_cast<chrono::milliseconds>(End - Begin).count()
	<< "ms\n";
	assert(V1 == V2);
	return 0;
	}

view raw main.cpp hosted with ❤ by GitHub

[Discretize Relabeling] 離散化器

離散化是演算法競賽常用的操作，在各種實際問題上也能看到其應用。最基本的情況，是對於n個可排序的元素，製造一個map使得它們可以和自己的名次一一對應，但通常的應用中這n個元素確定之後就不太會有增減的動作，因此可以存到vector中排序去除重複的部分，搜索的部分就用二分搜尋來取代。

	#include <algorithm>
	#include <stdexcept>
	#include <vector>
	template <typename T, typename Alloc = std::allocator<T>>
	class Discretizer : private std::vector<T, Alloc> {
	void build() {
	std::sort(std::vector<T, Alloc>::begin(), std::vector<T, Alloc>::end());
	std::vector<T, Alloc>::erase(std::unique(std::vector<T, Alloc>::begin(),
	std::vector<T, Alloc>::end()),
	std::vector<T, Alloc>::end());
	}
	public:
	using const_iterator = typename std::vector<T, Alloc>::const_iterator;
	using const_reverse_iterator =
	typename std::vector<T, Alloc>::const_reverse_iterator;
	using const_reference = typename std::vector<T, Alloc>::const_reference;
	using size_type = typename std::vector<T, Alloc>::size_type;
	Discretizer() = default;
	template <class InputIterator>
	Discretizer(InputIterator first, InputIterator last,
	const Alloc &alloc = Alloc())
	: std::vector<T, Alloc>(first, last, alloc) {
	build();
	}
	Discretizer(const typename std::vector<T, Alloc> &x)
	: std::vector<T, Alloc>(x) {
	build();
	}
	Discretizer(const typename std::vector<T, Alloc> &x, const Alloc &alloc)
	: std::vector<T, Alloc>(x, alloc) {
	build();
	}
	Discretizer(typename std::vector<T, Alloc> &&x)
	: std::vector<T, Alloc>(std::move(x)) {
	build();
	}
	Discretizer(typename std::vector<T, Alloc> &&x, const Alloc &alloc)
	: std::vector<T, Alloc>(std::move(x), alloc) {
	build();
	}
	Discretizer(std::initializer_list<T> il, const Alloc &alloc = Alloc())
	: std::vector<T, Alloc>(il, alloc) {
	build();
	}
	Discretizer(const Discretizer &x) : std::vector<T, Alloc>(x) {}
	Discretizer(Discretizer &&x) : std::vector<T, Alloc>(std::move(x)) {}
	Discretizer(Discretizer &&x, const Alloc &alloc)
	: std::vector<T, Alloc>(std::move(x), alloc) {}
	Discretizer &operator=(const Discretizer &x) {
	std::vector<T, Alloc>::operator=(x);
	return *this;
	}
	Discretizer &operator=(Discretizer &&x) {
	std::vector<T, Alloc>::operator=(std::move(x));
	return *this;
	}
	const_iterator begin() const noexcept {
	return std::vector<T, Alloc>::begin();
	}
	const_iterator end() const noexcept { return std::vector<T, Alloc>::end(); }
	const_reverse_iterator rbegin() const noexcept {
	return std::vector<T, Alloc>::rbegin();
	}
	const_reverse_iterator rend() const noexcept {
	return std::vector<T, Alloc>::rend();
	}
	size_type size() const noexcept { return std::vector<T, Alloc>::size(); }
	size_type capacity() const noexcept {
	return std::vector<T, Alloc>::capacity();
	}
	bool empty() const noexcept { return std::vector<T, Alloc>::empty(); }
	void shrink_to_fit() { std::vector<T, Alloc>::shrink_to_fit(); }
	const_reference operator[](size_type n) const {
	return std::vector<T, Alloc>::operator[](n);
	}
	const_reference at(size_type n) const { return std::vector<T, Alloc>::at(n); }
	const_reference front() const { return std::vector<T, Alloc>::front(); }
	const_reference back() const { return std::vector<T, Alloc>::back(); }
	void pop_back() { std::vector<T, Alloc>::pop_back(); }
	void clear() noexcept { std::vector<T, Alloc>::clear(); }
	void swap(Discretizer<T, Alloc> &x) { std::vector<T, Alloc>::swap(x); }
	const_iterator lower_bound(const_reference x) const {
	return std::lower_bound(begin(), end(), x);
	}
	const_iterator upper_bound(const_reference x) const {
	return std::upper_bound(begin(), end(), x);
	}
	size_type getIndex(const_reference x) const {
	auto Iter = lower_bound(x);
	if (Iter == end() || *Iter != x)
	throw std::out_of_range("value not exist.");
	return Iter - begin();
	}
	};

view raw Discretizer.h hosted with ❤ by GitHub

	#include <iostream>
	#include "Discretizer.h"
	int main() {
	std::vector<int> V{3, 1, 9, 2, 2, 7, 3, 100};
	Discretizer<int> D(std::move(V));
	for (auto e : D)
	std::cout << e << ' ';
	std::cout << '\n';
	std::cout << D.getIndex(7) << '\n';
	std::cout << D.getIndex(100) << '\n';
	std::cout << D.upper_bound(9) - D.lower_bound(2) << '\n';
	return 0;
	}

view raw main.cpp hosted with ❤ by GitHub