机器学习算法全栈工程师

公众号：
Jeemy110

功能介绍
机器学习、深度学习、数据挖掘等人工智能领域的技术实战干货文章

经典文章推荐：


快来操纵你的GPU| CUDA编程入门极简教程

2006年，NVIDIA公司发布了CUDA（http://docs.nvidia.com/cuda/），CUDA是建立在NVIDIA的CPUs上的一个通用并行计算平台和编程模型，基于CUDA编程可以利用GPUs的并行计算引擎来更加高效地解决比较复杂的计算难题。近年来，GPU最成功的一个应用就是深度学习领域，基于GPU的并行计算已经成为训练深度学习模型的标配。目前，最新的CUDA版本为CUDA 9。

GPU并不是一个独立运行的计算平台，而需要与CPU协同工作，可以看成是CPU的协处理器，因此当我们在说GPU并行计算时，其实是指的基于CPU+GPU的异构计算架构。在异构计算架构中，GPU与CPU通过PCIe总线连接在一起来协同工作，CPU所在位置称为为主机端（host），而GPU所在位置称为设备端（device），如下图所示。

基于CPU+GPU的异构计算. 来源：Preofessional CUDA® C Programming

可以看到GPU包括更多的运算核心，其特别适合数据并行的计算密集型任务，如大型矩阵运算，而CPU的运算核心较少，但是其可以实现复杂的逻辑运算，因此其适合控制密集型任务。另外，CPU上的线程是重量级的，上下文切换开销大，但是GPU由于存在很多核心，其线程是轻量级的。因此，基于CPU+GPU的异构计算平台可以优势互补，CPU负责处理逻辑复杂的串行程序，而GPU重点处理数据密集型的并行计算程序，从而发挥最大功效。

基于CPU+GPU的异构计算应用执行逻辑. 来源：Preofessional CUDA® C Programming

CUDA是NVIDIA公司所开发的GPU编程模型，它提供了GPU编程的简易接口，基于CUDA编程可以构建基于GPU计算的应用程序。CUDA提供了对其它编程语言的支持，如C/C++，Python，Fortran等语言，这里我们选择CUDA C/C++接口对CUDA编程进行讲解。开发平台为Windows 10 + VS 2013，Windows系统下的CUDA安装教程可以参考这里http://docs.nvidia.com/cuda/cuda ... -windows/index.html

更多点击链接

深度学习入门

引言

       近几年来人工智能越来越火，大家都已经知道了AlphaGo的威力，然而在其背后，从技术层面来说，深度学习功不可没。那么深度学习到底是什么，其与传统的机器学习之间又有什么样的关联。对于想入坑深度学习的同学，又该从哪些方面入手。这就是本文要回答的问题。

深度学习的提出

       先从深度学习的提出开始说起，深度学习的概念是由Hinton在2006年提出，他当时首次提出了深度信念网络(DBN)，相比之前，他采用无监督方式逐层训练深层网络，在深层网络训练中取得了跨越式的进展。虽然称为是深度学习，但其实是深层神经网络。神经网络或者说人工神经网络早在上个世纪都已经提出，但是在Hinton之前，很少人尝试去训练深层神经网络，也当然没有深度的概念了。2006年可以说是深度学习的元年，但是对于神经网络来说，虽然不是元年，但确是其振兴的又一个重要转折点。神经网络之前经历了跌宕的发展，但是从此时之后，它重回时代的舞台。

深度学习的兴起

