• 基础知识
  • AOP的3个实现层面
  • AOP的3个实现层面
  • 实现机制比较
  • AOP的基础
    • Joinpoint
    • Pointcut
    • Advice
  • JoinPoint、Pointcut、Advice之间的关系
• 动态字节码生成
  • 原理
• 字节码修改
• 字节码转换器
  • 配置
  • 执行结果

基础知识

AOP的3个实现层面

AOP就是面向切面编程，可以从3个层面来实现AOP

1. 编译期：修改源代码。
2. 字节码加载前：修改字节码。
3. 字节码加载后：动态创建代理类的字节码。

   AOP的3个实现层面

   

   实现机制比较

   

• 引言
• 概念
  • Moore教授例子
  • 特点
  • 概念
  • 坏字符
  • 好后缀
• 代码
  • C++代码
  • Java代码1
  • Java代码2
  • Java代码3
• 代码解释
  • 坏字符
  • 好后缀
  • 改进suff方法
  • suff数组

引言

KMP它并不是效率最高的算法，实际采用并不多。各种文本编辑器的”查找”功能（Ctrl+F），大多采用Boyer-Moore算法。

Boyer-Moore算法不仅效率高，而且构思巧妙，容易理解。1977年，德克萨斯大学的Robert S. Boyer教授和J Strother Moore教授发明了这种算法。
在用于查找子字符串的算法当中，BM（Boyer-Moore）算法是目前被认为最高效的字符串搜索算法。 一般情况下，比KMP算法快3-5倍。该算法常用于文本编辑器中的搜索匹配功能，比如大家所熟知的GNU grep命令使用的就是该算法，这也是GNU grep比BSD grep快的一个重要原因。

• 引言
  • 思想
  • 程序
• 概念
• 思想
  • 部分匹配表
  • 如何计算Next[]
    • k值定义
  • Next的核心思想
• 优化
• 计算
• 程序代码
  • Java版本

引言

简单匹配模式算法的效率不高，原因在于匹配过程中有回溯。
示例：从左到右一个个匹配，如果这个过程中有某个字符不匹配，就跳回去，将模式串向右移动一位。

我们只需要比较i指针指向的字符和j指针指向的字符是否一致。如果一致就都向后移动，如果不一致，如下图：

A和E不相等，那就把i指针移回第1位（假设下标从0开始），j移动到模式串的第0位，然后又重新开始这个步骤：

思想

在S[i]!=P[j]达到失配点，主串S要回到原来的i+1的位置（回溯），模式串P要回到第一个字符的位置，然后继续比较。每次到达失配点时，串S和串P的指针i，j都要回溯，因此效率比较低。

• JDK7自带工具目录
• Jstat
  • 命令
    • interval
    • count
    • -options
      • class类加载情况统计
      • compiler查看HotSpot中即时编译器编译情况的统计
      • GC JVM中堆的垃圾收集情况的统计
      • gccapacity新生代、老生代及持久代的存储容量情况
      • gccause用于查看垃圾收集的统计情况（这个和-gcutil选项一样）
      • gcnew新生代垃圾收集的情况
      • gcnewcapacity新生代的存储容量情况
      • gcold老生代及持久代发生GC的情况
      • gcoldcapacity老生代的存储容量情况
      • gcpermcapacity持久代的存储容量情况
      • gcutil新生代、老生代及持代垃圾收集的情况
      • printcompilation HotSpot编译方法的统计
• Jmap命令
  • histo
    • 命令
    • 注意
  • heap
    • 命令
  • dump
    • 命令
    • 注意
  • permstat
    • 命令
    • 注意
• 4 内存分析工具（Memory Analyzer Tool，MAT）
  • 修改参数配置
  • 分析文件

JDK7自带工具目录

1
2
3
4

C:\Users\Administrator>java -version
java version "1.7.0_76"
Java(TM) SE Runtime Environment (build 1.7.0_76-b13)
Java HotSpot(TM) 64-Bit Server VM (build 24.76-b04, mixed mode)

命令 | 说明
—|—
appletviewer | 用于运行并浏览applet小程序。
extcheck | 扩展检测工具，主要用于检测指定jar文件与当前已安装的Java SDK扩展之间是否存在版本冲突。
idlj | IDL转Java编译器(IDL-to-Java Compiler)，用于为指定的IDL文件生成Java绑定。IDL意即接口定义语言(Interface Definition Language)。
jar | jar文件管理工具，主要用于打包压缩、解压jar文件。
jarsigner | jar密匙签名工具。
java | Java运行工具，用于运行.class字节码文件或.jar文件。
javac | Java编译工具(Java Compiler)，用于编译Java源代码文件。
javadoc | Java文档工具，主要用于根据Java源代码中的注释信息生成HTML格式的API帮助文档。
javafxpackager | JavaFX包装器，用于执行与封装或签名JavaFX应用有关的任务。JDK 8u20已经迁移此工具到javapackager。
javah | Java头文件工具，用于根据Java类生成C/C++头文件和源文件(主要用于JNI开发领域)。
javap | Java反编译工具，主要用于根据Java字节码文件反汇编为Java源代码文件。
javapackager | 执行针对Java应用程序和JavaFX应用程序的打包和签名的任务。包含了javafxpackager的功能。
jcmd | Java 命令行(Java Command)，用于向正在运行的JVM发送诊断命令请求。
jconsole | 图形化用户界面的监测工具，主要用于监测并显示运行于Java平台上的应用程序的性能和资源占用等信息
jdeps | 用于分析Java class的依赖关系
jdb | Java调试工具(Java Debugger)，主要用于对Java应用进行断点调试
jhat | Java堆分析工具(Java Heap Analysis Tool)，用于分析Java堆内存中的对象信息。
jinfo | Java配置信息工具(Java Configuration Information)，用于打印指定Java进程、核心文件或远程调试服务器的配置信息。
jjs | 对Nashorn引擎的调用。Nashorn是基于Java实现一个轻量级高性能的JavaScript运行环境。
jmap | Java内存映射工具(Java Memory Map)，主要用于打印指定Java进程、核心文件或远程调试服务器的共享对象内存映射或堆内存细节。
jmc | Java任务控制工具(Java Mission Control)，主要用于HotSpot JVM的生产时间监测、分析、诊断。开发者可以使用jmc命令来创建JMC工具。
jps | JVM进程状态工具(JVM Process Status Tool)，用于显示目标系统上的HotSpot JVM的Java进程信息。
jrunscript | Java命令行脚本外壳工具(command line script shell)，主要用于解释执行javascript、groovy、ruby等脚本语言。
jsadebugd | Java可用性代理调试守护进程(Java Serviceability Agent Debug Daemon)，主要用于附加到指定的Java进程、核心文件，或充当一个调试服务器。
jstack | Java堆栈跟踪工具，主要用于打印指定Java进程、核心文件或远程调试服务器的Java线程的堆栈跟踪信息。
jstat | JVM统计监测工具(JVM Statistics Monitoring Tool)，主要用于监测并显示JVM的性能统计信息，包括gc统计信息。
jstatd | jstatd(VM jstatd Daemon)工具是一个RMI服务器应用，用于监测HotSpot JVM的创建和终止，并提供一个接口，允许远程监测工具附加到运行于本地主机的JVM上。
jvisualvm | JVM监测、故障排除、分析工具，主要以图形化界面的方式提供运行于指定虚拟机的Java应用程序的详细信息。
keytool | 密钥和证书管理工具，主要用于密钥和证书的创建、修改、删除等。主要用于获取或缓存Kerberos协议的票据授权票据。允许用户查看本地凭据缓存和密钥表中的条目(用于Kerberos协议)。Kerberos密钥表管理工具，允许用户管理存储于本地密钥表中的主要名称和服务密钥。
native2ascii | 本地编码到ASCII编码的转换器(Native-to-ASCII Converter)，用于”任意受支持的字符编码”和与之对应的”ASCII编码和(或)Unicode转义”之间的相互转换。
orbd | 对象请求代理守护进程(Object Request Broker Daemon)，它使客户端能够透明地定位和调用位于CORBA环境的服务器上的持久对象。
pack200 | JAR文件打包压缩工具，它可以利用Java类特有的结构，对普通JAR文件进行高效压缩，以便于能够更快地进行网络传输。这是微软提供的对象包装程序，用于对象安装包。
policytool | 策略工具，用于管理用户策略文件(.java.policy)。
rmic | Java RMI 编译器，为使用JRMP或IIOP协议的远程对象生成stub、skeleton、和tie类，也用于生成OMG IDL。
rmid | Java RMI 激活系统守护进程，rmid启动激活系统守护进程，允许在虚拟机中注册或激活对象。
rmiregistry | Java 远程对象注册表，用于在当前主机的指定端口上创建并启动一个远程对象注册表。
schemagen | XML schema生成器，用于生成XML schema文件。
serialver | 序列版本命令，用于生成并返回serialVersionUID。
servertool | Java IDL 服务器工具，用于注册、取消注册、启动和终止持久化的服务器。
tnameserv | Java IDL瞬时命名服务。
unpack200 | JAR文件解压工具，将一个由pack200打包的文件解压提取为JAR文件。
wsgen | XML Web Service 2.0的Java API，生成用于JAX-WS Web Service的JAX-WS便携式产物。
wsimport | XML Web Service 2.0的Java API，主要用于根据服务端发布的wsdl文件生成客户端存根及框架。
xjc | 主要用于根据XML schema文件生成对应的Java类。

Jstat

Jstat用于监控基于HotSpot的JVM，对其堆的使用情况进行实时的命令行的统计，使用jstat我们可以对指定的JVM做如下监控：

• 类的加载及卸载情况。
• 查看新生代、老生代及持久代的容量及使用情况。
• 查看新生代、老生代及持久代的垃圾收集情况，包括垃圾回收的次数及垃圾回收所占用的时间。
• 查看新生代中Eden区及Survior区中容量及分配情况等。

jstat工具特别强大，它有众多的可选项，通过提供多种不同的监控维度，使我们可以从不同的维度来了解到当前JVM堆的使用情况。详细查看堆内各个部分的使用量，使用的时候必须加上待统计的Java进程号，可选的不同维度参数以及可选的统计频率参数。它主要是用来显示GC及PermGen相关的信息。

• 介绍
• 一只探路猫
• 简化搜索区域
• Open和Closed列表
• 路径增量
• 关于G值
• 关于H值
• A星算法
• 猫的路径
  • 第一步
  • 第二步
  • 第三步
  • 第四步
  • 第五步
  • 第六步
  • 第七步
  • 第八步
• 一只有远见的猫
  • object-c
  • java
    • 上下左右寻找，未做斜对角线寻找路径
    • 上下左右，斜对角线寻找
• 改进
  • 优化速度
    • 排序查找算法
    • 二叉树查找算法
  • 总结

转帖：A*寻路算法介绍

介绍

你是否在做一款游戏的时候想创造一些怪兽或者游戏主角，让它们移动到特定的位置，避开墙壁和障碍物呢？
如果是的话，请看这篇教程，我们会展示如何使用A寻路算法来实现它！
在网上已经有很多篇关于A寻路算法的文章，但是大部分都是提供给已经解基本原理的高级开发者的。
本篇教程将从最基本的原理讲起。我们会一步步讲解A寻路算法，幷配有很多图解和例子。
不管你使用的是什么编程语言或者操作平台，你会发现本篇教程很有帮助，因为它在非编程语言的层面上解释算法的原理。稍后，会有一篇教程，展示如何在Cocos2D iPhone 游戏中实现A算法。
现在找下到达一杯咖啡因饮料和美味的零食的最短路径，开始吧！

一只探路猫

让我们想象一下，有一款游戏，游戏中一只猫想要找到获取骨头的路线。
“为什么会有一只猫想要骨头？！”你可能会这么想。在本游戏中， 这是一只狡猾的猫，他想捡起骨头给狗，以防止被咬死！
现在想像一下下图中的猫想找到到达骨头的最短路径。

不幸的是，猫不能直接从它当前的位置走到骨头的位置，因为有面墙挡住去路，而且它在游戏中不是一只幽灵猫！
游戏中的猫同样懒惰，它总是想找到最短路径，这样当他回家看望它的女朋友时不会太累。
但是我们如何编写一个算法计算出猫要选择的那条路径呢？A*算法拯救我们！

简化搜索区域

寻路的第一步是简化成容易控制的搜索区域。
怎么处理要根据游戏来决定。例如，我们可以将搜索区域划分成像素点，但是这样的划分粒度对于我们这款基于方块的游戏来说太高（没必要）。
作为代替，我们使用方块（一个正方形）作为寻路算法的单元。其他的形状类型也是可能的（比如三角形或者六边形），但是正方形是最简单并且最适合我们需求的。
像那样去划分，我们的搜索区域可以简单的用一个地图大小的二维数组去表示。所以如果是25*25方块大小的地图，我们的搜索区域将会是一个有625个正方形的数组。如果我们把地图划分成像素点，搜索区域就是一个有640，000个正方形的数组（一个方块是32*32像素）！
现在让我们基于目前的区域，把区域划分成多个方块来代表搜索空间（在这个简单的例子中，7*6个方块 = 42 个方块）。

• 第57条、只针对异常的情况才使用异常
  • 总结
• 第58条、对可恢复的异常使用检测性异常，对编程错误使用运行时异常
  • 受检异常
  • 运行时异常
  • 错误
  • 总结
• 第59条、避免不必要地使用检测性异常
  • 总结
• 第60条、优先使用标准的异常
  • 总结
• 第61条、抛出与抽象相对应的异常
  • 总结
• 第62条、每个方法抛出的异常都要有文档
• 第63条、在细节消息中包含能捕获失败的信息
  • 总结
• 第64条、努力使失败保持原子性
  • 总结
• 第65条、不要忽略异常
  • 总结

第57条、只针对异常的情况才使用异常

不知道你否则遇见过下面的代码。

1
2
3
4
5
6

try {
       int i = 0;3
       while (true)    
           range[i++].climb();
}catch (ArrayIndexOutOfBoundsException e) {
}

这段代码的意图不是很明显，其本意就是遍历变量range[]中的每一个元素，并执行元素的climb()，当下标超出range[]的长度时，将会直接抛出ArrayIndexOutOfBoundsException异常，catch代码块将会捕获到该异常，但是未作任何处理，只是将该错误视为正常工作流程的一部分来看待。这样的写法确实给人一种匪夷所思的感觉，让我们再来看一下修改后的写法。

1
2
3

for (Mountain m : range) {
        m.climb();
 }

和之前的写法相比其可读性不言而喻。那么为什么又有人会用第一种写法呢？显然他们是被误导了，他们企图避免for-each循环中JVM对每次数组访问都要进行的越界检查。这无疑是多余的，甚至适得其反，因为将代码放在try-catch块中反而阻止了JVM的某些特定优化，至于数组的边界检查，现在很多JVM实现都会将他们优化掉了。在实际的测试中，我们会发现采用异常的方式其运行效率要比正常的方式慢很多。
除了刚刚提到的效率和代码可读性问题，第一种写法还会掩盖一些潜在的Bug，假设数组元素的climb()中也会访问某一数组，并且在访问的过程中出现了数组越界的问题，基于该错误，JVM将会抛出ArrayIndexOutOfBoundsException异常，不幸的是，该异常将会被climb()之外catch语句捕获，在未做任何处理之后，就按照正常流程继续执行了，这样Bug也就此被隐藏起来。
这个例子的教训很简单：”异常应该只用于异常的情况下，它们永远不应该用于正常的控制流”。虽然有的时候有人会说这种怪异的写法可以带来性能上的提升，即便如此，随着平台实现的不断改进，这种异常模式的性能优势也不可能一直保持。然而，这种过度聪明的模式带来的微妙的Bug，以及维护的痛苦却依然存在。
根据这条原则，我们在设计API的时候也是会有所启发的。设计良好的API不应该为了正常的控制流而使用异常。如Iterator，JDK在设计时充分考虑到这一点，客户端在执行next()之前，需要先调用hasNext()已确认是否还有可读的集合元素，见如下代码。

1
2
3

for (Iterator i = collection.iterator(); i.hasNext(); ) {
    Foo f = i.next();
}

如果Iterator缺少hasNext()，改为下面的写法。

1
2
3
4
5
6

try {
    Iterator i = collection.iterator();
    while (true)
       Foo f = i.next();
 }catch (NoSuchElementException e) {
 }

这应该非常类似于本条目开始时给出的遍历数组的例子。在实际的设计中，还有另外一种方式，即验证可识别的错误返回值，然而该方式并不适合于此例，因为对于next()，返回null可能是合法的。那么这两种设计方式在实际应用中有哪些区别呢？

1. 如果是缺少同步的并发访问，或者可被外界改变状态，使用可识别返回值的方法是非常必要的，因为在测试状态(hasNext())和对应的调用(next())之间存在一个时间窗口，在该窗口中，对象可能会发生状态的变化。因此，在该种情况下应选择返回可识别的错误返回值的方式。
2. 如果状态测试方法(hasNext())和相应的调用方法(next())使用的是相同的代码，出于性能上的考虑，没有必要重复两次相同的工作，此时应该选择返回可识别的错误返回值的方式。
3. 对于其他情形则应该尽可能考虑”状态测试”的设计方式，因为它可以带来更好的可读性。

   总结

   需要异常的地方才使用异常，不能使用异常去控制正常的业务流程。

• 基础算法
• Minimax
  • 问题
  • 基本思路
  • 解题
  • Alpha-beta剪枝
  • 针对2048游戏的实现
    • 建模
    • 格局评价
    • 单调性
    • 平滑性
    • 空格数
    • 孤立空格数
    • 对对方选择的剪枝
    • 搜索深度
    • 算法的改进
• 参考文献

1

针对目前火爆的2048游戏，有人实现了一个AI程序，可以以较大概率（高于90%）赢得游戏，并且作者在stackoverflow上简要介绍了AI的算法框架和实现思路。但是这个回答主要集中在启发函数的选取上

针对目前火爆的2048游戏，有人实现了一个AI程序，可以以较大概率（高于90%）赢得游戏，并且作者在stackoverflow上简要介绍了AI的算法框架和实现思路。但是这个回答主要集中在启发函数的选取上，对AI用到的核心算法并没有仔细说明。这篇文章将主要分为两个部分，第一部分介绍其中用到的基础算法，即Minimax和Alpha-beta剪枝；第二部分分析作者具体的实现。

• 优点
• 优化思路

优点

增强代码的可读性，可维护性，并降低错误的可能性。

优化思路

1. 要使局部变量的作用域最小化，最有力的方法就是在第一次使用它的地方声明，这样有便于读者集中注意力，不容易分散；如果在之前申明，阅读者很容易忘记变量的类型和变量的意义。
2. 过早的声明变量，使得变量的作用域过早的扩展（作用域扩大），变量销毁的时间过于晚。
3. 变量的作用域从申明点开始，到这个方法的结束。
4. 局部变量声明的时候，都应该要先初始化变量。比如，A a;写成A a=null;相对更好，更直观的看到a = null。
5. 循环的使用，for和while；for比while好用。
   for变量定义在for的作用域内部，while则在外部。这样容易造成变量使用错误，而不会报异常。
   for更简短，增强可读性。
6. 将局部变量的作用域最小化。如果一个方法有2个操作（不只是业务），可以拆分成2个方法，变量不会冲突，耦合度低。（平时开发也是这样，耦合度低，扩展性好，可读性强，好维护）

• 概述
• 解题思路
• 程序代码
  • C++代码
  • Java代码
  • 活动队列

概述

有一批共n个集装箱要装上2艘载重量分别为c1，c2的轮船，其中集装箱i的重量为wi，且要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。可证明，采用如下策略可以得到一个最优装载方案：先尽可能的将第一艘船装满，其次将剩余的集装箱装到第二艘船上。

解题思路

1. 首先将第一艘轮船尽可能装满。
2. 将剩余的集装箱装上第二艘轮船。

在算法的while循环中，首先检测当前扩展结点的左儿子结点是否为可行结点。如果是则将其加入到活结点队列中。然后将其右儿子结点加入到活结点队列中(右儿子结点一定是可行结点)。2个儿子结点都产生后，当前扩展结点被舍弃。
活结点队列中的队首元素被取出作为当前扩展结点，由于队列中每一层结点之后都有一个尾部标记-1，故在取队首元素时，活结点队列一定不空。当取出的元素是-1时，再判断当前队列是否为空。如果队列非空，则将尾部标记-1加入活结点队列，算法开始处理下一层的活结点。
节点的左子树表示将此集装箱装上船，右子树表示不将此集装箱装上船。设bestw是当前最优解；ew是当前扩展结点所相应的重量；r是剩余集装箱的重量。则当ew+r<bestw时，可将其右子树剪去，因为此时若要船装最多集装箱，就应该把此箱装上船。另外，为了确保右子树成功剪枝，应该在算法每一次进入左子树的时候更新bestw的值。
为了在算法结束后能方便地构造出与最优值相应的最优解，算法必须存储相应子集树中从活结点到根结点的路径。为此目的，可在每个结点处设置指向其父结点的指针，并设置左、右儿子标志。
找到最优值后，可以根据parent回溯到根节点，找到最优解。

• 概念
  • 回溯算法与分支限界法的不同之处
• 基本思想
  • 队列式(FIFO)分支限界法
    • 搜索策略
  • 优先队列式分支限界法
    • 搜索策略
• 示例
  • 步骤

概念

分支限界算法类似于回溯算法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。

回溯算法与分支限界法的不同之处

求解目标

• 回溯算法的求解目标：是找出T中满足约束条件的所有解。
• 分支限界算法的求解目标：是找出满足约束条件的一个解，或者是在满足约束条件的解中找出使某一目标函数值达到极大或者极小的解。（即：最优解）

搜索方式：由于求解目标不同，导致分支限界法和回溯法在解空间树T上的搜索方式也不相同。

• 回溯法：以深度优先的方式搜索解空间树T。
• 分支限界法：以广度优先的方式或者以最小耗费优先的方式搜索解空间树T。