Welcome to

Poan

全部
分类

Apr 5, 2018
wait、notify——生产者消费者
在Java中，wait、notify、notifyAll是Object的方法，在java中任何对象都可以作为锁，而这几个方法必须得在获取锁以后才能使用，否则会报InterruptedException异常在生产者和消费者模式中，假设：生产者每生产一个（也可以是诺干个，一个简单点）产品，就会等待他人消费以免浪费生产力；而消费者则是会等待生产者通知自己产品已产出，然后自己便去消费，随后通知生产者缺货了赶紧生产；这里比较简单的方式就是用java对象的wait和notify实现： package com.git.poan; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; /** * Created by poan on 2018/04/12. */ public class WaitNotityTest { public static void bake() { synchronized (WaitNotityTest.class) { for...
Read More
Apr 5, 2018
数据结构—AVL搜索树
BST在极端情况下，比如按顺序插入1，2，3，4，5，6，7；那么这几个元素都会变成上一个元素的右节点，，这样搜索起来复杂度又变成线性的了；在基于BST的约束上，新增了一个约束，来保证树的搜索不会恶化成线性的：根结点的左子树和右子树高度距离不超过1 为了实现上述这一点，基于BST需要进行以下改造：在节点上会多记录一个平衡因子的属性，每个节点的平衡因子都是由其直系子节点的左右分配情况而来；比如叶子节点的平衡因子就是0。没新增一个节点，需要更新其父节点的平衡因子，递归更新到根结点为止如果根结点的平衡因子大于一，需要对树进行旋转： 3.1 旋转的过程类似于BST寻找继任者的过程，如果树失衡了，需要将根结点及其偏轻的子树与其偏重的子树割； 3.2 偏重的子树会成为新的根，而偏轻的那一根子树，需要在新的根中找到合适的位置插入： 3.2.1 偏轻的那根树，观其方向，理论上只要取代新的根同一个方向的节点，并将被取代的节点插入到取代后的位置即可； 3.2.2 然而有种特殊的现象，新的根走势为’<’或’>’字型，这样的化会死循环，，为了解决这种现象，先将’<’或’>’转为’'或’/’，这样旋转才能生效；以上的规则都是由实际的二叉树图表推导的；AVL树基于BST稍微修改即可得到，但是很少用到AVL，每次插入都递归更新向上节点的平衡因子，并且根结点的平衡因子如果大于 1 的话，还要旋转，性能太低；虽然实现了绝对的平衡，但是带来的性能影响太大；左旋和右旋比较抽象，实际上就是在BST寻找继任者的基础上改的
Read More
Apr 5, 2018
数据结构—二叉搜索树
二叉搜索树又叫BST，这种结构主要是为了与列表搜索和哈希搜索区别开； BST这种结构，不同于列表一味将元素按递增或递减的顺序排列，而是将元素在插入到树中位置时，就先为其找好适当的位置插入，待需要查询的时候，不需要像列表查询那样需要从头找到尾（或者二分法查找）； BST的实现，其实只要知道以下几个条件即可自己实现：树中只能有一个根结点每个节点最多能有两个子节点每个节点的左子节点必须小于自己，右节点必须大于自己根据以上三个条件，就可以完成BST了，不过实际上流程还是比较复杂，网上给的教程都是噼里啪啦给一堆图；个人感觉用流程图更清晰： put方法： delete方法：在删除node的方法中，判断node是否为子节点，如果不是叶子节点，那么删除了node时需要考虑它的子节点怎么处理；处理的方式就是在node子节点中寻找一位继任者来代替node的位置；看似很麻烦，其实由于BST的三个约束，寻找继任者很简单：删除node，node的继任者必须满足继任者大于原node的左节点，小于等于原node的右节点；对于寻找继任者，感觉只要看看二叉堆的性质即可，二叉堆的最左边的左节点是最小的（最左边意思就是它已经没有子左节点，不管它有没有子右节点）实现以上所说的Node结构，以及BST树中核心的put和delete方法，以及一些辅助方法，就能实现一个二叉搜索树了，至于具体实现网上已经很多就不写了。
Read More
Apr 4, 2018
设计模式小记&重温数据结构
前几篇将使用工作中到的设计模式进行一些归纳，设计模式只是一些套路、招式，可以用来简化代码，提高代码阅读性；提高代码的阅读性这一点对于编写代码的人一开始可能会有异议，感觉有时候用了设计模式反而把代码变得更复杂，频繁的使用继承、实现、多态，可能让人懵逼。对于查看代码的人来说，使用了设计模式的代码，结构更清晰，更方便别人和自己后期的修改在使用上，不需要强行硬套模式，一般都是先实现了功能，然后发现哪个地方有可以改进的地方，尝试着使用模式简化提炼一下，时间久了应该就能写出好看的代码了，至少我是这样鼓励自己的…… 下一步，准备将之前看的Python版数据结再复习一遍；用Java和c实现数据结构比较麻烦，国外现在数据结构这门课都用Python来讲解，附上一本好书的在线连接《Problem Solving with Algorithms and Data Structures using Python》
Read More
Apr 4, 2018
设计模式——单例模式中的DCL运用
单例模式如果说最常用到的，应该就是枚举吧，枚举中的构造器即是单例，并且枚举的每个实例在实现上都是静态的；或者手写单例，通过静态内部类或者双检索；双检索双检索实现的单例，主要是因为该实现方式是基于懒汉式，而懒汉又有线程安全问题，比如以下场景：某次活动发放了数张邀请码，每个邀请码只能用一次，在竞态环境下如何保证该邀请码只能被使用一次 package com.git.toolbox.util; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.locks.ReadWriteLock; import java.util.concurrent.locks.ReentrantReadWriteLock; /** * Created by poan on 2017/11/03. */ class InviteCode { /** * 1 已经使用 0...
Read More