负载均衡的几种算法

发表于 2019-05-07 更新于 2019-05-11 分类于 algorithm
本文字数： 1.6k 阅读时长 ≈ 1 分钟

常见几种负载均衡算法

轮询法

j = i;
do
{
    j = (j + 1) mod n;
    i = j;
    return Si;
} while (j != i);
return NULL;

加权轮询

普通加权轮询

缺点是分配不均衡，有可能多个连续请求分配至统一服务器。

轮训所有节点，找到一个最大权重节点；
选中的节点权重-1；
直到减到0，恢复该节点原始权重，继续轮询；

这样的算法看起来简单，最终效果是：{a, a, a, a, a, b, c}，即前5次可能选中的都是a，这可能造成权重大的服务器造成过大压力的同时，小权重服务器还很闲。

平滑加权轮询

对普通加权轮询的改进。

概念解释，每个节点有三个权重变量，分别是：

(1) weight: 约定权重，即在配置文件或初始化时约定好的每个节点的权重。

(2) effectiveWeight: 有效权重，初始化为weight。

在通讯过程中发现节点异常，则-1；之后再次选取本节点，调用成功一次则+1，直达恢复到weight；此变量的作用主要是节点异常，降低其权重。

(3) currentWeight: 节点当前权重，初始化为0。

算法逻辑

(1) 轮询所有节点，计算当前状态下所有节点的effectiveWeight之和totalWeight；

(2) currentWeight = currentWeight + effectiveWeight; 选出所有节点中currentWeight中最大的一个节点作为选中节点；

(3) 选中节点的currentWeight = currentWeight - totalWeight；

基于以上算法，我们看一个例子：

这时有三个节点{a, b, c}，权重分别是{a=4, b=2, c=1}，共7次请求，初始currentWeight值为{0, 0, 0}，每次分配后的结果如下：

请求序号	请求前currentWeight值	选中节点	请求后currentWeight值
1	{c=1,b=2,a=4}	a	{c=1,b=2,a=-3}
2	{c=2,b=4,a=1}	b	{c=2,b=-3,a=1}
3	{c=3,b=-1,a=5}	a	{c=3,b=-1,a=-2}
4	{c=4,b=1,a=2}	c	{c=-3,b=1,a=2}
5	{c=-2,b=3,a=6}	a	{c=-2,b=3,a=-1}
6	{c=-1,b=5,a=3}	b	{c=-1,b=-2,a=3}
7	{c=0,b=0,a=7}	a	{c=0,b=0,a=0}

观察到七次调用选中的节点顺序为{a, b, a, c, a, b, a}，a节点选中4次，b节点选中2次，c节点选中1次，算法保持了currentWeight值从初始值{c=0,b=0,a=0}到7次调用后又回到{c=0,b=0,a=0}。

随机法

加权随机法

源地址哈希法

nginx负载均衡

轮询（默认）

weight

upstream bakend {  
  server 192.168.0.1 weight=4;  
  server 192.168.0.2 weight=1;  
}

ip_hash

同一ip分配至统一服务器，可以解决session问题

upstream bakend {  
  ip_hash;  
  server 192.168.0.1:80;  
  server 192.168.0.2:8080;  
}

fair

服务端响应时间短的优先分配

upstream backend {  
  server server1;  
  server server2;  
  fair;  
}

url_hash

对url进行hash

健康检查

负载均衡时又是需要检查服务器状态。

hash常见构造和处理冲突方法

发表于 2019-04-18 分类于 algorithm
本文字数： 242 阅读时长 ≈ 1 分钟

几种hash的构造和处理冲突方法的名字经常记混，记录一下。

构造方法

直接定址法

$H(key)=a*key+b$

除留余数法

$H(key)=key%p$

数字分析法
平方取中法
折叠法

处理冲突

开放定址

$H_i=(H(key)+d_i)%m$

线性探测

$d_i=0,1,2,…,m-1$

平方探测

$d_i=0^2,1^2,…,k^2,-k^2; k<=m/2$

再散列

$d_i=Hash_2(key)$

伪随机序列

链地址

同义词存在链表中。

一个简易的游戏2d场景管理实现

发表于 2019-04-18 更新于 2020-02-27 分类于 algorithm
本文字数： 29k 阅读时长 ≈ 26 分钟

任务要求

用编程语言实现一个服务器端的游戏2d场景管理模块，场景上包括了地图的信息，以及一些游戏元素，如NPC，树，石头，建筑等静态元素，地图设计尽可能大，场景上至少包含100个活动元素（玩家、NPC等）模拟随机行走（行走方式有：1.单步移动，2.两点寻路），活动元素不能穿越静态元素的位置。要求使用合理的数据结构及算法实现。
编程要求:

无需图形界面
地图尺寸为10000*10000个基础单位
活动元素随机行走触发随机事件，每秒移动一次
可以使用go/c++语言实现
Cpu利用率经可能低
建议开发周期不超过2周

实现

主要思路

