分类 技术教程 下的文章

蒙特卡洛——使用CDF反函数生成非均匀随机数

  并查集(union-find disjoint sets)是一种十分精巧和精练的数据结构,主要用于处置不相交聚集的合并问题。正如它的名字一样,并查集的主要的操作有合并(union)与查找(find)。一些算法也会用到并查集,好比求最小天生树的Kruskal算法。下面先通过举例说明并查集的基本看法。

 

并查集的引入

  首先,我们怎么样来示意一个聚集呢?实在很简朴,只需要在这个聚集内里随便找一个元素作为这个聚集的代表就可以了。用哪个元素作为代表并不是我们体贴的问题,我们体贴的是,给定一个元素要找到它所属的谁人聚集。所谓找到所属的聚集,也就是找到这个聚集的代表元素。

  好比我们现在有0,1,2,3,4,5,6,7这8个元素,他们各自所在的聚集如下:

  图中有3个聚集,这3个聚集的代表元素划分为1,6,5。其中代表元素为1的聚集含有的元素有0,1,2,4;代表元素为6的聚集含有元素有3,6,7;代表元素为5的聚集含有的元素就只有5。

  以是,若是我们要查找某一个元素属于哪一个聚集,只需要从这个元素的节点最先,凭证箭头偏向一直向上找就可以了。当某个元素没有向外指出的箭头,就说明这个元素就是这个聚集的代表元素。

  好比,若是现在要找4是属于哪一个聚集,凭证上面的方式我们可以知道4这个元素在代表元素为1的这个聚集中。若是要找5这个元素,那么5这个元素就在代表元素为5的聚集中,同时代表元素为5的聚集中就只有5这个元素。

  现在我们要把代表元素为7的聚集合并到代表元素为4的聚集,我们需要先找到7所属的聚集的代表元素6,以及4所属的聚集的代表元素1,然后再让6指向1就完成了合并了。

  上面大致解说了查找和合并的实现历程,下面我们用代码来实现。先讲我常用的并查集算法。

  先说明,集适用数组set来示意,数组的下标就是对应的元素,而数组存放的是该元素的上一个元素。就拿上面这个图来举例,我们的set数组是这样的:

  set数组中存放的值有正数和负数。其中只有代表元素存放负数,这里的"-1"代表5是对应聚集的代表元素,"-1"的绝对值也就是"1"说明在代表元素为5的这个聚集中,含有元素的个数为1。同理,"-7"代表1是对应聚集的代表元素,"-7"的绝对值也就是"7"说明在代表元素为1的这个聚集中,含有元素的个数为7。而非代表元素存放正数,响应的值示意该元素的前一个元素(父节点或是索引)。

 

初始化

  首先我们需要将每一个元素所属的聚集初始化为其自己,也就是每一个元素所属聚集的代表元素就是它自己,初始化为"-1"。

  若是我们有n个元素,初始化的代码如下:

1 void initSet(int *set, intn) {2     for (int i = 0; i < n; i++) {3         set[i] = -1;4 }5 }

  固然,你也可以简简朴单的就一句话: std::fill(set, set + n, -1); ,到达同样的效果。

 

查找

  与上面所说的方式一样,若是我们要找某一个元素所在的聚集(的代表元素),就先找到它的前一个元素,若是没有前一个元素,那么它自己就是谁人代表元素;若是有前一个元素,那么再找前一个元素的前一个元素,这样总是可以找到代表元素。

  查找的代码如下:

1 int find(int *set, intx) {2     while (x > 0) {3         x = set[x];4 }5     returnx;6 }

 

合并

  我们需要先找到要合并的谁人元素所属聚集的代表元素,然后才可以举行合并。

  合并的代码如下:

Unity 渲染流水线 :CPU与GPU合作创造的艺术wfd

1 void merge(int *set, int x, inty) {2     int x = find(set, x);3     int y = find(set, y);4     set[y] =x;5 }

  这里我们始终把y所属的聚集合并到x所属的聚集。

 