这里有必要谈一下深度学习的兴起原因。为什么是深度学习或者说是深层神经网络成为热点。神经网络从生物相似性来说，应该是比较理想的人工智能实现载体，因为其与生物的神经元结构是类似的。通过层与层之间的连接或者传递，可以实现复杂模式的学习。早在上个世纪，就已经证明了单隐含层的神经网络就可以实现任何非线性模式的拟合。因此，经典的BP神经网络也大多采用单个隐含层，按理说可以拟合任何模型。不过这毕竟是理想，现实并非如此，因为找到这个优化点就是个大难题。那么人们可能会尝试增加隐含层的个数即深层神经网络，从直观上讲，深层神经网络要由于增加了隐含层，表达力会更强，而且应该在实践中比浅层神经网络的效果要好。但是在真实情境中却并不是这样，因为在当时深层神经网络的训练难度要大，这与算法、数据以及计算力都有关系。比如，我们知道神经网络的初始参数对网络训练可能会影响很大，较糟糕的初始参数可能会导致网络很难收敛，对深层神经网络这个效应更大，而Hinton提出无监督预训练方式也就是解决网络的初始参数问题，无监督预训练的原理是他假定一个好的特征表达，后面的输出层总是可以重构出前面的输入层。还有如果你的训练样本很少，也很难训练出一个很好的深度模型。而目前深度学习之所以热，就是现在出现了新技术来解决深层神经网络的难训练问题。这主要归功于以下三个方面：

       (1) 计算力的提高：大家都知道的摩尔定律，以及GPU，FPGA，ASIC等在深度学习的应用；

       (2) 大数据时代的到来：我们有了更多的训练样本；

       (3) 算法的创新：启发式的参数初始化，新的激活函数、优化方法以及网络架构等；

       深度学习的兴起与这三个方面紧密相关，其实更重要的是前两个方面，因为深度学习的核心算法相比之前并没有太大的变革，也难怪有人称为深度学习为“暴力计算型”人工智能，有了更多的训练数据，加上强大的计算能力我们完全可以拟合更好的模型，之前是理论上可以实现，现在是实践上做得越来越好。值得一提的是，深度学习是一个发展迅速的领域，尤其是近几年更是暴热，当年Hinton提出的深度信念网络现在也被遗忘在角落里了，也许这就是技术变革吧。

深度学习与机器学习

       由于之前神经网络也是归到机器学习的范畴，毕竟是表征学习（Representation learning），还是在机器学习的定义中，所以从这个角度来看，深度学习也是在机器学习之下的，但是由于时势造英雄，只不过单独被拎出来罢了，而现在我们说机器学习可能大多是指传统的机器学习方法如决策树及支持向量机等，或者说是除了神经网络之外的算法，不过从本质上讲，机器学习应该囊括了深度学习，至少现在还是这样。

深度学习如何入门

       如果要入门深度学习，掌握了神经网络基础之后，可以先学习深度学习两个最基本的模型：卷积神经网络(CNnsorflow以及Facebook的Pytorch等等，大家可以选择某个框架从简单的N)和递归神经网络(RNN)。前者主要用于计算机视觉(CV),后者主要用于自然语言处理(NLP)。其实两种模型也早在上个世纪被提出，不过加上深度，两个模型分别在两个不同的领域取得重大进展。然后还要学习一下深度学习模型的训练方法，即相关梯度下降法（SGD）以及相关变体，值得注意的是SGD方法需要计算梯度，这不得牵扯到经典的BP算法，还有一些自动求导的方法，这些也只很重要的方面。接着要开始学习深度学习的框架，如Google的Tedemo开始搭建模型，这对学习理论是有裨益的。作为一个迅猛发展的领域，最重要的是要开始跟进一些最新的paper，多学习一些新的模型及架构。下面我们来介绍CV中使用最多的CNN模型。

更多点击链接链接

机器学习该如何入门

引言

　　可能你对这个名字叫“机器学习”的家伙不是特别的了解，但是相信用过iPhone的同学都知道iPhone的语音助手Siri，它能帮你打电话，查看天气等等；相信大家尤其是美女童鞋都用过美颜相机，它能自动化的给我们拍出更漂亮的照片；逛京东淘宝的时候，细心的童鞋应该也会发现它们会有一个栏目“猜你喜欢”；最近异军突起的新闻客户端软件今日头条，它们就是会根据分析你的日常喜好给每个人推荐不同的新闻……没错，这些功能背后的核心就是今天要介绍的主题：机器学习。

什么是机器学习

　　对于这个问题的解释，说实话我很有压力，因为在分享篇文章之前就有朋友告诉我，这个百度上一搜一大片，还需要你讲吗？但是，我觉得并非如此。正如同一千个读者眼里有一千个林黛玉一样，我解释的当然是我个人自从读研到工作这么多年对机器学习的学习到应用过程的独特见解。

　　首先我们看下图了解一下机器学习在AI（Artificial Intelligence 人工智能）领域的地位。在图中，我们可以看到，机器学习是人工智能的一个子领域。而现在火的不要不要的 深度学习 其实是机器学习的一个子分支。