使用网格法模拟地图
随机生成10000x10000的地图
地图大，要求CPU利用率低，没做内存要求，所以在合理的情况下尽量空间换时间
使用A Star算法做两点间路径搜索，但是必须做量级的优化
由于是静态地图，把大地图拆分为多个区块，在区块边上计算互通点，互通点描述区块间的连通性，预存区块内互通点间的路径
搜索使用堆和启发函数优化
经过拆分和预处理，每次寻路只需要搜索一次100x100的起始点到互通点到路径、一次100x100的区块间路径、一次100x100的互通点到目标点的路径。
经过优化，搜索区域从10000x10000降至3次100x100的空间。

代码在特殊情况有bug，但是数据庞大而随机没有继续调试，实现了主要功能。

//#define Debug
#include <bits/stdc++.h>
#include <unistd.h>
#include <signal.h>


using namespace std;

#define MAP_NULL 0
#ifdef Debug
const int MAPSIZE = 100;
const int BLOCKSIZE = 10;
#else
const int MAPSIZE = 10000;
const int BLOCKSIZE = 100;  //这里按照均分设计，如果不均分需要改动
#endif
const float EVENTPROBABLITY = 5.0 / MAPSIZE;  //根据地图尺寸计算每点触发事件概率
const int BLOCKNUM = MAPSIZE / BLOCKSIZE;
char MAP[MAPSIZE][MAPSIZE];

struct Point;
struct Block;
struct PathNode;

int calcBlockId(Point a);

Point calcBlockStartPoint(int bid);

Point calcBlockEndPoint(int bid);

PathNode *findBlockPath(Point src, Point dst);

int getMhtDis(Point a, Point b);

int getMhtDis(PathNode *a, PathNode *b);

typedef struct Point
{
    int x = -1;
    int y = -1;
    
    bool isInMap()
    {
        return x >= 0 && x < MAPSIZE && y >= 0 && y < MAPSIZE;
    }
    
    bool operator<(Point a) const
    {
        return x < a.x ? true : ((x == a.x) ? y < a.y : false);
    }
    
    bool operator>(Point a) const
    {
        return x > a.x ? true : ((x == a.x) ? y > a.y : false);
    }
    
    bool operator==(Point a) const { return x == a.x && y == a.y; }    //用于hash碰撞检测
    
    Point getUp() { return {x - 1, y}; }
    
    Point getDown() { return {x + 1, y}; }
    
    Point getLeft() { return {x, y - 1}; }
    
    Point getRight() { return {x, y + 1}; }
    
} Point;


struct PointPairHash
{
    size_t operator()(const pair<Point, Point> &p) const
    {    //assume the int is 32bit
        auto h1 = hash<long long>()((long long) (p.first.x << 31) + p.first.y);
        auto h2 = hash<long long>()((long long) (p.second.x << 31) + p.second.y);
        return h1 ^ h2;
    }
    
};

struct PointHash
{
    size_t operator()(const Point &p) const
    {
        return hash<long long>()((long long) (p.x << 31) + p.y);
    }
};


typedef struct Block
{
    int id;
    vector<Point> up, down, left, right;   //方向上的互通点
    unordered_map<pair<Point, Point>, vector<Point>*, PointPairHash> pathsMap;   //区块内互通点到其它互通点的路径
    unordered_map<Point, vector<Point>*, PointHash> connectedPointList;   //区块内一互通点可到达另一互通点的点对列表
    
    Point getStartPoint()
    {
        return calcBlockStartPoint(id);
    }
    
    Point getEndPoint()
    {
        return calcBlockEndPoint(id);
    }
    
    vector<Point> getAllConnectedPoints()
    {
        vector<Point> v;
        v.insert(v.end(), up.begin(), up.end());
        v.insert(v.end(), right.begin(), right.end());
        v.insert(v.end(), down.begin(), down.end());
        v.insert(v.end(), left.begin(), left.end());
        return v;
    }
} Block;
Block BLOCK[(BLOCKNUM) * (BLOCKNUM)];

typedef enum
{
    STATICNPC = 1, TREE = 2, STONE = 3, BUILDING = 4
} StaticItemType;
const int StaticItemTypeMaxValue = 5; //标记有几种静态元素,此处用于随机元素添加

typedef enum
{
    player = 1, ACTIVITYNPC = 2
} ActivityItemType;
const int ActivityItemTypeMaxValue = 3; //标记有几种动态元素,此处用于随机元素添加

class BoxArea
{
public:
    BoxArea()
    {
    }
    
    BoxArea(Point a, Point b)
    {
        if (a.x > b.x)
            std::swap(a, b);
        if (a.y > b.y)
            std::swap(a.y, b.y);
        L = a;
        R = b;
    }
    
    bool isInmap()
    {
        return L.isInMap() && R.isInMap();
    }
    
    int getLx() { return L.x; }
    
    int getLy() { return L.y; }
    
    int getRx() { return R.x; }
    
    int getRy() { return R.y; }
    
private:
    Point L, R;
};

typedef struct PathNode : Point
{
    int F = 0;
    int G = 0;
    int H = 0;
    PathNode *parent = nullptr;
    
    bool operator<(PathNode *a) const { return F < a->F; }
    
    bool operator>(PathNode *a) const { return F > a->F; }
    bool operator<(Point a) const
    {
        return x < a.x ? true : ((x == a.x) ? y < a.y : false);
    }
    
    bool operator>(Point a) const
    {
        return x > a.x ? true : ((x == a.x) ? y > a.y : false);
    }
    
    void operator=(Point a)
    {
        x = a.x;
        y = a.y;
    }
    
    PathNode(Point a)
    {
        x = a.x;
        y = a.y;
    }
} PathNode;
priority_queue<PathNode *, vector<PathNode *>, greater<PathNode *> > open;
set<pair<int, int> > openSet;
set<pair<int, int> > closed;
vector<PathNode *> FreeList;


