IPB

 
>

Курилка программистов

, Флуд на около программерские темы

 
 NanoBot-AMK
сообщение 17.05.2019, 17:25
Сообщение #281


Почти Игроман
*********

Группа: Участник
Сообщений: 629
Регистрация: 10.11.2015
Пользователь №: 22739



Что быстрей, ассемблер или компилятор С/С++? Вопрос не такой однозначный!
TestSort.cpp
Код
/*=============================================================
        Тест сортировок v1.01
radixsort
radixsortmsd

(с) Intro        27.04.2019, 23:11        7.05.2019, 23:54
===============================================================*/
/* #include <stdio.h>
#include <stdlib.h>
#include <time.h> */
#include <cstdio>
#include <iostream>
#include <vector>
#include <string>
#include <ctime>
#include <algorithm>
#include <stack>
#include <cassert>
#include <queue>
#include <map>
#include <set>
#include <iterator>
#include <bitset>
#include <intrin.h>
using namespace std;

#define            TYPESORT        1
#define            _TimerRDTSC_    1

#define            byte        unsigned char
#define            uint64        unsigned long long
#define            int64        long long

uint64            m_startTicks;
double            m_fTimeTicks;

const static char*    name_sorts[] = {
    "radixsort",        //0
    "radixsortmsd",        //1
    "radixsort1",        //2
    "radixsortmsd1",    //3
    "bubblesort",        //4
    "shakersort",        //5
    "combsort",            //6
    "insertionsort",    //7
    "shellsort",        //8
    "gnomesort",        //9
    "selectionsort",    //10
    "quicksort",        //11
    "quickinssort",        //12
    "mergesort",        //13
    "mergeinssort",        //14
    "newbucketsort",    //15
    "bitonicsort",        //16
    "std::sort",        //17
    "timsort",            //18
};

inline    void     swap(int& p0, int& p1)
{
    int    tmp = p0;
    p0 = p1; p1 = tmp;
}

inline    void     swap(int*& p0, int*& p1)
{
    int*    tmp = p0;
    p0 = p1; p1 = tmp;
}

inline    int        max(int p0, int p1)
{
    return p0>p1 ? p0 : p1;
}

inline    int        min(int p0, int p1)
{
    return p0<p1 ? p0 : p1;
}

__inline    uint64    RDTSC()
{
    return __rdtsc();
}

double    GetFrequencyCPU()
{
    clock_t                tm0, tm1;
    unsigned long long    ticks;
    tm0 = clock();
    //Определим начало интервала
    while ((tm1 = clock()) == tm0){}
    ticks = RDTSC();
    tm0 = tm1;
    //Определим конец интервала
    while ((tm1 = clock()) < tm0 + 250){}
    //вычислим частоту
    ticks = RDTSC() - ticks;
    return (double)ticks / (double(tm1 - tm0)*(1.0 / CLOCKS_PER_SEC));
}

//original
int digit(int n, int k, int N, int M)
{
    return (n >> (N * k) & (M - 1));
}
void _radixsort(int* pBegin, int* pEnd, int N) {
    int k = (32 + N - 1) / N;
    int M = 1 << N;
    int sz = pEnd - pBegin;
    int* b = new int[sz];
    int* c = new int[M];
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < M; j++)
            c[j] = 0;
        for (int* j = pBegin; j < pEnd; j++)
            c[digit(*j, i, N, M)]++;
        for (int j = 1; j < M; j++)
            c[j] += c[j - 1];
        for (int* j = pEnd - 1; j >= pBegin; j--)
            b[--c[digit(*j, i, N, M)]] = *j;
        int cur = 0;
        for (int* j = pBegin; j < pEnd; j++)
            *j = b[cur++];
    }
    delete b;
    delete c;
}

void radixsort(int* pBegin, int* pEnd) {
    _radixsort(pBegin, pEnd, 8);
}

void _radixsortmsd(int* pBegin, int* pEnd, int N, int d, int* temp) {
    if (d == -1) return;
    /* if (pEnd - pBegin <= 32) {
        insertionsort(pBegin, pEnd);
        return;
    } */
    int M = 1 << N;
    int* cnt = new int[M + 1];
    for (int i = 0; i <= M; i++)
        cnt[i] = 0;
    int cur = 0;
    for (int* i = pBegin; i < pEnd; i++) {
        temp[cur++] = *i;
        cnt[digit(*i, d, N, M) + 1]++;
    }
    int sz = 0;
    for (int i = 1; i <= M; i++)
        if (cnt[i]) sz++;
    int* run = new int[sz];
    cur = 0;
    for (int i = 1; i <= M; i++)
        if (cnt[i]) run[cur++] = i - 1;
    for (int i = 1; i <= M; i++)
        cnt[i] += cnt[i - 1];
    cur = 0;
    for (int *i = pBegin; i < pEnd; i++) {
        int ind = digit(temp[cur], d, N, M);
        *(pBegin + cnt[ind]) = temp[cur];
        cur++;
        cnt[ind]++;
    }
    for (int i = 0; i < sz; i++) {
        int r = run[i];
        if (r != 0)
            _radixsortmsd(pBegin + cnt[r - 1], pBegin + cnt[r], N, d - 1, temp);
        else
            _radixsortmsd(pBegin, pBegin + cnt[r], N, d - 1, temp);
    }
    delete run;
    delete cnt;
}
void radixsortmsd(int* pBegin, int* pEnd) {
    int* temp = new int[pEnd - pBegin];
    _radixsortmsd(pBegin, pEnd, 8, 3, temp);
    delete temp;
}
//моя версия
__inline    int Number(int* n, int k)
{
    return (((byte*)n)[k]);
}
void _radixsort1(int* pBegin, int* pEnd, int* tmp)
{
    const int    k = sizeof(*pBegin), M = 256;
    int     size_arr = pEnd - pBegin;
    int64    abc[M];
    for (int i = 0; i < k; ++i){
        for (int j = 0; j < M; ++j)    //256
            abc[j] = 0;
        int *j;
        for (j = pBegin; j < pEnd-2; j+=3){    //разворот цикла на 3
            int    a=Number(j+0, i);
            int    b=Number(j+1, i);
            int    c=Number(j+2, i);
            ++abc[a]; ++abc[b]; ++abc[c];
        }
        for (;j < pEnd; ++j)                //выполняем хвост цикла
            ++abc[Number(j, i)];
        for (int n = 0; n < M-1; ++n)    //256-1
            abc[n+1] += abc[n];
        for (j = pEnd-1; j >= pBegin+2; j-=3){    //разворот цикла на 3
            int    a=Number(j-0, i);
            int    b=Number(j-1, i);
            int    c=Number(j-2, i);
            tmp[--abc[a]] = *j;
            tmp[--abc[b]] = *(j-1);
            tmp[--abc[c]] = *(j-2);
        }
        for (;j >= pBegin; --j)                //выполняем хвост цикла
            tmp[--abc[Number(j, i)]] = *j;
        //копируем из tmp в pBegin
        swap(tmp, pBegin);
        pEnd = pBegin+size_arr;
    }
}