机器学习在人工智能中的地位

那么到底什么才是真正的机器学习呢？在这里我将对比我和学术界大神的解释：

• 大神的解释
  　　机器学习研究的是计算机怎样模拟人类的学习行为，以获取新的知识或技能，并重新组织已有的知识结构使之不断改善自身。简单一点说，就是计算机从数据中学习出规律和模式，以应用在新数据上做预测的任务。
• 我的解释
  　　传统的机器学习主要做的事情就是利用统计学的基本观点，利用要学习的问题的历史样本数据的分布对总体样本分布进行估计。分析数据大致特性建立数学分布模型，并利用最优化的知识对模型的参数进行调优学习，使得最终的学习模型能够对已知样本进行很好的模拟与估计。最终利用学习好的模型对未知标签的样本进行预测和估计的过程。
  　　但是越说越觉得机器学习有距离感，云里雾里高深莫测，我们不是专家，但说起算有一些从业经验，做过一些项目在实际数据上应用机器学习。这一篇就我们的经验和各位同仁的分享，总结一些对于初学者入门有帮助的方法和对进阶有用的资料。
  
  

机器学习的基本问题

　　对于机器学习中的基本问题，我们将从以下几个角度进行讲解：机器学习的特点；机器学习的对象；机器学习的分类；机器学习的要素；模型的评估与选择。

机器学习的特点

机器学习主要特点如下：

• 机器学习以数据为研究对象，是数据驱动的科学；
• 机器学习的目的是对数据进行预测与分析；
• 机器学习以模型方法为中心，利用统计学习的方法构建模型并且利用模型对未知数据进行预测和分析；
• 统计学习是概率论、统计学、信息论、计算理论、最优化理论以及计算机科学等多领域的交叉学科，并且逐渐形成自己独自的理论体系和方法论。
  
  

机器学习的一般训练过程
机器学习的对象

　　机器学习研究的对象是多维向量空间的数据。它从各种不同类型的数据（数字，文本，图像，音频，视频）出发，提取数据的特征，抽象出数据的模型，发现数据中的知识，又回到数据的分析与预测中去。

机器学习的分类

　　对于机器学习的分类，绝大多数人只简单的分为有监督学习和无监督学习这两类。严格意义上来讲应该分为四大类：有监督学习、无监督学习、半监督学习、强化学习。下面对这四种学习做一下简要的介绍：

• 有监督学习
  　　有监督学习是指进行训练的数据包含两部分信息：特征向量 + 类别标签。也就是说，他们在训练的时候每一个数据向量所属的类别是事先知道的。在设计学习算法的时候，学习调整参数的过程会根据类标进行调整，类似于学习的过程中被监督了一样，而不是漫无目标地去学习，故此得名。
• 无监督学习
  　　相对于有监督而言，无监督方法的训练数据没有类标，只有特征向量。甚至很多时候我们都不知道总共的类别有多少个。因此，无监督学习就不叫做分类，而往往叫做聚类。就是采用一定的算法，把特征性质相近的样本聚在一起成为一类。
• 半监督学习
  　　半监督学习是一种结合有监督学习和无监督学习的一种学习方式。它是近年来研究的热点，原因是在真正的模型建立的过程中，往往有类标的数据很少，而绝大多数的数据样本是没有确定类标的。这时候，我们无法直接应用有监督的学习方法进行模型的训练，因为有监督学习算法在有类标数据很少的情况下学习的效果往往很差。但是，我们也不能直接利用无监督学习的方式进行学习，因为这样，我们就没有充分的利用那些已给出的类标的有用信息。
  
  

更多链接

Tensorflow快速入门

引言

实践深度学习肯定要至少学习并掌握一个深度学习框架。这里我们介绍一个最流行的深度学习框架：Tensorflow。Tensorflow是谷歌公司在2015年9月开源的一个深度学习框架。虽然我们称Tensorflow为一种深度学习框架，但是看看官网：

