首页 > 其他 > 详细

一些日常卡常工具集合

时间:2018-07-18 01:07:05      阅读:86      评论:0      收藏:0      [点我收藏+]

标签:分支预测   代码   mes   ont   选择   决定   的区别   expec   函数名   

一些日常卡常工具集合

  ——工欲善其事,必先利其器

  尽管不会松松松,但是至少维持一个比较小的常数还是比较好的

  在此之前依然要保证算法的正确性以及代码的可写性

  本文依然会持久更新,因为一次写不完

Tools1:算法

  这个的重要性就不强调了,轻则$log$,重则$n^2$,更令人窒息者为多项式和非多项式的区别

  设计一个好的算法,首先不要想着如何去用$O(n^2)$碾压$O(n)$,而是先想如何实现$O(n)$才是比较好的

Tools2:IO

  IO输出要么没有显著优化,要么直接从TLE优化到AC,在另一篇博客有介绍https://www.cnblogs.com/CreeperLKF/p/8448568.html

  然后下面放上一些我平时用的贴在代码前面且具有不同功能的一些东西:

  1.  短一些,只有一个小的工具包,没有使用要求

技术分享图片
#include <cstdio>
#include <cctype>
#include <cstring>

//User‘s Lib

using namespace std;

char buf[11111111], *pc = buf;

extern inline void Main_Init(){
    static bool INITED = false;
    if(INITED) fclose(stdin), fclose(stdout);
    else {
        fread(buf, 1, 11111111, stdin); 
        INITED = true;           
    }
}

static inline int read(){
    int num = 0;
    char c, sf = 1;
    while(isspace(c = *pc++));
    if(c == 45) sf = -1, c = *pc ++;
    while(num = num * 10 + c - 48, isdigit(c = *pc++));
    return num * sf;
}

namespace LKF{
    template <typename T>
    extern inline T abs(T tar){
        return tar < 0 ? -tar : tar;
    }
    template <typename T>
    extern inline void swap(T &a, T &b){
        T t = a;
        a = b;
        b = t;
    }
    template <typename T>
    extern inline void upmax(T &x, const T &y){
        if(x < y) x = y;
    }
    template <typename T>
    extern inline void upmin(T &x, const T &y){
        if(x > y) x = y;
    }
    template <typename T>
    extern inline T max(T a, T b){
        return a > b ? a : b;
    }
    template <typename T>
    extern inline T min(T a, T b){
        return a < b ? a : b;
    }
}

//Source Code

  2.  长一些,分类讨论一些开关,然后不是所有东西保证效率,功能多

技术分享图片
//Created By Creeper_LKF
//Caution::We used "pragma" in the code
#include <cstdio>
#include <cctype>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>

#ifdef __gnu_linux__

#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>

#endif

#if __cplusplus < 201103L

#include <stdarg.h>

#endif

//Algorithm Heads


using namespace std;

//Debug Port

#define DEBUG_PORT
#define DEBUG

#ifdef ONLINE_JUDGE
#undef DEBUG_PORT
#undef DEBUG
#endif

#ifdef DEBUG_PORT
#if __cplusplus < 201103L
# pragma message "Warning : C++11 Not Use"
#ifdef DEBUG
template<typename T>
extern inline void Debug(T tar){
    cerr << tar << endl;
}
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
    cerr << head <<  ;
    Debug(mid, tail...);
}
#else
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
    return ;
}
#endif
#else
#ifdef DEBUG
template <typename T>
extern inline void Debug(T tar){
    cerr << tar << endl;
}
#else
template <typename T>
extern inline void Debug(T tar){
    return ;
}
#endif
#endif
#else
template <typename T>
extern inline void Debug(T tar){
    return ;
}
#endif

const char file_name[] = "b";

#define NAME_SPACE
#define USING

#ifdef NAME_SPACE
namespace LKF{
#endif
    #define SF_READ
    #define EOF_READ
    // #define ONLINE_JUDGE
    #define WRITE_ENDL
    // #define FAST_WRITE
    #define SPLIT_WRITE
    const size_t MAX_BUF_SIZE = 50000000;
    