void radixsort1(int* pBegin, int* pEnd)
{
    int size_arr = pEnd - pBegin;
    if (size_arr<=512){
        int        tmp[512];
        _radixsort1(pBegin, pEnd, tmp);
    }else{
        int*    tmp = new int[size_arr];
        _radixsort1(pBegin, pEnd, tmp);
        delete tmp;
    }
}

int    num_call    = 0;
void _radixsortmsd1(int* pBegin, int* pEnd, int d, int* pTemp)
{
//    ++num_call;
    const int    M = 256;
    int        abc[M+1];
    int*    run = new int[M];
    for (int i = 0; i <= M; ++i)
        abc[i] = 0;
    for (int* i = pBegin,  *j = pTemp; i < pEnd; ++i, ++j) {
        *j = *i;                    //копируем pTemp в pBegin
        abc[Number(i, d) + 1]++;        //подсчитывает кол. букв
    }
    int sz = 0;
    for (int i = 1; i <= M; ++i){
        if (abc[i])
            run[sz++] = i-1;
        abc[i] += abc[i-1];
    }
//    for (int i = 0; i <= M; ++i)
//        abc[i] += pBegin;
    int *tmpEnd = pTemp + (pEnd-pBegin);
    for (int *tmpCur = pTemp; tmpCur < tmpEnd; ++tmpCur) {
        int i = Number(tmpCur, d);
        pBegin[abc[i]] = *tmpCur;
        abc[i]++;
    }
    if (d>0){
        for (int i = 0; i < sz; ++i) {
            int r = run[i];
            if (r)
                _radixsortmsd1(pBegin + abc[r-1], pBegin + abc[r], d - 1, pTemp);
            else
                _radixsortmsd1(pBegin, pBegin + abc[r], d - 1, pTemp);
        }
    }
    delete run;
}
void radixsortmsd1(int* pBegin, int* pEnd) {
    int* pTemp = new int[pEnd - pBegin];
    _radixsortmsd1(pBegin, pEnd, 3, pTemp);
    delete pTemp;
}

inline    int*    max_element(int* First_, int* Last_)
{
    int*    Found_ = First_;
    if ( First_ != Last_ ){
        while (++First_ != Last_){
            if (*Found_ >= *First_)
                Found_ = First_;
        }
    }
    return Found_;
}

void bubblesort(int* pBegin, int* pEnd)
{
    int sz = pEnd - pBegin;
    if (sz <= 1) return;
    bool b = true;
    while (b) {
        b = false;
        for (int* i = pBegin; i + 1 < pEnd; i++) {
            if (*i > *(i + 1)) {
                swap(*i, *(i + 1));
                b = true;
            }
        }
        pEnd--;
    }
}

void shakersort(int* pBegin, int* pEnd)
{
    int sz = pEnd - pBegin;
    if (sz <= 1) return;
    bool b = true;
    int* beg = pBegin - 1;
    int* end = pEnd - 1;
    while (b) {
        b = false;
        beg++;
        for (int* i = beg; i < end; i++) {
            if (*i > *(i + 1)) {
                swap(*i, *(i + 1));
                b = true;
            }
        }
        if (!b) break;
        end--;
        for (int* i = end; i > beg; i--) {
            if (*i < *(i - 1)) {
                swap(*i, *(i - 1));
                b = true;
            }
        }
    }
}

void combsort(int* pBegin, int* pEnd)
{
    int sz = pEnd - pBegin;
    if (sz <= 1) return;
    const double    k = 1.2473309;
    int step = sz - 1;
    while (step > 1) {
        for (int* i = pBegin; i + step < pEnd; i++) {
            if (*i > *(i + step))
                swap(*i, *(i + step));
        }
        step /= k;
    }
    bool b = true;
    while (b) {
        b = false;
        for (int* i = pBegin; i + 1 < pEnd; i++) {
            if (*i > i[1])) {
                swap(*i, i[1]);
                b = true;
            }
        }
    }
}

