单例模式浅谈

单例模式几种实现方式

单例模式作为设计模式中最简单，应用最广泛的一个，熟练掌握该设计模式无论对于面试还是项目使用，想来是极好的。最近也是看面试题的时候看到了这块，发现自己忘的都差不多了，又重新熟悉了下，并且综合网上各种混杂的实现方式以及四人帮的《设计模式》，把几种单例模式的关系捋清，并且给出自己的解答

总体呢，单例模式有两种，一种是懒汉，一种是饿汉，这两种是实现单例模式的不同思路。第一种呢，就是“懒”嘛，只有具体使用这个实例的时候才会去实例化。那饿汉则反之，程序一开始就实例化。

那明显呢，上述两者有自己的优缺点。懒汉的优点就是实例创建延迟至真正使用的时候，无疑对内存效率使用较高。但是缺点是不具有线程安全性，也就是说不做一些处理就不能适应多线程；饿汉的优点则是具有线程安全性，因为在程序运行一开始即在主线程已经实例化好了。但缺点则是内存效率较低。简单来说，懒汉是以时间换空间；饿汉是以空间换时间。

最简单的懒汉实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//类定义
class Singleton
{
	public:
    		static Singleton* GetInstance()
            {
            	if(m_Instance == NULL)
                {
                	m_Instance = new Singleton();
                }
                return m_Instance;
            }
     protected: Singleton(){}
     private:
     		static Singleton *m_Instance;
}
//初始化
Singleton *Singleton::m_Instance = nullptr;
//使用时
Singleton *obj=Singleton::GetInstance();

该实现方式是最简单的单例模式，但带来的问题是 不具有线程安全性，当多线程环境下，会实例化多个对象。所以就引申出下一个多线程模式。

懒汉多线程加锁实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//类定义
class Singleton
{
	public:
    		static Singleton* GetInstance()
            {
            	Lock();//具体实现可以采用boost库，或者用mutex变量
            	if(m_Instance == NULL)
                {
                	m_Instance = new Singleton();
                }
                UnLock();
                return m_Instance;
            }
     protected: Singleton(){}
     private:
     		static Singleton *m_Instance;
}

我们采用加锁的方式，因为一个时刻只有一个线程能得到锁，所以可以解决多线程问题。但是仔细分析又有一个问题，那就是每次去getInstance()时都会去加上一个锁，而加锁是一个很耗时的操作，所以在没必要的时候要避免去加锁。这就是下一个改进版的double-check。

懒汉多线程加锁改进实现（double-check）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//类定义
class Singleton
{
	public:
    		static Singleton* GetInstance()
            {
            	if(m_Instance == NULL)//前后两次判断，这样可以大大减少不必要的加锁操作
                {
            		Lock();
            		if(m_Instance == NULL)
                	{
                		m_Instance = new Singleton();
                	}
                	UnLock();
                }
                return m_Instance;
            }
     protected: Singleton(){}
     private:
     		static Singleton *m_Instance;
}

这种写法提高了效率，但是实现起来比较复杂而且容易出错。下来推荐更加优秀的写法。

懒汉最简洁实现（局部静态变量）

1
2
3
4
5
6
7
8
9
10
11
12
13
//类定义
class Singleton
{
	public:
    		static Singleton& GetInstance()
            {
            	static Singleton m_Instance;
                return m_Instance;
            }
     protected: Singleton(){}
}
//使用时
Singleton *obj=Singleton::GetInstance();

最简洁，没有之一。c++11标准可以保证局部静态变量的线程安全性，所以这种方式不仅简洁，而且不用考虑其他实现方式还要考虑的delete过程，所以非常推荐这种方法，不过这个也有一个不适用的地方，对于打印机，加锁的文件等并不是在不用的时候就delete掉，而是必须在程序结束时delete 的场景，这个实现方式就无法解决了。而饿汉的一种改进形式可以完美解决这个问题（通过内嵌一个static的类）。

饿汉实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//类定义
class Singleton
{
	public:
    		static const Singleton* GetInstance()
            {
                return m_Instance;
            }
     protected: Singleton(){}
     private:
     		static const Singleton *m_Instance;
}
//静态初始化
const Singleton *Singleton::m_Instance = new Singleton();
//使用时
Singleton *obj=Singleton::GetInstance();

由于在程序开始时即以静态初始化的方式 主线程完成了初始化，所以可以保证线程安全性。在性能要求比较高时，采用这种方式，可以避免频繁的加锁和解锁造成的资源浪费。

