精华内容
下载资源
问答
  • 感悟线段

    2019-08-05 19:49:48
    其实线段树的数据结构没什么可说的,但是怎么用好它就有得说了。 具体的来说就是: 首先就是有段关系了,这个是第一位的。 接着就是有大小关系了,这个是第二位的。 再者就是数据大,这个是次要的。 只要满足...

    其实线段树的数据结构没什么可说的,但是怎么用好它就有得说了。

    具体的来说就是:

    首先就是有段关系了,这个是第一位的。

    接着就是有大小关系了,这个是第二位的。

    再者就是数据量大,这个是次要的。

    只要满足了这三个条件,就是用线段树的时候了。

    如何理解段呢?比如说让你统计小于200的数据有多少个。这个就是段了。

    至于大小就是小于200的200了。

    (1)1 3 2 4 5 63 563 23 46 56 23 455 …… 888 这个例子是落在888以前的。

    (2)当然还是段中段,这个就不解释了。

     

    下面来贴出一道相关的题目。

    http://acm.swust.edu.cn/oj/contest/29/825/

     

    View Code
    #include "iostream"
    #include "cstdio"
    #include "cstring"
    #include "string"
    #include "algorithm"
    using namespace std;
    #define Maxn 100005
    struct Animals
    {
    int s, v;
    bool Flag;
    };
    Animals RT[Maxn*2];
    bool Cmp(Animals a, Animals b)
    {
    return (a.s<b.s);
    }
    struct Node
    {
    int Left, Right, Sum;
    };
    Node Tree[Maxn*4];
    void BTree(int x, int y, int p)
    {
    Tree[p].Left = x;
    Tree[p].Right = y;
    Tree[p].Sum = 0;
    if(x<y)
    {
    int Mid = (x+y)/2;
    BTree(x, Mid, p<<1); //2*p
    BTree(Mid+1, y, p<<1|1); //2*p+1 //mid+1哈,不然stack overflow
    }
    }
    void Add(int x, int p)
    {
    if(Tree[p].Left==Tree[p].Right && Tree[p].Left==x)
    {
    Tree[p].Sum=(Tree[p].Sum+1)%2012;
    return;
    }
    int Mid=(Tree[p].Left+Tree[p].Right)/2;
    if(x<=Mid) Add(x, p<<1);
    else Add(x, p<<1|1);
    Tree[p].Sum = (Tree[p<<1].Sum+Tree[p<<1|1].Sum)%2012;
    }
    long long Query(int x, int y, int p)
    {
    if(Tree[p].Left==x && Tree[p].Right==y) return Tree[p].Sum;
    int Mid = (Tree[p].Left+Tree[p].Right)/2;
    if(y<=Mid) return Query(x, y, p<<1);
    else if(x>=Mid+1) return Query(x, y, p<<1|1);
    else return (Query(x, Mid, p<<1)+Query(Mid+1, y, p<<1|1))%2012;
    }
    int N;
    int main()
    {
    int Max=0;
    while(scanf("%d", &N)!=EOF)
    {
    for(int i=0; i<N; i++)
    {
    scanf("%d%d", &RT[i].s, &RT[i].v);
    RT[i].Flag = true;
    Max = max(Max, RT[i].v);
    }
    for(int i=N; i<2*N; i++)
    {
    scanf("%d%d", &RT[i].s, &RT[i].v);
    RT[i].Flag = false;
    Max = max(Max, RT[i].v);
    }
    sort(RT, RT+2*N, Cmp);
    BTree(1, Max, 1);
    int Ans = 0;
    for(int i=0; i<2*N; i++)
    {
    if(RT[i].Flag)
    {
    if(RT[i].v==Max) continue;
    Ans=(Ans+Query(RT[i].v+1, Max, 1))%2012;
    }
    else Add(RT[i].v, 1);
    }
    printf("%d\n", Ans);
    }
    }



    转载于:https://www.cnblogs.com/o8le/archive/2012/03/31/2427756.html

    展开全文
  • 增加树的度可以减少树的高度,比如每个树的度最大是1000时;这样就形成了一颗m叉的平衡查找树。这正是B+树的核心,也是众多存储引擎使用的数据结构。 当然,B+树在存储引擎的实现要...
  • 决策算法梳理

    2019-04-03 21:51:21
    那么,怎么衡量不确定性的变化的大小呢?怎么定义呢? 一,起码不是个负数吧,不然说句话还偷走信息呢~ 二,起码信息和信息之间可以相加吧! 三,刚刚已经提过,信息跟概率有关系,但我们应该会觉得,信息...

    信息论基础(熵 联合熵 条件熵 信息增益 基尼不纯度)

    : 信息是不是可以量化?为什么有的信息量大有的信息量小?那么,不确定性的变化跟什么有关呢?
    一,跟事情的可能结果的数量有关;二,跟概率有关。
    那么,怎么衡量不确定性的变化的大小呢?怎么定义呢?
    一,起码不是个负数吧,不然说句话还偷走信息呢~
    二,起码信息量和信息量之间可以相加吧!
    三,刚刚已经提过,信息量跟概率有关系,但我们应该会觉得,信息量是连续依赖于概率的吧!
    四,刚刚也提过,信息量大小跟可能结果数量有关。假如每一个可能的结果出现的概率一样,那么对于可能结果数量多的那个事件,新信息有更大的潜力具有更大的信息量,因为初始状态下不确定性更大。
    信息熵就是平均而言发生一个事件我们得到的信息量大小。所以数学上,信息熵其实是信息量的期望。
    H=xϵUP(x)logP(x)H=-\sum_{x\epsilon U}{P(x)\log P(x)}
    讨论下二元随机变量的情况,为了直观解释和记忆,先给出如下图解:
    在这里插入图片描述
     
    **联合熵:**先说联合熵的定义,代表X,Y同时发生的不确定性;公式为在这里插入图片描述
    从上图中理解就是两个大圆的面积。

    再说条件熵,代表在已知一个变量发生的条件下,另一个变量发生所新增的不确定性;公式为:在这里插入图片描述
    有兴趣的朋友可以自己推导一下是如何从(1)式到(2)式的,从上图中理解就是两个大圆去掉其中一个大圆所剩下的面积。

    最后定义互信息,其中的一个定义就是在已知X发生的条件下,Y不确定性减少的程度,这个定义在ID3算法中也叫信息增益,计算公式可以理解为:在这里插入图片描述
    有兴趣的朋友可以自己推导一下是如何从(1)式到(2)式的,从上图理解就是两个大圆相交的面积,所以互信息是对偶的。

    另一个定义是这样
    在这里插入图片描述
    等式右边的值叫做KL散度,相对熵,或者交叉熵等等,所以说理解了交叉熵就理解了互信息的第二个定义。

    定义交叉熵,代表两个概率分布(函数)的相似度,计算公式为:
    在这里插入图片描述

    信息增益:
    信息增益率:

    在这里插入图片描述
    **基尼系数:**分类问题中,假设有K个类别,第k个类别的概率为pk, 则基尼系数的表达式为:

    Gini(p)=1k=1Kpk2Gini(p)=1−∑_{k=1}^Kp_k^2

    决策树的不同分类算法(ID3算法、C4.5、CART分类树)的原理及应用场景

    ID3算法中我们使用了信息增益来选择特征,信息增益大的优先选择。在C4.5算法中,采用了信息增益比来选择特征,以减少信息增益容易选择特征值多的特征的问题。但是无论是ID3还是C4.5,都是基于信息论的熵模型的,这里面会涉及大量的对数运算。能不能简化模型同时也不至于完全丢失熵模型的优点呢?有!CART分类树算法使用基尼系数来代替信息增益比,基尼系数代表了模型的不纯度,基尼系数越小,则不纯度越低,特征越好。

    回归树原理

    决策树防止过拟合手段

    1. 预剪枝(pre-pruning)
    2. 后剪枝(post-pruning)
    首先剪枝(pruning)的目的是为了避免决策树模型的过拟合。因为决策树算法在学习的过程中为了尽可能的正确的分类训练样本,不停地对结点进行划分,因此这会导致整棵树的分支过多,也就导致了过拟合。决策树的剪枝策略最基本的有两种:预剪枝(pre-pruning)和后剪枝(post-pruning):

    预剪枝(pre-pruning):预剪枝就是在构造决策树的过程中,先对每个结点在划分前进行估计,若果当前结点的划分不能带来决策树模型泛华性能的提升,则不对当前结点进行划分并且将当前结点标记为叶结点。
    后剪枝(post-pruning):后剪枝就是先把整颗决策树构造完毕,然后自底向上的对非叶结点进行考察,若将该结点对应的子树换为叶结点能够带来泛华性能的提升,则把该子树替换为叶结点。

    模型评估

    混淆矩阵
    混淆矩阵也称误差矩阵,是表示精度评价的一种标准格式,用n行n列的矩阵形式来表示。在机器学习的模型评价中用到的很多指标都来源于对混淆矩阵结果的运算。

    下图是常见的二分类问题的混淆矩阵:
    在这里插入图片描述

    其中列表示模型预测值,行表示数据真实值。

    根据图中的交叉结果会出现以下4种状况:

    真实值为0,预测值也为0,用字母TP(True Positive)表示真正类数据。
    真实值为0,预测值为1,用字母FN(False Negative)表示假反类数据。
    真实值为1,预测值也为1,用字母TN(True Negative)表示真反类数据。
    真实值为1,预测值为0,用字母FP(False Positive)表示假正类数据。
    其中,True、False表示预测结果正确与否,Positive、Negative表示预测倾向为正类或者反类。

    准确率、F1-Score、ROC曲线
    整体分类结果的准确率accuracy=(TP+TN)/(TP+FN+TN+FP)

    预测为正类的准确率,即在被预测为正类中真正是正类样本比例,又称精确率或查准率precision=TP/(TP+FP)

    真实为正类的准确率,即在所有正类样本中被正确识别的比例,又称召回率或查全率TPR/recall=TP/(TP+FN)

    F1-score是综合precision和recall两个指标的判断指标,
    F1-Score=2/(1/precision+1/recall)=2precisionrecall/(precision+recall),
    F1-Score的值在0到1之间,越大越好。

    真实FP为负类预测错误率,即负类被预测为正类占所有真实负类的比例FPR=FP/(FP+TN)

    ROC曲线是根据一系列不同的二分类方式(分界值或决定阈),以TPR为纵坐标,FPR为横坐标绘制的曲线。实际上ROC曲线是对一系列的TPR和FPR的值所构成点的连线绘制,而其中每一个点的都代表一个概率分界值,即把大于分界值得部分分为正类,小于分界值的分为负类。对于模型而言,我们计算出每个样本属于正类的概率,然后对概率值按顺序排序,计算每个概率作为分界点的TPR和FPR,然后绘制曲线,就构成了模型的ROC曲线。

    在这里插入图片描述

    在样本有限的情况下,ROC曲线通常不是一条平滑的曲线,而是锯齿形的,数据较多的情况下,曲线会接近平滑。同时我们也可以通过计算 AUC(Area Under roc Cure)来做为评价指标。

    sklearn参数详解,Python绘制决策树

    在这里插入图片描述

    展开全文
  • 【JTS】利用JTS生成R索引

    千次阅读 2017-07-30 22:30:51
    前言因为,笔者最近在做一个大数据...那么怎么知道目前窗口大小内的有哪些点位信息呢,这个时候,R树的索引就出现了,可以很好地解决这个问题。利用一个矩形框(浏览器窗口大小)来进行R树索引就可以找出矩形框内的点位

    前言

    因为,笔者最近在做一个大数据量地图在线展示的项目,因此需要利用一些手段来提升效率,例如地图缩放的时候,需要展示浏览器窗口下的实时点位,轨迹等信息。在大比例尺下(也就是放大级别较大的时候),因此只需要展示目前这个窗口大小内的数据。那么怎么知道目前窗口大小内的有哪些点位信息呢,这个时候,R树的索引就出现了,可以很好地解决这个问题。利用一个矩形框(浏览器窗口大小)来进行R树索引就可以找出矩形框内的点位了。

    R树索引是一种空间数据索引,具有高效的特点,在现实生活中,R树可以用来存储地图上的空间信息,例如餐馆地址,或者地图上用来构造街道,建筑,湖泊边缘和海岸线的多边形。然后可以用它来回答“查找距离我2千米以内的博物馆”,“检索距离我2千米以内的所有路段”(然后显示在导航系统中)或者“查找(直线距离)最近的加油站”这类问题。R树还可以用来加速使用包括大圆距离在内的各种距离度量方式的最邻近搜索。

    具体原理和用途可以参考下面两个网页:

    R树维基百科
    R树索引原理

    而目前有很多成熟的第三方库提供了这个功能,例如本文用到的JTS。

    JTS的开发文档和相应的jar包的下载地址:JTS下载

    JTS提供了如下的空间数据类型,还提供了读取各种空间描述文件(WTK等),线简化,空间操作(求交,计算距离,计算外包矩形等),建立空间索引等多种算法。

    Point
    MultiPoint
    LineString
    LinearRing 封闭的线条
    MultiLineString 多条线
    Polygon
    MultiPolygon
    GeometryCollection 包括点,线,面

    里面最主要的几个类,GeometryFactory,Geometry,Envelope以及上面提到的几种常用数据类型。

    因为本文中主要用到空间索引和空间拓扑关系的计算,因此下面重点讲解一下相关的内容。

    1,几个概念

    Geometry类:所有的空间数据类型,点,线,面,多点,环,多边形等等都是继承自Geometry类的。
    Envelope类:该类就是描述一个空间几何对象的外包矩形,由max_x,max_y,min_x,min_y组成。

    2,空间关系

    空间关系主要是由九交模型来描述的,九交模型的讲解可以参考:九交模型的讲解

    至于在JTS中的对应的关系,就是以下几种:
    这里写图片描述

    3,空间索引

    空间索引有很多种,下面就介绍网格索引和R树索引,这部分很成熟,网格索引是最原始的空间索引了,R树稍微“时髦”一点,效率更高。
    这两个可以参看:
    地理信息系统原理在线教程——空间索引
    深入浅出空间索引:为什么需要空间索引
    深入浅出空间索引:2

    相应的,如何利用JTS实现R树索引呢?

    以下是相应的代码

    SpatialUtil.java

    package util;
    
    import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map.Entry;
    
    import com.vividsolutions.jts.geom.Coordinate;
    import com.vividsolutions.jts.geom.CoordinateSequences;
    import com.vividsolutions.jts.geom.Envelope;
    import com.vividsolutions.jts.geom.Geometry;
    import com.vividsolutions.jts.geom.GeometryFactory;
    import com.vividsolutions.jts.geom.LineString;
    import com.vividsolutions.jts.geom.LinearRing;
    import com.vividsolutions.jts.geom.MultiPoint;
    import com.vividsolutions.jts.geom.Polygon;
    import com.vividsolutions.jts.geom.impl.CoordinateArraySequence;
    import com.vividsolutions.jts.index.strtree.STRtree;
    
    import config.GeoConfig;
    import dao.QueryTrail;
    import entity.CompareValue;
    import entity.GPSPoint;
    import entity.Grid;
    import entity.Line;
    import entity.Point;
    import io.vertx.core.Vertx;
    import io.vertx.core.buffer.Buffer;
    import io.vertx.core.json.JsonObject;
    import io.vertx.ext.web.client.HttpResponse;
    import io.vertx.ext.web.client.WebClient;
    
    public class SpatialUtil {
        static String result=new String();
        //下面是我用高德地图API和JTS求解武汉市的边界多边形之后,求解出的武汉的外包矩形范围(里面用了vertx中的client)
        public static void getPolygonofWuhan(String[] args) {
            Vertx vertx = Vertx.vertx();
            WebClient client = WebClient.create(vertx);
            client.get(80, "restapi.amap.com",
                    "/v3/config/district?keywords=%E6%AD%A6%E6%B1%89&subdistrict=0&key=高德地图API申请的Token&extensions=all")
                    .send(ar -> {
                        if (ar.succeeded()) {
                            // Obtain response
                            HttpResponse<Buffer> response = ar.result();
                            result = response.bodyAsString();
                            JsonObject jo = new JsonObject(result);
                            result = jo.getJsonArray("districts").getJsonObject(0).getString("polyline");
                            GeometryFactory factory=new GeometryFactory();
                            String[] xyStrings=result.replace("|", ";").split(";");
                            List<Coordinate> list=new ArrayList<>();
                            for(String xy:xyStrings){
                                String[] s_arr=xy.split(",");
                                double[] d_xy=new double[2];
                                d_xy[0]=Double.parseDouble(s_arr[0]);
                                d_xy[1]=Double.parseDouble(s_arr[1]);
                                Coordinate coor=new Coordinate(d_xy[0], d_xy[1]);
                                list.add(coor);
                            }
                            Coordinate[] coor_arr=list.toArray(new Coordinate[0]);
                            MultiPoint multiPoint=factory.createMultiPoint(coor_arr);
                            Geometry env=multiPoint.getEnvelope();
                            Coordinate[] MBR=env.getCoordinates();
                            for(int i=0;i<MBR.length;i++){
                                System.out.println(MBR[i].x+","+MBR[i].y);
                            }
                            client.close();
                            vertx.close();
                        } else {
                            System.out.println("Something went wrong " + ar.cause().getMessage());
                        }
                    });
        }
        /**
         * 计算两点的距离差在哪个阈值范围内
         * @param pt1
         * @param pt2
         * @param config    阈值的设置
         * @return
         */
        public static CompareValue inTolerance(Point pt1,Point pt2,GeoConfig config){
            double delta=Math.sqrt(Math.pow(pt1.getX()-pt2.getX(),2)+Math.pow(pt1.getY()-pt2.getY(), 2));
            double max=config.getMaxGeoRange();
            double min=config.getMinGeoRange();
            if(delta<min){
                return CompareValue.LT;
            }else if(delta<=max&&delta>=min){
                return CompareValue.IN;
            }else{
                return CompareValue.GT;
            }
        }
        /**
         * 建立网格
         * @return
         */
        public static HashMap<String,Grid> createGrids(){
            HashMap<String,Grid> gridMap=new HashMap<>();
            double left_top_x=Double.parseDouble(PropertiesUtil.getProperties("common", "left-top").split(",")[0]);
            double left_top_y=Double.parseDouble(PropertiesUtil.getProperties("common", "left-top").split(",")[1]);
            double right_bottom_x=Double.parseDouble(PropertiesUtil.getProperties("common", "right-bottom").split(",")[0]);
            double right_bottom_y=Double.parseDouble(PropertiesUtil.getProperties("common", "right-bottom").split(",")[1]);
            int rows=Integer.parseInt(PropertiesUtil.getProperties("common", "rows"));
            int cols=Integer.parseInt(PropertiesUtil.getProperties("common", "cols"));
            double interval_x=Double.parseDouble(ParseDataType.parseD2s((right_bottom_x-left_top_x)/(cols*1.0),6));
            double interval_y=Double.parseDouble(ParseDataType.parseD2s((left_top_y-right_bottom_y)/(rows*1.0),6));
            for(int i=0;i<rows;i++){
                for(int j=0;j<cols;j++){
                    Grid grid=new Grid();
                    grid.setCol(cols);
                    grid.setRow(rows);
                    grid.setIndex(i*cols+j+1);
                    Point lefttop=new Point();
                    Point rightbottom=new Point();
                    lefttop.setX(left_top_x+j*interval_x);
                    lefttop.setY(left_top_y-i*interval_y);
                    if(j==cols-1){
                        rightbottom.setX(right_bottom_x);
                    }else{
                        rightbottom.setX(left_top_x+(j+1)*interval_x);
                    }
                    if(i==rows-1){
                        rightbottom.setY(right_bottom_y);
                    }else{
                        rightbottom.setY(left_top_y-(i+1)*interval_y);
                    }
                    grid.setLefttop(lefttop);
                    grid.setRightbottom(rightbottom);
                    gridMap.put(String.valueOf(grid.getRow())+"_"+String.valueOf(grid.getCol())+"_"+String.valueOf(grid.getIndex()),grid);
                }
            }
            return gridMap;
        }
    
        /**
         * 建立网格索引
         */
        public static HashMap<String, Grid> createGridIndex(){
    
            HashMap<String, Grid> gridmap=createGrids();
    
            int cols=Integer.parseInt(PropertiesUtil.getProperties("common", "cols"));
            int rows=Integer.parseInt(PropertiesUtil.getProperties("common", "rows"));
            String rbPt_s=PropertiesUtil.getProperties("common", "right-bottom");
            Point rbPt=new Point();
            rbPt.setX(Double.parseDouble(rbPt_s.split(",")[0]));
            rbPt.setY(Double.parseDouble(rbPt_s.split(",")[1]));
            String ltPt_s=PropertiesUtil.getProperties("common", "left-top");
            Point ltPt=new Point();
            ltPt.setX(Double.parseDouble(ltPt_s.split(",")[0]));
            ltPt.setY(Double.parseDouble(ltPt_s.split(",")[1]));
            double range_x=rbPt.getX()-ltPt.getX();
            double range_y=ltPt.getY()-rbPt.getY();
            QueryTrail query=new QueryTrail();
            HashMap<String, Line> map=query.getLine();
            GeoConfig config=new GeoConfig();
            config.setMaxGeoRange(Double.parseDouble(PropertiesUtil.getProperties("common", "maxGeoRange")));
            config.setMinGeoRange(Double.parseDouble(PropertiesUtil.getProperties("common", "minGeoRange")));
            GeometryFactory factory=new GeometryFactory();
            for(Entry<String, Line> entry:map.entrySet()){
                Line templine=entry.getValue().sort(true);
                List<Line> list=templine.filter(config);
                for(Line line:list){
                    List<GPSPoint> gpslist=line.getCoors();
                    List<Coordinate> coors=new ArrayList<>();
                    for(GPSPoint xy:gpslist){
                        double x=xy.getX();
                        double y=xy.getY();
                        Coordinate coor=new Coordinate(x, y);
                        coors.add(coor);
                    }
                    Coordinate[] coor_arr=coors.toArray(new Coordinate[0]);
                    if(coor_arr.length>1){
                        LineString l_s=factory.createLineString(coor_arr);
                        Envelope env=l_s.getEnvelopeInternal();
                        double max_x=env.getMaxX();
                        double min_x=env.getMinX();
                        double max_y=env.getMaxY();
                        double min_y=env.getMinY();
                        int max_j=(int)((max_x-ltPt.getX())/range_x*cols);
                        int max_i=(int)((ltPt.getY()-max_y)/range_y*rows);
                        int min_j=(int)((min_x-ltPt.getX())/range_x*cols);
                        int min_i=(int)((ltPt.getY()-min_y)/range_y*rows);
                        a:for(int i=max_i;i<=min_i;i++){
                            for(int j=min_j;j<=max_j;j++){
                                Grid grid=gridmap.get(String.valueOf(rows)+"_"+String.valueOf(cols)+"_"+String.valueOf(i*cols+j+1));
                                Coordinate[] coor_arr1=new Coordinate[5];
                                coor_arr1[0]=new Coordinate(grid.getLefttop().getX(), grid.getLefttop().getY());
                                coor_arr1[1]=new Coordinate(grid.getLefttop().getX(), grid.getRightbottom().getY());
                                coor_arr1[2]=new Coordinate(grid.getRightbottom().getX(), grid.getRightbottom().getY());
                                coor_arr1[3]=new Coordinate(grid.getRightbottom().getX(), grid.getLefttop().getY());
                                coor_arr1[4]=new Coordinate(grid.getLefttop().getX(), grid.getLefttop().getY());
                                CoordinateArraySequence seq=new CoordinateArraySequence(coor_arr1);
                                LinearRing ring = new LinearRing(seq, new GeometryFactory());
                                Polygon poly=new Polygon(ring, null, new GeometryFactory());
                                if(l_s.crosses(poly)||poly.covers(l_s)){
                                    grid.addLine(line);
                                    break a;
                                }
                            }
                        }
                    }else{
                        GPSPoint point=gpslist.get(0);
                        int j=(int)((point.getX()-ltPt.getX())/range_x*cols);
                        int i=(int)((ltPt.getY()-point.getY())/range_y*rows);
                        Grid grid=gridmap.get(String.valueOf(rows)+"_"+String.valueOf(cols)+"_"+String.valueOf(i*cols+j+1));
                        grid.addLine(line);
                    }
                }
            }
            System.out.println("网格索引创建成功!");
            return gridmap;
        }
    
    
        /**
         * 建立R树索引
         * @return
         */
        public static STRtree createRtree(){
            QueryTrail query=new QueryTrail();
            HashMap<String, Line> map=query.getLine();
            GeoConfig config=new GeoConfig();
            config.setMaxGeoRange(Double.parseDouble(PropertiesUtil.getProperties("common", "maxGeoRange")));
            config.setMinGeoRange(Double.parseDouble(PropertiesUtil.getProperties("common", "minGeoRange")));
            STRtree tree=new STRtree();
            for(Entry<String, Line> entry:map.entrySet()){
                Line templine=entry.getValue().sort(true);
                List<Line> list=templine.filter(config);
                for(Line line:list){
                    GeometryFactory factory=new GeometryFactory();
                    List<Coordinate> coors=new ArrayList<>();
                    List<GPSPoint> gpslist=line.getCoors();
                    for(GPSPoint xy:gpslist){
                        double x=xy.getX();
                        double y=xy.getY();
                        Coordinate coor=new Coordinate(x, y);
                        coors.add(coor);
                    }
                    Coordinate[] coor_arr=coors.toArray(new Coordinate[0]);
                    if(coor_arr.length>1){
                        LineString lineStr=factory.createLineString(coor_arr);
                        Envelope env=lineStr.getEnvelopeInternal();
                        tree.insert(env, lineStr);
                    }else{
                        com.vividsolutions.jts.geom.Point point=factory.createPoint(coor_arr[0]);
                        Envelope env=point.getEnvelopeInternal();
                        tree.insert(env, point);
                    }
                }
            }
            tree.build();
            System.out.println("R树索引创建成功!");
            return tree;
        }
        /**
         * R树查询
         * @param tree
         * @param searchGeo
         * @return
         */
        public static List<Geometry> query(STRtree tree,Geometry searchGeo){
            List <Geometry> result=new ArrayList<>();
            @SuppressWarnings("rawtypes")
            List list=tree.query(searchGeo.getEnvelopeInternal());
            for(int i=0;i<list.size();i++){
                Geometry lineStr=(Geometry)list.get(i);
                if(lineStr.intersects(searchGeo)){
                    result.add(lineStr);
                }
            }
            return result;
        }
        //根据两点生成矩形搜索框
        public static Geometry generateSearchGeo(double left_top_x,double left_top_y,double right_bottom_x,double right_bottom_y){
            Coordinate[] coors=new Coordinate[4];
            coors[0]=new Coordinate(left_top_x, left_top_y);
            coors[1]=new Coordinate(right_bottom_x, left_top_y);
            coors[2]=new Coordinate(left_top_x, right_bottom_y);
            coors[3]=new Coordinate(right_bottom_x, right_bottom_y);
            LinearRing ring=new LinearRing(new CoordinateArraySequence(coors),new GeometryFactory());
            return ring;
        }
    
    }
    

    common.properties:

    #两点间最大间隔(经纬度差值,目前按照江的宽度)
    maxGeoRange=0.002
    #maxGeoRange=0.012
    #两点间最小间隔(经纬度差值,目前按照地图上一栋楼的宽度)
    minGeoRange=0.0005
    #minGeoRange=0.0017
    #武汉市外包矩形的范围
    #左上角
    left-top=113.702282,31.36127
    #左下角
    left-bottom=113.702282,29.969079
    #右上角
    right-top=115.082574,31.36127
    #右下角
    right-bottom=115.082574,29.969079
    #设定的网格的行数
    rows=10
    #设定的网格的列数
    cols=10
    #坐标保留小数点后几位
    CoorAbs=10000

    GPSPoint.java:

    package entity;
    
    import java.util.Date;
    
    /**
     * 点,描述点的位置,所属网格和所属线条
     * @author KingWang
     *
     */
    public class GPSPoint extends Point{
        private Date date=new Date();
        private Grid grid=new Grid();
        private Line line=new Line();
    
        public Date getDate() {
            return date;
        }
        public void setDate(Date date) {
            this.date = date;
        }
        public Grid getGrid() {
            return grid;
        }
        public void setGrid(Grid grid) {
            this.grid = grid;
        }
        public Line getLine() {
            return line;
        }
        public void setLine(Line line) {
            this.line = line;
        }
    
    }
    

    Grid.java:

    package entity;
    
    import java.util.HashSet;
    
    public class Grid {
        private int index=0;
        private int col=0;
        private int row=0;
        private Point lefttop=new Point();
        private Point rightbottom=new Point();
        private HashSet<Line> set=new HashSet<>();
        public int getIndex() {
            return index;
        }
        public void setIndex(int index) {
            this.index = index;
        }
        public int getCol() {
            return col;
        }
        public void setCol(int col) {
            this.col = col;
        }
        public int getRow() {
            return row;
        }
        public void setRow(int row) {
            this.row = row;
        }
        public Point getLefttop() {
            return lefttop;
        }
        public void setLefttop(Point lefttop) {
            this.lefttop = lefttop;
        }
        public Point getRightbottom() {
            return rightbottom;
        }
        public void setRightbottom(Point rightbottom) {
            this.rightbottom = rightbottom;
        }
        public HashSet<Line> getSet() {
            return set;
        }
        public void setSet(HashSet<Line> set) {
            this.set = set;
        }
        public void addLine(Line line){
            this.set.add(line);
        }
    }
    

    Line.java:

    package entity;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    import java.util.Random;
    import java.util.concurrent.CopyOnWriteArrayList;
    
    import config.GeoConfig;
    import util.SpatialUtil;
    /**
     * 线,点串,描述整条轨迹
     * @author KingWang
     *
     */
    public class Line {
        /**
         * 轨迹的id
         */
        private String id="";
        /**
         * 按照顺序存储点轨迹
         */
        private List<GPSPoint> coors=new ArrayList<>();
        /**
         * 经过的网格,按照轨迹顺序存储
         */
        private List<Grid> grids=new ArrayList<>();
    
        public String getId() {
            return id;
        }
        public void setId(String id) {
            this.id = id;
        }
        public List<GPSPoint> getCoors() {
            return coors;
        }
        public void setCoors(List<GPSPoint> coors) {
            this.coors = coors;
        }
        public List<Grid> getGrids() {
            return grids;
        }
        public void setGrids(List<Grid> grids) {
            this.grids = grids;
        }
        public void addPoint(GPSPoint p){
            this.coors.add(p);
        }
    
        public void removePoint(int index){
            this.coors.remove(index);
        }
    
        public Line sort(boolean isTimeAsc){
            List<GPSPoint> list=this.getCoors();
            Collections.sort(list, (point1,point2)->{
                if(point1.getDate().after(point2.getDate())){
                    if(isTimeAsc){
                        return 1;
                    }else{
                        return -1;
                    }
                }else{
                    if(isTimeAsc){
                        return -1;
                    }else{
                        return 1;
                    }
                }
            });
            return this;
        }
        /**
         * 对线坐标串进行粗处理,太密的点删掉,太远的点打断成两段
         * @param config
         * @return
         */
        public List<Line> filter(GeoConfig config){
            List<Line> resultList=new ArrayList<>();
            List<GPSPoint> list=new CopyOnWriteArrayList<>(this.getCoors());
            Point lastPt=new Point();
            int i=0;
            int lastCutIndex=0;
            for(GPSPoint point:list){
                if(i>0&&SpatialUtil.inTolerance(lastPt,point,config)==CompareValue.GT){
                    List<GPSPoint> list_temp=new ArrayList<>();
                    list_temp.addAll(list.subList(lastCutIndex, i));
                    Line line_temp=new Line();
                    line_temp.setCoors(list_temp);
                    line_temp.setId(String.valueOf(System.currentTimeMillis()+new Random().nextInt(10)));
                    resultList.add(line_temp);
                    lastCutIndex=i;
                }else if(i>0&&SpatialUtil.inTolerance(lastPt, point, config)==CompareValue.LT){
                    list.remove(i);
                    i--;
                }
                lastPt=point;
                i++;
            }
            if(lastCutIndex==i){
                Line line_temp=new Line();
                line_temp.setCoors(this.getCoors());
                line_temp.setId(String.valueOf(System.currentTimeMillis()+new Random().nextInt(10)));
                resultList.add(line_temp);
            }else{
                List<GPSPoint> list_temp=new ArrayList<>();
                list_temp.addAll(list.subList(lastCutIndex, i));
                Line line_temp=new Line();
                line_temp.setCoors(list_temp);
                line_temp.setId(String.valueOf(System.currentTimeMillis()+new Random().nextInt(10)));
                resultList.add(line_temp);
            }
            return resultList;
        }
    }
    

    Point.java:

    package entity;
    
    import config.GeoConfig;
    
    /**
     * 点,描述点的位置
     * @author KingWang
     *
     */
    public class Point {
        private double x=0.0;
        private double y=0.0;
    
        public double getX() {
            return x;
        }
    
        public void setX(double x) {
            this.x = x;
        }
    
        public double getY() {
            return y;
        }
    
        public void setY(double y) {
            this.y = y;
        }
    }
    

    注:

    这里需要用到求解空间拓扑关系的函数。

    具体参考博主另外一篇文章关于拓扑关系的测试。

    JTS拓扑关系测试

    展开全文
  • 我们知道 HashMap 底层是由数组,链表,红黑组成,在 HashMap 做扩容操作时,除了把数组容量扩大为原来两倍外,还会对所有元素重新计算 hash 值,因为长度扩大以后,hash值也随之改变。 如果是简单 Node ...

    我们知道 HashMap 的底层是由数组,链表,红黑树组成的,在 HashMap 做扩容操作时,除了把数组容量扩大为原来的两倍外,还会对所有元素重新计算 hash 值,因为长度扩大以后,hash值也随之改变。

    如果是简单的 Node 对象,只需要重新计算下标放进去就可以了,如果是链表和红黑树,那么操作就会比较复杂,下面我们就来看下,JDK1.8 下的 HashMap 在扩容时对链表和红黑树做了哪些优化?

    rehash 时,链表怎么处理?

    假设一个 HashMap 原本 bucket 大小为 16。下标 3 这个位置上的 19, 3, 35 由于索引冲突组成链表。

    HashMap扩容时,究竟对链表和红黑树做了什么?

     

    当 HashMap 由 16 扩容到 32 时,19, 3, 35 重新 hash 之后拆成两条链表。

    HashMap扩容时,究竟对链表和红黑树做了什么?

     

    查看 JDK1.8 HashMap 的源码,我们可以看到关于链表的优化操作如下:

    // 把原有链表拆成两个链表
    // 链表1存放在低位(原索引位置)
    Node<K,V> loHead = null, loTail = null;
    // 链表2存放在高位(原索引 + 旧数组长度)
    Node<K,V> hiHead = null, hiTail = null;
    Node<K,V> next;
    do {
        next = e.next;
        // 链表1
        if ((e.hash & oldCap) == 0) {
            if (loTail == null)
                loHead = e;
            else
                loTail.next = e;
            loTail = e;
        }
        // 链表2
        else {
            if (hiTail == null)
                hiHead = e;
            else
                hiTail.next = e;
            hiTail = e;
        }
    } while ((e = next) != null);
    // 链表1存放于原索引位置
    if (loTail != null) {
        loTail.next = null;
        newTab[j] = loHead;
    }
    // 链表2存放原索引加上旧数组长度的偏移量
    if (hiTail != null) {
        hiTail.next = null;
        newTab[j + oldCap] = hiHead;
    }

    正常我们是把所有元素都重新计算一下下标值,再决定放入哪个桶,JDK1.8 优化成直接把链表拆成高位和低位两条,通过位运算来决定放在原索引处或者原索引加原数组长度的偏移量处。我们通过位运算来分析下。

    先回顾一下原 hash 的求余过程:

    HashMap扩容时,究竟对链表和红黑树做了什么?

     

    再看一下 rehash 时,判断时做的位操作,也就是这句 e.hash & oldCap:

    HashMap扩容时,究竟对链表和红黑树做了什么?

     

    再看下扩容后的实际求余过程:

    HashMap扩容时,究竟对链表和红黑树做了什么?

     

    这波操作是不是很666,为什么 2 的整数幂 - 1可以作 & 操作可以代替求余计算,因为 2 的整数幂 - 1 的二进制比较特殊,就是一串 11111,与这串数字 1 作 & 操作,结果就是保留下原数字的低位,去掉原数字的高位,达到求余的效果。2 的整数幂的二进制也比较特殊,就是一个 1 后面跟上一串 0。

    HashMap 的扩容都是扩大为原来大小的两倍,从二进制上看就是给这串数字加个 0,比如 16 -> 32 = 10000 -> 100000,那么他的 n - 1 就是 15 -> 32 = 1111 -> 11111。也就是多了一位,所以扩容后的下标可以从原有的下标推算出来。差异就在于上图我标红的地方,如果标红处是 0,那么扩容后再求余结果不变,如果标红处是 1,那么扩容后再求余就为原索引 + 原偏移量。如何判断标红处是 0 还是 1,就是把 e.hash & oldCap。

    rehash 时,红黑树怎么处理?

    // 红黑树转链表阈值
    static final int UNTREEIFY_THRESHOLD = 6;
    // 扩容操作
    final Node<K,V>[] resize() {
        // ....
        else if (e instanceof TreeNode)
           ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
        // ...
    }
    final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
        TreeNode<K,V> b = this;
        // Relink into lo and hi lists, preserving order
        // 和链表同样的套路,分成高位和低位
        TreeNode<K,V> loHead = null, loTail = null;
        TreeNode<K,V> hiHead = null, hiTail = null;
        int lc = 0, hc = 0;
        /**
          * TreeNode 是间接继承于 Node,保留了 next,可以像链表一样遍历
          * 这里的操作和链表的一毛一样
          */
        for (TreeNode<K,V> e = b, next; e != null; e = next) {
            next = (TreeNode<K,V>)e.next;
            e.next = null;
            // bit 就是 oldCap
            if ((e.hash & bit) == 0) {
                if ((e.prev = loTail) == null)
                    loHead = e;
                else
                // 尾插
                    loTail.next = e;
                loTail = e;
                ++lc;
            }
            else {
                if ((e.prev = hiTail) == null)
                    hiHead = e;
                else
                    hiTail.next = e;
                hiTail = e;
                ++hc;
            }
        }
        // 树化低位链表
        if (loHead != null) {
            // 如果 loHead 不为空,且链表长度小于等于 6,则将红黑树转成链表
            if (lc <= UNTREEIFY_THRESHOLD)
                tab[index] = loHead.untreeify(map);
            else {
                /**
                  * hiHead == null 时,表明扩容后,
                  * 所有节点仍在原位置,树结构不变,无需重新树化
                  */
                tab[index] = loHead;
                if (hiHead != null) // (else is already treeified)
                    loHead.treeify(tab);
            }
        }
        // 树化高位链表,逻辑与上面一致
        if (hiHead != null) {
            if (hc <= UNTREEIFY_THRESHOLD)
                tab[index + bit] = hiHead.untreeify(map);
            else {
                tab[index + bit] = hiHead;
                if (loHead != null)
                    hiHead.treeify(tab);
            }
        }
    }

    从源码可以看出,红黑树的拆分和链表的逻辑基本一致,不同的地方在于,重新映射后,会将红黑树拆分成两条链表,根据链表的长度,判断需不需要把链表重新进行树化。

    作者:超超不会飞

    链接:https://juejin.im/post/5ed9add1e51d45788e17ee73

    来源:掘金

    展开全文
  • 我们知道 HashMap 底层是由数组,链表,红黑组成,在 HashMap 做扩容操作时,除了把数组容量扩大为原来两倍外,还会对所有元素重新计算 hash 值,因为长度扩大以后,hash值也随之改变。 如果是简单 Node ...
  • 怎么和平衡删除这么像 1.都不存在,肯定是maybe 2.左端点不存在,判断中间一段最大值和右端点关系 3.右端点不存在,判断中间一段最大值和左端点关系(这里有点疑惑,感觉自己写错了,居然过了) 4.都...
  • 根据数据计算出一个数值,存储时,将数据按这个数值的大小排序。查询时,也根据要查的数据计算出一个数值,拿这个数值比较,先取中间的值,如果大,往后找,如果小,往前找。有种数据结构就是用于这种算法的,就是二...
  • 在需求中由于要批量查数据,且表中数据挺大(2300万条记录) 且查询条件的这两个字段没有加索引,为了增加查询速度,现在需要去为这两个字段添加索引。...由于每个字段的大小是256 所以说这个索引建下来还是...
  • 输入的第一行为一个正整数n,表示词典的大小,其后n行,每一行一个单词(不保证是英文单词,也有可能是火星文单词哦),单词由不超过10个的小写英文字母组成,可能存在相同的单词,此时应将其视作不同的单词。...
  • 美团一面二面

    2021-04-28 00:31:42
    一面 问项目 做过的项目 做题: 两个栈实现一个队列 二叉树的最大路径和 10L水,3L杯子和7L杯子,得到5L水 计算机网络方面: ...三次握手两次行不行 ...大量线程阻塞在了一起怎么排查 ...B树和B+树的区别 怎么用sql
  • HashMap原理(一)

    2019-12-20 10:03:33
    HashMaphash值是怎么算出来,为什么这么算 HashMapput()过程 一、HashMap底层数据结构 HashMap底层数据结构是数组+单向链表+红黑(jdk1.8及以后版本才有红黑结构)。 二、为什么默认初始大小为...
  • 1、为什么用HashMap? 2、HashMap的工作原理是什么? 3、有什么方法可以减少碰撞? 4、HashMap中hash函数怎么是是实现的?...8、如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办? ...
  • Java面试-HashMap

    2019-07-23 15:33:09
    文章目录1、为什么用HashMap?2、HashMap的工作原理是什么?3、有什么方法可以减少碰撞?4、HashMap中hash函数怎么是是实现的?...8、如果HashMap的大小超过了负载因子(load factor)定义的容量,怎么办?9、重新调...
  • //输出树的元素 printf(" ");//输出时的空格 if(a->lchild)EnQueue(Q,a->lchild);//左孩子存在,入队 if(a->rchild)EnQueue(Q,a->rchild);//右孩子存在,入队 } } void Exchange_Tree(BiTree T) { if(T) { BiTree ...
  • Tree of tree

    2019-08-10 21:26:14
    一棵结点带权大小(结点数)为k子树权值和最大为多少。 初步分析 这道题其实就是一道01背包问题只是是在上做而已。背包总容量就是k个结点(一定得刚好装满),每个物品价值就是结点权值w[i].注意,并...
  • [ CodeVS冲杯之路 ] P1092

    2016-10-18 16:50:00
     嗯,这道题有一定难度啊,需要先用扩展欧几里得算法求出逆元,然后按照大小构一颗带边权为小时数的树  链剖分后在上DP,设f[i][j]为以 i 为根 j 为子树最小那一天  注意DP方程是有单调性,可以用...
  • 题目意思也很简单,给定一个H×W的矩阵地图,其中有一些点是柿子,又给定矩形框的大小为T×S,要求用矩形框可以框到的最多多少个柿子? 二、题目思路以及AC代码 这道题是明显的水题,一开始我还在琢磨怎么做,...
  • 初始化大小10会怎么样?为什么Map桶结点大于8才转为红黑构造方法成员方法增加方法转换红黑扩容方法_resize()扩容机制1、什么时候需要扩容2、扩容是什么resize源码删除方法_remove()查找元素方法_get()遍历...
  • 垃圾回收过程是怎么? 什么是写屏障、混合写屏障,如何实现? 开源库里会有一些类似下面这种奇怪用法:var _ io.Writer = (*myWriter)(nil),是为什么? GMP模型 动图图解,GMP里为什么要有P 协程之间是怎么...
  • 8、虚函数会增加类的大小吗 9、图形学了解吗 10、stable_sort和sort区别 11、异常安全讲一下(查一下) 12、手写strncpy 13、两个矩形怎么判断重叠 360 视频一面 1、自我介绍 2、Linux系统了解深吗,命令,用了什么...
  • 写一段程序,找出数组中第k大小的数,输出数所在位置。例如{2,4,3,4,7}中,第一大数是7,位置在4。第二大、第三大数都是4,位置在1、3随便输出哪一个均可。 3.5.3 给40亿个不重复unsigned int整数,...
  • 前端如何提高用户体验:增强可点击区域的大小 CSS Viewport 单位,很多人还不知道使用它来快速布局! 小智在这3年开发中遇到的 CSS 问题及解决方案,有大佬帮他总结好了 ! 这些 CSS 伪类,你可能还不知道,...
  • ExtAspNet_v2.3.2_dll

    2010-09-29 14:37:08
    -重新设计模拟树的下拉列表的实现,避免选中某项后的闪烁。 +2009-11-21 v2.1.5 +Tree优化。 -修正Expanded项和Checked项的状态在回发改变后不能保持的BUG。 -GetNodeById更名为FindNode,保持和...
  • -重新设计模拟树的下拉列表的实现,避免选中某项后的闪烁。 +2009-11-21 v2.1.5 +Tree优化。 -修正Expanded项和Checked项的状态在回发改变后不能保持的BUG。 -GetNodeById更名为FindNode,保持和...

空空如也

空空如也

1 2 3
收藏数 51
精华内容 20
关键字:

树的大小怎么量