    #define NEED_FILE

    #ifdef FAST_WRITE
    char outp[MAX_BUF_SIZE], *op = outp;
    #endif

    #ifdef ONLINE_JUDGE
    #undef NEED_FILE
    #endif    

    #ifdef FAST_WRITE
    #ifndef WRITE_ENDL
    #define WRITE_ENDL
    #endif
    #endif

    extern inline void FILE_OPT(){
        #ifdef NEED_FILE
        #define FILE_NAME file_name
        char IN_FILE[sizeof(FILE_NAME) + 5], OUT_FILE[sizeof(FILE_NAME) + 5];
        strcpy(IN_FILE, FILE_NAME), strcpy(OUT_FILE, FILE_NAME);
        strcat(IN_FILE, ".in"), strcat(OUT_FILE, ".out");
        freopen(IN_FILE, "r", stdin);
        freopen(OUT_FILE, "w", stdout);  
        #endif      
    }

    #ifdef __gnu_linux__

    char *pc;

    extern inline void Main_Init(){
        static bool INITED = false;
        if(INITED){
            #ifdef FAST_WRITE
            fwrite(outp, 1, op - outp - 1, stdout);
            #endif
            fclose(stdin), fclose(stdout);
        } else {
            FILE_OPT();
            pc = (char *) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0);
            INITED = true;
        }
    }

    #else

    char buf[MAX_BUF_SIZE], *pc = buf;

    extern inline void Main_Init(){
        static bool INITED = false;
        if(INITED){
            #ifdef FAST_WRITE
            fwrite(outp, 1, op - outp - 1, stdout);
            #endif
            fclose(stdin), fclose(stdout);
        } else {
            FILE_OPT();
            fread(buf, 1, MAX_BUF_SIZE, stdin); 
            INITED = true;
        }
    }

    #endif

    inline char read_ch(){
        char c;
        while(isspace(c = *pc ++));
        return c;
    }

    #ifdef EOF_READ

    #ifdef SF_READ

    template<typename T>
    static inline void read(T &num){
        num = 0;
        char c, sf = 1;
        while(isspace(c = *pc++));
        if(c == 45) sf = -1, c = *pc ++;
        while(num = num * 10 + c - 48, isdigit(c = *pc++));
        num *= sf;
    }

    static inline int read(){
        int num = 0;
        char c, sf = 1;
        while(isspace(c = *pc++));
        if(c == 45) sf = -1, c = *pc ++;
        while(num = num * 10 + c - 48, isdigit(c = *pc++));
        return num * sf;
    }

    static inline double read_dec(){
        double num = 0, decs = 1;
        char c, sf = 1;
        while(isspace(c = *pc ++));
        if(c == -) sf = -1, c = *pc ++;
        while(num = num * 10 + c - 48, isdigit(c = *pc ++));
        if(c != .) return num * sf;
        c = *pc ++;
        while(num += (decs *= 0.1) * (c - 48), isdigit(c = *pc ++));
        return num * sf;
    }

    #else

    template<typename T>
    static inline T read(T &num){
        num = 0;
        char c;
        while (isspace(c = *pc++));
        while (num = num * 10 + c - 48, isdigit(c = *pc++));
        return num;
    }

    static inline int read(){
        int num = 0;
        char c;
        while (isspace(c = *pc++));
        while (num = num * 10 + c - 48, isdigit(c = *pc++));
        return num;
    }

    static inline double read_dec(){
        double num = 0, decs = 1;
        char c;
        while(isspace(c = *pc ++));
        while(num = num * 10 + c - 48, isdigit(c = *pc ++));
        if(c != .) return num;
        c = *pc ++;
        while(num += (c - 48) * (decs *= 0.1), isdigit(c = *pc ++));
        return num;
    }

    #endif

    #else

    #ifdef SF_READ

    template<typename T>
    static inline void read(T &num){
        num = 0;
        char c, sf = 1;
        while((c = *pc++) < 45);
        if(c == 45) sf = -1, c = *pc ++;
        while(num = num * 10 + c - 48, (c = *pc++) >= 48);
        num *= sf;
    }

    static inline int read(){
        int num = 0;
        char c, sf = 1;
        while((c = *pc++) < 45);
        if(c == 45) sf = -1, c = *pc ++;
        while(num = num * 10 + c - 48, (c = *pc++) >= 48);
        return num * sf;
    }

    static inline double read_dec(){
        double num = 0, decs = 1;
        char c, sf = 1;
        while(isspace(c = *pc ++));
        if(c == -) sf = -1, c = *pc ++;
        while(num = num * 10 + c - 48, isdigit(c = *pc ++));
        if(c != .) return num * sf;
        c = *pc ++;
        while(num += (decs *= 0.1) * (c - 48), isdigit(c = *pc ++));
        return num * sf;
    }

    #else

    template<typename T>
    static inline T read(T &num){
        num = 0;
        char c;
        while ((c = *pc++) < 48);
        while (num = num * 10 + c - 48, (c = *pc++) >= 48);
        return num;
    }

    static inline int read(){
        int num = 0;
        char c;
        while ((c = *pc++) < 48);
        while (num = num * 10 + c - 48, (c = *pc++) >= 48);
        return num;
    }

    static inline double read_dec(){
        double num = 0, decs = 1;
        char c;
        while(isspace(c = *pc ++));
        while(num = num * 10 + c - 48, isdigit(c = *pc ++));
        if(c != .) return num;
        c = *pc ++;
        while(num += (c - 48) * (decs *= 0.1), isdigit(c = *pc ++));
        return num;
    }

    #endif

    #endif

    #ifdef FAST_WRITE
    template <typename T>
    inline void Call_Write(char Split, T tar){
        char buf[20];
        int top = 0;
        if(tar == 0) *op ++ = 48;
        else {
            if(tar < 0) *op ++ = -, tar = -tar;
            while(tar) buf[++top] = tar % 10, tar /= 10;
            while(top) *op ++ = buf[top --] ^ 48;
        }
        *op ++ = Split;
    }
    template <typename T>
    inline void Call_Write(T tar){
        char buf[20];
        int top = 0;
        if(tar == 0) *op ++ = 48;
        else {
            if(tar < 0) *op ++ = -, tar = -tar;
            while(tar) buf[++top] = tar % 10, tar /= 10;
            while(top) *op ++ = buf[top --] ^ 48;
        }
    }
    #endif

    #ifdef FAST_WRITE

    extern inline void write(){
        *op ++ = \n;
    }

    template<typename T>
    extern inline void write(T tar){
        Call_Write(tar);
        #ifdef WRITE_ENDL
        write();
        #endif
    }

    #if __cplusplus >= 201103L

    # pragma GCC diagnostic push
    # pragma GCC diagnostic ignored "-Wunused-parameter"

    template<typename T>
    extern inline void write(char Split, T tar){
        Call_Write(tar);
        #ifdef WRITE_ENDL
        write();
        #endif
    }

    # pragma GCC diagnostic pop
    # pragma message "Warning : pragma used"

    template<typename Head, typename T, typename... Tail>
    extern inline void write(char Split, Head head, T mid, Tail... tail){
        Call_Write(Split, head);
        write(Split, mid, tail...);
    }

    #else

    template <typename T>
    extern inline void write(char Split, T tar){
        Call_Write(tar);
        #ifdef WRITE_ENDL
        write();
        #endif
    }

    #endif

    #else

    extern inline void write(){
        cout << endl;
    }

    template<typename T>
    extern inline void write(T tar){
        cout << tar;
        #ifdef WRITE_ENDL
        write();
        #endif
    }

    #if __cplusplus >= 201103L

    template<typename T>
    extern inline void write(char Split, T tar){
        cout << tar << Split;
        #ifdef WRITE_ENDL
        write();
        #endif
    }

    template<typename Head, typename T, typename... Tail>
    extern inline void write(char Split, Head head, T mid, Tail... tail){
        #ifdef SPLIT_WRITE
        cout << head << Split;
        #else
        cout << head;
        #endif
        write(Split, mid, tail...);
    }

    #else

    template <typename T>
    extern inline void write(char Split, T tar){
        cout << tar << Split;
        #ifdef WRITE_ENDL
        write();
        #endif
    }

    #endif

    #endif

    template <typename T>
    extern inline void upmax(T &x, const T &y){
        if(x < y) x = y;
    }
    template <typename T>
    extern inline void upmin(T &x, const T &y){
        if(x > y) x = y;
    }

    #if __cplusplus >= 201103L

    template<typename T>
    extern inline T max(T tar){
        return tar;
    }

    template<typename T>
    extern inline T min(T tar){
        return tar;
    }

    template <typename Head, typename T, typename... Tail>
    extern inline Head max(Head head, T mid, Tail... tail){
        Head tmp = max(mid, tail...);
        return head > tmp ? head : tmp;
    }
    template <typename Head, typename T, typename... Tail>
    extern inline Head min(Head head, T mid, Tail... tail){
        Head tmp = min(mid, tail...);
        return head < tmp ? head : tmp;
    }

    #else

    template <typename T>
    extern inline T max(T a, T b){
        return a > b ? a : b;
    }
    template <typename T>
    extern inline T min(T a, T b){
        return a < b ? a : b;
    }    

    #endif

    template <typename T>
    extern inline T abs(T tar){
        return tar < 0 ? -tar : tar;
    }
    template <typename T>
    extern inline void swap(T &a, T &b){
        T t = a;
        a = b;
        b = t;
    }