void clearOpenQueue()
{
    //        while(open.empty())
    //            open.pop();
    open = priority_queue<PathNode *, vector<PathNode *>, greater<PathNode *> >();
}

int calcG(PathNode p)
{
    if (p.parent == nullptr)
        return 0;
    else
        return p.parent->G + 1;
}

int calcH(PathNode start, PathNode end)
{
    return abs(end.x - start.x) + abs(end.y - start.y);
}

int calcF(PathNode p)
{
    return p.G + p.H;
}

vector<PathNode> getRoundPoints(PathNode *loc) //remember to add it to freelist
{
    vector<PathNode> res;
    PathNode u(loc->getUp());
    PathNode d(loc->getDown());
    PathNode l(loc->getLeft());
    PathNode r(loc->getRight());
    if (u.isInMap())
        res.push_back(u);
    if (d.isInMap())
        res.push_back(d);
    if (l.isInMap())
        res.push_back(l);
    if (r.isInMap())
        res.push_back(r);
    return res;
}

PathNode *findPath(Point src, Point dst, Point start, Point end)    //build path list
{
    PathNode *first = new PathNode(src);
    PathNode *last = new PathNode(dst);
    FreeList.push_back(first);
    FreeList.push_back(last);
    open.push(first);
    openSet.insert(make_pair(first->x, first->y));
    while (!open.empty()) {
        PathNode *cur = open.top();
        //            cout<<cur->x<<','<<cur->y<<endl;
        open.pop();
        closed.insert(make_pair(cur->x, cur->y));
        
        auto roundPoints = getRoundPoints(cur);
        for (auto point:roundPoints) {
            if (MAP[point.x][point.y] != MAP_NULL || point<start || point>end) //有静态元素不能走,超出范围不搜索
                continue;
            if (closed.count(make_pair(point.x, point.y)))   //closed表已有
                continue;
            PathNode *p = new PathNode({point.x, point.y}); //remember to add it to freelist
            FreeList.push_back(p);
            if (!openSet.count(make_pair(p->x, p->y)))   //不在open表
            {
                p->parent = cur;
                p->G = calcG(*p);
                p->H = calcH(*p, *last);
                p->F = calcF(*p);
                
                open.push(p);
                openSet.insert(make_pair(p->x, p->y));
            } else {
                int tmpG = calcG(*p);
                if (tmpG < p->G) {
                    p->parent = cur;
                    p->G = tmpG;
                    p->F = calcF(*p);
                }
            }
            if (p->x == last->x && p->y == last->y) {
                clearOpenQueue();
                openSet.clear();
                closed.clear();
                return p;
            }
        }
    }
    
    clearOpenQueue();
    openSet.clear();
    closed.clear();
    return nullptr;
}

bool getPath(Point src, Point dst, vector<Point> &path)
{
    //ToDo
    int bid1, bid2;
    bid1 = calcBlockId(src);
    bid2 = calcBlockId(dst);
    PathNode *last = nullptr;
    if (bid1 == bid2)
        last = findPath(src, dst, calcBlockStartPoint(bid1), calcBlockEndPoint(bid1));
    else
        last = findPath(src, dst, {0, 0}, {MAPSIZE - 1, MAPSIZE - 1});
    
    if (last == nullptr)
        return false;
    while (last) {
        path.push_back({last->x, last->y});
        last = last->parent;
    }
    
    for (auto p:FreeList)     //free the freelist
        delete p;
    vector<PathNode *>().swap(FreeList);
    return true;
}


class StaticItem
{
public:
    StaticItem(StaticItemType type, BoxArea box)
    {
        if (!box.isInmap())
            throw "location exceed";
        this->type = type;
        this->box = box;
    }
    
    void putItemOnMap()
    {
        for (int i = box.getLy(); i <= box.getRy(); ++i)
            for (int j = box.getLx(); j <= box.getRx(); ++j)
                MAP[i][j] = MAP[i][j] ? '#' : type; //混合区域暂用#表示，因为目前静态元素表现形式一样，不用做过多区分
    }
    
private:
    StaticItemType type;
    BoxArea box;
};

class ActivityItem
{
public:
    Point loc;
    bool isMoving;
    vector<Point> path;
    ActivityItem(int id, Point loc, ActivityItemType type)
    {
        if (!loc.isInMap())
            throw "location exceed";
        this->id = id;
        this->loc = loc;
        this->type = type;
        isMoving = false;
    }
    
    int getPathSize()
    {
        return path.size();
    }
    
    bool oneStepMove(Point dst)
    {
        //移动在地图范围内，移动慢哈顿距离为1
        if (!dst.isInMap() || getMhtDis(loc, dst) != 1)
        {
            cout<<"the Point cannot move"<<endl;
            return false;
        }
        else
            cout<<id<<"move to "<<loc.x<<','<<loc.y<<endl;
        float t = rand() % 10 / 10.0;
        if (t < EVENTPROBABLITY)   //概率触发事件
            doSomeThing();
        return true;
    }
    
