Сортировка MSD Radix на месте в c ++, объектно-указательная ориентация

объем памяти: 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 Я использую это для двух резонансов:

    1. Таким образом, мы можем выполнить сортировку без счетчиков изменений, потому что мы будем использовать это как указатели
    2. не будет никаких дополнительных расчетов.
  • алгоритм рекурсивный, как быстрая сортировка, с использованием счетчиков в качестве точек поворота

  • я использую Нестабильный 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";
    }

}

Так скажи мне, как это выглядит?

0

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *