码力欧

GC

引用计数算法，记录对象被引用的次数。
可达性分析算法，通过一系列的“GC Roots” 根对象作为开始节点集，根据引用关系向下搜索，如果某个对象到 GC Roots 间没有任何引用链相连，表明对象不可达。

引用的概念

强引用，普遍的引用赋值。
软引用，在程序将要内存溢出的时候可以进行回收，回收后内存依然不够时则抛出异常。
弱引用，生存周期为下一次垃圾回收为止。
虚引用，被垃圾回收时触发一次系统通知。

垃圾收集算法 - 分代收集理论

内存区域
- 新生代
- 老年代
- 永久代（元空间、方法区）
回收类型
- 新生代收集
- 老年代收集
- 整堆收集
回收算法
- 标记 - 清除算法：将垃圾对象标记清除。容易造成内存空间碎片化，大对象申请问题，可能触发下一次垃圾收集动作。
- 标记 - 复制算法：半区复制，浪费空间。新生代 eden 空间、两块 survivor 空间，比例是 8:1，每次只使用 Eden空间和一块survivor空间，进行垃圾回收时会将存活对象复制到另一块 survivor 空间，然后清理掉已经用过的 Eden 空间和 survivor 空间，这样整个新生代利用了 90% 的空间。当一次垃圾回收的存活对象超过一个surivor空间时会通过分配担保机制使用老年代空间。
- 标记 - 整理算法：清除后将所有存活对象向内存空间一端移动。

经典垃圾收集器

https://juejin.im/post/5e197cc0e51d451c774dc56f

Java8 GC 默认使用的是 Parallel Scavenge (新生代) 和 Parallel Old (老年代)。

GC 日志

在启动命令中增加 -XX:+PrintGCDetails 输出详细GC日志。

/**
 * VM Args: -verbose:gc -Xms20M -Xmx20M -Xmn10M -XX:+PrintGCDetails -XX:SurvivorRatio=8
 * 堆内存溢出
 */
public class JvmDemo1 {

    public static void main(String[] args) {
        Random random = new Random();
        List<Long> list = new ArrayList<>();
        while (true) {
            list.add(random.nextLong());
        }
    }
}

1
2
3

[GC (Allocation Failure) [PSYoungGen: 8097K->1008K(9216K)] 11954K->10351K(19456K), 0.0091685 secs] [Times: user=0.02 sys=0.01, real=0.01 secs] 

[Full GC (Ergonomics) [PSYoungGen: 1008K->495K(9216K)] [ParOldGen: 9343K->9793K(10240K)] 10351K->10288K(19456K), [Metaspace: 3224K->3224K(1056768K)], 0.1013312 secs] [Times: user=0.16 sys=0.00, real=0.10 secs]

GC：表明进行了一次垃圾回收，前面没有Full修饰，表明这是一次Minor GC ,注意它不表示只GC新生代，并且现有的不管是新生代还是老年代都会STW。 Allocation Failure：表明本次引起GC的原因是因为在年轻代中没有足够的空间能够存储新的数据了。

JVM

JVM 堆栈配置参数

jps 查看 JVM 进程启动参数

默认元空间大小128M，最大元空间大小256M，初始化堆大小2G，最大堆大小5G，新生代512M，每个线程分配内存大小1M。eden空间和survivor空间的分配比率8:2，使用标记复制算法。

1
2

root@xxx:/usr/lib/jvm/java-8-oracle/bin# ./jps -v
1 xxx.jar -XX:MetaspaceSize=128m -XX:MaxMetaspaceSize=256m -Xms2048m -Xmx5048m -Xmn512m -Xss1024k -XX:SurvivorRatio=8 -XX:+UseConcMarkSweepGC -XX:+PrintGCDetails

jmap 生成堆快照

format 指定输出格式，live 指明是活着的对象，file 指定文件名。方便后面通过分析工具分析。

1	jmap -dump:live,format=b,file=dump.hprof pid

jstat 查看 JVM 进程已使用空间百分比

1
2
3

root@xxx:/usr/lib/jvm/java-8-oracle/bin# ./jstat -gcutil 1
  S0 S1 E O M CCS YGC YGCT FGC FGCT GCT
  0.00 72.37 40.12 3.59 96.52 94.68 113 4.433 0 0.000 4.433

S0 survivo0
S1 survivo1
E Eden空间
O 老年代
M 元空间使用率
CCS 压缩使用比例
YGC 新生代 GC 次数
YGCT 新生代 GC 耗时
FGC Full GC 次数
FGCT Full GC 耗时
GCT GC 耗时

jmap 查看进程堆的详细信息

jmap -heap pid

Attaching to process ID 3764, please wait...
Debugger attached successfully.
Server compiler detected.
JVM version is 25.171-b11

using thread-local object allocation.
Parallel GC with 8 thread(s) //采用Parallel GC 

Heap Configuration:
   MinHeapFreeRatio = 0 //JVM最小空闲比率 可由-XX:MinHeapFreeRatio=<n>参数设置， jvm heap 在使用率小于 n 时 ,heap 进行收缩
   MaxHeapFreeRatio = 100 //JVM最大空闲比率 可由-XX:MaxHeapFreeRatio=<n>参数设置， jvm heap 在使用率大于 n 时 ,heap 进行扩张 
   MaxHeapSize = 2095054848 (1998.0MB) //JVM堆的最大大小 可由-XX:MaxHeapSize=<n>参数设置
   NewSize = 44040192 (42.0MB) //JVM新生代的默认大小 可由-XX:NewSize=<n>参数设置
   MaxNewSize = 698351616 (666.0MB) //JVM新生代的最大大小 可由-XX:MaxNewSize=<n>参数设置
   OldSize = 88080384 (84.0MB) //JVM老生代的默认大小 可由-XX:OldSize=<n>参数设置 
   NewRatio = 2 //新生代：老生代（的大小）=1:2 可由-XX:NewRatio=<n>参数指定New Generation与Old Generation heap size的比例。
   SurvivorRatio = 8 //survivor:eden = 1:8,即survivor space是新生代大小的1/(8+2)[因为有两个survivor区域] 可由-XX:SurvivorRatio=<n>参数设置
   MetaspaceSize = 21807104 (20.796875MB) //元空间的默认大小，超过此值就会触发Full GC 可由-XX:MetaspaceSize=<n>参数设置
   CompressedClassSpaceSize = 1073741824 (1024.0MB) //类指针压缩空间的默认大小 可由-XX:CompressedClassSpaceSize=<n>参数设置
   MaxMetaspaceSize = 17592186044415 MB //元空间的最大大小 可由-XX:MaxMetaspaceSize=<n>参数设置
   G1HeapRegionSize = 0 (0.0MB) //使用G1垃圾收集器的时候，堆被分割的大小 可由-XX:G1HeapRegionSize=<n>参数设置

Heap Usage:
PS Young Generation //新生代区域分配情况
Eden Space: //Eden区域分配情况
   capacity = 89653248 (85.5MB)
   used = 8946488 (8.532035827636719MB)
   free = 80706760 (76.96796417236328MB)
   9.978989272089729% used
From Space: //其中一个Survivor区域分配情况
   capacity = 42467328 (40.5MB)
   used = 15497496 (14.779563903808594MB)
   free = 26969832 (25.720436096191406MB)
   36.49275037977431% used
To Space: //另一个Survivor区域分配情况
   capacity = 42991616 (41.0MB)
   used = 0 (0.0MB)
   free = 42991616 (41.0MB)
   0.0% used
PS Old Generation //老生代区域分配情况
   capacity = 154664960 (147.5MB)
   used = 98556712 (93.99100494384766MB)
   free = 56108248 (53.508995056152344MB)
   63.722715216167906% used

1819 interned Strings occupying 163384 bytes.

JVM调优

目的：对JVM内存的系统级的调优主要的目的是减少GC的频率和Full GC的次数，减少系统停顿时间。

步骤：

监控GC状态
生成 dump 文件
分析dump 文件（MAT 工具）
分析判断是否需要进行优化

Minor GC执行时间超过50ms；
Minor GC执行频繁，约10秒内一次；
Full GC执行时间超过1s；
Full GC执行频繁，高于10分钟1次；

调整GC类型和内存分配
不断分析调整