#ifdef NAME_SPACE
}
#endif

//Algorithm

#ifdef NAME_SPACE
namespace LKF{
#endif

    template <typename T>
    struct Queue{
        size_t s, t;
        T *q;
        Queue(){
            s = 1, t = 0;
            q = NULL;
        }
        Queue(size_t siz){
            s = 1, t = 0;
            q = (T*)malloc(sizeof(T) * siz);
            assert(q != NULL);
        }
        inline void Re_Init(size_t siz){
            q = (T*)realloc(q, sizeof(T) * siz);
            assert(q != NULL);
        }
        ~Queue(){
            delete[] q;
        }
        inline void clear(){
            s = 1, t = 0;
        }
        inline bool empty(){
            return s > t;
        }
        inline size_t size(){
            return t - s + 1;
        }
        inline void push(T tar){
            q[++ t] = tar;
        }
        inline void pop_front(){
            s ++;
        }
        inline void pop_back(){
            t --;
        }
        inline T front(){
            return q[s];
        }
        inline T back(){
            return q[t];
        }
    };

    template <typename T>
    struct Stack{
        size_t t;
        T *s;
        Stack(){
            t = 0;
            s = NULL;
        }
        Stack(size_t siz){
            t = 0;
            s = (T*)malloc(sizeof(T) * siz);
            assert(s != NULL);
        }
        inline void Re_Init(size_t siz){
            s = (T*)realloc(s, sizeof(T) * siz);
            assert(s != NULL);
        }
        ~Stack(){
            delete[] s;
        }
        inline void clear(){
            t = 0;
        }
        inline bool empty(){
            return t == 0;
        }
        inline size_t size(){
            return t;
        }
        inline void push(T tar){
            s[++ t] = tar;
        }
        inline T top(){
            return s[t];
        }
        inline void pop(){
            t --;
        }
    };

#ifdef NAME_SPACE
}
#endif

#ifdef USING

#ifdef NAME_SPACE
using LKF::pc;
using LKF::read_ch;
using LKF::read_dec;
using LKF::read;
using LKF::Main_Init;
using LKF::write;
using LKF::upmax;
using LKF::upmin;
using LKF::max;
using LKF::min;
using LKF::abs;
// using LKF::swap;
#else
using ::pc;
using ::read_ch;
using ::read_dec;
using ::read;
using ::Main_Init;
using ::write;
using ::upmax;
using ::upmin;
using ::max;
using ::min;
using ::abs;
// using ::swap;
#endif

#endif

//Source Code

  3.  C++11下可以使用调试多参数调试 Debug(arg1, arg2...) ,建议搭配dot可以直接图论题中绘图,可以不删除调试代码交到Luogu上

技术分享图片
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>

//User‘s Lib

using namespace std;

// #define DEBUG_PORT
#define DEBUG

#ifdef ONLINE_JUDGE
#undef DEBUG_PORT
#undef DEBUG
#endif

#ifdef DEBUG_PORT
#if __cplusplus >= 201103L
#ifdef DEBUG
template<typename T>
extern inline void Debug(T tar){
    cerr << tar << endl;
}
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
    cerr << head <<  ;
    Debug(mid, tail...);
}
#else
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wunused-parameter"
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
    return ;
}
# pragma GCC diagnostic pop
# pragma message "Warning : pragma used"
#endif
#else
# pragma message "Warning : C++11 Not Use"
#ifdef DEBUG
template <typename T>
extern inline void Debug(T tar){
    cerr << tar << endl;
}
#else
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wunused-parameter"
template <typename T>
extern inline void Debug(T tar){
    return ;
}
# pragma GCC diagnostic pop
# pragma message "Warning : pragma used"
#endif
#endif
#else
# pragma GCC diagnostic push
# pragma GCC diagnostic ignored "-Wunused-parameter"
template<typename Head, typename T, typename... Tail>
extern inline void Debug(Head head, T mid, Tail... tail){
    return ;
}
template <typename T>
extern inline void Debug(T tar){
    return ;
}
# pragma GCC diagnostic pop
# pragma message "Warning : pragma used"
#endif