    void mergePath(vector<Point> &startPath, vector<Point> &blockPath, vector<Point> &endPath, vector<Point> &path)
    {
        /*
        // 正序
        path.insert(path.end(), startPath.rbegin(), startPath.rend());
        auto src = blockPath[blockPath.size()-1];
        for(int i=blockPath.size()-2;i>=0;--i)
        {
            path.pop_back();    //避免重复
            int bid = calcBlockId(src);
            vector<Point> *p;
            if(getMhtDis(src, blockPath[i])==1) //邻接互通点
            {
                path.push_back(src);
                path.push_back(blockPath[i]);
            }
            else if(src<blockPath[i])
            {
                p = BLOCK[bid].pathsMap[make_pair(src, blockPath[i])];
                path.insert(path.end(), p->rbegin(), p->rend());
            }
            else if(src>blockPath[i])
            {
                p = BLOCK[bid].pathsMap[make_pair(blockPath[i], src)];
                path.insert(path.end(), p->begin(), p->end());
            }
            src = blockPath[i];
        }
        path.insert(path.end(), endPath.rbegin(), endPath.rend());
         */
        path.insert(path.end(), endPath.begin(), endPath.end());
        auto src = blockPath[0];
        for(int i=1;i<blockPath.size();++i)
        {
            path.pop_back();    //避免重复
            int bid = calcBlockId(src);
            vector<Point> *p;
            if(getMhtDis(src, blockPath[i])==1) //邻接互通点
            {
                path.push_back(src);
                path.push_back(blockPath[i]);
            }
            else if(src<blockPath[i])
            {
                p = BLOCK[bid].pathsMap[make_pair(src, blockPath[i])];
                path.insert(path.end(), p->begin(), p->end());
            }
            else if(src>blockPath[i])
            {
                p = BLOCK[bid].pathsMap[make_pair(blockPath[i], src)];
                path.insert(path.end(), p->rbegin(), p->rend());
            }
            src = blockPath[i];
        }
        path.insert(path.end(), startPath.begin(), startPath.end());
    }
    
    bool moveTo(Point dst)
    {
        int startBlockId = calcBlockId(loc);
        int endBlockId = calcBlockId(dst);
        vector<Point> startPath, endPath;
        //ToDO
        vector<Point> startAll = BLOCK[startBlockId].getAllConnectedPoints();
        vector<Point> endAll = BLOCK[endBlockId].getAllConnectedPoints();
        PathNode *last = nullptr;
        bool found = false;
        for(auto start:startAll)
        {
            for(auto end:endAll)
            {
                getPath(loc, start, startPath);
                getPath(end, dst, endPath);
//                printf("start&&end:loc:%d,%d size:%d,%d\n", loc.x, loc.y, startPath.size(), endPath.size());

                if(startPath.empty()||endPath.empty())  //前提在区块边上的点路径包括自身
                    continue;
                last = findBlockPath(start, end);
                if(last== nullptr)
                    continue;
                vector<Point> cntPointPath;
                while(last)
                {
                    cntPointPath.push_back({last->x, last->y});
                    last = last->parent;
                }
                //                printf("pathSize: %d\n", path.size());
                for(auto p:FreeList)
                    delete p;
                vector<PathNode *>().swap(FreeList);
//                cout<<startPath.size()<<' '<<cntPointPath.size()<<' '<<endPath.size()<<endl;

                mergePath(startPath, cntPointPath, endPath, path);
                
//                for(auto &p:path)
//                    cout<<p.x<<','<<p.y<<' ';
//                cout<<endl;
                
                found = true;
                break;
            }
            if(found)
                break;
        }
        if(found)
        {
            isMoving = true;
        }
            
        return found;
    }
    
    void printPath()
    {
        cout << endl;
        while (path.size()) {
            Point t = path.back();
            path.pop_back();
            cout << t.x << ',' << t.y << ' ';
        }
        cout << endl;
    }
    
    void doSomeThing()
    {
        cout << "player " << id << " handle an event" << endl;
    }
    
    int getId()
    {
        return id;
    }
    
private:
    int id;
    ActivityItemType type;
    
};

vector<ActivityItem *> PLAYERS;


int getMhtDis(Point a, Point b)
{
    return abs(a.x - b.x) + abs(a.y - b.y);
}

int getMhtDis(PathNode *a, PathNode *b)
{
    return abs(a->x - b->x) + abs(a->y - b->y);
}

void setMapZero()
{
    memset(MAP, MAP_NULL, sizeof(MAP));
}


int myRand(int l, int r)
{
    int x;
    do {
        x = rand() % (r - l) + l;
    } while (x < l);
    return x;
}