路径压缩

  思量一种情形,若是有元素0,1,2,3,4。

  上面合并后的效果就像一条链,随着链越来越长,每次我们从底部查找到根节点所需的时间也会越长。有没有什么方式可以削减链的长度,以提高查找的效率?固然有,那就是路径压缩。只需要在查询的历程中,把沿途的每个元素都指向代表元素就可以了,以是经由路径压缩后,上面的合并情形应该酿成这个样子:

  通过路径压缩改善后的查找代码也很简朴,这里我们用递归的方式实现:

1 int find(int *set, intx) {2     if (x < 0) returnx;3     else return set[x] = find(set, set[x]);4 }

  我们并不是直接返回聚集的代表元素,而是先把聚集的代表元素赋值给沿途的谁人元素,让这个元素指向代表元素,然后再返回聚集的代表元素。这样就实现了路径压缩。

 

按秩合并

  这里我是根据聚集的规模巨细来举行合并的。

  在上面的合并函数代码中,我们总是把后一个聚集合并到前一个聚集,也正是这种方式使得之前我们合并出一条很长的链。以是我们应该用一种更高效的方式来举行合并,阻止合并出一条很长的链。

  以是我们接纳了按秩合并的方式,就是每次我们都是把规模小的聚集合并到规模大的聚集。而聚集的规模,也就是元素的数目,可以通过代表元素在set数组中存放的值的绝对值知道。以是我们只需要找到合并元素所属聚集的代表元素,然后对照两个聚集元素个数巨细,根据小并到大的规则来合并就可以了。

  按秩合并(按规模巨细)的代码如下:

1 void merge(int *set, int x, inty) {2     int x = find(set, x);3     int y = find(set, y);4     if (set[x] > set[y]) {  //注重我们对照的是负数,若是set[x] > set[y],说明abs(set[x]) < abs(set[y]),也就是x所属的聚集的规模小于y所属聚集的规模
5         set[y] += set[x];   //以是应该把x所属的聚集合并到y所属的聚集。先改变y聚集的规模巨细
6         set[x] = y;         //再把x所属的聚集合并到y所属的聚集
7 }8     else {                  //y所属的聚集的规模小于x所属聚集的规模
9         set[x] += set[y];   //以是应该把y所属的聚集合并到x所属的聚集。先改变x聚集的规模巨细
10         set[y] = x;         //再把y所属的聚集合并到x所属的聚集
11 }12 }

 

并查集算法

  下面给出改善后的并查集的完整代码(路径压缩与按秩合并):

1 void initSet(int *set, intn) {2     for (int i = 0; i < n; i++) {3         set[i] = -1;4 }5 }6 
7 int find(int *set, intx) {8     if (x < 0) returnx;9     else return set[x] = find(set, set[x]);10 }11 
12 void merge(int *set, int x, inty) {13     int x = find(set, x);14     int y = find(set, y);15     if (set[x] > set[y]) {16         set[y] += set[x];17         set[x] =y;18 }19     else{20         set[x] += set[y];21         set[y] =x;22 }23 }

 

另外一种并查集算法

  这种方式需要分外的一个rank数组,rank[n],用来存放代表元素所属聚集的秩(深度)。或者说,是存放每个根节点对应的树的深度(若是该元素不是根节点,其rank存放的值是以它作为根节点的子树的深度)。好比:

  对应的按秩合并的规则是,把rand小的聚集合并到rank大的聚集。若是两个聚集的秩巨细相同,则让其中一个聚集合并另外一个聚集,同时把合并后的谁人聚集的rank加1。

  在初始化时,把每个元素对应的rank初始化为1,同时set数组的初始化的值不再是-1,而是元素自己的值。以及在查找函数中,找到代表元素的条件需要改变。剩下的部门都基真相同。

  有个问题就是,若是将路径压缩和按秩合并一起使用,很可能会损坏rank的准确性。

  响应的代码如下:

1 void initSet(int *set, int *rank, intn) {2     for (int i = 0; i < n; i++) {3         set[i] =i;4         rank[i] = 1;5 }6 }7 
8 int find(int *set, intx) {9     if (x == set[x]) returnx;10     else return set[x] = find(set, set[x]);11 }12 
13 void merge(int *set, int rank, int x, inty) {14     int x = find(set, x);15     int y = find(set, y);16     if (rank[x] <=rank[y]) {17         set[x] =y;18         if (rank[x] == rank[y] && x != y) rank[y]++;19 }20     else{21         set[y] =x;22 }23 }

 

参考资料

  算法学习条记(1) : 并查集:https://zhuanlan.zhihu.com/p/93647900

  并查集:https://www.cnblogs.com/cyjb/p/UnionFindSets.html

python基础(补充):lambda匿名函数,用了的,都说好!

NLP入门学习中关于分词库HanLP导入使用教程

『单例模式』是一种确立型的设计模式,保证一个类只有一个实例,并提供一个接见它的全局接见点。

在一个系统中,一个类经常会被使用在差其余地方,通过单例模式,我们可以制止多次确立多个实例,从而节约系统资源。

单例模式往往有三个特征,一个类只能有一个实例,它必须自行提供实例的确立,它必须提供方式露出此实例。

饿汉方式

饿汉总是一次吃个饱,以是这种方式总是在系统初始化的时刻确立所有的工具,不管会不会何时被使用

public class SingleTon {

    //自行组织实例
    private static final SingleTon instance = new SingleTon();

    //置空组织器,不允许外部组织
    public SingleTon(){}

    //对外露出内部实例
    public SingleTon getInstance(){
        return this.instance;
    }
}

饿汉方式实现的单例模式是极其简朴的,但瑕玷也很显著,即便这个类一时半会不会被使用到,但也必须在编译的时刻初始化分配堆内存,确立这个内部实例。

懒汉方式

懒汉很懒,只有在系统用到某个类的实例的时刻,才会实例化出一个唯一实例。

public class SingleTon {

    private static SingleTon instance= null;
    
    private SingleTon(){}
    
    public static SingleTon getInstance(){
        if(null == instance){
            instance = new SingleTon();
        }
        return instance;
    }
}

instance 在类编译的时刻没有初始化,而只有在挪用 getInstance 方式的时刻,才会去实例化 instance。

looks pretty!

多线程环境下,线程 A 和线程 B 同时判断 instance==null,都去实例化 instance,导致 instance 被实例化两次,堆中发生一个无引用工具,并发量大的情形下,会有更多的无用工具被确立,甚至可能提前触发 GC。

懒汉方式优化一(加内陆锁)

线程不平安,信托你第一时间也会想到加锁控制,那你是不是也这么加的呢?

public class SingleTonLock {

    private static SingleTonLock instance= null;

    public SingleTonLock(){}

    public synchronized SingleTonLock getInstance(){
        if (instance == null){
            instance = new SingleTonLock();
        }
        return instance;
    }
}

这种方式直接给 getInstance 方式加锁了,很显著,会造成大量无效的锁守候,继续优化。

public class SingleTonLock {

    private static volatile SingleTonLock instance= null;

    public SingleTonLock(){}

    public SingleTonLock getInstance(){
        if (instance == null){
            synchronized(this){
                //再次判断是为了防止有的线程醒来以后再次实例化
                //有可能其他线程已经实例化完成了
                if (instance == null){
                    instance = new SingleTonLock();
                }
            }
        }
        return instance;
    }
}

给 instance 加 volatile 修饰是为了防止 jvm 指令重排序,通过再次判断可以保证此实例的唯一实例化。

这简直是一种不错的懒汉实例,推荐人人使用,但我更推荐下一种。

懒汉方式优化二(枚举类)

小我私人以为使用枚举类实现懒汉单例模式是最佳实践,枚举类本质上是用静态字段来实现的,例如:

对不起,“下一代ERP”依旧是现在的ERP

public enum Color {
    RED(), GREEN(), BLUE(), YELLOW();
}