char buf[11111111], *pc = buf;

extern inline void Main_Init(){
    static bool INITED = false;
    if(INITED) fclose(stdin), fclose(stdout);
    else {
        fread(buf, 1, 11111111, stdin); 
        INITED = true;           
    }
}

static inline int read(){
    int num = 0;
    char c, sf = 1;
    while(isspace(c = *pc++));
    if(c == 45) sf = -1, c = *pc ++;
    while(num = num * 10 + c - 48, isdigit(c = *pc++));
    return num * sf;
}

namespace LKF{
    template <typename T>
    extern inline T abs(T tar){
        return tar < 0 ? -tar : tar;
    }
    template <typename T>
    extern inline void swap(T &a, T &b){
        T t = a;
        a = b;
        b = t;
    }
    template <typename T>
    extern inline void upmax(T &x, const T &y){
        if(x < y) x = y;
    }
    template <typename T>
    extern inline void upmin(T &x, const T &y){
        if(x > y) x = y;
    }
    template <typename T>
    extern inline T max(T a, T b){
        return a > b ? a : b;
    }
    template <typename T>
    extern inline T min(T a, T b){
        return a < b ? a : b;
    }
}

//Source Code
简单

  4.  只能读非负整数,然后用的是更快的读入,但是在本地都开了文件输入输出

技术分享图片
#include <cstdio>

#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>

//User‘s Lib

using namespace std;

char *pc;

inline void Main_Init(){
    static bool inited = false;
    if(inited) fclose(stdin), fclose(stdout);
    else {
        #ifndef ONLINE_JUDGE
        freopen("b.in", "r", stdin);
        freopen("b.out", "w", stdout);
        #endif
        pc = (char *) mmap(NULL, lseek(0, 0, SEEK_END), PROT_READ, MAP_PRIVATE, 0, 0);
        inited = true;
    }
}

inline int read(){
    int num = 0;
    char c;
    while((c = *pc ++) < 48);
    while(num = num * 10 + c - 48, (c = *pc ++) >= 48);
    return num;
}

namespace LKF{
    template <typename T>
    extern inline T abs(T tar){
        return tar < 0 ? -tar : tar;
    }
    template <typename T>
    extern inline void swap(T &a, T &b){
        T t = a;
        a = b;
        b = t;
    }
    template <typename T>
    extern inline void upmax(T &x, const T &y){
        if(x < y) x = y;
    }
    template <typename T>
    extern inline void upmin(T &x, const T &y){
        if(x > y) x = y;
    }
    template <typename T>
    extern inline T max(T a, T b){
        return a > b ? a : b;
    }
    template <typename T>
    extern inline T min(T a, T b){
        return a < b ? a : b;
    }
}

//Do not copy from other files

//Source Code
快速

  5.  C++11特性用,删掉了分类讨论

技术分享图片
#include <cstdio>
#include <cctype>
#include <cstring>
#include <iostream>

//User‘s Lib

using namespace std;

#define DEBUG

#ifdef ONLINE_JUDGE
#undef DEBUG
#endif

#ifdef DEBUG
    template<typename T>
    extern inline void Debug(T tar){
        cerr << tar << endl;
    }
    template<typename Head, typename T, typename... Tail>
    extern inline void Debug(Head head, T mid, Tail... tail){
        cerr << head <<  ;
        Debug(mid, tail...);
    }
#else
    # pragma GCC diagnostic push
    template<typename Head, typename T, typename... Tail>
    extern inline void Debug(Head head, T mid, Tail... tail){
        return ;
    }
    # pragma GCC diagnostic pop
#endif

char buf[11111111], *pc = buf;

extern inline void Main_Init(){
    static bool INITED = false;
    if(INITED) fclose(stdin), fclose(stdout);
    else {
        fread(buf, 1, 11111111, stdin); 
        INITED = true;           
    }
}

static inline int read(){
    int num = 0;
    char c, sf = 1;
    while(isspace(c = *pc++));
    if(c == 45) sf = -1, c = *pc ++;
    while(num = num * 10 + c - 48, isdigit(c = *pc++));
    return num * sf;
}

namespace LKF{
    template <typename T>
    extern inline void upmax(T &x, const T &y){
        if(x < y) x = y;
    }
    template <typename T>
    extern inline void upmin(T &x, const T &y){
        if(x > y) x = y;
    }

    template<typename T>
    extern inline T max(T tar){
        return tar;
    }

    template<typename T>
    extern inline T min(T tar){
        return tar;
    }

    template <typename Head, typename T, typename... Tail>
    extern inline Head max(Head head, T mid, Tail... tail){
        Head tmp = max(mid, tail...);
        return head > tmp ? head : tmp;
    }
    template <typename Head, typename T, typename... Tail>
    extern inline Head min(Head head, T mid, Tail... tail){
        Head tmp = min(mid, tail...);
        return head < tmp ? head : tmp;
    }

    template <typename T>
    extern inline T abs(T tar){
        return tar < 0 ? -tar : tar;
    }
    template <typename T>
    extern inline void swap(T &a, T &b){
        T t = a;
        a = b;
        b = t;
    }
}

//Source Code
C++11

  6.  最简单的快读

技术分享图片
#include <cstdio>

using namespace std;

char buf[11111111], *pc = buf;

inline void Main_Init(){
    static bool inited = false;
    if(inited) fclose(stdin), fclose(stdout);
    else {
        fread(buf, 1, 11111111, stdin);
        inited = true;
    }
}

inline int read(){
    int num = 0;
    char c;
    while((c = *pc ++) < 48);
    while(num = num * 10 + c - 48, (c = *pc ++) >= 48);
    return num;
}

//Source Code
快读

Tools3:__builtin_

  一个非常妙而且实用的工具,有些C++库函数会调用到,不过自己去学会调用肯定会比较妙,整个Builtin家族非常大(看文档https://gcc.gnu.org/onlinedocs/gcc/,具体可以在https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#Other-Builtins查找),这里只介绍一些常用的。下面的函数的参数以及返回值对照了gcc文档。

  二进制相关

  (注意下面函数定义在unsigned int(或int)上,如果需要使用unsigned long long(或long long)版则可以在函数名后面加上ll,例如__builtin_ffsll接受long long的参数)(还有一个__builtin_clrsb看不懂什么玩意)。

  1.   int __builtin_ffs (int x):查询x二进制最后一个1是第几位
  2.   int __builtin_clz (unsigned int x):查询x有多少个前导0,If x is 0, the result is undefined.
  3.   int __builtin_ctz (unsigned int x):查询x有多少个后缀0,If x is 0, the result is undefined.
  4.   int __builtin_popcount (unsigned int x):查询x有多少个1
  5.   int __builtin_parity (unsigned int x):查询x的二进制奇偶校验,也就是x中1的个数模2
  6.   uint16_t __builtin_bswap16 (uint16_t x):按照字节翻转二进制位,例如0xaabb翻转成为0xbbaa,然后16可替换为32,64,表示位数

  CPU分支预测优化

  long __builtin_expect (long exp, long c)

    函数的作用就是引导CPU在分支预测的时候选择某个if分支执行,以前靠这个东西直接把一道题卡到了0ms,单点甩Rank2接近8ms,可见有些情况下效果还是不错的

    食用方法:exp那里填写你希望预测的一个表达式,建议不要写的太复杂了,c填写你预测表达式大概率会是什么值,然后直接用在if内即可,例如 if(__builtin_expect(a === b, 0)) 

    效果:如果写的比较好的话有一些大优化,否则会导致CPU频繁罚时

    例子:例如你知道某个数据结构它的体型庞大而且你有特意地防止node指针指向NULL,但是如果你不放心的话那么可以加一个这个。例如表达式$i%100000000==1$一般会比较难成立,可以优化,而$i%10==1$就不需要这样优化了

  提前写入缓存

  void __builtin_prefetch (const void *addr, ...)

    就是提前把数据取到缓存

    gcc的参数表最后面还有两个可选参数,rw和locality,表示使用这个数据是读或者写,以及这个数据的时间局部性。

    读或者写就不说了

    时间局部性表示这个数据在被访问之后在一定时间内还会不会再次访问(而不是距离第一次访问还有多久),决定了这个数据在缓存中的“寿命”。0表示没有时间局部性,也就是很长时间内不再访问,而1表示高时间局部性,表示访问了时候很快又会访问。这个参数一定是个编译时候的常量,默认为3.

 

Tools4:细节

  首先register和inline标记应该都会吧。register表示建议编译器将变量放在编译器中,C++11及以上为了防止滥用渐渐开始忽略这个东西,在C++17时你会被提醒这个东西已经不再被编译了。inline在我讲快读那篇文章的末尾有https://www.cnblogs.com/CreeperLKF/p/8448568.html

  例如下面Luogu上两份A+B Problem(找LZL123测试的),代码相差无几,但是时间差了584ms,空间差了63971kb,差距竟然只有1000的数据范围

  见提交记录https://www.luogu.org/record/show?rid=6205849https://www.luogu.org/recordnew/show/5650350

  代码区别:

  584ms:

 1 #include <cstdio>
 2 int x[1<<24];
 3 int main() 
 4 {
 5     int a,b,ans=0;
 6     for(int i=1;i<=1<<24;++i)   
 7         x[i]++,ans+=x[i];
 8     scanf("%d%d",&a,&b);
 9     printf("%d",a+b);
10     return 0;
11 }

  0ms:

 1 #include <cstdio>
 2 int x[1<<24+1000];
 3 int main() 
 4 {
 5     int a,b,ans=0;
 6     for(int i=1;i<=1<<24+1000;++i)   
 7         x[i]++,ans+=x[i];
 8     scanf("%d%d",&a,&b);
 9     printf("%d",a+b);
10     return 0;
11 }

 

一些日常卡常工具集合

标签:分支预测   代码   mes   ont   选择   决定   的区别   expec   函数名   

原文:https://www.cnblogs.com/CreeperLKF/p/9314916.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号