可以看到，从功能上看，Tensorflow定义为专为机器智能打造的开源软件库。而从内部机制上，Tensorflow定义为一个使用数据流图进行数值计算的开源软件库。这说明Tensorflow的功能远不是只应用在深度学习领域，但是通常我们还是用Tensorflow来搭建深度学习模型。其他流行的深度学习框架也有很多，如PyTorch, MXnet, Theano，Caffe等，还有根据这些框架衍生出来的高级深度学习框架，如Keras, TFLearn, TensorLayer等。其实各个深度学习框架都有自己独特的优势，网上也有针对各个框架的对比。但是，不管在学术界还是在工业界，Tensorflow绝对是学习深度学习的一个较好的选择，这里谈一下其优势：

1.平台支持性良好，无论是Windows, Linux, 和macOS等系统，还是IOS和Android；
2提供简单且灵活的Python API接口，内部使用C++进行优化；
3丰富的算子，可以很容易搭建各种深度学习模型，如CNN和RNN模型；
4提供可视化工具TensorBoard，这个是TF独有的优势；
5支持CPU和GPU，支持分布式多机多卡训练；


总之，TF的优势还是挺多的，基本上的需求都可以满足，毕竟背后有强大的谷歌大佬在维护。接下来，就从入门TF开始吧。

更多点击链接

详解数据挖掘与机器学习的区别与联系



0、为什么写这篇博文

　　最近有很多刚入门AI领域的小伙伴问我：数据挖掘与机器学习之间的区别与联系。为了不每次都给他们长篇大论的解释，故此在网上整理了一些资料，整理成此篇文章，下次谁问我直接就给他发个链接就好了。

　　本篇文章主要阐述我个人在数据挖掘、机器学习等方面的学习心得，并搜集了网上的一些权威解释，或许不太全面，但应该会对绝大多数入门者有一个直观地解释。

　　本文主要参照周志华老师的：机器学习与数据挖掘 一文。有兴趣的可以自行百度，其文对人工智能、数据挖掘、机器学习等演变历程，有详细介绍。

1、概念定义

首先，第一步，我们对机器学习和数据挖掘的定义做一下总结，看看大家有没有一点体会：

　　机器学习：广泛的定义为 “利用经验来改善计算机系统的自身性能。”，事实上，由于“经验”在计算机系统中主要是以数据的形式存在的,因此机器学习需要设法对数据进行分析,这就使得它逐渐成为智能数据分析技术的创新源之一,并且为此而受到越来越多的关注。

　　数据挖掘：一种解释是“识别出巨量数据中有效的、新颖的、潜在有用的、最终可理解的模式的非平凡过程”，顾名思义，数据挖掘就是试图从海量数据中找出有用的知识。

2、关系与区别2.1 关系

　　 数据挖掘可以认为是数据库技术与机器学习的交叉，它利用数据库技术来管理海量的数据，并利用机器学习和统计分析来进行数据分析。其关系如下图：

　　数据挖掘受到了很多学科领域的影响,其中数据库、机器学习、统计学无疑影响最大。粗糙地说,数据库提供数据管理技术,机器学习和统计学提供数据分析技术。由于统计学界往往醉心于理论的优美而忽视实际的效用,因此,统计学界提供的很多技术通常都要在机器学习界进一步研究,变成有效的机器学习算法之后才能再进入数据挖掘领域。从这个意义上说,统计学主要是通过机器学习来对数据挖掘发挥影响,而机器学习和数据库则是数据挖掘的两大支撑技术。

2.2 区别

　　 数据挖掘并非只是机器学习在工业上的简单应用，他们之间至少包含如下两点重要区别：

• 传统的机器学习研究并不把海量数据作为处理对象，因此，数据挖掘必须对这些技术和算法进行专门的、不简单的改造。
• 作为一个独立的学科，数据挖掘也有其独特的东西，即：关联分析。简单地说,关联分析就是希望从数据中找出“买尿布的人很可能会买啤酒”这样看起来匪夷所思但可能很有意义的模式。
  
  

链接

全面直观认识深度神经网络


1.深度学习的精准定义


一类通过多层非线性变换对高复杂性数据建模算法的集合。它的两个非常重要的特征是多层性和非线性。俗称多层非线性变换。所以深度学习要去线性化。

为什么呢？因为线性模型存在局限性，任意线性模型得到组合仍然还是线性模型。所以只要通过线性变换，任意层的全连接神经网络和单层神经网络模型的表达能力没有任何区别，而且他们都是线性模型，线性模型解决问题的能力是有限的。


