2015-09-08 16:11:33 xy010902100449 阅读数 3988
  • Docker入门与进阶实战

    Docker是一个开源的应用容器引擎,使用Go语言开发, 基于Linux内核的cgroup,namespace,Union FS等技术,对应用进程进行封装隔离,并且独立于宿主机与其他进程。Docker理念是将应用及依赖包打包到一个可移植的容器中,可发布到任意Linux发行版Docker引擎上。 使用沙箱机制运行程序,程序之间相互隔离。 Docker技术已经成为开发、运维职位必备的专业技能之一,非常有必要深入学习下,提供职业竞争力。 学完这门课程会获得什么? 首先从零开始教你安装Docker。接下来,学习Docker核心功能,例如镜像、容器、网络等知识点,再教你如何 定制化容器镜像并使用Harbor统一管理容器镜像,然后图形管理和容器监控。贴近企业生产环境讲解,即学即用,确保实用性,实战性!

    3699 人正在学习 去看看 李振良

1、引言

共用体常用来节省内存,特别是一些嵌入式编程,内存是非常宝贵的!
共用体也常用于操作系统数据结构或硬件数据结构!
union 在操作系统底层的代码中用的比较多,因为它在内存共享布局上方便且直观。所以网络编程,协议分析,内核代码上有一些用到 union 都比较好懂,简化了设计。

共用体(union)是一种数据格式,它能够存储不同类型的数据,但是只能同时存储其中的一种类型。主要用处分以下几个方面

2、测试大小端模式

大小端不同,则存储的方式也存在差别,比如int需要4个字节,而char只需要1个字节,根据1个字节所在的具体位置即可判定CPU的模式。

union TestCPU
{
     int i;
     char ch;
};
void testCPUMode(void)
{
    union TestCPU Test;
    Test.i = 1;
    if(Test.ch == 1)
    {
      //这个CPU是小端模式
    }
    else
    {
       //这种情况下就是大端模式
    }
}

如果是 little endian 字节序的话,那个Test.i = 1;的内存从小到大依次放的是:0x01 0x00 0x00 0x00,如是,按照i的起始地址变成按照char 方式(1字节)存取,即得c = 0x01;
反之亦然

2.1 大小端转换函数

/*1.宏定义*/
#define Little_To_LargeOfEndian(x) (((x&0xff)<<24)|((x&0xff00)<<8)| \
((x&0xff0000)>>8)|((x&0xff000000)>>24))      
 //1.四个字节的排放顺序要弄清楚

/*2.写成函数*/
void Little_To_LargeOfEndian(int x)
{
    char a,b,c,d;
    a=(char)(x&0xff);
    b=(char)((x&0xff00)>>8); //3. 字符类型转换的优先级高于移位,所以用括号把移位操作括起来~
    c=(char)((x&0xff0000)>>16);
    d=(char)((x&0xff000000)>>24);
    //printf("0x%x 0x%x 0x%x 0x%x\n",a,b,c,d);
    x=(a<<24)|(b<<16)|(c<<8)|d;
    printf("after transfered x is 0x%x\n",x);
}

3、实现多种数据类型之间转换

3.1 案例一

union Type
{
   int i;
   char ch;
   long lint;
   ....
};

...
union Type type;

这样各种类型的数据共用存储空间,很方便的实现了不同数据类型之间的转换,不需要显示的强制类型转换。

union相比struct更加的节省空间。

3.2 案例二(很常用)

在嵌入式系统开发中,有时需要将一些变量存储在EEPROM中,变量类型若是char、int就很好办,可是如果要存储float、double类型的变量怎么办呢?
这个问题可以用共用体解决:

union myfloat
{
    char i[4];
    float j;
}Test;

因为float是四个字节,因此我们定义一个4个元素的char数组和float公用一段内存,接下来就是EEPROM存取了

在程序中要使用 j 的地方使用Test.j就行了,想把 j 写入EEPROM可以这样:

EEPROM_WRITE(0,myfloat.i[0]);
EEPROM_WRITE(1,myfloat.i[1]);
EEPROM_WRITE(2,myfloat.i[2]);
EEPROM_WRITE(3,myfloat.i[3]);

注:上面参数0、1、2、3为EEPROM地址,上面的EEPROM_WRITE只是示意,有时需要对地址使用(void*)进行类型转换

想把 j 从EEPROM读出可以这样:

myfloat.i[0]=EEPROM_READ(0);
myfloat.i[1]=EEPROM_READ(1);
myfloat.i[2]=EEPROM_READ(2);
myfloat.i[3]=EEPROM_READ(3);

然后在程序中继续使用Test.j就可以了。

4、寄存器的定义,实现整体的访问和单项的访问

struct register
{
    char a;
    char b;
    char c;
    char d;
};

union Register
{
   struct register;
   int whole;
};

这样就能实现单项和整体的访问,特别是引入位域操作等相关结构以后,能够实现每一个bit的访问。

2019-07-13 11:38:06 qq_41958198 阅读数 46
  • Docker入门与进阶实战

    Docker是一个开源的应用容器引擎,使用Go语言开发, 基于Linux内核的cgroup,namespace,Union FS等技术,对应用进程进行封装隔离,并且独立于宿主机与其他进程。Docker理念是将应用及依赖包打包到一个可移植的容器中,可发布到任意Linux发行版Docker引擎上。 使用沙箱机制运行程序,程序之间相互隔离。 Docker技术已经成为开发、运维职位必备的专业技能之一,非常有必要深入学习下,提供职业竞争力。 学完这门课程会获得什么? 首先从零开始教你安装Docker。接下来,学习Docker核心功能,例如镜像、容器、网络等知识点,再教你如何 定制化容器镜像并使用Harbor统一管理容器镜像,然后图形管理和容器监控。贴近企业生产环境讲解,即学即用,确保实用性,实战性!

    3699 人正在学习 去看看 李振良