饿汉自动销毁实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//类定义
class Singleton
{
	public:
    		static Singleton* GetInstance()
            {
                return m_Instance;
            }
     protected: Singleton(){}
     private:
     		static Singleton *m_Instance;
            class GC
            {
            	public:
                		~GC()
                        {
                        	if(m_Instance != NULL)
                            {
                            	delete m_Instance;
                                m_Instance=NULL;
                            }
                        }
            }
            static GC gc;
}
//初始化
Singleton *Singleton::m_Instance = new Singleton();
Singleton ::GC Singleton ::gc;
//使用时
Singleton *obj=Singleton::GetInstance();

在程序运行结束后，系统会对静态存储区的变量释放，这就包括全局变量以及类的静态成员变量（这里是同等对待的），我们定义了Singleton私有的类GC来实现最终释放我们的实例。释放静态变量gc时，调用其析构函数~GC(),在这里实现了对m_Instance的释放。

总结

以上几种单例模式的实现都有其特点，根据实际场景可能会有所结合或者改动。目前来说c++的所有单例模式实现原理思路就是上述几种啦。其实还有一种更吊的方式，既能按需创建实例（即懒汉），又能自动释放，又很简洁。那就是c#的静态构造函数。具体实现机制自行百度。

转载请注明出处

展开全文 >>

Cocos2d-x基础知识

Cocos2d-x基础知识

近来要开始一项之前想了很久的计划，那么玩转cocos2d则是这个计划中的第一步，并且在接下来的一系列文章中会记录自己的学习过程，也算是一种监督吧。本文先来说一下自己对cocos2dx一些基本概念的理解，至于一些高级特性，以后边学边更新。

一 游戏框架

在coco2dx引擎中，采用树的结构来管理游戏对象。对于一个游戏来说（或者说你的一个工程），那么有且仅有一个导演Director来管理整个游戏的流程，比如场景的切换等等。它管理着多个场景Scene，而一个场景又分为不同的层Layer，每个层又有N个精灵Sprite。大致结构如下：

导演

在cocos2dx中把统筹游戏大局的类抽象为导演（Director），它是整个游戏引擎的核心，掌控着整个游戏的运作。比如场景的切换，游戏暂停开始，节点控制。因为导演只有一个，所以很自然的想到用单例模式来设计Director类。

场景

这个场景就相当于电影中的场景，比如一部电影可能需要很多个场地，不容的场景，而游戏也一样需要构建不同的场景。那么就像游戏的关卡，模块的切换就是一个个场景的切换。
它的重要应用就是配合导演实现流程控制。

层

层主要用来处理玩家响应，与抽象的场景不同，层包含的是直接在屏幕上显示的内容，通常我们需要在层中添加精灵或者其他游戏元素。主要用法就是在层中添加要素，并且编写对应的逻辑代码，组织好之后，把层按设计的顺序添加到场景中即可，使用addChild（）方法，在层中添加精灵也累死。
注意，Node类是几乎所有类的父类。

精灵

其实就是一个图片对象，比如游戏中的英雄，怪物，石头等等等等。精灵呢有动作（移动，旋转，动画神马的），主要由Texure，frame和animation组成，简单过程可描述为：使用Texture2D加载图片，可以用Texture2D生成对应的SpriteFrame（精灵帧），将SpriteFrame添加到Animation生成动画数据，用Animation生成Animate（就是最终的动画动作），最后用Sprite执行这个动作。

调度器

为游戏提供定时事件和定时调用服务。cocos2d呢总共提供了三种方式的调度器：默认；自定义的；单次的。默认的需要重载update函数来实现。而自定义和单次的则需要自己实现一个函数，通过schedule或scheduleOnce函数传入函数指针来做的。

二 渲染和动画

坐标系

标准屏幕坐标系：原点屏幕左上角，x向右，y向下。
OpenGL或 Cocos2d坐标系：原点为屏幕左下角，x向右，y向上。
游戏开发中常用到两种坐标系：世界坐标系，本地坐标系。世界坐标系就是针对于你的游戏世界的坐标，是绝对坐标。而本地的，因为cocos2d中元素是通过节点层级结构组织，所以本地坐标系指的是相对于父节点的坐标。

展开全文 >>

A*算法游戏中需要考虑的几点