可视化分析工具 MAT

https://blog.csdn.net/wwlwwy89/article/details/74330544

设计原则

如果把设计模式理解为优秀软件系统模块设计的最小抽象，那么设计原则就是这些抽象的指导思想。目的是设计一个易于扩展和维护的系统。设计模式的六大原则有：

Single Responsibility Principle：单一职责原则
Open Closed Principle：开闭原则
Liskov Substitution Principle：里氏替换原则
Law of Demeter：迪米特法则
Interface Segregation Principle：接口隔离原则
Dependence Inversion Principle：依赖倒置原则

单一职责原则

应该有且只有一个原因引起类的变化，一个类只负责一个职责。一个功能应该要划分成多少个职责类去实现，并没有明显的限定。举例说明对于用户管理，用户信息管理和用户行为管理可以做初步拆分，用户信息管理又可以拆分成普通信息维护和敏感信息的维护。又比如用户发生一笔支付行为可以初步拆分为交易信息管理和支付信息管理。职责划分的粗细的影响因素有对于业务理解程度、项目开发阶段等，过粗会造成一个处理类包含太多职责，过细又会增加开发维护成本。单一职责是“高内聚低耦合”设计的一种实现形式，单一职责即为同一职责内部的内聚性，降低不同职责之间的耦合性。

里氏替换原则

描述继承关系，子类全部实现或继承父类方法，子类可以扩展父类方法实现，将子类替换父类不会产生异常。在重构角度来说如果多个子类拥有相同的行为，可以将相同行为提取到父类实现，子类调用扩展父类实现。在开发上基于“组合大于继承”的原则，通过定义实现接口的形成被其它类调用。违反这个原则不一定会产生严重后果，但是会对后面的开发维护造成困难。

开闭原则

描述的是对于需求产生变化后，软件实体部分应该进行扩展开发，避免修改。通过扩展实体行为来响应需求变化，而不是通过修改现有软件代码。

迪米特法则

描述的是一个对象应该进行减少对于其它对象的理解。通过封装我们可以屏蔽类内部逻辑，只提供足够用且少量的方法来给外部使用，降低对象之间的耦合性。当一个接口或者一个对象被公开，意味着后面我们进行开发和维护的时候很难再将这个对象收回，重构内部逻辑时也会更加困难。

接口隔离原则

描述的是建立单一的接口，不要建立庞大臃肿的接口，尽量细化接口，接口中的方法尽量行为统一，避免臃肿。对于支付接口来说，定义类通用支付方法，对于获取分期支付信息也属于支付行为的一个环节，但不是所有实体类必须要实现的，可以拆分出来。

依赖倒置原则

描述的是实现类之间不能直接发生依赖关系，其依赖关系是通过接口或者抽象类产生，即面向接口编程。实现类依赖接口或者抽象类，而接口或者抽象类不依赖实现类。

设计模式

https://design-patterns.readthedocs.io/zh_CN/latest/index.html

丹东之旅

发表于 2020-01-11

丹东是中国的一个边境小城市，在东三省的辽宁，与朝鲜隔鸭绿江相望。丹东春秋去会比较好，还有点景色可以看看，冬天的话来泡温泉吧，还可以顺便来一趟朝鲜游，带着护照来就好了。可惜的是因为一些原因无法泡温泉和去趟朝鲜。所以只是趁着年末逃离下北京，换个环境放松一下，其它的不重要了。

丹东是个有山有水有美食的地方，来这边可以沿着鸭绿江散步，好奇的望望对面神秘的社会主义同僚。去趟鸭绿江美术馆、抗美援朝纪念馆之类的地方看看当地的人文。鸭绿江断桥是一定要去的，走上去一点点感受下当年的气息和脚下的滚滚江水，一座见证历史的铁桥。丹东的🍓很出名，冬天来了可以尝尝，味道还是很甜的。还有当地著名的全州拌饭馆，超级好吃绝对不是吹的，还有有名参鸡汤，夜里的烧烤。。。想想又饿了。

这里的夜景也还不错，丹东这个城市挺小的，发展还不错，赶上季节好可以来这里吃海鲜~

语言栈转型经验谈

发表于 2019-12-01

背景介绍

近一年都在做语言栈的转型，也注意到周围很多公司都在做相似的事情，大概的路径是 Python -> Go -> Java，转型的起因也是有诸多的因素，像 Python 这种开发速度快，执行相对慢的语言更适合中小型项目，加上国内语言生态不够成熟，项目做大了会发现大家一刀切的转到其它语言上，当然这些说的是在做 web 后端方向上，Python 在数据分析和人工智能方向上还是势头很猛的。Go 可能还是因为它能承载的并发更高，性能更好而逐渐流行起来。在并发模型上 Java 原生 API 使用上确实做得不好驾驭，Go 则要相对好用很多。还有在某些垂直领域上，Java 的生态已经很成熟，其它语言栈上则需要自己造轮子，相应对于开发人员的水平要求就会低很多了。

在当前互联网领域，后端研发做 web 主要谈的还是通过抽象和建模来提高项目的可迭代性与可维护性，另一方面谈的是工程实现上的优化和性能上的优化。在这些后面依赖的则是中台来保证的基础服务综合稳定性。

在语言栈转型中也踩过一些坑，遇到过一些小问题，当然这些也得益于一个相对靠谱的方案来保证迁移的安全，基于这些经验总结一下，在以后的迁移中使问题可预见和避免采坑。

转型流程

首先要明确转型的三个开发流程 MRO (Migration, Reconstruction, Optimization)

迁移就是把原语言代码照着抄一遍到新语言项目上，按照新语言的工程实现风格来做就可以。
重构的目的是来提高项目代码的可维护性和可迭代性，让代码更加优雅和好读懂，可以放到迁移完成来做。
优化则可以是在模块依赖、调用关系、接口字段等方面调整来降低项目的复杂性和提高合理性。

然后看我们人力和时间是否充足，我想大部分情况下是不充足的，按照最短时间交付的原则，我们应该只做迁移流程，也就是说先对原有代码进行语言上的迁移，这样我们可以快速实现交付。在人力充沛的情况下可以配备两个小组，一个维护现有系统，一个主力开发新系统，或者说锁定需求全力开发新系统。在对快速交付更看中的行业里前一个方案更合适一些。

交付流程

在交付过程中的验证流程 单测验证 -> 测试环境功能验证 -> QA生产回测 -> 灰度验证 -> 完全上线。
只有功能和单测代码都迁移完才能算代码部分完成，需要优先保证单测行数覆盖率再去保证分支覆盖率，测试环境的功能验证需要覆盖所有 case 来保证大部分问题都被发现，然后进入小范围的灰度验证，之后逐步提高灰度比率直至完全上线。如果是纯读接口则可以直接进行异步校验，就是请求两遍，然后对比差异来不断的发现和修复 bug，直至问题收敛完全解决。
如果明确只做迁移，那么期间如果有发现旧逻辑的 bug 也不要管，这样才好去对比验证，验证通过上线后再去修复。只有通过明确目的和流程并且遵循这个流程做，才能更快的去交付。

验证方案

针对新代码的验证方案分为别为读写接口做不同的验证方案：

读接口：异步请求到新接口做接口响应值校验，打印出差异数据，然后不断修正逻辑。这样可以避免在线上灰度造成数据的不一致。
写接口：测试用例覆盖，然后测试环境验证，灰度回测，灰度验证，修复问题，继续灰度验证。

平稳交付

在整个交付的过程中，转型前后对 SLA 要提供一致的保证，可以看看下面的几个衡量标准：

服务可用性级别	服务正常运行时间	年宕机时间	日宕机时间
1	90%	36.5day	2.4hour
2	99%	3.65day	14min
3	99.9%	8.76hour	86sec
4	99.99%	52.6min	8.6sec
5	99.999%	5.26min	0.86sec
6	99.9999%	31.5sec	8.6msec

在线 MD 表格生成

一般 3 个 9 的可用性全年宕机时间约为 8.76 小时，针对不同系统不同用户规模对于系统可用性的要求不一样，边缘业务的要求可能会低一些，但是对于核心支付链路场景 TPS 可能不高，但是必须要求保证高可用级别。如何保证或者提升服务的 SLA 是我们接下来要探讨的目标，一般有下面两个影响因素：

MTBF (Mean Time Between Failures) 系统服务平均故障时间间隔
MTTR (Mean Time To Recover) 系统服务平均故障恢复时长

也就是说我们系统要尽可能的降低故障频率以及出现故障时能尽快的恢复。基于这两点我们在做系统平稳过渡时，要充分测试所有 case ，并且进行内部灰度方案和异步重试对比，发现异常立即回滚查找结局问题后再重新灰度。这里需要做到一键开关，数据可监控和追溯。

持续监控，感知系统稳定性的第一步就是监控，通过监控和系统日志来排查问题和及时响应处理。监控有两个层面，一个是基础设施提供的机器监控以及接口级别的响应稳定性监控，另一个是业务数据层面的多维度监控。系统日志按照等级大致分为 INFO 日志以及 ERROR 日志。

快速交付

关于快速交付，可以了解下敏捷开发，及早和持续不断的交付有价值的软件。关于 Scrum 开发的介绍可以看：什么是敏捷

现状及未来

基于公司现状考虑 nginx 不支持长时间和自定义灰度，所以 http 接口层没做改动，只是在内部逻辑上通过 rpc 服务转到新的系统中。基于以上要点可以做到功能的快速交付。截止此文撰写时间，语言栈转型已经将系统核心接口逻辑 100% 迁移到新的系统上，对于日常系统需求已经可以做到在新系统开发和接入了。后面要做的有以下几点：

将系统外围逻辑迁移到新系统；
不断监控降噪，细化监控粒度，继续提高服务的稳定性；
当前对于Python的花式“魔法” 硬翻译还需要不断重构和优化。
完善监控大盘，通过数据驱动来运营优化我们的流程；
项目复盘总结以及业务普及宣讲，提升人员对于业务细节的认知。

转型痛点

迁移后再做重构和优化过程。在迁移过程中有一个痛点是新需求过来了，要么锁定需求只做迁移，要么写两遍。基于人力情况可以选择一个小组同时写新旧系统或者一个小组维护新的一个小组维护旧的。
在转型过程中新需求过来有时要写两边，或者要把旧系统流量打到新系统接口上，常常在排查问题时遇到流量忘记转移的情况，所以在迁移过程要尽可能的快速交付上线。

反思

对于每一位工程师来说语言栈的转型既是挑战也是机遇，只有保持开放学习心态，及时调整和提升才能更好应对，同时增强自身软素质。
当前互联网环境下分布式是必经之地，而系统绝非 100% 可靠，每一个环节可能的异常在上线后必定遇到，所以针对不同场景我们要在 AP 与 CP 之间做出选择。
对于支付交易核心链路，一条柱子肯定是不稳的，双链路也未必可靠，但至少更稳一些。曾经遇到过相隔几公里的两条光纤被施工队挖断的情况，双机房访问直接 gg 了，但总归是少见的。
提系统可用性要避免出问题，除了问题要快快快速响应恢复，有问题先回滚。

云南之旅

发表于 2019-11-30

多图预警！！！
多图预警！！！
多图预警！！！
多图预警！！！

云南是一个离家好几千公里的地方。最初要去的想法是在一次同学聚会上大家商量的，结果到了十月一只有们两个人过来玩了，倒也好，制定行程和订票比较省事。于是，参加完同学婚礼就开始了我们的云南之旅，从国际庄直飞昆明。

去之前做攻略的时候并没有觉得昆明有什么好玩的地方，所以只是做了一天半的行程，要说昆明吃的地方也就是鲜花饼和米线了。对比过几家不同的，一个是花多纷的鲜花饼，另一个是建新园的米线不错。

玩的地方是真没觉得什么，然后就是去了云南省博物馆看了看，一般我到一个城市会先去了解下这个城市的历史和人文，博物馆建的是很恢弘有气势。看了看滇人、昆明人和汉人之间的历史渊源。

明明天还很早，博物馆就早早往外赶人了，算是逛了一半吧，然后看旁边有个官渡古镇，便抱着试试看的心态去逛了逛，果然跟预料的一样，纯粹的商业化街道让人不会再来第二次，就像北方的太行水镇、古北水镇，北京的王府井小吃街和天津的古文化街。。。

也许第一天太兴奋了吧，晚上不想回去，这边比北京在地理时区上差一个多小时。然后便跑去了云大看妹子，可惜到了都晚上了（😶），有大学地方就有小吃街，果然不出所料。

在昆明的第二天，睡了个懒觉，下午去的海埂公园看的滇池。不得不说，景色是真的不错，空气也很好，来到这里就是一场洗肺之旅。

海埂公园是从南到北的，可以遥望西山，走着走着不知不觉就想着去西山看看，站在山顶来俯瞰滇池和昆明应该很不错。就这样被什么驱使着，拿着地图导航，顺着一个不知名的小路就上⛰了。还真是曲径通幽处，好多次都给走错路了，因为真的挺偏。

山中刚下过雨路有点滑，望着遮住天空的树也不知道累，总归心情是很好的，空气也很好，想到这里总对比起北京令人头疼的雾霾天，天高皇帝远，有点不想回去了，在这种地方真的挺宜居的。

想看到的总归是要看到的，但不是在山顶，而是在爬山的某条路途中。

最后，爬到山顶是不能了，来的有点晚，得趁着天黑前下山回去，结果顺着某德导航走了一条崎岖山路，纯人工走出来的土路，崎岖泥泞，向前看不见头，向后难以攀爬。。。有点绝望了，真不知道这种路怎么会被收录并作为导航路线。。。大概是下图这样子的，真的是手脚并用出来的，最口看到村口灯光的时候特别的激动，是看到希望的激动😂。

已经很晚了，到了有人的地方赶紧打车回去市里找了个吃饭的地方。傣族风味，看评价还是挺地道的，发现和其它吃过的才来说，做法上好像没有太特别的地方，只是这里的都加了好多特别香味的香草。

要去的地方总归要去的，一个号称风花雪月的地方——大理，但是我要说与我和我的小伙伴无关。虽然我没有被过多的安利大理的美，但也还是抱着去放松的心态走一趟的。

后面几天的行程比较集中，便商量租了辆车，两个新手，开启了试车模式，尤其我这个拿本六年没摸过车的纯新手，还是比较紧张和激动的。。。我们开上了苍山，到过洱海，去过古镇（(⊙o⊙)…好像哪里不对），先练了半天车。

开过了洱海边的乡间小路、白族人的原始村镇，看到了一片金黄的稻田，如此没见过世面的我自己都很惊讶。。。

站在洱海边遥望苍山，哪些传说的爱情故事也只是传说，我所切实感受到的是景色真的很棒，随手一拍都是能做壁纸的那种。我想和对象一起来的话，住着海景房也是会很浪漫的吧？？？

待在这样的环境里我想一辈子也不会厌倦吧。晚上开去大理古城吃饭，石井私房菜，一个小巷子里，菜品也不错。邻桌的也是从北京过来旅游的。

也许大理的爱情偶遇会在古城中一个故事里发生，在不经意之间吧。

开车就要到平时不能到的地方去看看，经过重重山路不经意间来到了赵灵儿的故乡。查了查发现这里是南诏文化，巍山自治县，这里也有一个古城，慢悠悠的古城里有着原始的居民，又没有太过浓厚的商业化，保护的还相对比较好。

来大理的第三天，想着去丽江看看，最后因为时间距离问题没去，二刷再说吧。那么之前在洱海西线走了一遍，今天就在东线的环海公路走一遍吧。来到了一个叫双廊古镇的浓浓商业化的地方，有着网红打卡地天空之境，随处可见的海景房，这些都不重要，重要的是回去路上沿海公路，听着小歌吹着海风，心情超级好。当然还要感谢一下驾驶员智哥~

出来玩还是不要太久的，容易疲惫，好时光总是很快的，回家啦~

走啦～

参考攻略

云南游玩交通参考

大理景点分布

行程规划

预算

基本的照片脱敏处理

发表于 2019-10-27

我们平时拍照的照片中会包含很多额外信息可能暴露我们的地理位置、拍摄数据、拍照时间等信息。在一些网站上传原图时会暴露这些敏感信息，这个脚本主要用来通过 pillow 库将照片的 exif 信息抹掉。

其它校验网站： https://exif.tuchong.com/

通过这个网站也可以查看这些额外信息：

P/NP 问题

发表于 2019-09-22

夜色降临，三男（老张、老王和老李）一女（小刘）三人对视而坐。

老王率先打破僵局，说：既然大家都还没吃饭，今晚我们叫麻辣烫怎么样？我来点。

小刘：可以哦，终于可以吃上王哥的麻辣烫了呀~

老张：下次我来。

老李：不如今天一起呗。

四人迅速点完，等待外卖小哥上门，期间有些无聊，老李趁机开启了话题。

老李：现在有些无聊，不如我们聊一聊 NP 咋样？嘿嘿嘿~

小刘：李哥你在说什么呀（脸色微微泛红）

老王：我知道，我先来说吧。所谓 NP 其实是计算复杂度理论中最重要的集合之一。非决定性多项式集合 ( non-deterministic polynomial )，简称 NP。

它包含 P 和 NP-complete。 P 集合的问题即在多项式时间内可以找出解的决策性问题 ( decision problem ) 集合。注意 NP 包含 P 和 NP-complete 问题, 因此 NP 集合中有简单的问题和不容易快速得到解的难题。

那么画图表示就是下面这样：

老张：说的好，我来补充说一下 NP-complete 问题，又叫 NP 完备，简称 NPC，注意不是游戏里那个。

NPC 是计算复杂度理论中，决定性问题的等级之一。NP 完备是 NP 与 NP 困难的交集，是 NP 中最难的决定性问题。因此 NP 完备问题应该是最不可能被化简为 P（多项式时间可决定）的决定性问题的集合。一个决定性问题C若是为NPC，则代表它对NP是完备的，这表示：

它是一个NP问题。

其他属于NP的问题都可在多项式时间内归约成它。

可归约在此意指对每个问题L，总有一个多项式时间多对一变换，即一个决定性的算法可以将实例l ∈ L转化成实例c ∈ C，并让c回答Yes当且仅当此答案对l也是Yes。为了证明某个NP问题A实际上是NPC问题，证明者必须找出一个已知的NPC问题可以变换成A。

但如果我们证明了一个问题是 NPC 问题，则表明这个问题很可能不能通过多项式时间解决。

老李：得，一个回合下来都给你们说完了，那我就说说 NP-hard 问题吧。又称 NP 困难、NPH 问题。在说到 NPH 问题之前，你们也都对 P/NP 问题有一些了解了。

P 问题就是在多项式时间内可以被解决的问题，NP 问题就是在多项式时间内可以被验证其正确性的问题。如果所有 NP 问题都可以多项式时间归约到某个问题，则称该问题为 NP 困难。因为 NP 困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是 NP 问题），因此即使 NP 完全问题有多项式时间的解（P=NP），NP 困难问题依然可能没有多项式时间的解。因此 NP 困难问题“至少与 NP 完全问题一样难”。

说了这么多，小刘你一定很懵吧，看下面这个图的左半部分就可以很清楚的了解它们几个之间的关系了。

小刘：几位哥，哦不，几位大佬，你们刚才说的我好多不懂的，比如说的什么，计算复杂度理论、多项式时间。。。

老王：哈哈哈，小刘还是很好学的吗。

计算复杂性理论（Computational complexity theory）是理论计算机科学和数学的一个分支，它致力于将可计算问题根据它们本身的复杂性分类，以及将这些类别联系起来。一个可计算问题被认为是一个原则上可以用计算机解决的问题，亦即这个问题可以用一系列机械的数学步骤解决，例如算法。
计算复杂性理论最成功的成果之一是NP完备理论。通过该理论，我们可以理解为什么在程序设计与生产实践中遇到的很多问题至今没有找到多项式算法。而该理论更为计算复杂性中的核心问题：P与NP的关系问题指明了方向。
https://zh.wikipedia.org/wiki/計算複雜性理論

多项式时间（英语：Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间 m(n) 不大于问题大小 n 的多项式倍数。任何抽象机器都拥有一复杂度类，此类包括可于此机器以多项式时间求解的问题。
https://zh.wikipedia.org/wiki/多項式時間

常见的多项式时间有：

常量时间：O(1)
线性时间：O(n)
平方时间：O(n^2)
立方时间：O(n^3)
O(n log(n))

与多项式时间对应的是超多项式时间，比如指数时间 O(c^n)。

小刘：明白了，那我们点麻辣烫的等待时间应该是 O(log(n)) 时间了吧，也是属于多项式时间的。其实我们今天交流的 P/NP 问题指的是在计算复杂度上对于问题的复杂程度的一个划分。但是我注意到其中一个图中表达着 P = NP 和 P ≠ NP 的划分，那么 P ≠ NP 吗？

老张：哎呀，小刘真是聪明又细心，那么关于 P 等不等于 NP 这个问题也有得说了….

哐哐哐有人敲门，不一会儿，只见老王拿着东西走了过来：饭来喽，先吃麻辣烫，吃完我们再交流。

老李：对的，对的，吃完了我们可以深入交流一下嘛，哈哈。

PS：本文背景纯属虚构，内容均来自维基百科 https://zh.wikipedia.org/wiki/P/NP问题

数据结构与算法思想

发表于 2019-08-29

人生只有贪心，没有动态规划。

数据结构

数组
栈，先进后出
队列，先进先出
- 双端队列，双端队列中的元素可以从两端弹出，插入和删除操作限定在队列的两边进行。
- 环形队列，环形队列是一种特殊的队列结构，保证了元素也是先进先出的，但与一般队列的区别是，他们是环形的，即队列头部的上个元素是队列尾部，通常是容纳元素数固定的一个闭环。
堆，一种特别的树状数据结构。堆总是一棵完全树。即除了最底层，其他层的节点都被元素填满，且最底层尽可能地从左到右填入。
链表
- 单向链表。
- 双向链表。
- 跳表，一种带多级索引的链表。
散列表，是根据键而直接访问在内存存储位置的数据结构。它通过计算一个关于键值的函数，将所需查询的数据映射到表中一个位置来访问记录，这加快了查找速度。
树
- 二叉树，二叉树是一个连通的无环图，并且每一个顶点的度不大于3。
- 红黑树，是一种自平衡二叉查找树。
- 字典树（Trie）
图，图（Graph）是由顶点的有穷非空集合和顶点之间的边的集合组成。
- https://zhuanlan.zhihu.com/p/25498681
- TODO
布隆过滤器，一个概率型数据结构，可以用来判断一个元素是否在一个集合中。判断某个元素在，可能会被误判；判断某个元素不在，那么一定不在。
- https://juejin.im/post/5bc7446e5188255c791b3360

算法思想

分治法

分治法是基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

例子：快排、归并排序、MapReduce

贪心算法

贪心算法就是在每一步的选择中都按照当前最优的选择，从而希望最终结果得到最优解。贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。

例子：最小生成树、哈夫曼编码

动态规划（Dynamic Programming）

动态规划通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。常常适用于有重叠子问题和最优子结构性质的问题。
若要解一个给定问题，我们需要解其不同部分（即子问题），再根据子问题的解以得出原问题的解。通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

递归+记忆=递推

适用情况：

具有最优子结构性质。
无后效性，子问题确定后不会再改变。
子问题重叠的性质。

例子：背包问题
https://zh.wikipedia.org/wiki/%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92
https://www.zhihu.com/question/23995189/answer/613096905

回溯法（backtracking）

回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况：

找到一个可能存在的正确的答案
在尝试了所有可能的分步方法后宣告该问题没有答案

在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。

例子：八皇后问题

https://zh.wikipedia.org/wiki/%E5%9B%9E%E6%BA%AF%E6%B3%95
https://www.cnblogs.com/zuzZ/p/8178950.html

分支界限法

与贪婪算法一样，这种方法也是用来为组合优化问题设计求解算法的，所不同的是它在问题的整个可能解空间搜索，所设计出来的算法虽其时间复杂度比贪婪算法高，但它的优点是与穷举法类似，都能保证求出问题的最佳解，而且这种方法不是盲目的穷举搜索，而是在搜索过程中通过限界，可以中途停止对某些不可能得到最优解的子空间进一步搜索（类似于人工智能中的剪枝），故它比穷举法效率更高。