void insertionsort(int* pBegin, int* pEnd)
{
    for (int *i = pBegin + 1; i < pEnd; i++) {
        int* j = i;
        while (j > pBegin && *(j - 1) > *j) {
            swap(*(j - 1), *j);
            j--;
        }
    }
}

void shellsort(int* pBegin, int* pEnd)
{
    int sz = pEnd - pBegin;
    int step = sz / 2;
    while (step >= 1) {
        for (int *i = pBegin + step; i < pEnd; i++) {
            int *j = i;
            int *diff = j - step;
            while (diff >= pBegin && *diff > *j) {
                swap(*diff, *j);
                j = diff;
                diff = j - step;
            }
        }
        step /= 2;
    }
}

void gnomesort(int* pBegin, int* pEnd)
{
    int *i = pBegin;
    while (i < pEnd) {
        if (i == pBegin || *(i - 1) <= *i)
            i++;
        else
            swap(*(i - 1), *i), i--;
    }
}

void selectionsort(int* pBegin, int* pEnd)
{
    for (int *i = pBegin; i < pEnd; i++) {
        int minz = *i, *ind = i;
        for (int *j = i + 1; j < pEnd; j++) {
            if (*j < minz) minz = *j, ind = j;
        }
        swap(*i, *ind);
    }
}

void quicksort(int* pBegin, int* pEnd)
{
    if (pEnd - pBegin <= 1) return;
    int z = *(pBegin + (pEnd - pBegin) / 2);
    int* ll = pBegin, *rr = pEnd - 1;
    while (ll <= rr) {
        while (*ll < z) ll++;
        while (*rr > z) rr--;
        if (ll <= rr) {
            swap(*ll, *rr);
            ll++;
            rr--;
        }
    }
    if (pBegin < rr)
        quicksort(pBegin, rr + 1);
    if (ll < pEnd)
        quicksort(ll, pEnd);
}

void quickinssort(int* pBegin, int* pEnd)
{
    if (pEnd - pBegin <= 32){
        insertionsort(pBegin, pEnd);
        return;
    }
    int z = *(pBegin + (pEnd - pBegin) / 2);
    int* ll = pBegin, *rr = pEnd - 1;
    while (ll <= rr) {
        while (*ll < z) ll++;
        while (*rr > z) rr--;
        if (ll <= rr) {
            swap(*ll, *rr);
            ll++;
            rr--;
        }
    }
    if (pBegin < rr)
        quickinssort(pBegin, rr + 1);
    if (ll < pEnd)
        quickinssort(ll, pEnd);
}

void merge(int* l, int* m, int* r, int* temp)
{
    int *cl = l, *cr = m, cur = 0;
    while (cl < m && cr < r) {
        if (*cl < *cr)
            temp[cur++] = *cl, cl++;
        else
            temp[cur++] = *cr, cr++;
    }
    while (cl < m)
        temp[cur++] = *cl, cl++;
    while (cr < r)
        temp[cur++] = *cr, cr++;
    cur = 0;
    for (int* i = l; i < r; i++)
         *i = temp[cur++];
}
void _mergesort(int* pBegin, int* pEnd, int* temp)
{
    if (pEnd - pBegin <= 1) return;
    int *m = pBegin + (pEnd - pBegin) / 2;
    _mergesort(pBegin, m, temp);
    _mergesort(m, pEnd, temp);
    merge(pBegin, m, pEnd, temp);
}
void mergesort(int* pBegin, int* pEnd)
{
    int* temp = new int[pEnd - pBegin];
    _mergesort(pBegin, pEnd, temp);
    delete temp;
}
void _mergeinssort(int* pBegin, int* pEnd, int* temp)
{
    if (pEnd - pBegin <= 32) {
        insertionsort(pBegin, pEnd);
        return;
    }
    int *m = pBegin + (pEnd - pBegin) / 2;
    _mergeinssort(pBegin, m, temp);
    _mergeinssort(m, pEnd, temp);
    merge(pBegin, m, pEnd, temp);
}
void mergeinssort(int* pBegin, int* pEnd)
{
    int* temp = new int[pEnd - pBegin];
    _mergeinssort(pBegin, pEnd, temp);
    delete temp;
}

void _newbucketsort(int* pBegin, int* pEnd, int* temp) {
    if (pEnd - pBegin <= 1) return;
    int minz = *pBegin, maxz = *pBegin;
    bool is_sorted = true;
    for (int *i = pBegin + 1; i < pEnd; i++) {
        minz = min(minz, *i);
        maxz = max(maxz, *i);
        if (*i < *(i - 1)) is_sorted = false;
    }
    if (is_sorted) return;
    int diff = maxz - minz + 1;
    int numbuckets;
    if (pEnd - pBegin <= 1e7) numbuckets = 1500;
    else numbuckets = 3000;
    int range = (diff + numbuckets - 1) / numbuckets;
    int* cnt = new int[numbuckets + 1];
    for (int i = 0; i <= numbuckets; i++)
        cnt[i] = 0;
    int cur = 0;
    for (int* i = pBegin; i < pEnd; i++) {
        temp[cur++] = *i;
        int ind = (*i - minz) / range;
        cnt[ind + 1]++;
    }
    int sz = 0;
    for (int i = 1; i <= numbuckets; i++)
        if (cnt[i]) sz++;
    int* run = new int[sz];
    cur = 0;
    for (int i = 1; i <= numbuckets; i++)
        if (cnt[i]) run[cur++] = i - 1;
    for (int i = 1; i <= numbuckets; i++)
        cnt[i] += cnt[i - 1];
    cur = 0;
    for (int *i = pBegin; i < pEnd; i++) {
        int ind = (temp[cur] - minz) / range;
        *(pBegin + cnt[ind]) = temp[cur];
        cur++;
        cnt[ind]++;
    }
    for (int i = 0; i < sz; i++) {
        int r = run[i];
        if (r != 0)
            _newbucketsort(pBegin + cnt[r - 1], pBegin + cnt[r], temp);
        else
            _newbucketsort(pBegin, pBegin + cnt[r], temp);
    }
    delete run;
    delete cnt;
}
void newbucketsort(int* pBegin, int* pEnd)
{
    int *temp = new int[pEnd - pBegin];
    _newbucketsort(pBegin, pEnd, temp);
    delete temp;
}

void bitseqsort(int* pBegin, int* pEnd, bool inv)
{
    if (pEnd - pBegin <= 1) return;
    int *m = pBegin + (pEnd - pBegin) / 2;
    for (int *i = pBegin, *j = m; i < m && j < pEnd; i++, j++) {
        if (inv ^ (*i > *j))
            swap(*i, *j);
    }
    bitseqsort(pBegin, m, inv);
    bitseqsort(m, pEnd, inv);
}
void makebitonic(int* pBegin, int* pEnd)
{
    if (pEnd - pBegin <= 1) return;
    int *m = pBegin + (pEnd - pBegin) / 2;
    makebitonic(pBegin, m);
    bitseqsort(pBegin, m, 0);
    makebitonic(m, pEnd);
    bitseqsort(m, pEnd, 1);
}
void bitonicsort(int* pBegin, int* pEnd)
{
    int n = 1;
    int inf = *max_element(pBegin, pEnd) + 1;
    while (n < pEnd - pBegin)
        n *= 2;
    int* a = new int[n];
    int cur = 0;
    for (int *i = pBegin; i < pEnd; i++)
        a[cur++] = *i;
    while (cur < n)
        a[cur++] = inf;
    makebitonic(a, a + n);
    bitseqsort(a, a + n, 0);
    cur = 0;
    for (int *i = pBegin; i < pEnd; i++)
        *i = a[cur++];
    delete a;
}

void _timsort(int* pBegin, int* pEnd, int* temp) {
    int sz = pEnd - pBegin;
    if (sz <= 1) {
    //    insertionsort(pBegin, pEnd);
        return;
    }
    int minrun = sz, f = 0;
    while (minrun >= 64) {
        f |= minrun & 1;
        minrun >>= 1;
    }
    minrun += f;
    int* cur = pBegin;
    stack<pair<int, int*>> s;
    while (cur < pEnd){
        int* c1 = cur;
        while (c1 < pEnd - 1 && *c1 <= *(c1 + 1))
            c1++;
        int* c2 = cur;
        while (c2 < pEnd - 1 && *c2 >= *(c2 + 1))
            c2++;
        if (c1 >= c2){
            c1 = max(c1, cur + minrun - 1);
            c1 = min(c1, pEnd - 1);
            insertionsort(cur, c1 + 1);
            s.push({ c1 - cur + 1, cur });
            cur = c1 + 1;
        }else{
            c2 = max(c2, cur + minrun - 1);
            c2 = min(c2, pEnd - 1);
            reverse(cur, c2 + 1);
            insertionsort(cur, c2 + 1);
            s.push({ c2 - cur + 1, cur });
            cur = c2 + 1;
        }
        while (s.size() >= 3) {
            pair<int, int*> x = s.top();
            s.pop();
            pair<int, int*> y = s.top();
            s.pop();
            pair<int, int*> z = s.top();
            s.pop();
            if (z.first >= x.first + y.first && y.first >= x.first) {
                s.push(z);
                s.push(y);
                s.push(x);
                break;
            }else if (z.first >= x.first + y.first) {
                merge(y.second, x.second, x.second + x.first, temp);
                s.push(z);
                s.push({ x.first + y.first, y.second });
            }else {
                merge(z.second, y.second, y.second + y.first, temp);
                s.push({ z.first + y.first, z.second });
                s.push(x);
            }
        }
    }
    while (s.size() != 1) {
        pair<int, int*> x = s.top();
        s.pop();
        pair<int, int*> y = s.top();
        s.pop();
        if (x.second < y.second) swap(x, y);
        merge(y.second, x.second, x.second + x.first, temp);
        s.push({ y.first + x.first, y.second });
    }
}
void timsort(int* pBegin, int* pEnd) {
    int* temp = new int[pEnd - pBegin];
    _timsort(pBegin, pEnd, temp);
    delete temp;
}

double    Time()
{
#if (_TimerRDTSC_==0)
    return clock()*(1.0 / CLOCKS_PER_SEC);
#else
    return (RDTSC() - m_startTicks)*m_fTimeTicks;
#endif
}

bool check(int* pBegin, int* pEnd)
{
    for (int* j = pBegin; j < pEnd-1; ++j)
        if (j[0] > j[1]) return false;
    return true;
}