Disjoint Sets是一种用于互质集合(一个元素不同使包含于多个集合的集合)对数据进行分类管理的数据结构。这种数据结构可以有效的动态处理一下操作。

  • makeSet(x):创建仅包含元素x的新的集合
  • findSet(x):求包含元素x的集合的“代表”元素
  • unite(x):合并指定的元素x、y

在Disjoint Sets中,查询“指定的两个元素x、y是否包含于同一个集合”的操作称为Union FInd。

直接一点的Union FInd类似家谱图的构造。

#include<iostream>
#include<string>
using namespace std;
int fa[100];
int findfa(int x){
	return fa[x]==x?x:(fa[x]=findfa(fa[x]));
}
void merge(int x,int y){
	//x祖先的值用y祖先的值代替 
	fa[findfa(x)]=findfa(y);
}
int main(){

	int n;
	cin>>n;
    //将自己祖先设为自己
	for(int i=0;i<n;i++){
		fa[i]=i;
	}
	int m,x,y;
	cin>>m;
	for(int i=0;i<m;i++){
		cin>>x>>y;
        //建立关系修改祖先
		merge(x,y);
	}
	for(int i=0;i<n;i++){
		cout<<i<<"的祖先: "<<fa[i]<<endl;
	}
	return 0;
} 

 以上的findfa()、merge()这两个函数可以完成并查集。

回归正题,在Dijoint Sets中我们将各个树的根结点用作区分集合的代表元素(representative)。因此,findSet(x)将返回元素x所属的树的根结点的值。为了是根结点可以输出,我们将根节点的父结点指向本身。

findSet(x)的复杂度等于结点到代表元素之间所经历的指针数,即树的高度。所有我们需要适当的进行路径压缩,也就是在求代表元素的同时,对起始到代表元素之间的路径上的所有结点都进行修改。如下就是个例子。

这样我们会得到一个更低的树,能够以极低的复杂度来完成。接下来就是unite(x,y),结合各个集合我们依据树的高度。在这里我们将各结点x为根的树的高度记入变量rank[x]。初始状态下每个集合中都只有一个元素,因此rank[x]的值全部为0。

不同高度的将低树指向高树。


考察:通过路径压缩和rank的算法实现分析起来十分复杂,不过其算法的复杂度要低于O(logn)。

#include<iostream>
#include<vector>
using namespace std;
class DisjointSet{
	public:
		vector<int>rank,p;
		
		DisjointSet(){}
		DisjointSet(int size){
			rank.resize(size,0);
			p.resize(size,0);
			for(int i=0;i<size;i++)
				makeSet(i);
		} 
		
		void makeSet(int x){
			p[x]=x;
			rank[x]=0;
		}
		
		bool same(int x,int y){
			return findSet(x)==findSet(y);
		}
		
		void unite(int x,int y){
			link(findSet(x),findSet(y));	
		} 
		
		void link(int x,int y){
			if(rank[x]>rank[y]){
				p[y]=x;
			}else{
				p[x]=y;
				if(rank[x]==rank[y]){
					rank[y]++;
				}
			} 
		}
		
		int findSet(int x){
			if(x!=p[x]){
				p[x]=findSet(p[x]);
			}	
			return p[x];
		}
};
int main(){
	int n,a,b,q;
	int t;
	cin>>n>>q;
	DisjointSet ds = DisjointSet(n);
	
	for(int i=0;i<q;i++){
		cin>>t>>a>>b;
		if(t==0)
			ds.unite(a,b);
		else if(t==1){
			if(ds.same(a,b))
				cout<<1<<endl;
			else
				cout<<0<<endl;
		}
	}
	return 0;
}
/*
输入 
5 12
0 1 4
0 2 3
1 1 2
1 3 4
1 1 4
1 3 2
0 1 3
1 2 4
1 3 0
0 0 4
1 0 2
1 3 0
输出 
0
0
1
1
1
0
1
1
*/