javap 反编译这个枚举类获得:

public final class com.example.test.lazy.Color extends java.lang.Enum {
  public static final com.example.test.lazy.Color RED;
  public static final com.example.test.lazy.Color GREEN;
  public static final com.example.test.lazy.Color BLUE;
  public static final com.example.test.lazy.Color YELLOW;
  public static com.example.test.lazy.Color[] values();
  public static com.example.test.lazy.Color valueOf(java.lang.String);
  static {};
}

那么,枚举若何实现单例模式,上代码:

public class SingleTonE {

    public static SingleTonE getInstance(){
        return SingleTonEnum.SINGLETON.getInstance();
    }

    private enum SingleTonEnum{
        SINGLETON;

        private SingleTonE instance;

        SingleTonEnum(){
            instance = new SingleTonE();
        }

        public SingleTonE getInstance(){
            return this.instance;
        }
    }
}

只有当挪用 getInstance 方式获取实例的时刻,才会触发枚举类的加载,然后根据上面说的,天生一个静态字段并初始化其内部的单例 instance,由于 jvm 保证只能一个线程举行类加载,以是整个历程看起来异常的简朴。

小我私人以为,枚举类实现单例模式是一种最佳实践,推荐你应用到自己的项目。

近期会整理一个设计模式系列,划分讲讲 23 种设计模式,感兴趣的可以关注下哦~

关注民众不迷路:有诗有酒有代码。

民众号回复「1024」加作者微信一起探讨学习!

民众号回复「面试题」送你一份面试题以及作者的作答谜底

每篇文章用到的所有案例代码素材都市上传我小我私人 github

https://github.com/SingleYam/overview_java
迎接来踩!

线程、多线程和线程池,看完这些你就能所有搞懂了

你了解单例模式的最佳实践吗?

  人人好,时隔多年再次打开我的博客园写下自己的履历和学习总结,开园三年多,文章数少得可怜,一方面自己手艺水平手限,另一方面是自己确实想放弃写博客。由于结业事情的缘故原由,经常性的加班以及仅剩下少的可怜的休息时间着实是想好好休息。但现在又回到了校园,在2019年4月份我选择了告退考研,如愿考取了盘算机科学与手艺的硕士研究生,现在在长春理工大学就读,在导师的建议下我选择NLP(自然语言处置)这个研究偏向。对于自己重新最先写博客,一方面是为了牢固自己学习的功效,另一方面是自己在试探的历程中履历了一些问题,走了一些弯路,写博文是希望同样遇到这个问题的兄弟姐妹看到我的博文后自己的问题能够顺遂解决。

  作为NLP的入门学者,为了能够学得更好,我们需要将理论学习与实践相连系。我们在学习 <<自然语言处置入门>> 这本书时需要导入作者何晗开发的中文语言处置类库 HanLP。 我是自学过一段时间得java语言,以是本篇博客接纳java方式导入。

   导入之前需领会的基础知识:java运行环境的设置、maven项目的确立以及系列操作

步骤:

1.确立一个文件夹作为maven工程存放的父级目录 例如:nlpProject

2.在此目录下新建一个maven Module

选择好安装好的JDK之后给你的maven Module取一个名字

3.设置pom.xml文件,将下列代码加到文件中

1 <dependencies>
2         <dependency>
3             <groupId>com.hankcsgroupId>
4             <artifactId>hanlpartifactId>
5             <version>portable-1.8.1version>
6         dependency>
7     dependencies>

4.安装依赖

5.运行

对不起,“下一代ERP”依旧是现在的ERP

 

上面是一帆风顺情形下的步骤,固然,真真相形并不是那么完善。你有可能会泛起以下几种问题,对应解决方案如下:

问题1:报找不到加载类的编译错误

解决方案:你需要在这个地方更改一下你的编译设置

 

问题2:显著你导入了依赖,而且idea未编译之前不报错。然则为什么报 HanLP无法找到的错误

 

乱码情形如下图:

 

线程、多线程和线程池,看完这些你就能所有搞懂了