объем памяти: O (журнал (макс) база (мод) * мод)
Скорость: O (журнал (макс) база (мод) * n)
Я сделал сортировку по основанию, чтобы не получить вспомогательный массив. В процессе я дискортирую несколько вещей.
Невозможно сделать LSD radix sort на месте без жертвовать скоростьюПоверь мне, если я скажу, что попробую. ЭТО НЕ БУДЕТ ОБЪЯСНЯТЬ
счетная сортировка, ты можешь сделать это для на месте(с O (n) и объект / указатель ориентированный), Но это Нестабильный. это будет объяснено здесь.
мод (количество% мод) использовать idiv / div если значение (мод) не определяется во время компиляции.
Память
Алгоритм использует O ((N ~ превышение (log (max) base (mod)) +2) * mod)
это часть кода:
size_t max = get_max(arr, size);
const size_t num_count = logb_pow2(max, mod_pow2);
size_t* count_control = new size_t[1 << mod_pow2];
for (size_t i = 0; i < 1 << mod_pow2; i++)
count_control[i] = 0;
//------------------
size_t** counts = new size_t * [num_count];
for (size_t i = 0; i < num_count; i++) {
counts[i] = new size_t[1 << mod_pow2];
}
Алгоритм
Я объясню это пунктами, чтобы мне было проще:
Как видите, мы используем count_control Я использую это для двух резонансов:
- Таким образом, мы можем выполнить сортировку без счетчиков изменений, потому что мы будем использовать это как указатели
- не будет никаких дополнительных расчетов.
алгоритм рекурсивный, как быстрая сортировка, с использованием счетчиков в качестве точек поворота
я использую Нестабильный sort и я объясню, как с таблицей:
Код
Я сделал собственные get_max и log base 2, так что я могу забыть добавлять дополнительные библиотеки.
Также я сделал собственный мод, чтобы можно было выбрать объем используемой памяти на основе предыдущих расчетов. Без компилятора используйте idiv или div.
Также я сделал объектно-ориентированный и объектно-ориентированный код с указателем.
код
#pragma once
namespace leixor {
//we write the mod pow 2 to avoid idv instruccion of the compiler
static constexpr size_t modpow2(size_t& num, size_t& mod_pow2) {
return num - (num >> mod_pow2 << mod_pow2);
}
static constexpr size_t modpow2(size_t& num, size_t mod_pow2) {
return num - (num >> mod_pow2 << mod_pow2);
}
static constexpr size_t modpow2(size_t num, size_t mod_pow2) {
return num - (num >> mod_pow2 << mod_pow2);
}
//fast log in power of 2
static size_t& logb_pow2(size_t num, const size_t& base_pow2) {
size_t aux = 1;
if (base_pow2 == 0) return aux = -1;
while (0 < (num >>= base_pow2))
aux++;
return aux;
}
//------------------------obj version---------------------------
//custom get_max because i don't wanna add lib,and normaly we will use this in a custom class
template<class obj_arr>
static size_t& get_max(obj_arr*& arr, const size_t& size) {
size_t i = modpow2(size, 1), aux = arr[0].get_size_t(), aux2;
for (; i < size; i += 2) {
aux2 = arr[i].get_size_t();
aux = aux2 * (aux < aux2) + aux * (aux >= aux2);
aux2 = arr[i + 1].get_size_t();
aux = aux2 * (aux < aux2) + aux * (aux >= aux2);
}
return aux;
}
template<class obj_arr>
void countrad(
size_t depth,
obj_arr*& arr,
size_t*& count_control, size_t**& counts, size_t& mod_pow2,
size_t start, size_t finish
) {
size_t i;
static size_t move;
static obj_arr auxiliar;
depth--;
for (i = start; i < finish; i++) {
count_control[modpow2(arr[i].get_size_t() >> (depth * mod_pow2), mod_pow2)]++;
}
counts[depth][0] = start;
for (i = 1; i < 1 << mod_pow2; i++) {
counts[depth][i] = counts[depth][i - 1] + count_control[i - 1];
}
for (i = 0; i < 1 << mod_pow2; i++) {
while (count_control[i] > 0) {
auxiliar = arr[counts[depth][i] + count_control[i] - 1];
move = modpow2(auxiliar.get_size_t() >> (depth * mod_pow2), mod_pow2);
arr[counts[depth][i] + count_control[i] - 1] = arr[counts[depth][move] + count_control[move] - 1];
arr[counts[depth][move] + count_control[move] - 1] = auxiliar;
count_control[move]--;
}
}
if (depth > 0) {
start = counts[depth][(1 << mod_pow2) - 1];
countrad(depth, arr, count_control, counts, mod_pow2, start, finish);
for (i = 0; i < (1 << mod_pow2) - 1; i++) {
start = counts[depth][i];
finish = counts[depth][i + 1];
countrad(depth, arr, count_control, counts, mod_pow2, start, finish);
}
}
}
template<class obj_arr>
bool radix_sort_ftl(obj_arr* arr, size_t size, size_t mod_pow2 = 4) {
if (mod_pow2 == 0 || size < 2)
return false;
size_t max = get_max(arr, size), start = 0, finish = size;
const size_t num_count = logb_pow2(max, mod_pow2);
//we use count_control so we don't need a axiliar memory the same size as arr
size_t* count_control = new size_t[1 << mod_pow2];
for (size_t i = 0; i < 1 << mod_pow2; i++)
count_control[i] = 0;
//------------------
size_t** counts = new size_t * [num_count];
for (size_t i = 0; i < num_count; i++) {
counts[i] = new size_t[1 << mod_pow2];
}
countrad(num_count, arr, count_control, counts, mod_pow2, start, finish);
delete[] count_control;
for (size_t i = 0; i < num_count; i++)
delete[] counts[i];
delete[]counts;
return true;
}
//----------------------------pointer obj version---------------------
template<class obj_arr>
static size_t& get_max(obj_arr**& arr, const size_t& size) {
size_t i = modpow2(size, 1), aux = arr[0]->get_size_t(), aux2;
for (; i < size; i += 2) {
aux2 = arr[i]->get_size_t();
aux = aux2 * (aux < aux2) + aux * (aux >= aux2);
aux2 = arr[i + 1]->get_size_t();
aux = aux2 * (aux < aux2) + aux * (aux >= aux2);
}
return aux;
}
template<class obj_arr>
void countrad(
size_t depth,
obj_arr**& arr,
size_t*& count_control, size_t**& counts, size_t& mod_pow2,
size_t start, size_t finish
) {
size_t i;
static size_t move;
static obj_arr* auxiliar;
depth--;
for (i = start; i < finish; i++) {
count_control[modpow2(arr[i]->get_size_t() >> (depth * mod_pow2), mod_pow2)]++;
}
counts[depth][0] = start;
for (i = 1; i < 1 << mod_pow2; i++) {
counts[depth][i] = counts[depth][i - 1] + count_control[i - 1];
}
for (i = 0; i < 1 << mod_pow2; i++) {
while (count_control[i] > 0) {
auxiliar = arr[counts[depth][i] + count_control[i] - 1];
move = modpow2(auxiliar->get_size_t() >> (depth * mod_pow2), mod_pow2);
arr[counts[depth][i] + count_control[i] - 1] = arr[counts[depth][move] + count_control[move] - 1];
arr[counts[depth][move] + count_control[move] - 1] = auxiliar;
count_control[move]--;
}
}
if (depth > 0) {
start = counts[depth][(1 << mod_pow2) - 1];
countrad(depth, arr, count_control, counts, mod_pow2, start, finish);
for (i = 0; i < (1 << mod_pow2) - 1; i++) {
start = counts[depth][i];
finish = counts[depth][i + 1];
countrad(depth, arr, count_control, counts, mod_pow2, start, finish);
}
}
}
template<class obj_arr>
bool radix_sort_ftl(obj_arr** arr, size_t size, size_t mod_pow2 = 4) {
if (mod_pow2 == 0 || size < 2)
return false;
size_t max = get_max(arr, size), start = 0, finish = size;
const size_t num_count = logb_pow2(max, mod_pow2);
//we use count_control so we don't need a axiliar memory the same size as arr
size_t* count_control = new size_t[1 << mod_pow2];
for (size_t i = 0; i < 1 << mod_pow2; i++)
count_control[i] = 0;
//------------------
size_t** counts = new size_t * [num_count];
for (size_t i = 0; i < num_count; i++) {
counts[i] = new size_t[1 << mod_pow2];
}
countrad(num_count, arr, count_control, counts, mod_pow2, start, finish);
delete[] count_control;
for (size_t i = 0; i < num_count; i++)
delete[] counts[i];
delete[]counts;
return true;
}
}
Время выполнения
время выполнения — O (log (max) base (mod) * n)
таблицы в миллисекундах
Кстати, мой ЦП с 2014 года, и у меня очень ограниченная оперативная память, так что да
/*
--------------------------------------------------
----------------object oriented version-----------
--------------------------------------------------
------------------size mod of 4 ------------------
---------------------size pow 10------------------
--------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
--------------------------------------------------
max|2 |0.0076|0.0236|0.2069|2.4733|26.9838|255.068|2309.22
--------------------------------------------------
num|3 |0.0167|0.0419|0.3858|4.1228|44.7138|433.727|4314.11
--------------------------------------------------
pow|4 |0.0101|0.0432|0.4358|4.5905|42.4533|429.153|4314.23
--------------------------------------------------
|5 |0.0143|0.0713|0.6083|6.1008|62.0323|630.773|6315.29
--------------------------------------------------
2 |6 |0.0163|0.0621|0.6158|7.3441|62.1267|628.958|6304.4
--------------------------------------------------
------------------size mod of 8 ------------------
---------------------size pow 10------------------
--------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
--------------------------------------------------
max|2 |0.1094|0.0263|0.2302|2.1466|22.7497|228.865|2303.3
--------------------------------------------------
num|3 |0.0093|0.0242|0.2205|2.2055|22.8613|226.658|2314.24
--------------------------------------------------
pow|4 |0.0117|0.0447|0.5455|4.4147|43.9577|432.973|4406.73
--------------------------------------------------
|5 |0.0124|0.0445|0.4058|4.055|41.8984|430.084|4326.23
--------------------------------------------------
2 |6 |0.0117|0.0433|0.4014|4.6221|42.2156|433.02|4341.24
--------------------------------------------------
------------------size mod of 16 ------------------
---------------------size pow 10------------------
--------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
--------------------------------------------------
max|2 |0.0191|0.0243|0.2243|2.1877|23.1079|230.527|2293.82
--------------------------------------------------
num|3 |0.0093|0.0238|0.214|2.1241|22.3461|235.777|2295.13
--------------------------------------------------
pow|4 |0.0086|0.0272|0.2134|2.224|23.807|228.782|2297.63
--------------------------------------------------
|5 |0.0145|0.0466|0.473|4.7459|43.1028|430.736|4299.26
--------------------------------------------------
2 |6 |0.0215|0.0464|0.4031|4.2045|41.8412|429.463|4291.11
--------------------------------------------------
------------------size mod of 32 ------------------
---------------------size pow 10------------------
--------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
--------------------------------------------------
max|2 |0.0102|0.0281|0.2348|2.2269|23.0951|233.078|2282.3
--------------------------------------------------
num|3 |0.0195|0.0281|0.2142|2.2431|22.5763|231.902|2284.49
--------------------------------------------------
pow|4 |0.0134|0.0274|0.2268|2.2565|22.737|231.406|2293.99
--------------------------------------------------
|5 |0.0147|0.0282|0.343|2.1646|24.4202|236.879|2325.05
--------------------------------------------------
2 |6 |0.0325|0.0547|0.4244|4.1533|43.6177|433.502|4326.64
--------------------------------------------------
--------------------------------------------------
----------------pointer oriented version-----------
--------------------------------------------------
------------------size mod of 4 ------------------
---------------------size pow 10------------------
--------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
--------------------------------------------------
max|2 |0.0056|0.0165|0.1427|1.507|17.7379|182.47|1823.31
--------------------------------------------------
num|3 |0.0092|0.03|0.2664|2.832|32.4554|348.994|3535.21
--------------------------------------------------
pow|4 |0.009|0.0288|0.2794|2.6144|35.1367|401.047|4058.5
--------------------------------------------------
|5 |0.012|0.0447|0.4567|3.8103|49.5403|607.592|6154.31
--------------------------------------------------
2 |6 |0.0125|0.0424|0.3702|4.8526|51.0433|668.851|6713.33
--------------------------------------------------
------------------size mod of 8 ------------------
---------------------size pow 10------------------
--------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
--------------------------------------------------
max|2 |0.0066|0.0186|0.1465|1.5798|17.796|194.092|1815.05
--------------------------------------------------
num|3 |0.017|0.0174|0.1431|1.5255|16.8148|181.812|1834.28
--------------------------------------------------
pow|4 |0.0107|0.0289|0.2762|3.2135|36.3079|360.955|3615.19
--------------------------------------------------
|5 |0.01|0.0303|0.2602|2.8911|35.5301|412.652|4225.77
--------------------------------------------------
2 |6 |0.019|0.0304|0.2881|3.3176|42.6521|459.499|4506.64
--------------------------------------------------
------------------size mod of 16 ------------------
---------------------size pow 10------------------
--------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
--------------------------------------------------
max|2 |0.0084|0.0174|0.1481|1.5799|17.17|179.65|1811.61
--------------------------------------------------
num|3 |0.0106|0.0169|0.1484|1.498|18.9011|184.272|1828.91
--------------------------------------------------
pow|4 |0.0094|0.0169|0.1459|1.5219|22.7538|206.602|2083.07
--------------------------------------------------
|5 |0.0132|0.0354|0.2809|2.8347|34.8864|395.352|3955.96
--------------------------------------------------
2 |6 |0.0188|0.0334|0.2755|2.9177|33.8708|418.193|4198.72
--------------------------------------------------
------------------size mod of 32 ------------------
---------------------size pow 10------------------
--------------------------------------------------
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
--------------------------------------------------
max|2 |0.0084|0.0189|0.149|1.9447|18.7979|180.437|1806.58
--------------------------------------------------
num|3 |0.0093|0.0166|0.5307|1.4293|19.0638|182.021|1846.18
--------------------------------------------------
pow|4 |0.0124|0.0191|0.1559|1.4994|19.8116|210.089|2111.82
--------------------------------------------------
|5 |0.0092|0.0179|0.1669|1.5301|20.5126|231.144|2303.58
--------------------------------------------------
2 |6 |0.0304|0.1304|0.3452|2.7494|36.1319|398.604|4132.56
--------------------------------------------------
*/
Код времени выполнения
#include "radix_sort_ftl.h"
#include <stdlib.h> /* srand, rand */
#include <time.h>
#include <iostream>
#include <chrono>
#include<string>
#include <array>
#include <math.h>
class data
{
public:
data() {};
size_t& get_size_t() { return m; };
void operator = (data& T) { m = T.m; };
size_t m;
};
void object_version(const size_t pow10,const size_t pow2,const size_t mod_pow2) {
size_t size = pow(10,pow10);
data* arr = new data[size];
size_t mod = 1 << (2+pow2);
for (size_t i = 0; i < size; i++) {
arr[i].m = rand() % mod;
}
auto started = std::chrono::high_resolution_clock::now();
leixor::radix_sort_ftl(arr, size,mod_pow2);
auto done = std::chrono::high_resolution_clock::now();
std::cout<<"|" << float(std::chrono::duration_cast<std::chrono::nanoseconds>(done - started).count()) / float(1000000);
delete[] arr;
};
void pointer_object_version(const size_t pow10, const size_t pow2, const size_t mod_pow2) {
size_t size = pow(10, pow10);
data** arr = new data*[size];
size_t mod = 1 << (2 + pow2);
for (size_t i = 0; i < size; i++) {
arr[i] = new data();
arr[i]->m = rand() % mod;
}
auto started = std::chrono::high_resolution_clock::now();
leixor::radix_sort_ftl(arr, size, mod_pow2);
auto done = std::chrono::high_resolution_clock::now();
std::cout << "|" << float(std::chrono::duration_cast<std::chrono::nanoseconds>(done - started).count()) / float(1000000);
for (size_t i = 0; i < size; i++) {
delete arr[i];
}
delete[] arr;
};
int main() {
srand(time(NULL));
std::cout <<
"n --------------------------------------------------"<<
"n ----------------object oriented version-----------"<<
"n --------------------------------------------------nn";
std::array<std::string, 5> alfa = { "nmax|2 ","nnum|3 ","npow|4 ","n |5 ","n2 |6 " };
for (size_t mod_pow2 = 2; mod_pow2 < 6; mod_pow2++){
std::cout <<
"n ------------------size mod of "<< size_t(1<<mod_pow2)<<" ------------------";
std::cout <<
"n ---------------------size pow 10------------------" <<
"n --------------------------------------------------" <<
"n | 1 | 2 | 3 | 4 | 5 | 6 | 7 |";
for (size_t z = 0; z < 5; z++) {
std::cout << "n --------------------------------------------------"<<
alfa[z];
for (size_t i = 1; i < 8; i++){
object_version(i,z,mod_pow2);
}
}
std::cout << "n --------------------------------------------------n";
}
std::cout <<
"n --------------------------------------------------" <<
"n ----------------pointer oriented version-----------" <<
"n --------------------------------------------------nn";
for (size_t mod_pow2 = 2; mod_pow2 < 6; mod_pow2++) {
std::cout <<
"n ------------------size mod of " << size_t(1 << mod_pow2) << " ------------------";
std::cout <<
"n ---------------------size pow 10------------------" <<
"n --------------------------------------------------" <<
"n | 1 | 2 | 3 | 4 | 5 | 6 | 7 |";
for (size_t z = 0; z < 5; z++) {
std::cout << "n --------------------------------------------------" <<
alfa[z];
for (size_t i = 1; i < 8; i++) {
pointer_object_version(i, z, mod_pow2);
}
}
std::cout << "n --------------------------------------------------n";
}
}
Так скажи мне, как это выглядит?