Перейти в начало страницы

Здравствуйте, гость ( Авторизация | Регистрация )

Gameru.net останавливает работу в связи с вторжением армии РФ в Украину. Следите за дальнейшими анонсами.
Support Gameru!
22 страниц V  « < 13 14 15 16 17 > »   
Ответить в данную темуНачать новую тему
> Курилка программистов, Флуд на около программерские темы
NanoBot-AMK
сообщение 17.05.2019, 17:29
Сообщение #281


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

Репутация:   75  
Группа: Участник
Сообщений: 1168
Награды: 4
Регистрация: 10.11.2015




Вставить ник Цитировать выделенное в форуму быстрого ответа


Что быстрей, ассемблер или компилятор С/С++? Вопрос не такой однозначный!
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

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

Сообщение отредактировал NanoBot-AMK - 17.05.2019, 17:33


--------------------
СТАЛКЕР только для ПК!
Перейти в начало страницы
 
iOrange
сообщение 17.05.2019, 17:50
Сообщение #282
BFG9000 owner

Половина землекопа
**************

Репутация:   247  
Группа: Припаркованный аккаунт
Сообщений: 1813
Награды: 3
Регистрация: 30.03.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


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

Если таки сможете - прославитесь z_lol1.gif

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

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

Напостили простыни какого-то стремного кода, и что?
Бремя доказательства лежит на плечах утверждающего, не слыхали?


--------------------
Hello worlds!
Перейти в начало страницы
 
cjayho
сообщение 17.05.2019, 22:12
Сообщение #283


Мастер Игры
************

Репутация:   248  
Группа: Участник
Сообщений: 1363
Награды: 4
Регистрация: 08.03.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


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


Примите синтаксический сахар biggrin.gif

Сообщение отредактировал cjayho - 17.05.2019, 22:12


--------------------
Набор шейдеров для S.T.A.L.K.E.R: Shadow of chernobyl: ECB-Shaderpack - https://github.com/cjayho/ecb-shaderpack/

------

Продюсер электронной музыки в стиле Dark Ambient, автор саундтрека для Desowave S.T.A.L.K.E.R.: Lost Alpha.

Spotify | Apple Music | YouTube | BandCamp | AudioMack
Перейти в начало страницы
 
NanoBot-AMK
сообщение 18.05.2019, 03:46
Сообщение #284


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

Репутация:   75  
Группа: Участник
Сообщений: 1168
Награды: 4
Регистрация: 10.11.2015




Вставить ник Цитировать выделенное в форуму быстрого ответа


Вам смешно, а мне совсем не смешно. sad.gif z_crazy.gif
Код я показал, вот и тестируйте. Или что GCC не можете скачать. Батник запустить, это же так просто.
Ладно, не подставайте меня, я сейчас не в том состоянии чтобы шутить.


--------------------
СТАЛКЕР только для ПК!
Перейти в начало страницы
 
iOrange
сообщение 18.05.2019, 03:54
Сообщение #285
BFG9000 owner

Половина землекопа
**************

Репутация:   247  
Группа: Припаркованный аккаунт
Сообщений: 1813
Награды: 3
Регистрация: 30.03.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


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

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

Читайте выше про "бремя доказательства..."


--------------------
Hello worlds!
Перейти в начало страницы
 
cjayho
сообщение 18.05.2019, 04:44
Сообщение #286


Мастер Игры
************

Репутация:   248  
Группа: Участник
Сообщений: 1363
Награды: 4
Регистрация: 08.03.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


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


Харэ бухать, алкоголь убивает моск. Ато скоро начнете верить в то что максимальная крепость этилового спирта составляет 96% wink.gif


--------------------
Набор шейдеров для S.T.A.L.K.E.R: Shadow of chernobyl: ECB-Shaderpack - https://github.com/cjayho/ecb-shaderpack/

------

Продюсер электронной музыки в стиле Dark Ambient, автор саундтрека для Desowave S.T.A.L.K.E.R.: Lost Alpha.

Spotify | Apple Music | YouTube | BandCamp | AudioMack
Перейти в начало страницы
 
NanoBot-AMK
сообщение 18.05.2019, 04:56
Сообщение #287


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

Репутация:   75  
Группа: Участник
Сообщений: 1168
Награды: 4
Регистрация: 10.11.2015




Вставить ник Цитировать выделенное в форуму быстрого ответа


Я не бухаю, я свою кошку Люску поминаю. sad.gif
Код приведён, компилируешь, и тестируешь, я не собираюсь что-то доказывать.
Блин вы программисты или кто. kozak.gif


--------------------
СТАЛКЕР только для ПК!
Перейти в начало страницы
 
cjayho
сообщение 18.05.2019, 05:04
Сообщение #288


Мастер Игры
************

Репутация:   248  
Группа: Участник
Сообщений: 1363
Награды: 4
Регистрация: 08.03.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


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


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

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


Я с вами в спор не вступал, потому не обязан отлавливать бетастазы вашего кода smile.gif. Я чо, на бетатестера похож?


--------------------
Набор шейдеров для S.T.A.L.K.E.R: Shadow of chernobyl: ECB-Shaderpack - https://github.com/cjayho/ecb-shaderpack/