void addRandomStaticItem(int l = 1, int r = 1)  //左闭右开
{
    if (r < l || l < 1)
        throw "wrong range";
    int itemNum = myRand(l, r);
    while (itemNum--) {
        Point t1, t2;
        t1 = {myRand(0, MAPSIZE), myRand(0, MAPSIZE)};  //这里直接使用了随机坐标，静态元素面积大概率偏大，可以改用根据面积随机
        t2 = {myRand(0, MAPSIZE), myRand(0, MAPSIZE)};
        //        std::cout<<t1.x<<','<<t1.y<<','<<t2.x<<','<<t2.y<<std::endl;
        BoxArea box(t1, t2);
        //        std::cout<<box.getLx()<<','<<box.getLy()<<','<<box.getRx()<<','<<box.getRy()<<std::endl;
        StaticItemType type((StaticItemType) myRand(1, StaticItemTypeMaxValue));
        StaticItem item(type, box);
        item.putItemOnMap();
    }
}

void addRandomActivityItem(int l = 1, int r = 1)
{
    int itemNum = myRand(l, r);
    for (int i = 1; i <= itemNum; ++i) {
        int id = i;
        Point t;
        do {
            t = {myRand(0, MAPSIZE), myRand(0, MAPSIZE)};
        } while (MAP[t.x][t.y] != MAP_NULL);
        ActivityItemType type((ActivityItemType) myRand(1, ActivityItemTypeMaxValue));
        ActivityItem *item = new ActivityItem(id, t, type);
        PLAYERS.push_back(item);
    }
}


void printMap()
{
    printf("%4c", ' ');
    for (int i = 0; i < MAPSIZE; ++i)
        printf("%4d", i);
    puts("");
    for (int i = 0; i < MAPSIZE; ++i) {
        printf("%4d", i);
        for (int j = 0; j < MAPSIZE; ++j) {
            printf("%4d", (int) MAP[i][j]);
        }
        puts("");
    }
}

int calcBlockId(Point a)
{
    int id = 0;
    id += BLOCKNUM * (a.x / BLOCKSIZE);
    id += a.y / BLOCKSIZE;
    return id;
}

Point calcBlockStartPoint(int bid)
{
    Point t = {bid / (BLOCKNUM) * BLOCKSIZE, (bid % BLOCKNUM) * BLOCKSIZE};
    return t;
}

Point calcBlockEndPoint(int bid)
{
    Point t = calcBlockStartPoint(bid);
    return {t.x + BLOCKSIZE - 1, t.y + BLOCKSIZE - 1};
}



void initBlock()
{
    for (int i = 0; i < BLOCKNUM * BLOCKNUM; ++i)
        BLOCK[i].id = i;
}

vector<int> getRoundBlockId(int bid)
{
    vector<int> v;
    int up, right, down, left;
    up = bid - BLOCKNUM;
    right = bid + 1;
    down = bid + BLOCKNUM;
    left = bid - 1;
    if (up >= 0 && up < BLOCKNUM * BLOCKNUM)
        v.push_back(up);
    if (right >= 0 && right < BLOCKNUM * BLOCKNUM)
        v.push_back(right);
    if (down >= 0 && down < BLOCKNUM * BLOCKNUM)
        v.push_back(down);
    if (up >= 0 && up < BLOCKNUM * BLOCKNUM)
        v.push_back(left);
    return v;
}

void getConnectPoint(Block *block1, Block *block2)
{
    if (block1->id == block2->id)
        throw "block id wrong";
    Block *b1, *b2;
    b1 = block1;
    b2 = block2;
    if (block1->id > block2->id) {
        b1 = block2;
        b2 = block1;
    }
    if (b1->id + 1 == b2->id)    //block2 on the right
    {
        Point start, end;
        start = {b1->id / (BLOCKNUM) * BLOCKSIZE, ((b1->id + 1) % (BLOCKNUM)) * BLOCKSIZE - 1};
        end = {start.x + BLOCKSIZE - 1, start.y};
        int low, high;
        low = high = start.x;
        while (high <= end.x) {
            for (int i = start.x; i <= end.x; ++i) {    //确保数组有序，后面有二分
                if (MAP[i][start.y] == MAP_NULL && MAP[i][start.y + 1] == MAP_NULL)
                    ++high;
            }
            int mid;
            mid = (low + high) >> 1;
            if (MAP[mid][start.y] == MAP_NULL && MAP[mid][start.y + 1] == MAP_NULL) {
                b1->right.push_back({mid, start.y});
                b2->left.push_back({mid, start.y + 1});
            }
            low = ++high;
        }
    } else            //block2 on the bottom, assume the data is legal
    {
        Point start, end;
        start = {(b1->id / (BLOCKNUM) + 1) * BLOCKSIZE - 1, (b1->id % (BLOCKNUM)) * BLOCKSIZE};
        end = {start.x, start.y + BLOCKSIZE - 1};
        int left, right;
        left = right = start.y;
        while (right <= end.y) {
            for (int i = start.y; i <= end.y; ++i) {    //确保数组有序，后面有二分
                if (MAP[start.x][i] == MAP_NULL && MAP[start.x + 1][i] == MAP_NULL)
                    ++right;
            }
            int mid;
            mid = (left + right) >> 1;
            if (MAP[start.x][mid] == MAP_NULL && MAP[start.x + 1][mid] == MAP_NULL) {
                b1->down.push_back({start.x, mid});
                b2->up.push_back({start.x + 1, mid});
            }
            left = ++right;
        }
    }
}

void preProcessBlock(Block &block)
{
    vector<Point> all;
    for (auto p:block.up)
        all.push_back(p);
    for (auto p:block.right)
        all.push_back(p);
    for (auto p:block.down)
        all.push_back(p);
    for (auto p:block.left)
        all.push_back(p);
    if(block.id%10==0)
        cout << "process block "<<block.id << ", cntPointNum:" << all.size() << endl;
    for (int i = 0; i < all.size() - block.left.size(); ++i) {
        int j;
        if (i < block.up.size())
            j = block.up.size();
        else if (i < block.up.size() + block.right.size())
            j = block.up.size() + block.right.size();
        else    //else if(i<all.size()-block.left.size())
            j = all.size() - block.left.size();
        for (; j < all.size(); ++j) {
            Point a, b;
            a = all[i];
            b = all[j];
            if (a == b)    //避免角点与自身计算
                continue;
            if (a > b) //避免重复计算路径，压缩存储空间，但是后面要判断路径方向
                swap(a, b);
            if(block.pathsMap.count({a, b}))
                continue;
            vector<Point> *path;
            path = new vector<Point> ();
            if (getPath(a, b, *path)) {
                //                cout<<a.x<<','<<a.y<<' '<<b.x<<','<<b.y<<endl;
                if(!block.connectedPointList.count(a))
                    block.connectedPointList.insert(make_pair(a, new vector<Point> ()));
                block.connectedPointList[a]->push_back(b);
                if(!block.connectedPointList.count(b))
                    block.connectedPointList.insert(make_pair(b, new vector<Point> ()));
                block.connectedPointList[b]->push_back(a);
                //                cout<<block.connectedPointList.size()<<endl;
                block.pathsMap.insert(make_pair(make_pair(a, b), path));
                //                cout<<block.pathsMap.size()<<endl;
            }
            //            printf("<%d,%d>,<%d,%d>:%d\n", a.x,a.y,b.x,b.y, path.size());
        }
    }
    //    if(block.id%100==0)
    //        cout<<block.id<<endl;
}

void preProcessMap()
{
    for (int i = 0; i < BLOCKNUM * BLOCKNUM; ++i) {
        if (i % BLOCKSIZE == BLOCKNUM - 1)
            continue;
        getConnectPoint(&BLOCK[i], &BLOCK[i + 1]);
    }
    for (int i = 0; i < BLOCKNUM * BLOCKNUM - BLOCKNUM; ++i) {
        getConnectPoint(&BLOCK[i], &BLOCK[i + BLOCKNUM]);
    }
    
    for (auto &block:BLOCK)
        preProcessBlock(block);
}

vector<Point> getRoundBLockConnectedPoints(PathNode *cur)   //要求方向上互通点数组有序
{
    Point t = {cur->x, cur->y};
    int bid = calcBlockId({cur->x, cur->y});
    vector<Point> v;
    auto test = BLOCK[bid].connectedPointList;
    if (BLOCK[bid].connectedPointList.count(t))
        v.insert(v.end(), BLOCK[bid].connectedPointList[t]->begin(), BLOCK[bid].connectedPointList[t]->end());
    //遇到角点可能会push两个点
    if (binary_search(BLOCK[bid].up.begin(), BLOCK[bid].up.end(), t))
        v.push_back({t.x - 1, t.y});
    if (binary_search(BLOCK[bid].right.begin(), BLOCK[bid].right.end(), t))
        v.push_back({t.x, t.y + 1});
    if (binary_search(BLOCK[bid].down.begin(), BLOCK[bid].down.end(), t))
        v.push_back({t.x + 1, t.y});
    if (binary_search(BLOCK[bid].left.begin(), BLOCK[bid].left.end(), t))
        v.push_back({t.x, t.y - 1});
    return v;
}

