实时联网游戏后台服务技术选型和挑战（网络接入篇）

发表于 2018-04-23

概述：本文尝试从开发者角度梳理开发实时联网游戏后台服务过程中可能面临的挑战，并针对性地提供相应解决思路，期望帮助开发者依据自身游戏特点做出合理的技术选型。
维基百科关于网络游戏的定义：通过计算机网络，将专用服务器和用户的客户端设备(手机、PC、游戏主机等)相连，让多名玩家同时联机进行游戏的娱乐形式，由此可知网络游戏涉及三个角色：客户端、网络、服务器，从网络架构上来讲网络游戏可分为C/S 架构和P2P架构(特指客户端间直连通信)，在实际开发中还有一种C/S和P2P架构混合:C/M架构。

P2P架构不在本文讨论范围，C/M架构和C/S架构类似，和经典的LAMP网站架构类似一般C/S架构的游戏后台也可划分为如下三层：（1）网络接入层；（2）游戏逻辑层；（3）数据存储层。

网络接入、游戏逻辑、数据存储层各自所面临的问题域及对应技术栈都大为不同，做此划分不仅有助于模块解耦、技术分工、组件复用，也可方便服务的运维部署。本文也着重从这三个方面来阐述游戏服务器的开发。
1、网络接入层

网络接入层的主要任务是建立客户端和后台服务以及客户端之间的信道，接收来自客户端大量并发请求，考核该层的主要性能指标是：高吞吐、低延迟。因而网络接入层开发考验的是开发者高性能网络编程的功底，即解决C10K甚至C10M的能力。

1.1协议选择

根据OSI的七层网络参考模型，我们可将网游网络也做如下7层划分:

其中4层以下都由操作系统来负责，开发者无需为此操心，在实际的开发过程中开发者首要面临的问题便是传输层是采用TCP还是UDP，下表简要对比了两者的优劣。
综合两者优劣，简单来说除非对延迟有极致要求(例如FPS、MOBA类游戏)需采用UDP外，TCP可应对大部分游戏。在实际游戏开发中不管是采用TCP还是UDP方式，都很少直接通过 Socket编程方式来进行，一来因为开发工作量大，质量性能难以保证；二来平台兼容性不好(比如H5并没有提供socket编程能力)，而是基于更上层的通讯协议比如基于TCP的HTTP、Websocket协议，GRPC，以及基于UDP实现的QUIC，WebRTC协议等。

值得注意的是基于安全性考虑，浏览器标准未提供UDP收发能力，QUIC协议也只在chrome得到了支持，WebRTC也还不是浏览器事实标准且协议初始目的是用于实现点对点的音视频通信，协议内容过于庞杂不容易提炼应用于游戏开发中，因而现阶段H5游戏还只能采用HTTP或Websocket方式通讯。
通讯协议确定后，随后要考虑的便是游戏对象的序列化，序列化主要有基于文本、基于二进制两种，其优劣如下表所示。在开发过程中一般会先采用文本序列化方式，便于前后端开发联调，在游戏正式上线前切换至二进制序列化方式以减少传输流量、提升编解码效率。

至于数据安全性问题，为了保护敏感数据安全开发者可以选择安全的https或WSS通讯协议，而对于直接基于TCP协议通讯，可采用先用RSA协商加密秘钥，然后使用对称加密方式将数据加密后发送。
通过以上分析，对于游戏协议类型的选择我们给出有以下准则：

1、弱联网类游戏：诸如休闲、卡牌类游戏可直接HTTP协议，对安全性有要求的话就使用HTTPS；

2、实时性，交互性要求较高：这类游戏一般需要保持长连接，优先选择标准的ws协议（同时使用二进制序列化方式），如考虑安全性可使用wss协议。而对于提供socket接口的native平台也可使用TCP协议，同时对数据做对称加密增强安全性；

3、实时性要求极高：不仅需要和服务器保持长连接，且延迟和网络抖动都要求极高（如FPS，赛车类游戏），可使用基于UDP的实现流传输协议如QUIC，KCP等。

1.2并发模型

为了处理来自客户端的并发请求，服务端有4种常见的并发模型。

1.2.1进程

进程是最早采用的并发模型，进程作为操作资源分配、调度的单位，拥有独立的运行空间。进程并发模型中每个请求由独立的进程来处理，进程一次只能处理一个请求，该模型最大的优点就是简单。如果处理请求的进程由于系统调用而阻塞或进程的时间片用完，抢占式的进程调度器就会暂停旧进程执行，调度执行新的进程，这个过程涉及大开销的上下文切换，进程并发模型的缺点是比较低效。最典型的采用进程模型的服务有Apache。

1.2.2线程

线程并发模型是进程模型的改进，线程从属于进程，是系统更小粒度的执行调度单元。不同请求可由进程内多个并发执行的线程来处理，这些线程由操作系统内核自动调度。线程相对进程的主要优势在于，调度上下文切换开销更小，但由于多个线程共享地址空间，需要额外的线程间互斥、同步机制来保证程序性正确性。典型的采用线程模型的服务有Tomcat。

1.2.3 IO多路复用

利用操作系统提供的epoll等IO多路复用机制，能同时监控多个连接上读、写事件， IO多路复用也称事件驱动模型，网络程序执行逻辑可抽象为事件驱动的状态机。 IO多路复用避免了读写阻塞，减少了上下文切换，提升了CPU利用率和系统吞吐率。但IO多路复用它将原本“同步”、线性的处理逻辑变成事件驱动的状态机，处理逻辑分散于大量的事件回调函数。这种异步、非线性的模型，极大地增加了编程难度，如nodeJs的常见的回调地狱问题。典型的采用IO复用模型的服务有Nginx，netty。

1.2.4 协程

协程也称为轻量级线程，是一种协同的、非抢占式的多任务并发模型。协程运行在用户空间，当遇到阻塞或特定入口时，通过显式调用切换方法主动让出CPU，由任务调度器选取另一个协程执行。

协程切换只是简单地改变执行函数栈，不涉及内核态与用户态转化，也涉及上下文切换，开销远小于进程/线程切换。协程的概念虽早已提出，随着近些年年越来越多的语言（go、 Haskell）内置对协程支持才被开发者所熟知，协程极大的优化了开发者编程体验，在同步、顺序编程风格能快速实现程序逻辑，还拥有IO多路复用异步编程的性能。典型的采用协程模型的服务有openresty(Lua), gevent(Python), golang。

以上总结了目前4种常用的并发模型，它们在工作原理、运行效率、编程难度等方面有显著区别，各自有适用场景，在实际使用时应该根据需求仔细评估。在实际开发过程中如果没有可复用的现成网络组件或历史包袱我们建议使用协程并发模式开发网络接入层服务。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

SpringBoot+Docker+Git+Jenkins实

发表于 2018-04-23

努力了这么久，但凡有点儿天赋，也该有些成功的迹象了。

前言

本篇文章引导你使用Jenkins部署SpringBoot项目,同时使用Docker和Git实现简单的持续集成和持续部署。（项目地址：sso-merryyou）

流程图如下：

push代码到Github触发WebHook。（因网络原因，本篇使用gitee）
Jenkins从仓库拉去代码
mavem构建项目
代码静态分析
单元测试
build镜像
push镜像到镜像仓库（本篇使用的镜像仓库为网易镜像仓库）
更新服务

Jenkins安装

下载jenkins

从jenkins.io/download/下载对应的jenkins

初始化密码

访问本地：http://localhost:8080输入密码

选择插件

进入用户自定义插件界面，选择第二个（因为我们本次构建使用的为Pipelines）

勾选与Pipelines相关的插件

等待插件安装完成

配置用户名和密码

全局配置

系统管理-》全局工具配置配置Git,JDK和Maven

安全配置

系统管理-》全局安全配置

勾选Allow anonymous read access
取消防止跨站点请求伪造

新建任务

新建任务-》流水线

构建脚本

勾选触发远程构建 (WebHooks触发地址)，填写简单的Pipeline script

复制代码#!groovy
pipeline{
    agent any

    stages {

        stage('test'){
            steps {
                echo "hello world"

            }
        }            
    }
}

测试脚本

立即构建

控制台输出

gitee集成WebHooks

添加SSH公匙

配置WebHooks

使用natapp实现内网穿透

修改脚本

修改Pipeline script

复制代码#!groovy
pipeline{
    agent any
    //定义仓库地址
    environment {
        REPOSITORY="https://gitee.com/merryyou/sso-merryyou.git"
    }

    stages {

        stage('获取代码'){
            steps {
                echo "start fetch code from git:${REPOSITORY}"
                //清空当前目录
                deleteDir()
                //拉去代码    
                git "${REPOSITORY}"
            }
        }

        stage('代码静态检查'){
            steps {
                //伪代码检查
                echo "start code check"
            }
        }        

        stage('编译+单元测试'){
            steps {
                echo "start compile"
                //切换目录
                dir('sso-client1') {
                    //重新打包
                    bat 'mvn -Dmaven.test.skip=true -U clean install'
                }
            }
        }

        stage('构建镜像'){
            steps {
                echo "start build image"
                dir('sso-client1') {
                    //build镜像
                    bat 'docker build -t hub.c.163.com/longfeizheng/sso-client1:1.0 .'
                    //登录163云仓库
                    bat 'docker login -u longfei_zheng@163.com -p password hub.c.163.com'
                    //推送镜像到163仓库
                    bat 'docker push hub.c.163.com/longfeizheng/sso-client1:1.0'
                }
            }
        }

        stage('启动服务'){
            steps {
                echo "start sso-merryyou"
                //重启服务
                bat 'docker-compose up -d --build'
            }
        }                

    }
}

Pipeline的几个基本概念：

Stage: 阶段，一个Pipeline可以划分为若干个Stage，每个Stage代表一组操作。注意，Stage是一个逻辑分组的概念，可以跨多个Node。
Node: 节点，一个Node就是一个Jenkins节点，或者是Master，或者是Agent，是执行Step的具体运行期环境。
Step: 步骤，Step是最基本的操作单元，小到创建一个目录，大到构建一个Docker镜像，由各类Jenkins Plugin提供。

更多Pipeline语法参考：pipeline 语法详解

测试

docker-compose up -d 启动服务

访问http://sso-taobao:8083/client1登录

修改内容效果如下：

更多效果图

代码下载

github:github.com/longfeizhen…
gitee:gitee.com/merryyou/ss…

Android SharedPreferences的理解与使

发表于 2018-04-22

Android 五种数据存储的方式分别为：

SharedPreferences：以Map形式存放简单的配置参数；
ContentProvider：将应用的私有数据提供给其他应用使用；
文件存储：以IO流形式存放，可分为手机内部和手机外部（sd卡等）存储，可存放较大数据；
SQLite：轻量级、跨平台数据库，将所有数据都是存放在手机上的单一文件内，占用内存小；
网络存储：数据存储在服务器上，通过连接网络获取数据；

Sharedpreferences是Android平台上一个轻量级的存储类，用来保存应用程序的各种配置信息，其本质是一个以“键-值”对的方式保存数据的xml文件，其文件保存在/data/data//shared_prefs目录下。在全局变量上看，其优点是不会产生Application 、静态变量的OOM（out of memory）和空指针问题，其缺点是效率没有上面的两种方法高。

获取SharedPreferences

要想使用 SharedPreferences 来存储数据，首先需要获取到 SharedPreferences 对象。Android中主要提供了三种方法用于得到 SharedPreferences 对象。

1.1 Context 类中的 getSharedPreferences()方法：

此方法接收两个参数，第一个参数用于指定 SharedPreferences 文件的名称，如果指定的文件不存在则会创建一个，第二个参数用于指定操作模式，主要有以下几种模式可以选择。MODE_PRIVATE 是默认的操作模式，和直接传入 0 效果是相同的。

MODE_WORLD_READABLE 和 MODE_WORLD_WRITEABLE 这两种模式已在 Android 4.2 版本中被废弃。

复制代码Context.MODE_PRIVATE: 指定该SharedPreferences数据只能被本应用程序读、写；
Context.MODE_WORLD_READABLE:  指定该SharedPreferences数据能被其他应用程序读，但不能写；
Context.MODE_WORLD_WRITEABLE:  指定该SharedPreferences数据能被其他应用程序读；
Context.MODE_APPEND：该模式会检查文件是否存在，存在就往文件追加内容，否则就创建新文件；

1.2 Activity 类中的 getPreferences()方法：

这个方法和 Context 中的 getSharedPreferences()方法很相似，不过它只接收一个操作模式参数，因为使用这个方法时会自动将当前活动的类名作为 SharedPreferences 的文件名。

1.3 PreferenceManager 类中的 getDefaultSharedPreferences()方法：

这是一个静态方法，它接收一个 Context 参数，并自动使用当前应用程序的包名作为前缀来命名 SharedPreferences 文件。

SharedPreferences的使用

SharedPreferences对象本身只能获取数据而不支持存储和修改,存储修改是通过SharedPreferences.edit()获取的内部接口Editor对象实现。使用Preference来存取数据，用到了SharedPreferences接口和SharedPreferences的一个内部接口SharedPreferences.Editor，这两个接口在android.content包中；

复制代码 1）写入数据：
     //步骤1：创建一个SharedPreferences对象
     SharedPreferences sharedPreferences= getSharedPreferences("data",Context.MODE_PRIVATE);
     //步骤2： 实例化SharedPreferences.Editor对象
     SharedPreferences.Editor editor = sharedPreferences.edit();
     //步骤3：将获取过来的值放入文件
     editor.putString("name", “Tom”);
     editor.putInt("age", 28);
     editor.putBoolean("marrid",false);
     //步骤4：提交               
     editor.commit();


 2）读取数据：
     SharedPreferences sharedPreferences= getSharedPreferences("data", Context .MODE_PRIVATE);
     String userId=sharedPreferences.getString("name","");
  
3）删除指定数据
     editor.remove("name");
     editor.commit();


4）清空数据
     editor.clear();
     editor.commit();

注意：如果在 Fragment 中使用SharedPreferences 时，需要放在onAttach(Activity activity)里面进行SharedPreferences的初始化，否则会报空指针即 getActivity()会可能返回null ！

读写其他应用的SharedPreferences 步骤如下:

1. 在创建SharedPreferences时，指定MODE_WORLD_READABLE模式，表明该SharedPreferences数据可以被其他程序读取；

2. 创建其他应用程序对应的Context；

3. 使用其他程序的Context获取对应的SharedPreferences；

4. 如果是写入数据，使用Editor接口即可，所有其他操作均和前面一致；

复制代码try {
//这里的com.example.mpreferences 就是应用的包名
 Context mcontext = createPackageContext("com.example.mpreferences", CONTEXT_IGNORE_SECURITY);


 SharedPreferences msharedpreferences = mcontext.getSharedPreferences("name_preference", MODE_PRIVATE);
 int count = msharedpreferences.getInt("count", 0);


 } catch (PackageManager.NameNotFoundException e) {
       e.printStackTrace();
 }

SharedPreferences 的源码分析（API 25）

Context的getSharedPreferences：

1	复制代码 public abstract SharedPreferences getSharedPreferences(String name, int mode);

我们知道Android中的Context类其实是使用了装饰者模式，而被装饰对象其实就是一个ContextImpl对象，ContextImpl的getSharedPreferences方法：