在实际游戏开发过程中采用A*算法，考虑清楚以下几点并采取适当的策略，那么必然可以得到一种高效美观合适的优化算法。

  • 空间的划分：
    矩形栅格；四叉树；凸多边形；可见点；广义圆柱体

  • 相邻状态：
    取决于地图表示和量化方式。比如在正方形栅格中，量化方式是只选择相邻位置-取周围8个还是4个，还有量化方式是取周围一定量的点（跟定义的规则有关），还要考虑地形（障碍物或者陆军不能过海）

  • 代价：
    可以是距离，时间，花费点数等。这里还要考虑地形（穿越某种地形对应不同的代价）或者审美（看起来更直，更平滑。比如正方形栅格走对角比直线运动代价高）。甚至具有不对称性，从a-b代价比从b-a代价高（上坡等）

  • 估价：
    到目标点的估价不要太高估（会导致找不到路径），但也不要太低（比如取两点间欧式距离，会导致效率降低，虽然一定可以找到最短路径）。所以估价函数的建立既要考虑最终结果不能太高估，又要考虑速度适当放大，甚至冒着取一条“次优路径”的风险进行高估。

  • 目标：
    可能是多个目标点（比如一个角色在远处有多个攻击目标），所以需要首先获得这些目标，然后对一个新节点计算到每一个目标的cost，取最小的作为costToGoal。

另外，A算法一定不要用在判断两点是否有路径。因为假如无路径，会使一个大型地图几乎所有的点被搜索，效率最低。此时最好使用地图预分析，比如当两个点在两个隔离的岛上，则直接不调用A*。

展开全文 >>

人民网解析池简单分析

导语：

人民网是世界十大报纸之一《人民日报》建设的以新闻为主的大型网上信息交互平台，也是国际互联网上最大的综合性网络媒体之一。而作为一个著名的门户网站，信息量丰富，信息类别多样，网站结构复杂，反爬虫策略严密等特点使得结构化爬取该网站变得异常困难，本篇文章则重点讨论人民网网站结构以及给出一种较为有效的爬取策略。

一，网站整体结构

人民网的网站结构如下所示，该网站内部链接比较清晰，首页与频道页，专题页以及内容页之间都是互相链接的，所以这势必会造成很多的重复url，不过庆幸地是我们的框架可以很轻松地完成上亿条数据的去重，所以这就大大减轻了解析模块的负担。

二，页面内部结构

首页结构

经分析人民网首页结构整体如下，s代表多个标签