PathNode *findBlockPath(Point src, Point dst)
{
    PathNode *first = new PathNode(src);
    PathNode *last = new PathNode(dst);
    FreeList.push_back(first);
    FreeList.push_back(last);
    open.push(first);
    openSet.insert(make_pair(first->x, first->y));
    while (!open.empty()) {
        PathNode *cur = open.top();
        //            cout<<cur->x<<','<<cur->y<<endl;
        open.pop();
        closed.insert(make_pair(cur->x, cur->y));
        
        auto roundPoints = getRoundBLockConnectedPoints(cur);
        for (auto point:roundPoints) {
            if (MAP[point.x][point.y] != MAP_NULL) //有静态元素不能走
                throw "Connected Points wrong";
            if (closed.count(make_pair(point.x, point.y)))   //closed表已有
                continue;
            PathNode *p = new PathNode({point.x, point.y}); //remember to add it to freelist
            FreeList.push_back(p);
            if (!openSet.count(make_pair(p->x, p->y)))   //不在open表
            {
                p->parent = cur;
                if (getMhtDis(p, cur) == 1) {
                    p->G = cur->G + 1;
                } else {
                    Point a = {cur->x, cur->y};
                    Point b = {p->x, p->y};
                    int bid = calcBlockId(a);
                    bool reverse = false;
                    
                    if (a > b)
                        reverse = true;
                    if (reverse)
                        p->G = BLOCK[bid].pathsMap[make_pair(b, a)]->size() -
                        1;   //pair<a,b>取自getRoundBLockConnectedPoints确保size不为0,区块间互通点曼哈顿距离大于1
                    else
                        p->G = BLOCK[bid].pathsMap[make_pair(a, b)]->size() - 1;
                }
                p->H = getMhtDis(p, last);
                p->F = p->G + p->H;
                
                open.push(p);
                openSet.insert(make_pair(p->x, p->y));
            } else {
                int tmpG;
                if (p->parent)
                {
                    if (getMhtDis(p, p->parent) == 1)
                    {
                        tmpG = p->parent->G + 1;
                    }
                    else
                    {
                        Point a = {p->parent->x, p->parent->y};
                        Point b = {p->x, p->y};
                        int bid = calcBlockId(a);
                        bool reverse = false;
                        
                        if (a > b)
                            reverse = true;
                        tmpG = p->parent->G;
                        if (reverse)
                            tmpG += BLOCK[bid].pathsMap[make_pair(b, a)]->size() -
                            1;   //pair<a,b>取自getRoundBLockConnectedPoints确保size不为0,区块间互通点曼哈顿距离大于1
                        else
                            tmpG += BLOCK[bid].pathsMap[make_pair(a, b)]->size() - 1;
                    }
                }
                else
                    tmpG = 0;
                
                if (tmpG < p->G) {
                    p->parent = cur;
                    p->G = tmpG;
                    p->F = p->G + p->H;
                }
            }
            if (p->x == last->x && p->y == last->y) {
                clearOpenQueue();
                openSet.clear();
                closed.clear();
                return p;
            }
        }
    }
    
    clearOpenQueue();
    openSet.clear();
    closed.clear();
    return nullptr;
}


void timer(int sig)
{
    if(SIGALRM == sig)
    {
        for (auto &player:PLAYERS)
        {
            int r = myRand(0, 30);
            if(player->isMoving)
            {
                if(player->getPathSize()!=0)
                    player->path.pop_back();
                else
                    player->isMoving = false;
                continue;
            }
            if(r<7)
                player->oneStepMove(player->loc.getUp());
            else if(r<14)
                player->oneStepMove(player->loc.getRight());
            else if(r<21)
                player->oneStepMove(player->loc.getDown());
            else if(r<28)
                player->oneStepMove(player->loc.getLeft());
            else
                player->moveTo({myRand(0, MAPSIZE), myRand(0, MAPSIZE)});
                
        }
        alarm(1);       //重新继续定时1s
    }
    
    return ;
}


int main(int argc, const char *argv[])
{
    srand((unsigned)time(0));
    addRandomStaticItem(50, 150);
    
    addRandomActivityItem(100, 1000);
    
    initBlock();
    preProcessMap();
    cout << "Finished" << endl;
    getchar();
    
    
#ifdef Debug
//    printMap();
#endif
    
    signal(SIGALRM, timer); //注册安装信号
    
    alarm(1);       //触发定时器
    
    getchar();
    
    return 0;
}

C++11 匿名函数

发表于 2019-04-17
本文字数： 1.9k 阅读时长 ≈ 2 分钟

表达式

[capture](parameters)->return-type{body}

如果没有参数，（）括号、返回值可以省略。

example：

[](int x, int y) { return x + y; } // 隐式返回类型
[](int& x) { ++x; }   // 没有return语句 -> lambda 函数的返回类型是'void'
[]() { ++global_x; }  // 没有参数,仅访问某个全局变量
[]{ ++global_x; }     // 与上一个相同,省略了()

显示指定返回类型

[](int x, int y) -> int { int z = x + y; return z; }

引用外部变量

Lambda函数可以引用在它之外声明的变量. 这些变量的集合叫做一个闭包. 闭包被定义在Lambda表达式声明中的方括号[]内. 这个机制允许这些变量被按值或按引用捕获.下面这些例子就是:

[]        //未定义变量.试图在Lambda内使用任何外部变量都是错误的.
[x, &y]   //x 按值捕获, y 按引用捕获.
[&]       //用到的任何外部变量都隐式按引用捕获
[=]       //用到的任何外部变量都隐式按值捕获
[&, x]    //x显式地按值捕获. 其它变量按引用捕获
[=, &z]   //z按引用捕获. 其它变量按值捕获

函数作为参数传递

如果用户想把lambda函数做为一个参数来传递, 那么形参的类型必须是模板类型或者必须能创建一个std::function类似的对象去捕获lambda函数.使用 auto关键字可以帮助存储lambda函数。

auto my_lambda_func = [&](int x) { /*...*/ };
auto my_onheap_lambda_func = new auto([=](int x) { /*...*/ });

#include<functional>
#include<vector>
#include<iostream>
double eval(std::function<double(double)> f, double x = 2.0){return f(x);}
int main()
{
     std::function<double(double)> f0    = [](double x){return 1;};
     auto                          f1    = [](double x){return x;};
     decltype(f0)                  fa[3] = {f0,f1,[](double x){return x*x;}};
     std::vector<decltype(f0)>     fv    = {f0,f1};
     fv.push_back                  ([](double x){return x*x;});
     for(int i=0;i<fv.size();i++)  std::cout << fv[i](2.0) << "\n";
     for(int i=0;i<3;i++)          std::cout << fa[i](2.0) << "\n";
     for(auto &f : fv)             std::cout << f(2.0) << "\n";
     for(auto &f : fa)             std::cout << f(2.0) << "\n";
     std::cout << eval(f0) << "\n";
     std::cout << eval(f1) << "\n";
     return 0;
}