复制代码    /**
     * Map from preference name to generated path.
     * 从preference名称到生成路径的映射；
     */
    @GuardedBy("ContextImpl.class")
    private ArrayMap<String, File> mSharedPrefsPaths;


    /**
     * Map from package name, to preference name, to cached preferences.
     * 从包名映射到preferences，以缓存preferences，这是个静态变量；
     */
    @GuardedBy("ContextImpl.class")
    private static ArrayMap<String, ArrayMap<File, SharedPreferencesImpl>> sSharedPrefsCache;


    @Override
    public SharedPreferences getSharedPreferences(String name, int mode) {
        // At least one application in the world actually passes in a null
        // name.  This happened to work because when we generated the file name
        // we would stringify it to "null.xml".  Nice.
        if (mPackageInfo.getApplicationInfo().targetSdkVersion <
                Build.VERSION_CODES.KITKAT) {
            if (name == null) {
                name = "null";
            }
        }


        File file;
        synchronized (ContextImpl.class) {
            if (mSharedPrefsPaths == null) {
                mSharedPrefsPaths = new ArrayMap<>();
            }
            file = mSharedPrefsPaths.get(name);
            if (file == null) {
                file = getSharedPreferencesPath(name);
                mSharedPrefsPaths.put(name, file);
            }
        }
        return getSharedPreferences(file, mode);
    }




    @Override
    public SharedPreferences getSharedPreferences(File file, int mode) {
        checkMode(mode);
        SharedPreferencesImpl sp;
        synchronized (ContextImpl.class) {
            final ArrayMap<File, SharedPreferencesImpl> cache = getSharedPreferencesCacheLocked();
            sp = cache.get(file);
            if (sp == null) {
                sp = new SharedPreferencesImpl(file, mode);
                cache.put(file, sp);
                return sp;
            }
        }
        if ((mode & Context.MODE_MULTI_PROCESS) != 0 ||
            getApplicationInfo().targetSdkVersion < android.os.Build.VERSION_CODES.HONEYCOMB) {
            // If somebody else (some other process) changed the prefs
            // file behind our back, we reload it.  This has been the
            // historical (if undocumented) behavior.
            sp.startReloadIfChangedUnexpectedly();
        }
        return sp;
    }


    private ArrayMap<File, SharedPreferencesImpl> getSharedPreferencesCacheLocked() {
        if (sSharedPrefsCache == null) {
            sSharedPrefsCache = new ArrayMap<>();
        }


        final String packageName = getPackageName();
        ArrayMap<File, SharedPreferencesImpl> packagePrefs = sSharedPrefsCache.get(packageName);
        if (packagePrefs == null) {
            packagePrefs = new ArrayMap<>();
            sSharedPrefsCache.put(packageName, packagePrefs);
        }


        return packagePrefs;
    }

从上面我们可以看出他们之间的关系：

（ArrayMap<String, File>）

mSharedPrefsPaths存放的是名称与文件夹的映射，这里的名称就是我们使用getSharedPreferences时传入的name，如果mSharedPrefsPaths为null则初始化，如果file为null则新建一个File并将其加入mSharedPrefsPaths中；

（ ArrayMap<String, ArrayMap<File, SharedPreferencesImpl>> ）

sSharedPrefsCache 存放包名与ArrayMap键值对
初始化时会默认以包名作为键值对中的Key，注意这是个static变量；

（ArrayMap<File, SharedPreferencesImpl>）

sSharedPrefs packagePrefs存放文件name与SharedPreferencesImpl键值对

注意：

对于一个相同的SharedPreferences name，获取到的都是同一个SharedPreferences对象，它其实是SharedPreferencesImpl对象。
sSharedPrefs在程序中是静态的，如果退出了程序但Context没有被清掉，那么下次进入程序仍然可能取到本应被删除掉的值。而换了另一种清除SharedPreferences的方式：使用SharedPreferences.Editor的commit方法能够起作用，调用后不退出程序都马上生效。

SharedPreferencesImpl对象

复制代码  SharedPreferencesImpl(File file, int mode) {
        mFile = file;
        //  备份的File
        mBackupFile = makeBackupFile(file);
        mMode = mode;
        mLoaded = false;
        mMap = null;
        startLoadFromDisk();
    }


   private void startLoadFromDisk() {
        synchronized (this) {
            mLoaded = false;
        }
        new Thread("SharedPreferencesImpl-load") {
            public void run() {
                loadFromDisk();
            }
        }.start();
    }


    private void loadFromDisk() {
        synchronized (SharedPreferencesImpl.this) {
            if (mLoaded) {
                return;
            }
            if (mBackupFile.exists()) {
                mFile.delete();
                mBackupFile.renameTo(mFile);
            }
        }


        // Debugging
        if (mFile.exists() && !mFile.canRead()) {
            Log.w(TAG, "Attempt to read preferences file " + mFile + " without permission");
        }


        Map map = null;
        StructStat stat = null;
        try {
            stat = Os.stat(mFile.getPath());
            if (mFile.canRead()) {
                BufferedInputStream str = null;
                try {
                    str = new BufferedInputStream(
                            new FileInputStream(mFile), 16*1024);
                    map = XmlUtils.readMapXml(str);
                } catch (XmlPullParserException | IOException e) {
                    Log.w(TAG, "getSharedPreferences", e);
                } finally {
                    IoUtils.closeQuietly(str);
                }
            }
        } catch (ErrnoException e) {
            /* ignore */
        }


        synchronized (SharedPreferencesImpl.this) {
            mLoaded = true;
            if (map != null) {
                mMap = map;
                mStatTimestamp = stat.st_mtime;
                mStatSize = stat.st_size;
            } else {
                mMap = new HashMap<>();
            }
            notifyAll();
        }
    }

可以看到对于一个SharedPreferences文件name，第一次调用getSharedPreferences时会去创建一个SharedPreferencesImpl对象，它会开启一个子线程，然后去把指定的SharedPreferences文件中的键值对全部读取出来，存放在一个Map中。

调用getString时那个SharedPreferencesImpl构造方法开启的子线程可能还没执行完（比如文件比较大时全部读取会比较久），这时getString当然还不能获取到相应的值，必须阻塞到那个子线程读取完为止，如getString方法：

复制代码    @Nullable
    public String getString(String key, @Nullable String defValue) {
        synchronized (this) {
            awaitLoadedLocked();
            String v = (String)mMap.get(key);
            return v != null ? v : defValue;
        }
    }


   private void awaitLoadedLocked() {
        if (!mLoaded) {
            // Raise an explicit StrictMode onReadFromDisk for this
            // thread, since the real read will be in a different
            // thread and otherwise ignored by StrictMode.
            BlockGuard.getThreadPolicy().onReadFromDisk();
        }
        while (!mLoaded) {
            try {
                wait();
            } catch (InterruptedException unused) {
            }
        }
    }

显然这个awaitLoadedLocked方法就是用来等this这个锁的，在loadFromDiskLocked方法的最后我们也可以看到它调用了notifyAll方法，这时如果getString之前阻塞了就会被唤醒。那么这里会存在一个问题，我们的getString是写在UI线程中，如果那个getString被阻塞太久了，比如60s，这时就会出现ANR，所以要根据具体情况考虑是否需要把SharedPreferences的读写放在子线程中。

关于mBackupFile，SharedPreferences在写入时会先把之前的xml文件改成名成一个备份文件，然后再将要写入的数据写到一个新的文件中，如果这个过程执行成功的话，就会把备份文件删除。由此可见每次即使只是添加一个键值对，也会重新写入整个文件的数据，这也说明SharedPreferences只适合保存少量数据，文件太大会有性能问题。

注意：

在UI线程中调用getXXX可能会导致ANR。
我们在初始化SharedPreferencesImpl对象时会加SharedPreferencesImpl对应的xml文件中的所有数据都加载到内存中，如果xml文件很大，将会占用大量的内存，我们只想读取xml文件中某个key的值，但我们获取它的时候是会加载整个文件。
每添加一个键值对，都会重新写入整个文件的数据，不是增量写入；
综上原因能说明Sharedpreferences只适合做轻量级的存储。

SharedPreferences的内部类Editor

复制代码   SharedPreferences sharedPreferences= getSharedPreferences("data",Context.MODE_PRIVATE);
   SharedPreferences.Editor editor = sharedPreferences.edit();
   editor.putString("name", “Tom”);


   public Editor edit() {
        // TODO: remove the need to call awaitLoadedLocked() when
        // requesting an editor.  will require some work on the
        // Editor, but then we should be able to do:
        //
        //      context.getSharedPreferences(..).edit().putString(..).apply()
        //
        // ... all without blocking.
        synchronized (this) {
            awaitLoadedLocked();
        }


        return new EditorImpl();
    }

其实拿到的是一个EditorImpl对象，它是SharedPreferencesImpl的内部类：

复制代码  public final class EditorImpl implements Editor {
        private final Map<String, Object> mModified = Maps.newHashMap();
        private boolean mClear = false;


        public Editor putString(String key, @Nullable String value) {
            synchronized (this) {
                mModified.put(key, value);
                return this;
            }
        }
          .....
}

可以看到它有一个Map对象mModified，用来保存“修改的数据”，也就是你每次put的时候其实只是把那个键值对放到这个mModified 中，最后调用apply或者commit才会真正把数据写入文件中，如上面的putString方法，其它putXXX代码基本也是一样的。

commit方法和apply方法的不同

复制代码    public void apply() {
            final MemoryCommitResult mcr = commitToMemory();
            final Runnable awaitCommit = new Runnable() {
                    public void run() {
                        try {
                            mcr.writtenToDiskLatch.await();
                        } catch (InterruptedException ignored) {
                        }
                    }
                };


            QueuedWork.add(awaitCommit);


            Runnable postWriteRunnable = new Runnable() {
                    public void run() {
                        awaitCommit.run();
                        QueuedWork.remove(awaitCommit);
                    }
                };


            SharedPreferencesImpl.this.enqueueDiskWrite(mcr, postWriteRunnable);


            // Okay to notify the listeners before it's hit disk
            // because the listeners should always get the same
            // SharedPreferences instance back, which has the
            // changes reflected in memory.
            notifyListeners(mcr);
        }


    public boolean commit() {
            MemoryCommitResult mcr = commitToMemory();
            SharedPreferencesImpl.this.enqueueDiskWrite(
                mcr, null /* sync write on this thread okay */);
            try {
                mcr.writtenToDiskLatch.await();
            } catch (InterruptedException e) {
                return false;
            }
            notifyListeners(mcr);
            return mcr.writeToDiskResult;
        }


    // Return value from EditorImpl#commitToMemory()
    private static class MemoryCommitResult {
        public boolean changesMade;  // any keys different?
        public List<String> keysModified;  // may be null
        public Set<OnSharedPreferenceChangeListener> listeners;  // may be null
        public Map<?, ?> mapToWriteToDisk;
        public final CountDownLatch writtenToDiskLatch = new CountDownLatch(1);
        public volatile boolean writeToDiskResult = false;


        public void setDiskWriteResult(boolean result) {
            writeToDiskResult = result;
            writtenToDiskLatch.countDown();
        }
    }

两种方式首先都会先使用commitTomemory函数将修改的内容写入到SharedPreferencesImpl当中，再调用enqueueDiskWrite写磁盘操作，commitToMemory就是产生一个“合适”的MemoryCommitResult对象mcr，然后调用enqueueDiskWrite时需要把这个对象传进去，commitToMemory方法：

复制代码        // Returns true if any changes were made
        private MemoryCommitResult commitToMemory() {
            MemoryCommitResult mcr = new MemoryCommitResult();
            synchronized (SharedPreferencesImpl.this) {
                // We optimistically don't make a deep copy until
                // a memory commit comes in when we're already
                // writing to disk.
                if (mDiskWritesInFlight > 0) {
                    // We can't modify our mMap as a currently
                    // in-flight write owns it.  Clone it before
                    // modifying it.
                    // noinspection unchecked
                    mMap = new HashMap<String, Object>(mMap);
                }
                mcr.mapToWriteToDisk = mMap;
                mDiskWritesInFlight++;


                boolean hasListeners = mListeners.size() > 0;
                if (hasListeners) {
                    mcr.keysModified = new ArrayList<String>();
                    mcr.listeners =
                            new HashSet<OnSharedPreferenceChangeListener>(mListeners.keySet());
                }


                synchronized (this) {
                    if (mClear) {
                        if (!mMap.isEmpty()) {
                            mcr.changesMade = true;
                            mMap.clear();
                        }
                        mClear = false;
                    }


                    for (Map.Entry<String, Object> e : mModified.entrySet()) {
                        String k = e.getKey();
                        Object v = e.getValue();
                        // "this" is the magic value for a removal mutation. In addition,
                        // setting a value to "null" for a given key is specified to be
                        // equivalent to calling remove on that key.
                        if (v == this || v == null) {
                            if (!mMap.containsKey(k)) {
                                continue;
                            }
                            mMap.remove(k);
                        } else {
                            if (mMap.containsKey(k)) {
                                Object existingValue = mMap.get(k);
                                if (existingValue != null && existingValue.equals(v)) {
                                    continue;
                                }
                            }
                            mMap.put(k, v);
                        }


                        mcr.changesMade = true;
                        if (hasListeners) {
                            mcr.keysModified.add(k);
                        }
                    }


                    mModified.clear();
                }
            }
            return mcr;
        }

这里需要弄清楚两个对象mMap和mModified，mMap是存放当前SharedPreferences文件中的键值对，而mModified是存放此时edit时put进去的键值对。mDiskWritesInFlight表示正在等待写的操作数量。

可以看到这个方法中首先处理了clear标志，它调用的是mMap.clear()，然后再遍历mModified将新的键值对put进mMap，也就是说在一次commit事务中，如果同时put一些键值对和调用clear后再commit，那么clear掉的只是之前的键值对，这次put进去的键值对还是会被写入的。

遍历mModified时，需要处理一个特殊情况，就是如果一个键值对的value是this（SharedPreferencesImpl）或者是null那么表示将此键值对删除，这个在remove方法中可以看到，如果之前有同样的key且value不同则用新的valu覆盖旧的value，如果没有存在同样的key则完整写入。需要注意的是这里使用了同步锁住edtor对象，保证了当前数据正确存入。

复制代码 public Editor remove(String key) {
            synchronized (this) {
                mModified.put(key, this);
                return this;
            }
        }


        public Editor clear() {
            synchronized (this) {
                mClear = true;
                return this;
            }
        }

接下来就是调用enqueueDiskWrite方法：

复制代码private void enqueueDiskWrite(final MemoryCommitResult mcr,
                                  final Runnable postWriteRunnable) {
        final Runnable writeToDiskRunnable = new Runnable() {
                public void run() {
                    synchronized (mWritingToDiskLock) {
                        writeToFile(mcr);
                    }
                    synchronized (SharedPreferencesImpl.this) {
                        mDiskWritesInFlight--;
                    }
                    if (postWriteRunnable != null) {
                        postWriteRunnable.run();
                    }
                }
            };


        final boolean isFromSyncCommit = (postWriteRunnable == null);


        // Typical #commit() path with fewer allocations, doing a write on
        // the current thread.
        if (isFromSyncCommit) {
            boolean wasEmpty = false;
            synchronized (SharedPreferencesImpl.this) {
                wasEmpty = mDiskWritesInFlight == 1;
            }
            if (wasEmpty) {
                writeToDiskRunnable.run();
                return;
            }
        }


        QueuedWork.singleThreadExecutor().execute(writeToDiskRunnable);
    }

定义一个Runnable任务，在Runnable中先调用writeToFile进行写操作，写操作需要先获得mWritingToDiskLock，也就是写锁。然后执行mDiskWritesInFlight–，表示正在等待写的操作减少1。

判断postWriteRunnable是否为null，调用commit时它为null，而调用apply时它不为null。isFromSyncCommit为true，而且有1个写操作需要执行，那么就调用writeToDiskRunnable.run()，注意这个调用是在当前线程中进行的。如果不是commit，那就是apply，这时调用QueuedWork.singleThreadExecutor().execute(writeToDiskRunnable)，这个QueuedWork类其实很简单，里面有一个SingleThreadExecutor，用于异步执行这个writeToDiskRunnable，commit的写操作是在调用线程中执行的，而apply内部是用一个单线程的线程池实现的，因此写操作是在子线程中执行的。

commit和apply的总结：

apply没有返回值而commit返回boolean表明修改是否提交成功；
commit是把内容同步提交到硬盘的，而apply先立即把修改提交到内存，然后开启一个异步的线程提交到硬盘，并且如果提交失败，你不会收到任何通知。
所有commit提交是同步过程，效率会比apply异步提交的速度慢，在不关心提交结果是否成功的情况下，优先考虑apply方法。
apply是使用异步线程写入磁盘，commit是同步写入磁盘。所以我们在主线程使用的commit的时候，需要考虑是否会出现ANR问题。（不适合大量数据存储）

查看Sharedpreferencesd 保存数据的xml文件

要想查看data文件首先要获取手机root权限，成功root后，修改data权限即可查看data里面的数据库。由于在xml文件内可以很清楚的查看到各个键-值”对数据，所以用Sharedpreferencesd保存比较重要的数据的时候最好先加密再保存。成功查看如下图所示：

data权限修改办法：

复制代码1. 打开cmd；
2. 输入’adb shell’；
3. 输入su，回车 ；
4. 输入chmod 777 /data/data/<package name>/shared_prefs 回车
该步骤设置data文件夹权限为777（drwxrwxrwx,也即administrators、power users和users组都有对该文件夹的读、写、运行权限） ;

当你在Linux下用命令ll 或者ls -la的时候会看到类似drwxr-xr-x这样标识，具体代表什么意思呢?
这段标识总长度为10位（10个‘-’），第一位表示文件类型，如该文件是文件(用-表示），如该文件是文件夹(用d表示),如该文件是连接文件(用l表示），后面9个按照三个一组分，第一组：用户权限，第二组：组权限，第三组：其他权限。每一组是三位，分别是读 r ,写 w,执行 x，这些权限都可以用数字来表示：r 4, w 2 , x 1。如果没有其中的某个权限则用‘-’表示。例如：
1. -rwxrwx—，第一位‘-’代表的是文件，第二位到第四位rwx代表此文件的拥有者有读、写、执行的权限，同组用户也有读、写、及执行权限，其他用户组没任何权限。用数字来表示的话则是770.

2. drwx——，第一位‘d’代表的是文件夹，第二位到第四位rwx代表此文件夹的拥有者有读、写、执行的权限，第五位到第七位代表的是拥有者同组用户的权限，同组用户没有任何权限，第八位到第十位代表的是其他用户的权限，其他用户也没有任何权限。用数字来表示的话则是700.

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

Java 中的时间日期 API

发表于 2018-04-21

自从 14 年发布 Java 8 以后，我们古老 java.util.Date 终于不再是我们 Java 里操作日期时间的唯一的选择。

其实 Java 里的日期时间的相关 API 一直为世猿诟病，不仅在于它设计分上工不明确，往往一个类既能处理日期又能处理时间，很混乱，还在于某些年月日期的数值映射存储反人类，例如：0 对应月份一月，11 对应月份十二月，118 对应年份 2018（1900 + 118）等。

往往我们得到某个年月值还需要再做相应的运算才能得到准确的年月日信息，直到我们的 Java 8 ，借鉴了第三方开源库 Joda-Time 的优秀设计，重新设计了一个日期时间 API，相比之前，可以说好用百倍，相关 API 接口全部位于包 java.time 下。

古老的日期时间接口

表示时刻信息的 Date

世界上所有的计算机内部存储时间都使用一个 long 类型的整数，而这个整数的值就是相对于英国格林尼治标准时间（1970年1月1日0时0分0秒）的毫秒数。例如：

复制代码public static void main(String[] args){
    //January 1, 1970 00:00:00 GMT.
    Date date = new Date(1000);
    System.out.println(date);
}

输出结果：

1 2	复制代码//1970-1-1 8:00:01 Thu Jan 01 08:00:01 CST 1970

很多人可能会疑惑，1000 表示的是距离标准时间往后 1 秒，那为什么时间却多走了八个小时？

这和「时区」有关系，如果你位于英国的格林尼治区，那么结果会如预想一样，但是我们位于中国东八区，时间要早八个小时，所以不同时区基于的基础值不同。

Date 这个类以前真的扮演过很多角色，从它的源码就可以看出来，有可以操作时刻的方法，有可以操作年月日的方法，甚至它还能管时区。可以说，日期时间的相关操作有它一个人就足够了。

但这个世界就是这样，你管的东西多了，自然就不能面面俱到，Date 中很多方法的设计并不是很合理，之前我们也说了，甚至有点反人类。所以，现在的 Date 类中接近百分之八十的方法都已废弃，被标记为 @Deprecated。

sun 公司给 Date 的目前定位是，唯一表示一个时刻，所以它的内部应该围绕着那个整型的毫秒，而不再着重于各种年历时区等信息。

Date 允许通过以下两种构造器实例化一个对象：

复制代码private transient long fastTime;

public Date() {
    this(System.currentTimeMillis());
}

public Date(long date) {
    fastTime = date;
}

这里的 fastTime 属性存储的就是时刻所对应的毫秒数，两个构造器还是很简单，如果调用的是无参构造器，那么虚拟机将以系统当前的时刻值对 fastTime 进行赋值。

还有几个为数不多没有被废弃的方法：

public long getTime() ：返回内部存储的毫秒数
public void setTime(long time)：重新设置内存的毫秒数
public boolean before(Date when)：比较给定的时刻是否早于当前 Date 实例
public boolean after(Date when)：比较给定的时刻是否晚于当前 Date 实例

还有两个方法是 jdk1.8 以后新增的，用于向 Java 8 新增接口的转换，待会介绍。

描述年历的 Calendar

Calendar 用于表示年月日等日期信息，它是一个抽象类，所以一般通过以下四种工厂方法获取它的实例对象。

复制代码public static Calendar getInstance()

public static Calendar getInstance(TimeZone zone)

public static Calendar getInstance(Locale aLocale)

public static Calendar getInstance(TimeZone zone,Locale aLocale)

其实内部最终会调用同一个内部方法：

1	复制代码private static Calendar createCalendar(TimeZone zone,Locale aLocale)

该方法需要两个参数，一个是时区，一个是国家和语言，也就是说，构建一个 Calendar 实例最少需要提供这两个参数信息，否则将会使用系统默认的时区或语言信息。

因为不同的时区与国家语言对于时刻和年月日信息的输出是不同的，所以这也是为什么一个 Calendar 实例必须传入时区和国家信息的一个原因。看个例子：

复制代码public static void main(String[] args){


    Calendar calendar = Calendar.getInstance();
    System.out.println(calendar.getTime());

    Calendar calendar1 = Calendar.getInstance
            (TimeZone.getTimeZone("GMT"), Locale.ENGLISH);
    System.out.println( calendar1.get(Calendar.YEAR) + ":" +
                        calendar1.get(Calendar.HOUR) + ":" +
                        calendar1.get(Calendar.MINUTE));
    }

输出结果：

1 2	复制代码Sat Apr 21 10:32:20 CST 2018 2018:2:32

可以看到，第一个输出为我们系统默认时区与国家的当前时间，而第二个 Calendar 实例我们指定了它位于格林尼治时区（0 时区），结果也显而易见了，相差了八个小时，那是因为我们位于东八区，时间早于 0 时区八个小时。

可能有人会疑惑了，为什么第二个 Calendar 实例的输出要如此复杂的拼接，而不像第一个 Calendar 实例那样直接调用 getTime 方法简洁呢？

这涉及到 Calendar 的内部实现，我们一起看看：

复制代码protected long          time;

public final Date getTime() {
    return new Date(getTimeInMillis());
}

和 Date 一样，Calendar 的内部也维护着一个时刻信息，而 getTime 方法实际上是根据这个时刻构建了一个 Date 对象并返回的。

而一般我们构建 Calendar 实例的时候都不会传入一个时刻信息，所以这个 time 的值在实例初始化的时候，程序会根据系统默认的时区和当前时间计算得到一个毫秒数并赋值给 time。

所以，所有未手动修改 time 属性值的 Calendar 实例的内部，time 的值都是当时系统默认时区的时刻数值。也就是说，getTime 的输出结果是不会理会当前实例所对应的时区信息的，这也是我觉得 Calendar 设计的一个缺陷所在，因为这样会导致两个不同时区 Calendar 实例的 getTime 输出值只取决于实例初始化时系统的运行时刻。

Calendar 中也定义了很多静态常量和一些属性数组：

复制代码public final static int ERA = 0;

public final static int YEAR = 1;

public final static int MONTH = 2;

public final static int WEEK_OF_YEAR = 3;

public final static int WEEK_OF_MONTH = 4;

public final static int DATE = 5;
....

复制代码protected int           fields[];

protected boolean       isSet[];
...

有关日期的所有相关信息都存储在属性数组中，而这些静态常量的值往往表示的就是一个索引值，通过 get 方法，我们传入一个属性索引，返回得到该属性的值。例如：

1 2	复制代码Calendar myCalendar = Calendar.getInstance(); int year = myCalendar.get(Calendar.YEAR);

这里的 get 方法实际上就是直接取的 fields[1] 作为返回值，而 fields 属性数组在 Calendar 实例初始化的时候就已经由系统根据时区和语言计算并赋值了，注意，这里会根据你指定的时区进行计算，它不像 time 始终是依照的系统默认时区。

个人觉得 Calendar 的设计有优雅的地方，也有不合理的地方，毕竟是个「古董」了，终将被替代。

DateFormat 格式化转换

从我们之前的一个例子中可以看到，Calendar 想要输出一个预期格式的日期信息是很麻烦的，需要自己手动拼接。而我们的 DateFormat 就是用来处理格式化字符串和日期时间之间的转换操作的。

DateFormat 和 Calendar 一样，也是一个抽象类，我们需要通过工厂方式产生其实例对象，主要有以下几种工厂方法：

复制代码//只处理时间的转换
public final static DateFormat getTimeInstance()

//只处理日期的转换
public final static DateFormat getDateInstance()

//既可以处理时间，也可以处理日期
public final static DateFormat getDateTimeInstance()

当然，它们各自都有各自的重载方法，具体的我们待会儿看。

DateFormat 有两类方法，format 和 parse。

1
2
3

复制代码public final String format(Date date)

public Date parse(String source)

format 方法用于将一个日期对象格式化为字符串，parse 方法用于将一个格式化的字符串装换为一个日期对象。例如：

复制代码public static void main(String[] args){
    Calendar calendar = Calendar.getInstance();
    DateFormat dateFormat = DateFormat.getDateTimeInstance();
    System.out.println(dateFormat.format(calendar.getTime()));
}

输出结果：

1	复制代码2018-4-21 16:58:09

显然，使用工厂构造的 DateFormat 实例并不能够自定义输出格式化内容，即输出的字符串格式是固定的，不能满足某些情况下的特殊需求。一般我们会直接使用它的一个实现类，SimpleDateFormat。

SimpleDateFormat 允许在构造实例的时候传入一个 pattern 参数，自定义日期字符的输出格式。例如：

复制代码public static void main(String[] args){    
    DateFormat dateFormat = new SimpleDateFormat("yyyy年MM月dd日");
    System.out.println(dateFormat.format(new Date()));
}

输出结果：

1	复制代码2018年04月21日

其中，

yyyy：年份用四位进行输出
MM：月份用两位进行输出
dd：两位表示日信息
HH：两位来表示小时数
mm：两位表示分钟数
ss：两位来表示秒数
E：表示周几，如果 Locale 在中国则会输出星期x，如果在美国或英国则会输出英文的星期
a：表示上午或下午

当然，对于字符串转日期也是很方便的，允许自定义模式，但必须遵守自己制定的模式，否则程序将无法成功解析。例如：

复制代码public static void main(String[] args){
    String str = "2018年4月21日 17点17分 星期六";
    DateFormat sDateFormat = new SimpleDateFormat("yyyy年M月dd日 HH点mm分 E");
    sDateFormat.parse(str);
    System.out.println(sDateFormat.getCalendar().getTime());
}

输出结果：

1	复制代码Sat Apr 21 17:17:00 CST 2018

显然，程序是正确的解析的我们的字符串并转换为 Calendar 对象存储在 DateFormat 内部的。

总的来说，Date、Calendar 和 DateFormat 已经能够处理一般的时间日期问题了，但是不可避免的是，它们依然很繁琐，不好用。

限于篇幅，我们下篇将对比 Java 8 的新式日期时间 API，你会发现它更加优雅的设计和简单的操作性。

文章中的所有代码、图片、文件都云存储在我的 GitHub 上：

(https://github.com/SingleYam/overview\_java)

欢迎关注微信公众号：扑在代码上的高尔基，所有文章都将同步在公众号上。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

Linux进程间通信-eventfd

发表于 2018-04-17

eventfd是linux 2.6.22后系统提供的一个轻量级的进程间通信的系统调用，eventfd通过一个进程间共享的64位计数器完成进程间通信，这个计数器由在linux内核空间维护，用户可以通过调用write方法向内核空间写入一个64位的值，也可以调用read方法读取这个值。

创建方法

1 2	复制代码#include <sys/eventfd.h> int eventfd(unsigned int initval, int flags);

创建的时候可以传入一个计数器的初始值initval。
第二个参数flags在linux 2.6.26之前的版本是没有使用的，必须初始化为0，在2.6.27之后的版本flag才被使用。

EFD_CLOEXEC(2.6.27～):

A copy of the file descriptor created by eventfd() is inherited by the child produced by fork(2). The duplicate file descriptor is associated with the same eventfd object. File descriptors created by eventfd() are preserved across execve(2), unless the close-on-exec flag has been set.

eventfd()会返回一个文件描述符，如果该进程被fork的时候，这个文件描述符也会复制过去，这时候就会有多个的文件描述符指向同一个eventfd对象，如果设置了EFD_CLOEXEC标志，在子进程执行exec的时候，会清除掉父进程的文件描述符

EFD_NONBLOCK(2.6.27～): 就如它字面上的意思，如果没有设置了这个标志位，那read操作将会阻塞直到计数器中有值。如果没有设置这个标志位，计数器没有值的时候也会立即返回-1；

EFD_SEMAPHORE(2.6.30～): 这个标志位会影响read操作，具体可以看read方法中的解释

提供的方法

read: 读取计数器中的值

如果计数器中的值大于0
- 设置了EFD_SEMAPHORE标志位，则返回1，且计数器中的值也减去1。
- 没有设置EFD_SEMAPHORE标志位，则返回计数器中的值，且计数器置0。
如果计数器中的值为0
- 设置了EFD_NONBLOCK标志位就直接返回-1。
- 没有设置EFD_NONBLOCK标志位就会一直阻塞直到计数器中的值大于0。

write: 向计数器中写入值

如果写入值的和小于0xFFFFFFFFFFFFFFFE，则写入成功
如果写入值的和大于0xFFFFFFFFFFFFFFFE
- 设置了EFD_NONBLOCK标志位就直接返回-1。
- 如果没有设置EFD_NONBLOCK标志位，则会一直阻塞知道read操作执行

close: 关闭文件描述符

一个小Demo

复制代码#include <sys/eventfd.h>
#include <unistd.h>
#include <iostream>

int main() {
    int efd = eventfd(0, EFD_NONBLOCK | EFD_CLOEXEC);
    eventfd_write(efd, 2);
    eventfd_t count;
    eventfd_read(efd, &count);
    std::cout << count << std::endl;
    close(efd);
}

上面的程序中我们创建了一个eventfd,并将它的文件描述符保存在efd中，然后调用eventfd_write向计数器中写入数字2，然后调用eventfd_read读取计数器中的值并打印处理，最后关闭eventfd。
运行结果：

1	复制代码count=2

多次read和write

复制代码#include <sys/eventfd.h>
#include <unistd.h>
#include <iostream>

int main() {
    int efd = eventfd(0, EFD_NONBLOCK | EFD_CLOEXEC);
    eventfd_write(efd, 2);
    eventfd_write(efd, 3);
    eventfd_write(efd, 4);
    eventfd_t count;
    int read_result = eventfd_read(efd, &count);
    std::cout << "read_result=" << read_result << std::endl;
    std::cout << "count=" << count << std::endl;
    read_result = eventfd_read(efd, &count);
    std::cout << "read_result=" << read_result << std::endl;
    std::cout << "count=" << count << std::endl;
    close(efd);
}

运行结果：

复制代码read_result=0
count=9
read_result=-1
count=9

从运行结果我们可以看出当多次调用eventfd_write的时候，计数器一直在累加，但是eventfd_read只需调用一次就可以将计数器中的数取出来，如果再次调用eventfd_read将会返回失败。

EFD_NONBLOCK标志位的作用

复制代码#include <sys/eventfd.h>
#include <unistd.h>
#include <iostream>

int main() {
    int efd = eventfd(0, EFD_CLOEXEC);
    eventfd_write(efd, 2);
    eventfd_write(efd, 3);
    eventfd_write(efd, 4);
    eventfd_t count;
    int read_result = eventfd_read(efd, &count);
    std::cout << "read_result=" << read_result << std::endl;
    std::cout << "count=" << count << std::endl;
    read_result = eventfd_read(efd, &count);
    std::cout << "read_result=" << read_result << std::endl;
    std::cout << "count=" << count << std::endl;
    close(efd);
}

运行结果：

1 2	复制代码read_result=0 count=9

和前一个运行结果直接返回-1相比，如果去掉EFD_NONBLOCK标志位，程序会在计数器没有值的情况下一直阻塞在eventfd_read方法。

EFD_SEMAPHORE标志位的作用

复制代码#include <sys/eventfd.h>
#include <unistd.h>
#include <iostream>

int main() {
    int efd = eventfd(0, EFD_NONBLOCK | EFD_CLOEXEC | EFD_SEMAPHORE);
    eventfd_write(efd, 2);
    eventfd_t count;
    int read_result = eventfd_read(efd, &count);
    std::cout << "read_result=" << read_result << std::endl;
    std::cout << "count=" << count << std::endl;
    read_result = eventfd_read(efd, &count);
    std::cout << "read_result=" << read_result << std::endl;
    std::cout << "count=" << count << std::endl;
    read_result = eventfd_read(efd, &count);
    std::cout << "read_result=" << read_result << std::endl;
    std::cout << "count=" << count << std::endl;
    close(efd);
}

运行结果：

复制代码read_result=0
count=1
read_result=0
count=1
read_result=-1
count=1

可以看到设置了EFD_SEMAPHORE后，每次读取到的值都是1，且read后计数器也递减1。

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

基于 Spring Boot 20 构建一个 RESTfu

发表于 2018-04-17

REST 全称是 Representational State Transfer，中文意思是“表述性状态转移”。RESTful 是关于 Web 的现有特征和使用方式的一些准则和约束。基于 Spring MVC 的 RestController，我们可以方便的构建一个 RESTful 风格的应用。

使用 Maven 创建项目

我们可以直接使用 IntelliJ IDEA （推荐）中的 Spring initializer 快速创建一个基于 Spring Boot 的项目，这里使用 Maven 构建， pom.xml 文件如下：

复制代码<?xml version="1.0" encoding="UTF-8"?>
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>

    <groupId>org.springframework</groupId>
    <artifactId>gs-rest-service</artifactId>
    <version>0.1.0</version>

    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>2.0.1.RELEASE</version>
    </parent>

    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
        </dependency>
        <dependency>
            <groupId>com.jayway.jsonpath</groupId>
            <artifactId>json-path</artifactId>
            <scope>test</scope>
        </dependency>
    </dependencies>

    <properties>
        <java.version>1.8</java.version>
    </properties>


    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
            </plugin>
        </plugins>
    </build>

    <repositories>
        <repository>
            <id>spring-releases</id>
            <url>https://repo.spring.io/libs-release</url>
        </repository>
    </repositories>
    <pluginRepositories>
        <pluginRepository>
            <id>spring-releases</id>
            <url>https://repo.spring.io/libs-release</url>
        </pluginRepository>
    </pluginRepositories>
</project>

Spring Maven plugin 是 Spring 针对 Maven 开发的一套插件，包含了几个强大的功能：

无需过多复杂的配置即可快速构建一个可执行的 jar 包，使应用的运行可以几乎不受环境的影响
自动搜索 public static void main() 方法，并将其所在的类标志为启动类
对 Spring Boot 的依赖进行自动化管理，所有的依赖项目版本都和 Spring Boot 父项目保持一致（默认情况下），当然也可以手动指定其他版本

Spring 同样支持 Gradle 构建，详细配置请参考 Build with Gradle

创建实体类

这里的实体类并非 ORM 中的实体类，而是 REST 中的 “资源” ，我们的 web service 要实现的功能是处理 URL 为 /userinfo/1 的 GET 请求，并将结果以 JSON 作为响应体返回，响应状态码为 200 OK，JSON 的格式如下：

复制代码{
    "id": 1,
    "name": "张三"
}

这个例子简单模拟了获取 id 为 1 的用户信息，首先要创建 POJO 类 User：

复制代码public class User {

    private final long id;
    private final String name;

    public User(long id, String name) {
        this.id = id;
        this.name = name;
    }

    public long getId() {
        return id;
    }

    public String getName() {
        return name;
    }
}

1	复制代码Spring 默认使用 `Jackson` 作为 JSON 解析库将 POJO 类对象序列化为 JSON。

创建 Controller

在 controller 类上添加 @RestController 注解即可实现将返回值序列化为 JSON 并充当响应体返回，返回的 content-type 为 application/json，请求 /user/1 将得 id 为 1 的用户的信息，下面是 controller 类：

复制代码@RestController
public class GreetingController {

    private static final String template = "张三";
    private final long id = 1;

    @RequestMapping("/user/{id}")
    public User userInfo(@PathVariable("id")long id) {
        return new User(id, template);
    }
}

让应用跑起来

传统的构建方式是生成一个 war 文件然后部署到 web 服务器上，这样有时会觉得不太方便，因此推荐使用 Spring Boot 的 Maven 插件快速生成一个独立的可执行的 jar 文件，使用 java -jar 命令即可启动这个应用，所有的类和资源等文件都被集成到这一个 jar 文件中，里面也包括了嵌入式的 servlet 容器（比如 Tomcat），下面是这个应用的启动类：

复制代码@SpringBootApplication
public class Application {

    public static void main(String[] args) {
        SpringApplication.run(Application.class, args);
    }
}

@SpringBootApplication 这个注解是一个组合注解，它包括：

@Configuration：声明这个类是上下文中的 bean 的配置类
@EnableAutoConfiguration：使 Spring 将上下文中扫描到的相关 bean 配置类或 properties 类，并将这些 bean 放到应用上下文中
Spring 当检测到 classpath 下有 spring-webmvc 的依赖后，会自动给应用启动类上添加 @EnableWebMvc 的注解，它表示这个应用是一个 web 应用，应用启动时就会执行和 web 相关的操作，比如实例化 DispatcherServlet 类并进行相关的配置
@ComponentScan：使 Spring 扫描所有自定义组件类、配置类、业务类以及控制器，并将其装配

在启动类中的 main 方法中调用 SpringBootApplication.run() 即可实现应用的启动，和传统 Java web 应用配置复杂的 web.xml 文件截然不同，不需要在配置上花费太多时间

构建可执行的 jar

我们可以使用一条简单的命令来完成应用打包成 jar：

1	复制代码$ ./mvnw clean package

执行这条命令来启动应用：

1 2	复制代码 $ java -jar target/gs-rest-service-0.1.0.jar

做一些简单的测试

在浏览器中访问 htpp://localhost:8080/user/1，没问题的话会得到如下响应：

复制代码{
    "id": 1,
    "name": "张三"
}

总结

这仅仅是一个 RESTful web service，更多文档请浏览：Building a RESTful Web Service

个人博客同步更新，获取更多技术分享请关注：郑保乐的博客

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

【译】数据结构中关于树的一切（java版）

发表于 2018-04-17

你每天都那么努力，忍受了那么多的寂寞和痛苦。可我也没见你有多优秀。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1dd95fa3~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1dd95fa3~tplv-t2oaga2asx-image.image)

当我还是一个年轻男孩的时候画的一张关于树的画。

当你第一次学习编码时，大部分人都是将数组作为主要数据结构来学习。

之后，你将会学习到哈希表。如果你是计算机专业的，你肯定需要选修一门数据结构的课程。上课时，你又会学习到链表，队列和栈等数据结构。这些都被统称为线性的数据结构，因为它们在逻辑上都有起点和终点。

当你开始学习树和图的数据结构时，你会觉得它是如此的混乱。因为它的存储方式不是线性的，它们都有自己特定的方式存储数据。

这篇文章帮助你更好的理解树形数据结构并尽可能的帮你解决你的疑问。本章我们将学到

是什么是树？
一个简单树的例子
树的术语和工作原理
如何在代码中实现树结构

定义

当学习编程时，我们更容易理解线性的数据结构而不是树和图的数据结构。

树是众所周知的非线性数据结构。它们不以线性方式存储数据。他们按层次组织数据。

我们来举例一个现实生活中的例子

我们所说的层次组织到底是是什么呢？

想象一下我们的家谱：祖父母，父母，子女，兄弟姐妹等等，我们通常按层次结构组织家谱。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1d8bd514~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1d8bd514~tplv-t2oaga2asx-image.image)

我的家庭族谱

上图是我的家谱。tossico，akikazu，hitomi和takemi是我的祖父母。

Toshiaki 和 Juliana 是我的父母。

TK 、Yuji 、Bruno 和 Kaio 是我父母的孩子（我和我的兄弟们）。

另一个层次结构的例子是企业的组织结构。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1d51bf83~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1d51bf83~tplv-t2oaga2asx-image.image)

