精华内容
下载资源
问答
  • 决策树(Decision tree)是在已知各种情况发生概率的基础上,通过构成决策树来求取净现值的期望值大于等于零的概率,评价项目风险,判断其可行性的决策分析方法,是直观运用概率分析的种图解法。由于这种决策分支...

           决策树是一个树结构(可以是二叉树或非二叉树),其每个非叶节点表示一个特征属性上的测试,每个分支代表这个特征属性在某个值域上的输出,而每个叶节点存放一个输出类别。使用决策树进行决策的过程就是从根节点开始,测试待分类项中相应的特征属性,并按照其值选择输出分支,直到到达叶子节点,将叶子节点存放的类别作为决策结果。

    决策树学习通常包含这几个方面:特征选择、决策树生成、决策树剪枝、缺失值/异常值处理、决策树集成学习。

    决策树-特征属性选择划分

    决策树-缺失值和连续值处理及属性划分

    决策树-不同的决策树模型对比

    决策树-避免过拟合预剪枝和后剪枝对比区别

    决策树-算法小结及常见问题


        

    到目前为止我们仅讨论了基于离散属性来生成决策树,现实学习任务中常常遇到连续属性,以及数据中缺失问题。

    目录

    连续值处理

    缺失值处理


    连续值处理

    基本思路:连续属性离散化,常见做法:二分法(这是C4.5决策树算法中采用的机制)。

    对于连续属性a,我们可考察包括 n-1 个元素的候选划分集合(个属性值可形成 n-1 个候选点):

    示例1:

    示例2:

    图片描述

    对于数据集中的属性“密度”,决策树开始学习时,根节点包含的17个训练样本在该属性上取值均不同。我们先把“密度”这些值从小到大排序:
    图片描述
    根据上面计算 的公式,可得:
    图片描述
    下面开始计算t 取不同值时的信息增益:
    图片描述

    有一点需要注意的是 :与离散属性不同,若当前结点划分属性为连续属性,该属性还可作为其后代结点的划分属性。**如下图所示的一颗决策树,“含糖率”这个属性在根节点用了一次,后代结点也用了一次,只是两次划分点取值不同。
    图片描述

    缺失值处理

           现实生活中的数据集中的样本通常在某系属性上是缺失的,如果属性值缺失的样本数量比较少,我们可以直接简单粗暴的把不完备的样本删除掉,但是如果有大量的样本都有属性值的缺失,那么就不能简单地删除,因为这样删除了大量的样本,对于机器学习模型而言损失了大量有用的信息,训练出来的模型性能会受到影响。

    在决策树中处理含有缺失值的样本的时候,需要解决两个问题:

    • 如何在属性值缺失的情况下进行划分属性的选择?(比如“色泽”这个属性有的样本在该属性上的值是缺失的,那么该如何计算“色泽”的信息增益?)
    • 给定划分属性,若样本在该属性上的值是缺失的,那么该如何对这个样本进行划分?(即到底把这个样本划分到哪个结点里?)

     

    示例1:

    图片描述

    比较发现,“纹理”在所有属性中的信息增益值最大,因此,“纹理”被选为划分属性,用于对根节点进行划分。划分结果为:“纹理=稍糊”分支:{7,9,13,14,17},“纹理=清晰”分支:{1,2,3,4,5,6,15},“纹理=模糊”分支:{11,12,16}。如下图所示:

    图片描述

    那么问题来了,编号为{8,10}的样本在“纹理”这个属性上是缺失的,该被划分到哪个分支里?前面讲过了,这两个样本会同时进入到三个分支里,只不过进入到每个分支后权重会被调整(前面也说过,在刚开始时每个样本的权重都初始化为1)。编号为8的样本进入到三个分支里后,权重分别调整为5/15,7/15 和 3/15;编号为10的样本同样的操作和权重。因此,经过第一次划分后的决策树如下图所示:

    图片描述

    我们都知道构造决策树的过程是一个递归过程,原来不打算继续介绍递归过程了,但是因为权重发生了变化,所以继续介绍下递归过程。接下来,递归执行“纹理=稍糊”这个分支,样本集D = {7,8,9,10,13,14,17},共7个样本。如下图所示:

    图片描述

    下面来看具体的计算过程:
    

    图片描述

    对比能够发现属性“敲声”的星系增益值最大,因此选择“敲声”作为划分属性,划分后的决策树如下图所示:
    图片描述
    接下来对分支{敲声 = 沉闷}即结点{9,14,17}进行划分,根据博客决策树(一)介绍的三种递归返回情形,结点{9,14,17}因为包含的样本全部属于同一类别,因此无需划分,直接把结点{9,14,17}标记为叶结点,如下图所示:
    图片描述
    根据递归过程,接下来对分支“敲声 = 浊响”即结点{7,8,13}进行划分,计算过程和上面一样,虽然我也算过了,但是不再贴出来了,需要注意的是样本的权重是1/3。计算完比较能够知道属性“脐部”的信息增益值最大,因此选择“脐部”作为划分属性,划分完的决策树如下图所示:
    图片描述
    接下来,继续,对于结点{13},因为就一个样本了,直接把该结点标记为叶结点,类别为“坏瓜”;递归到结点{7,8},因为样本类别相同,所以也标记为叶结点,类别为“好瓜”;递归到结点“脐部=平坦”,因为这个结点不包含任何样本为空集,因此,把该结点标记为叶结点,类别设置为父节点中多数类的类别,即为“好瓜”。因此“纹理=稍糊”这颗子树构造完毕,如下图所示:
    图片描述


    接下来,只需递归的重复上述过程即可,即能训练出一颗完整的决策树,最终的决策树如下图所示(该图片来自西瓜书):
    图片描述
     

     

     

    参考链接:https://www.imooc.com/article/257743
    参考链接:https://blog.csdn.net/leaf_zizi/article/details/83503167
    参考链接:https://www.cnblogs.com/lsm-boke/p/12260343.html
    参考链接:https://blog.csdn.net/qq_35649945/article/details/96633602

     

    展开全文
  • Java内存划分和分配

    千次阅读 2018-10-18 15:03:41
    最后学习一下Java堆内存的分代划分和内存分配。 Java内存区域划分 首先通过一张图来看一下Java虚拟机是如何划分内存空间的。 程序计数器:是块较小内存,可以看作是当前线程所执行的字节码的行号指示...

    综述

    在这边文章中我们将了解一下Java的内存区域是怎么划分的以及每个区域的功能。在了解Java每个内存区域的功能之后,进一步分析Java对象如何的创建和对象的内存分配,以及如何访问对象中的内存。最后学习一下Java堆内存的分代划分和内存分配。

    Java内存区域划分

    首先通过一张图来看一下Java虚拟机是如何划分内存空间的。

    程序计数器:是一块较小内存,可以看作是当前线程所执行的字节码的行号指示器。每条线程都需要有一个独立的程序计数器,各个线程之间计数器互不影响。

    Java虚拟机栈:Java虚拟机栈也是线程私有,他的生命周期与线程相同。虚拟机栈描述的是Java方法执行的内存模型:每个方法在执行的同时都会创建一个栈帧用于存储局部变量、操作数、操作数栈、动态链接、方法出口等信息。每一个方法的调用过程直至执行完成的过成,就对应着一个栈帧在虚拟机栈中入栈到出栈的过程。

    局部变量表存放了编译期可知的各种基本数据类型、对象引用和returnAddress类型。如果线程请求的栈深度大于虚拟机所允许的深度,将抛出StackOverflowError异常;如果虚拟机可以动态扩展,如扩展时无法申请到足够的内存,就会抛出OutOfMemoryError异常

    本地方法栈:与虚拟机栈类似,他们之间的区别是虚拟机栈为虚拟机执行Java方法(字节码)服务,而本地方法栈则为虚拟机使用到的Native方法服务。

    Java堆:Java堆(Java Heap)是Java虚拟机所管理的内存中最大的一块。Java堆是被所有线程共享的一块内存区域。在此内存区域中唯一目的就是存放对象实例,几乎所有的对象都在这里分配内存。

    Java堆是垃圾收集器管理的主要区域。也叫“GC堆”。从内存回收的角度来看,由于现在的收集器基本都采用分代收集算法,所以Java堆还可以细分为:新生代和老年代;在细致一点的有Eden空间、From Survivor空间、To Survivor空间等。从内存分配的家读来看,线程共享的Java堆中可能划分出多个线程私有分配缓冲区(Thread Local Allocation Buffer,TLAB)。不过无论如何划分,都与存放内容无关,无论那个区域,存储的都是对象实例,进一步划分的目的是为了更好地回收内存,或者更快的分配内存。Java堆可以处于物理上不连续的内存空间中,只要逻辑上是连续的即可。

    方法区(Method Area):和Java堆一样也是各个线程共享的内存区域,他用于存储已被虚拟机加载的类信息、常量、静态变量、即时编译后的代码等数据。使用永久代实现方法区。

    对象的创建

    对象内存的分配

    虚拟机遇到一条new指令时,先去检查这个指令的参数是否能在常量池中定位到一个类的符号的引用,并且检查这个符号引用代表的类是否已经被加载、解析和初始化。如果没有,那必须先执行相应的类的加载过程。在类加载检查通过后,虚拟机将为新生对象分配内存。对象所需要的内存在类加载完成之后便可完全确定。

    指针碰撞:假设Java堆是绝对规整的,所有用过的内存放在一边,空闲的内存放在另一边,中间放一个指针作为分界点的指示器。为对象分配内存时把那个指针向空闲空间那边挪动一段与对象大小相等的距离。

    空闲列表:Java堆中的内存不是规整的,以使用的内存和空闲的内存相互交错,无法使用指针碰撞。这时虚拟机就必须维护一个列表,记录上哪些内存是可用的,在分配内存的时候从列表中找一块足够大的空间划分给对象实例,并更新列表上的记录。

    选择哪种分配方式由Java堆是否规整决定,而Java堆是否规整又由所采用的垃圾收集器是否带有压缩整理功能决定。

    如果只是修改一个指针所指向的位置,在并发情况下并不是线程安全,可能出现正在给对象A分配内存,指针还没来的及修改,对象B又同时使用了原来的指针来分配内存的情况。两种解决方案,一种是对分配内存空间的动作进行同步处理——实际上虚拟机采用CAS配上失败重试的方式保证更新操作的原子性;另一种是把内存分配的动作按照线程划分在不同的空间之中进行,即每个线程在Java堆中预先分配一小块内存,称为本地线程分配缓冲(Thread Local Allocation Buffer,TLAB)。那个线程要分配内存,就在哪个线程的TLAB上分配,只有TLAB用完并分配新的TLAB时,才需要同步锁定。

    对象的内存布局

    对象在内存存储的布局可以分为3块区域:对象头(Header)、实例数据(Instance Data)和对齐填充(Padding)。

    HotSpot虚拟机的对象头包括两部分信息,第一部分用于存储对象自身的运行时数据,如哈希码(HashCode),GC分代年龄,锁状态标志,线程持有的锁,偏向线程ID,偏向时间戳等.这部分数据在长度32位和64位的虚拟机(未开启压缩指针)中分别为32bit和64bit,官方称它为"Mark Word".考虑到虚拟机的空间效率,Mark Word被设计成一个非固定的数据结构以便在极小的空间内存储尽量多的信息,他会根据对象的状态复用自己的存储空间,对象头的另一部分是类型指针,即对象指向它的类元数据的指针,虚拟机通过这个指针来确定这个对象是哪个类的实例.并不是所有的虚拟机实现都必须在对象数据上保留类型指针.另外,如果对象是一个Java数组,那么在对象头中还必须有一块用于记录数组长度的数据,因为虚拟机可以通过普通Java对象的元数据信息确定Java对象的大小.

    实例数据部分是对象真正存储的有效信息,也是在程序代码中多定义的各种类型字段内容.无论是从父类继承下来的,还是在子类定义的,都需要记录起来.

    对其填充不是必然存在的,只是起着占位符的作用.由于HotSpot VM的自动内存管理系统要求对象起始地址必须是8字节的整数倍,也就是说对象大小必须是8字节的证书倍.对象头部分正好是8字节的倍数(1倍或者2倍),因此当实例数据部分没有对齐时,就需要通过对齐填充来补全.

    对象访问定位

    目前主流的访问方式有使用句柄直接指针两种。

    句柄访问:Java堆将会划分出一块内存作为句柄池,reference中存储的就是对象的句柄地址,而句柄中包含了对象实例数据和类型数据各自的具体地址信息。

    直接指针访问:Java堆对象的布局中就须考虑如何放置访问类型数据相关信息,而reference中存储的就是对象地址。

    使用句柄访问的最大好处就是reference中存储的是稳定的句柄地址,在对象被移动(垃圾收集时移动对象是非常普遍的行为)时只会改变句柄中的实例数据指针,而reference本身不需要修改。使用直接指针访问的最大好处就是速度更快,他节省了一次指针定位时间的开销。HotSpot采用的是直接指针进行对象访问的。

    Java内存分配

    Java堆内存可以分为新生代和老年代。在新生代中可以分为一块较大的Eden空间和两块较小的Survivor空间,HotSpot虚拟机默认Eden和Survivor的大小比例是8:1。

    对象的内存分配,一般来说,就是在堆上分配(也可能经过JIT编译后被拆散为标量类型并间接地栈上分配),对象主要分配在新生代的Eden区上,如果启动了本地线程分配缓冲,将按线程优先在TLAB上分配。少数情况下也可能会直接分配在老年代中,分配规则并不是固定的。

    对象优先在Eden分配

    大多数情况下,对象在新生代Eden区中分配。当Eden区没有足够空间进行分配时,虚拟机将发起一次Minor GC。
    新生代GC(Minor GC):是指发生在新生代的垃圾收集动作,因为Java对象大多数都具备朝生夕死的特性,所以Minor GC非常频繁,一般回收速度比较快。
    老年代GC(Major GC/Full GC):指发生在老年代的GC,出现了Major GC,经常会伴随至少一次的Minor GC(并非绝对)。Major GC的速度一般会比 Minor GC 慢10倍以上。

    大对象直接进入老年代

    大对象对虚拟机内存分配来说是一个坏消息(写程序应该避免写出一群“朝生夕死”的“短命大对象”),经常出现大对象容易导致内存还有不少空间时就提前触发垃圾收集以获取足够的连续空间来“安置”它们。虚拟机提供了一个-XX:PretenureSizeThreshold参数,令大于这个设置值的对象直接在老年代分配。这样做的目的是避免在Eden区及两个Survivor区之间发生大量的内存复制

    长期存活的对象将进入老年代

    如果对象在Eden出生并经过第一次Minor GC后仍然存活,并且能够被Survivor容纳的话,将会被移动到Survivor空间中,并且对象年龄设为1.对象在Survivor区中每“熬过”一次Minor GC,年龄就增加1岁,当它的年龄增加到一定程度(默认15岁)的时候就会被晋升到老年代当中。对象晋升老年代年龄的阀至可以通过参数-XX:MaxTenuringThreshold设置。

    为了更好的适应内存的不同状况,虚拟机并不是永远的要求对象的年龄必须达到了MaxTenuringThreshold才能晋升老年代,如果Survivor空间中相同年龄所有对象大小的总和大于Survivor空间的一半,年龄大于或等于该年龄的对象就可以直接进入老年代,无需等到MaxTenuringThreshold中要求的年龄。

    总结

    Java内存可以分为程序计数器、Java虚拟机栈、本地方法栈、Java堆、方法区这几个部分。其中程序计数器、Java虚拟机栈、本地方法栈属于线程私有,而Java堆和方法区属于线程共享区域。对于Java的堆内存可以划分为新生代和老年代。在新生代中划分为一个Eden区和两个Survivor区。创建一个Java对象时,会通过指针碰撞或空闲列表法为对象分配内存。而当我们访问一个对象的时候可以通过句柄或者直接地址的方式进行对象的访问。

    参考周志明的《深入理解Java虚拟机》

    展开全文
  • 期次是指一个喷发中心一次相对集中的(准连续)火山活动,在物质成分、喷发方式及喷发强度的规律性变化过程中,所形成的一套相序上具有成因联系的岩石组合。旋回由一个至若干个期次构成。在期次划分过程中,综合运用...
  • 快速排序

    万次阅读 多人点赞 2017-03-18 18:11:48
    下面来看某一次划分的步骤,如下图: 上图中的划分操作可以分为以下5个步骤: 获取中轴元素 i从左至右扫描,如果小于基准元素,则i自增,否则记下a[i] j从右至左扫描,如果大于基准元素,则i自减,否则...

    快速排序也是一种采用分治法解决问题的一个典型应用。在很多编程语言中,对数组,列表进行的非稳定排序在内部实现中都使用的是快速排序。而且快速排序在面试中经常会遇到。

    本文首先介绍快速排序的思路,算法的实现、分析、优化及改进,最后分析了.NET 中列表排序的内部实现。

    一 原理

    Sorting_quicksort_anim

    快速排序的基本思想如下:

    1. 对数组进行随机化。
    2. 从数列中取出一个数作为中轴数(pivot)。
    3. 将比这个数大的数放到它的右边,小于或等于它的数放到它的左边。
    4. 再对左右区间重复第三步,直到各区间只有一个数。

    Basic Step of Quick Sort

    如上图所示快速排序的一个重要步骤是对序列进行以中轴数进行划分,左边都小于这个中轴数,右边都大于该中轴数,然后对左右的子序列继续这一步骤直到子序列长度为1。

    下面来看某一次划分的步骤,如下图:

    Partition trace in Quick Sort

    上图中的划分操作可以分为以下5个步骤:

    1. 获取中轴元素
    2. i从左至右扫描,如果小于基准元素,则i自增,否则记下a[i]
    3. j从右至左扫描,如果大于基准元素,则i自减,否则记下a[j]
    4. 交换a[i]和a[j]
    5. 重复这一步骤直至i和j交错,然后和基准元素比较,然后交换。

    划分过程的代码实现如下:

    /// <summary>
    /// 快速排序中的划分过程
    /// </summary>
    /// <param name="array">待划分的数组</param>
    /// <param name="lo">最左侧位置</param>
    /// <param name="hi">最右侧位置</param>
    /// <returns>中间元素位置</returns>
    private static int Partition(T[] array, int lo, int hi)
    {
        int i = lo, j = hi + 1;
        while (true)
        {
            //从左至右扫描,如果碰到比基准元素array[lo]小,则该元素已经位于正确的分区,i自增,继续比较i+1;
            //否则,退出循环,准备交换
            while (array[++i].CompareTo(array[lo]) < 0)
            {
                //如果扫描到了最右端,退出循环
                if (i == hi) break;
            }
    
            //从右自左扫描,如果碰到比基准元素array[lo]大,则该元素已经位于正确的分区,j自减,继续比较j-1
            //否则,退出循环,准备交换
            while (array[--j].CompareTo(array[lo]) > 0)
            {
                //如果扫描到了最左端,退出循环
                if (j == lo) break;
            }
    
            //如果相遇,退出循环
            if (i >= j) break;
    
            //交换左a[i],a[j]右两个元素,交换完后他们都位于正确的分区
            Swap(array, i, j);
        }
        //经过相遇后,最后一次a[i]和a[j]的交换
        //a[j]比a[lo]小,a[i]比a[lo]大,所以将基准元素与a[j]交换
        Swap(array, lo, j);
        //返回扫描相遇的位置点
        return j;
    }

    划分前后,元素在序列中的分布如下图:

    before and after partition

    二 实现

    与合并算法基于合并这一过程一样,快速排序基于分割(Partition)这一过程。只需要递归调用Partition这一操作,每一次以Partition返回的元素位置来划分为左右两个子序列,然后继续这一过程直到子序列长度为1,代码的实现如下:

    public class QuickSort<T> where T : IComparable<T>
    {
        public static void Sort(T[] array)
        {
            Sort(array, 0, array.Length - 1);
        }
    
        private static void Sort(T[] array, int lo, int hi)
        {
            //如果子序列为1,则直接返回
            if (lo >= hi) return;
            //划分,划分完成之后,分为左右序列,左边所有元素小于array[index],右边所有元素大于array[index]
            int index = Partition(array, lo, hi);
    
           //对左右子序列进行排序完成之后,整个序列就有序了
            //对左边序列进行递归排序
            Sort(array, lo, index - 1);
            //对右边序列进行递归排序
            Sort(array, index + 1, hi);
        }
    }

    下图说明了快速排序中,每一次划分之后的结果:

    the two part sorted

    一般快速排序的动画如下:

    quicksort

    三 分析

    1. 在最好的情况下,快速排序只需要大约nlgn次比较操作,在最坏的情况下需要大约1/2 n2 次比较操作。

      在最好的情况下,每次的划分都会恰好从中间将序列划分开来,那么只需要lgn次划分即可划分完成,是一个标准的分治算法Cn=2Cn/2+N,每一次划分都需要比较N次,大家可以回想下我们是如何证明合并排序的时间复杂度的。

      the compare complexity in  quick sort at the bese case

      在最坏的情况下,即序列已经排好序的情况下,每次划分都恰好把数组划分成了0,n两部分,那么需要n次划分,但是比较的次数则变成了n, n-1, n-2,….1, 所以整个比较次数约为n(n-1)/2~n2/2.

      the compare complexity in  quick sort at the worst case

    2. 快速排序平均需要大约2NlnN次比较,来对长度为n的排序关键字唯一的序列进行排序。 证明也比较简单:假设CN为快速排序平均花在比较上的时间,初始C0=C1=0,对于N>1的情况,有:

      image

      其中N+1是分割时的比较次数,image 表示将序列分割为0,和N-1左右两部分的概率为1/N, 划分为1,N-2左右两部分的概率也为1/N,都是等概率的。

      然后对上式左右两边同时乘以N,整理得到:

      image

      然后,对于N为N-1的情况:

      image

      两式相减,然后整理得到:

      image

      然后左右两边同时除以N(N+1),得到:

      image

      可以看到,这是一个递归式,我们将image 递归展开得到:

      image

      然后处理一下得到:

      image

    3. 平均情况下,快速排序需要大约1.39NlgN次比较,这比合并排序多了39%的比较,但是由于涉及了较少的数据交换和移动操作,他要比合并排序更快。
    4. 为了避免出现最坏的情况,导致序列划分不均,我们可以首先对序列进行随机化排列然后再进行排序就可以避免这一情况的出现。
    5. 快速排序是一种就地(in-place)排序算法。在分割操作中只需要常数个额外的空间。在递归中,也只需要对数个额外空间。
    6. 另外,快速排序是非稳定性排序。

    Quick Sort is not Stable

    四 改进

    对一般快速排序进行一些改进可以提高其效率。

    1. 当划分到较小的子序列时,通常可以使用插入排序替代快速排序

    对于较小的子序列(通常序列元素个数为10个左右),我们就可以采用插入排序直接进行排序而不用继续递归,算法改造如下:

    private const int CUTTOFF = 10;
    private static void Sort(T[] array, int lo, int hi)
    {
        //如果子序列为1,则直接返回
        if (lo >= hi) return;
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1) 
        {
            Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        //划分,划分完成之后,分为左右序列,左边所有元素小于array[index],右边所有元素大于array[index]
        int index = Partition(array, lo, hi);
    
        //对左右子序列进行排序完成之后,整个序列就有序了
    
        //对左边序列进行递归排序
        Sort(array, lo, index - 1);
        //对右边序列进行递归排序
        Sort(array, index + 1, hi);
    }

    2. 三平均分区法(Median of three partitioning)

    在一般的的快速排序中,选择的是第一个元素作为中轴(pivot),这会出现某些分区严重不均的极端情况,比如划分为了1和n-1两个序列,从而导致出现最坏的情况。三平均分区法与一般的快速排序方法不同,它并不是选择待排数组的第一个数作为中轴,而是选用待排数组最左边、最右边和最中间的三个元素的中间值作为中轴。这一改进对于原来的快速排序算法来说,主要有两点优势:

    (1) 首先,它使得最坏情况发生的几率减小了。

    (2) 其次,未改进的快速排序算法为了防止比较时数组越界,在最后要设置一个哨点。如果在分区排序时,中间的这个元素(也即中轴)是与最右边数过来第二个元素进行交换的话,那么就可以省略与这一哨点值的比较。

    对于三平均分区法还可以进一步扩展,在选取中轴值时,可以从由左中右三个中选取扩大到五个元素中或者更多元素中选取,一般的,会有(2t+1)平均分区法(median-of-(2t+1)。常用的一个改进是,当序列元素小于某个阈值N时,采用三平均分区,当大于时采用5平均分区。

    采用三平均分区法对快速排序的改进如下:

    private static void Sort(T[] array, int lo, int hi)
    {
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1) 
        {
            //Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        //采用三平均分区法查找中轴
        int m = MedianOf3(array, lo, lo + (hi - lo) / 2, hi);
        Swap(array, lo, m);
        //划分,划分完成之后,分为左右序列,左边所有元素小于array[index],右边所有元素大于array[index]
        int index = Partition(array, lo, hi);
    
        //对左右子序列进行排序完成之后,整个序列就有序了
    
        //对左边序列进行递归排序
        Sort(array, lo, index - 1);
        //对右边序列进行递归排序
        Sort(array, index + 1, hi);
    }
    
    /// <summary>
    /// 查找三个元素中位于中间的那个元素
    /// </summary>
    /// <param name="array"></param>
    /// <param name="lo"></param>
    /// <param name="center"></param>
    /// <param name="hi"></param>
    /// <returns></returns>
    private static int MedianOf3(T[] array, int lo, int center, int hi)
    {
        return (Less(array[lo], array[center]) ?
               (Less(array[center], array[hi]) ? center : Less(array[lo], array[hi]) ? hi : lo) :
               (Less(array[hi], array[center]) ? center : Less(array[hi], array[lo]) ? hi : lo));
    }
    
    private static bool Less(T t1, T t2)
    {
        return t1.CompareTo(t2) < 0;
    }

    使用插入排序对小序列进行排序以及使用三平均分区法对一般快速排序进行改进后运行结果示意图如下:

    Improvement using Insertsort and 3 mediation partition

    3. 三分区(3-way partitioning) 快速排序

    通常,我们的待排序的序列关键字中会有很多重复的值,比如我们想对所有的学生按照年龄进行排序,按照性别进行排序等,这样每一类别中会有很多的重复的值。理论上,这些重复的值只需要处理一次就行了。但是一般的快速排序会递归进行划分,因为一般的快速排序只是将序列划分为了两部分,小于或者大于等于这两部分。

    既然要利用连续、相等的元素不需要再参与排序这个事实,一个直接的想法就是通过划分让相等的元素连续地摆放:

     3-way partition quick sort

    然后只对左侧小于V的序列和右侧大于V对的序列进行排序。这种三路划分与计算机科学中无处不在,它与Dijkstra提出的“荷兰国旗问题”(The Dutch National Flag Problem)非常相似。

    Dijkstra的方法如上图:

    从左至右扫描数组,维护一个指针lt使得[lo…lt-1]中的元素都比v小,一个指针gt使得所有[gt+1….hi]的元素都大于v,以及一个指针i,使得所有[lt…i-1]的元素都和v相等。元素[i…gt]之间是还没有处理到的元素,i从lo开始,从左至右开始扫描:

    · 如果a[i]<v: 交换a[lt]和a[i],lt和i自增

    · 如果a[i]>v:交换a[i]和a[gt], gt自减

    · 如果a[i]=v: i自增

    下面是使用Dijkstra的三分区快速排序代码:

    private static void Sort(T[] array, int lo, int hi)
    {
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1)
        {
            Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        //三分区
        int lt = lo, i = lo + 1, gt = hi;
        T v = array[lo];
        while (i<=gt)
        {
            int cmp = array[i].CompareTo(v);
            if (cmp < 0) Swap(array, lt++, i++);
            else if (cmp > 0) Swap(array, i, gt--);
            else i++;
        }
    
        //对左边序列进行递归排序
        Sort(array, lo, lt - 1);
        //对右边序列进行递归排序
        Sort(array, gt + 1, hi);
    }

    三分区快速排序的每一步如下图所示:

    3-way partitioning trace

    三分区快速排序的示意图如下:

    3 way quick sort visual trace

    Dijkstra的三分区快速排序虽然在快速排序发现不久后就提出来了,但是对于序列中重复值不多的情况下,它比传统的2分区快速排序需要更多的交换次数。

    Bentley 和D. McIlroy在普通的三分区快速排序的基础上,对一般的快速排序进行了改进。在划分过程中,i遇到的与v相等的元素交换到最左边,j遇到的与v相等的元素交换到最右边,i与j相遇后再把数组两端与v相等的元素交换到中间

    Bentley  McIlroy 3 way partition 

    这个方法不能完全满足只扫描一次的要求,但它有两个好处:首先,如果数据中没有重复的值,那么该方法几乎没有额外的开销;其次,如果有重复值,那么这些重复的值不会参与下一趟排序,减少了无用的划分。

    下面是采用 Bentley&D. McIlroy 三分区快速排序的算法改进:

    private static void Sort(T[] array, int lo, int hi)
    {
        //对于小序列,直接采用插入排序替代
        if (hi - lo <= CUTTOFF - 1)
        {
            Sort<int>.InsertionSort(array, lo, hi);
            return;
        }
        // Bentley-McIlroy 3-way partitioning
        int i = lo, j = hi + 1;
        int p = lo, q = hi + 1;
        T v = array[lo];
        while (true)
        {
            while (Less(array[++i], v))
                if (i == hi) break;
            while (Less(v, array[--j]))
                if (j == lo) break;
    
            // pointers cross
            if (i == j && Equal(array[i], v))
                Swap(array, ++p, i);
            if (i >= j) break;
    
            Swap(array, i, j);
            if (Equal(array[i], v)) Swap(array, ++p, i);
            if (Equal(array[j], v)) Swap(array, --q, j);
        }
    
        //将相等的元素交换到中间
        i = j + 1;
        for (int k = lo; k <= p; k++) Swap(array, k, j--);
        for (int k = hi; k >= q; k--) Swap(array, k, i++);
    
        Sort(array, lo, j);
        Sort(array, i, hi);
    }

    三分区快速排序的动画如下:

    3wayquick sort

    4.并行化

    和前面讨论对合并排序的改进一样,对所有使用分治法解决问题的算法其实都可以进行并行化,快速排序的并行化改进我在之前的浅谈并发与并行这篇文章中已经有过介绍,这里不再赘述。

    五 .NET 中元素排序的内部实现

    快速排序作为一种优秀的排序算法,在很多编程语言的元素内部排序中均有实现,比如Java中对基本数据类型(primitive type)的排序,C++,Matlab,Python,FireFox Javascript等语言中均将快速排序作为其内部元素排序的算法。同样.NET中亦是如此。

    .NET这种对List<T>数组元素进行排序是通过调用Sort方法实现的,其内部则又是通过Array.Sort实现,MSDN上说在.NET 4.0及之前的版本,Array.Sort采用的是快速排序,然而在.NET 4.5中,则对这一算法进行了改进,采用了名为Introspective sort 的算法,即保证在一般情况下达到最快排序速度,又能保证能够在出现最差情况是进行优化。他其实是一种混合算法:

    • 当待分区的元素个数小于16个时,采用插入排序
    • 当分区次数超过2*logN,N是输入数组的区间大小,则使用堆排序(Heapsort)
    • 否则,使用快速排序。

    有了Reflector这一神器,我们可以查看.NET中的ArraySort的具体实现:

    Array.Sort这一方法在mscorlib这一程序集中,具体的实现方法有分别针对泛型和普通类型的SortedGenericArray和SortedObjectArray,里面的实现大同小异,我们以SortedGenericArray这个类来作为例子看:

    ArraySort implementation in .NET_1

    首先要看的是Sort方法,其实现如下:

    ArraySort implementation in .NET_2

    该方法中,首先判断运行的.NET对的版本,如果是4.5及以上版本,则用IntrospectiveSort算法,否则采用限定深度的快速排序算法DepthLimitedQuickSort。先看IntrospectiveSort:

    ArraySort implementation in .NET_3

    该方法第一个元素为数组的最左边元素位置,第二个参数为最右边元素位置,第三个参数为2*log2N,继续看方法内部:

    ArraySort implementation in .NET_4

    可以看到,当num<=16时,如果元素个数为1,2,3,则直接调用SwapIfGreaterWithItem进行排序了。否则直接调用InsertSort进行插入排序。

    这里面也是一个循环,每循环一下depthLimit就减小1个,如果为0表示划分的次数超过了2logN,则直接调用基排序(HeapSort),这里面的划分方法PickPivortAndPartitin的实现如下:

    ArraySort implementation in .NET_5

    它其实是一个标准的三平均快速排序。可以看到在.NET 4.5中对Quick进行优化的部分主要是在元素个数比较少的时候采用选择插入,并且在递归深度超过2logN的时候,采用基排序。

    下面再来看下在.NET 4.0及以下平台下排序DepthLimitedQuickSort方法的实现:

    从名称中可以看出这是限定深度的快速排序,在第三个参数传进去的是0x20,也就是32。

    DepthLimitedQuickSort

    可以看到,当划分的次数大于固定的32次的时候,采用了基排序,其他的部分是普通的快速排序。

    六 总结

    由于快速排序在排序算法中具有排序速度快,而且是就地排序等优点,使得在许多编程语言的内部元素排序实现中采用的就是快速排序,本问首先介绍了一般的快速排序,分析了快速排序的时间复杂度,然后就分析了对快速排序的几点改进,包括对小序列采用插入排序替代,三平均划分,三分区划分等改进方法。最后介绍了.NET不同版本下的对元素内部排序的实现。

    快速排序很重要,希望本文对您了解快速排序有所帮助。

    展开全文
  • VVC块划分

    万次阅读 2019-12-03 11:36:01
    VVCHEVC与AVC一样,都是基于块的混合编码框架,其编码流程也都类似。下图是VVC的编码架构。 VVCHEVC的块划分有很多...帧图像被划分个或多个tile行tile列,每个tile是个矩形区域包含整数个CTU。 ...

    VVC和HEVC与AVC一样,都是基于块的混合编码框架,其编码流程也都类似。下图是VVC的编码架构。

     

    VVC和HEVC的块划分有很多类似的地方,同时划分方式、形状、尺寸等又有很多不同。

    1、slices,tiles和bricks划分

    VVC里的slice和tile跟HEVC是一样的。

    一帧图像被划分为一个或多个tile行和tile列,每个tile是一个矩形区域包含整数个CTU。

    每个tile可以被划分为一个或多个brick,每个brick包含该tile里几个CTU行。一个tile如果没有被划分为多个brick,那该tile被看作是一整个brick。

    一个slice包含一帧图像的多个tile,或包含一个tile内的多个brick。

    VVC支持两种类型的slice, raster-scan slice mode和rectangular slice mode。raster-scan slice mode的slice包含帧内按扫描顺序排列的一系列tile。rectangular slice mode的slice包含一系列brick并形成矩形形状。

     

    上图中图像被划分12个tile(3个 tile列,4个tile行)和3个raster-scan slice mode的slice。

     

    上图中图像被划分为24个tile(6个 tile列,4个tile行)和9个rectangular slice mode的slice。

     

    上图中图像被划分为4个tile(2个 tile列,2个tile行),11个brick(左上角1个,右上角5个,左下角2个,右下角3个),4个rectangular slice mode的slice。

    2、CTU划分

    在VVC中为了适应4k、8k等视频编码的需要将CTU的最大尺寸提高到128x128,最小尺寸还是4x4。

    在HEVC中CTU会按四叉树划分方式被划分为CU,每个CU又可以划分为PU和TU。在VVC中将不在区分CU、PU和TU的概念。

    VVC中除了四叉树划分方式外,还引进了多类型树(multi-type tree,MTT)概念,包括二叉树(binary tree,BT)和三叉树(ternary tree,TT)。一个CTU首先按四叉树方式进行一次划分,四叉树的每个叶子节点可以进一步按照多类型树方式进行划分,有4种多类型树划分方式水平二叉树划分(SPLIT_BT_HOR),垂直二叉树划分(SPLIT_BT_VER),水平三叉树划分(SPLIT_TT_HOR),垂直三叉树划分(SPLIT_TT_VER)。

    下图是多类型树的几种划分模式。其中三叉树是按1:2:1的方式划分的。

     

    下图是一个CTU划分实例,粗实线是四叉树划分边界,细实线是多类型树边界。

     

    在VTM5中支持亮度和色度块使用不同的划分结构。目前,对于P和Bslice,同一个CTU的亮度和色度CTB划分结构相同,对于I slice同一个CTU的亮度和色度CTB可以按不同的结构进行划分。

    3、图像边界处CU划分

    当一个块超过图像的右边界或下边界时,该块会被强制进行进一步划分直到所有CU都在图像内部。下面是VTM5内的划分规则:

    • 如果一个块既超出了下边界也超出了右边界

      • 如果该块是一个四叉树节点且尺寸大于最小四叉树节点尺寸,则该块被强制进行四叉树划分

      • 否则该块被强制进行SPLIT_BT_HOR模式划分

    • 如果一个块只超出了下边界

      • 如果该块是一个四叉树节点且尺寸大于最小四叉树节点尺寸,且该块尺寸大于最大的二叉树节点尺寸,该块被强制进行四叉树划分

      • 如果该块是一个四叉树节点且尺寸大于最小四叉树节点尺寸,且该块尺寸小于等于最大的二叉树节点尺寸,该块被强制进行四叉树划分或SPLIT_BT_HOR模式划分

      • 否则(该块是一个二叉树节点或尺寸小于等于最小四叉树节点尺寸),该块被强制进行SPLIT_BT_HOR模式划分

    • 如果一个块只超出了右边界

      • 如果该块是一个四叉树节点且尺寸大于最小四叉树节点尺寸,且该块尺寸大于最大的二叉树节点尺寸,该块被强制进行四叉树划分

      • 如果该块是一个四叉树节点且尺寸大于最小四叉树节点尺寸,且该块尺寸小于等于最大的二叉树节点尺寸,该块被强制进行四叉树划分或SPLIT_BT_VER模式划分

      • 否则(该块是一个二叉树节点或尺寸小于等于最小四叉树节点尺寸),该块被强制进行SPLIT_BT_VER模式划分

    4、CU冗余划分的限制

    四叉树和多类型树相结合的划分方式使得VVC块划分更加灵活,但也可能造成不同划分方式相结合导致相同的划分结果,这种冗余的划分应该被禁止。

    如下图,在同一个方向进行两次连续的二叉树划分,和先进行一次三叉树划分再在中间进行二叉树划分的结果相同。所以VVC禁止在三叉树中间部分进行同方向的二叉树划分。

     

    5、Virtual pipeline data units (VPDUs)

    VPDU是图像中不重叠的单元。在硬件解码器中,连续的VDPU要同时被多阶段流水线并行处理。VDPU要和该阶段的buffer size近似成比例时效率最高,所以要保持VDPU size比较小。在大部分硬件解码器中VDPU size被设置为最大的TB size。但是VVC内三叉树(TT)和二叉树(BT)划分模式可能导致VDPU size变大。

    为了使VDPU size保持在64x64亮度块的大小,VTM5做了如下限制:

    • 如果CU的宽或高等于128,则不进行TT划分。

    • 对于128xN的CU,N<=164,不进行水平BT划分

    • 对于Nx128的CU,N<=164,不进行垂直BT划分

    下图是禁止划分的实例。

     

    感兴趣的请关注微信公众号Video Coding

     

    展开全文
  • 2019工程伦理慕课答案(2019秋)习题及期末答案

    万次阅读 多人点赞 2019-11-08 18:19:53
    章习题(下) 单选题 (1/1 point) 下列哪项不是工程与技术的区别 内容性质 目的 活动主体 任务、对象思维方式 单选题 (1/1 point) 下列哪项不是工程活动的特征 自主性 创造性 ...
  • 图像分割综述

    万次阅读 多人点赞 2019-07-09 22:03:48
    所谓图像分割是指根据灰度、彩色、空间纹理、几何形状等特征把图像划分成若干个互不相交的区域,使得这些特征在同一区域内表现出一致性或相似性,而在不同区域间表现出明显的不同。简单的说就是在副图像中,把目标...
  • 快速掌握子网划分和子网汇总

    千次阅读 多人点赞 2020-11-17 10:19:47
    是由连续的1和连续的0组成的32位。 作用:确定IP地址的网络位 什么是网络号? 又称网段。就是IP地址的主机位全为0。 什么是直接广播? 就是主机位全为1 。 什么是全网广播 255.255.255.255 。 直接广播和全网广播的...
  • 计算机复试面试题总结

    万次阅读 多人点赞 2019-03-07 20:06:56
    支持面向对象面向过程的开发。 2.C++的异常处理机制? 抛出异常捕捉异常进行处理。(实际开发) 3.cc++,java的区别? c是纯过程,c++是对象加过程,java是纯面向对象的 4.纯虚函数? 被virtual修饰的...
  • 、瀑布模型 1.1什么是瀑布模型 1.2特点 1.3优缺点 1.4客户需求 二、快速原型模型 2.1什么是快速原型模型 2.2优缺点 2.3快速原型模型的思想产生、原理及运用方式 2.4类型 2.5开发步骤 三、增量模型 3.1...
  • IP子网划分和规划

    千次阅读 2018-07-31 17:36:24
    IP地址分类有类地址无类地址。 有类地址就是标准的IP地址 无类地址:是对IP地址进行子网划分   子网划分:将网络划分适当大小的多个子网。...为什么要划分子网?...IP地址经过一次子网划分之后,变为由三部分...
  • 软件测试_笔记(完整版)

    万次阅读 多人点赞 2018-07-02 08:51:28
    广义的软件测试定义:人工或自动地运行或测定某系统的过程,目的在于检验它是否满足规定的需求或弄清预期结果实际结果间的差别 为什么要做软件测试 发现软件缺陷 功能错 功能遗漏 超出需求部分(画蛇添足) ...
  • ip网段子网划分

    千次阅读 2018-03-13 15:45:29
    最近在学习Linux运维知识。...IP分配及网段划分 1、IP我们先来了解一下3类常用的IP A类IP段 0.0.0.0 到127.255.255.255 B类IP段 128.0.0.0 到191.255.255.255 C类IP段 192.0.0.0 到223.255....
  • 1.留出法(hold-out)直接将数据集D...在使用留出法时,一般要采用若干随机划分、重复进行实验评估后取平均值作为留出法的评估结果。通常情况下我们将2/3~4/5的样本划分出来用于训练。使用sklearn.model_selectio...
  • SPSS(十九)SPSS之时间序列模型(图文+数据集)

    万次阅读 多人点赞 2019-06-17 22:32:38
    SPSS(十九)SPSS之时间序列模型(图文+数据集) 时间序列是指将同一统计指标的数值按其发生的时间先后顺序排列...在大数据时代,时间序列分析已经成为 AI 技术的个分支,通过将时间序列分析与分类模型相结合,更好...
  • H.266/VVC的编码结构划分

    千次阅读 2020-02-15 21:13:24
    对于帧具有三通道的图像,CTU由个N×N的亮度样本块两个相应的色度样本块组成。图1显示了个图片被划分为CTU的示例。 在VVC中为了适应4k、8k等视频编码的需要,CTU中的亮度块的最大允许尺寸被指定为128×128...
  • 机器学习算法 综述(入门)

    万次阅读 多人点赞 2019-06-16 21:59:28
    学习了个学期机器学习算法,从什么都不懂到对十个机器学习算法有一定的了解,下面总结一下十大机器学习算法,从算法的概念、原理、优点、缺点、应用等方面来...它同时适用于分类变量和连续因变量。在这个算法中...
  • 子网划分和子网掩码的计算方法

    千次阅读 2015-07-22 17:28:39
    看到有好多的人都不会子网划分和子网掩码的计算方法(其实我也不会) 经过翻箱倒柜终于找到关于子网的来历和详细的计算方法。 在这里给大家分享下! Internet组织机构定义了五种IP地址,用于主机的有A、B、C三类...
  • 小波变换小波阈值法去噪

    万次阅读 多人点赞 2017-07-24 18:05:38
    小波变换是种信号的时间——尺度(时间——频率)分析方法,它具有多分辨分析的特点,而且在时频两域都具有表征信号局部特征的能力,。在小波分析中经常用到近似细节,近似表示信号的高尺度,即低频信息;细节...
  • 机器学习中首要环节就是数据集的处理,其中数据集的处理从个人理解(如有错误敬请谅解)的角度来说包括两个方面:数据集划分和数据清理。其中数据集划分是指训练集、验证集和测试集的数据类别划分;数据清理是指数据的...
  • TCP/IP--划分子网构造超网

    千次阅读 2017-09-28 19:04:26
    接着上篇,继续分享网际协议IP的内容–划分子网构造超网。 那么,为什么要划分子网构造超网? 我们知道,分类的IP地址主要有A类、B类、C类三类(D类为多播地址),其中: A类拥有超过65535台主机 B...
  • 支持向量机SVM、支持向量回归SVR详细推导

    万次阅读 多人点赞 2019-06-30 09:31:52
    文章详细介绍了支持向量机SVM及其拓展,支持向量回归SVR.并从线性分类非线性分类的角度出发,详细推导了硬间隔、软间隔核函数的支持向量机。
  • .原理 K均值聚类 最常见的划分方法是K均值聚类分析。从概念上讲, K均值算法如下: (1) 选择K个中心点(随机选择K行); (2) 把每个数据点分配到离它最近的中心点; (3) 重新计算每类中的点到该类中心点距离...
  • 对于ip地址我们前面通过多文章,大家都有一定的理解,不过通过的留言,有部分朋友还是对子网掩码、ip地址的网段有些疑问,那么今天我们起来...子网掩码只有个作用,就是将某个IP地址划分成网络地址主机地址...
  • 当采用亮色度独立划分树时,亮度CTB被种编码树结构划分为luma-CUs,色度CTB被另种编码树结构划分为chroma-CUs。这意味着I slice中的CU可以由亮度分量的编码块或两个色度分量的编码块组成,并且P或B slice中的CU...
  • 决策树与随机森林初探

    万次阅读 2018-08-19 13:11:04
    决策树的最关键的问题,如何选择划分属性的顺序才能使得决策树的平均性能最好 举例: 这堆西瓜的熵是Ent(D),按照某种属性划分之后这堆西瓜的熵是Ent(D′),Ent(D′) &amp;amp;amp;amp;amp;amp;amp;amp;...
  • COMSOL网格划分技巧总结

    千次阅读 2021-05-04 15:36:56
    在对马赫曾德尔型光学传感器进行模拟仿真时,在采用自动物理场自动控制网格-极细化的情况下透射谱曲线仍不理想,因此需要手动划分网格来对其进行更精细的剖分。 手动划分的基本原则是在作用边界,热点,曲边处做...
  • sklearn中的交叉验证数据划分

    千次阅读 2017-11-27 16:38:28
    给定个训练数据集合,寻找个模型去fit这个训练数据,如果在全部的训练数据上训练获得模型并且在全部的训练数据上测试模型,则测试结果会很好; 但是对于未知的数据泛化效果会很不好,即过拟合。所以需要在不同...
  • IP地址 网段的划分

    千次阅读 2019-06-24 22:52:23
    IP子网掩码我们都知道,IP是由四段数字组成,在此,我们先来了解一下3类常用的IP A类IP段 0.0.0.0 到127.255.255.255 B类IP段 128.0.0.0 到191.255.255.255 C类IP段 192.0.0.0 到223.255.255.255 XP默认...
  • 再谈子网划分划分示例

    千次阅读 2013-05-28 08:49:42
    现从我今年出版的新作《深入理解计算机网络》中摘录该部分内容,做一次集中解答,希望对这些朋友有用。可点击这里,了解几百名真实读者对本书的评价:http://winda.blog.51cto.com/55153/1205295 8.2.3 VLSM子网...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 138,878
精华内容 55,551
关键字:

一次划分和连续划分