ref

wiki

常用概率公式

发表于 2019-04-13 更新于 2019-04-16 分类于 math
本文字数： 1.9k 阅读时长 ≈ 2 分钟

古典概率

一般说来,如果在全部可能出现的基本事件范围内构成事件A的基本事件有a个,不构成事件A的事件有b个,则出现事件A的概率为:

$$P(A)=\frac{a}{a+b}$$

例子:

同时掷两枚硬币，可能出现正正、反反、正反、反正四种可能的结果，每种可能出现概率1/4

条件概率公式

$$P(A|B)=\frac{P(AB)}{P(B)}$$

描述：

公式中P(AB)为事件AB的联合概率，P(A|B)为条件概率，表示在B条件下A的概率，P(B)为事件B的概率。

例子：

有一同学，考试成绩数学不及格的概率是0.15，语文不及格的概率是0.05，两者都不及格的概率为0.03，在一次考试中，已知他数学不及格，那么他语文不及格的概率是多少？
记事件A为“数学不及格”，事件B为“语文不及格”,则P(A)=0.15 P(B)=0.05, P(AB)=0.03 则P(B|A)=P(AB)/P(A)=0.2

推广：

上述乘法公式可推广到任意有穷多个事件时的情况。

设$A_1,A_2,…A_n$为任意n 个事件（n≥2）且 $P(A_1A_2 \cdots A_n)>0$，则$P(A_1,A_2,…A_n) = P(A_1)p(A_2|A_1) \cdots P(A_n|A_1A_2 \cdots A_n-1)$

3.全概率公式

$$P(B)=\sum_{i=1}^{n}P(A_i)P(B|A_i)$$

描述：

公式表示若事件A1，A2，…，An构成一个完备事件组且都有正概率，则对任意一个事件B都有公式成立。

例子：

首先建立一个完备事件组的思想,其实全概就是已知第一阶段求第二阶段,比如第一阶段分A B C三种,然后A B C中均有D发生的概率,最后让你求D的概率

P(D)=P(A)P(D/A)+P(B)P(D/B)+P(C)*P(D/C})

例子：

甲乙丙三个车间生产同一种产品，其产量分别占总产量的25%，35%，40%，次品率率分别是5%，4%，2%，从这一产品中取任一ji件，则是次品的概率是。

设P(A1)为抽到甲车间的概率，P(A2)为抽到乙车间的概率，P(A3)为抽到丙车间的概率。

设P(B)为抽到次品的概率。

则P(B)=P(A1)P(B|A1)+P(A2)P(B|A2)+P(A3)P(B|A3)=25%5%+35%4%+40%2%=0.0345

4.贝叶斯公式

$$P(B_i|A)=\frac{P(B_i)P(A|B_i)}{\sum_{j=1}^{n}P(B_j)(A|B_j)}$$
公式描述：

公式中，事件Bi的概率为P(Bi)，事件Bi已发生条件下事件A的概率为P(A│Bi)，事件A发生条件下事件Bi的概率为P(Bi│A)。

例子：

已知在所有男子中有5%，在所有女子中有0.25%有色盲症，随机抽一人发现患有色盲症，问其为男子的概率是是多少？（设男子和女子的人数相等)

设A表示抽到为男子，B表示抽到是女子，C表示ch抽到的人有色盲症。

则P(A)=P(B)=1/2, P(C|A) = 0.05, P(C|B) = 0.0025

由Bayes公式有

P(A|C) = P(A)P(C|A)/P(A)P(C|A)+P(B)P(C|B) = 0.50.05/0.50.05+0.5*0.0025 = 95%

0-1分布

略
$$E(X)=p, D(X)=p(1-p)$$

二项分布

$$P { X=k } =C_n^kp^kq^{n-k}, k=0,1,2,…,n$$
$$E(X)=np, D(X)=np(1-p)$$

几何分布

在独立地重复做一系列伯努利试验中，若每次试验成功率为p，则在k次试验时才首次试验成功地概率服从几何分布。
$$P { X=k } = pq^{k-1}, k=1,2,…$$
$$E(X)=\frac{1}{p}, D(X)=\frac{1-p}{p^2}$$

超几何分布

$$P { X=k } = \frac{C_m^kC_{N-M}^{n-k}}{C_N^n}, k=l_1,…,l_2$$
其中l1=max(0,n-N+M),l2=min(M,n).则称随机变量X服从参数为n,N,M的超几何分布.

如果N件产品中含有M件次品，从中任意一次取出n件（或从中一件接一件不放回取n件），令X=抽取的n件产品中的次品件数，则X服从参数为n,N,M的超几何分布

如果
如果N件产品中含有M件次品，从中一件接一件有放回取n次,则X服从B(n,M/N)

泊松分布

均匀分布

$$E(X)=\frac{a+b}{2}, D(X)=\frac{(b-a)^2}{12}$$

AIRobot

AIRobot quick note

GitHub E-Mail