公司的结构也是是一个层次结构的例子

在 HTML 中，文档对象模型（DOM）是树形结构的。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1d86c62f~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1d86c62f~tplv-t2oaga2asx-image.image)

文档对象模型（dom）

HTML 标签包含其他的标签。我们有一个 head 标签和 body 标签。这些标签包含特点的元素。head 标签中有 meta 和 title 标签。body 标签中有在用户界面展示的标签，如 h1 、a 、li 等等。

树的术语定义

树(tree)是被称为结点(node)的实体的集合。结点通过边(edge)连接。每个结点都包含值或数据(value/date)，并且每结节点可能有也可能没有子结点。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1d6f688b~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1d6f688b~tplv-t2oaga2asx-image.image)
树的首结点叫根结点（即root结点）。如果这个根结点和其他结点所连接，那么根结点是父结点(parent node，与根结点连接的是子结点（child node）。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1dcd4d97~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c1dcd4d97~tplv-t2oaga2asx-image.image)
所有的结点都通过边(edge)连接。它是树中很重要得一个概念，因为它负责管理节点之间的关系。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c6b710864~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c6b710864~tplv-t2oaga2asx-image.image)
叶子结点（leaves）是树末端，它们没有子结点。像真正的大树一样，我们可以看到树上有根、枝干和树叶。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c73645dae~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c73645dae~tplv-t2oaga2asx-image.image)
树的高度(height)和深度(depth)

树的高度是到叶子结点（树末端）的长度
结点的深度是它到根结点的长度

术语汇总

根结点是树最顶层结点
边是两个结点之间的连接
子结点是具有父结点的结点
父结点是与子结点有连接的结点
叶子结点是树中没有子结点的结点（树得末端）
高度是树到叶子结点（树得末端）的长度
深度是结点到根结点的长度

二叉树

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c751c98d5~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4c751c98d5~tplv-t2oaga2asx-image.image)
现在我们来讨论一个特殊的树类型。我们把它叫作二叉树。

“在计算机科学领域，二叉树是一种树形数据结构，它的每个节点最多有两个孩子，被叫作左孩子和右孩” — Wikipedia

我们来写一个二叉树

当我们要实现二叉树时，我们需要牢记的第一件事是它是一个结点集合。每个结点都有三个属性：value，left_child``和right_child。

那么我们怎么才能实现一个有这三个属性的简单二叉树呢？

我们来实现一个二叉树的例子

复制代码/**
 * Created on 2018/4/16.
 *
 * @author zlf
 * @since 1.0
 */
public class BinaryTree {

    public BinaryTree left; //左节点

    public BinaryTree right; //右节点

    public String data;  //树的内容

    public BinaryTree() {
    }

    /**
     * 构造方法
     *
     * @param data
     * @param left
     * @param right
     */
    public BinaryTree(String data, BinaryTree left, BinaryTree right) {
        this.left = left;
        this.right = right;
        this.data = data;
    }

    /**
     * 构造方法
     *
     * @param data
     */
    public BinaryTree(String data) {
        this(data, null, null);
    }

好，这就是我们的二叉树类

当我们实例化一个对象时，我们把值（点的相关数据）作为参数传递给类。看上面类的左孩子结点和右孩子结点。两个都被赋值为null。

为什么？

因为当我们创建节点时，它还没有孩子，只有结点数据。

代码测试

复制代码   /**
     * 构建树
     */
    public static void testCreate() {
        BinaryTree node = new BinaryTree("a");

        System.out.println("【node data】:" + node.getData());
        System.out.println("【node left data】:" + (node.left==null?"null":node.left.getData()));
        System.out.println("【node right data】:" + (node.right==null?"null":node.right.getData()));
    }

输出：

1
2
3

复制代码【node data】:a
【node left data】:null
【node right data】:null

我们可以将字符串’a’作为参数传给二叉树结点。如果将值、左孩子结点、右孩子结节点输出的话，我们就可以看到这个值了。

下面开始插入部分的操作。那么我们需要做些什么工作呢？

有两个要求：

如果当前的结点没有左孩子结点，我们就创建一个新结点，然后将其设置为当前结点的左结点。
如果已经有了左结点，我们就创建一个新结点，并将其放在当前左结点的位置。然后再将原左结点值为新左结点的左结点。

图形如下：

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4d10dfd5d0~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4d10dfd5d0~tplv-t2oaga2asx-image.image)
下面是插入的代码：

复制代码 /**
     * 插入节点 ，如果当前的节点没有左节点，我们就创建一个新节点，然后将其设置为当前节点的左节点。
     *
     * @param node
     * @param value
     */
    public static void insertLeft(BinaryTree node, String value) {
        if (node != null) {
            if (node.left == null) {
                node.setLeft(new BinaryTree(value));
            } else {
                BinaryTree newNode = new BinaryTree(value);
                newNode.left = node.left;
                node.left = newNode;
           }
        } 
    }

再次强调，如果当前结点没有左结点，我们就创建一个新结点，并将其置为当前结点的左结点。否则，就将新结点放在左结点的位置，再将原左结点置为新左结点的左结点。

同样，我们编写插入右结点的代码

复制代码/**
    * 同插入左结点
    * @param node
    * @param value
    */
   public static void insertRight(BinaryTree node, String value) {
       if (node != null) {
           if (node.right == null) {
               node.setRight(new BinaryTree(value));
           } else {
               BinaryTree newNode = new BinaryTree(value);
               newNode.right = node.right;
               node.right = newNode;
           }
       } 
   }

但是这还不算完成。我们得测试一下。

我们来构造一个像下面这样的树：

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4d49ff6f75~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4d49ff6f75~tplv-t2oaga2asx-image.image)

有一个根结点
b是左结点
c是右结点
b的结节点是d(b没有左结点)
c的左结点是e
c的右结点是f
e，f都没有子结点

下面是这棵树的实现代码：

复制代码/**
     * 测试插入结点
     */
    public static void testInsert() {
        BinaryTree node_a = new BinaryTree("a");
        node_a.insertLeft(node_a, "b");
        node_a.insertRight(node_a, "c");

        BinaryTree node_b = node_a.left;
        node_b.insertRight(node_b, "d");

        BinaryTree node_c = node_a.right;
        node_c.insertLeft(node_c, "e");
        node_c.insertRight(node_c, "f");

        BinaryTree node_d = node_b.right;
        BinaryTree node_e = node_c.left;
        BinaryTree node_f = node_c.right;

        System.out.println("【node_a data】:" + node_a.getData());
        System.out.println("【node_b data】:" + node_b.getData());
        System.out.println("【node_c data】:" + node_c.getData());
        System.out.println("【node_d data】:" + node_d.getData());
        System.out.println("【node_e data】:" + node_e.getData());
        System.out.println("【node_f data】:" + node_f.getData());
    }

输出：

复制代码【node_a data】:a
【node_b data】:b
【node_c data】:c
【node_d data】:d
【node_e data】:e
【node_f data】:f

插入已经结束

现在，我们来考虑一下树的遍历。

树的遍历有两种选择，深度优先搜索（DFS）和广度优先搜索（BFS）。

DFS是用来遍历或搜索树数据结构的算法。从根节点开始，在回溯之前沿着每一个分支尽可能远的探索。 — Wikipedia

BFS是用来遍历或搜索树数据结构的算法。从根节点开始，在探索下一层邻居节点前，首先探索同一层的邻居节点。 — Wikipedia

下面，我们来深入了解每一种遍历算法。

深度优先搜索（Depth-First Search，DFS）

DFS 在回溯和搜索其他路径之前找到一条到叶节点的路径。让我们看看这种类型的遍历的示例。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4ca8eabc95~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4ca8eabc95~tplv-t2oaga2asx-image.image)
输出结果为： 1–2–3–4–5–6–7

为什么？

让我们分解一下：

从根结点（1）开始。输出
进入左结点（2）。输出
然后进入左孩子（3）。输出
回溯，并进入右孩子（4）。输出
回溯到根结点，然后进入其右孩子（5）。输出
进入左孩子（6）。输出
回溯，并进入右孩子（7）。输出
完成

当我们深入到叶结点时回溯，这就被称为 DFS 算法。

既然我们对这种遍历算法已经熟悉了，我们将讨论下 DFS 的类型：前序、中序和后序。

前序遍历

这和我们在上述示例中的作法基本类似。

输出节点的值
进入其左结点并输出。当且仅当它拥有左结点。
进入右结点并输出之。当且仅当它拥有右结点

复制代码/**
     * 前序遍历
     *
     * @param node
     */
    public static void preOrder(BinaryTree node) {
        if (node != null) {

            System.out.println(node.data);

            if (node.left != null) {
                node.left.preOrder(node.left);
            }

            if (node.right != null) {
                node.right.preOrder(node.right);
            }
        }
    }

中序遍历

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4d9d967906~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4d9d967906~tplv-t2oaga2asx-image.image)
示例中此树的中序算法的结果是3–2–4–1–6–5–7。

左结点优先，之后是中间，最后是右结点。

代码实现：

复制代码/**
     * 中序遍历
     *
     * @param node
     */
    public static void inOrder(BinaryTree node) {
        if (node != null) {
            if (node.left != null) {
                node.left.inOrder(node.left);
            }

            System.out.println(node.data);

            if (node.right != null) {
                node.right.inOrder(node.right);
            }
        }
    }

进入左结点并输出之。当且仅当它有左结点。
输出根结点的值。
进入结节点并输出之。当且仅当它有结节点。

后序遍历

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4d71908b54~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4d71908b54~tplv-t2oaga2asx-image.image)
以此树为例的后序算法的结果为 3–4–2–6–7–5–1 。

左结点优先，之后是右结点，根结点的最后。

代码实现：

复制代码/**
     * 后序遍历
     *
     * @param node
     */
    public static void postOrder(BinaryTree node) {
        if (node != null) {
            if (node.left != null) {
                node.left.postOrder(node.left);
            }

            if (node.right != null) {
                node.right.postOrder(node.right);
            }

            System.out.println(node.data);
        }
    }

进入左结点输出，
进入右结点输出
输出根结点

广度优先搜索（BFS）

BFS是一层层逐渐深入的遍历算法

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4d86da5624~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4d86da5624~tplv-t2oaga2asx-image.image)
下面这个例子是用来帮我们更好的解释该算法。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4da7d3108c~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4da7d3108c~tplv-t2oaga2asx-image.image)
我们来一层一层的遍历这棵树。本例中，就是1-2-5-3-4-6-7.

0层/深度0：只有值为1的结点
1层/深度1：有值为2和5的结点
2层/深度2：有值为3、4、6、7的结点

代码实现：

复制代码/**
     * 广度排序
     *
     * @param node
     */
    public static void bfsOrder(BinaryTree node) {
        if (node != null) {
            Queue<BinaryTree> queue = new ArrayDeque<BinaryTree>();
            queue.add(node);

            while (!queue.isEmpty()) {
                BinaryTree current_node = queue.poll();

                System.out.println(current_node.data);

                if (current_node.left != null) {
                    queue.add(current_node.left);
                }
                if (current_node.right != null) {
                    queue.add(current_node.right);
                }
            }
        }
    }

为了实现BFS算法，我们需要用到一个数据结构，那就是队列。

队列具体是用来干什么的呢？

请看下面解释。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4dc5edd2de~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4dc5edd2de~tplv-t2oaga2asx-image.image)

首先用add方法将根结点添加到队列中。
当队列不为空时迭代。
获取队列中的第一个结点，然后输出其值
将左节点和右结点添加到队列
在队列的帮助下我们将每一个结点值一层层输出

二叉搜索树

二叉搜索树有时候被称为二叉有序树或二叉排序树，二叉搜索树的值存储在有序的顺序中，因此，查找表和其他的操作可以使用折半查找原理。——Wikipedia

二叉搜索树中的一个重要性质是，二叉搜索树中一个节点的值大于其左结点，但是小于其右结点

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4dba65fe53~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4dba65fe53~tplv-t2oaga2asx-image.image)

是反的二叉搜索树。子树 7-5-8-6应该在右边，而子树2-1-3 应该在左边。
是唯一正确的选项。它满足二叉搜索树的性质
有一个问题：值为4的那个结点应该在根结点的左边，因为这个节点的值比根结点的值5小。

代码实现二叉树搜索

插入：向我们的树添加新的结点

现在想像一下我们有一棵空树，我们想将几个节点添加到这棵空树中，这几个结点的值为：50、76、21、4、32、100、64、52。

首先我们需要知道的是，50是不是这棵树的根结点。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4de9c2fa9b~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4de9c2fa9b~tplv-t2oaga2asx-image.image)
现在我们开始一个一个的插入结点

76比50大，所以76插入在右边。
21比50小，所以21插入在左边。
4比50小。但是50已经有了值为21的左结点。然后，4又比21小，所以将其插入在21的左边。
32比50小。但是50已经有了值为21的左结点。然后，32又比21大，所以将其插入在21的右边。
100比50大。但是50已经有了一个值为76的右结点。然后，100又比76大，所以将其插入在76的右边。
64比50大。但是50已经有了一个值为76的右结点。然后，64又比76小，所以将其插入在76的左边。
52比50大。但是50已经有了一个值为76的右结点。52又比76小，但是76也有一个值为64左结点。52又比64小，所以将52插入在64的左边。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4ddebdb757~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4ddebdb757~tplv-t2oaga2asx-image.image)
你注意到这里的模式了吗？

让我们把它分解。

新结点值大于当前节点还是小于当前结点？
如果新节点的值大于当前结点，则转到右结点。如果当前节点没有右结点，则在那里插入新结点，否则返回步骤1。
如果新节点的值小于当前结点，则转到左结点。如果当前节点没有左结点，则在那里插入新结点，否则返回步骤1。
这里我们没有处理特殊情况。当新节点的值等于结点的当前值时，使用规则3。考虑在子结点的左侧插入相等的值。

代码实现：

复制代码/**
     * 插入树
     *
     * @param node
     * @param value
     */
    public void insertNode(BinaryTree node, Integer value) {
        if (node != null) {
            if (value <= Integer.valueOf(node.data) && node.left != null) {
                node.left.insertNode(node.left, value);
            } else if (value <= Integer.valueOf(node.data)) {
                node.left = new BinaryTree(String.valueOf(value));
            } else if (value > Integer.valueOf(node.data) && node.right != null) {
                node.right.insertNode(node.right, value);
            } else {
                node.right = new BinaryTree(String.valueOf(value));
            }
        }
    }

看起来很简单。

该算法的强大之处是其递归部分，即第9行和第13行。这两行代码均调用 insertNode 方法，并分别为其左结点和右结点使用它。第11行和第15行则在子结点处插入新结点。

搜索结点

我们现在要构建的算法是关于搜索的。对于给定的值（整数），我们会搜索出我们的二叉查找树有或者没有这个值。

需要注意的一个重要事项是我们如何定义树的插入算法。首先我们有根结点。所有左子的节点值都比根结点小。所有右子树的节点值都比根结点大。

让我们看一个例子。

假设我们有这棵树。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4e3601f689~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4e3601f689~tplv-t2oaga2asx-image.image)
现在我们想知道是否有一个结点的值为52。

[

https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4e45584fe1~tplv-t2oaga2asx-image.image](https://p1-jj.byteimg.com/tos-cn-i-t2oaga2asx/gold-user-assets/2018/4/17/162d1b4e45584fe1~tplv-t2oaga2asx-image.image)
让我们把它分解。

我们以根结点作为当前节点开始。给定值小于当前结点值吗？如果是，那么我将在左子树上查找它。
给定值大于当前结点值吗？如果是，那么我们将在右子树上查找它。
如果规则 #1 和 #2 均为假，我们可以比较当前节点值和给定值是否相等。如果返回真，那么我们可以说：“是的，我们的树拥有给定的值。” 否则，我们说： “不，我们的树没有给定的值。”

代码实现：

复制代码/**
     * 查找节点是否存在
     *
     * @param node
     * @param value
     * @return
     */
    public boolean findNode(BinaryTree node, Integer value) {
        if (node != null) {
            if (value < Integer.valueOf(node.data) && node.left != null) {
                return node.left.findNode(node.left, value);
            }
            if (value > Integer.valueOf(node.data) && node.right != null) {
                return node.right.findNode(node.right, value);
            }
            return value == Integer.valueOf(node.data);
        }
        return false;
    }

代码分析：

第8行和第9行归于规则#1。
第10行和第11行归于规则#2。
第13行归于规则#3。

删除：移除和重新组织树

删除是一个更复杂的算法，因为我们需要处理不同的情况。对于给定值，我们需要删除具有此值的结点。想象一下这个节点的以下场景：它没有孩子，有一个孩子，或者有两个孩子。

一个没有孩子的节点（叶节点）。

复制代码#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 20) --->   |30|   |70|
#   /    \                                \
# |20|   |40|                             |40|

如果要删除的结点没有子结点，我们简单地删除它。该算法不需要重组树。

仅有一个孩子（左或右孩子）的结点。

复制代码#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |20|   |70|
#   /            
# |20|

在这种情况下，我们的算法需要使节点的父节点指向子结点。如果节点是左孩子，则使其父结点指向其子结点。如果结点是右孩子，则使其父结点指向其子结点。

有两个孩子的节点。

复制代码#        |50|                              |50|
#      /      \                           /    \
#    |30|     |70|   (DELETE 30) --->   |40|   |70|
#   /    \                             /
# |20|   |40|

当节点有两个孩子，则需要从该节点的右孩子开始，找到具有最小值的结点。我们将把具有最小值的这个节点置于被删除的节点的位置。

代码实现：

复制代码
    /**
     * 删除节点
     * @param node
     * @param value
     * @param parent
     * @return
     */
    public boolean removeNode(BinaryTree node, Integer value, BinaryTree parent) {
        if (node != null) {
            if (value < Integer.valueOf(node.data) && node.left != null) {
                return node.left.removeNode(node.left, value, node);
            } else if (value < Integer.valueOf(node.data)) {
                return false;
            } else if (value > Integer.valueOf(node.data) && node.right != null) {
                return node.right.removeNode(node.right, value, node);
            } else if (value > Integer.valueOf(node.data)) {
                return false;
            } else {
                if (node.left == null && node.right == null && node == parent.left) {
                    parent.left = null;
                    node.clearNode(node);
                } else if (node.left == null && node.right == null && node == parent.right) {
                    parent.right = null;
                    node.clearNode(node);
                } else if (node.left != null && node.right == null && node == parent.left) {
                    parent.left = node.left;
                    node.clearNode(node);
                } else if (node.left != null && node.right == null && node == parent.right) {
                    parent.right = node.left;
                    node.clearNode(node);
                } else if (node.right != null && node.left == null && node == parent.left) {
                    parent.left = node.right;
                    node.clearNode(node);
                } else if (node.right != null && node.left == null && node == parent.right) {
                    parent.right = node.right;
                    node.clearNode(node);
                } else {
                    node.data=String.valueOf(node.right.findMinValue(node.right));
                    node.right.removeNode(node.right,Integer.valueOf(node.right.data),node);
                }
                return true;
            }
        }
        return false;
    }

首先: 注意下参数 value 和 parent 。我们想找到值等于该 value 的 node ，并且该 node 的父节点对于删除该 node 是至关重要的。
其次: 注意下返回值。我们的算法将会返回一个布尔值。我们的算法在找到并删除该节点时返回 true 。否则返回 false 。
第2行到第9行：我们开始查找等于我们要查找的给定的 value 的 node 。如果该 value 小于 current node 值，我们进入左子树，递归处理（当且仅当，current node 有左孩子）。如果该值大于，则进入右子树。递归处理。
第10行: 我们开始考虑删除算法。
第11行到第13行: 我们处理了没有孩子、并且是父节点的左孩子的节点。我们通过设置父节点的左孩子为空来删除该节点。
第14行和第15行: 我们处理了没有孩子、并且是父节点的右孩子的节点。我们通过设置父节点的右孩子为空来删除该节点。
清除节点的方法：我将会在后续文章中给出 clear_node 的代码。该函数将节点的左孩子、右孩子和值都设置为空。
第16行到第18行: 我们处理了只有一个孩子（左孩子）、并且它是其父节点的左孩子的节点。我们将父节点的左孩子设置为当前节点的左孩子（这是它唯一拥有的孩子）。
第19行到第21行: 我们处理了只有一个孩子（左孩子）、并且它是其父节点的右孩子的节点。我们将父节点的右孩子设置为当前节点的左孩子（这是它唯一拥有的孩子）。
第22行到第24行: 我们处理了只有一个孩子（右孩子），并且是其父节点的左孩子的节点。我们将父节点的左孩子设置为当前节点的右孩子（这是它唯一的孩子）。
第25行到第27行: 我们处理了只有一个孩子（右孩子），并且它是其父节点的右孩子的节点。我们将父节点的右孩子设置为当前节点的右孩子（这是它唯一的孩子）。
第28行到第30行: 我们处理了同时拥有左孩子和右孩子的节点。我们获取拥有最小值的节点（代码随后给出），并将其值设置给当前节点。通过删除最小的节点完成节点移除。
第32行: 如果我们找到了要查找的节点，就需要返回 true 。从第11行到第31行，我们处理了这些情况。所以直接返回 true ，这就够了。

clear_node 方法：设置节点的三个属性为空——(value, left_child, and right_child)

复制代码/**
     * 清空n节点
     *
     * @param node
     */
    public void clearNode(BinaryTree node) {
        node.data = null;
        node.left = null;
        node.right = null;
    }

find_minimum_value方法：一路向下找最左侧的。如果我们无法找到任何节点，我们找其中最小的

复制代码/**
     * 查找树中最小值
     */
    public Integer findMinValue(BinaryTree node) {
        if (node != null) {
            if (node.left != null) {
                return node.left.findMinValue(node.left);
            } else {
                return Integer.valueOf(node.data);
            }
        }
        return null;
    }

原文链接：Everything you need to know about tree data structures

代码下载：

从我的 github 中下载，【译】数据结构中关于树的一切（java版)

为什么在Go语言中要慎用interface{}

发表于 2018-04-14

记得刚从Java转Go的时候，一个用Go语言的前辈告诉我：“要少用interface{}，这玩意儿很好用，但是最好不要用。”那时候我的组长打趣接话：“不会，他是从Java转过来的，碰到个问题就想定义个类。”当时我对interface{}的第一印象也是类比Java中的Object类，我们使用Java肯定不会到处去传Object啊。后来的事实证明，年轻人毕竟是年轻人，看着目前项目里漫天飞的interface{}，它们时而变成函数形参让人摸不着头脑；时而隐藏在结构体字段中变化无穷。不禁想起以前看到的一句话：“动态语言一时爽，重构代码火葬场。”故而写下此篇关于interface{}的经验总结，供以后的自己和读者参考。

1. interface{}之对象转型坑

一个语言用的久了，难免使用者的思维会受到这个语言的影响，interface{}作为Go的重要特性之一，它代表的是一个类似*void的指针，可以指向不同类型的数据。所以我们可以使用它来指向任何数据，这会带来类似与动态语言的便利性，如以下的例子：

复制代码type BaseQuestion struct{
    QuestionId int
    QuestionContent string
}

type ChoiceQuestion struct{
    BaseQuestion
    Options []string
}

type BlankQuestion struct{
    BaseQuestion
    Blank string
}

func fetchQuestion(id int) (interface{} , bool) {
    data1 ,ok1 := fetchFromChoiceTable(id) // 根据ID到选择题表中找题目，返回(ChoiceQuestion)
    data2 ,ok2 := fetchFromBlankTable(id)  // 根据ID到填空题表中找题目，返回(BlankQuestion)
    
    if ok1 {
        return data1,ok1
    }
    
    if ok2 {
        return data2,ok2
    }
    
    return nil ,false
}

在上面的代码中，data1是ChoiceQuestion类型，data2是BlankQuestion类型。因此，我们的interface{}指代了三种类型，分别是ChoiceQuestion、BlankQuestion和nil，这里就体现了Go和面向对象语言的不同点了，在面向对象语言中，我们本可以这么写：

1
2
3

复制代码func fetchQuestion(id int) (BaseQuestion , bool) {
    ...
}

只需要返回基类BaseQuestion即可，需要使用子类的方法或者字段只需要向下转型。然而在Go中，并没有这种is-A的概念，代码会无情的提示你，返回值类型不匹配。

那么，我们该如何使用这个interface{}返回值呢，我们也不知道它是什么类型啊。所以，你得不厌其烦的一个一个判断：

复制代码func printQuestion(){
    if data, ok := fetchQuestion(1001); ok {
		switch v := data.(type) {
		case ChoiceQuestion:
			fmt.Println(v)
		case BlankQuestion:
			fmt.Println(v)
		case nil:
			fmt.Println(v)
		}
		fmt.Println(data)
	}
}

// ------- 输出--------
{{1001 CHOICE} [A B]}
data -  &{{1001 CHOICE} [A B]}

EN，好像通过Go的switch-type语法糖，判断起来也不是很复杂嘛。如果你也这样以为，并且跟我一样用了这个方法，恭喜你已经入坑了。

因为需求永远是多变的，假如现在有个需求，需要在ChoiceQuesiton打印时，给它的QuestionContent字段添加前缀选择题，于是代码变成以下这样：

