64 bit キーの安定基数ソート

components/radix_sort.hpp · GitHub で見る

共通ページ

#include "lib/components/radix_sort.hpp"
#include <cassert>
#include <cstdint>
#include <vector>

int main() {
	struct Item { std::uint64_t key; int id; };
	std::vector<Item> values = { {5, 0}, {1, 1}, {5, 2} };
	stable_radix_sort(values, [](const Item &item) { return item.key; });
	assert(values[0].id == 1 && values[1].id == 0 && values[2].id == 2);
}

操作	内容・返り値	計算量
stable_radix_sort(values,key)	vector<T> を key(const T&) の昇順に並べ替え。同じキーでは元の順序を保つ	\(O(N)\)
stable_radix_sort<Bits>(values,key)	1 回に分配する bit 数を指定。1 <= Bits <= 16	\(O(N+2^{Bits})\)

キーは64 bit以下の符号なし整数にしてください。要素はデフォルト構築・ムーブ構築・ムーブ代入が必要です。コピーできない要素も利用できます。キーの関数は要素を変更せず、呼び出すたびに同じ値を返すものを使ってください。

補助配列との入れ替えにより、元の要素への参照・ポインタ・イテレータは無効になる場合があります。

既定では 8 bit ずつの安定な分配を行います。stable_radix_sort<11>(values,key) のように指定すると、分配の回数を減らせます。全要素で共通の部分は処理を省き、既に昇順なら補助配列を確保しません。256要素未満では std::stable_sort を使います。

要素数を \(N\) として、時間は \(O(N)\)、追加空間は \(O(N)\) です。キーの計算・要素の構築・移動は \(O(1)\) とします。空の場合にも定数時間かかります。

検証コード

• test/auxiliary_tree.test.cpp
• test/compressed_lazy_segtree_large.test.cpp
• test/dynamic_convex_hull.test.cpp
• test/geometry_argument_sort.test.cpp
• test/geometry_circle_line.test.cpp
• test/geometry_circle_polygon.test.cpp
• test/geometry_closest_pair.test.cpp
• test/geometry_closest_pair.test.cpp
• test/geometry_convex_cut.test.cpp
• test/geometry_convex_hull.test.cpp
• test/geometry_convex_hull.test.cpp
• test/geometry_furthest_pair.test.cpp
• test/geometry_furthest_pair.test.cpp
• test/geometry_polygon_contains.test.cpp
• test/geometry_projection.test.cpp
• test/geometry_segment_distance.test.cpp
• test/li_chao_tree_line.test.cpp
• test/li_chao_tree_segment.test.cpp
• test/minimum_spanning_tree.test.cpp
• test/mo_inversions.test.cpp
• test/offline_dynamic_connectivity.test.cpp
• test/offline_range_sum.test.cpp
• test/offline_rectangle_sum.test.cpp
• test/ordered_set.test.cpp
• test/parallel_binary_search.test.cpp
• test/predecessor_set_priority_queue.test.cpp
• test/top_k_sum.test.cpp
• test/weighted_wavelet_matrix_rectangle.test.cpp

コード

#ifndef RADIX_SORT_HPP
#define RADIX_SORT_HPP

#include <algorithm>
#include <array>
#include <cstddef>
#include <cstdint>
#include <type_traits>
#include <utility>
#include <vector>

template <int Bits, class T, class Key>
void stable_radix_sort(std::vector<T> &values, Key &&key) {
	static_assert(1 <= Bits && Bits <= 16);
	constexpr unsigned buckets = 1U << Bits, mask = buckets - 1;
	using K = std::remove_cvref_t<decltype(key(std::declval<const T &>()))>;
	static_assert(std::is_integral_v<K> && std::is_unsigned_v<K> && sizeof(K) <= sizeof(std::uint64_t));
	if (values.size() < 2) return;
	if (values.size() < 256) {
		std::stable_sort(values.begin(), values.end(), [&](const T &a, const T &b) { return key(a) < key(b); });
		return;
	}
	std::uint64_t first = key(values.front()), previous = first, varying = 0;
	bool sorted = true;
	for (std::size_t i = 1; i < values.size(); ++i) {
		std::uint64_t current = key(values[i]);
		varying |= first ^ current;
		sorted &= previous <= current;
		previous = current;
	}
	if (sorted) return;
	std::vector<T> scratch(values.size());
	using Counts = std::conditional_t<(Bits <= 11), std::array<std::size_t, buckets>, std::vector<std::size_t>>;
	Counts count = [] {
		if constexpr (Bits <= 11) return Counts{};
		else return Counts(buckets);
	}();
	for (int shift = 0; shift < 64; shift += Bits) {
		if (!((varying >> shift) & mask)) continue;
		std::fill(count.begin(), count.end(), 0);
		for (const auto &value : values) ++count[(static_cast<std::uint64_t>(key(value)) >> shift) & mask];
		std::size_t sum = 0;
		for (auto &x : count) {
			auto n = x;
			x = sum, sum += n;
		}
		for (auto &&value : values) scratch[count[(static_cast<std::uint64_t>(key(value)) >> shift) & mask]++] = std::move(value);
		values.swap(scratch);
	}
}

template <class T, class Key>
void stable_radix_sort(std::vector<T> &values, Key key) {
	stable_radix_sort<8>(values, std::move(key));
}

namespace radix_sort_detail {
template <int Bits = 8, class T, class Key>
void sort_by_key(std::vector<T> &values, Key key) {
	using K = std::remove_cvref_t<decltype(key(std::declval<const T &>()))>;
	if constexpr (std::is_integral_v<K> && !std::is_same_v<K, bool> && sizeof(K) <= 8 && std::is_default_constructible_v<T>) {
		using U = std::make_unsigned_t<K>;
		constexpr U sign = std::is_signed_v<K> ? U(1) << (sizeof(K) * 8 - 1) : U(0);
		stable_radix_sort<Bits>(values, [&](const T &value) { return U(U(key(value)) ^ sign); });
	} else std::sort(values.begin(), values.end(), [&](const T &a, const T &b) { return key(a) < key(b); });
}
}

#endif

Back to top page