最小生成树可以通过下述克鲁斯卡尔算法(Kruskal's Algorithm)求出。

基本步骤:

  • 将图G=(V,E)的边e_{i}按权值升序排列
  • 设最小生成树的边的集合为K,并将其初始化设为空。
  • 在保证K\bigcup { e_{i} }不出现环的前提下,按i=1,2,...,|E|的顺序将e_{i}添加至K,直至|K|=|V|-1。
class Edge{
	public:
		int source,target,cost;
		Edge(int source=0,int target=0,int cost=0):
			source(source),target(target),cost(cost){}
		bool operator < ( const Edge &e ) const{
			return cost<e.cost;
		}
};
int kruskal(int N,vector<Edge> edges){
	int totalCost = 0;
	sort(edges.begin(),edges.end());
	
	DisjointSet dset = DisjointSet(N+1);
	
	for(int i=0;i<N;i++) dset.makeSet(i);
	for(int i=0;i<edges.size();i++){
		Edge e = edges[i];
		if(!dset.same(e.source,e.target)){ 
			totalCost+=e.cost;
			dset.unite(e.source,e.target);
		} 
	}
	
	//for(int i=0;i<N;i++){
		//cout<<i<<" "<<dset.p[i]<<endl;
	//}
	return totalCost; 
}

 

2013-05-09 09:19:24 u010224394 阅读数 1423
  • Docker入门与进阶实战

    Docker是一个开源的应用容器引擎,使用Go语言开发, 基于Linux内核的cgroup,namespace,Union FS等技术,对应用进程进行封装隔离,并且独立于宿主机与其他进程。Docker理念是将应用及依赖包打包到一个可移植的容器中,可发布到任意Linux发行版Docker引擎上。 使用沙箱机制运行程序,程序之间相互隔离。 Docker技术已经成为开发、运维职位必备的专业技能之一,非常有必要深入学习下,提供职业竞争力。 学完这门课程会获得什么? 首先从零开始教你安装Docker。接下来,学习Docker核心功能,例如镜像、容器、网络等知识点,再教你如何 定制化容器镜像并使用Harbor统一管理容器镜像,然后图形管理和容器监控。贴近企业生产环境讲解,即学即用,确保实用性,实战性!

    3699 人正在学习 去看看 李振良

一:union find简介

二:union find实现

三:union find应用举例



一:union find简介


           union find 并查集是专门针对检测动态连通性的一种数据结构。什么问题会用到动态连通性?举个简单的例子当我们有一张图,上面连满了点如何判断两个点之间是否有可以连通的路径。



              并集查通常用来解决图的连通性的问题。“图”当然不仅仅限于图片。图片中的两个像素点是否连通可以用union find,人与人直接的关系此类联系也通常可以看作是图,比如我们想查看在N个人的朋友关系中,其中的两个人是否有间接的联系我们也可以用union find。

              union的运用集中在解决是否具有连通性此类问题上,当如下事物需要解决一些联通性问题时运用union find这种数据结构来模拟非常合适:

  • 图片中的像素点Tarjan算法
  • 计算机网络中的节点
  • 社交网络中的节点
  • 数学集合中的元素

             union find算法的一些经典应用包括:

  • Hoshen-Kopelman算法  (用来判断网格中节点的连续性)
  • Kruskal最小生成树算法   
  • Tarjan算法                         (寻找最近公共祖先)
  • Prelocation theory       (物理,化学中的著名理论,不太了解)

二:union find的实现


      union find是一个以连续地址为底层存储的数据结构,通常是数组。在这个结构中我们以数组的索引来表示对应的元素,数组中索引对应的元素的值表示元素的父节点。举例 array[1] 表示元素1,array[1]的值为2代表元素1的父节点为元素2。我们可以从一个元素一直查找到它的根节点。根节点的特征就是元素索引和数组中元素索引对应的值相等,比如元素array[5]=5 ,元素5的值为5,代表元素5的父节点为自己,也就是说元素5是根节点。当两个元素的跟节点相等时我们便说两个根节点是相连通的。下面我们举一个例子:



0 1 1 3 3 0 1 3 3

在这之中 0,5,6都是联通的,所以他们的根节点应该为一样0。1,2,7联通对应的元素根节点都为1。3,4,8,9联通对应的根节点3。(为了简单我们暂时将所有节点的值都设为他们的根节点)


查找操作:

                 查找两个节点是否连通,我们可以通过两个节点的根节点是否相同来进行比较。查找一个节点根节点的操作就是递归查找该节点父节点的操作。

                 

int root(int i)
{
        while(i!=_array[i])   //根元素条件_array[i]=i
                 i=_array[i];
        return i;
}
               通过比较跟节点是否相同来判断两个节点是否联通

bool is_connected(int i ,int j )
{
        return true:false ? root(i) == root(j);
}


合并操作:

                合并两个节点的操作,一种非常简便的操作即是让其中一个节点的根节点的值变为另外一个节点根节点的值。即是削掉一个根节点让它的父节点等于另外一个节点的根节点。

               我们还是以上面的图为例子,假设我们现在合并节点1和6(我们总是让后一个节点的根节点改变),我们只要让6的根节点的父节点变为1的根节点就行了

  

0 0 1 3 3 0 1 3 3

             这里我们将array[1]的父节点改为了0,因为array[1]是1,2,7集合的根节点,而0是0,5,6集合的根节点。

             

void union(int i , int j )  //联通节点i,j
{
       _array[root(j)] = root(i); //将j的根节点的父节点设为i的根节点
}

           用这种方式实现的并查集叫做快速并查集(quick-union)。quick-union的合并操作最坏操作时间O(n),最坏查找连通性时间O(n)。如果按照平均来说应该是介于O(lgn)与O(n)之间。

改进一 平衡并查集:

              上面只是一个最基本的并集查找的实现,这个实现有一个非常知名的缺陷就是在某种特殊情况下它的查找和合并操作的耗时接近O(n)。为什么会出现这种最坏的情况?看下面的图



当我们执行操作union(4,1),union(5,1),union(6,1)时,因为我们总是改变1的根节点指向前一个节点所以造成下面这种情况。



当我们查找3的根节点的时候我们将耗时6步,即O(n)。


改变这种情况的方法就是当我们执行union操作的时候先判断联通的两个节点的哪边的集合大,我们把小的节点连接到大的节点的根节点就可以避免这种情况了。(刚才造成上面极端情况的原因的我们老是把大的集合的根节点连接到小的集合的根节点)。这种改进便是所说的平衡并查集(weighted quick-union)。


平衡并查集的实现需要除了原有的存储数据,还要加上各个集合大小数据。我们这里用一个额外的数组_size[]来表示。(一个集合的大小只保存在这个结合的根结点上_size[root] )

int _size[SIZE]//用来存储每个节点所在的集合大小
int _array[SIZE]//存储各个节点的集合的大小

void union(int i ,int j)
{
       int rooti = root(i);   //得到i的根节点
       int rootj = root(j);   //得到j的根结点
       if( _size(rooti) > _size(rootj) )   //比较i属于的集合与j属于的集合的大小
              {
                _array(rootj) = _array(rooti); //如果i的集合较大,我们将j的根结点的父节点设置为i的根结点
                _size(rooti) += _size(rootj);  //更新合并后的新集合大小,一个集合的大小只保存在它的根结点

              } 
       else
              {
                _array(rooti) = _array(rootj);
                _size(rootj) += _size(rooti);
              }
}

               运用平衡并查集之后,root()函数的时间复杂度可以达到近似O(lgn)的情况,如果画一张树状,并仔细观察合并的过程,可以很容易的推到出为什么会得到近似O(lgn)时的时间复杂度。这里简而言之就是只有到两个深度的集合(树)合并才能让合并的后的树的深度+1。由于上面我并没有太多用树的方法来说明并查集所以说出来有点抽象。


改进二 路径压缩:

              第二种改进,不得不说还是得从树的角度来阐述。看下面这张图。途中圆圈中的数字表明节点的索引,连线表明父子关系(在线段上方的为父节点)。


         可以看到这个集合的深度为6。当我们对“11”节点执行root()操作的时候,我们会逐渐遍历它的父节点直到到达根结点0为止,比较次数为6与深度相等。

         那么我们有不有办法使这个过程缩短呢?这就是我们接下来要提到的path compression(路径压缩)。当我们执行root()操作的时候我们将可以将我们遍历的每个父节点的父节点直接连接到根结点这样深度就得到压缩了。这个压缩操作一直执行下去的话我们会发现这个集合的深度最终将变为2层。

          假设我们对"11"执行root()操作,第一个遍历的父节点为"9"如上图红点所示。我们将“9”的父节点直接设为根结点如下图


然后在接着第一副图的足迹遍历,下一个节点即是“6”,我们将“6”的父节点设置为根结点


接着第一副图的足迹接下来是节点“3”,然后是节点“1”,到根结点“0”结束操作。最终操作如下


                     进行路径压缩虽然会逐渐减少集合(树)的深度,但是这个减少的过程本身也增加了root()操作的耗时。但是从总的来说这个消耗得到的收益随着union的大小增长也呈现飞速增长。来看看path compression的具体实现。

int root(int j) 
{
        int i = j;
        while(i !=_array[i])   //根元素条件_array[i]=i  
              i =_array[i];
        path_compression(i , j) //利用查找到的根结点i来对j的路径压缩
        return i;
}


void path_compression(int root,int i)
{
          while( i != _array[i] ) 
          {
                _array( _array[i] ) = root; //将遍历的父节点的父节点设为根结点 
                i = _array[i]; 
          }
}


这种path-compression 也即是我们上图所描述的path_compression,这种方法先搜索一次路径查找到根结点,然后利用查找到的根结点来进行路径压缩,即是搜索了两次路径。

                      还有一种只搜索路径一次便可以进行路径压缩的方法,这种压缩方法使路径中的父节点的父节点等于它的上一级的父节点(就像这个节点向上跳跃了一级),它的的压缩使路径深度减半。因为只搜索一次路径所以在时间上节约不少,但是压缩效果可能不如地一种。

int root(int j)  //跟前面的方法一致
{
        int i = j;
        while(i !=_array[i])   //根元素条件_array[i]=i
        {         
                  _array[i] = _array[ array[i] ];//只增加了一行,使父节点的父节点指向它的上一级的父节点 
                  i =_array[i];
        }                  
        return i;
}


2018-11-18 14:41:28 jmh1996 阅读数 124
  • Docker入门与进阶实战

    Docker是一个开源的应用容器引擎,使用Go语言开发, 基于Linux内核的cgroup,namespace,Union FS等技术,对应用进程进行封装隔离,并且独立于宿主机与其他进程。Docker理念是将应用及依赖包打包到一个可移植的容器中,可发布到任意Linux发行版Docker引擎上。 使用沙箱机制运行程序,程序之间相互隔离。 Docker技术已经成为开发、运维职位必备的专业技能之一,非常有必要深入学习下,提供职业竞争力。 学完这门课程会获得什么? 首先从零开始教你安装Docker。接下来,学习Docker核心功能,例如镜像、容器、网络等知识点,再教你如何 定制化容器镜像并使用Harbor统一管理容器镜像,然后图形管理和容器监控。贴近企业生产环境讲解,即学即用,确保实用性,实战性!

    3699 人正在学习 去看看 李振良

这节 我们来看看,Union-Find 并查集这种数据结构来。

并查集用于解决快速判断两个元素是否来自同一个集合的很高效(FIND操作)以及合并两个集合的元素(UNION)的数据结构。
并查集广泛用于 图的连通性检查、Kruskal 最小生成树等问题中,在实际应用以及ACM竞赛中用的也是特别多。
根据不同的实现方法,并查集可以取得不同的时间复杂度,其中带有路径压缩以及rank的实现 每次FIND和UNION可以平均取得几乎常数的时间复杂度。而带rank的实现每次FIND和UNION可以平均取得O(logn)的复杂度。
在这里插入图片描述

其实并查集的思想就是很简单的:每一个集合使用一个代表元来表示这个集合。

基于数组的实现

在这里插入图片描述
我们给每个集合用一个数字来表示这个集合的代表元,初始化的时候每个元素自成一个集合。这种方式下FIND()很快,只需要O(1)的复杂度。每个元素都需要使用数组中的某个元素来表示它所在的集合。
但是这种方式的合并就不是很快了,集合A,B合并的时候,需要把其中的一个集合的所有元素对应的标记都做修改。这是需要O(n)的复杂度。
在这里插入图片描述

基于树的实现

既然基于数组的实现是把每个集合用一个数组来表示,这样在合并的时候会很低效。那如果我们使用树来组织一个集合呢?用树的树根元素来标识这个集合,每个找某个元素所在的集合的时候都往上遍历找到它所在树的根。这样子 在合并的时候 就只维护好树根就可以啦。
在这里插入图片描述
合并时的伪代码:
在这里插入图片描述

用树组织一个集合的确在"合并"的时候很快了,但是嘞,查找的时候就有一些“意外”情况不好解决了。
例如:
存在如下的一个合并序列:
在这里插入图片描述
这个集合的树就变得相当的不平衡了,此时从FIND( C )的时候需要花费O(n)的时间。相应的,因为UNION的时候需要先找到两个元素的树根,招致UNION也需要花费O(n)。

那么解决方法是什么呢? 如果我们能够让这颗树“平衡”一下就好啦,不要让某个集合出现这么诡异的树出来。

基于树+rank的实现

我们给树的每个节点定义一个rank,这个rank表示以这个节点为树根的子树的高度,只含有一个元素的节点的rank为0。合并两个集合的时候,我们把低rank的节点当做高rank树根的孩子;如果两个rank相等,谁成为谁的孩子都没有关系,但是成为父亲的那个节点需要把自己的rank自增1,因为高度增加了。
FIND过程:
在这里插入图片描述
UNION过程:
在这里插入图片描述
通过这么做,就可以控制各个树的深度都不会超过logn。这是为什么呢?
这是因为,当两个rank相同的节点合并起来,其中一个节点的rank会加一,当这个节点不在和与他具有相同rank的节点合并时,它的rank不变,所有rank小于它的节点都可以成为它的孩子。于是,一个树根节点的rank为k,那么这个树至少会包含2k2^{k}个节点。显然,当n个节点全部在同一个集合的时候,这个集合的最大深度为 lognlog n.
取得这个效果还是蛮不错的了。
但是,我们来看看FIND函数:
在这里插入图片描述
对于下面这颗树:
在这里插入图片描述
如果我们执行一次FIND(t),查最下面那个元素的根,那么它就会沿着 t&gt;s&gt;o&gt;f&gt;at-&gt;s-&gt;o-&gt;f-&gt;a 直到树根a为止。其实,我们可以知道的,从t往a的这一条路径的所有节点的树根都是a了。如果我们把这条路径的所有节点都直接指向a,那么下次FIND(s),其实应该直接返回a了。那么 我们怎么实现这一点呢?

基于树+rank+路径压缩的实现

在这里插入图片描述
方法很巧妙,递归返回的时候把这个节点的父节点改成根。
直观上把握,通过这种方式,同一个集合中的很多元素都会直接指向它的树根,如果此时不是指向树根,那么只要一次FIND,那么它就会直接指向树根了。
通过借助势函数分析,我们可以得到FIND(x)和UNION(x,y)的时间复杂度是lognlog * n。这是什么鬼东西呢?
我们定义函数f:N&gt;Nf:N-&gt;N.
其中f(2)=1f(2)=1,f(n)=1+f(log2(n))f(n)=1+f(log_{2}(n))当n>2时。其实就是一个数n做几次log运算就可以把它变成1,而这个f就是log*n的定义。
举个例子:
f(216)=1+f(16)=1+f(24)=2+f(22)=3+f(2)=4f(2^{16})=1+f(16)=1+f(2^4)=2+f(2^2)=3+f(2)=4
f(2216)=f(265536)=1+f(216)f(2^{2^{16}})=f(2^{65536})=1+f(2^{16})=5
em~~~~~ log265536log * 2^{65536}都才5,这得是有多快哦。

应用

NUMBER ISLAND
寻找小岛个数。

https://leetcode.com/problems/number-of-islands/description/

class Solution {
public:
	struct _point
	{
		int i, j;
		int rank = 0;
		_point(int _i, int _j, int _rank)
			:i(_i), j(_j), rank(_rank)
		{
		}
		bool operator !=(_point const & rhs) const
		{
			return i != rhs.i || j != rhs.j;
		}
		bool operator ==(_point const & rhs) const
		{
			return i == rhs.i && j == rhs.j;
		}
		bool operator < (_point const & rhs) const
		{
			return i < rhs.i || (i==rhs.i && j < rhs.j);
		}
	};
	_point  find(_point x ,vector< vector<_point> > & parent)
	{
		if (parent[x.i][x.j] != x)
		{
			_point rst = find(parent[x.i][x.j],parent);
			parent[x.i][x.j] = rst;
			return rst;
		}
		else
		{
			return parent[x.i][x.j];
		}
	}
	void unions(_point x, _point y, vector<vector <_point> > & parent, set<_point> & island)
	{
		_point xf = find(x, parent);
		_point yf = find(y, parent);
		if (xf == yf)
		{
			return;
		}
		if (xf.rank < yf.rank)
		{
			parent[xf.i][xf.j] = yf;
			island.erase(xf);
			}
		else
		{
			
			if (yf.rank == xf.rank)
			{
				parent[xf.i][xf.j].rank++;
			}
			parent[yf.i][yf.j] = xf;
			island.erase(yf);
		}
	}
	int numIslands(vector<vector<char>>& grid) {
		vector< vector<_point> > parent;
		set< _point> islands;
		for (int i = 0; i < grid.size(); i++)
		{
			parent.push_back(vector<_point>());
			for (int j = 0; j < grid[i].size(); j++)
			{
				parent[i].push_back(_point( i, j, 0 ));
				if (grid[i][j] == '1')
				{
					islands.insert(_point( i, j, 0 ));
					if ((i - 1) >= 0 && grid[i - 1][j] == '1')
					{
						unions(_point( i, j, 0 ), _point( i - 1, j, 0 ), parent, islands);
					}
					if ((j - 1) >= 0 && grid[i][j - 1] == '1')
					{
						unions(_point( i, j, 0 ), _point( i, j - 1, 0 ), parent, islands);
					}

				}
			}
		}
		return islands.size();
	}
	
};

LONGEST CONSECUTIVE SEQUENCE

https://leetcode.com/articles/longest-consecutive-sequence/
在O(n)的时间内,找出数值上连续递增的最长子序列。
例如:
Input: [100, 4, 200, 1, 3, 2]
Output: 4
Explanation: The longest consecutive elements sequence is [1, 2, 3, 4]. Therefore its length is 4.

解题思路:
对于输入数据的任意元素x,尝试让它与x-1 合并,然后尝试让它与x+1合并(如果x-1,x+1都存在的话)。使用并查集来把数值上连续递增的元素划分到一个一个集合中,同时,使用并查集来维护各集合中元素个数。

class Solution {
public:
	struct _node
	{
		int parent;
		int num_cnt;
		int rank;
	};
	int find(int x,map<int ,_node> &cnt)
	{
		if (cnt[x].parent != x)
		{
			int rst = find(cnt[x].parent, cnt);
			cnt[x].parent = rst;
			return rst;
		}
		else
		{
			return cnt[x].parent;
		}
	}
	void unions(int x, int y, map<int, _node> & cnt, int &maxcnt)
	{
		int fx = find(x, cnt);
		int fy = find(y, cnt);
		if (fx == fy)
			//相同就不再合并
		{
			return;
		}
		if (cnt[fx].rank < cnt[fy].rank)
		{
			cnt[fx].parent = fy;
			cnt[fy].num_cnt += cnt[fx].num_cnt;
			if (cnt[fy].num_cnt > maxcnt)
			{
				maxcnt = cnt[fy].num_cnt;
			}
		}
		else
		{
			cnt[fy].parent = fx;
			if (cnt[fy].rank == cnt[fx].rank)
			{
				cnt[fx].rank++;
			}
			cnt[fx].num_cnt += cnt[fy].num_cnt;
			if (cnt[fx].num_cnt > maxcnt)
			{
				maxcnt = cnt[fx].num_cnt;
			}
		}
	}
	int longestConsecutive(vector<int>& nums)
	{
		map<int, _node> cnt;
		int maxcnt = nums.size() ? 1 : 0;
		for (int i = 0; i < nums.size(); i++)
		{
			int num = nums[i];
			if (cnt.find(num) == cnt.end())
			{
				cnt[num].num_cnt = 1;
				cnt[num].parent = num;
				cnt[num].rank = 0;
			}
			if (cnt.find(num - 1) != cnt.end())
				//把它和左边的元素合并
			{
				unions(num, num - 1, cnt, maxcnt);
			}
			if (cnt.find(num + 1) != cnt.end())
				//把它和大于它的元素合并
			{
				unions(num, num + 1, cnt, maxcnt);
			}
		}
		return maxcnt;
	}
};
2015-08-15 11:14:04 liuyanfeier 阅读数 447
  • Docker入门与进阶实战

    Docker是一个开源的应用容器引擎,使用Go语言开发, 基于Linux内核的cgroup,namespace,Union FS等技术,对应用进程进行封装隔离,并且独立于宿主机与其他进程。Docker理念是将应用及依赖包打包到一个可移植的容器中,可发布到任意Linux发行版Docker引擎上。 使用沙箱机制运行程序,程序之间相互隔离。 Docker技术已经成为开发、运维职位必备的专业技能之一,非常有必要深入学习下,提供职业竞争力。 学完这门课程会获得什么? 首先从零开始教你安装Docker。接下来,学习Docker核心功能,例如镜像、容器、网络等知识点,再教你如何 定制化容器镜像并使用Harbor统一管理容器镜像,然后图形管理和容器监控。贴近企业生产环境讲解,即学即用,确保实用性,实战性!

    3699 人正在学习 去看看 李振良

叫做并查集的主要原因是该数据结构的主要操作是:

1:合并区间(union

2:查找元素所属区间(find

所以叫做并查集

 

如果给出各个元素之间的联系,要求将这些元素分成几个集合,每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找,因此将这种集合称为并查集。

 

问题:若某个家族人员过于庞大,要判断两个是否是亲戚,确实还很不容易,给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。 规定:xy是亲戚,yz是亲戚,那么xz也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。

 

要解决这个问题或许可以使用图论,最后判断两个人是否在一个连通子图中,但是考虑到复杂度等我们发现这样并不好处理并且当数据很多的时候会很费时间。这时候我们考虑使用并查集。

 

就动态连通性这个场景而言,我们需要解决的问题可能是:

给出两个节点,判断它们是否连通,如果连通,不需要给出具体的路径

给出两个节点,判断它们是否连通,如果连通,需要给出具体的路径

 

就上面两种问题而言,虽然只有是否能够给出具体路径的区别,但是这个区别导致了选择算法的不同,本文主要介绍的是第一种情况,即不需要给出具体路径的Union-Find算法,而第二种情况可以使用基于DFS的算法。

 

思想基本都体现在下面的一步一步改进的代码中了,请仔细看。


//简单数组,也可看做是使用了链表的数组化
//#include <iostream>
//#include <cstdio>
//#include <cstring>
//#include <string>
//#include <queue>
//#include <algorithm>
//#include <cmath>
//#include <iomanip>
//#include <stack>
//using namespace std;
//
//const int maxn = 1000005;
//int a[maxn];   //a[i]表示的是结点i的组号,初始值是
//int n,m,coun;//count记录一共有多少组
//
//int find(int ind)
//{
//    return a[ind];//查找ind的组号
//}
//
//void unio(int p,int q)
//{
//    int pID=find(p);
//    int qID=find(q);//获得p和q的组号
//    if(pID==qID)return ;
//    for(int i = 0 ; i < n ; i++)
//    {
//        if(a[i]==pID)a[i]=qID;
//        //将两组合并,组号都变为qID
//    }
//    coun--;//组数减少1
//}
//
//int main()
//{
//    while(1)
//    {
//        int p,q;
//        scanf("%d%d",&n,&m);
//        coun=n;//初始时候每个节点都是一组
//        for(int i = 0 ; i < n ; i++)
//        {
//            a[i]=i;
//        }
//        for(int i = 0 ; i < m ; i++)
//        {
//            scanf("%d%d",&p,&q);//表示结点p和q连通
//            unio(p,q);
//        }
//        int t = 4;
//        while(t--)
//        {
//            scanf("%d%d",&p,&q);
//            if(find(p)==find(q))printf("YES\n");
//            else printf("NO\n");
//        }
//    }
//    return 0;
//}
////最简单的并查集,可以看到unio函数每次更新结点所属的组号的时候
////时间复杂度是O(n),这样总的时间复杂度就是O(m*n),可能会超时



////使用树形结构
//#include <iostream>
//#include <cstdio>
//#include <cstring>
//#include <string>
//#include <queue>
//#include <algorithm>
//#include <cmath>
//#include <iomanip>
//#include <stack>
//using namespace std;
//
//const int maxn = 1000005;
//int a[maxn];   //a[i]表示的是结点i的组号,初始值是
//int n,m,coun;//count记录一共有多少组
//
//int find(int p)
//{
//    while(p!=a[p])p=a[p];
//    return p;//查找p的组号(根节点)
//}
//
//void unio(int p,int q)
//{
//    int pRoot=find(p);
//    int qRoot=find(q);//获得p和q的组号
//    if(pRoot==qRoot) return ;
//    a[pRoot]=qRoot;//之后将根节点改变就相当于将该组的所有节点所在组都改论了
//    coun--;//组数减少1
//}
//
//int main()
//{
//    while(1)
//    {
//        int p,q;
//        scanf("%d%d",&n,&m);
//        coun=n;//初始时候每个节点都是一组
//        for(int i = 0 ; i < n ; i++)
//        {
//            a[i]=i;
//        }
//        for(int i = 0 ; i < m ; i++)
//        {
//            scanf("%d%d",&p,&q);//表示结点p和q连通
//            unio(p,q);
//        }
//        int t = 4;
//        while(t--)
//        {
//            scanf("%d%d",&p,&q);
//            if(find(p)==find(q))printf("YES\n");
//            else printf("NO\n");
//        }
//    }
//    return 0;
//}
//树形结构容易出现极端情况,即所有的子节点在一行形成一个链表
//这时候在查找的时候会很浪费时间。



//其实现在这颗树已经很节减了,但我们永远要追求更完美,那么怎么样才能使
//结果更完美呢,我们看到现在我们所有的操作的时间都花费在查找函数上面了,
//那查找函数还可以在压缩一下时间吗,这腰取决于这颗树是怎么样的。假如每一
//颗树的深度都是1,也就是说所有的结点都直接挂在根结点上面,那么这棵树
//是不是查找起来很方便了。但这是理想状态,很难达到,但是我们可以尽可能的
//使数的深度更小。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
using namespace std;

const int maxn = 1000005;
int a[maxn];   //a[i]表示的是结点i的组号,初始值是
int s[maxn];   //s[i]表示的是结点i所属的组中结点的个数(数的大小)
int n,m,coun;  //count记录一共有多少组

int Find(int p)
{
     //一种更好的路径压缩
     //二分压缩路径(compresses paths by halving):
     //具体思想就是把当前的结点,跳过一个指向父亲的父亲,
     //从而使整个路径减半深度减半。
     //这种办法比满路径压缩要快那么一点点。数据越大,当然区别就会越明显。
    while(p!=a[p])
    {
        a[p]=a[a[p]];
        //添加这样一行代码,将每个节点都挂在原父节点的
        //父节点上面,查找的时间复杂度至少少一半
        //路径压缩,在集合的查找过程中顺便将树的深度降低
        p=a[p];
    }
    return p;//查找p的组号(根节点)


    //满路径压缩(full compresses paths):这是一种极其简单但又很常用的方法。
    //就是在添加另一个集合的时候,把所有遇到的结点都指向根节
//    if(p!=a[p])
//        a[p]=Find(a[p]);
//    //在递归回来的时候把路径上元素的父亲指针都指向根结点。
//    return a[p];

}

void Union(int p,int q)
{
    int pRoot=Find(p);
    int qRoot=Find(q);//获得p和q的组号
    if(pRoot==qRoot) return ;
    //将小数作为大数的子树
    //按秩进行合并
    if(s[pRoot]<s[qRoot])
    {
        a[pRoot]=qRoot;
        s[qRoot]+=s[pRoot];
    }
    else
    {
        a[qRoot]=pRoot;
        s[pRoot]+=s[qRoot];
    }
    //之后将根节点改变就相当于将该组的所有节点所在组都改论了
    coun--;//组数减少1
}

int main()
{
    while(1)
    {
        int p,q;
        scanf("%d%d",&n,&m);
        coun=n;//初始时候每个节点都是一组
        for(int i = 0 ; i < n ; i++)
        {
            a[i]=i;s[i]=1;
        }
        for(int i = 0 ; i < m ; i++)
        {
            scanf("%d%d",&p,&q);//表示结点p和q连通
            Union(p,q);
        }
        int t = 4;
        while(t--)
        {
            scanf("%d%d",&p,&q);
            if(Find(p)==Find(q))printf("YES\n");
            else printf("NO\n");
        }
    }
    return 0;
}



//我们考虑一下上面代码中的unio函数中的这一段,a[pRoot]=qRoot;
//有没有问题呢,一看好像没有问题,一个简简单单的赋值操作。但是我们
//看到这个操作是直接赋值的,并没有进行什么判断,其实我们每次需要的
//是将一颗比较小的数挂在一颗大一点的数上面,所以需要判断
//#include <iostream>
//#include <cstdio>
//#include <cstring>
//#include <string>
//#include <queue>
//#include <algorithm>
//#include <cmath>
//#include <iomanip>
//#include <stack>
//using namespace std;
//
//const int maxn = 1000005;
//int a[maxn];   //a[i]表示的是结点i的组号,初始值是
//int s[maxn];   //s[i]表示的是结点i所属的组中结点的个数(数的大小)
//int n,m,coun;  //count记录一共有多少组
//
//int find(int p)
//{
//    while(p!=a[p])p=a[p];
//    return p;//查找p的组号(根节点)
//}
//
//void unio(int p,int q)
//{
//    int pRoot=find(p);
//    int qRoot=find(q);//获得p和q的组号
//    if(pRoot==qRoot) return ;
//    //将小数作为大数的子树
//    if(s[pRoot]<s[qRoot])
//    {
//        a[pRoot]=qRoot;
//        s[qRoot]+=s[pRoot];
//    }
//    else
//    {
//        a[qRoot]=pRoot;
//        s[pRoot]+=s[qRoot];
//    }
//    //之后将根节点改变就相当于将该组的所有节点所在组都改论了
//    coun--;//组数减少1
//}
//
//int main()
//{
//    while(1)
//    {
//        int p,q;
//        scanf("%d%d",&n,&m);
//        coun=n;//初始时候每个节点都是一组
//        for(int i = 0 ; i < n ; i++)
//        {
//            a[i]=i;s[i]=1;
//        }
//        for(int i = 0 ; i < m ; i++)
//        {
//            scanf("%d%d",&p,&q);//表示结点p和q连通
//            unio(p,q);
//        }
//        int t = 4;
//        while(t--)
//        {
//            scanf("%d%d",&p,&q);
//            if(find(p)==find(q))printf("YES\n");
//            else printf("NO\n");
//        }
//    }
//    return 0;
//}


例题hdu1232

 

城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇。省政府畅通工程的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可)。问最少还需要建设多少条道路? 

 

思路:最简单明显的并查集



#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <stack>
using namespace std;

const int maxn = 1005;
int a[maxn];   //a[i]表示的是结点i的组号,初始值是
int s[maxn];   //s[i]表示的是结点i所属的组中结点的个数(数的大小)
int n,m,coun;  //count记录一共有多少组

int Find(int p)
{
     //一种更好的路径压缩
     //二分压缩路径(compresses paths by halving):
     //具体思想就是把当前的结点,跳过一个指向父亲的父亲,
     //从而使整个路径减半深度减半。
     //这种办法比满路径压缩要快那么一点点。数据越大,当然区别就会越明显。
    while(p!=a[p])
    {
        a[p]=a[a[p]];
        //添加这样一行代码,将每个节点都挂在原父节点的
        //父节点上面,查找的时间复杂度至少少一半
        //路径压缩,在集合的查找过程中顺便将树的深度降低
        p=a[p];
    }
    return p;//查找p的组号(根节点)


    //满路径压缩(full compresses paths):这是一种极其简单但又很常用的方法。
    //就是在添加另一个集合的时候,把所有遇到的结点都指向根节
//    if(p!=a[p])
//        a[p]=Find(a[p]);
//    //在递归回来的时候把路径上元素的父亲指针都指向根结点。
//    return a[p];

}

//一颗树要是连通并且没有环,最终的结果应该是结点的个数等于边的数目+1
void Union(int p,int q)
{
    int pRoot=Find(p);
    int qRoot=Find(q);//获得p和q的组号
    if(pRoot==qRoot) return ;   //此时说明这棵树有环
    //将小数作为大数的子树
    //按秩进行合并
    if(s[pRoot]<s[qRoot])
    {
        a[pRoot]=qRoot;
        s[qRoot]+=s[pRoot];
    }
    else
    {
        a[qRoot]=pRoot;
        s[pRoot]+=s[qRoot];
    }
    //之后将根节点改变就相当于将该组的所有节点所在组都改论了
    coun--;//组数减少1
}

int main()
{
    while(scanf("%d",&n)!=EOF&&n)
    {
        scanf("%d",&m);
        int p,q;
        coun=n-1;//初始时候每个节点都是一组
        for(int i = 1 ; i <= n ; i++)
        {
            a[i]=i;s[i]=1;
        }
        for(int i = 0 ; i < m ; i++)
        {
            scanf("%d%d",&p,&q);//表示结点p和q连通
            Union(p,q);
        }
        printf("%d\n",coun);
    }
    return 0;
}


struct union数据对齐

阅读数 282

union

阅读数 173

结构体与union

阅读数 837

没有更多推荐了,返回首页