body顶部有两个div标签广告以及一个section标签广告。之后则是十几个section，中间掺杂着若干个div标签的广告，底部则是分站与友情链接模块。
很明显首页的所有新闻相关类链接全存在与section标签中（除去第一个），如此我们则可以通过这个特点来提取我们想要的url，比如通过xpath(“//section[position()>1 and position()<12]//a/@href”)。

获取url数据库展示：

频道页结构

由于人民网频道种类的繁多，经验证发现频道间结构有较大差异，只有个别频道（如时政，财经等）结构大致相同，而大多频道差异性很大，这就造成了无法通过分析结构来写一个通用的频道页解析方法。还有一个较为尴尬的问题–有些新闻的url是相对路径。考虑到这些特殊性，所以最终决定通过暴力获取所有url，然后过滤掉不满足要求的url并为相对路径补充父亲节点。

我们需要的url具有如下特点：

  • 字符串中包含n1–对应内容页
  • 字符串中包含GB–对应内专题页
  • 字符串中包含index–对应内频道页的翻页
  • 字符串以.people.com.cn结尾

具体代码如下：

self.links.append(selector.xpath(
    '//a/@href'
))
parent = url.split('/')[0]
self.links = filter(lambda x: '/n1' not in x and '/GB' not in x and 'index' not in x, self.links)
for i in range(0, len(self.links)):
    if self.links[i].startswith('/n1') or self.links[i].startswith('index'):
        self.links[i] = parent + '/' + self.links[i]

专题页结构

专题页面和频道页面差不多，甚至具有更大的差异性，所以我们采取和频道页面相同的处理方式。

内容页结构

内容页结构如下所示，标题都在class= text_title的div标签的h1标签下，而新闻正文则是在id=rwb_zw的div标签的p标签下。所以我们可以分别通过这两个xpath来获取相应的新闻标题和正文。

即xpath(“//h1/text()”)–标题,xpath(“//*[@id=”rwb_zw”]/p/text()”)–正文

数据库结果展示：

程序源代码: https://github.com/LZleejean/PeopleSpider

展开全文 >>

A*算法入门浅谈

A*算法浅析

在玩游戏时，我们遇到过这样的场景：接到一个任务，需要前往某个坐标（例如npc，某个地区），此时我们点击任务列表中的坐标，我们的角色就会自动前往该目标，并且可以自动的规避一些障碍或者死胡同。那么这种AI路径规划技术就是A算法。本文将会简单介绍A算法的概念，并且给出一个最为简单的例子。

概述

A*算法的原理呢，比较简单，这里我们就简单说明下。这个算法呢，是在状态空间上进行搜索的，通过检查某个状态的相邻状态来得到从起始状态到目标状态的最小代价路径。实质上就是反复检查它已经看到的但是还没有搜索到的最有希望的位置。而当目标位置被探索到时，算法终止。

原理

通过维护两张表（OPEN，CLOSED）来标记地图上的未检查状态和已检查状态，对于某个结点，检查其相邻状态，然后选择最好的状态继续检查，直至检查到目标点。

从上面这段描述来看，有没有感觉有点熟悉？dijktra算法。确实，有点像，不过看完下面这张图，你就知道和dj算法哪里不同了。

  • A*算法维护着一个父状态以保证最终可以从终点通过父结点来回溯找到完整的路径；而dj算法只是求最短路径。
  • A*算法使用场景比较广泛，可以直接运用至游戏世界中；而dj算法是相对抽象的图场景。
  • 还有一点这个图中体现的不明显。A*算法是启发式搜索，即尽可能朝着目标方向搜索；而dj算法在这种场景下则是一层层向外扩展。

从原理描述，我们可以提一个问题：怎么选择最好的状态？仅仅是离目标点最近吗？显然不行。对于最简单的无障碍物来说，影响不大。而对于有障碍物的情况，那么这种启发式会仅仅考虑到达目标的代价，而忽略了当前已花费的代价，于是尽管路径变得很长，它仍然继续走下去。

所以我们结合一下，共维护两种代价：一种是从开始状态到该状态的代价；另一种则是到达目标位置剩余距离的代价的一个启发式估价函数（例如离目标点最近）。而整个路径的估价值（前面两种代价相加）用以决定下一个要检查的状态即选择相邻状态中最好的那个。

实现

目前A*的思路就很明显了。具体实现思路：closed表初始为空，open表只有初始状态。每次迭代，将open表中最好的状态（即Totalcost最小）取出检查。如不是目标状态，则检查它的相邻状态（如果是新状态，添加必要信息如父状态，CostFromStart，CostToGoal；如已经在open表中且代价更低，则更新该位置的信息如update新的父状态，代价等；如已经在closed表中，忽略）。

伪代码形式如下：

AStarSearch(Location StartLoc, Location EndLoc)
{
    //初始化起点
    StartNode.Loc=StartLoc
    StartNode.CostFromStart=0
    StartNode.CostToGoal=PathCost(StartLoc, EndLoc)
    StartNode.TotalCost=CostFromStart+CostToGoal
    StartNode.parent=NULL
    push StartNode on Open

    while Open is not empty
    {
        //按totalcost排序，将最小代价节点取出
        pop Node from Open

        if (Node is Goal)
        {
            构造路径
            return success
        }
        else
        {
            for each NewNode of Node
            {
                NewCost = Node.GetCostFromStart() + GetCost(Node,NewNode)
                //已存在的就忽略
                if (NewNode is in Closed or (NewNode is in Open and NewNode.CostFromStart 小于等于 NewCost))
                {
                    continue;
                }
                else
                {
                    //在open表中则只更新数据
                    if (NewNode is in Open)
                    {
                        NewNode.Parent=Node
                        NewNode.CostFromStart=NewCost
                        NewNode.CostToGoal=PathCost(NewNode.Loc, EndLoc)
                        NewNode.TotalCost=NewNode.CostFromStart+NewNode.CostToGoal
                    }
                    else
                    {
                        NewNode.Parent=Node
                        NewNode.CostFromStart=NewCost
                        NewNode.CostToGoal=PathCost(NewNode.Loc, EndLoc)
                        NewNode.TotalCost=NewNode.CostFromStart+NewNode.CostToGoal
                        push New Node to Open
                    }                
                }
            }//相邻状态遍历完毕
        }
        push Node to Closed
    }
    return failure
}

我用c++实现了一个最简单的形式，地图为方形栅格，无障碍物，取与目标点的欧几里得距离为启发式估价函数。设相邻状态对角的cost为14，直线的cost为10。

运行结果展示：
我假设的起始点为(5,5).终点为(15,10)

这里的open表我采用的是list，其实有一种更好的方法就是采用优先级队列。这种方式实现起来会更简单，而且效率也会较高。

程序源代码: https://github.com/LZleejean/AStar

这里给大家推荐一个写的特别好的A*算法的文章。http://theory.stanford.edu/~amitp/GameProgramming/

后续将会讨论一些A*算法优化问题。

转载请注明出处

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

LZ