2.激活函数实现去线性化


       每个神经元（也就是神经网络上的节点）的输出通过一个非线性函数，那么整个神经网络的模型也就不再是线性的了，这个非线性函数就是激活函数。

tensorflow常见的激活函数有:
tf.nn.relu
tf.sigmoid
tf.tanh
tensorflow 也支持自定义激活函数。

带激活函数的前向传播算法：
a = tf.nn.relu(tf.matmul(x, w1) + biases1)
y = tf.nn.relu(tf.matmul(a, w2) + biases2)



3.单层神经网络解决不了的问题
事实上，一个单极网络可以将平面划分为两部分，用多个单极网络组合在一起，并用其中的一个区综合其他单极网络的结果，就可以构造出一个两极神经网络。

4.组合特征提取


深度神经网络具有组合特征提取的功能，这个特征对于不易提取特征向量的问题（比如图片识别和语音识别等）有很大的帮助。隐藏层的主要作用也就是隐藏层节点可以被认为代表了从输入特征中抽取更高纬度的特征。

5.损失函数


损失函数用于评价模型的效果。分类问题使用最广泛的损失函数是交叉熵。

交叉熵：
        刻画两个概率分布的距离，也就是说交叉熵越小两个概率分布越接近。

交叉熵的数学定义是：
        其用来衡量在给定真实分布下，使用非真实分布所指定的策略消除系统不确定性所需付出的努力的大小。

神经网络的输出不一定是概率模型，可以使用Softmat回归将神经网络的前向传播的结果变成概率分布。

代码实例：
cross_entropy = -tf.reduce_mean(
        y_ * tf.log(tf.clip_by_value(y, 1e-10, 1.0)

        但是交叉熵一般会和softmax回归一起使用，所以会使用tf.nn.softm
cross_entropy=
    tf.nn.softmax_cross_entropy_with_logits(y,y_)
y代表原始神经网络的输出结果，而y_给出了标准答案。

在只有一个正确答案的分类问题中，Tensorflow提供了函数：
tf.nn.sparse_softmax_cross_entropy_with_logits
来加快计算过程。

回归问题常用的损失函数是均方误差。均方误差是指各数据偏离真实值的距离平方和的平均数。


6.神经网络的优化算法


梯度下降算法主要用于优化单个参数的取值，而反向传播算法则给出了一个高效的方式在所有参数上使用梯度下降算法，从而使神经网络模型在训练数据集上的损失函数尽可能的小。

反向传播算法是训练神经网络的核心算法。它可以根据定义好的损失函数优化神经网络中参数的取值，从而使神经网络模型在训练数据集上的损失函数达到一个较小的值。

神经网络模型中参数的优化过程直接决定了模型的质量。


7.什么是梯度和学习率

梯度：
由导数的概念，对点x0的导数反应了函数在点x0出的瞬时变化速率，或者叫做点x0出的斜度。推广到多维函数中，就有了梯度的概念，梯度是一个向量的组合，反应了多维图形中变化速率最快的反向。

学习率：
每次参数移动的幅度。


更多点击链接

Isolation Forest算法原理详解

iTree的构造

   提到森林，自然少不了树，毕竟森林都是由树构成的，那么我们在看Isolation Forest（简称iForest）前，我们先来看看Isolation-Tree（简称iTree）是怎么构成的，iTree是一种随机二叉树，每个节点要么有两个女儿，要么就是叶子节点，一个孩子都没有。给定一堆数据集D，这里D的所有属性都是连续型的变量，iTree的构成过程如下：

• 随机选择一个属性Attr；
• 随机选择该属性的一个值Value；
• 根据Attr对每条记录进行分类，把Attr小于Value的记录放在左女儿，把大于等于Value的记录放在右孩子；
• 然后递归的构造左女儿和右女儿，直到满足以下条件：
  
  
  • 传入的数据集只有一条记录或者多条一样的记录；
  • 树的高度达到了限定高度；
    
    
  
  

        iTree构建好了后，就可以对数据进行预测啦，预测的过程就是把测试记录在iTree上走一下，看测试记录落在哪个叶子节点。iTree能有效检测异常的假设是：异常点一般都是非常稀有的，在iTree中会很快被划分到叶子节点，因此可以用叶子节点到根节点的路径h(x)长度来判断一条记录x是否是异常点；对于一个包含n条记录的数据集，其构造的树的高度最小值为log(n)，最大值为n-1，论文提到说用log(n)和n-1归一化不能保证有界和不方便比较，用一个稍微复杂一点的归一化公式：

s(x,n)就是记录x在由n个样本的训练数据构成的iTree的异常指数，s(x,n)取值范围为[0,1]异常情况的判断分以下几种情况：

• 越接近1表示是异常点的可能性高；
• 越接近0表示是正常点的可能性比较高；
• 如果大部分的训练样本的s(x,n)都接近于0.5，整个数据没有明显的异常。
  
  

    由于是随机选属性，随机选属性值，一棵树这么随便搞肯定是不靠谱，但是把多棵树结合起来就变强大了；

s(x,n)就是记录x在由n个样本的训练数据构成的iTree的异常指数，s(x,n)取值范围为[0,1]异常情况的判断分以下几种情况：

• 越接近1表示是异常点的可能性高；
• 越接近0表示是正常点的可能性比较高；
• 如果大部分的训练样本的s(x,n)都接近于0.5，整个数据没有明显的异常。
  
  

    由于是随机选属性，随机选属性值，一棵树这么随便搞肯定是不靠谱，但是把多棵树结合起来就变强大了；

更多链接


Sample K算法

0、题目来源

　　 最近去国内某牛叉互联网公司面试，出了一道算法题，看似简单，但是真正的答案十分巧妙。故此回忆并将原题以及解题思路记录下来，供大家学习：

　　随机的选取容量为N的数组中的k个元素，要求是不能重复选取，并且不能删除数组中的元素，只能够进行交换。其中 k≤n 。

1、解题思路

　
对于这个问题我目前有两种解法：

• 蓄水池算法 ；
• 交换元素法；
  
  

下面我就将这两种算法解决该问题的思路进行详细的解释。

1.1 蓄水池算法解题思路

　　蓄水池算法的详细原理的解释和证明不是本文的重点，读者可以去百度上搜索（我发誓，我绝对会）。但是本文还是会简单的介绍一下它的大致的意思：对于一个未知大小的数组，从其中最多选取K个不重复的数据，保证每个数据被选取的概率大小完全一样。
　　
　　如果你搞明白了蓄水池算法的思路，你就会明白它和本题的题意其实是完全一模一样。并且很清楚的知道它的算法复杂度为 O(n) 。

1.2 交换元素法解题思路

　　第二种解题思路就更巧妙了，因为它不需要 O(n) 的复杂度，仅仅需要的是 O(k) 的复杂度。因为题目中我们知道 k≤n ，所以O(k) 的复杂度比O(n) 的复杂度更优。接下来我将解释交换元素法的原理以及必要性。

　　首先，我们设想一下，如果题目不要求不重复选取的条件，那么我们很容易的想得到 O(k) 的算法。也就是依次从数组中随机的选取k个数字，不管他重复与否。但是现在题目的要求是不重复，当n很大k很小的时候，采用上述的方法也许可行，但是当k —> n 时，那时候随机选取的重复的概率将趋向于1，此法不可行。
　　
　　再进一步设想，如果我们把已经选取的数据与未被选取的数据能够分隔开的话，那么这样的话，我们是不是就可以毫无顾忌的在未被选取的数据集合中进行选取而保证不会出现过重复？ 答案是肯定的。
　　
　　具体的做法如下：逻辑上将元素分成前n-k个元素，和最后的k个被选的元素。这样就能把元素分隔开。每次迭代的从前n-k个元素中依次选取第k个元素，此时将被选取的元素与第n-k个元素进行交换。这样就能保证，当k递增的时候，未被选取的元素总在前n-k个中，所以随机选取的时候不会出现重复的情况。而且，我们只需要k次操作就能完成所有的元素的选取，因此算法复杂度为 O(k) 。

1.3 上述两种算法优缺点1.3.1 蓄水池算法

• 优点：不会改变元素的顺序；
• 缺点：算法复杂度高于交换元素法。
  
  

1.3.2 交换元素法

• 优点：算法复杂度最优；
• 缺点：改变了原始数组的数据出现的顺序；
  
  

所以，针对具体的问题场景和要求我们可以在上述两种算法中选择一种。

2、贴上源码（Java）

　　本文题目的要求来说，算法2是最优的算法。所以给出的代码是第二种算法的实现。如果你因为对Java不熟悉看不懂源码，那么我只能说，怪我咯……

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
* Created by Administrator on 2017/7/23.
*/
public class Test {
   
    public static void main(String[] args) {

        int N = 100;
        int k = 50;

        // 产生一个1~100的整形数组
      List<Integer> src = new ArrayList<Integer>();
        for (int i = 0; i < N; i++) {
            src.add(i + 1);
        }

        // 定义结果数组并获取数据
        List<Integer> ans;
        ans = sample(src, k);

        // 输出结果，并检验结果
        for (int i = 0; i < ans.size(); i++) {
           System.out.print(String.format("%-5d", ans.get(i)));

            if (i % 10 == 9) {
                System.out.println();
            }
        }

    }

    public static List<Integer> sample(List<Integer> src, int k) {

        int rear = src.size();
        int index, tmp;
        Random random = new Random(System.currentTimeMillis());
        List<Integer> ans = new ArrayList<Integer>();

        for (int i = 0; i < k; i++) {

            // 随机获取数组所以并将其添加到结果数组中
            index = random.nextInt(rear);
            ans.add(src.get(index));

            // 交换数组数据
         tmp = src.get(index);
            src.set(index, src.get(rear - 1));
            src.set(rear - 1, tmp);

            // 将随机选取的数组索引下界范围前移
            rear--;
        }
        return ans;
    }
}

运行结果：

32  66  16  3   82  20  97  61  74  8   

19  100 23  11  42  35  75  13  15  89   

84  81  9   55  38  94  67  71  96  58   

30  24  57  5   12  90  95  63  99  14   

17  88  69  53  46  52  21  39  93  6   

红黑树算法

前情提要


红黑树是AVL树里最流行的变种，有些资料甚至说自从红黑树出来以后，AVL树就被放到博物馆里了。红黑树是否真的有那么优秀，我们一看究竟。红黑树遵循以下5点规则，需要我们理解并熟记。
规则：
1.树节点要么是红的，要么是黑的
2.树的根节点是黑的
3.树的叶节点链接的空节点都是黑的，即nullNode为黑
4.红色节点的左右孩子必须是黑的
5.从某节点到null节点所有路径都包含相同数目的黑节点
正是因为作为二叉查找树的红黑树满足这些性质，才使得树的节点是相对平衡的。由归纳法得知，如果一颗子树的根到nullNode节点的路径都包含B个黑色节点，则这棵子树含有除nullNode节点外的2^B-1个节点，而由性质4得从根到nullNode节点的路径上至少有一半的节点是黑色的，从而得到树包含的节点数n>=2^(h/2)-1,h是树的深度，从而得到h<=2*log(n+1)。即可以保证红黑树的深度是对数的，可以保证对树的查找、插入删除等操作满足对数级的时间复杂度。
下边我们将讨论红黑树最主要的两个算法，插入和删除。


红黑树的插入

为了不违反规则5，所以我们将带插入的节点先染成红色，再进行调整以满足其他性质。为了能够清晰的解决问题，我们可以将红黑树的插入分为以下五种情况：

情况1：插入空树中，插入的节点是根节点

情况2：插入的节点的父亲是黑色的

情况3：插入的节点的父亲是红色的，而父节点的兄弟为黑色，且插入节点为外部节点（要找到它要么一直遍历做节点，要么一直遍历右节点）

情况4：插入的节点的父亲是红色的，而父节点的兄弟为黑色，且插入节点为内部节点（不是外外部节点的节点）

情况5：插入的节点的父亲是红色的，而父节点的兄弟也是红色的

对于第一种情况：插入后将根节点再染成黑色即可。

对于第二种情况：直接插入依然满足性质。首先设X是新增节点，P是其父节点，S是其父节点的兄弟节点，G是其的祖父节点。

对于第三种情况：违反了性质4，我们可以通过对P进行右旋和节点的重新着色对树进行修复（应对三、四两种情况我们的着色方式都是：在旋转前先将要旋转的根节点染红，然后旋转，最后将新的根节点染黑）见下面的“图2”。

对于第四种情况：亦是如此，只不过我们需要两次旋转，先对P做左旋再对G做右旋，并重新着色，见下面的“图3”。

对于第五种情况：我们如果按照三四两种情况的修复方式是无法满足性质的，我们就考虑旋转后将新的根节点染红，未插入之前的父节点的兄弟节点染红，新根节点的孩子节点染黑。这样出现的问题是新根节点的父节点可能是红的。此时，我们只能向着根的方向逐步过滤这种情况，不再有连续的两个红色节点或遇到根节点为止（把根重染成黑色）。这种策略自底向上，逐步递归完成，见下面的“图4”。

       我们还有一种策略是自顶向下，如果遇到一个黑色节点有两个红色节点，我们将进行颜色翻转（如果节点X有两个红色孩子，我们将X染成红色，将它的两个孩子染成黑色），如果X的父节点也是红色的呢？我们这又归于3、4两种情况。X的父节点的兄弟节点会不会是红色的呢？答案是不会，应为我们自顶向下已经排除了这种情况。此时我们可以排除情况5，将所有情况都转换为情况一到四的处理，除了特殊情况，就剩下情况三和情况四了。

下边是Java代码具体实现：

public void insert(E item){
    current = parent = grand = header;
    nullNode.element = item;
    //当未找到正确插入位置时，一直向下查找,
    //并对树中一个黑节点有两个红节点的情况进行调整  
    while(compare(item,current)!=0){
        great = grand;
        grand = parent;
        parent = current;
        current = compare(item,current)<0?current.left:current.right;
        if(current.left.color==RED&t.right.color==RED)
        handleReorient(item);
    }

    if(current!=nullNode){
        System.out.println("该项已存在");
        return;
    }
    //创建节点并插入修复  
    current = new RedBlackNode<E>(item, nullNode, nullNode);
    if(compare(item,parent)<0){
        parent.left = current;
    }
    else{
        parent.right = current;
    }
    current.parent = parent;
    handleReorient(item);
    nullNode.element = null;
}

//对要插入的节点的链进行调整修复  
private void handleReorient(E item){
    current.color = RED;
    current.left.color = BLACK;
    current.right.color = BLACK;

    if(parent.color == RED){
        grand.color = RED;//先把要旋转的树的根节点染红  
        // 如果不是外节点，则需要旋转两次，
        // 第一次旋转以parent为根，这里传过去的参数树根的父节点  
        if((compare(item,parent)<0)!=(compare(item,grand)<0))
        parent = rotate(item,grand);
        current = rotate(item,great);

        current.color = BLACK;//将新的根节点染黑  
    }
    header.right.color = BLACK;//将整棵树的根节点染黑  
}

/**
* 明确旋转树在根的左边还是右边后，
* 我们将旋转树父节点指向根，如果
* 最终项在左边就右旋，在右边就左旋
* @param item 最终项  
* @param parent 旋转树的根的父节点  
* @return 旋转树的根节点
*/
private RedBlackNode<E> rotate(E item,RedBlackNode<E> parent){
    if(compare(item,parent)<0){
        parent.left = compare(item,parent.left)<0?
                rotateWithLeftChild(parent.left):rotateWithRightChild(parent.left);
        parent.left.parent = parent;
        return parent.left;
    }
    else{
        parent.right = compare(item,parent.right)<0?
                rotateWithLeftChild(parent.right):
                rotateWithRightChild(parent.right);
        parent.right.parent = parent;
        return parent.right;
    }
}
//以左孩子为支点旋转，即我们所说的右旋（形象理解
//为以支点为中心向右旋转），t1为旋转树的根.返回新根  
private RedBlackNode<E> rotateWithLeftChild(RedBlackNode t1){

    RedBlackNode<E> t2 = t1.left;//得到左孩子  
    t1.left = t2.right;//将左孩子的右子树作为原根的左子树  
    t2.right = t1;//此时t2作为新根  

    t1.parent = t2;
    t2.left.parent = t2;
    t1.left.parent = t1;
    t1.right.parent = t1;
    return t2;
}
//以右孩子为支点旋转，即左旋  
private RedBlackNode<E> rotateWithRightChild(RedBlackNode t1){
    RedBlackNode<E> t2 = t1.right;
    t1.right = t2.left;
    t2.left = t1;

    t1.parent = t2;
    t2.right.parent = t2;
    t1.left.parent = t1;
    t1.right.parent = t1;
    return t2;
}

更多链接