复制代码func printQuestion() {
	if data, ok := fetchQuestion(1001); ok {
		switch v := data.(type) {
		case ChoiceQuestion:
		    v.QuestionContent = "选择题"+ v.QuestionContent
			fmt.Println(v)
			
		...
		fmt.Println(data)
	}
}

// ------- 输出--------
{{1001 选择题CHOICE} [A B]}
data -  {{1001 CHOICE} [A B]}

我们得到了不一样的输出结果，而data根本没有变动。可能有的读者已经猜到了，v和data根本不是指向同一份数据，换句话说，v := data.(type)这条语句，会新建一个data在对应type下的副本，我们对v操作影响不到data。当然，我们可以要求fetchFrom***Table()返回*ChoiceQuestion类型，这样我们可以通过判断*ChoiceQuestion来处理数据副本问题：

复制代码func printQuestion() {
	if data, ok := fetchQuestion(1001); ok {
		switch v := data.(type) {
		case *ChoiceQuestion:
		    v.QuestionContent = "选择题"+ v.QuestionContent
			fmt.Println(v)
		...
		fmt.Println(data)
	}
}
// ------- 输出--------
&{{1001 选择题CHOICE} [A B]}
data -  &{{1001 选择题CHOICE} [A B]}

不过在实际项目中，你可能有很多理由不能去动fetchFrom***Table()，也许是涉及数据库的操作函数你没有权限改动；也许是项目中很多地方使用了这个方法，你也不能随便改动。这也是我没有写出fetchFrom***Table()的实现的原因，很多时候，这些方法对你只能是黑盒的。退一步讲，即使方法签名可以改动，我们这里也只是列举出了两种题型，可能还有材料题、阅读题、写作题等等，如果需求要对每个题型的QuestonContent添加对应的题型前缀，我们岂不是要写出下面这种代码：

复制代码func printQuestion() {
	if data, ok := fetchQuestion(1001); ok {
		switch v := data.(type) {
		case *ChoiceQuestion:
		    v.QuestionContent = "选择题"+ v.QuestionContent
		    fmt.Println(v)
		case *BlankQuestion:
		    v.QuestionContent = "填空题"+ v.QuestionContent
		    fmt.Println(v)
		case *MaterialQuestion:
		    v.QuestionContent = "材料题"+ v.QuestionContent
		    fmt.Println(v)
		case *WritingQuestion:
		    v.QuestionContent = "写作题"+ v.QuestionContent
		    fmt.Println(v)
		... 
		case nil:
		    fmt.Println(v)
		fmt.Println(data)
	}
}

这种代码带来了大量的重复结构，由此可见，interface{}的动态特性很不能适应复杂的数据结构，难道我们就不能有更方便的操作了么？山穷水尽之际，或许可以回头看看面向对象思想，也许继承和多态能很好的解决我们遇到的问题。

我们可以把这些题型抽成一个接口，并且让BaseQuestion实现这个接口。

复制代码type IQuestion interface{
    GetQuestionType() int
    GetQuestionContent()string
    AddQuestionContentPrefix(prefix string)
}

type BaseQuestion struct {
	QuestionId      int
	QuestionContent string
	QuestionType    int
}

func (self *BaseQuestion) GetQuestionType() int {
	return self.QuestionType
}

func (self *BaseQuestion) GetQuestionContent() string {
	return self.QuestionContent
}

func (self *BaseQuestion) AddQuestionContentPrefix(prefix string) {
	self.QuestionContent = prefix + self.QuestionContent
}

//修改返回值为IQuestion
func fetchQuestion(id int) (IQuestion, bool) {
	data1, ok1 := fetchFromChoiceTable(id) // 根据ID到选择题表中找题目
	data2, ok2 := fetchFromBlankTable(id)  // 根据ID到选择题表中找题目

	if ok1 {
		return &data1, ok1
	}

	if ok2 {
		return &data2, ok2
	}

	return nil, false
}

不管有多少题型，只要它们包含BaseQuestion，就能自动实现IQuestion接口，从而，我们可以通过定义接口方法来控制数据。

复制代码func printQuestion() {
	if data, ok := fetchQuestion(1002); ok {
		var questionPrefix string

        //需要增加题目类型，只需要添加一段case
		switch  data.GetQuestionType() {
		case ChoiceQuestionType:
		    questionPrefix = "选择题"
		case BlankQuestionType:
		    questionPrefix = "填空题"
		}

		data.AddQuestionContentPrefix(questionPrefix)
		fmt.Println("data - ", data)
	}
}

//--------输出--------
data -  &{{1002 填空题BLANK 2} [ET AI]}

这种方法无疑大大减少了副本的创建数量，而且易于扩展。通过这个例子，我们也了解到了Go接口的强大之处，虽然Go并不是面向对象的语言，但是通过良好的接口设计，我们完全可以从中窥探到面向对象思维的影子。也难怪在Go文档的FAQ中，对于Is Go an object-oriented language?这个问题，官方给出的答案是yes and no.

这里还可以多扯一句，前面说了v := data.(type)这条语句是拷贝data的副本，但当data是接口对象时，这条语句就是接口之间的转型而不是数据副本拷贝了。

复制代码//定义新接口
type IChoiceQuestion interface {
	IQuestion
	GetOptionsLen() int
}

func (self *ChoiceQuestion) GetOptionsLen() int {
	return len(self.Options)
}

func showOptionsLen(data IQuestion) {
    //choice和data指向同一份数据
	if choice, ok := data.(IChoiceQuestion); ok {
	    fmt.Println("Choice has :", choice.GetOptionsLen())
	}
}

//------------输出-----------
Choice has : 2

2. interface{}之`nil`坑

看以下代码：

复制代码func fetchFromChoiceTable(id int) (data *ChoiceQuestion) {
	if id == 1001 {
		return &ChoiceQuestion{
			BaseQuestion: BaseQuestion{
				QuestionId:      1001,
				QuestionContent: "HELLO",
			},
			Options: []string{"A", "B"},
		}
	}
	return nil
}


func fetchQuestion(id int) (interface{}) {
	data1 := fetchFromChoiceTable(id) // 根据ID到选择题表中找题目
	return data1
}

func sendData(data interface{}) {
	fmt.Println("发送数据 ..." , data)
}

func main(){
    data := fetchQuestion(1002)
    
    if data != nil {
        sendData(data)
    }
}

一串很常见的业务代码，我们根据id查询Question，为了以后能方便的扩展，我们使用interface{}作为返回值，然后根据data是否为nil来判断是不是要发送这个Question。不幸的是，不管fetchQuestion()方法有没有查到数据，sendData()都会被执行。运行main()，打印结果如下:

1
2
3

复制代码发送数据 ... <nil>

Process finished with exit code 0

要明白内中玄机，我们需要回忆下interface{}究竟是个什么东西，文档上说，它是一个空接口，也就是说，一个没有声明任何方法的接口，那么，接口在Go的内部又究竟是怎么表示的？我在官方文档上找到一下几句话：

Under the covers, interfaces are implemented as two elements, a type and a value. The value, called the interface’s dynamic value, is an arbitrary concrete value and the type is that of the value. For the int value 3, an interface value contains, schematically, (int, 3).

以上的话大意是说，interface在Go底层，被表示为一个值和值对应的类型的集合体，具体到我们的示例代码，fetchQuestion()的返回值interface{}，其实是指(*ChoiceQuestion, data1)的集合体，如果没查到数据，则我们的data1为nil，上述集合体变成(*ChoiceQuestion, nil)。而Go规定中，这样的结构的集合体本身是非nil的，进一步的，只有(nil,nil)这样的集合体才能被判断为nil。

这严格来说，不是interface{}的问题，而是Go接口设计的规定，你把以上代码中的interface{}换成其它任意你定义的接口，都会产生此问题。所以我们对接口的判nil，一定要慎重，以上代码如果改成多返回值形式，就能完全避免这个问题。

复制代码func fetchQuestion(id int) (interface{},bool) {
	data1 := fetchFromChoiceTable(id) // 根据ID到选择题表中找题目
	if data1 != nil {
	    return data1,true
	}
	return nil,false
}

func sendData(data interface{}) {
	fmt.Println("发送数据 ..." , data)
}

func main(){
    if data, ok := fetchQuestion(1002); ok {
        sendData(data)
    }
}

当然，也有很多其它的办法可以解决，大家可以自行探索。

3. 总结和引用

零零散散写了这么多，有点前言不搭后语，语言不通之处还望见谅。Go作为一个设计精巧的语言，它的成功不是没有道理的，通过对目前遇到的几个大问题和总结，慢慢对Go有了一点点浅薄的认识，以后碰到了类似的问题，还可以继续添加在文章里。

interface{}作为Go中最基本的一个接口类型，可以在代码灵活性方面给我们提供很大的便利，但是我们也要认识到，接口就是对一类具体事物的抽象，而interface{}作为每个结构体都实现的接口，提供了一个非常高层次的抽象，以至于我们会丢失事物的大部分信息，所以我们在使用interface{}前，一定要谨慎思考，这就像相亲之前提要求，你要是说只要是个女的我都可以接受，那可就别怪来的人可能是高的矮的胖的瘦的美的丑的。

文中出现的代码，可以在示例代码中找到完整版。

EffectiveGo

GoFAQ

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

R 语言入门的 7 个技巧 R 语言入门的 7 个技巧

发表于 2018-04-11

R 语言入门的 7 个技巧

避免 R 编程语言的常见陷阱并快速入门

这样，您就正式进入 R 语言的世界了。或许您有 STATA 或 SAS 方面的背景，或许您精通 Python。或者，您可能是一位 Excel 专家。无论您拥有何种背景，在深入使用 R 编程语言之前，都应该对它有所了解。本文将重点介绍您在开始使用 R 语言之前应该了解的 7 件事，并帮助您避免新 R 语言用户会遇到的一些最常见问题。

在深入分析我们的技巧之前，让我们快速定义一下 R。R 是一种编程语言，通常用于统计计算和图形领域。但是，用户创建的大量包将 R 的适用性扩展到了数据分析和可视化之外的领域。

1.为此问题有一个适用包

最初，为看似无法使用基础 R 包解决的问题，您可能忍不住拼凑出一些解决方案。这是一个糟糕的想法，原因有很多，首要原因是，或许有一个包可用于简化您的解决方案并确保它没有错误。您需要了解并使用您的 R 包，R 包的大部分都存储在 Comprehensive R
Network (CRAN) 中。

清单 1 给出了一个让您更轻松完成工作的包的示例。

清单 1. 一个 R 包示例

复制代码library(sandwich)
library(lmtest)
xs <- rnorm(1000,10,2)
ys <- xs*2
X <- cbind(1,xs)
plot(ys~xs)
ys <- ys + xs * rnorm(1000,1,1)
plot(ys~xs)
mod <- lm(ys~xs)
summary(mod)
ehat <- diag(residuals(mod)^2)
sqrt(diag(solve(t(X)%*%X) %*% t(X) %*% ehat %*% X %*% solve(t(X)%*%X)))
coeftest(mod, vcov = sandwich)

清单 1 中的代码创建了两个将在回归函数中使用的数据矢量（第 3-5 行）。该数据的设计将 X 和 Y 关联起来，但也存在异方差性。第 7 行中的代码展示了异方差性是如何产生的。Y（已与 X 相关）有一个通过 X 创建的随机成份。异方差性不会妨碍您估算一次回归的能力。但是，各个系数的标准误差被认为是不可靠的，因此回归值只是估算值，而不是实际计算的值。然后，我们可以运行回归，查看来自 summary 函数的标准误差（错误的标准误差）。

为了计算可靠的标准误差，需要创建剩余矩阵以及一个 X 矩阵（第 11 和第 5 行）。然后，这些矩阵需要执行矩阵公式，以获得可靠的标准误差（第 12 行）。您可能需要在线查看一些操作，以便记住如何执行这些操作，并不可避免地不断试错。下一行（第 13 行）展示了如何使用 sandwich 和 lmtest 包获得可靠的标准误差。

这些包是在第 1 和第 2 行中加载的。为了使用它们，必须使用 install.packages() 函数安装它们。与尝试自己设计的方法相比，这些包更容易使用，而且产生错误的可能性更低。这些包不仅能够执行基础 R 无法执行的任务，还经过了开源社区的审查。

R 中的包拥有优秀的标准化文档，而且非常重视示例，这很有帮助。您应该使用包来解决基础 R 中的问题，确保理解这些包并以最佳方式使用它们。这样您的 R 代码就能变得很完美。

2.如何搭建数据结构

理解如何在 R 中搭建数据结构很重要。本节中的脚本和输出列出了一些可用的数据结构，包括矢量、矩阵、数据帧和列表。

数据结构用例

让我们快速查看每种数据结构类型的用例。

矢量：在需要存储同一类型的一个变量时使用，比如数据集中所有福特 F-150 的重量。
矩阵：在需要存储同一类型的多个变量或需要在 R 中移动或转换数据时使用。许多 R 函数需要将数据输入到矩阵中，比如主成份分析。
数据帧：用于存储不同数据类型的多个变量；它们非常适合调查和观察数据集。
列表：用于在不确定数据的类型长度时移动数据。列表适合用作函数结果的返回工具。

我们首先来研究一下矢量，如清单 2 所示。矢量是同类型数据的集合。它们是在 R 中移动数据的基础单元，而且它们是使用 C 函数创建的。它们很容易创建，而且各个元素可以使用一个索引（从 1 开始，而不是从 0 开始）来查看。

清单 2. R 中的矢量

复制代码#Vectors
vex <- c(1,5,3)
vex
[1] 1 5 3
vex <- c(1 + 2i,4,5)
vex
[1] 1+2i 4+0i 5+0i
vex <- c(TRUE,1,0,1)
vex
[1] 1 1 0 1
vex <- c("This","That",1)
vex
[1] "This" "That" "1"
vex[1]
[1] "This"

此代码表明，当您向 C 函数送入一组不同类型的数据时，它会将这些数据强制转换为一种给定类型。

矩阵也是如此，如清单 3 所示。矩阵不仅仅是二维矢量。R 也有多维数组，这些数组是更高维的矩阵。您可以使用两个矢量并创建一个矩阵。如果您没有指定其他任何选项，结果矩阵 mat1 是一个只有一列的矩阵。如果通过指定“2”来指定您希望在 mat1 中包含的行数，那么该矩阵现在是一个 2x5 矩阵。

清单 3. R 中的矩阵

复制代码#Matrices
v1 <- c(0:4)
v2 <- c(5:10)
mat1 <- matrix(c(v1,v2))
mat1
[,1]
 [1,] 0
 [2,] 1
 [3,] 2
 [4,] 3
 [5,] 4
 [6,] 5
 [7,] 6
 [8,] 7
 [9,] 8
[10,] 9
mat1 <- matrix(c(v1,v2),nrow=2)
mat1
[,1] [,2] [,3] [,4] [,5]
[1,]    0    2    4    6 8
[2,]    1    3    5    7 9
mat2 <- matrix(c(v1,v2),ncol=2)
mat1*mat2
Error in mat1 * mat2 : non-conformable arrays
mat3 <- mat1%*%mat2
mat3[1,2]
[1] 160

您会注意到，创建矩阵不是将矢量彼此堆叠。这是因为，除非另行指定，否则矩阵会按列输入数据。这样，如果您创建同一个矩阵但指定了两列，您就无法将这些矩阵相乘。矩阵默认情况下会采用逐单元乘法和除法，而不是矩阵乘法。可以使用 % 来指定矩阵乘法。在这些情况下，执行矩阵乘法后，您可以访问结果矩阵中的第一行和第二列中的单元。

接下来讨论一下数据帧，如清单 4 所示。

下面的脚本首先使用 data.frame 函数创建一个数据帧。您可以添加数据而不指定变量名称。在本示例中，已经指定了变量名称。您会注意到，数据帧可以存储不同类型的数据，而矩阵和矢量仅存储一种类型的数据。

清单 4. R 中的数据帧

复制代码#Dataframes
df <- data.frame(Bool = sample(c(TRUE,FALSE),100,replace=T),Int =
c(1:100),String=sample(LETTERS,100,replace=TRUE))
df$Bool
  [1] FALSE  TRUE  TRUE FALSE  TRUE  TRUE FALSE FALSE FALSE  TRUE  TRUE
FALSE  TRUE  TRUE FALSE  TRUE FALSE  TRUE  TRUE  TRUE FALSE TRUE
 [23] FALSE  TRUE FALSE FALSE FALSE  TRUE FALSE  TRUE FALSE  TRUE FALSE
 TRUE  TRUE  TRUE  TRUE FALSE  TRUE  TRUE  TRUE FALSE  TRUE TRUE
 [45] FALSE FALSE FALSE FALSE  TRUE FALSE FALSE  TRUE FALSE  TRUE  TRUE
FALSE  TRUE  TRUE FALSE  TRUE  TRUE FALSE FALSE FALSE TRUE FALSE
 [67]  TRUE FALSE FALSE FALSE FALSE FALSE  TRUE FALSE  TRUE  TRUE  TRUE
FALSE  TRUE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE  TRUE TRUE
 [89]  TRUE FALSE  TRUE  TRUE FALSE FALSE FALSE FALSE FALSE FALSE  TRUE
TRUE
df[df$Bool,]
Bool Int String
2   TRUE   2 Z
3   TRUE   3 R
5   TRUE   5 K
6   TRUE   6 T
10  TRUE  10 O
11  TRUE  11 U
13  TRUE  13 Y
14  TRUE  14 Z
16  TRUE  16 N
df[df$Bool,3]
[1] Z R K T O U Y Z N H D L B H N L D Z R M I W W I M D A C B R S M Y Y F V B
W P Q Q S M Y K Z J V I
Levels: A B C D E F H I J K L M N O P Q R S T U V W X Y Z
df$String[df$Bool]
[1] Z R K T O U Y Z N H D L B H N L D Z R M I W W I M D A C B R S M Y Y F V B
W P Q Q S M Y K Z J V I
Levels: A B C D E F H I J K L M N O P Q R S T U V W X Y Z
df$NewVar <- c(1:101)
Error in `$<-.data.frame`(`*tmp*`, "NewVar", value = 1:101) :
replacement has 101 rows, data has 100
df$NewVar <- c(1:99)
Error in `$<-.data.frame`(`*tmp*`, "NewVar", value = 1:99) : 
  replacement has 99 rows, data has 100

在此代码中，可以看到使用 $ 运算符调用数据帧变量 Bool 时的输出（第 4 行）。这是一种访问存储在数据帧中的数据的常见轻松方法。接下来，可以使用布尔值或 1 和 0 来访问特定行或列。df[df$Bool,]（第 5 行）输出了 Bool 为 TRUE 的所有行。在此清单中，因为没有指定任何列，所以将输出所有列。

下一次调用指定了第三列，所以仅输出 String 变量的值（第 6 行）。在这之后，可以看到另一种处理方式。$ 运算符用于指定 String 变量，可将该变量视为矢量，然后使用 Bool 值来指定哪些值是输出。因为 String 变量是首先指定的，所以在使用 Bool 选择要输出的内容时不需要指定列（第 7 行）。

显然，数据帧比矢量和矩阵灵活得多。但是，上面的最后两行脚本表明，所有新变量都必须有相同的长度。此要求不是非常严格，但列表（我们现在将讨论）在添加数据时没那么严格。

清单 5 给出了用于创建包含 3 个不同长度矢量的列表的代码。您仍可以使用 $ 运算符访问列表对象，或者使用 [[]]。

关于列表的另一个重要方面是，它能包含其他数据对象。要让一个列表包含其他数据对象，可以向列表添加一个数据帧（第 6 行）。完整的数据帧会被存储，而且仍可以通过我们之前讨论过的方式进行访问（第 8 行）。此外，列表既可以拥有指定的名称也可以没有名称。所有这些在创建函数或包时都很重要。许多不同的例程会创建大量不同类型的数据，这些数据需要通过各种不同方式存储。列表变得有用是因为，所有这些不同类型的数据对象都可以打包在一起返回。

清单 5. R 中的列表

复制代码#Lists
ls <- list(Bool = sample(c(TRUE,FALSE),50,replace=T),Int =
c(1:75),String=sample(LETTERS,100,replace=TRUE))
ls$String
[1] "O" "F" "E" "U" "O" "P" "E" "V" "G" "Z" "T" "F" "T" "C" "J" "P" "G"
"L" "M" "E" "O" "T" "E" "R" "A" "Z" "E" "Y" "N" "Y" "U" "N" "E"
[34] "T" "N" "W" "Z" "D" "S" "R" "P" "C" "H" "G" "N" "Y" "P" "M" "H" "A"
"J" "Y" "C" "C" "Y" "S" "P" "J" "W" "J" "H" "E" "B" "Z" "X" "T"
[67] "B" "M" "I" "P" "V" "I" "H" "M" "D" "I" "T" "L" "J" "F" "M" "B" "J"
"E" "G" "K" "E" "U" "F" "U" "T" "L" "B" "Z" "U" "X" "U" "P" "D"
[100] "W"
Ls[[3]]
[1] "O" "F" "E" "U" "O" "P" "E" "V" "G" "Z" "T" "F" "T" "C" "J" "P" "G"
"L" "M" "E" "O" "T" "E" "R" "A" "Z" "E" "Y" "N" "Y" "U" "N" "E"
[34] "T" "N" "W" "Z" "D" "S" "R" "P" "C" "H" "G" "N" "Y" "P" "M" "H" "A"
"J" "Y" "C" "C" "Y" "S" "P" "J" "W" "J" "H" "E" "B" "Z" "X" "T"
[67] "B" "M" "I" "P" "V" "I" "H" "M" "D" "I" "T" "L" "J" "F" "M" "B" "J"
"E" "G" "K" "E" "U" "F" "U" "T" "L" "B" "Z" "U" "X" "U" "P" "D"
[100] "W"
ls[[4]] <- df
Ls[[4]]
Bool Int String
1   FALSE   1 Q
2    TRUE   2 Z
3    TRUE   3 R
4   FALSE   4 M
5    TRUE   5 K
6    TRUE   6 T
Ls[[4]][2:5,1]
[1]  TRUE  TRUE FALSE TRUE
names(ls)
[1] "Bool"   "Int"    "String" ""

关于 R 中的数据有许多需要学习的地方，但理解如何使用矢量、矩阵、数据帧和列表可以帮助您入门。

3.Rstudio 是 IDE 世界的主宰

在编写 R 脚本时，Rstudio 是您唯一需要使用的 IDE。它将您需要的所有工具都集中在一个地方，而且它在 Sweave 和 R Markdown 的集成使用中不可或缺。这些工具可用于创建包含代码、输出、图表和文本的文档。这些文档的创建是脚本化的，因此是完全可复制的。

RStudio 的另一个不错的工具是 R 调试器，它被集成到 IDE 中。清单 6 展示了该调试器的实际用法。

清单 6. 调试器的实际用法

复制代码testF <- function(x,y){
if(length(x) == length(y)){testF1(x,y)}
}
testF1 <- function(x,y){
print(cbind(x,y))
}
x <- c(1:10)
y <- c(11:21)
testF(x,y)

如果您希望输出 x 和 y，在无法输出它们时您就会很失望。假如您无法自行确定原因，可以向控制台输入以下命令来启动调试器（参见图 1）。

1 2	复制代码> debug(testF) > testF(x,y)

图 1. 调试器

现在您可以访问调试器，还可以对函数单步调试或进入下一行，如图 2 所示。

图 2. 对函数执行单步调试

此时还会打开一个 Traceback 窗格，以及一个特定的调试窗格（参见图 3）。

图 3. 调试窗格

无可否认，此示例不是特别重要，但重要的是，您可以看到 RStudio 确实是解决您的 R 脚本所需的一站式场所。

4.如何自行应用

R 非常棒，但您常常会遇到使用 for 循环导致脚本长时间运行的情形。清单 7 给出了这样一段脚本的示例。基本上讲，这是一个包含 1,000,000 条记录的庞大数据集，需要检查这些记录，并根据两个变量的值来为另一个变量赋值。

清单 7. 一个 for 循环示例

复制代码df <- data.frame(Strings=sample(c("This","That","The Other"),1000000,replace=T),
Values=sample(c(0:4),1000000,replace=T),Result =
rep("DA",1000000))
 
for(i in 1:length(df[,1])){
if(df$Strings[i] == "This"){
if(df$Values[i] > 2){
df$Results[i] <- "CP"
next
}else{
df$Results[i] <- "QM"
}
}else if(df$Strings[i] == "That"){
df$Results[i] <- "BS"
next
}else if(df$Strings[i] == "The Other"){
if(df$Values[i] == 4){
df$Results[i] <- "FP"
next
}else{
df$Results[i] <- "DT"
}
}
}

注意嵌套的 if 语句（第 7-10 行）。for 循环中的嵌套可能会打乱 R 中的运转。根据您的硬件，这个 for 循环可能花一整晚才能运行完。

这时 apply 系列函数就可以派上用场。a``pply 和所有类似函数：lapply、mapply 等函数将一个函数应用于一个矩阵型对象的行或列。a``pply 有两种重要用途，其中一种是加快速度。

清单 8 给出了 apply 函数的一个示例。函数 applyF 获取之前的 for 循环并将它转换为一个函数。然后，可将该函数应用于数据帧中的每行，并将返回值存储为结果中的一个列表。通过一次快速转换，可以将具有正确格式的结果存储在数据帧变量中。这个过程执行的任务等同于 for 循环的任务，但只需几秒即可完成。

清单 8. apply 函数

复制代码applyF <- function(vex){
if(vex[1] == "This"){
if(vex[2] > 2){
return("CP")
}else{
return("QM")
}
}else if(vex[1] == "That"){
return("BS")
}else if(vex[1] == "The Other"){
if(vex[2] == 4){
return("FP")
}else{
return("DT")
}
}
}
results <- apply(df,1,applyF)
df$Result <- factor(unlist(results))

当然，几秒与几小时是有很大差别的。清单 9 给出了一个快得多的结果。

清单 9. 更快的结果

复制代码df2 <- data.frame(A=sample(as.character(c(1:100)),1000,replace=T),B=sample(as.
character(c(1:100)),1000,replace=T),
C=sample(as.character(c(1:100)),1000,replace=T),D=sample(as.character(c
(1:100)),1000,replace=T),
E=sample(as.character(c(1:100)),1000,replace=T),F=sample(as.character(c
(1:100)),1000,replace=T))
df2[,1:6] <- apply(df2,1,as.numeric)

apply 函数的另一个好处是它简化了代码。此外，有一个由存储为字符的整数组成的数据帧。您可通过多种方法转换每个变量。可以使用 apply 和 as.numeric 函数将它们全部更改为数字。然后可以通过很短的一行代码执行一次大规模转换。最后一个示例是 apply 的一种更常见用法：

复制代码vars <- apply(df2,2,var)
vars
       A        B        C        D        E        F
831.8953 810.2209 806.5781 854.8382 820.8769 866.8276

如果您想知道数据帧中每个变量的方差，只需指定该数据帧、索引（在本例中，“2”表示列）和该函数。输出结果表明，您现在拥有每列的方差。如果您想成为高效的 R 用户，了解 apply 和它的相关函数就非常重要。

5.基础图形很棒，ggplot2 也很棒

R 使用基础包创建了非常有用的图形，但在掌握 ggplot2 之后，您的图形才会真正引人注目。让我们看看使用基础图形和 ggplot2 的一些示例。

清单 10 中的脚本生成了图 4 和图 5 所示的图像。

清单 10. 一个基础包结果与 ggplot2 结果

复制代码library(ggplot2)
data(list=esoph)
barplot(xtabs(esoph$ncases~esoph$tobg+esoph$alcgp),beside=TRUE,col=rainbow(4)
,
main="Number of Cancer cases by Alcohol and Tobacco Use
Groups",xlab="Alcohol Use Group",ylab="Cases")
legend("topright",legend=levels(esoph$tobgp),fill=rainbow(4),title="Tobacco
Use Group")
ggplot(esoph,aes(x=alcgp,y=ncases,fill=tobgp))+
geom_bar(position="dodge",stat="identity")+
labs(fill="Tobacco Use Group",x="Acohol Use Group",y="Cases",title="Number
 of Cancer cases by Alcohol and Tobacco Use Groups")

图 4. 基础包结果

图 5. ggplot2 结果

二者都很不错。它们都提供了必要的信息，但 ggplot2 版本更美观一些。

让我们看看另一个示例。清单 11 中的脚本比较了德国和瑞士股票，同时显示了基础包结果和 ggplot2 结果。

清单 11. 一个展示基础包结果和 ggplot2 结果的股票示例

复制代码EUst <- EuStockMarkets
plot(EUst[,1],ylab="Euros",main="German and Swiss Stock Time Series
Comparison")
lines(EUst[,2],col="Blue")
legend("topleft",legend=c("German","Swiss"),col=c("Black","Blue"),lty=1)
df <- data.frame(Year = as.double(time(EUst)),German=
as.double(EUst[,1]),Swiss = as.double(EUst[,2]))
ggplot(df,aes(x=Year))+
geom_line(aes(y=df$Swiss,col="Swiss"))+
geom_line(aes(y=df$German,col="German"))+
labs(color="",y="Euros",title="German and Swiss Stock Time Series
 Comparison")

图 6. 使用基础包的德国和瑞士股票

图 7. 使用 ggplot2 的德国和瑞士股票

使用基础图形没什么不好，它们比一些与 R 类似的语言创建的图形还要好，但 ggplot2 版本更美观一些。此外，使用 ggplot2 创建图形所采用的方式比使用基础包创建图形更直观。

最后一个示例（清单 12）展示了 ggplot2 如何采用比基础包更好的方式显示数据（参见图 8 和图 9）。

这是得到广泛使用的经典的鸢尾花数据集。在这里可以看到基于这些花的物理属性的 k 均值聚类，而不是种类分类的聚类。有 3 个种类，所以您有 3 个聚类。

清单 12. ggplot2 的强大功能

复制代码iris <- iris
wssplot <- function(data, nc=15, seed=1234){
wss <- (nrow(data)-1)*sum(apply(data,2,var))
for (i in 2:nc){
set.seed(seed)
wss[i] <- sum(kmeans(data, centers=i)$withinss)}
plot(1:nc, wss, type="b", xlab="Number of Clusters",
ylab="Within groups sum of squares")}
fit <- kmeans(iris[,1:4], 3)
iris$Cluster <- fit$cluster
par(mfrow=c(1,2))
plot(iris$Sepal.Length,iris$Sepal.Width,col=iris$Cluster,pch=16,xlab="Sepal
Length",ylab="Sepal Width",
main="Iris Data Colored by Cluster")
legend("topright",legend=c(1:3),col=c(1:3),pch=16)
plot(iris$Sepal.Length,iris$Sepal.Width,col=iris$Species,pch=16,xlab="Sepal
Length",ylab="Sepal Width",
main="Iris Data Colored by Species")
legend("topright",legend=levels(iris$Species),col=c(1:3),pch=16)
par(mfrow=c(1,1))
ggplot(iris,aes(x=Sepal.Length,y=Sepal.Width))+
geom_point(aes(colour=Species))+
facet_grid(Cluster~.)+
labs(x="Sepal Length",y="Sepal Width",title="Iris Species-Cluster
 Relationship")

基础包的图形表明，山鸢尾种类与该聚类一致。该图形还表明，该聚类没有正确识别杂色鸢尾和维吉尼亚鸢尾，但它仅告诉我们上述这些内容。

图 8. 使用基础包的鸢尾花数据

ggplot2 图堆叠了这些聚类，然后根据种类对各个点着色。杂色鸢尾与维吉尼亚鸢尾聚类种类的关系更容易识别，而且您还可以开始查看为什么可能存在这种关系。分类到错误种类的维吉尼亚鸢尾的萼片长度比其他维吉尼亚鸢尾更短。这可能是很好的解释。

图 9. 使用 ggplot2 的鸢尾花数据

在您不是很关心外观时，基础图形非常适合用于实际分析数据。在向外界显示数据时，了解 ggplot2 有助于让您的数据更加显眼。

6.R 正是您想要或需要的工具

R 可以完成很多您可能留给一种不太受数据分析驱动的语言来完成的事情。清单 13 是采用一种更普通的脚本编写方式来使用 R 的示例。

此查询是使用 HTTP 来执行的。httr 包有一个仅用作标准 HTTP GET 请求的 GET 函数。Google Places API 拥有 HTTP 功能，其中一个特定 URL 可通过 GET 请求发起查询。该 URL 从第 4 和第 5 行开始（没有包含我的密钥，但您可以从 Google 获取您的密钥）。然后，在 qgoogle 函数内，在第 13-22 行构建了这个特定的查询，执行了 GET 请求，并解析了结果。

清单 13. R 的强大脚本功能

复制代码library('httr')
library('rjson')
library('stringr')
preamble <- 'https://maps.googleapis.com/maps/api/place/textsearch/json?'
key <- 'key=yourkeyhere’
for(i in 1:length(dataset[,1])) {
dataset[i,] <- tryCatch(qgoogle(dataset[i,]),
    error = function(err){
        print(paste("ERROR: ",err))
    })
}
qgoogle <- function(vex){
name <- str_replace_all(vex$BUSINESS," ","+")
line_two <- str_replace_all(vex$BUSINESS2," ","+")
city <- str_replace_all(vex$CITY," ","+")
addr <- str_replace_all(vex$CLEANADDRE," ","+")
if(line_two == ""){
query <- paste(name,addr,city,state,sep="+")
}else{
query <- paste(name,line_two,addr,city,state,sep="+")
}
url <- paste(preamble,'&',"query=",query,'&',key,sep = "")
json.obj <- GET(url)
content <- content(json.obj)
if(content$status != "ZERO_RESULTS") {
vex$DATA <- TRUE
vex$DATA.WITH.ADDRESS <- TRUE
vex$NAME <- content$results[[1]]$name
vex$ADDR <- content$results[[1]]$formatted_address
vex$LAT <- content$results[[1]]$geometry$location$lat
vex$LONG <- content$results[[1]]$geometry$location$lng
if(length(content$results[[1]]$types) != 0){
vex$TYPE <- content$results[[1]]$types[[1]]
}
if(length(content$results[[1]]$permanently_closed) != 0){
vex$CLOSED <- "Permanently Closed"
}
  } else {
vex$NAME <- NA
vex$ADDR <- NA
vex$LAT <- NA
vex$LONG <- NA
vex$TYPE <- NA
vex$CLOSED <- NA
vex$DATA <- FALSE
vex$DATA.WITH.ADDRESS <- FALSE
}
return(vex)
}

R 不是其他脚本语言的完美替代，但是，上面的示例表明，R 可以执行其他任何脚本语言可以执行的许多相同任务。

7.Rcpp 很不错

Rcpp 是一个包，可用于将 C++ 函数导入到 R 脚本中。下面给出了 C++ 中适用于 R 中的函数的标准示例：

复制代码#include <Rcpp.h>
using namespace Rcpp;
// [[Rcpp::export]]
int timesTwo(int x) {
return x * 2;
}

可以在 R 中创建此示例，但这里的重点是展示如何非常轻松地创建一个 C++ 函数，然后将该函数迁移到 R 环境中。此外，RStudio 让此过程的管理变得更容易。如果您需要实现一个非常不错的功能，并且可以使用 C++ 实现它，那么您可以轻松地将此功能集成到您想要的任何 R 脚本中。

结束语

本文仅触及了 R 的功能和您在使用它时需要了解的知识的皮毛。这 7 个技巧非常重要，在您踏上使用 R 的旅程时，它们可以帮助您节省一些时间和消除一些麻烦。祝开发脚本愉快。

漫画：什么是八皇后问题？

发表于 2018-04-10

————— 第二天 —————

题目是什么意思呢？

国际象棋中的皇后，可以横向、纵向、斜向移动。如何在一个8X8的棋盘上放置8个皇后，使得任意两个皇后都不在同一条横线、竖线、斜线方向上？

让我们来举个栗子，下图的绿色格子是一个皇后在棋盘上的“封锁范围”，其他皇后不得放置在这些格子：

下图的绿色格子是两个皇后在棋盘上的“封锁范围”，其他皇后不得放置在这些格子：

那么，如何遵循规则，同时放置这8个皇后呢？让我们来看看小灰的回答。

————————————

什么是八皇后问题？

八皇后问题是一个古老的问题，于1848年由一位国际象棋棋手提出：在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，如何求解？

以高斯为代表的许多数学家先后研究过这个问题。后来，当计算机问世，通过计算机程序的运算可以轻松解出这个问题。

如何解决八皇后问题？

所谓递归回溯，本质上是一种枚举法。这种方法从棋盘的第一行开始尝试摆放第一个皇后，摆放成功后，递归一层，再遵循规则在棋盘第二行来摆放第二个皇后。如果当前位置无法摆放，则向右移动一格再次尝试，如果摆放成功，则继续递归一层，摆放第三个皇后……

如果某一层看遍了所有格子，都无法成功摆放，则回溯到上一个皇后，让上一个皇后右移一格，再进行递归。如果八个皇后都摆放完毕且符合规则，那么就得到了其中一种正确的解法。

说起来有些抽象，我们来看一看递归回溯的详细过程。

1.第一层递归，尝试在第一行摆放第一个皇后：

2.第二层递归，尝试在第二行摆放第二个皇后（前两格被第一个皇后封锁，只能落在第三格）：

3.第三层递归，尝试在第三行摆放第三个皇后（前四格被第一第二个皇后封锁，只能落在第五格）：

4.第四层递归，尝试在第四行摆放第四个皇后（第一格被第二个皇后封锁，只能落在第二格）：

5.第五层递归，尝试在第五行摆放第五个皇后（前三格被前面的皇后封锁，只能落在第四格）：

6.由于所有格子都“绿了”，第六行已经没办法摆放皇后，于是进行回溯，重新摆放第五个皇后到第八格。：

7.第六行仍然没有办法摆放皇后，第五行也已经尝试遍了，于是回溯到第四行，重新摆放第四个皇后到第七格。：

8.继续摆放第五个皇后，以此类推……

八皇后问题的代码实现？

解决八皇后问题，可以分为两个层面：

1.找出第一种正确摆放方式，也就是深度优先遍历。

2.找出全部的正确摆放方式，也就是广度优先遍历。

由于篇幅优先，我们本篇只介绍如何找出第一种正确摆放方式。

在研究代码实现的时候，我们需要解决几个问题：

1.国际象棋的棋盘如何表示？

很简单，用一个长度是8的二维数组来表示即可。

由于这里使用的是int数组，int的初始值是0，代表没有落子。当有皇后放置的时候，对应的元素值改为1。

在这里，二维数组的第一个维度代表横坐标，第二个维度代表纵坐标，并且从0开始。比如chessBoard[3][4]代表的是棋盘第四行第五列格子的状态。

2.如何判断皇后的落点是否合规？

定义一个check方法，传入新皇后的落点，通过纵向和斜向是否存在其他皇后来判断是否合规。

3.如何进行递归回溯？

递归回溯是本算法的核心，代码逻辑有些复杂

4.如何输出结果？

这个问题很简单，直接遍历二维数组并输出就可以。

5.如何把这些方法串起来？

在main函数里分三步来调用：

第一步：初始化

第二步：递归摆放皇后

第三步：最后输出结果。

其中Queen8是整个类的名字。

最终输出如下：

10000000

00001000

00000001

00000100

00100000

00000010

01000000

00010000

几点补充：

1.由于篇幅原因，这一篇只讲了如何找出第一种正确的八皇后摆放。大家如果有兴趣，可以对文中的代码稍作改动，实现找出所有八皇后摆放的代码。

2.本漫画纯属娱乐，还请大家尽量珍惜当下的工作，切勿模仿小灰的行为哦。

—————END—————

喜欢本文的朋友们，欢迎长按下图关注订阅号程序员小灰，收看更多精彩内容

本文转载自: 掘金

开发者博客 – 和开发相关的这里全都有

前言

Jenkins安装

下载jenkins

初始化密码

选择插件

配置用户名和密码

全局配置

安全配置

新建任务

构建脚本

测试脚本

gitee集成WebHooks

添加SSH公匙

配置WebHooks

修改脚本

测试

代码下载

推荐文章

1.1 Context 类中的 getSharedPreferences()方法：

1.2 Activity 类中的 getPreferences()方法：

1.3 PreferenceManager 类中的 getDefaultSharedPreferences()方法：

Context的getSharedPreferences：

SharedPreferencesImpl对象

SharedPreferences的内部类Editor

commit方法和apply方法的不同

古老的日期时间接口

表示时刻信息的 Date

描述年历的 Calendar

DateFormat 格式化转换

创建方法

提供的方法

一个小Demo

多次read和write

EFD_NONBLOCK标志位的作用

EFD_SEMAPHORE标志位的作用

使用 Maven 创建项目

创建实体类

创建 Controller

让应用跑起来

构建可执行的 jar

做一些简单的测试

总结

定义

我们来举例一个现实生活中的例子

树的术语定义

术语汇总

二叉树

我们来写一个二叉树

深度优先搜索（Depth-First Search，DFS）

前序遍历

中序遍历

后序遍历

广度优先搜索（BFS）

二叉搜索树

插入：向我们的树添加新的结点

搜索结点

删除：移除和重新组织树

一个没有孩子的节点（叶节点） 。

仅有一个孩子（左或右孩子）的结点。

有两个孩子的节点。

代码下载：

推荐文章

1. interface{}之对象转型坑

2. interface{}之nil坑

3. 总结和引用

R 语言入门的 7 个技巧

1.为此问题有一个适用包

清单 1. 一个 R 包示例

2.如何搭建数据结构

数据结构用例

清单 2. R 中的矢量

清单 3. R 中的矩阵

清单 4. R 中的数据帧

清单 5. R 中的列表

3.Rstudio 是 IDE 世界的主宰

清单 6. 调试器的实际用法

图 1. 调试器

图 2. 对函数执行单步调试

图 3. 调试窗格

4.如何自行应用

一个没有孩子的节点（叶节点）。

2. interface{}之`nil`坑