------

Продюсер электронной музыки в стиле Dark Ambient, автор саундтрека для Desowave S.T.A.L.K.E.R.: Lost Alpha.

Spotify | Apple Music | YouTube | BandCamp | AudioMack
Перейти в начало страницы
 
iOrange
сообщение 18.05.2019, 06:31
Сообщение #289
BFG9000 owner

Половина землекопа
**************

Репутация:   247  
Группа: Припаркованный аккаунт
Сообщений: 1813
Награды: 3
Регистрация: 30.03.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


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

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

А если серьезно - хотели бы показать что-то - показали бы. Даже просто результаты прогонов.
А не то что вы постили.


--------------------
Hello worlds!
Перейти в начало страницы
 
NanoBot-AMK
сообщение 18.05.2019, 10:25
Сообщение #290


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

Репутация:   75  
Группа: Участник
Сообщений: 1168
Награды: 4
Регистрация: 10.11.2015




Вставить ник Цитировать выделенное в форуму быстрого ответа



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:31


--------------------
СТАЛКЕР только для ПК!
Перейти в начало страницы
 
abramcumner
сообщение 18.05.2019, 14:20
Сообщение #291


Игровое Воплощение
*********************

Репутация:   394  
Группа: Участник
Сообщений: 4791
Награды: 4
Регистрация: 27.04.2011




Вставить ник Цитировать выделенное в форуму быстрого ответа


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

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

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

biggrin.gif

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

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


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

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


Грандмастер
**************

Репутация:   118  
Группа: Участник
Сообщений: 1788
Награды: 4
Регистрация: 04.04.2013




Вставить ник Цитировать выделенное в форуму быстрого ответа


biggrin.gif



--------------------


Те кто играют уже не забудут ​​​​​​​© Алексей Сытянов
Перейти в начало страницы
 
Молния в вакууме
сообщение 19.06.2019, 02:40
Сообщение #293


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

Репутация:   187  
Группа: Участник
Сообщений: 647
Награды: 4
Регистрация: 05.05.2007




Вставить ник Цитировать выделенное в форуму быстрого ответа


Заценил всё-таки Objective-C, правда не современный, а вариант из Portable Object Compiler.
Интересный язык, можно прям в рантайме один класс на другой заменять 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


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


Игровой Бог
**********************

Репутация:   648  
Группа: Участник
Сообщений: 5354
Награды: 9
Регистрация: 24.09.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


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

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


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


--------------------
Перейти в начало страницы
 
iOrange
сообщение 14.08.2019, 06:12
Сообщение #295
BFG9000 owner

Половина землекопа
**************

Репутация:   247  
Группа: Припаркованный аккаунт
Сообщений: 1813
Награды: 3
Регистрация: 30.03.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


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

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

Пришлось в свое время несколько лет на этом пописать под MacOS/iOS. С тех пор ненавижу эти оси dry.gif


--------------------
Hello worlds!
Перейти в начало страницы
 
iOrange
сообщение 21.08.2019, 03:41
Сообщение #296
BFG9000 owner

Половина землекопа
**************

Репутация:   247  
Группа: Припаркованный аккаунт
Сообщений: 1813
Награды: 3
Регистрация: 30.03.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


Цитата
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 реп там лежит. dry.gif
Что за день блин сегодня такой, одни разочарования


--------------------
Hello worlds!
Перейти в начало страницы
 
ForserX
сообщение 21.08.2019, 07:50
Сообщение #297


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

Репутация:   91  
Группа: Модератор
Сообщений: 516
Награды: 4
Регистрация: 19.07.2015




Вставить ник Цитировать выделенное в форуму быстрого ответа


iOrange, экспортируй в гит. Я такое провернул два года назад.


--------------------

В армии по 01.07.2020.
Перейти в начало страницы
 
iOrange
сообщение 21.08.2019, 08:21
Сообщение #298
BFG9000 owner

Половина землекопа
**************

Репутация:   247  
Группа: Припаркованный аккаунт
Сообщений: 1813
Награды: 3
Регистрация: 30.03.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


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

Ну то понятно, но мне нравился Hg... Эх, ну ладно, перенесу на гитхаб все.


--------------------
Hello worlds!
Перейти в начало страницы
 
RayTwitty
сообщение 21.08.2019, 15:20
Сообщение #299


Игровой Бог
**********************

Репутация:   648  
Группа: Участник
Сообщений: 5354
Награды: 9
Регистрация: 24.09.2010




Вставить ник Цитировать выделенное в форуму быстрого ответа


Цитата(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:52
Сообщение #300


Мастер Игры
************

Репутация:   104  
Группа: Участник
Сообщений: 1331
Регистрация: 08.08.2018




Вставить ник Цитировать выделенное в форуму быстрого ответа


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

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

22 страниц V  « < 13 14 15 16 17 > » 
Ответить в данную темуНачать новую тему
2 чел. читают эту тему (гостей: 2, скрытых пользователей: 0)
Пользователей: 0

 



Текстовая версия Сейчас: 29.03.2024, 15:26