void fulltest(int size_arr, int type_sort)
{
    double    tm0;
    //Init
//    srand(time(0));
    m_startTicks = RDTSC();
    // Определить текущую частоту процессора.
    m_fTimeTicks = 1.0 / GetFrequencyCPU();    // длительность такта, сек
    int* TestArr = new int[size_arr];
    for (int i=0; i<size_arr; ++i){
        TestArr[i] = (rand()*RAND_MAX + rand()) /* % (int)1e4 */;
//        printf("[%04d] = %08X\n", i, TestArr[i]);
    }
//    printf("OK\n");
    //Test
    switch (type_sort){
    case 0:
        tm0 = Time();
        radixsort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 1:
        tm0 = Time();
        radixsortmsd(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 2:
        tm0 = Time();
        radixsort1(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 3:
        tm0 = Time();
        radixsortmsd1(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 4:
        tm0 = Time();
        bubblesort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 5:
        tm0 = Time();
        shakersort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 6:
        tm0 = Time();
        combsort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 7:
        tm0 = Time();
        insertionsort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 8:
        tm0 = Time();
        shellsort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 9:
        tm0 = Time();
        gnomesort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 10:
        tm0 = Time();
        selectionsort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 11:
        tm0 = Time();
        quicksort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 12:
        tm0 = Time();
        quickinssort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 13:
        tm0 = Time();
        mergesort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 14:
        tm0 = Time();
        mergeinssort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 15:
        tm0 = Time();
        newbucketsort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 16:
        tm0 = Time();
        bitonicsort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 17:
        tm0 = Time();
        sort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    case 18:
        tm0 = Time();
        timsort(TestArr, TestArr+size_arr);
        tm0 = Time()-tm0;
        break;
    default:
        printf("Unknown type of sorting: %d\n", type_sort);
        delete TestArr;
        return;
    }
//    for(int i; i<size_arr; ++i)    printf("[%04d] = %08X\n", i, TestArr[i]);
    //Print result
    if (check(TestArr, TestArr+size_arr)){
        double    tm = tm0>1e-5 ? tm0*1e3 : tm0*1e6;
        printf("TEST: [% 14s], size[% 11d], time = %.3f %s\n", name_sorts[type_sort], size_arr, tm, tm0>1e-5 ? "msec" : "mksec");
    }else
        printf("TEST: [% 14s], Incorrect!\n", name_sorts[type_sort]);
//    printf("num_call = %d\n", num_call);
    //Destroy
    delete TestArr;
}

int main(int argc, const char *argv[])
{
    if (argc!=3){
        puts("Usage: TestSort size_arr type_sort\n");
        return 0;
    }
    int    size_arr = atoi(argv[1]);
    if (size_arr<0){
        puts("Error: size_arr is negative\n");
        return 1;
    }
    fulltest(size_arr, atoi(argv[2]));
    return 0;
}

Компиляция GCC
Код
@echo off
gcc TestSort.cpp -lstdc++ -std=c++14 -Wall -O3 -march=native -g3 -s -o TestSort.exe
rem athlon-xp amdfam10
pause

Батники для теста.
Test.bat
@echo off

TestSort 10 0
TestSort 100000 0
TestSort 1000000 0
TestSort 10000000 0
REM TestSort 100000000 0

REM TestSort 10 1
REM TestSort 100000 1
REM TestSort 1000000 1
REM TestSort 10000000 1
REM TestSort 100000000 1
rem TestSort 200000000 1

TestSort 10 2
TestSort 100 2
TestSort 1000 2
TestSort 10000 2
REM TestSort 100000 2

TestSort 10 3
TestSort 100 3
TestSort 1000 3
TestSort 10000 3
REM TestSort 100000 3

TestSort 10 4
TestSort 100 4
TestSort 1000 4
TestSort 10000 4
TestSort 100000 4

TestSort 10 5
TestSort 100 5
TestSort 1000 5
TestSort 10000 5

TestSort 10 6
TestSort 100 6
TestSort 1000 6
TestSort 10000 6
TestSort 100000 6

TestSort 10 7
TestSort 100 7
TestSort 1000 7
TestSort 10000 7

TestSort 10 8
TestSort 100 8
TestSort 1000 8
TestSort 10000 8

TestSort 10 9
TestSort 100 9
TestSort 1000 9
TestSort 10000 9
TestSort 100000 9

TestSort 10 10
TestSort 100 10
TestSort 1000 10
TestSort 10000 10
TestSort 100000 10

TestSort 10 11
TestSort 100 11
TestSort 1000 11
TestSort 10000 11
TestSort 100000 11

TestSort 10 12
TestSort 100 12
TestSort 1000 12
TestSort 10000 12
TestSort 100000 12

TestSort 10 13
TestSort 100 13
TestSort 1000 13
TestSort 10000 13
TestSort 100000 13

TestSort 10 14
TestSort 100 14
TestSort 1000 14
TestSort 10000 14
TestSort 100000 14

pause

Test2.bat
Код
@echo off

rem bubblesort
TestSort 10 4
TestSort 100 4
TestSort 1000 4
TestSort 10000 4
REM TestSort 100000 4
rem shakersort
TestSort 10 5
TestSort 100 5
TestSort 1000 5
TestSort 10000 5
rem combsort
TestSort 10 6
TestSort 100 6
TestSort 1000 6
TestSort 10000 6
TestSort 100000 6
TestSort 1000000 6
TestSort 10000000 6
TestSort 100000000 6
rem insertionsort
TestSort 10 7
TestSort 64 7
TestSort 100 7
TestSort 128 7
TestSort 1000 7
TestSort 10000 7
TestSort 100000 7
rem gnomesort
TestSort 10 9
TestSort 100 9
TestSort 1000 9
TestSort 10000 9
REM TestSort 100000 9
rem selectionsort
TestSort 10 10
TestSort 100 10
TestSort 1000 10
TestSort 10000 10
REM TestSort 100000 10

pause

Test3.bat
Код
@echo off

TestSort 10 0
TestSort 1000 0
TestSort 10000 0
TestSort 100000 0
TestSort 1000000 0
TestSort 10000000 0
TestSort 100000000 0
REM TestSort 300000000 0

TestSort 10 1
TestSort 100000 1
TestSort 1000000 1
TestSort 10000000 1
TestSort 100000000 1
REM TestSort 200000000 1

TestSort 10 2
TestSort 1000 2
TestSort 10000 2
TestSort 100000 2
TestSort 1000000 2
TestSort 10000000 2
TestSort 100000000 2
REM TestSort 300000000 2

TestSort 10 3
TestSort 100000 3
TestSort 1000000 3
TestSort 10000000 3
TestSort 100000000 3
REM TestSort 200000000 3

TestSort 10 11
TestSort 100 11
TestSort 1000 11
TestSort 10000 11
TestSort 100000 11
TestSort 1000000 11
TestSort 10000000 11
TestSort 100000000 11

TestSort 10 12
TestSort 100 12
TestSort 1000 12
TestSort 10000 12
TestSort 100000 12
TestSort 1000000 12
TestSort 10000000 12
TestSort 100000000 12

TestSort 10 13
TestSort 100 13
TestSort 1000 13
TestSort 10000 13
TestSort 100000 13
TestSort 1000000 13
TestSort 10000000 13
TestSort 100000000 13

TestSort 10 14
TestSort 100 14
TestSort 1000 14
TestSort 10000 14
TestSort 100000 14
TestSort 1000000 14
TestSort 10000000 14
TestSort 100000000 14

TestSort 10 17
TestSort 100 17
TestSort 1000 17
TestSort 10000 17
TestSort 100000 17
TestSort 1000000 17
TestSort 10000000 17
TestSort 100000000 17

TestSort 10 18
TestSort 100 18
TestSort 1000 18
TestSort 10000 18
TestSort 100000 18
TestSort 1000000 18
TestSort 10000000 18
TestSort 100000000 18

pause

ЗЫ
Что хрень, я не могу зачать винрар архивы. (IMG:style_emoticons/default/z_crazy.gif)
ЗЫЫ
Ладно ассемблер всегда рулит. (IMG:style_emoticons/default/rolleyes.gif)
ЗЫЫЫ
Темы с чего началось.
https://habr.com/ru/post/448542/#first_unread
https://habr.com/ru/post/450160/#first_unread

Сообщение отредактировал NanoBot-AMK - 17.05.2019, 17:29
Перейти в начало страницы
 
 
 iOrange
сообщение 17.05.2019, 17:46
Сообщение #282


Почти Мастер
***********

Группа: Участник
Сообщений: 1079
Регистрация: 30.03.2010
Из: Planet Earth
Пользователь №: 13811



Цитата(NanoBot-AMK @ 17.05.2019, 16:29) *
я не могу зачать винрар архивы

Если таки сможете - прославитесь (IMG:style_emoticons/default/z_lol1.gif)

Цитата(NanoBot-AMK @ 17.05.2019, 16:29) *
Ладно ассемблер всегда рулит.

Так а где результаты то?

Напостили простыни какого-то стремного кода, и что?
Бремя доказательства лежит на плечах утверждающего, не слыхали?
Перейти в начало страницы
 
 
 cjayho
сообщение 17.05.2019, 22:08
Сообщение #283


Почти Мастер
***********

Группа: Участник
Сообщений: 1128
Регистрация: 08.03.2010
Из: Україна
Пользователь №: 13783



QUOTE (NanoBot-AMK @ 17.05.2019, 16:29) *
Что хрень, я не могу зачать винрар архивы. (IMG:style_emoticons/default/z_crazy.gif)


Примите синтаксический сахар (IMG:style_emoticons/default/biggrin.gif)

Сообщение отредактировал cjayho - 17.05.2019, 22:08
Перейти в начало страницы
 
 
 NanoBot-AMK
сообщение 18.05.2019, 03:42
Сообщение #284


Почти Игроман
*********

Группа: Участник
Сообщений: 629
Регистрация: 10.11.2015
Пользователь №: 22739



Вам смешно, а мне совсем не смешно. (IMG:style_emoticons/default/sad.gif) (IMG:style_emoticons/default/z_crazy.gif)
Код я показал, вот и тестируйте. Или что GCC не можете скачать. Батник запустить, это же так просто.
Ладно, не подставайте меня, я сейчас не в том состоянии чтобы шутить.
Перейти в начало страницы
 
 
 iOrange
сообщение 18.05.2019, 03:50
Сообщение #285


Почти Мастер
***********

Группа: Участник
Сообщений: 1079
Регистрация: 30.03.2010
Из: Planet Earth
Пользователь №: 13811



Цитата(NanoBot-AMK @ 18.05.2019, 02:46) *
Код я показал, вот и тестируйте

Нет, это Вы постоянно пишите голословные утверждения, соответственно Вы и должны их доказывать.

Читайте выше про "бремя доказательства..."
Перейти в начало страницы
 
 
 cjayho
сообщение 18.05.2019, 04:40
Сообщение #286


Почти Мастер
***********

Группа: Участник
Сообщений: 1128
Регистрация: 08.03.2010
Из: Україна
Пользователь №: 13783



QUOTE (NanoBot-AMK @ 18.05.2019, 02:46) *
я сейчас не в том состоянии чтобы шутить.


Харэ бухать, алкоголь убивает моск. Ато скоро начнете верить в то что максимальная крепость этилового спирта составляет 96% (IMG:style_emoticons/default/wink.gif)
Перейти в начало страницы
 
 
 NanoBot-AMK
сообщение 18.05.2019, 04:52
Сообщение #287


Почти Игроман
*********

Группа: Участник
Сообщений: 629
Регистрация: 10.11.2015
Пользователь №: 22739



Я не бухаю, я свою кошку Люску поминаю. (IMG:style_emoticons/default/sad.gif)
Код приведён, компилируешь, и тестируешь, я не собираюсь что-то доказывать.
Блин вы программисты или кто. (IMG:style_emoticons/default/kozak.gif)
Перейти в начало страницы
 
 
 cjayho
сообщение 18.05.2019, 05:00
Сообщение #288


Почти Мастер
***********

Группа: Участник
Сообщений: 1128
Регистрация: 08.03.2010
Из: Україна
Пользователь №: 13783



QUOTE (NanoBot-AMK @ 18.05.2019, 03:56) *
Я не бухаю, я свою кошку Люску поминаю. (IMG:style_emoticons/default/sad.gif)


ага, а потом будет всемирный день осьминогов, будете пить за этих очаровательных созданий? (IMG:style_emoticons/default/smile.gif)

QUOTE (NanoBot-AMK @ 18.05.2019, 03:56) *
Код приведён, компилируешь, и тестируешь, я не собираюсь что-то доказывать.
Блин вы программисты или кто. (IMG:style_emoticons/default/kozak.gif)


Я с вами в спор не вступал, потому не обязан отлавливать бетастазы вашего кода (IMG:style_emoticons/default/smile.gif) . Я чо, на бетатестера похож?
Перейти в начало страницы
 
 
 iOrange
сообщение 18.05.2019, 06:27
Сообщение #289


Почти Мастер
***********

Группа: Участник
Сообщений: 1079
Регистрация: 30.03.2010
Из: Planet Earth
Пользователь №: 13811



Цитата(NanoBot-AMK @ 18.05.2019, 03:56) *
Код приведён, компилируешь, и тестируешь, я не собираюсь что-то доказывать.

Я вам тогда выставлю счет по своему обычному рейту, ок?

А если серьезно - хотели бы показать что-то - показали бы. Даже просто результаты прогонов.
А не то что вы постили.
Перейти в начало страницы
 
 
 NanoBot-AMK
сообщение 18.05.2019, 10:21
Сообщение #290


Почти Игроман
*********

Группа: Участник
Сообщений: 629
Регистрация: 10.11.2015
Пользователь №: 22739



(IMG:https://images.gameru.net/thumb/57ea12827968f9f.png)
AMD Athlon II X4 640 3.00 GHz
Это старый процессор, нет кеша 3-го уровня, и всего 3 инструкции за такт.
Более новые процессоры дадут гораздо лучший результат.
Ах да, тест ассемблерного варианта дал скорость 2.4 сек за 100'000'000 двордов.
Но GCC x86-32 дал результат аналогичный ассемблерному, при ключе -march=athlon-xp, а ассемблерный вариант х86-32 не дал такой эффективности.
Код VS2017, VS2010 получился более медленный.
Вот тут то у меня и возникла мысль что хорошо бы заменить компилятор. Вероятно можно повысить скорость XRay'я если использовать GCC.
ЗЫ
При правильных ключей оптимизации конечно.

Сообщение отредактировал NanoBot-AMK - 18.05.2019, 10:27
Перейти в начало страницы
 
 
 abramcumner
сообщение 18.05.2019, 14:16
Сообщение #291


Босс
********************

Группа: Участник
Сообщений: 4066
Регистрация: 27.04.2011
Из: Россия
Пользователь №: 14366



Цитата
Ах да, тест ассемблерного варианта дал скорость 2.4 сек за 100'000'000 двордов.

У radixsort1 на скрине 2.6 сек. Если заменить int64 на dword, как в ассемблерном, уделает его на полсекунды.

Цитата
Но GCC x86-32 дал результат аналогичный ассемблерному, при ключе -march=athlon-xp, а ассемблерный вариант х86-32 не дал такой эффективности.

(IMG:style_emoticons/default/biggrin.gif)

Цитата
Более новые процессоры дадут гораздо лучший результат.

На более новых процессорах с/с++ будет рвать ассемблер, как тузик грелку.


Цитата
Код VS2017, VS2010 получился более медленный.

Студией тоже с -O3 собирал? (IMG:style_emoticons/default/z_lol1.gif)
Перейти в начало страницы
 
 
 aka_sektor
сообщение 15.06.2019, 00:23
Сообщение #292


Заслуженный Мастер Игры
*************

Группа: Участник
Сообщений: 1580
Регистрация: 04.04.2013
Из: Беларусь
Пользователь №: 16432



(IMG:style_emoticons/default/biggrin.gif)

Перейти в начало страницы
 
 
 Молния в вакууме
сообщение 19.06.2019, 02:36
Сообщение #293


Почти Игроман
*********

Группа: Участник
Сообщений: 624
Регистрация: 05.05.2007
Пользователь №: 6215



Заценил всё-таки Objective-C, правда не современный, а вариант из Portable Object Compiler.
Интересный язык, можно прям в рантайме один класс на другой заменять (IMG:style_emoticons/default/biggrin.gif)
например
Код
#include <Object.h>

@interface MyBase1 : Object
-(void) sayHello;
@end

@implementation MyBase1
-(void) sayHello
{
    printf("hello from MyBase1\n");
}
@end

@interface MyBase2 : MyBase1
-(void) sayHello;
@end

@implementation MyBase2
-(void) sayHello
{
    printf("hello from MyBase2\n");
}
@end

@interface MyObject : MyBase1
-(void) sayHello;
@end

@implementation MyObject
-(void) sayHello
{
    [super sayHello];
}
@end

int main(int argc, char *argv[])
{
    id myobj = [MyObject new];
    
    [myobj sayHello];
    [MyBase2 poseAs: MyBase1];
    [myobj sayHello];
    
    [myobj free];
    
    return 0;
}

напечатает в консоль
Код
hello from MyBase1
hello from MyBase2


В компилируемых языках я такого ещё не встречал. (IMG:style_emoticons/default/smile.gif)
Перейти в начало страницы
 
 
 RayTwitty
сообщение 14.08.2019, 03:02
Сообщение #294


Доктор Игровых Наук
*******************

Группа: Участник
Сообщений: 3805
Регистрация: 24.09.2010
Пользователь №: 14086



Почему на вики гитхаба перестали работать якори на странице? Причем только якори с кириллицей.
Работает
Код
https://github.com/proj/wiki/Скриптовый-API#actor

Не работает
Код
https://github.com/proj/wiki/Скриптовый-API#Классы-игровых-объектов


Мелкософт?????
Перейти в начало страницы
 
 
 iOrange
сообщение 14.08.2019, 06:08
Сообщение #295


Почти Мастер
***********

Группа: Участник
Сообщений: 1079
Регистрация: 30.03.2010
Из: Planet Earth
Пользователь №: 13811



Цитата(Молния в вакууме @ 19.06.2019, 01:40) *
можно прям в рантайме один класс на другой заменять

Потому что это не классы, а таблицы. Еще можно вызывать методы тьфу ты, т.е., посылать сигналы нулевому обекту (тот который nil).
Ибо нет методов - есть интерфейсы и сигналы - и при посылке сигнала рантайм проверит есть ли объект, если да - то есть ли в его таблице обработчик такого сигнала, и только тогда будет вызов.

Пришлось в свое время несколько лет на этом пописать под MacOS/iOS. С тех пор ненавижу эти оси (IMG:style_emoticons/default/dry.gif)
Перейти в начало страницы
 
 
 iOrange
сообщение 21.08.2019, 03:37
Сообщение #296


Почти Мастер
***********

Группа: Участник
Сообщений: 1079
Регистрация: 30.03.2010
Из: Planet Earth
Пользователь №: 13811



Цитата
Atlassian

After much consideration, we've decided to remove Mercurial support from Bitbucket Cloud and the API. Mercurial features and repositories will be officially removed from Bitbucket and its API on June 1, 2020.


Шикарно блин, у меня куча Mercurial реп там лежит. (IMG:style_emoticons/default/dry.gif)
Что за день блин сегодня такой, одни разочарования
Перейти в начало страницы
 
 
 ForserX
сообщение 21.08.2019, 07:46
Сообщение #297


Продвинутый геймер
********

Группа: Модератор
Сообщений: 469
Регистрация: 19.07.2015
Из: Москва
Пользователь №: 22151



iOrange, экспортируй в гит. Я такое провернул два года назад.
Перейти в начало страницы
 
 
 iOrange
сообщение 21.08.2019, 08:17
Сообщение #298


Почти Мастер
***********

Группа: Участник
Сообщений: 1079
Регистрация: 30.03.2010
Из: Planet Earth
Пользователь №: 13811



Цитата(ForserX @ 21.08.2019, 06:50) *
экспортируй в гит. Я такое провернул два года назад.

Ну то понятно, но мне нравился Hg... Эх, ну ладно, перенесу на гитхаб все.
Перейти в начало страницы
 
 
 RayTwitty
сообщение 21.08.2019, 15:16
Сообщение #299


Доктор Игровых Наук
*******************

Группа: Участник
Сообщений: 3805
Регистрация: 24.09.2010
Пользователь №: 14086



Цитата(RayTwitty @ 14.08.2019, 03:06) *
Почему на вики гитхаба перестали работать якори на странице? Причем только якори с кириллицей.
Работает
Код
https://github.com/proj/wiki/Скриптовый-API#actor

Не работает
Код
https://github.com/proj/wiki/Скриптовый-API#Классы-игровых-объектов


Мелкософт?????

Посмотрел, не совсем понял, косяк именно гитхаба или браузера.
Вот якорь с латиницей, он работает как надо:
Код
<a id="user-content-new-sound" class="anchor" href="#new-sound" aria-hidden="true">

А вот с кириллицей:
Код
<a id="user-content-Общие-моменты" class="anchor" href="#%D0%9E%D0%B1%D1%89%D0%B8%D0%B5-%D0%BC%D0%BE%D0%BC%D0%B5%D0%BD%D1%82%D1%8B" aria-hidden="true">

закодированный урл декодируется как раз в "Общие-моменты"
https://www.artlebedev.ru/decoder/advanced/

но если в href дописать "user-content-" таким образом, то якорь начинает работать нормально.
Код
<a id="user-content-Общие-моменты" class="anchor" href="#user-content-%D0%9E%D0%B1%D1%89%D0%B8%D0%B5-%D0%BC%D0%BE%D0%BC%D0%B5%D0%BD%D1%82%D1%8B" aria-hidden="true">
Перейти в начало страницы
 
 
 xrModder
сообщение 21.08.2019, 20:48
Сообщение #300


Игроман
**********

Группа: Участник
Сообщений: 796
Регистрация: 08.08.2018
Из: Казахстан
Пользователь №: 29590



Есть код:
Код
BOOL SymRegisterCallback(IN PSYMBOL_REGISTERED_CALLBACK CallbackFunction, IN PVOID UserContext)

Чем заменить PVOID для корректной сборки под 32 и 64 бит?
Перейти в начало страницы
 
 
 
 

 
3 чел. читают эту тему (гостей: 3, скрытых пользователей: 0)
Пользователей: 0

 

Текстовая версия Сейчас: 16.12.2019, 12:58