0%

img

reset

git reset [--soft | --mixed | --hard] [HEAD]

--soft
修改版本库,保留暂存区,保留工作区。头指针全部重置到指定版本,也会重置暂存区,并且会将工作区代码也回退到这个版本。

--hard
修改版本库,修改暂存区,修改工作区。头指针全部重置到指定版本,且将这次提交之后的所有变更都移动到暂存区。

Tips:
使用git reset --hard HEAD移除当前暂存区及工作区所有的修改。

tag

给当前commit打标签。
git tag v1.0

删除标签
git tag -d v1.0

显示标签修改内容
git show v1.0

log

查看最近提交的文件差异,最近两篇。
git log -p -2

clean

用于删除Untracked file, 常与git reset --hard一起使用,完全回复到指定commit。
git clean -dfd为文件夹,f为文件。

Linux下修改环境变量

查看PATH

echo $PATH
以添加mongodb server为列

修改方法一

export PATH=/usr/local/mongodb/bin:$PATH
//配置完后可以通过echo $PATH查看配置结果。
生效方法:立即生效
有效期限:临时改变,只能在当前的终端窗口中有效,当前窗口关闭后就会恢复原有的path配置
用户局限:仅对当前用户

修改方法二

通过修改.bashrc文件:
vim ~/.bashrc
//在最后一行添上:
export PATH=/usr/local/mongodb/bin:$PATH
生效方法:(有以下两种)
1、关闭当前终端窗口,重新打开一个新终端窗口就能生效
2、输入“source ~/.bashrc”命令,立即生效
有效期限:永久有效
用户局限:仅对当前用户

修改方法三

通过修改profile文件:
vim /etc/profile
/export PATH //找到设置PATH的行,添加
export PATH=/usr/local/mongodb/bin:$PATH
生效方法:系统重启
有效期限:永久有效
用户局限:对所有用户

修改方法四

通过修改environment文件:
vim /etc/environment
在PATH=”/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games:/usr/local/games”中加入“:/usr/local/mongodb/bin”
生效方法:系统重启
有效期限:永久有效
用户局限:对所有用户

MacOS

MAC OS X环境配置的加载顺序

  • 系统级别
    /etc/profile
    /etc/paths

  • 用户级别
    ~/.bash_profile
    ~/.bash_login
    ~/.profile
    ~/.bashrc (在打开shell时加载)

/etc/paths 全局建议修改这个文件
/etc/profile 不建议修改这个文件,全局共有配置,用户登录时候都会加载该文件
/etc/bashrc 一般在这个文件中添加系统级别的环境变量,全局共有配置,bash shell执行时候都会加载

Tips

想要立即生效执行source

对Jupyter添加Kernel

对虚拟环境的操作

进入想要添加到Jupyter的Python虚拟环境

conda activate pytorch

安装ipykernel

conda install ipykernel

在虚拟环境中执行以下以添加Kernel到Jupyter

python -m ipykernel install --name kernelname

对Jupyter的操作

查看存在的Kernel

jupyter kernelspec list

删除Kernel

jupyter kernelspec remove kernelname

CluasteringGANSiamese

代码复现

ST-SiameseNet

安装依赖pip install -r requirement

pip指定版本安装pip install xxx==version

conda指定版本安装conda install xx=version

作为Keras后台的Tensorflow有一些版本约束-版本匹配

GAN

报错信息
Error while reading resource variable _AnonymousVar41 from Container: localhost. This could mean that the variable was uninitialized. Not found: Resource localhost/_AnonymousVar41/class tensorflow::Var does not exist.

解决办法
keras改为tensorflow.keras

数据库笔记

以下Mysql为例

数据库完整性

实体完整性

实体完整性即主码,用PRIMARY KEY定义.

  • 列级约束:只能应用于一列上。
  • 表级约束:可以应用于表的多个列上。

简而言之,如果完整性约束涉及到该表的多个属性列,必须定义在表级上,否则既可以定义在列级也可以定义在表级。

参照完整性

参照完整性即外码,用FOREIGN KEY (列名) REFERENCES <表名>(列名)定义.

用constraint指定约束名,约束不指定名称时,系统会给定一个名称。

注意:外码一定参照主码(可以是其他表的主码,也可以时自己的),而且外码的列数一定要等于被参照表的主码列数。

违约处理:对被参照表进行update/delete/insert操作时会破坏参照完整性时,参照表需要告诉被参照表听改怎么做。需要对参照表定义外码时添加on delete/on update[<no action>/<cascade>]

  • CASCADE:在父表(被参照表)上update/delete记录时,同步子表(参照表)的匹配记录。
  • SET NULL:在父表(被参照表)上update/delete记录时,将子表(参照表)上匹配的列设为null(子表的外键列不能为not null)。
  • NO ACTION:如果子表中有匹配的记录,不允许对父表进行操作。
  • RESTRICT:同NO ACTION,立即检查外键约束。

NULL、RESTRICT、NO ACTION
删除:从表记录不存在时,主表才可以删除。删除从表,主表不变
更新:从表记录不存在时,主表才可以更新。更新从表,主表不变(无法更新从表)

CASCADE
删除:删除主表时自动删除从表。删除从表,主表不变
更新:更新主表时自动更新从表。更新从表,主表不变(无法更新从表)

SET NULL
删除:删除主表时自动更新从表值为NULL。删除从表,主表不变
更新:更新主表时自动更新从表值为NULL。更新从表,主表不变

总结:CASCADE对主表操作 主表影响子表.
RESTRICT对主表操作 子表限制主表.
Mysql中均无法更新子表.

用户定义完整性

列值非空(not null),列值唯一(unique),列值需要满足条件表达式(check).

  • not null:列值不能为空,(列级完整性约束)
  • unique:列值唯一,(列级或表级约束)
  • check:列值应该满足的条件,(列级或表级约束)
a b
属性 列级
元组 表级

完整性约束命名子句

完整性约束命名子句是用来给完整性约束命名,这样我们就可以通过该名称对完整性约束进行删除、增加操作。

数据定义

索引类型

类型 特点
普通索引 是最基本的索引,它没有任何限制。
唯一索引 索引列的值必须唯一,但允许有空值。
主键索引 是一种特殊的唯一索引,一个表只能有一个主键,不允许有空值。
组合索引 指多个字段上创建的索引,只有在查询条件中使用了创建索引时的第一个字段,索引才会被使用。
全文索引 主要用来查找文本中的关键字,而不是直接与索引中的值相比较。fulltext索引配合match against操作使用,而不是一般的where语句加like。

索引方法

类型 特点
BTREE BTree索引是最常用的mysql数据库索引算法,因为它不仅可以被用在=,>,>=,<,<=和between这些比较操作符上,而且还可以用于like操作符,只要它的查询条件是一个不以通配符开头的常量
HASH Hash索引只能用于对等比较,例如=,<=>(相当于=)操作符。由于是一次定位数据,不像BTree索引需要从根节点到枝节点,最后才能访问到页节点这样多次IO访问,所以检索效率远高于BTree索引。

数据查询

连接查询

  1. 等值与非等值连接查询

=为等值连接,连接字段必须为可比的。

  1. 自身连接

自己对自己相连,比如要查询先修课的先修课,要对自己查询两次。

  1. 外连接

LEFT JOIN 保存左侧所有元组,右侧不存在的用NULL补齐.(Mysql中LEFT JOINLEFT OUTER JOIN相同)

  1. 多表连接

跨多个表进行连接查询。

  1. *交叉连接

笛卡尔积。
SELECT * FROM <TABLE1>, <TABLE2>SELECT * FROM <TABLE1> CROSS JOIN <TABLE2>

  1. *内连接

如果没有连接条件,INNER JOIN 和 CROSS JOIN 在语法上是等同的,两者可以互换。

SELECT <字段名> FROM <表1> INNER JOIN <表2> [ON子句]

嵌套查询

  1. 不相关子查询

子查询的查询条件不依赖于父查询。
有些嵌套查询可以使用连接运算替代,有些不可以。

  1. 相关子查询

子查询的条件依赖于父查询。
SELECT Sno, Cno FROM SC x WHERE Grade >= (SELECT AVG(Grade) FROM SC y WHERE y.Sno = x.Sno)

  1. 带有ANY(SOME)或ALL谓词的子查询

子查询返回单值用比较运算符,返回多值时需要用ANY(SOME)或ALL谓词修饰符。且使用ANY或ALL时需要同时使用比较运算符。

  1. 带有EXISTS谓词的子查询

子查询不返回任何数据,只产生逻辑真值truefalse

注意:全称量词可以通过否运算转换成存在量词。
注意:蕴含式可以转换为析取式。

  1. 集合查询

并操作UNION,交操作INTERSECT,差操作EXCEPT.

  1. 派生表查询

子查询出现在FROM子句中时,这是子查询生成临时的派生表。

注意:必须为派生关系指定一个别名。

BERT 概述

BERT的全称是Bidirectional Encoder Representation from Transformers,即双向Transformer的Encoder,因为decoder是不能获要预测的信息的。模型的主要创新点都在pre-train方法上,即用了Masked LM和Next Sentence Prediction两种方法分别捕捉词语和句子级别的representation。

训练方法:

  • 它在训练双向语言模型时以减小的概率把少量的词替成了Mask或另一个随机的单词。
  • 增加了一个预测下一句的loss。

特点:

  • 模型深,12层,中间层只有1024wide。Transformer的中间层有2048。(深而窄 比 浅而宽 的模型更好?)
  • MLM(Masked Language Model),同时利用左侧和右侧的词语。

Reference

BERT | Bidirectional Encoder Representation from Transformers
https://easyai.tech/ai-definition/bert/

Encoder-Decoder 和 Seq2Seq 概述

Encoder-Decoder

将现实问题转化为数学问题 通过求解数学问题 从而解决现实问题

img-encoder
img-decoder
img-en-de

缺点:

Encoder 和 Decoder之间只有一个向量C来传递信息,且C的长度固定。

当输入信息太长时,会丢掉一些信息。

Attention机制就是为了解决信息过长,信息丢失的问题。

Attention模型的特点是Encoder不再将整个输入序列编码为固定长度的中间向量C,而是编码成一个向量的序列。

img-attention

Seq2Seq

*输入一个序列 输出另一个序列 *

这种结构最重要的地方在于输入序列和输出序列的长度是可变的。

Encoder-Decoder and Seq2Seq

  • Seq2Seq属于Encoder-Decoder的大范畴
  • Seq2Seq更强调目的,Encoder-Decoder更强调方法

Rreference

Encoder-Decoder 和 Seq2Seq

https://easyai.tech/ai-definition/encoder-decoder-seq2seq/

NLP中处理文本方法

由于文本是一种非架构化的数据,我们要将这种非结构化的数据转化为结构化的信息,这样我们才能对其进行处理。

现在文本表示大致有三种方式。

img

One-Hot

向量中每一个位置代表一个词

one-hot的缺点:

  • 无法表达词语之间的关系
  • 这种过于稀疏的向量,导致计算和存储的效率不高

整数编码

整数编码的缺点

  • 无法表达词语之间的关系
  • 对于模型解释而言,整数编码可能具有挑战性

Word Embedding (词嵌入)

优点:

  • 可以将文本通过一个低维向量来表达,不像one-hot长
  • 语义相似的词在向量空间上比较相近
  • 通用性强,可用在不同的任务中

Word2Vec

基于统计方法来获得词向量的方法。

两种训练模式:

  • 通过上下文来预测当前词(CBOW)
  • 通过当前词来预测上下文(Skip-gram)

提高速度的优化方法:

  • Negtive Sample (负采样)
  • Hierarchical Softmax

优点:

  • 由于Word2Vec会考虑上下文,跟之前的Embedding方法相比,效果要更好
  • 比之前的Embedding方法维度更少,速度更快
  • 通用性强,用于各种NLP任务

缺点:

  • 由于词和向量是一对一的关系,所以多义词的问题无法解决
  • Word2Vec是一种静态的方式,虽然通用性强,但是无法针对特定任务做动态优化

GloVe

实现有三步:

  • 根据语料库构建一个共现矩阵,矩阵中的每一个元素代表单词和上下文单词在特定大小的上下文窗口内共同出现的次数。
  • 构建词向量和共现矩阵之间的近似关系。
  • loss function

Reference

词嵌入 | Word embedding

https://easyai.tech/ai-definition/word-embedding/

Word2vec

https://easyai.tech/ai-definition/word2vec/

GloVe详解

http://www.fanyeong.com/2018/02/19/glove-in-detail/

XLNet Generalized Autoregressive Pretraining for Language Understanding

Abstract

Bert基于去噪自编码器的预训练模型,性能优于自回归语言模型的预训练方法。而由于mask一部分输入,bert忽略了被mask位置之间的依赖关系。

XLNet基于此优缺点可以

  • 通过最大化所有可能的因式分解顺序的对数似然,学习双向语境信息
  • 用自回归本身的特点克服bert的缺点
  • 融合了自回归模型Transformer-XT的思路

作者从自回归(autoregressive)和自编码(autoencoding)两大范式分析了当前的预训练语言模型。

1 介绍

1.1 AutoRegression与AutoEncoding两大阵营

XLNet是一个类似BERT的模型,XLNet是一种通用的自回归预训练方法。

自回归(AutoRegression)语言模型

AR语言模型是一种使用上下文词来预测下一个词的模型,但是上下文单词被限制在两个方向,前向和后向。(例如:GPT,GPT-2)

img-前向后向

AR语言模型擅长生成式NLP任务,生成上下文时总是前向的。

但是AR只能使用前向上下文或后向上下文,这意味着它不能同时使用前向和后向上下文。

自编码(AutoEncoding)语言模型

BERT被归类为自编码器语言模型。AE旨在从损坏的输入中重建原始数据。

损坏的输入意味着我们在预训练阶段用[MASK]替换原始词,目标是预测得到原始句子。
img-双向

AE语言模型的优势是,它可以从前向和后向的方向看到上下文。

AE语言模型的缺点是

  • [MASK]这种人为的符号在调优时在真实数据中并不存在,会导致预训练-调优的差异(pretrain-finetune discrepancy)
  • [MASK]假设mask词在给定未mask词的情况下彼此独立(例:住房危机已经变成银行业危机。 其忽略了 银行业 与 危机 间的关系)。

1.2 两大阵营需要新的XLNet

XLNet提出了一种让AR语言模型从双向上下文中学习的新方法,以避免[MASK]方法在AE语言模型中带来的缺点。

XLNet是一种泛化自回归(AR)方法,既集合了AR和AE方法的优势,又避免了二者的缺陷。

  • XLNet不使用传统AR模型中固定的前向或后向因式分解顺序,而是最大化所有可能因式分解顺序的期望对数似然,由于对因式分解顺序的排列操作,每个位置的语境都包含来自左侧和右侧的token。因此,每个位置都能学习来自所有位置的语境信息,即捕获双向语境。
  • 作为一个泛化自回归(AR)模型,XLNet不依赖残缺数据。不会有BERT的预训练-微调差异。自回归目标提供一种自然的方式,来利用乘法法则对预测token的联合概率执行因式分解(factorize),这消除了BERT中的独立性假设。
  • XLNet将Transformer-XL的分割循环机制和相对编码范式整合到预训练中。

2 Proposed Solution

2.1 在自回归模型中引入双向语言模型基本思想

XLNet仍然遵循两阶段的过程(pretrain fine-tune)。其主要希望改动第一阶段的过程,即不像BERT那样带[MASK]的Denoising-autoencoder的模式,而是采用AR语言模型的模式。

简单来说就是,输入句子X仍然使自左向右的输入,看到Ti单词的上文Context-before来预测Ti这个单词,又希望Context-before例不仅看到上文单词又能看到后面的Context-after里的下文单词。这样一来BERT预训练阶段引入的[MASK]符号就不需要了。

基本思想:在预训练阶段引入Permutation LM的训练目标。

举例:比如包含单词Ti的当前输入的句子X,由顺序的几个单词构成x1, x2, x3, x4四个单词顺序组成。假设x3为要预测的单词Ti,其所在的位置为Position 3,要想让它能够在上文Context-before中,也就是Pos 1或Pos 2的位置看到Pos 4的单词x4。可以这么做,假设固定住x3的位置,也就是仍在x3,之后随机排列组合句子中的4个单词,在所有可能里训责一部分作为模型的预训练的输入X。比如随机排列组合后x4, x2, x3, x1这样一个排列组合作为模型的输入X。于是x3就能同时看到上文x2以及下文x4的内容了。

img-permutation-language-model

看上去仍然是个自回归的从左到右的模型,但是其实通过对句子中单词排列组合,把一部分Ti下文的单词排到Ti上文位置中,于是就看到了上文和下文,但是形式上看上去仍然是从左到右在预测后一个单词。

2.2 具体实现

尽管基本思想里提到把句子X的单词排列组合后,再随机抽取例子作为输入,但实际上不可以,因为Fine-tune阶段不可能去排列组合原始输入。所以必须让预训练阶段的输入部分看上去仍然是x1, x2, x3, x4这个顺序,但是可以在Transformer部分做些工作,来达成目标。

XLNet采取了Attention掩码机制,输入的X没有任何变化,单词Ti还是第i个单词,前面有1到i-1个单词。但是Transformer内部,通过Attention掩码从X的输入单词里,也就是Ti的Context-before和Context-after中随机选择i-1个单词,放到Ti的Context-before上,把其他单词的输入通过Attention掩码隐藏掉。(当然这个所谓放到Ti的上文位置,只是一种形象的说法,其实在内部,就是通过Attention Mask,把其它没有被选到的单词Mask掉,不让它们在预测单词Ti的时候发生作用,如此而已。看着就类似于把这些被选中的单词放到了上文Context_before的位置了)。

XLNet是用双流自注意力模型实现的。一个是内容流自注意力,其实就是标准的Transformer的计算过程,主要引入了Query流自注意力。其实就是用来替代[MASK]标记的,XLNet因为要抛弃[MASK]又不能看到x3的输入,于是Query流就直接忽略掉x3的输入,只保留这个位置信息,用参数w来代表位置的embedding编码。其实XLNet只是抛弃了[MASK]这个占位符号,内部还是引入Query流来忽略掉被MASK的这个单词。和BERT比只是实现方式不同而已

img-two-stream-attention

如图所示,输入序列仍是x1, x2, x3, x4,通过不同的掩码矩阵,让当前单词Xi只能看到被排列组合后的顺序x3->x2->x4->x1中自己前面的单词。

2.3 XLNet与BERT

通过改造BERT预训练的过程,其实可以模拟XLNet的PLM过程。

第一种思路:Bert目前的做法是,给定输入句子X,随机Mask掉15%的单词,然后要求利用剩下的85%的单词去预测任意一个被Mask掉的单词。对于输入句子,随机选择X中的任意i个单词,只用这i个单词去预测被Mask的单词。这个过程理论上可以在Transformer内采用Attention Mask来实现,这样BERT的预训练模型就和XLNet基本等价了。

第二种思路:假设仍使用BERT目前的Mask机制,将Mask 15%改为,每次一个句子只Mask掉一个单词,利用剩下的单词来预测被Mask掉的单词。因为XLNet在实现的时候,为了提升效率,其实是选择每个句子最后末尾的1/K个单词被预测,假设K=7,意味着一个句子X,只有末尾的1/7的单词会被预测。这样两者基本是等价的。

XLNet维持了自回归(AR)语言模型的从左向右的模式,这个BERT做不到。明显的好处是,对于生成类的任务,能够在维持表面从左向右的生成过程前提下,模型里隐含了上下文的信息。XLNet貌似应该对于生成类型的NLP任务,会比BERT又明显优势。此外,XLNet还引入了Transformer XL机制,所以对于长文档输入类型的NLP任务,也会比BERT有明显优势。

3 总结

Permutation Language Model是XLNet的主要理论创新,它开启了自回归(AR)语言模型如何引入下文的一个思路

XLNet也相当于是BERT, GPT2.0, Transformer XL的综合体。

  • 通过Permutation LM 预训练目标,吸收了BERT的双向语言模型;
  • 吸收了GPT2.0使用更多更高质量的预训练数据;
  • 吸收了Transformer XL的主要思想。

XLNet其实本质上还是ELMO/GPT/BERT这一系列两阶段模型的进一步延伸。在自回归(AR)语言模型方向引入双向语言模型打开了新思路。

未来预期

  • Transformer天然对长文档任务处理有弱点,所以XLNet对于长文档NLP任务相比BERT应该有直接且比较明显的性能提升;
  • 对于生成类的NLP任务,XLNet的预训练模式符合下游任务序列生成结果。

Rreference

https://zhuanlan.zhihu.com/p/70257427

https://blog.csdn.net/weixin_37947156/article/details/93035607

// AR AE LM 实现步骤?
// TODO Transformer 较于 RNN?
// TODO encoding decoding?
// TODO denoising-autoencoder?

// TODO Transformer-XL 分割循环机制 相对编码范式??
// TODO BERT 预训练-微调两阶段模式(pretrain fine-tune) 抛弃mask使两阶段保持一致? fine-tune阶段?
// TODO AR模型前向后向因式分解顺序?

Java中继承与实现的思考

继承(extend): 继承传达的意思是is-a, 比如Cat is an Animal.

实现(Implement): 实现传达的意思是able一种能力, 比如Cat is swimmable.

extend

比较灵活可以继承抽象类,也可以继承实体类。
抽象类可以定义非抽象方法与抽象方法,如果有抽象方法则子类必须继承,如果子类没有重写非抽象方法则子类的实例使用的是父类的方法。

多态
如果实例化一个子类赋给一个父类(例: Animal cat = new Cat()), 则只能够使用父类中的field与method,如果method被子类重写则会调用子类的method。

implement

比较严格,若实现则必须实现所有方法。
其中的field都是static final修饰的,且只能被实现的子类获取。method不能有body,但是如果static修饰则可以有body(怎么用?)。

多态
如果实例化一个子类赋给一个接口(例: Swimmable cat = new Cat()),则只能够使用该接口的field并且无法获得field。
如果一个子类继承了一个实现了该接口的父类则可以重写方法,如果没有重写则(Swimmable cat = new Cat())中cat获取的方法则是父类中实现的方法。

Docker 部署 Lineloss

1 拉取redhat镜像

docker pull yjjy0921/redhat7.2

2 进入镜像换yum源

  • rpm安装wget(docker cp host.path cotainer:container.path)
  • wget下载yum相关包
  • rpm安装下载的相关包

报错:
python-urlgrabber >= 3.10-8 is needed by yum-3.4.3-167.el7.centos.noarch
rpm >= 0:4.11.3-22 is needed by yum-3.4.3-167.el7.centos.noarch

查询存在的python-urlgrabber包
rpm -q python-urlgrabber~~

删除python-urlgrabber包
rpm -e python-urlgrabber

更新rpm包
rpm -Uvh rpm-4.11.3-43.el7.x86_64.rpm --nodeps

3 创建aliyun.repo

cd /etc/yum.repo.d/
vim aliyun.repo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
[base]
name=CentOS-$releasever - Base
baseurl=http://mirrors.aliyun.com/centos/7.8.2003/os/$basearch/
gpgcheck=1
gpgkey=http://mirrors.aliyun.com/centos/7.8.2003/os/x86_64/RPM-GPG-KEY-CentOS-7


#released updates
[updates]
name=CentOS-$releasever - Updates
baseurl=http://mirrors.aliyun.com/centos/7.8.2003/updates/$basearch/
gpgcheck=1
gpgkey=http://mirrors.aliyun.com/centos/7.8.2003/os/x86_64/RPM-GPG-KEY-CentOS-7


[extras]
name=CentOS-$releasever - Extras
baseurl=http://mirrors.aliyun.com/centos/7.8.2003/extras//$basearch/
gpgcheck=1
gpgkey=http://mirrors.aliyun.com/centos/7.8.2003/os/x86_64/RPM-GPG-KEY-CentOS-7

[centosplus]
name=CentOS-$releasever - Plus
baseurl=http://mirrors.aliyun.com/centos/7.8.2003/centosplus//$basearch/
gpgcheck=1
enabled=0

清除redhat.repo
mv redhat.repo redhat.temp

检验yum配置成功
yum update -y --skip-broken

4 安装mariadb

安装
yum install -y mysql

注意
docker无法使用systemctl指令使mysql后台运行

查看容器配置文件
docker inspect containerID

修改已经运行的容器配置文件
/usr/lib/docker...

运行镜像时需要
docker run --privileged --name=lineloss -d -it edlison/lineloss /usr/sbin/init

--privileged赋予额外权限
/usr/sbin/init将cmd设置为这个 dbus服务就会运行

systemctl start mariadb 启动服务
systemctl enable mariadb 设置开机启动
systemctl restart mariadb 重新启动
systemctl stop mariadb.service 停止MariaDB

初始化数据库
mysql_secure_installation

设置密码
mysqladmin -u root password 'newpassword'

导入数据
create database lineloss;
use lineloss;
source /home/xs_project/sql/lineloss.sql

5 Java环境

安装Java
yum install java

6 Python环境

安装python3
yum install python3

安装依赖
pip3 install Flask
pip3 install flask_sqlalchemy
pip3 install pymysql
pip3 install numpy
pip3 install sklearn
pip3 install jieba
pip3 install pandas
pip3 install statsmodels

7 运行测试

运行镜像
docker run --privileged --name=lineloss -d -p 18084:18084 -it edlison/lineloss /usr/sbin/init

Java
cd /home/xs_project/java
java -jar RuoYi.jar

Python
cd /home/xs_project/python/LineLoss
python3 service.py

8 Dockerfile

只是构建镜像???不便于执行镜像内程序???

9 其他

复制文件

容器内新建文件夹
mkdir /home/xs_project/java
mkdir /home/xs_project/python
mkdir /home/xs_project/sql

将文件复制到容器内
cp RuoYi.jar containerID:/home/xs_project/java
cp LineLoss.zip containerID:/home/xs_project/python
cp lineloss.sql containerID:/home/xs_project/sql

容器提交成镜像

docker commit -a "userid" -m "comment" containerID imageName:tag

镜像上传仓库

docker push userName/imageName

注意

tag命令修改为规范的镜像名
docker tag lineloss:latest edlison/lineloss

push到用户仓库
docker push edlison/lineloss

镜像导出导入

导出镜像
docker save -o lineloss.tar edlison/lineloss
docker save edlison/lineloss>/home/lineloss.tar

导入镜像
docker load<lineloss.tar

Attention Is All You Need

Abstract

我们提出一种全新的简洁的网络架构–Transfomer,它完全基于Attention机制,舍弃了循环与卷积。

1 Introduction

Transformer的并行性很好的解决了RNN模型的序列化输入输出。

2 Background

3 Model Architecture

大部分序列神经网络模型都具有encoder-decoder结构。

3.1 Encoder and Decoder Stacks

encoder由6个相同的层构成,每一层有两个子层。第一个是一个多Attention机制,第二个是一个简单的全连接feed-forward网络。两个子层中间部署一个参差网络,后接一个正则化。

decoder也是由6个相同的层构成。除了两个子层外中间还加入了一个第三子层Multi-head Attention.

3.2 Attention

Attention的核心内容是为输入向量的每个单词(512d)学习一个权重。在self-attention中,每个单词有3个不同的向量,Query,Key,Value,长度均是64. 他们通过3个不同的权值矩阵由嵌入向量X乘以三个不同的权值矩阵WQ,WK,WV(512 * 64)得到。

Attention计算步骤:

  • 将输入单词转换成词向量
  • 根据词向量得到q, k, v三个向量
  • 为每个向量计算一个score: score = q * kT
  • 为了梯度的稳定,Transformer使用了score归一化,即除以根号dk
  • 对score过一遍softmax函数
  • softmax点乘value得到每个输入向量的评分v
  • 想家之后得到最终的输出结果z=∑v

3.3 Multi-Head Attention

Multi-Head Attention相当于h个不同的self-attention的集成。

Multi-Head输出分三步

  • 将X分别输入到8个self-attention中得到8个加权后的特征矩阵Z
  • 将8个Z按列拼接成一个大的特征矩阵
  • 将特征矩阵经过一层fc后得到输出Z

3.4 损失层

解码器解码后,解码的特征向量通过一层激活函数为softmax的全连接层之后得到反应每个单词概率的输出向量。此时通过CTC等损失函数训练模型。

4 位置编码

Transfomer无法捕捉循序序列的能力。论文在编码词向量时引入了位置编码的特征,位置编码会在词向量中加入单词的位置信息。

在上式中, [公式] 表示单词的位置, [公式] 表示单词的维度。关于位置编码的实现可在Google开源的算法中get_timing_signal_1d()函数找到对应的代码。

作者这么设计的原因是考虑到在NLP任务重,除了单词的绝对位置,单词的相对位置也非常重要。根据公式 [公式] 以及[公式] ,这表明位置 [公式] 的位置向量可以表示为位置 [公式] 的特征向量的线性变化,这为模型捕捉单词之间的相对位置关系提供了非常大的便利。

问题

位置编码对词袋模型等具有普适性?
encoder/decoder通过self-attention层所得到的向量即理解为加密/解密?
得到最后的Z之后怎么用?

Cookie, Session, Token, JWT

Authentication(认证)

认证当前的用户的身份

互联网中的认证

  • 用户名密码登陆
  • 邮箱发送登陆链接
  • 手机号接受验证码

Authorization(授权)

用户权限

实现授权的方式

  • Cookie
  • Session
  • Token
  • OAuth

Credentials(凭证)

实现认证和授权的前提是需要一种媒介(证书)来标记访问者的身份。

在互联网应用中,一般网站(如掘金)会有两种模式,游客模式和登录模式。游客模式下,可以正常浏览网站上面的文章,一旦想要点赞/收藏/分享文章,就需要登录或者注册账号。当用户登录成功后,服务器会给该用户使用的浏览器颁发一个令牌(token),这个令牌用来表明你的身份,每次浏览器发送请求时会带上这个令牌,就可以使用游客模式下无法使用的功能。

Cookie

  • HTTP 是无状态的协议(对于事务处理没有记忆能力,每次客户端和服务端会话完成时,服务端不会保存任何会话信息):每个请求都是完全独立的,服务端无法确认当前访问者的身份信息,无法分辨上一次的请求发送者和这一次的发送者是不是同一个人。所以服务器与浏览器为了进行会话跟踪(知道是谁在访问我),就必须主动的去维护一个状态,这个状态用于告知服务端前后两个请求是否来自同一浏览器。而这个状态需要通过 cookie 或者 session 去实现。
  • cookie 存储在客户端: cookie 是服务器发送到用户浏览器并保存在本地的一小块数据,它会在浏览器下次向同一服务器再发起请求时被携带并发送到服务器上。
  • cookie 是不可跨域的: 每个 cookie 都会绑定单一的域名,无法在别的域名下获取使用,一级域名和二级域名之间是允许共享使用的(靠的是 domain)。

Session

  • Session是另一种记录服务器和客户端会话状态的机制。
  • Session是基于Cookie实现的,Session存储在服务器端,SessionId会被存储到客户端的Cookie中。
  • Session认证流程
    • 用户第一次请求服务器的时候,服务器根据用户提交的相关信息,创建对应的Session。
    • 请求返回时将此Session对应的唯一标识信息SessionId返回给浏览器。
    • 浏览器接受到服务器返回的SessionId信息后,会将此信息存入到Cookie中,同时Cookie记录此SessionId属于哪个域名。
    • 当用户第二次访问服务器的时候,请求会自动判断此域名下是否存在Cookie信息,如果存在自动将Cookie信息信息也发送到服务端,服务端会从Cookie中获取SessionId,再根据SessionId查找到对应的Session信息,如果没有找到说明用户没有登陆或登陆失效,如果找到Session证明用户已经登陆可执行后面操作。

根据以上流程可知,SessionID 是连接 Cookie 和 Session 的一道桥梁,大部分系统也是根据此原理来验证用户登录状态。

Cookie和Session的区别

  • 安全性:Session比Cookie安全,Session是存储在服务端的,Cookie是存储在客户端的。
  • 存取值的类型不同:Cookie只支持存字符串数据,想要设置其他类型的数据,需要将其转换成字符串,Session可以存任意数据类型。
  • 有效期不同:Cookie可设置为长时间按保持,比如我们经常使用的默认登陆功能,Session一半失效时间较短,客户端关闭或Session超时都会失效。
  • 存储大小不同:单个Cookie保存的数据不能超过4K,Session可存储数据远高于Cookie,但是当访问量过多,会占用过多的服务器资源。

Token(令牌)

Access Token

  • 访问资源接口(API)时所需要的资源凭证

  • 简单Token的组成:uid(用户唯一的身份标识)、time(当前时间的时间戳)、sign(签名,token 的前几位以哈希算法压缩成的一定长度的十六进制字符串)

  • 特点

    • 服务端无状态化、可扩展性好。
    • 支持移动端设备
    • 安全
    • 支持跨程序调用
  • Token的身份验证流程
    accessToken

    1. 客户端使用用户名跟密码请求登陆
    2. 服务端收到请求,去验证用户名与密码
    3. 验证成功后,服务端会签发一个Token并把这个Token发送到客户端
    4. 客户端收到Token后,会把它存储起来(Cookie, LocalStorage)
    5. 客户端每次向服务端请求资源的时候需要带着服务端签发的Token
    6. 服务端收到请求,然后去验证客户端请求里面带着的Token,如果验证成功,就向客户端返回请求的数据
  • 每一次请求都需要携带Token,需要把Token放到HTTP的Header里

  • 基于Token的用户认证是一种服务端无状态的认证方法,服务端不用存放Token数据。用解析Token的实践换取Session的存储空间,从而减轻服务器的压力,减少频繁的查询数据库

  • Token完全由应用管理,所以可以避开同源策略

Refresh Token

  • Refresh Token是专用于刷新Access Token的Token。如果没有Refresh Token,也可以刷新Access Token,但每次刷新都要用户输入登陆用户名和和密码。有了Refresh Token,客户端直接用Refresh Token去更新Access Token。

refreshToken

  • Access Token 的有效期比较短,当 Acesss Token 由于过期而失效时,使用 Refresh Token 就可以获取到新的 Token,如果 Refresh Token 也失效了,用户就只能重新登录了。
  • Refresh Token 及过期时间是存储在服务器的数据库中,只有在申请新的 Acesss Token 时才会验证,不会对业务接口响应时间造成影响,也不需要向 Session 一样一直保持在内存中以应对大量的请求。

Token和Session的区别

  • Session 是一种记录服务器和客户端会话状态的机制,使服务端有状态化,可以记录会话信息。而 Token 是令牌,访问资源接口(API)时所需要的资源凭证。Token 使服务端无状态化,不会存储会话信息。
  • Session 和 Token 并不矛盾,作为身份认证 Token 安全性比 Session 好,因为每一个请求都有签名还能防止监听以及重放攻击,而 Session 就必须依赖链路层来保障通讯安全了。如果你需要实现有状态的会话,仍然可以增加 Session 来在服务器端保存一些状态。
  • 所谓 Session 认证只是简单的把 User 信息存储到 Session 里,因为 SessionID 的不可预测性,暂且认为是安全的。而 Token ,如果指的是 OAuth Token 或类似的机制的话,提供的是 认证 和 授权 ,认证是针对用户,授权是针对 App 。其目的是让某 App 有权利访问某用户的信息。这里的 Token 是唯一的。不可以转移到其它 App上,也不可以转到其它用户上。Session 只提供一种简单的认证,即只要有此 SessionID ,即认为有此 User 的全部权利。是需要严格保密的,这个数据应该只保存在站方,不应该共享给其它网站或者第三方 App。所以简单来说:如果你的用户数据可能需要和第三方共享,或者允许第三方调用 API 接口,用 Token 。如果永远只是自己的网站,自己的 App,用什么就无所谓了。

JWT

  • JSON Web Token(简称 JWT)是目前最流行的跨域认证解决方案。
  • 是一种认证授权机制
  • JWT 是为了在网络应用环境间传递声明而执行的一种基于 JSON 的开放标准(RFC 7519)。JWT 的声明一般被用来在身份提供者和服务提供者间传递被认证的用户身份信息,以便于从资源服务器获取资源。比如用在用户登录上。
  • 可以使用 HMAC 算法或者是 RSA 的公/私秘钥对 JWT 进行签名。因为数字签名的存在,这些传递的信息是可信的。

原理

jwt

  • JWT认证流程
    • 用户输入用户名/密码登录,服务端认证成功后,会返回给客户端一个 JWT
    • 客户端将 token 保存到本地(通常使用 localstorage,也可以使用 cookie)
    • 当用户希望访问一个受保护的路由或者资源的时候,需要请求头的 Authorization 字段中使用Bearer 模式添加 JWT,其内容看起来是下面这样Authorization: Bearer <token>
  • 服务端的保护路由将会检查请求头 Authorization 中的 JWT 信息,如果合法,则允许用户的行为
  • 因为 JWT 是自包含的(内部包含了一些会话信息),因此减少了需要查询数据库的需要
  • 因为 JWT 并不使用 Cookie 的,所以你可以使用任何域名提供你的 API 服务而不需要担心跨域资源共享问题(CORS)
  • 因为用户的状态不再存储在服务端的内存中,所以这是一种无状态的认证机制

使用方式

客户端收到服务器返回的 JWT,可以储存在 Cookie 里面,也可以储存在 localStorage。

方法一

  • 当用户希望访问一个受保护的路由或者资源的时候,可以把它放在 Cookie 里面自动发送,但是这样不能跨域,所以更好的做法是放在 HTTP 请求头信息的 Authorization 字段里,使用 Bearer 模式添加 JWT。
    1
    2
    3
    GET /calendar/v1/events
    Host: api.example.com
    Authorization: Bearer <token>
    • 用户的状态不会存储在服务端的内存中,这是一种 无状态的认证机制
    • 服务端的保护路由将会检查请求头 Authorization 中的 JWT 信息,如果合法,则允许用户的行为。
    • 由于 JWT 是自包含的,因此减少了需要查询数据库的需要
    • JWT 的这些特性使得我们可以完全依赖其无状态的特性提供数据 API 服务,甚至是创建一个下载流服务。
    • 因为 JWT 并不使用 Cookie ,所以你可以使用任何域名提供你的 API 服务而不需要担心跨域资源共享问题(CORS)

方法二

  • 跨域的时候,可以把 JWT 放在 POST 请求的数据体里。

方法三

  • 通过URL传输。
    http://www.example.com/user?token=xxx

Token和JWT的区别

相同:

  • 都是访问资源的令牌
  • 都可以记录用户的信息
  • 都是使服务端无状态化
  • 都是只有验证成功后,客户端才能访问服务端上手保护的资源

区别:

  • Token: 服务端验证客户端发送过来的 Token 时,还需要查询数据库获取用户信息,然后验证 Token 是否有效。
  • JWT: 将 Token 和 Payload 加密后存储于客户端,服务端只需要使用密钥解密进行校验(校验也是 JWT 自己实现的)即可,不需要查询或者减少查询数据库,因为 JWT 自包含了用户信息和加密的数据。

常见的前后端鉴权方式

  • Session-Cookie
  • Token(JWT, SSO)
  • OAuth2.0

问题

使用Cookie时需要考虑的问题

  • 因为存储在客户端,容易被客户端篡改,使用前需要验证合法性
  • 不要存储敏感数据,比如用户密码,账户余额
  • 使用 httpOnly 在一定程度上提高安全性
  • 尽量减少 cookie 的体积,能存储的数据量不能超过 4kb
  • 设置正确的 domain 和 path,减少数据传输
  • cookie 无法跨域
  • 一个浏览器针对一个网站最多存 20 个Cookie,浏览器一般只允许存放 300 个Cookie
  • 移动端对 cookie 的支持不是很好,而 session 需要基于 cookie 实现,所以移动端常用的是 token

使用Session时需要考虑的问题

  • 将 session 存储在服务器里面,当用户同时在线量比较多时,这些 session 会占据较多的内存,需要在服务端定期的去清理过期的 session
  • 当网站采用集群部署的时候,会遇到多台 web 服务器之间如何做 session 共享的问题。因为 session 是由单个服务器创建的,但是处理用户请求的服务器不一定是那个创建 session 的服务器,那么该服务器就无法拿到之前已经放入到 session 中的登录凭证之类的信息了。
  • 当多个应用要共享 session 时,除了以上问题,还会遇到跨域问题,因为不同的应用可能部署的主机不一样,需要在各个应用做好 cookie 跨域的处理。
  • sessionId 是存储在 cookie 中的,假如浏览器禁止 cookie 或不支持 cookie 怎么办? 一般会把 sessionId 跟在 url 参数后面即重写 url,所以 session 不一定非得需要靠 cookie 实现
  • 移动端对 cookie 的支持不是很好,而 session 需要基于 cookie 实现,所以移动端常用的是 token

使用Token时需要考虑的问题

  • 如果你认为用数据库来存储 token 会导致查询时间太长,可以选择放在内存当中。比如 redis 很适合你对 token 查询的需求。
  • token 完全由应用管理,所以它可以避开同源策略
  • token 可以避免 CSRF 攻击(因为不需要 cookie 了)
  • 移动端对 cookie 的支持不是很好,而 session 需要基于 cookie 实现,所以移动端常用的是 token

使用JWT时需要考虑的问题

  • 因为 JWT 并不依赖 Cookie 的,所以你可以使用任何域名提供你的 API 服务而不需要担心跨域资源共享问题(CORS)
  • JWT 默认是不加密,但也是可以加密的。生成原始 Token 以后,可以用密钥再加密一次。
  • JWT 不加密的情况下,不能将秘密数据写入 JWT。
  • JWT 不仅可以用于认证,也可以用于交换信息。有效使用 JWT,可以降低服务器查询数据库的次数。
  • JWT 最大的优势是服务器不再需要存储 Session,使得服务器认证鉴权业务可以方便扩展。但这也是 JWT 最大的缺点:由于服务器不需要存储 Session 状态,因此使用过程中无法废弃某个 Token 或者更改 Token 的权限。也就是说一旦 JWT 签发了,到期之前就会始终有效,除非服务器部署额外的逻辑。
  • JWT 本身包含了认证信息,一旦泄露,任何人都可以获得该令牌的所有权限。为了减少盗用,JWT的有效期应该设置得比较短。对于一些比较重要的权限,使用时应该再次对用户进行认证。
  • JWT 适合一次性的命令认证,颁发一个有效期极短的 JWT,即使暴露了危险也很小,由于每次操作都会生成新的 JWT,因此也没必要保存 JWT,真正实现无状态。
  • 为了减少盗用,JWT 不应该使用 HTTP 协议明码传输,要使用 HTTPS 协议传输。

使用加密算法时需要考虑的问题

  • 绝不要以明文存储密码
  • 永远使用 哈希算法 来处理密码,绝不要使用 Base64 或其他编码方式来存储密码,这和以明文存储密码是一样的,使用哈希,而不要使用编码。编码以及加密,都是双向的过程,而密码是保密的,应该只被它的所有者知道, 这个过程必须是单向的。哈希正是用于做这个的,从来没有解哈希这种说法, 但是编码就存在解码,加密就存在解密。
  • 绝不要使用弱哈希或已被破解的哈希算法,像 MD5 或 SHA1 ,只使用强密码哈希算法。
  • 绝不要以明文形式显示或发送密码,即使是对密码的所有者也应该这样。如果你需要 “忘记密码” 的功能,可以随机生成一个新的 一次性的(这点很重要)密码,然后把这个密码发送给用户。

只要关闭浏览器,Session就消失了
不对。对 session 来说,除非程序通知服务器删除一个 session,否则服务器会一直保留,程序一般都是在用户做 log off 的时候发个指令去删除 session。
然而浏览器从来不会主动在关闭之前通知服务器它将要关闭,因此服务器根本不会有机会知道浏览器已经关闭,之所以会有这种错觉,是大部分 session 机制都使用会话 cookie 来保存 session id,而关闭浏览器后这个 session id 就消失了,再次连接服务器时也就无法找到原来的 session。如果服务器设置的 cookie 被保存在硬盘上,或者使用某种手段改写浏览器发出的 HTTP 请求头,把原来的 session id 发送给服务器,则再次打开浏览器仍然能够打开原来的 session。
恰恰是由于关闭浏览器不会导致 session 被删除,迫使服务器为 session 设置了一个失效时间,当距离客户端上一次使用 session 的时间超过这个失效时间时,服务器就认为客户端已经停止了活动,才会把 session 删除以节省存储空间。

分布式下Session共享方案

  1. Session复制

任何一个服务器上的 session 发生改变(增删改),该节点会把这个 session 的所有内容序列化,然后广播给所有其它节点,不管其他服务器需不需要 session ,以此来保证 session 同步

优点:可容错,各个服务器间Session能够实时响应。

缺点:会对网络负荷造成一定压力,如果 session 量大的话可能会造成网络堵塞,拖慢服务器性能。

  1. 粘性Session/IP绑定策略

采用 Ngnix 中的 ip_hash 机制,将某个 ip的所有请求都定向到同一台服务器上,即将用户与服务器绑定。 用户第一次请求时,负载均衡器将用户的请求转发到了 A 服务器上,如果负载均衡器设置了粘性 session 的话,那么用户以后的每次请求都会转发到 A 服务器上,相当于把用户和 A 服务器粘到了一块,这就是粘性 session 机制。

优点:简单,不需要对Session做任何个处理。

缺点:缺乏容错性,如果当前访问的服务器发生故障,用户被转移到第二个服务器上时,他的 session 信息都将失效。

  1. Session共享(常用)
  • 使用分布式缓存方案比如 Memcached 、Redis 来缓存 session,但是要求 Memcached 或 Redis 必须是集群
  • 把 session 放到 Redis 中存储,虽然架构上变得复杂,并且需要多访问一次 Redis ,但是这种方案带来的好处也是很大的:
    • 实现了 session 共享;
    • 可以水平扩展(增加 Redis 服务器);
    • 服务器重启 session 不丢失(不过也要注意 session 在 Redis 中的刷新/失效机制);
    • 不仅可以跨服务器 session 共享,甚至可以跨平台(例如网页端和 APP 端)
  1. Session持久化

将 session 存储到数据库中,保证 session 的持久化

优点:服务器出现问题,session 不会丢失

缺点:如果网站的访问量很大,把 session 存储到数据库中,会对数据库造成很大压力,还需要增加额外的开销维护数据库。

Word2Vec note

引入

Word2Vec是从大量文本语料中以无监督的方式学习语义知识的一种模型,它被大量的用在自然语言处理中。Word2Vec其实就是通过学习文本来用词向量的方式表征词的语义信息,即通过一个嵌入空间使得语义上相似的单词在该空间内距离很近。Embedding其实就是一个映射,将单词从原先所属的空间映射到新的多维空间中,也就是把原先词所在的空间嵌入到一个新的空间中去。

Week 2

深度学习与神经网络基础,pytorch基础。

神经网络训练过程

  • 将DataSet生成iter(train_iter, test_iter), 每个iter由X,y构成 (X:Sample的所有特征[samples * features], y:真实标签).
  • 计算y_hat (y_hat:通过构造的神经网络模型得到的预测值).
  • 计算损失函数 (均方差, 交叉熵).
  • 对所有params梯度清零.
  • loss.backward反向传播, 对损失函数求梯度, 也就是得所有的到权重和偏置的梯度param.grad.
  • params带入梯度下降算法, 更新params.
  • 每个epoch后, 将测试数据带入训练后的网络模型中计算准确率.

注意

1. W初始化
首先介绍一下我们不应该做的事情(即初始化为0)。需要注意的是我们并不知道在训练神经网络中每一个权重最后的值,但是如果进行了恰当的数据归一化后,我们可以有理由认为有一半的权重是正的,另一半是负的。令所有权重都初始化为0这个一个听起来还蛮合理的想法也许是一个我们假设中最好的一个假设了。但结果正确是一个错误(的想法),因为如果神经网络计算出来的输出值都一个样,那么反向传播算法计算出来的梯度值一样,并且参数更新值也一样(w=w−α∗dw)。更一般地说,如果权重初始化为同一个值,网络就不可能不对称(即是对称的)。

2. 梯度清零
每次反向传播前需要将params的梯度清零,否则每次计算的梯度为上一个梯度的累加。

3. 反向传播
计算的是给定图的叶子结点的梯度,对Loss函数进行反向传播计算所得即为所有的W与b。

4. python方法
method()代表执行完该函数
method仅函数对象

5. 二分类问题不小心将最后一层设为10维
最后训练出来的权重使得结果在0, 1上的概率更大,不排除最后的结果为2 ~ 9。

6. 网络的层次
每一层为激活函数

层数-1 为连接层 连接层对应[W, b]

X = [batch_size * features]

  • 第一层输入为([-1, features])

  • 矩阵计算: [-1, features] * [W1(input_num, hidden_num)] + b1

  • 隐藏层输入为(input_num, hidden_num)

  • 矩阵计算: [-1, hidden_num] * [W2(hidden_num, output_num)] + b2

  • 输出层为(hidden_num, output_num)

  • 最终矩阵格式: [-1, output_num]

7. 特殊第一层input输入层
输入的特征可能type为Long, 一定要转为float.
batch_size与input_num无关, 但features一定与input_num相等.

8. X.permute
model的forward必须要X.permute(1, 0)
LSTM(batch_first=True)没用???

9. python路径问题
相对路径取决于调用该函数的python文件位置,不是子函数所在python文件相对于文件的位置。

10. pytorch使用GPU计算

  • 训练及评价集需要X.cuda()将数据移至GPU
  • model与loss函数需要model.cuda(), loss.cuda()移至GPU

11. 导出数据
TestLoader导出预测结果时,一定不能将导入的数据Shuffle!!!

12. pad
<pad>对应一个随机生成的向量

13. torch.no_grad()

  • requires_grad=True 要求计算梯度
  • requires_grad=False 不要求计算梯度
  • with torch.no_grad()或者@torch.no_grad()中的数据不需要计算梯度,也不会进行反向传播

即使一个tensor(命名为x)的requires_grad = True,由x得到的新tensor(命名为w-标量)requires_grad也为False,且grad_fn也为None,即不会对w求导。

1
2
3
4
5
6
7
8
9
10
11
x = torch.randn(10, 5, requires_grad = True)
y = torch.randn(10, 5, requires_grad = True)
z = torch.randn(10, 5, requires_grad = True)
with torch.no_grad():
w = x + y + z
print(w.requires_grad)
print(w.grad_fn)
print(w.requires_grad)
False
None
False

14. train()/eval()

  • 在训练模型时,前面加上model.train()
    启用 BatchNormalization 和 Dropout

  • 在测试模型时,前面加上model.eval()
    不启用 BatchNormalization 和 Dropout
    即使不训练,它也会改变权值。这是model中含有batch normalization层所带来的的性质。

问题

最后一层输出不加激活函数 含义(最后预测值是数值最大的 因此没有影响)???

隐藏层没有激活函数 含义???

LSTM(batch_first=True)没用???

embedding_layer(X)中X.shape为(batch,seq)或(seq,batch)没影响???
若batch_first了embedding后要(batch,seq)后传入rnn???

lstm门使用sigmoid代表门开程度,而不是四舍五入为0或1???

词向量框架

  • 拿到每个样本
  • 每个样本分词
  • 构建词典{word: index}
  • 对每个Sample标准化处理, 长度不足补<pad>
  • 将每个Sample中的word对应index,没有的对应<pad>的index
  • 获取预训练的词向量

Docker-NextCloud

docker-compose.yml

1
2
3
4
5
6
7
8
9
10
version: '3'

services:
nextcloud:
image: nextcloud
restart: "no"
volumes:
- ~/docker_nextcloud/data/:/var/www/html
ports:
- "25000:80"

gRPC入门

下载依赖

pip install grpc
pip install proto
pip install grpc-tools

设置接口

在.proto文件中定义接口

生成文件

python -m grpc_tools.protoc -I. --python_out=. --grpc_python_out=. api.proto

proto示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
syntax = "proto3";

// The greeting service definition.
service Greeter {
// Sends a greeting
rpc SayHello (HelloRequest) returns (HelloReply) {}
// Sends another greeting
rpc SayHelloAgain (HelloRequest) returns (HelloReply) {}
}

// The request message containing the user's name.
message HelloRequest {
string name = 1;
}

// The response message containing the greetings
message HelloReply {
string message = 1;
}

server示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Greeter(api_pb2_grpc.GreeterServicer):

def SayHello(self, request, context):
return api_pb2.HelloReply(message='Hello, %s!' % request.name)

def SayHelloAgain(self, request, context):
return api_pb2.HelloReply(message='Hello again, %s!' % request.name)


def serve():
server = grpc.server(futures.ThreadPoolExecutor(max_workers=4))
api_pb2_grpc.add_GreeterServicer_to_server(Greeter(), server)
server.add_insecure_port('localhost:50051')
server.start()
try:
while True:
time.sleep(60 * 60 * 24)
except KeyboardInterrupt:
server.stop(0)


if __name__ == '__main__':
serve()

client示例

1
2
3
4
5
6
7
8
9
10
11
def run():
channel = grpc.insecure_channel('localhost:50051')
stub = api_pb2_grpc.GreeterStub(channel)
response = stub.SayHello(api_pb2.HelloRequest(name='you'))
print("Greeter client received: " + response.message)
response = stub.SayHelloAgain(api_pb2.HelloRequest(name='you'))
print("Greeter client received: " + response.message)


if __name__ == '__main__':
run()

Nginx

检测配置文件
nginx -t

重启服务
nginx -s reload

若重启报错 先运行
nginx -c /etc/nginx/nginx.conf

SSL config

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
  server {
listen 80 default_server;
listen [::]:80 default_server;
server_name api.gfgf.tech;
root /usr/share/nginx/html;

return 301 https://$server_name$request_uri;

# Load configuration files for the default server block.
include /etc/nginx/default.d/*.conf;

location / {
proxy_pass http://127.0.0.1:21000;
}

error_page 404 /404.html;
location = /40x.html {
}

error_page 500 502 503 504 /50x.html;
location = /50x.html {
}
}

server {
listen 443 ssl http2 default_server;
listen [::]:443 ssl http2 default_server;
server_name api.gfgf.tech;
root /usr/share/nginx/html;

ssl_certificate "/root/.acme.sh/api.gfgf.tech/api.gfgf.tech.cer";
ssl_certificate_key "/root/.acme.sh/api.gfgf.tech/api.gfgf.tech.key";
ssl_session_cache shared:SSL:1m;
ssl_session_timeout 10m;
ssl_ciphers HIGH:!aNULL:!MD5;
ssl_prefer_server_ciphers on;

# Load configuration files for the default server block.
include /etc/nginx/default.d/*.conf;

location / {
proxy_pass http://localhost:21000;
}

error_page 404 /404.html;
location = /40x.html {
}

error_page 500 502 503 504 /50x.html;
location = /50x.html {
}
}

Docker-Compose

运行指令

docker-compose指令执行当前文件夹下docker-compose.yml文件

项目运行
docker-compose up -d

项目停止
docker-compose down

挂载

volumes声明过的名称才能用在镜像的volumes挂载
镜像中volumes挂载地址也可以使用相对路径

Docker-GitLab

注意

若容器端口号设置为80,如果你这时修改external_url地址为http://ip:8080.
那GitLab肯定访问不了,因为已经将内部的端口号修改为8080端口了,而映射的是容器的80端口。

故一定要将容器内部端口号与宿主机端口号映射一致!!!

external_utl ‘http://119.23.107.61:13000'
ports:
- “13000:13000”

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
version: '3'

services:
gitlab:
image: gitlab/gitlab-ce
restart: always
environment:
TZ: "Asia/Shanghai"
GITLAB_OMNIBUS_CONFIG: |
external_url 'http://119.23.107.61:13000' // 好像需要手动改
volumes:
- ~/docker_gitlab/config:/etc/gitlab
- ~/docker_gitlab/logs:/var/log/gitlab
- ~/docker_gitlab/data:/var/opt/gitlab
ports:
- "13000:13000"
- "13443:443"
- "13022:22"

Docker & Docker-Compose

运行docker

$ service docker start

运行容器

docker run -i -t -p 11000:8888 continuumio/anaconda3 /bin/bash
-ddetach直接后台运行

1
2
3
-i: 是  以交互模式运行容器,通常与 -t 同时使用;
-t: 为容器重新分配一个伪输入终端,通常与 -i 同时使用;
-p: 指定端口映射,格式为:主机(宿主)端口:容器端口

退出容器并保存在后台
Control + P + Q

进入容器
docker exec -it name /bin/bash
此时exit不会关闭容器

查看运行的容器
docker ps -a

映射或挂载(重要)

宿主机:镜像

默认挂载路径
/var/lib/docker/volumes

镜像相关

生成镜像
docker commit -a "username" -m "msg" container_name new_image_name

上传镜像
将打包好的新镜像上传到 Docker Hub:

首先我们需要将这个新镜像打上 tag,方便在公共服务器进行上传:

docker tag new_anaconda_xgboost:latest nimendavid/machine_learning:v0.1

其中:

new_anaconda_xgboost:latest
(本地镜像名称:tag)

可以通过 docker image ls 查看
nimendavid/machine_learning:v0.1

格式是(dockerhub用户名/仓库名:tag) ,需要自己有一个dockerhub账号,v0.1就是自定义的版本号码

然后记得登录在服务器上dockerhub,否则推送会报错:

docker login

使用Docker配置Anaconda环境运行Jupyter

配置Anaconda环境

挂载

  • 文件夹挂载
    -v /root/notebook:/notebook
    (宿主机目录:镜像内挂载目录)

  • 配置文件挂载(生成的文件夹)
    -v /root/docker/config/anaconda3/jupyter_notebook_config.json:/root/.jupyter/jupyter_notebook_config.json

Example
docker run -i -t -p 11000:8888 -v ~/notebook:/notebook -v ~/docker/config/jupyter:/root/.jupyter continuumio/anaconda3 /bin/bash
挂载参数要在容器前

配置Jupyter Notebook

jupyter notebook --allow-root

启动Notebook
jupyter notebook --port 8888 --ip 0.0.0.0 --allow-root

后台运行Notebook
nohup jupyter notebook --port 8888 --ip 0.0.0.0 --allow-root &

相关配置

配置文件

1
2
3
4
5
6
7
8
c = get_config()
c.IPKernelApp.pylab = "inline"
c.NotebookApp.ip = "*"
c.NotebookAPp.open_browser = False
c.NotebookApp.password = 'sha1:5295d47ebd06:cdca9499f90b4b4616c935fdff61dda71e1e4393'
# c.NotebookApp.certfile = u'/root/.jupyter/mycert.pem'
c.NotebookApp.port= 8888
c.NotebookApp.notebook_dir = "/"

docker-compose配置出问题?

1
2
3
4
5
6
7
8
9
10
11
version: '3'

services:
notebook:
image: continuumio/anaconda3
restart: "no"
volumes:
- ~/notebook:/notebook
- ~/docker/config/jupyter:/root/.jupyter
ports:
- "11000:80"

使用Docker搭建图床

安装容器编排工具Compose
pip3 install docker-compose

pull镜像
docker pull mariadb:latest
docker pull nmtan/chevereto:latest

使用Docker-Compose启动
mkdir cheverto/
cd cheverto
touch docker-compose.yaml

docker-compose.yaml配置文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
version: '3'

services:
db:
image: mariadb
volumes:
- database:/var/lib/mysql:rw
restart: always
networks:
- private
environment:
MYSQL_ROOT_PASSWORD: chevereto_root
MYSQL_DATABASE: chevereto
MYSQL_USER: chevereto
MYSQL_PASSWORD: chevereto

chevereto:
depends_on:
- db
image: nmtan/chevereto
restart: always
networks:
- private
environment:
CHEVERETO_DB_HOST: db
CHEVERETO_DB_USERNAME: chevereto
CHEVERETO_DB_PASSWORD: chevereto
CHEVERETO_DB_NAME: chevereto
CHEVERETO_DB_PREFIX: chv_
volumes:
- chevereto_images:/var/www/html/images:rw
- chevereto_php_config:/usr/local/etc/php:rw
ports:
- 12000:80

networks:
private:
volumes:
database:
chevereto_images:
chevereto_php_config:

对应挂载到当前文件夹中的php.ini文件(注意 php.ini文件需要先创建 否则docker会自动创建同名文件夹)
- ./php.ini:/usr/local/etc/php/php.ini:rw

php.ini

1
2
3
memory_limit = 256M;
upload_max_filesize = 100M;
post_max_size = 100M;

运行Docker-Compose
docker-compose up -d

KNN-手写体数字数据集

1
2
3
4
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets
from sklearn.neighbors import KNeighborsClassifier
1
2
3
digits = datasets.load_digits()
X = digits.data
X.shape
(1797, 64)
1
2
y = digits.target
y.shape
(1797,)
1
2
3
one = X[100]
one = one.reshape(8, 8)
one
array([[ 0.,  0.,  0.,  2., 13.,  0.,  0.,  0.],
       [ 0.,  0.,  0.,  8., 15.,  0.,  0.,  0.],
       [ 0.,  0.,  5., 16.,  5.,  2.,  0.,  0.],
       [ 0.,  0., 15., 12.,  1., 16.,  4.,  0.],
       [ 0.,  4., 16.,  2.,  9., 16.,  8.,  0.],
       [ 0.,  0., 10., 14., 16., 16.,  4.,  0.],
       [ 0.,  0.,  0.,  0., 13.,  8.,  0.,  0.],
       [ 0.,  0.,  0.,  0., 13.,  6.,  0.,  0.]])
1
plt.imshow(one)
<matplotlib.image.AxesImage at 0x1a203a9ad0>

png

分离训练测试集

1
2
from sklearn.model_selection import train_test_split
train_test_split?
Signature: train_test_split(*arrays, **options)
Docstring:
Split arrays or matrices into random train and test subsets

Quick utility that wraps input validation and
``next(ShuffleSplit().split(X, y))`` and application to input data
into a single call for splitting (and optionally subsampling) data in a
oneliner.

Read more in the :ref:`User Guide <cross_validation>`.

Parameters
----------
*arrays : sequence of indexables with same length / shape[0]
    Allowed inputs are lists, numpy arrays, scipy-sparse
    matrices or pandas dataframes.

test_size : float, int or None, optional (default=None)
    If float, should be between 0.0 and 1.0 and represent the proportion
    of the dataset to include in the test split. If int, represents the
    absolute number of test samples. If None, the value is set to the
    complement of the train size. If ``train_size`` is also None, it will
    be set to 0.25.

train_size : float, int, or None, (default=None)
    If float, should be between 0.0 and 1.0 and represent the
    proportion of the dataset to include in the train split. If
    int, represents the absolute number of train samples. If None,
    the value is automatically set to the complement of the test size.

random_state : int, RandomState instance or None, optional (default=None)
    If int, random_state is the seed used by the random number generator;
    If RandomState instance, random_state is the random number generator;
    If None, the random number generator is the RandomState instance used
    by `np.random`.

shuffle : boolean, optional (default=True)
    Whether or not to shuffle the data before splitting. If shuffle=False
    then stratify must be None.

stratify : array-like or None (default=None)
    If not None, data is split in a stratified fashion, using this as
    the class labels.

Returns
-------
splitting : list, length=2 * len(arrays)
    List containing train-test split of inputs.

    .. versionadded:: 0.16
        If the input is sparse, the output will be a
        ``scipy.sparse.csr_matrix``. Else, output type is the same as the
        input type.

Examples
--------
>>> import numpy as np
>>> from sklearn.model_selection import train_test_split
>>> X, y = np.arange(10).reshape((5, 2)), range(5)
>>> X
array([[0, 1],
       [2, 3],
       [4, 5],
       [6, 7],
       [8, 9]])
>>> list(y)
[0, 1, 2, 3, 4]

>>> X_train, X_test, y_train, y_test = train_test_split(
...     X, y, test_size=0.33, random_state=42)
...
>>> X_train
array([[4, 5],
       [0, 1],
       [6, 7]])
>>> y_train
[2, 0, 3]
>>> X_test
array([[2, 3],
       [8, 9]])
>>> y_test
[1, 4]

>>> train_test_split(y, shuffle=False)
[[0, 1, 2], [3, 4]]
File:      /Applications/anaconda3/lib/python3.7/site-packages/sklearn/model_selection/_split.py
Type:      function
1
2
3
4
5
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2)
print(X_train.shape)
print(y_train.shape)
print(X_test.shape)
print(y_test.shape)
(1437, 64)
(1437,)
(360, 64)
(360,)

测试

1
KNNClf = KNeighborsClassifier(n_neighbors=3)
1
KNNClf.fit(X_train, y_train)
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
                     metric_params=None, n_jobs=None, n_neighbors=3, p=2,
                     weights='uniform')
1
2
res = KNNClf.predict(X_test)
res
array([3, 4, 8, 5, 5, 7, 0, 3, 1, 4, 7, 5, 5, 8, 0, 7, 4, 7, 1, 7, 9, 4,
       4, 7, 6, 1, 2, 9, 1, 3, 3, 3, 7, 0, 7, 0, 2, 8, 9, 1, 1, 5, 4, 8,
       9, 0, 4, 9, 4, 9, 7, 2, 7, 3, 3, 4, 1, 9, 9, 9, 0, 4, 0, 6, 1, 0,
       0, 3, 6, 2, 3, 2, 8, 5, 9, 3, 1, 1, 6, 9, 8, 1, 2, 3, 2, 6, 8, 8,
       4, 6, 8, 6, 3, 9, 2, 8, 3, 6, 5, 7, 1, 7, 3, 8, 8, 8, 0, 0, 9, 1,
       9, 8, 5, 1, 1, 0, 1, 6, 5, 1, 7, 6, 5, 7, 7, 2, 2, 7, 3, 1, 9, 5,
       9, 5, 5, 3, 8, 4, 9, 5, 4, 6, 0, 5, 4, 8, 6, 1, 2, 8, 0, 9, 0, 9,
       7, 9, 7, 0, 2, 8, 2, 4, 0, 6, 2, 6, 7, 5, 6, 3, 8, 8, 0, 3, 2, 0,
       6, 1, 0, 6, 0, 5, 9, 3, 3, 0, 4, 0, 4, 2, 4, 9, 0, 6, 7, 4, 6, 5,
       9, 7, 2, 2, 3, 3, 0, 3, 9, 4, 9, 8, 5, 6, 9, 0, 1, 3, 5, 0, 5, 1,
       6, 4, 6, 6, 6, 7, 9, 1, 0, 7, 6, 6, 7, 8, 0, 3, 8, 5, 6, 8, 1, 3,
       0, 3, 6, 0, 3, 5, 6, 7, 0, 6, 9, 7, 0, 0, 2, 1, 6, 6, 9, 1, 6, 9,
       8, 7, 0, 2, 5, 1, 8, 6, 4, 3, 8, 2, 9, 2, 8, 4, 6, 4, 8, 9, 3, 1,
       1, 5, 0, 7, 8, 2, 3, 8, 4, 7, 7, 7, 7, 9, 4, 1, 7, 0, 2, 9, 1, 8,
       2, 4, 1, 0, 7, 5, 6, 0, 7, 1, 1, 5, 7, 1, 1, 6, 5, 6, 2, 2, 3, 9,
       7, 5, 3, 1, 5, 9, 9, 2, 5, 1, 6, 8, 2, 2, 4, 2, 1, 0, 6, 1, 2, 9,
       7, 5, 3, 5, 6, 1, 8, 1])
1
y_test
array([3, 4, 8, 5, 5, 7, 0, 3, 1, 4, 7, 5, 5, 8, 0, 7, 4, 7, 1, 7, 9, 4,
       4, 7, 6, 1, 2, 9, 1, 3, 3, 3, 7, 0, 7, 0, 2, 8, 9, 1, 1, 5, 4, 8,
       9, 0, 4, 9, 4, 9, 7, 2, 7, 8, 3, 4, 1, 9, 9, 9, 0, 4, 0, 6, 1, 0,
       0, 3, 6, 2, 3, 2, 8, 5, 9, 3, 1, 1, 6, 9, 8, 1, 2, 3, 2, 6, 8, 8,
       4, 6, 8, 6, 3, 9, 2, 8, 3, 6, 5, 7, 1, 7, 9, 8, 8, 8, 0, 0, 9, 1,
       4, 8, 5, 1, 1, 0, 1, 6, 5, 1, 7, 6, 5, 7, 7, 2, 2, 7, 3, 1, 9, 5,
       9, 5, 5, 3, 8, 4, 9, 5, 4, 6, 0, 5, 4, 8, 6, 1, 2, 8, 0, 9, 0, 9,
       7, 9, 7, 0, 2, 8, 2, 4, 0, 6, 2, 6, 7, 5, 6, 3, 8, 8, 0, 3, 2, 0,
       6, 1, 0, 6, 0, 5, 9, 3, 3, 0, 4, 0, 4, 2, 4, 9, 0, 6, 7, 4, 6, 5,
       9, 7, 2, 2, 3, 3, 0, 3, 9, 4, 9, 8, 5, 6, 9, 0, 1, 3, 5, 0, 5, 1,
       6, 4, 6, 6, 6, 7, 9, 1, 0, 7, 6, 6, 7, 8, 0, 3, 8, 5, 6, 8, 1, 3,
       0, 3, 6, 0, 3, 5, 6, 7, 0, 6, 9, 7, 0, 0, 2, 1, 6, 6, 9, 1, 6, 9,
       8, 7, 0, 2, 5, 1, 8, 6, 4, 3, 8, 2, 9, 2, 8, 4, 6, 4, 8, 9, 3, 1,
       1, 5, 0, 7, 8, 2, 3, 8, 4, 7, 7, 7, 7, 7, 4, 1, 3, 0, 2, 9, 1, 8,
       2, 4, 1, 0, 7, 5, 6, 0, 7, 1, 1, 5, 7, 1, 1, 6, 5, 6, 2, 2, 3, 9,
       7, 5, 3, 1, 5, 9, 9, 2, 5, 1, 6, 8, 2, 2, 4, 2, 1, 0, 6, 1, 2, 9,
       7, 5, 3, 5, 6, 1, 8, 8])
1
2
num = sum(res == y_test)
num
354
1
print('accuracy ', num / len(y_test))
accuracy  0.9833333333333333

使用sklearn中封装的计算精确度的方法

1
from sklearn.metrics import accuracy_score as accuracy
1
accuracy(res, y_test)
0.9833333333333333
1
2


KNN-鸢尾花数据集

1
2
3
import numpy as np
import matplotlib.pyplot as plt
from sklearn import datasets

使用sklearn本地数据集中的鸢尾花数据集

1
2
iris = datasets.load_iris()
iris.keys()
dict_keys(['data', 'target', 'target_names', 'DESCR', 'feature_names', 'filename'])
1
X = iris.data
1
Y = iris.target
1
X.shape
(150, 4)
1
Y.shape
(150,)

手动分离测试数据

1
2
shuffled_indexes = np.random.permutation(len(X))
shuffled_indexes
array([ 47,  10, 144,  57, 135,  58,  36, 136,  73, 109,  64,  15, 104,
       143, 108,  83,  23, 126, 125, 131, 137,  22,  16,  29, 118,  31,
        33,  52,  32, 132,  45,  38,  78, 139,  30,  37,  61,  97, 122,
        56, 107,  66, 114,  87,  43,  76,  84,  79, 142,  70,  77,  42,
         7, 138, 141, 120, 129,  44,  24,  53, 116,  13,  91, 119,  93,
         6,  60,  50,  67,  20,  54,  71,  89,  68,  21, 133, 148,  81,
        25,  48, 130, 127,  28,  90,  82, 146, 100, 105,  80,  94,  14,
        55, 111, 106, 101, 103,  35,  99,   3,  26,  69, 124,  95,  96,
       140,  46,  19,  34,  75,  59,   1, 117, 121,  49, 110,   0, 115,
        72,   9,  18, 149,  40, 145,  92, 123,  51,   4,  11,  39,  85,
        62, 147, 102,  74,   2,  86,   8,  17,   5,  27, 112, 128,  12,
        65,  41, 134,  63,  88, 113,  98])
1
2
test_ratio = 0.2
test_size = int(len(X) * test_ratio)
1
2
test_indexes = shuffled_indexes[:test_size]
train_indexes = shuffled_indexes[test_size:]
1
2
3
4
5
X_train = X[train_indexes]
Y_train = Y[train_indexes]

X_test = X[test_indexes]
Y_test = Y[test_indexes]
1
print(X_train.shape);print(Y_train.shape);print(X_test.shape);print(Y_test.shape)
(120, 4)
(120,)
(30, 4)
(30,)

使用sklearn分离

1
2
from sklearn.model_selection import train_test_split
train_test_split?
Signature: train_test_split(*arrays, **options)
Docstring:
Split arrays or matrices into random train and test subsets

Quick utility that wraps input validation and
``next(ShuffleSplit().split(X, y))`` and application to input data
into a single call for splitting (and optionally subsampling) data in a
oneliner.

Read more in the :ref:`User Guide <cross_validation>`.

Parameters
----------
*arrays : sequence of indexables with same length / shape[0]
    Allowed inputs are lists, numpy arrays, scipy-sparse
    matrices or pandas dataframes.

test_size : float, int or None, optional (default=None)
    If float, should be between 0.0 and 1.0 and represent the proportion
    of the dataset to include in the test split. If int, represents the
    absolute number of test samples. If None, the value is set to the
    complement of the train size. If ``train_size`` is also None, it will
    be set to 0.25.

train_size : float, int, or None, (default=None)
    If float, should be between 0.0 and 1.0 and represent the
    proportion of the dataset to include in the train split. If
    int, represents the absolute number of train samples. If None,
    the value is automatically set to the complement of the test size.

random_state : int, RandomState instance or None, optional (default=None)
    If int, random_state is the seed used by the random number generator;
    If RandomState instance, random_state is the random number generator;
    If None, the random number generator is the RandomState instance used
    by `np.random`.

shuffle : boolean, optional (default=True)
    Whether or not to shuffle the data before splitting. If shuffle=False
    then stratify must be None.

stratify : array-like or None (default=None)
    If not None, data is split in a stratified fashion, using this as
    the class labels.

Returns
-------
splitting : list, length=2 * len(arrays)
    List containing train-test split of inputs.

    .. versionadded:: 0.16
        If the input is sparse, the output will be a
        ``scipy.sparse.csr_matrix``. Else, output type is the same as the
        input type.

Examples
--------
>>> import numpy as np
>>> from sklearn.model_selection import train_test_split
>>> X, y = np.arange(10).reshape((5, 2)), range(5)
>>> X
array([[0, 1],
       [2, 3],
       [4, 5],
       [6, 7],
       [8, 9]])
>>> list(y)
[0, 1, 2, 3, 4]

>>> X_train, X_test, y_train, y_test = train_test_split(
...     X, y, test_size=0.33, random_state=42)
...
>>> X_train
array([[4, 5],
       [0, 1],
       [6, 7]])
>>> y_train
[2, 0, 3]
>>> X_test
array([[2, 3],
       [8, 9]])
>>> y_test
[1, 4]

>>> train_test_split(y, shuffle=False)
[[0, 1, 2], [3, 4]]
File:      /Applications/anaconda3/lib/python3.7/site-packages/sklearn/model_selection/_split.py
Type:      function
1
X_train, X_test, Y_train, Y_test = train_test_split(X, Y, test_size=0.2, random_state=1)
1
2
3
4
print(X_train.shape)
print(Y_train.shape)
print(X_test.shape)
print(Y_test.shape)
(120, 4)
(120,)
(30, 4)
(30,)

使用sklearn中的KNN分离器测试

1
2
from sklearn.neighbors import KNeighborsClassifier
KNeighborsClassifier?
Init signature:
KNeighborsClassifier(
    n_neighbors=5,
    weights='uniform',
    algorithm='auto',
    leaf_size=30,
    p=2,
    metric='minkowski',
    metric_params=None,
    n_jobs=None,
    **kwargs,
)
Docstring:     
Classifier implementing the k-nearest neighbors vote.

Read more in the :ref:`User Guide <classification>`.

Parameters
----------
n_neighbors : int, optional (default = 5)
    Number of neighbors to use by default for :meth:`kneighbors` queries.

weights : str or callable, optional (default = 'uniform')
    weight function used in prediction.  Possible values:

    - 'uniform' : uniform weights.  All points in each neighborhood
      are weighted equally.
    - 'distance' : weight points by the inverse of their distance.
      in this case, closer neighbors of a query point will have a
      greater influence than neighbors which are further away.
    - [callable] : a user-defined function which accepts an
      array of distances, and returns an array of the same shape
      containing the weights.

algorithm : {'auto', 'ball_tree', 'kd_tree', 'brute'}, optional
    Algorithm used to compute the nearest neighbors:

    - 'ball_tree' will use :class:`BallTree`
    - 'kd_tree' will use :class:`KDTree`
    - 'brute' will use a brute-force search.
    - 'auto' will attempt to decide the most appropriate algorithm
      based on the values passed to :meth:`fit` method.

    Note: fitting on sparse input will override the setting of
    this parameter, using brute force.

leaf_size : int, optional (default = 30)
    Leaf size passed to BallTree or KDTree.  This can affect the
    speed of the construction and query, as well as the memory
    required to store the tree.  The optimal value depends on the
    nature of the problem.

p : integer, optional (default = 2)
    Power parameter for the Minkowski metric. When p = 1, this is
    equivalent to using manhattan_distance (l1), and euclidean_distance
    (l2) for p = 2. For arbitrary p, minkowski_distance (l_p) is used.

metric : string or callable, default 'minkowski'
    the distance metric to use for the tree.  The default metric is
    minkowski, and with p=2 is equivalent to the standard Euclidean
    metric. See the documentation of the DistanceMetric class for a
    list of available metrics.
    If metric is "precomputed", X is assumed to be a distance matrix and
    must be square during fit. X may be a :term:`Glossary <sparse graph>`,
    in which case only "nonzero" elements may be considered neighbors.

metric_params : dict, optional (default = None)
    Additional keyword arguments for the metric function.

n_jobs : int or None, optional (default=None)
    The number of parallel jobs to run for neighbors search.
    ``None`` means 1 unless in a :obj:`joblib.parallel_backend` context.
    ``-1`` means using all processors. See :term:`Glossary <n_jobs>`
    for more details.
    Doesn't affect :meth:`fit` method.

Attributes
----------
classes_ : array of shape (n_classes,)
    Class labels known to the classifier

effective_metric_ : string or callble
    The distance metric used. It will be same as the `metric` parameter
    or a synonym of it, e.g. 'euclidean' if the `metric` parameter set to
    'minkowski' and `p` parameter set to 2.

effective_metric_params_ : dict
    Additional keyword arguments for the metric function. For most metrics
    will be same with `metric_params` parameter, but may also contain the
    `p` parameter value if the `effective_metric_` attribute is set to
    'minkowski'.

outputs_2d_ : bool
    False when `y`'s shape is (n_samples, ) or (n_samples, 1) during fit
    otherwise True.

Examples
--------
>>> X = [[0], [1], [2], [3]]
>>> y = [0, 0, 1, 1]
>>> from sklearn.neighbors import KNeighborsClassifier
>>> neigh = KNeighborsClassifier(n_neighbors=3)
>>> neigh.fit(X, y)
KNeighborsClassifier(...)
>>> print(neigh.predict([[1.1]]))
[0]
>>> print(neigh.predict_proba([[0.9]]))
[[0.66666667 0.33333333]]

See also
--------
RadiusNeighborsClassifier
KNeighborsRegressor
RadiusNeighborsRegressor
NearestNeighbors

Notes
-----
See :ref:`Nearest Neighbors <neighbors>` in the online documentation
for a discussion of the choice of ``algorithm`` and ``leaf_size``.

.. warning::

   Regarding the Nearest Neighbors algorithms, if it is found that two
   neighbors, neighbor `k+1` and `k`, have identical distances
   but different labels, the results will depend on the ordering of the
   training data.

https://en.wikipedia.org/wiki/K-nearest_neighbor_algorithm
File:           /Applications/anaconda3/lib/python3.7/site-packages/sklearn/neighbors/_classification.py
Type:           ABCMeta
Subclasses:     
1
2
KNNClf = KNeighborsClassifier(n_neighbors=3)
KNNClf.fit(X_train, Y_train)
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
                     metric_params=None, n_jobs=None, n_neighbors=3, p=2,
                     weights='uniform')
1
2
res = KNNClf.predict(X_test)
res
array([0, 1, 1, 0, 2, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 0, 1, 1, 0, 0, 1, 1,
       1, 0, 2, 1, 0, 0, 1, 2])
1
Y_test
array([0, 1, 1, 0, 2, 1, 2, 0, 0, 2, 1, 0, 2, 1, 1, 0, 1, 1, 0, 0, 1, 1,
       1, 0, 2, 1, 0, 0, 1, 2])
1
acc = sum(res == Y_test)
1
print('accuracy ', acc / len(Y_test))
accuracy  1.0
1
2


手动实现KNN

1
2
import numpy as np
import matplotlib.pyplot as plt
1
2
3
4
5
6
7
8
9
10
11
12
raw_data_x = [[3.393533211, 2.331273381],
[3.110073483, 1.781539638],
[1.343808831, 3.368360954],
[3.582294042, 4.679179110],
[2.280362439, 2.866990263],
[7.423436942, 4.696522875],
[5.745051997, 3.533989803],
[9.172168622, 2.511101045],
[7.792783481, 3.424088941],
[7.939820817, 0.791637231]
]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]
1
2
x_train = np.array(raw_data_x)
y_train = np.array(raw_data_y)
1
x_train
array([[3.39353321, 2.33127338],
       [3.11007348, 1.78153964],
       [1.34380883, 3.36836095],
       [3.58229404, 4.67917911],
       [2.28036244, 2.86699026],
       [7.42343694, 4.69652288],
       [5.745052  , 3.5339898 ],
       [9.17216862, 2.51110105],
       [7.79278348, 3.42408894],
       [7.93982082, 0.79163723]])
1
y_train==1
array([False, False, False, False, False,  True,  True,  True,  True,
        True])
1
2
3
plt.scatter(x_train[y_train==1, 0], x_train[y_train==1, 1], color='r', label='1')
plt.scatter(x_train[y_train==0, 0], x_train[y_train==0, 1], color='g', label='0')
plt.legend()
<matplotlib.legend.Legend at 0x122311ad0>

png

1
2
3
4
5
6
7
x = np.array([8.093607318, 3.365731514])

plt.scatter(x_train[y_train==1, 0], x_train[y_train==1, 1], color='r', label='1')
plt.scatter(x_train[y_train==0, 0], x_train[y_train==0, 1], color='g', label='0')
plt.scatter(x[0], x[1], color='b')
plt.legend()
plt.show()

png

1
2
import math
distance = []
1
2
3
for each in x_train:
d = math.sqrt(np.sum((each - x) ** 2))
distance.append(d)
1
distance
[4.812566907609877,
 5.229270827235305,
 6.749798999160064,
 4.6986266144110695,
 5.83460014556857,
 1.4900114024329525,
 2.354574897431513,
 1.3761132675144652,
 0.3064319992975,
 2.5786840957478887]
1
2
distances = [math.sqrt(np.sum((each - x) ** 2)) for each in x_train]
distances
[4.812566907609877,
 5.229270827235305,
 6.749798999160064,
 4.6986266144110695,
 5.83460014556857,
 1.4900114024329525,
 2.354574897431513,
 1.3761132675144652,
 0.3064319992975,
 2.5786840957478887]
1
2
nearest = np.argsort(distances)
nearest
array([8, 7, 5, 6, 9, 3, 0, 1, 4, 2])
1
2
3
k = 6
topK_y = [y_train[i] for i in nearest[:k]]
topK_y
[1, 1, 1, 1, 1, 0]
1
2
3
import collections
votes = collections.Counter(topK_y)
votes
Counter({1: 5, 0: 1})
1
votes.most_common(1)
[(1, 5)]
1
2
predict_y = votes.most_common(1)[0][0]
predict_y
1

scikit-learn实现KNN

1
2
import numpy as np
from sklearn.neighbors import KNeighborsClassifier
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
raw_data_x = [[3.393533211, 2.331273381],
[3.110073483, 1.781539638],
[1.343808831, 3.368360954],
[3.582294042, 4.679179110],
[2.280362439, 2.866990263],
[7.423436942, 4.696522875],
[5.745051997, 3.533989803],
[9.172168622, 2.511101045],
[7.792783481, 3.424088941],
[7.939820817, 0.791637231]
]
raw_data_y = [0, 0, 0, 0, 0, 1, 1, 1, 1, 1]

x_train = np.array(raw_data_x)
y_train = np.array(raw_data_y)

target = np.array([8.093607318, 3.365731514])
1
KNN_classifier = KNeighborsClassifier(n_neighbors=6)
1
KNN_classifier.fit(x_train, y_train)
KNeighborsClassifier(algorithm='auto', leaf_size=30, metric='minkowski',
                     metric_params=None, n_jobs=None, n_neighbors=6, p=2,
                     weights='uniform')
1
2
target = x.reshape(1, -1)
print(target)
[[8.09360732 3.36573151]]
1
KNN_classifier.predict(target)
array([1])
1
2
res = KNN_classifier.predict(target)
res[0]
1

Python 数据可视化分析


介绍

在机器学习领域中,可视化是十分重要的。在开始一项新任务时,通过可视化手段探索数据能更好地帮助人们把握数据的要点。在分析模型表现和模型报告的结果时,可视化能使分析显得更加生动鲜明。有时候,为了理解复杂的模型,我们还可以将高维空间映射为视觉上更直观的二维或三维图形。

总而言之,可视化是一个相对快捷的从数据中挖掘信息的手段。本文将使用 Pandas、Matplotlib、seaborn 等流行的库,带你上手可视化。

知识点

  • 单变量可视化的常用方法
  • 多变量可视化的常用方法
  • t-SNE

数据集

首先使用 import 载入相关依赖。

1
2
3
4
import numpy as np
import pandas as pd
import seaborn as sns
sns.set()

在第一篇文章中,我们使用的是某电信运营商的客户离网数据集,本次实验仍旧使用这个数据集。

1
df = pd.read_csv('./data/telecom_churn.csv')
1
df.head()

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes Total eve calls Total eve charge Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn
0 KS 128 415 No Yes 25 265.1 110 45.07 197.4 99 16.78 244.7 91 11.01 10.0 3 2.70 1 False
1 OH 107 415 No Yes 26 161.6 123 27.47 195.5 103 16.62 254.4 103 11.45 13.7 3 3.70 1 False
2 NJ 137 415 No No 0 243.4 114 41.38 121.2 110 10.30 162.6 104 7.32 12.2 5 3.29 0 False
3 OH 84 408 Yes No 0 299.4 71 50.90 61.9 88 5.26 196.9 89 8.86 6.6 7 1.78 2 False
4 OK 75 415 Yes No 0 166.7 113 28.34 148.3 122 12.61 186.9 121 8.41 10.1 3 2.73 3 False

最后一个数据列 Churn 离网率 是我们的目标特征,它是布尔变量,其中 True 表示公司最终丢失了此客户,False 表示客户被保留。稍后,将构建基于其他特征预测 Churn 特征的模型。

单变量可视化

单变量(univariate)分析一次只关注一个变量。当我们独立地分析一个特征时,通常最关心的是该特征值的分布情况。下面考虑不同统计类型的变量,以及相应的可视化工具。

数量特征

数量特征(quantitative feature)的值为有序数值。这些值可能是离散的,例如整数,也可能是连续的,例如实数。

直方图和密度图

直方图依照相等的间隔将值分组为柱,它的形状可能包含了数据分布的一些信息,如高斯分布、指数分布等。当分布总体呈现规律性,但有个别异常值时,你可以通过直方图辨认出来。当你使用的机器学习方法预设了某一特定分布类型(通常是高斯分布)时,知道特征值的分布是非常重要的。

最简单的查看数值变量分布的方法是使用 DataFrame 的 方法绘制直方图。

1
2
features = ['Total day minutes', 'Total intl calls']
df[features].hist(figsize = (10, 4))
array([[<matplotlib.axes._subplots.AxesSubplot object at 0x12e3076d0>,
        <matplotlib.axes._subplots.AxesSubplot object at 0x12f4cbe90>]],
      dtype=object)

png

上图表明,变量 Total day minutes 每日通话时长 呈高斯分布,而 Total intl calls 总国际呼叫数 显著右倾(它右侧的尾巴更长)。

密度图(density plots),也叫核密度图( ,KDE)是理解数值变量分布的另一个方法。它可以看成是直方图平滑( )的版本。相比直方图,它的主要优势是不依赖于柱的尺寸,更加清晰。

让我们为上面两个变量创建密度图。

1
2
df[features].plot(kind='density', subplots=True, layout=(1,2),
sharex=False, figsize=(10, 4), legend=False, title=features)
array([[<matplotlib.axes._subplots.AxesSubplot object at 0x133bcc050>,
        <matplotlib.axes._subplots.AxesSubplot object at 0x1343f1ad0>]],
      dtype=object)

png

1
sns.distplot(df['Total day calls'])
<matplotlib.axes._subplots.AxesSubplot at 0x12e4f8810>

png

当然,还可以使用 seaborn 的 方法观测数值变量的分布。例如,Total day minutes 每日通话时长 的分布。默认情况下,该方法将同时显示直方图和密度图。

1
sns.distplot(df['Total intl calls'])
<matplotlib.axes._subplots.AxesSubplot at 0x12e5134d0>

png

上图中直方图的柱形高度已进行归一化处理,表示的是密度而不是样本数。

箱型图

箱形图的主要组成部分是箱子(box),须(whisker)和一些单独的数据点(离群值),分别简单介绍如下:

  • 箱子显示了分布的四分位距,它的长度由 $25th , (\text{Q1,下四分位数})$ 和 $75th , (\text{Q3,上四分位数})$ 决定,箱中的水平线表示中位数 ($50%$)。
  • 须是从箱子处延伸出来的线,它们表示数据点的总体散布,具体而言,是位于区间 $(\text{Q1} - 1.5 \cdot \text{IQR}, \text{Q3} + 1.5 \cdot \text{IQR})$的数据点,其中 $\text{IQR} = \text{Q3} - \text{Q1}$,也就是四分位距。
  • 离群值是须之外的数据点,它们作为单独的数据点,沿着中轴绘制。

使用 seaborn 的 boxplot() 方法绘制箱形图。

1
sns.boxplot(df['Total intl calls'])
<matplotlib.axes._subplots.AxesSubplot at 0x12e6e1750>

png

上图表明,在该数据集中,大量的国际呼叫是相当少见的。

提琴形图

我们最后考虑的分布图形是提琴形图(violin plot)。提琴形图和箱形图的区别是,提琴形图聚焦于平滑后的整体分布,而箱形图显示了单独样本的特定统计数据。

使用 violinplot() 方法绘制提琴形图。下图左侧是箱形图,右侧是提琴形图。

1
2
3
4
5
6
import matplotlib.pyplot as plt

_, ax = plt.subplots(1, 2, sharey=True, figsize=(10, 4))

sns.boxplot(df['Total intl calls'], ax=ax[0])
sns.violinplot(df['Total intl calls'], ax=ax[1])
<matplotlib.axes._subplots.AxesSubplot at 0x1380219d0>

png

数据描述

除图形工具外,还可以使用 DataFrame 的 方法来获取分布的精确数值统计。

1
df[features].describe()

Total day minutes Total intl calls
count 3333.000000 3333.000000
mean 179.775098 4.479448
std 54.467389 2.461214
min 0.000000 0.000000
25% 143.700000 3.000000
50% 179.400000 4.000000
75% 216.400000 6.000000
max 350.800000 20.000000

describe() 的输出基本上是自解释性的,25%,50% 和 75% 是相应的百分数

类别特征和二元特征

类别特征(categorical features take)反映了样本的某个定性属性,它具有固定数目的值,每个值将一个观测数据分配到相应的组,这些组称为类别(category)。如果类别变量的值具有顺序,称为有序(ordinal)类别变量。

二元(binary)特征是类别特征的特例,其可能值有 2 个。

频率表

让我们查看一下目标变量 Churn 离网率 的分布情况。首先,使用 方法得到一张频率表。

1
df['Churn'].value_counts()
False    2850
True      483
Name: Churn, dtype: int64

上表显示,该数据集的 Churn 有 2850 个属于 False(Churn==0),有 483 个属于 True(Churn==1),数据集中忠实客户(Churn==0)和不忠实客户(Churn==1)的比例并不相等。我们将在以后的文章中看到,这种数据不平衡的情况会导致建立的分类模型存在一定的问题。在这种情况下,构建分类模型可能需要加重对「少数数据(在这里是 Churn==1)分类错误」这一情况的惩罚。

条形图

频率表的图形化表示是条形图。创建条形图最简单的方法是使用 seaborn 的 函数。让我们来画出两个分类变量的分布。

1
2
3
4
fig, ax = plt.subplots(1, 2, figsize=[10, 4])

sns.countplot(df['Churn'], ax=ax[0])
sns.countplot(df['Customer service calls'], ax=ax[1])
<matplotlib.axes._subplots.AxesSubplot at 0x1382242d0>

png

条形图和直方图的区别如下:

  • 直方图适合查看数值变量的分布,而条形图用于查看类别特征。
  • 直方图的 X 轴是数值;条形图的 X 轴可能是任何类型,如数字、字符串、布尔值。
  • 直方图的 X 轴是一个笛卡尔坐标轴;条形图的顺序则没有事先定义。

上左图清晰地表明了目标变量的失衡性。上右图则表明大部分客户最多打了 2-3 个客服电话就解决了他们的问题。不过,既然想要预测少数数据的分类(Churn==1),我们可能对少数不满意的客户的表现更感兴趣。所以让我们尝试一下更有趣的可视化方法:多变量可视化,看能否对预测有所帮助。

多变量可视化

多变量(multivariate)图形可以在单张图像中查看两个以上变量的联系,和单变量图形一样,可视化的类型取决于将要分析的变量的类型。

先来看看数量变量之间的相互作用。

相关矩阵

相关矩阵可揭示数据集中的数值变量的相关性。这一信息很重要,因为有一些机器学习算法(比如,线性回归和逻辑回归)不能很好地处理高度相关的输入变量。

首先,我们使用 DataFrame 的 方法计算出每对特征间的相关性。接着,我们将所得的相关矩阵(correlation matrix)传给 seaborn 的 方法,该方法根据提供的数值,渲染出一个基于色彩编码的矩阵。

1
2
3
4
numerical = list(set(df.columns) - set(['State', 'International plan', 'Voice mail plan', 'Area code', 'Churn', 'Customer service calls']))

corr = df[numerical].corr()
sns.heatmap(corr)
<matplotlib.axes._subplots.AxesSubplot at 0x1388bad50>

png

上图中,Total day charge 日话费总额 是直接基于 Total day minutes 电话的分钟数 计算得到,它被称为因变量。除了 Total day charege 外,还有 3 个因变量:Total eve charge,Total night charge,Total intl charge。这 4 个因变量并不贡献任何额外信息,我们直接去除。

1
2
3
4
numerical = list(set(numerical) - set(['Total day charge', 'Total eve charge', 'Total night charge', 'Total intl charge']))

corr = df[numerical].corr()
sns.heatmap(corr)
<matplotlib.axes._subplots.AxesSubplot at 0x1396822d0>

png

散点图

散点图(scatter plot)将两个数值变量的值显示为二维空间中的笛卡尔坐标(Cartesian coordinate)。通过 matplotlib 库的 方法可以绘制散点图。

1
plt.scatter(df['Total day minutes'], df['Total night minutes'])
<matplotlib.collections.PathCollection at 0x139a17c10>

png

我们得到了两个正态分布变量的散点图,看起来这两个变量并不相关,因为上图的形状和轴是对齐的。

seaborn 库的 方法在绘制散点图的同时会绘制两张直方图,某些情形下它们可能会更有用。

1
sns.jointplot(df['Total day minutes'], df['Total night minutes'])
<seaborn.axisgrid.JointGrid at 0x139888cd0>

png

jointplot() 方法还可以绘制平滑过的散点直方图。

1
sns.jointplot(df['Total day minutes'], df['Total night minutes'], kind='kde', color='g')
<seaborn.axisgrid.JointGrid at 0x139dc1890>

png

上图基本上就是之前讨论过的核密度图的双变量版本。

散点图矩阵

在某些情形下,我们可能想要绘制如下所示的散点图矩阵(scatterplot matrix)。它的对角线包含变量的分布,并且每对变量的散点图填充了矩阵的其余部分。

1
2
# %config InlineBackend.figure_format = 'png'
sns.pairplot(df[numerical])
<seaborn.axisgrid.PairGrid at 0x139cb5810>

png

数量和类别

为了让图形更有趣一点,可以尝试从数值和类别特征的相互作用中得到预测 Churn 的新信息,更具体地,让我们看看输入变量和目标变量 Churn 的关系。使用 方法的 hue 参数来指定感兴趣的类别特征。

1
sns.lmplot('Total day minutes', 'Total night minutes', data=df, hue='Churn', fit_reg=False)
<seaborn.axisgrid.FacetGrid at 0x13e7df950>

png

看起来不忠实客户偏向右上角,也就是倾向于在白天和夜间打更多电话的客户。当然,这不是非常明显,我们也不会基于这一图形下任何确定性的结论。

现在,创建箱形图,以可视化忠实客户(Churn=0)和离网客户(Churn=1)这两个互斥分组中数值变量分布的统计数据。

1
2
3
4
5
6
7
8
9
numerical.append('Customer service calls')
print(numerical)
fig, axes = plt.subplots(3, 4, figsize=[10, 7])
for index, feat in enumerate(numerical):
ax = axes[int(index / 4), index % 4]
sns.boxplot(df['Churn'], df[feat], ax=ax)
ax.set_xlabel('')
ax.set_ylabel(feat)
fig.tight_layout()
['Total day minutes', 'Total night minutes', 'Number vmail messages', 'Total eve calls', 'Account length', 'Total intl calls', 'Total eve minutes', 'Total night calls', 'Total day calls', 'Total intl minutes', 'Customer service calls', 'Customer service calls', 'Customer service calls', 'Customer service calls', 'Customer service calls', 'Customer service calls', 'Customer service calls', 'Customer service calls']



---------------------------------------------------------------------------

IndexError                                Traceback (most recent call last)

<ipython-input-47-539701aff8ff> in <module>
      3 fig, axes = plt.subplots(3, 4, figsize=[10, 7])
      4 for index, feat in enumerate(numerical):
----> 5     ax = axes[int(index / 4), index % 4]
      6     sns.boxplot(df['Churn'], df[feat], ax=ax)
      7     ax.set_xlabel('')


IndexError: index 3 is out of bounds for axis 0 with size 3

png

上面的图表表明,两组之间分歧最大的分布是这三个变量:Total day minutes 日通话分钟数、Customer service calls 客服呼叫数、Number vmail messages 语音邮件数。在后续的课程中,我们将学习如何使用随机森林(Random Forest)或梯度提升(Gradient Boosting)来判定特征对分类的重要性,届时可以清晰地看到,前两个特征对于离网预测模型而言确实非常重要。

创建箱型图和提琴形图,查看忠实客户和不忠实客户的日通话分钟数。

1
2
3
4
5
_, axes = plt.subplots(2, 2, sharex=True, sharey=True, figsize=[10, 8])
sns.boxplot(x='Churn', y='Total day minutes', data=df, ax=axes[0][0])
sns.violinplot(x='Churn', y="Total day minutes", data=df, ax=axes[0][1])
sns.boxplot(x='Churn', y='Total night minutes', data=df, ax=axes[1][0])
sns.violinplot(x='Churn', y="Total night minutes", data=df, ax=axes[1][1])
<matplotlib.axes._subplots.AxesSubplot at 0x140f70290>

png

上图表明,不忠实客户倾向于打更多的电话。

我们还可以发现一个有趣的信息:平均而言,离网客户是通讯服务更活跃的用户。或许是他们对话费不满意,所以预防离网的一个可能措施是降低通话费。当然,公司需要进行额外的经济分析,以查明这样做是否真的有利。

当想要一次性分析两个类别维度下的数量变量时,可以用 seaborn 库的 函数。例如,在同一图形中可视化 Total day minutes 日通话分钟数 和两个类别变量(Churn 和 Customer service calls)的相互作用。

1
2
sns.catplot(x='Churn', y='Total day minutes', col='Customer service calls',
data=df[df['Customer service calls'] < 8], kind='box', col_wrap=4, height=3, aspect=.8)
<seaborn.axisgrid.FacetGrid at 0x140728250>

png

上图表明,从第 4 次客服呼叫开始,Total day minutes 日通话分钟数 可能不再是客户离网(Churn==1)的主要因素。也许,除了我们之前猜测的话费原因,还有其他问题导致客户对服务不满意,这可能会导致日通话分钟数更少。

类别与类别

正如之前提到的,变量 Customer service calls 客服呼叫数 的重复值很多,因此,既可以看成数值变量,也可以看成有序类别变量。之前已通过计数图(count plot)查看过它的分布了,现在我们感兴趣的是这一有序特征和目标变量 Churn 离网率 之间的关系。

使用 countplot() 方法查看客服呼叫数的分布,这次传入 hue=Churn 参数,以便在图形中加入类别维度。

1
sns.countplot(x='Customer service calls', hue='Churn', data=df[df["Customer service calls"] < 10])
<matplotlib.axes._subplots.AxesSubplot at 0x140cb7990>

png

上图表明,呼叫客服达到 4 次以上后,离网率显著增加了。

使用 countplot() 方法查看 Churn 离网率 和二元特征 International plan 国际套餐、Voice mail plan 语音邮件套餐 的关系。

1
2
3
4
_, axes = plt.subplots(1, 2, sharey=True, figsize=(10, 4))

sns.countplot(x='International plan', hue='Churn', data=df, ax=axes[0])
sns.countplot(x='Voice mail plan', hue='Churn', data=df, ax=axes[1])
<matplotlib.axes._subplots.AxesSubplot at 0x142344290>

png

上图表明,开通国际套餐后,离网率会高很多,即 International plan 是否开通国际套餐 是一个重要的特征。我们在 Vocie mail plan 语音邮件套餐 特征上没有观察到类似的效果。

交叉表

除了使用图形进行类别分析之外,还可以使用统计学的传统工具:交叉表(cross tabulation),即使用表格形式表示多个类别变量的频率分布。通过它可以查看某一列或某一行以了解某个变量在另一变量的作用下的分布情况。

通过交叉表查看 Churn 离网率 和类别变量 State 州 的关系。

1
pd.crosstab(df['State'], df['Churn']).T

State AK AL AR AZ CA CO CT DC DE FL ... SD TN TX UT VA VT WA WI WV WY
Churn
False 49 72 44 60 25 57 62 49 52 55 ... 52 48 54 62 72 65 52 71 96 68
True 3 8 11 4 9 9 12 5 9 8 ... 8 5 18 10 5 8 14 7 10 9

2 rows × 51 columns

上表显示,State 州 有 51 个不同的值,并且每个州只有 3 到 17 个客户抛弃了运营商。通过 groupby() 方法计算每个州的离网率,由高到低排列。

1
df.groupby(['State'])['Churn'].agg([np.mean]).sort_values(by='mean', ascending=False).T

State NJ CA TX MD SC MI MS NV WA ME ... RI WI IL NE LA IA VA AZ AK HI
mean 0.264706 0.264706 0.25 0.242857 0.233333 0.219178 0.215385 0.212121 0.212121 0.209677 ... 0.092308 0.089744 0.086207 0.081967 0.078431 0.068182 0.064935 0.0625 0.057692 0.056604

1 rows × 51 columns

上表显示,新泽西和加利福尼亚的离网率超过了 25%,夏威夷和阿拉斯加的离网率则不到 6%。然而,这些结论是基于极少的样本得出的,可能仅适用于这一特定数据集,不太具有泛用性。

全局数据集可视化

上面我们一直在研究数据集的不同方面(facet),通过猜测有趣的特征并一次选择少量特征进行可视化。如果我们想一次性显示所有特征并仍然能够解释生成的可视化,该怎么办?

降维

大多数现实世界的数据集有很多特征,每一个特征都可以被看成数据空间的一个维度。因此,我们经常需要处理高维数据集,然而可视化整个高维数据集相当难。为了从整体上查看一个数据集,需要在不损失很多数据信息的前提下,降低用于可视化的维度。这一任务被称为降维(dimensionality reduction)。降维是一个无监督学习(unsupervised learning)问题,因为它需要在不借助任何监督输入(如标签)的前提下,从数据自身得到新的低维特征。

主成分分析(Principal Component Analysis, PCA)是一个著名的降维方法,我们会在之后的课程中讨论它。但主成分分析的局限性在于,它是线性(linear)算法,这意味着对数据有某些特定的限制。

与线性方法相对的,有许多非线性方法,统称流形学习(Manifold Learning)。著名的流形学习方法之一是 t-SNE。

实验总结

本章节首先介绍了 Pandas、Matplotlib 和 seaborn 库的一些常用可视化方法,并对客户离网数据集进行了可视化分析和 t-SNE 降维。可视化是一个相对快捷的从数据中挖掘信息的手段,因此,学习这一技术并将其纳入你的日常机器学习工具箱,是很有必要的。

使用 Pandas 进行数据探索

本次实验通过分析电信运营商的客户离网率数据集来熟悉 Pandas 数据探索的常用方法,并构建一个预测客户离网率的简单模型。

Pandas 的主要方法

Pandas 是基于 NumPy 的一种工具,提供了大量数据探索的方法。Pandas 可以使用类似 SQL 的方式对 .csv、.tsv、.xlsx 等格式的数据进行处理分析。

Pandas 主要使用的数据结构是 Series 和 DataFrame 类。下面简要介绍下这两类:

  • Series 是一种类似于一维数组的对象,它由一组数据(各种 NumPy 数据类型)及一组与之相关的数据标签(即索引)组成。
  • DataFrame 是一个二维数据结构,即一张表格,其中每列数据的类型相同。你可以把它看成由 Series 实例构成的字典。

下面开始此次实验,我们将通过分析电信运营商的客户离网率数据集来展示 Pandas 的主要方法。

首先载入必要的库,即 NumPy 和 Pandas。

1
2
import numpy as np
import pandas as pd

通过 read_csv() 方法读取数据,然后使用 head() 方法查看前 5 行数据。

1
dataFrame = pd.read_csv('./data/telecom_churn.csv')

上图中的每行对应一位客户,每列对应客户的一个特征。

让我们查看一下该数据库的维度、特征名称和特征类型。

1
dataFrame.shape
(3333, 20)

上述结果表明,我们的列表包含 3333 行和 20 列。下面我们尝试打印列名。

1
dataFrame.columns
Index(['State', 'Account length', 'Area code', 'International plan',
       'Voice mail plan', 'Number vmail messages', 'Total day minutes',
       'Total day calls', 'Total day charge', 'Total eve minutes',
       'Total eve calls', 'Total eve charge', 'Total night minutes',
       'Total night calls', 'Total night charge', 'Total intl minutes',
       'Total intl calls', 'Total intl charge', 'Customer service calls',
       'Churn'],
      dtype='object')

我们还可以使用 info() 方法输出 DataFrame 的一些总体信息。

1
dataFrame.info()
<class 'pandas.core.frame.DataFrame'>
RangeIndex: 3333 entries, 0 to 3332
Data columns (total 20 columns):
State                     3333 non-null object
Account length            3333 non-null int64
Area code                 3333 non-null int64
International plan        3333 non-null object
Voice mail plan           3333 non-null object
Number vmail messages     3333 non-null int64
Total day minutes         3333 non-null float64
Total day calls           3333 non-null int64
Total day charge          3333 non-null float64
Total eve minutes         3333 non-null float64
Total eve calls           3333 non-null int64
Total eve charge          3333 non-null float64
Total night minutes       3333 non-null float64
Total night calls         3333 non-null int64
Total night charge        3333 non-null float64
Total intl minutes        3333 non-null float64
Total intl calls          3333 non-null int64
Total intl charge         3333 non-null float64
Customer service calls    3333 non-null int64
Churn                     3333 non-null bool
dtypes: bool(1), float64(8), int64(8), object(3)
memory usage: 498.1+ KB

boolint64float64object 是该数据库特征的数据类型。这一方法同时也会显示是否有缺失值,上述结果表明在该数据集中不存在缺失值,因为每列都包含 3333 个观测,和我们之前使用 shape 方法得到的数字是一致的。

astype() 方法可以更改列的类型,下列公式将 Churn 离网率 特征修改为 int64 类型。

1
2
3
4
df = dataFrame
df.head(5)
df['Churn'] = df['Churn'].astype('int64')
df.head(5)

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes Total eve calls Total eve charge Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn
0 KS 128 415 No Yes 25 265.1 110 45.07 197.4 99 16.78 244.7 91 11.01 10.0 3 2.70 1 0
1 OH 107 415 No Yes 26 161.6 123 27.47 195.5 103 16.62 254.4 103 11.45 13.7 3 3.70 1 0
2 NJ 137 415 No No 0 243.4 114 41.38 121.2 110 10.30 162.6 104 7.32 12.2 5 3.29 0 0
3 OH 84 408 Yes No 0 299.4 71 50.90 61.9 88 5.26 196.9 89 8.86 6.6 7 1.78 2 0
4 OK 75 415 Yes No 0 166.7 113 28.34 148.3 122 12.61 186.9 121 8.41 10.1 3 2.73 3 0

describe() 方法可以显示数值特征(int64float64)的基本统计学特性,如未缺失值的数值、均值、标准差、范围、四分位数等。

1
df.describe()

Account length Area code Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes Total eve calls Total eve charge Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn
count 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000 3333.000000
mean 101.064806 437.182418 8.099010 179.775098 100.435644 30.562307 200.980348 100.114311 17.083540 200.872037 100.107711 9.039325 10.237294 4.479448 2.764581 1.562856 0.144914
std 39.822106 42.371290 13.688365 54.467389 20.069084 9.259435 50.713844 19.922625 4.310668 50.573847 19.568609 2.275873 2.791840 2.461214 0.753773 1.315491 0.352067
min 1.000000 408.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 23.200000 33.000000 1.040000 0.000000 0.000000 0.000000 0.000000 0.000000
25% 74.000000 408.000000 0.000000 143.700000 87.000000 24.430000 166.600000 87.000000 14.160000 167.000000 87.000000 7.520000 8.500000 3.000000 2.300000 1.000000 0.000000
50% 101.000000 415.000000 0.000000 179.400000 101.000000 30.500000 201.400000 100.000000 17.120000 201.200000 100.000000 9.050000 10.300000 4.000000 2.780000 1.000000 0.000000
75% 127.000000 510.000000 20.000000 216.400000 114.000000 36.790000 235.300000 114.000000 20.000000 235.300000 113.000000 10.590000 12.100000 6.000000 3.270000 2.000000 0.000000
max 243.000000 510.000000 51.000000 350.800000 165.000000 59.640000 363.700000 170.000000 30.910000 395.000000 175.000000 17.770000 20.000000 20.000000 5.400000 9.000000 1.000000

通过 include 参数显式指定包含的数据类型,可以查看非数值特征的统计数据。

1
df.describe(include=['object', 'bool'])

State International plan Voice mail plan
count 3333 3333 3333
unique 51 2 2
top WV No No
freq 106 3010 2411

value_counts() 方法可以查看类别(类型为 object )和布尔值(类型为 bool )特征。让我们看下 Churn 离网率 的分布。

1
df['Churn'].value_counts()
0    2850
1     483
Name: Churn, dtype: int64

上述结果表明,在 3333 位客户中, 2850 位是忠实客户,他们的 Churn 值为 0。调用 value_counts() 函数时,加上 normalize=True 参数可以显示比例。

1
df['Churn'].value_counts(normalize=True)
0    0.855086
1    0.144914
Name: Churn, dtype: float64

排序

DataFrame 可以根据某个变量的值(也就是列)排序。比如,根据每日消费额排序(设置 ascending=False 倒序排列)。

1
df.sort_values(by='Total day charge', ascending=False).head(5)

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes Total eve calls Total eve charge Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn
365 CO 154 415 No No 0 350.8 75 59.64 216.5 94 18.40 253.9 100 11.43 10.1 9 2.73 1 1
985 NY 64 415 Yes No 0 346.8 55 58.96 249.5 79 21.21 275.4 102 12.39 13.3 9 3.59 1 1
2594 OH 115 510 Yes No 0 345.3 81 58.70 203.4 106 17.29 217.5 107 9.79 11.8 8 3.19 1 1
156 OH 83 415 No No 0 337.4 120 57.36 227.4 116 19.33 153.9 114 6.93 15.8 7 4.27 0 1
605 MO 112 415 No No 0 335.5 77 57.04 212.5 109 18.06 265.0 132 11.93 12.7 8 3.43 2 1

此外,还可以根据多个列的数值排序。下面函数实现的功能为:先按 Churn 离网率 升序排列,再按 Total day charge 每日总话费 降序排列,优先级 Churn > Tatal day charge。

1
df.sort_values(by=['Churn', 'Total day charge'], ascending=[True, False]).head()

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes Total eve calls Total eve charge Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn
688 MN 13 510 No Yes 21 315.6 105 53.65 208.9 71 17.76 260.1 123 11.70 12.1 3 3.27 3 0
2259 NC 210 415 No Yes 31 313.8 87 53.35 147.7 103 12.55 192.7 97 8.67 10.1 7 2.73 3 0
534 LA 67 510 No No 0 310.4 97 52.77 66.5 123 5.65 246.5 99 11.09 9.2 10 2.48 4 0
575 SD 114 415 No Yes 36 309.9 90 52.68 200.3 89 17.03 183.5 105 8.26 14.2 2 3.83 1 0
2858 AL 141 510 No Yes 28 308.0 123 52.36 247.8 128 21.06 152.9 103 6.88 7.4 3 2.00 1 0

索引和获取数据

DataFrame 可以以不同的方式进行索引。

使用 DataFrame['Name'] 可以得到一个单独的列。比如,离网率有多高?

1
df['Churn'].mean()
0.14491449144914492

对一家公司而言,14.5% 的离网率是一个很糟糕的数据,这么高的离网率可能导致公司破产。

布尔值索引同样很方便,语法是 df[P(df['Name'])],P 是在检查 Name 列每个元素时所使用的逻辑条件。这一索引的输出是 DataFrame 的 Name 列中满足 P 条件的行。

让我们使用布尔值索引来回答这样以下问题:离网用户的数值变量的均值是多少?

1
df[df['Churn'] == 1].mean()
Account length            102.664596
Area code                 437.817805
Number vmail messages       5.115942
Total day minutes         206.914079
Total day calls           101.335404
Total day charge           35.175921
Total eve minutes         212.410145
Total eve calls           100.561077
Total eve charge           18.054969
Total night minutes       205.231677
Total night calls         100.399586
Total night charge          9.235528
Total intl minutes         10.700000
Total intl calls            4.163561
Total intl charge           2.889545
Customer service calls      2.229814
Churn                       1.000000
dtype: float64

离网用户在白天打电话的总时长的均值是多少?

1
df[df['Churn'] == 1]['Total day minutes'].mean()
206.91407867494823

未使用国际套餐(International plan == NO)的忠实用户(Churn == 0)所打的最长的国际长途是多久?

1
2
df[(df['Churn'] == 1) & (df['International plan'] == 'No')]['Total intl minutes'].max()
df[(df['Churn'] == 0) & (df['International plan'] == 'No')]['Total intl minutes'].max()
18.9

DataFrame 可以通过列名、行名、行号进行索引。loc 方法为通过名称索引,iloc 方法为通过数字索引。

通过 loc 方法输出 0 至 5 行、State 州 至 Area code 区号 的数据。

1
df.loc[0:5, ['State','Area code']]

State Area code
0 KS 415
1 OH 415
2 NJ 415
3 OH 408
4 OK 415
5 AL 510

通过 ilo 方法输出前 5 行的前 3 列数据(和典型的 Python 切片一样,不含最大值)。

1
df.iloc[0:5, 0:3]

State Account length Area code
0 KS 128 415
1 OH 107 415
2 NJ 137 415
3 OH 84 408
4 OK 75 415

df[:1]df[-1:] 可以得到 DataFrame 的首行和末行。

1
df[-2:]

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes Total eve calls Total eve charge Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn
3331 CT 184 510 Yes No 0 213.8 105 36.35 159.6 84 13.57 139.2 137 6.26 5.0 10 1.35 2 0
3332 TN 74 415 No Yes 25 234.4 113 39.85 265.9 82 22.60 241.4 77 10.86 13.7 4 3.70 0 0

应用函数到单元格、列、行

下面通过 apply() 方法应用函数 max 至每一列,即输出每列的最大值。

1
df.apply(np.max)
State                        WY
Account length              243
Area code                   510
International plan          Yes
Voice mail plan             Yes
Number vmail messages        51
Total day minutes         350.8
Total day calls             165
Total day charge          59.64
Total eve minutes         363.7
Total eve calls             170
Total eve charge          30.91
Total night minutes         395
Total night calls           175
Total night charge        17.77
Total intl minutes           20
Total intl calls             20
Total intl charge           5.4
Customer service calls        9
Churn                         1
dtype: object

apply() 方法也可以应用函数至每一行,指定 axis=1 即可。在这种情况下,使用 lambda 函数十分方便。比如,下面函数选中了所有以 W 开头的州。

1
df[df['State'].apply(lambda state: state[0] == 'W')].head()

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes Total eve calls Total eve charge Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn
9 WV 141 415 Yes Yes 37 258.6 84 43.96 222.0 111 18.87 326.4 97 14.69 11.2 5 3.02 0 0
26 WY 57 408 No Yes 39 213.0 115 36.21 191.1 112 16.24 182.7 115 8.22 9.5 3 2.57 0 0
44 WI 64 510 No No 0 154.0 67 26.18 225.8 118 19.19 265.3 86 11.94 3.5 3 0.95 1 0
49 WY 97 415 No Yes 24 133.2 135 22.64 217.2 58 18.46 70.6 79 3.18 11.0 3 2.97 1 0
54 WY 87 415 No No 0 151.0 83 25.67 219.7 116 18.67 203.9 127 9.18 9.7 3 2.62 5 1

map() 方法可以通过一个 {old_value:new_value} 形式的字典替换某一列中的值。

1
2
3
d = {'No': False, 'Yes': True}
df['International plan'] = df['International plan'].map(d)
df.head()

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes Total eve calls Total eve charge Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn
0 KS 128 415 False Yes 25 265.1 110 45.07 197.4 99 16.78 244.7 91 11.01 10.0 3 2.70 1 0
1 OH 107 415 False Yes 26 161.6 123 27.47 195.5 103 16.62 254.4 103 11.45 13.7 3 3.70 1 0
2 NJ 137 415 False No 0 243.4 114 41.38 121.2 110 10.30 162.6 104 7.32 12.2 5 3.29 0 0
3 OH 84 408 True No 0 299.4 71 50.90 61.9 88 5.26 196.9 89 8.86 6.6 7 1.78 2 0
4 OK 75 415 True No 0 166.7 113 28.34 148.3 122 12.61 186.9 121 8.41 10.1 3 2.73 3 0

当然,使用 repalce() 方法一样可以达到替换的目的。

1
2
df = df.replace({'Voice mail plan': d})
df.head()

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes Total eve calls Total eve charge Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn
0 KS 128 415 False True 25 265.1 110 45.07 197.4 99 16.78 244.7 91 11.01 10.0 3 2.70 1 0
1 OH 107 415 False True 26 161.6 123 27.47 195.5 103 16.62 254.4 103 11.45 13.7 3 3.70 1 0
2 NJ 137 415 False False 0 243.4 114 41.38 121.2 110 10.30 162.6 104 7.32 12.2 5 3.29 0 0
3 OH 84 408 True False 0 299.4 71 50.90 61.9 88 5.26 196.9 89 8.86 6.6 7 1.78 2 0
4 OK 75 415 True False 0 166.7 113 28.34 148.3 122 12.61 186.9 121 8.41 10.1 3 2.73 3 0

增减 DataFrame 的行列

在 DataFrame 中新增列有很多方法,比如,使用 insert()方法添加列,为所有用户计算总的 Total calls 电话量。

1
2
3
4
5
6
total_calls = df['Total day calls'] + df['Total eve calls'] + \
df['Total night calls'] + df['Total intl calls']

df.insert(loc=len(df.columns), column='Total calls 2', value=total_calls)

df.head()

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes ... Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn Total calls Total calls 2
0 KS 128 415 False True 25 265.1 110 45.07 197.4 ... 244.7 91 11.01 10.0 3 2.70 1 0 303 303
1 OH 107 415 False True 26 161.6 123 27.47 195.5 ... 254.4 103 11.45 13.7 3 3.70 1 0 332 332
2 NJ 137 415 False False 0 243.4 114 41.38 121.2 ... 162.6 104 7.32 12.2 5 3.29 0 0 333 333
3 OH 84 408 True False 0 299.4 71 50.90 61.9 ... 196.9 89 8.86 6.6 7 1.78 2 0 255 255
4 OK 75 415 True False 0 166.7 113 28.34 148.3 ... 186.9 121 8.41 10.1 3 2.73 3 0 359 359

5 rows × 22 columns

上面的代码创建了一个中间 Series 实例,即 tatal_calls,其实可以在不创造这个实例的情况下直接添加列。

1
2
3
df['Total charge'] = df['Total day charge'] + df['Total eve charge'] + \
df['Total night charge'] + df['Total intl charge']
df.head()

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes ... Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn Total calls Total calls 2 Total charge
0 KS 128 415 False True 25 265.1 110 45.07 197.4 ... 91 11.01 10.0 3 2.70 1 0 303 303 75.56
1 OH 107 415 False True 26 161.6 123 27.47 195.5 ... 103 11.45 13.7 3 3.70 1 0 332 332 59.24
2 NJ 137 415 False False 0 243.4 114 41.38 121.2 ... 104 7.32 12.2 5 3.29 0 0 333 333 62.29
3 OH 84 408 True False 0 299.4 71 50.90 61.9 ... 89 8.86 6.6 7 1.78 2 0 255 255 66.80
4 OK 75 415 True False 0 166.7 113 28.34 148.3 ... 121 8.41 10.1 3 2.73 3 0 359 359 52.09

5 rows × 23 columns

使用 drop() 方法删除列和行。

1
2
df1 = df.drop([1, 2])
df1.head()

State Account length Area code International plan Voice mail plan Number vmail messages Total day minutes Total day calls Total day charge Total eve minutes ... Total night minutes Total night calls Total night charge Total intl minutes Total intl calls Total intl charge Customer service calls Churn Total calls Total charge
0 KS 128 415 False True 25 265.1 110 45.07 197.4 ... 244.7 91 11.01 10.0 3 2.70 1 0 303 75.56
3 OH 84 408 True False 0 299.4 71 50.90 61.9 ... 196.9 89 8.86 6.6 7 1.78 2 0 255 66.80
4 OK 75 415 True False 0 166.7 113 28.34 148.3 ... 186.9 121 8.41 10.1 3 2.73 3 0 359 52.09
5 AL 118 510 True False 0 223.4 98 37.98 220.6 ... 203.9 118 9.18 6.3 6 1.70 0 0 323 67.61
6 MA 121 510 False True 24 218.2 88 37.09 348.5 ... 212.6 118 9.57 7.5 7 2.03 3 0 321 78.31

5 rows × 22 columns

对上述代码的部分解释:

  • 将相应的索引 ['Total charge', 'Total calls']axis 参数(1 表示删除列,0 表示删除行,默认值为 0)传给 drop
  • inplace 参数表示是否修改原始 DataFrame (False 表示不修改现有 DataFrame,返回一个新 DataFrame,True 表示修改当前 DataFrame)。

预测离网率

首先,通过 crosstab() 方法构建一个交叉表来查看 International plan 国际套餐 变量和 Churn 离网率 的相关性,同时使用 countplot() 方法构建计数直方图来可视化结果。

1
2
3
# 加载模块,配置绘图
import matplotlib.pyplot as plt
import seaborn as sns
1
sns.countplot(x='International plan', hue='Churn', data=df)
<matplotlib.axes._subplots.AxesSubplot at 0x11f0c8450>

png

上图表明,开通了国际套餐的用户的离网率要高很多,这是一个很有趣的观测结果。也许,国际电话高昂的话费让客户很不满意。

同理,查看 Customer service calls 客服呼叫 变量与 Chunrn 离网率 的相关性,并可视化结果。

1
pd.crosstab(df['Churn'], df['Customer service calls'], margins=True)

Customer service calls 0 1 2 3 4 5 6 7 8 9 All
Churn
0 605 1059 672 385 90 26 8 4 1 0 2850
1 92 122 87 44 76 40 14 5 1 2 483
All 697 1181 759 429 166 66 22 9 2 2 3333
1
sns.countplot(x='Customer service calls', hue='Churn', data=df)
<matplotlib.axes._subplots.AxesSubplot at 0x11cb70d50>

png

上图表明,在客服呼叫 4 次之后,客户的离网率显著提升。

为了更好的突出 Customer service call 客服呼叫 和 Churn 离网率 的关系,可以给 DataFrame 添加一个二元属性 Many_service_calls,即客户呼叫超过 3 次(Customer service calls > 3)。看下它与离网率的相关性,并可视化结果。

1
2
3
df['Many_service_calls'] = (df['Customer service calls'] > 3).astype('int')

pd.crosstab(df['Many_service_calls'], df['Churn'], margins=True)

Churn 0 1 All
Many_service_calls
0 2721 345 3066
1 129 138 267
All 2850 483 3333
1
sns.countplot(x='Many_service_calls', hue='Churn', data=df)
<matplotlib.axes._subplots.AxesSubplot at 0x11ce1c850>

png

现在我们可以创建另一张交叉表,将 Churn 离网率 与 International plan 国际套餐 及新创建的 Many_service_calls 多次客服呼叫 关联起来。

1
pd.crosstab(df['Many_service_calls'] & df['International plan'], df['Churn'])

Churn 0 1
row_0
False 2841 464
True 9 19

上表表明,在客服呼叫次数超过 3 次并且已办理 International Plan 国际套餐 的情况下,预测一名客户不忠诚的准确率(Accuracy)可以达到 85.8%,计算公式如下:

$$准确率(Accuracy)=\frac{TP+TN}{TP+TN+FP+FN}=\frac{2841+19}{2841+9+19+464}\times100%$$

其中,TP 表示将 True 预测为 True 的数量,TN 表示将 Flase 预测为 Flase 的数量,FP 表示将 Flase 预测为 True 的数量,FN 表示将 True 预测为 Flase 的数量。

复习一下本次实验的内容:

  • 样本中忠实客户的份额为 85.5%。这意味着最简单的预测「忠实客户」的模型有 85.5% 的概率猜对。也就是说,后续模型的准确率(Accuracy)不应该比这个数字少,并且很有希望显著高于这个数字。
  • 基于一个简单的「(客服呼叫次数 > 3) & (国际套餐 = True) => Churn = 1, else Churn = 0」规则的预测模型,可以得到 85.8% 的准确率。以后我们将讨论决策树,看看如何仅仅基于输入数据自动找出类似的规则,而不需要我们手工设定。我们没有应用机器学习方法就得到了两个准确率(85.5% 和 85.8%),它们可作为后续其他模型的基线。如果经过大量的努力,我们仅将准确率提高了 0.5%,那么我们努力的方向可能出现了偏差,因为仅仅使用一个包含两个限制规则的简单模型就已提升了 0.3% 的准确率。
  • 在训练复杂模型之前,建议预处理一下数据,绘制一些图表,做一些简单的假设。此外,在实际任务上应用机器学习时,通常从简单的方案开始,接着尝试更复杂的方案。

实验总结

本次实验使用 Pandas 对数据进行了一定程度的分析和探索,交叉表、透视表等方法的运用将使你在数据探索过程中事半功倍。

MacOS安装Anaconda

conda配置文件

位置
~/.condarc

配置zsh环境变量
export PATH=/Applications/anaconda3/bin:$PATH

conda镜像源

添加镜像指令(亦可以直接在配置文件中添加)
conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/pkgs/free/
conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/cloud/conda-forge
conda config --add channels https://mirrors.tuna.tsinghua.edu.cn/anaconda/cloud/msys2/

设置搜索时显示通道地址
conda config --set show_channel_urls yes

shell虚拟环境

取消命令行前出现的(base)

  • 每次在命令行通过conda deactivate退出base环境回到系统自动的环境

  • conda config --set auto_activate_base false

安装TensorFlow环境

新建一个tf环境
conda create -n tensorflow python=3.7

进入tf环境
conda activate tensorflow

pip安装tf
pip install -i https://pypi.tuna.tsinghua.edu.cn/simple tensorflow

指定版本安装
conda install tensorflow=1.4
pip install tensorflow==1.4

卸载

安装clean包
conda install anaconda-clean

文件进行删除
anaconda-clean

删除Anaconda主文件包(默认路径)
/opt/anaconda3

矩阵连乘 (Multiplying a sequence of matrices)

我们想从两个以上矩阵连乘的式子中得到最佳的次序,使得计算时乘法运算最少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class DynamicProgramming {

private static final int N = 5;

public static void main(String[] args) {
int[][] C = new int[N][N];
int[][] S = new int[N][N];
int[] r = {4, 5, 3, 6, 4, 5};

for (int i = 0; i < N; i++) {// 初始化 最小乘运算数组
for (int j = 0; j < N; j++) {
C[i][j] = 0;
}
}

for (int i = 0; i < N; i++) {// 初始化 分割位置
for (int j = 0; j < N; j++) {
S[i][j] = 0;
}
}

for (int p = 2; p <= N; p++) {// P 为间隔
for (int i = 0, j; i < N - p + 1; i++) {// i 为起始值
j = i + p - 1;// j 为终止值
C[i][j] = C[i][i] + C[i + 1][j] + r[i] * r[i + 1] * r[j + 1];// 赋 C[i][j] 的初值方便下文比较取得最小值
S[i][j] = i;
for (int k = i; k< j; k++) {// k 为中间分割值
int temp = C[i][k] + C[k + 1][j] + r[i] * r[k + 1] * r[j + 1];

if (temp < C[i][j]) {// 取得每次分割后的最小值
C[i][j] = temp;
S[i][j] = k;
}
}
}
}

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
System.out.print(C[i][j] + "\t");
}
System.out.println();
}

System.out.println();

for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j > i) System.out.print(S[i][j] + 1 + "\t");
else System.out.print(0 + "\t");
}
System.out.println();
}
}
}

/* result
0 60 132 180 252
0 0 90 132 207
0 0 0 72 132
0 0 0 0 120
0 0 0 0 0

0 1 2 2 2
0 0 2 2 2
0 0 0 3 4
0 0 0 0 4
0 0 0 0 0

(A1 * A2) * ((A3 * A4) * A5)
*/

最长公共子序列 (Longest Common Subsequence)

给定两个字符串 text1 和 text2,返回这两个字符串的最长公共子序列的长度。

一个字符串的 子序列 是指这样一个新的字符串:它是由原字符串在不改变字符的相对顺序的情况下删除某些字符(也可以不删除任何字符)后组成的新字符串。
例如,”ace” 是 “abcde” 的子序列,但 “aec” 不是 “abcde” 的子序列。两个字符串的「公共子序列」是这两个字符串所共同拥有的子序列。

若这两个字符串没有公共子序列,则返回 0。

示例:

输入:text1 = “abcde”, text2 = “ace”
输出:3
解释:最长公共子序列是 “ace”,它的长度为 3。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
public class DynamicProgramming {

public static void main(String[] args) {
String A = "xzyzzyx";
String B = "zxyyzxz";
String res = "";

int[][] dp = new int[A.length() + 1][B.length() + 1];

for (int i = 0; i <= A.length(); i++) {
for (int j = 0; j <= B.length(); j++) {
if (i == 0 || j == 0) {
dp[i][j] = 0;
continue;
}

if (A.charAt(i - 1) == B.charAt(j - 1)) {
dp[i][j] = dp[i - 1][j - 1] + 1;
continue;
}

if (A.charAt(i - 1) != B.charAt(j - 1)) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
continue;
}
}
}

int row = A.length();
int col = B.length();

while (row > 0 && col > 0) {
if (dp[row - 1][col - 1] < dp[row][col]) {
res = res + A.charAt(row - 1);
row--; col--;
} else {
row--;
}
}

System.out.println("DP matrix is below: ");
for (int i = 0; i <= A.length(); i++) {
for (int j = 0; j <= B.length(); j++) {
System.out.print(dp[i][j] + " ");
}
System.out.println();
}

System.out.print("One of th LCS is: ");
for (int i = res.length() - 1; i >= 0; i--) {
System.out.print(res.charAt(i));
}
}
}

/* result

DP matrix is below:
0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1
0 1 1 1 1 2 2 2
0 1 1 2 2 2 2 2
0 1 1 2 2 3 3 3
0 1 1 2 2 3 3 4
0 1 1 2 3 3 3 4
0 1 2 2 3 3 4 4

One of th LCS is: xyzx

*/

典型的动态规划问题

首先声明一个以字符串A为行B为列的二维数组。

  • i=0j=0dp[i][j]=0
  • ai=bidp[i][j]=dp[i-1][j-1](对应位置相等的话公共子串在row-1,col-1的情况下加1.)
  • ai!=bidp[i][j]=max{dp[i-1][j], dp[i][j-1]}(不想等则取字符串A,B上一个相邻字符最长公共子串.)

最后显示一个最长子串时必须从后向前判断,顺序判断出的可能不是最长的子串。

Numpy训练实例

绘制Sigmoid函数与ReLU函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import numpy as np
import matplotlib.pyplot as plt

# 设置图片大小
plt.figure(figsize=(8, 3))

# x为1维数组
x = np.arange(-10, 10, 0.1)

# Sigmoid函数
s = 1. / (1 + np.exp(-x))

# ReLU函数
y = np.clip(x, a_min=0., a_max=None)

# 绘制Sigmoid函数
f = plt.subplot(121)
plt.plot(x, s, color='r')
plt.text(-5, 0.9, r'$y=\sigma(x)$', fontsize=13)
currentAxis = plt.gca()
currentAxis.xaxis.set_label_text('x', fontsize=15)
currentAxis.yaxis.set_label_text('y', fontsize=15)

# 绘制ReLU函数
f = plt.subplot(122)
plt.plot(x, y, color='g')
plt.text(-3, 9, r'$y=ReLU(x)$', fontsize=13)
currentAxis = plt.gca()
currentAxis.xaxis.set_label_text('x', fontsize=15)
currentAxis.yaxis.set_label_text('y', fontsize=15)

plt.show()

Mariadb的使用

Linux上已经摒弃了Mysql,以下是一些Mariadb的基本用法。

创建用户

CREATE USER 'username'@'host' IDENTIFIED BY 'password';

用户权限

GRANT privileges ON databasename.tablename TO 'username'@'host'

查看权限

show grants for 'root'@'%';

例:
MariaDB [(none)]> grant all on *.* to 'root'@'%';
MariaDB [mysql]> flush privileges;
MariaDB [(none)]> grant all privileges on *.* to 'root'@'%' identified by 'password';

查看用户

select user from mysql.user;

查看当前用户

select current_user;

删除用户

delete from mysql.user where user='root';

撤销权限

REVOKE privileges ON databasename.tablename FROM 'username'@'host';

[Linux]安装Java在多个版本中切换

查看yum中的Java版本

$ yum search java-1.8

安装JDK

yum install java-1.8.0-openjdk-devel

安装JDK包含JRE

Java Development EnvironmentKit 为 JDK
Java Runtime Environment 为 JRE

切换Java版本

$ sudo update-alternatives --display java 查看安装了几个java
$ sudo update-alternatives --config java 设置java的版本
$ alternatives --config javac 设置javac的版本

如已手动安装的可以用下面的命令去添加到列表
$ alternatives --install /usr/bin/java java /usr/java/jdk1.8/bin/java 180000
$ alternatives --install /usr/bin/java javac /usr/java/jdk1.8/bin/javac 180000

波士顿房价预测

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
import numpy as np
import json
import matplotlib.pyplot as plt


def load_data():
datafile = './data/housing.data'
data = np.fromfile(datafile, sep=' ')

feature_names = ['CRIM', 'ZN', 'INDUS', 'CHAS', 'NOX', 'RM', 'AGE', 'DIS',
'RAD', 'TAX', 'PTRATIO', 'B', 'LSTAT', 'MEDV']
feature_num = len(feature_names)
data = data.reshape([data.shape[0] // feature_num, feature_num])

ratio = 0.8
offset = int(data.shape[0] * ratio)
training_data = data[:offset]

maximums, minimums, avgs = training_data.max(axis=0), training_data.min(axis=0), training_data.sum(axis=0) / \
training_data.shape[0]
for i in range(feature_num):
data[:, i] = (data[:, i] - avgs[i]) / (maximums[i] - minimums[i])

training_data = data[:offset]
test_data = data[offset:]

return training_data, test_data


class Network(object):
def __init__(self, num_of_weights):
# 随机产生w的初始值
# 为了保持程序每次运行结果的一致性,此处设置固定的随机数种子
np.random.seed(0)
self.w = np.random.randn(num_of_weights, 1)
self.b = 0.

def forward(self, x):
z = np.dot(x, self.w) + self.b
return z

def loss(self, z, y):
error = z - y
cost = error * error
cost = np.mean(cost)
return cost

def gradient(self, x, y):
z = self.forward(x)
gradient_w = (z - y) * x
gradient_w = np.mean(gradient_w, axis=0)
gradient_w = gradient_w[:, np.newaxis]
gradient_b = (z - y)
gradient_b = np.mean(gradient_b)

return gradient_w, gradient_b

def update(self, gradient_w, gradient_b, eta=0.01):
self.w = self.w - eta * gradient_w
self.b = self.b - eta * gradient_b

def train(self, x, y, iterations=100, eta=0.01):
losses = []
for i in range(iterations):
z = self.forward(x)
L = self.loss(z, y)
gradient_w, gradient_b = self.gradient(x, y)
self.update(gradient_w, gradient_b, eta)
losses.append(L)
if (i + 1) % 10 == 0:
print('iter {}, loss {}'.format(i, L))
return losses



# 获取数据
train_data, test_data = load_data()
x = train_data[:, :-1]
y = train_data[:, -1:]
# 创建网络
net = Network(13)
num_iterations=1000
# 启动训练
losses = net.train(x,y, iterations=num_iterations, eta=0.01)

# 画出损失函数的变化趋势
plot_x = np.arange(num_iterations)
plot_y = np.array(losses)
plt.plot(plot_x, plot_y)
plt.show()


class NetworkOfSGD(object):
def __init__(self, num_of_weights):
# 随机产生w的初始值
# 为了保持程序每次运行结果的一致性,此处设置固定的随机数种子
# np.random.seed(0)
self.w = np.random.randn(num_of_weights, 1)
self.b = 0.

def forward(self, x):
z = np.dot(x, self.w) + self.b
return z

def loss(self, z, y):
error = z - y
num_samples = error.shape[0]
cost = error * error
cost = np.sum(cost) / num_samples
return cost

def gradient(self, x, y):
z = self.forward(x)
N = x.shape[0]
gradient_w = 1. / N * np.sum((z - y) * x, axis=0)
gradient_w = gradient_w[:, np.newaxis]
gradient_b = 1. / N * np.sum(z - y)
return gradient_w, gradient_b

def update(self, gradient_w, gradient_b, eta=0.01):
self.w = self.w - eta * gradient_w
self.b = self.b - eta * gradient_b

def train(self, training_data, num_epoches, batch_size=10, eta=0.01):
n = len(training_data)
losses = []
for epoch_id in range(num_epoches):
# 在每轮迭代开始之前,将训练数据的顺序随机的打乱,
# 然后再按每次取batch_size条数据的方式取出
np.random.shuffle(training_data)
# 将训练数据进行拆分,每个mini_batch包含batch_size条的数据
mini_batches = [training_data[k:k + batch_size] for k in range(0, n, batch_size)]
for iter_id, mini_batch in enumerate(mini_batches):
# print(self.w.shape)
# print(self.b)
x = mini_batch[:, :-1]
y = mini_batch[:, -1:]
a = self.forward(x)
loss = self.loss(a, y)
gradient_w, gradient_b = self.gradient(x, y)
self.update(gradient_w, gradient_b, eta)
losses.append(loss)
print('Epoch {:3d} / iter {:3d}, loss = {:.4f}'.
format(epoch_id, iter_id, loss))

return losses


# 获取数据
train_data, test_data = load_data()

# 创建网络
net = NetworkOfSGD(13)
# 启动训练
losses = net.train(train_data, num_epoches=50, batch_size=100, eta=0.1)

# 画出损失函数的变化趋势
plot_x = np.arange(len(losses))
plot_y = np.array(losses)
plt.plot(plot_x, plot_y)
plt.show()

V2ray

安装V2ray

  • 安装脚本

执行安装脚本

$ wget https://install.direct/go.sh

运行脚本

$ sudo bash go.sh

  • 运行V2ray

$ sudo systemctl start v2ray

  • V2ray配置文件

/etc/v2ray/config.json

TLS

  • 安装脚本

执行以下命令,acme.sh 会安装到 ~/.acme.sh 目录下。
$ curl https://get.acme.sh | sh

安装成功后执行 source ~/.bashrc 以确保脚本所设置的命令别名生效。

如果安装报错,那么可能是因为系统缺少 acme.sh 所需要的依赖项,acme.sh 的依赖项主要是 socat,我们通过以下命令来安装这些依赖项,然后重新安装一遍 acme.sh:

$ sudo apt-get install openssl cron socat curl

  • 分发证书

使用Nginx监听80端口进行证书分发

$ acme.sh --issue -d tunnel.edlison.xyz --nginx

使用acme自带的standalone进行端口监听

$ acme.sh --issue -d tunnel.edlieon.xyz --standalone

Example

$ acme.sh --issue -d tunnel.edlison.xyz --nginx --keylength ec-256

--keylength 表示密钥长度,后面的值可以是 ec-256 、ec-384、2048、3072、4096、8192,带有 ec 表示生成的是 ECC 证书,没有则是 RSA 证书。在安全性上 256 位的 ECC 证书等同于 3072 位的 RSA 证书

  • 更新证书

$ acme.sh --renew -d tunnel.edlison.xyz --force --ecc

由于 Let’s Encrypt 的证书有效期只有 3 个月,因此需要 90 天至少要更新一次证书,acme.sh 脚本会每 60 天自动更新证书。也可以手动更新。--ecc生成的ECC证书

  • 安装证书和密钥

将证书安装到V2ray目录下

1
2
3
$ acme.sh --installcert -d tunnel.edlison.xyz --ecc \
--fullchain-file /etc/v2ray/v2ray.crt \
--key-file /etc/v2ray/v2ray.key
  • 配置文件
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
{
"inbounds": [
{
"port": 443, // 建议使用 443 端口
"protocol": "vmess",
"settings": {
"clients": [
{
"id": "23ad6b10-8d1a-40f7-8ad0-e3e35cd38297",
"alterId": 64
}
]
},
"streamSettings": {
"network": "tcp",
"security": "tls", // security 要设置为 tls 才会启用 TLS
"tlsSettings": {
"certificates": [
{
"certificateFile": "/etc/v2ray/v2ray.crt", // 证书文件
"keyFile": "/etc/v2ray/v2ray.key" // 密钥文件
}
]
}
}
}
],
"outbounds": [
{
"protocol": "freedom",
"settings": {}
}
]
}

Nginx

  • Start

配置文件

$ nginx -c /etc/nginx/nginx.conf

启动Nginx

$ nginx -s reload

  • config

Nginx 仅需监听80端口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
server {
listen 80;
listen [::]:80;
server_name tunnel.edlison.xyz;

#return 301 https://$server_name$request_uri; // 可以将流量转向https

root /usr/share/nginx/html;

# Load configuration files for the default server block.
include /etc/nginx/default.d/*.conf;

location / {
}

error_page 404 /404.html;
location = /40x.html {
}

error_page 500 502 503 504 /50x.html;
location = /50x.html {
}
}

WebSocket + TLS + Web

这次 TLS 的配置将写入 Nginx/Caddy/Apache 配置中,由这些软件来监听 443 端口(443 比较常用,并非 443 不可),然后将流量转发到 V2Ray 的 WebSocket 所监听的内网端口(本例是 10000),V2Ray 服务器端不需要配置 TLS。

  • V2ray Settings
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
{
"inbounds": [
{
"port": 10000,
"listen":"127.0.0.1",//只监听 127.0.0.1,避免除本机外的机器探测到开放了 10000 端口
"protocol": "vmess",
"settings": {
"clients": [
{
"id": "b831381d-6324-4d53-ad4f-8cda48b30811",
"alterId": 64
}
]
},
"streamSettings": {
"network": "ws",
"wsSettings": {
"path": "/ray" // 路径
}
}
}
],
"outbounds": [
{
"protocol": "freedom",
"settings": {}
}
]
}
  • TLS

证书生成见上文

  • Nginx Setting
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
server {
listen 443 ssl;
listen [::]:443 ssl;

ssl_certificate /etc/v2ray/v2ray.crt;
ssl_certificate_key /etc/v2ray/v2ray.key;
ssl_session_timeout 1d;
ssl_session_cache shared:MozSSL:10m;
ssl_session_tickets off;

ssl_protocols TLSv1.2 TLSv1.3;
ssl_ciphers ECDHE-ECDSA-AES128-GCM-SHA256:ECDHE-RSA-AES128-GCM-SHA256:ECDHE-ECDSA-AES256-GCM-SHA384:ECDHE-RSA-AES256-GCM-SHA384:ECDHE-ECDSA-CHACHA20-POLY1305:ECDHE-RSA-CHACHA20-POLY1305:DHE-RSA-AES128-GCM-SHA256:DHE-RSA-AES256-GCM-SHA384;
ssl_prefer_server_ciphers off;

server_name tunnel.edlison.xyz;
location /ray { # 与 V2Ray 配置中的 path 保持一致
if ($http_upgrade != "websocket") { # WebSocket协商失败时返回404
return 404;
}
proxy_redirect off;
proxy_pass http://127.0.0.1:10000; # 假设WebSocket监听在环回地址的10000端口上
proxy_http_version 1.1;
proxy_set_header Upgrade $http_upgrade;
proxy_set_header Connection "upgrade";
proxy_set_header Host $host;
# Show real IP in v2ray access.log
proxy_set_header X-Real-IP $remote_addr;
proxy_set_header X-Forwarded-For $proxy_add_x_forwarded_for;
}
}
  • Client Setting
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
{
"inbounds": [
{
"port": 1080,
"listen": "127.0.0.1",
"protocol": "socks",
"sniffing": {
"enabled": true,
"destOverride": ["http", "tls"]
},
"settings": {
"auth": "noauth",
"udp": false
}
}
],
"outbounds": [
{
"protocol": "vmess",
"settings": {
"vnext": [
{
"address": "mydomain.me",
"port": 443,
"users": [
{
"id": "b831381d-6324-4d53-ad4f-8cda48b30811",
"alterId": 64
}
]
}
]
},
"streamSettings": {
"network": "ws",
"security": "tls",
"wsSettings": {
"path": "/ray"
}
}
}
]
}
  • 注意事项

注意事项
V2Ray 自 4.18.1 后支持 TLS1.3,如果开启并强制 TLS1.3 请注意 v2ray 客户端版本.
较低版本的 nginx 的 location 需要写为 /ray/ 才能正常工作
如果在设置完成之后不能成功使用,可能是由于 SElinux 机制(如果你是 CentOS 7 的用户请特别留意 SElinux 这一机制)阻止了 Nginx 转发向内网的数据。如果是这样的话,在 V2Ray 的日志里不会有访问信息,在 Nginx 的日志里会出现大量的 “Permission Denied” 字段,要解决这一问题需要在终端下键入以下命令:
setsebool -P httpd_can_network_connect 1
请保持服务器和客户端的 wsSettings 严格一致,对于 V2Ray,/ray 和 /ray/ 是不一样的
较低版本的系统/浏览器可能无法完成握手. 如 Chrome 49/XP SP3, Safari 8/iOS 8.4, Safari 8/OS X 10.10 及更低的版本. 如果你的设备比较旧, 则可以通过在配置中添加较旧的 TLS 协议以完成握手.

BBR

  • 一键安装脚本

$ wget --no-check-certificate https://github.com/teddysun/across/raw/master/bbr.sh && chmod +x bbr.sh && ./bbr.sh

  • 检测内核

$ uname -r

  • 检测安装情况

$ sysctl net.ipv4.tcp_available_congestion_control

Test

Just for test

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Example 1:

Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.
Example 2:

Input:
s = “aa”
p = “*”
Output: true
Explanation: ‘*’ matches any sequence.
Example 3:

Input:
s = “cb”
p = “?a”
Output: false
Explanation: ‘?’ matches ‘c’, but the second letter is ‘a’, which does not match ‘b’.
Example 4:

Input:
s = “adceb”
p = “ab”
Output: true
Explanation: The first ‘‘ matches the empty sequence, while the second ‘‘ matches the substring “dce”.
Example 5:

Input:
s = “acdcb”
p = “a*c?b”
Output: false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public boolean isMatch(String s, String p) {
int sLen = s.length(), pLen = p.length();
int sIdx = 0, pIdx = 0;
int starIdx = -1, sTmpIdx = -1;

while (sIdx < sLen) {

if (pIdx < pLen && (p.charAt(pIdx) == '?' || p.charAt(pIdx) == s.charAt(sIdx))){
++sIdx;
++pIdx;
}

else if (pIdx < pLen && p.charAt(pIdx) == '*') {

starIdx = pIdx;
sTmpIdx = sIdx;
++pIdx;
}

else if (starIdx == -1) {
return false;
}

else {

pIdx = starIdx + 1;
sIdx = sTmpIdx + 1;
sTmpIdx = sIdx;
}
}

for(int i = pIdx; i < pLen; i++)
if (p.charAt(i) != '*') return false;
return true;
}
}

Reference
https://leetcode-cn.com/problems/wildcard-matching/

TLS

从 v1.19 起引入了 TLS,TLS 中文译名是传输层安全,如果你没听说过,请 Google 了解一下。以下给出些我认为介绍较好的文章链接:

SSL/TLS 协议运行机制的概述

传输层安全协议

注册一个域名

如果已经注册有域名了可以跳过。 TLS 需要一个域名,域名有免费的和有付费的,如果你不舍得为一个域名每年花点钱,用个免费域名也可以,但总体来说付费的会优于免费的。为了方便,在本文中我就忽略如何注册购买域名了。关于如何获取域名,具体搜索相关文章教程。

注册好域名之后务必记得添加一个 A 记录指向你的 VPS!

以下假设注册的域名为 mydomain.me,请将之替换成自己的域名。

证书生成

TLS 是证书认证机制,所以使用 TLS 需要证书,证书也有免费付费的,同样的这里使用免费证书,证书认证机构为 Let’s Encrypt。 证书的生成有许多方法,这里使用的是比较简单的方法:使用 acme.sh 脚本生成,本部分说明部分内容参考于acme.sh README。

证书有两种,一种是 ECC 证书(内置公钥是 ECDSA 公钥),一种是 RSA 证书(内置 RSA 公钥)。简单来说,同等长度 ECC 比 RSA 更安全,也就是说在具有同样安全性的情况下,ECC 的密钥长度比 RSA 短得多(加密解密会更快)。但问题是 ECC 的兼容性会差一些,Android 4.x 以下和 Windows XP 不支持。只要您的设备不是非常老的老古董,建议使用 ECC 证书。

以下将给出这两类证书的生成方法,请大家根据自身的情况自行选择其中一种证书类型。

证书生成只需在服务器上操作。

安装 acme.sh

执行以下命令,acme.sh 会安装到 ~/.acme.sh 目录下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
$ curl  https://get.acme.sh | sh
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 671 100 671 0 0 680 0 --:--:-- --:--:-- --:--:-- 679
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
100 112k 100 112k 0 0 690k 0 --:--:-- --:--:-- --:--:-- 693k

[Fri 30 Dec 01:03:32 GMT 2016] Installing from online archive.
[Fri 30 Dec 01:03:32 GMT 2016] Downloading https://github.com/Neilpang/acme.sh/archive/master.tar.gz
[Fri 30 Dec 01:03:33 GMT 2016] Extracting master.tar.gz
[Fri 30 Dec 01:03:33 GMT 2016] Installing to /home/user/.acme.sh
[Fri 30 Dec 01:03:33 GMT 2016] Installed to /home/user/.acme.sh/acme.sh
[Fri 30 Dec 01:03:33 GMT 2016] Installing alias to '/home/user/.profile'
[Fri 30 Dec 01:03:33 GMT 2016] OK, Close and reopen your terminal to start using acme.sh
[Fri 30 Dec 01:03:33 GMT 2016] Installing cron job
no crontab for user
no crontab for user
[Fri 30 Dec 01:03:33 GMT 2016] Good, bash is found, so change the shebang to use bash as preferred.
[Fri 30 Dec 01:03:33 GMT 2016] OK
[Fri 30 Dec 01:03:33 GMT 2016] Install success!

安装成功后执行 source ~/.bashrc 以确保脚本所设置的命令别名生效。

如果安装报错,那么可能是因为系统缺少 acme.sh 所需要的依赖项,acme.sh 的依赖项主要是 socat,我们通过以下命令来安装这些依赖项,然后重新安装一遍 acme.sh:

$ sudo apt-get install openssl cron socat curl

使用 acme.sh 生成证书

证书生成

执行以下命令生成证书:

以下的命令会临时监听 80 端口,请确保执行该命令前 80 端口没有使用

script
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


$ sudo ~/.acme.sh/acme.sh --issue -d mydomain.me --standalone -k ec-256
[Fri Dec 30 08:59:12 HKT 2016] Standalone mode.
[Fri Dec 30 08:59:12 HKT 2016] Single domain='mydomain.me'
[Fri Dec 30 08:59:12 HKT 2016] Getting domain auth token for each domain
[Fri Dec 30 08:59:12 HKT 2016] Getting webroot for domain='mydomain.me'
[Fri Dec 30 08:59:12 HKT 2016] _w='no'
[Fri Dec 30 08:59:12 HKT 2016] Getting new-authz for domain='mydomain.me'
[Fri Dec 30 08:59:14 HKT 2016] The new-authz request is ok.
[Fri Dec 30 08:59:14 HKT 2016] mydomain.me is already verified, skip.
[Fri Dec 30 08:59:14 HKT 2016] mydomain.me is already verified, skip http-01.
[Fri Dec 30 08:59:14 HKT 2016] mydomain.me is already verified, skip http-01.
[Fri Dec 30 08:59:14 HKT 2016] Verify finished, start to sign.
[Fri Dec 30 08:59:16 HKT 2016] Cert success.
-----BEGIN CERTIFICATE-----
MIIEMTCCAxmgAwIBAgISA1+gJF5zwUDjNX/6Xzz5fo3lMA0GCSqGSIb3DQEBCwUA
MEoxCzAJBgNVBAYTAlVTMRYwFAYDVQQKEw1MZXQncyBFbmNyeXB0MSMwIQYDVQQD
ExpMZXQncyBFbmNyeXB0IEF1dGhvcml0eSBYMzAeFw0xNjEyMjkyMzU5MDBaFw0x
NzAzMjkyMzU5MDBaMBcxFTATBgNVBAMTDHdlYWtzYW5kLmNvbTBZMBMGByqGSM49
****************************************************************
4p40tm0aMB837XQ9jeAXvXulhVH/7/wWZ8/vkUUvuHSCYHagENiq/3DYj4a85Iw9
+6u1r7atYHJ2VwqSamiyTGDQuhc5wdXIQxY/YQQqkAmn5tLsTZnnOavc4plANT40
zweiG8vcIvMVnnkM0TSz8G1yzv1nOkruN3ozQkLMu6YS7lk/ENBN7DBtYVSmJeU2
VAXE+zgRaP7JFOqK6DrOwhyE2LSgae83Wq/XgXxjfIo1Zmn2UmlE0sbdNKBasnf9
gPUI45eltrjcv8FCSTOUcT7PWCa3
-----END CERTIFICATE-----
[Fri Dec 30 08:59:16 HKT 2016] Your cert is in /root/.acme.sh/mydomain.me_ecc/mydomain.me.cer
[Fri Dec 30 08:59:16 HKT 2016] Your cert key is in /root/.acme.sh/mydomain.me_ecc/mydomain.me.key
[Fri Dec 30 08:59:16 HKT 2016] The intermediate CA cert is in /root/.acme.sh/mydomain.me_ecc/ca.cer
[Fri Dec 30 08:59:16 HKT 2016] And the full chain certs is there: /root/.acme.sh/mydomain.me_ecc/fullchain.cer

-k 表示密钥长度,后面的值可以是 ec-256ec-3842048307240968192,带有 ec 表示生成的是 ECC 证书,没有则是 RSA 证书。在安全性上 256 位的 ECC 证书等同于 3072 位的 RSA 证书。

#证书更新
由于 Let’s Encrypt 的证书有效期只有 3 个月,因此需要 90 天至少要更新一次证书,acme.sh 脚本会每 60 天自动更新证书。也可以手动更新。

手动更新 ECC 证书,执行:

$ sudo ~/.acme.sh/acme.sh --renew -d mydomain.com --force --ecc
如果是 RSA 证书则执行:

$ sudo ~/.acme.sh/acme.sh --renew -d mydomain.com --force
由于本例中将证书生成到 /etc/v2ray/ 文件夹,更新证书之后还得把新证书生成到 /etc/v2ray。

#安装证书和密钥
#ECC 证书
将证书和密钥安装到 /etc/v2ray 中:

$ sudo ~/.acme.sh/acme.sh --installcert -d mydomain.me --fullchainpath /etc/v2ray/v2ray.crt --keypath /etc/v2ray/v2ray.key --ecc
#RSA 证书
$ sudo ~/.acme.sh/acme.sh --installcert -d mydomain.me --fullchainpath /etc/v2ray/v2ray.crt --keypath /etc/v2ray/v2ray.key
注意:无论什么情况,密钥(即上面的 v2ray.key)都不能泄漏,如果你不幸泄漏了密钥,可以使用 acme.sh 将原证书吊销,再生成新的证书,吊销方法请自行参考 acme.sh 的手册

#配置 V2Ray
#服务器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
{
"inbounds": [
{
"port": 443, // 建议使用 443 端口
"protocol": "vmess",
"settings": {
"clients": [
{
"id": "23ad6b10-8d1a-40f7-8ad0-e3e35cd38297",
"alterId": 64
}
]
},
"streamSettings": {
"network": "tcp",
"security": "tls", // security 要设置为 tls 才会启用 TLS
"tlsSettings": {
"certificates": [
{
"certificateFile": "/etc/v2ray/v2ray.crt", // 证书文件
"keyFile": "/etc/v2ray/v2ray.key" // 密钥文件
}
]
}
}
}
],
"outbounds": [
{
"protocol": "freedom",
"settings": {}
}
]
}

#客户端

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
{
"inbounds": [
{
"port": 1080,
"protocol": "socks",
"sniffing": {
"enabled": true,
"destOverride": ["http", "tls"]
},
"settings": {
"auth": "noauth"
}
}
],
"outbounds": [
{
"protocol": "vmess",
"settings": {
"vnext": [
{
"address": "mydomain.me", // tls 需要域名,所以这里应该填自己的域名
"port": 443,
"users": [
{
"id": "23ad6b10-8d1a-40f7-8ad0-e3e35cd38297",
"alterId": 64
}
]
}
]
},
"streamSettings": {
"network": "tcp",
"security": "tls" // 客户端的 security 也要设置为 tls
}
}
]
}

#验证
一般来说,按照以上步骤操作完成,V2Ray 客户端能够正常联网说明 TLS 已经成功启用。但要是有个可靠的方法来验证是否正常开启 TLS 无疑更令人放心。 验证的方法有很多,我仅介绍一种小白化一点的,便是 Qualys SSL Labs’s SSL Server Test。

注意:使用 Qualys SSL Labs’s SSL Server Test 要求使用 443 端口,意味着你服务器配置的 inbound.port 应当是 443

打开 Qualys SSL Labs’s SSL Server Test,在 Hostname 中输入你的域名,点提交,过一会结果就出来了。

这是对于你的 TLS/SSL 的一个总体评分,我这里评分为 A,看来还不错。有这样的界面算是成功了。

这是关于证书的信息。从图中可以看出,我的这个证书有效期是从 2016 年 12 月 27 号到 2017 年的 3 月 27 号,密钥是 256 位的 ECC,证书签发机构是 Let’s Encrypt,重要的是最后一行,Trusted 为 Yes,表明我这个证书可信。

#温馨提醒
V2Ray 的 TLS 不是伪装或混淆,这是完整、真正的 TLS。因此才需要域名和证书。后文提到的 WS(WebSocket) 也不是伪装。

Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

If there exists a solution, it is guaranteed to be unique.
Both input arrays are non-empty and have the same length.
Each element in the input arrays is a non-negative integer.
Example 1:

Input:
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]

Output: 3

Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:

Input:
gas = [2,3,4]
cost = [3,4,3]

Output: -1

Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.

Unsolved

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;

int total_tank = 0;
int curr_tank = 0;
int starting_station = 0;
for (int i = 0; i < n; ++i) {
total_tank += gas[i] - cost[i];
curr_tank += gas[i] - cost[i];
// If one couldn't get here,
if (curr_tank < 0) {
// Pick up the next station as the starting one.
starting_station = i + 1;
// Start with an empty tank.
curr_tank = 0;
}
}
return total_tank >= 0 ? starting_station : -1;
}
}

Reference
https://leetcode-cn.com/problems/gas-station

Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

Example 1:

Input: [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:

Input: [3,2,1,0,4]
Output: false
Explanation: You will always arrive at index 3 no matter what. Its maximum
jump length is 0, which makes it impossible to reach the last index.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public boolean canJump(int[] nums) {
int[] tag = new int[nums.length];
tag[nums.length - 1] = 1;
for (int i = nums.length - 2; i >= 0; i--) {
for (int j = i + 1; j <= i + nums[i] && j < nums.length; j++) {
if (tag[j] == 1) {
tag[i] = 1;
break;
}
}
}

return tag[0] == 1;
}
}
/*
执行用时 :580 ms, 在所有 Java 提交中击败了11.08%的用户
内存消耗 :40.6 MB, 在所有 Java 提交中击败了31.49%的用户
*/

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean canJump(int[] nums) {
int res = nums.length - 1;

for (int i = nums.length - 1; i >= 0; i--) {
if (i + nums[i] >= res) {
res = i;
}
}

return res == 0;
}
}
/*
执行用时 :1 ms, 在所有 Java 提交中击败了99.95%的用户
内存消耗 :40.9 MB, 在所有 Java 提交中击败了24.65%的用户
*/

We can use the position of that we can reach the target to record current result.
So we just need to calculate whether current position plus current value >= last which can reach the target result, so we can tag current position.

Reference
https://leetcode-cn.com/problems/jump-game

Assign Cookies

Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie. Each child i has a greed factor gi, which is the minimum size of a cookie that the child will be content with; and each cookie j has a size sj. If sj >= gi, we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.

Note:
You may assume the greed factor is always positive.
You cannot assign more than one cookie to one child.

Example 1:
Input: [1,2,3], [1,1]

Output: 1

Explanation: You have 3 children and 2 cookies. The greed factors of 3 children are 1, 2, 3.
And even though you have 2 cookies, since their size is both 1, you could only make the child whose greed factor is 1 content.
You need to output 1.
Example 2:
Input: [1,2], [1,2,3]

Output: 2

Explanation: You have 2 children and 3 cookies. The greed factors of 2 children are 1, 2.
You have 3 cookies and their sizes are big enough to gratify all of the children,
You need to output 2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int res = 0;

for (int i = 0, j = 0; i < g.length; i++) {
while (j < s.length) {
if (s[j] >= g[i]) {
res++;
j++;
break;
} else {
j++;
}
}
}

return res;
}
}

First we need to sort the array.
Then we define 2 pointers to find satisfied results.

Reference
https://leetcode-cn.com/problems/assign-cookies

Is Subsequence

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ace” is a subsequence of “abcde” while “aec” is not).

Example 1:
s = “abc”, t = “ahbgdc”

Return true.

Example 2:
s = “axc”, t = “ahbgdc”

Return false.

Follow up:
If there are lots of incoming S, say S1, S2, … , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Overtime

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public boolean isSubsequence(String s, String t) {
if (s.length() == 0) return true;

for (int i = 0; i < t.length() - s.length(); i++) {
int res = 0;
int cur = i;
while (cur < t.length() && res < s.length()) {
if (t.charAt(cur) == s.charAt(res)) res++;

cur++;

if (res == s.length()) return true;
}
}

return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public boolean isSubsequence(String s, String t) {
int res = -1;
for (int i = 0; i < s.length(); i++) {
res = t.indexOf(s.charAt(i), res + 1);
if (res == -1) return false;
}
return true;
}
}
/*
执行用时 :1 ms, 在所有 Java 提交中击败了90.09%的用户
内存消耗 :44.2 MB, 在所有 Java 提交中击败了100.00%的用户
*/

Reference
https://leetcode-cn.com/problems/is-subsequence

Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

Example 1:

Input: [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:

Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:

Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int maxProfit(int[] prices) {
int[] dp = new int[2];

dp[1] = Integer.MIN_VALUE;

for (int price : prices) {
dp[0] = Math.max(dp[0], dp[1] + price);
dp[1] = Math.max(dp[1], dp[0] - price);
}

return dp[0];
}

/*
执行用时 :2 ms, 在所有 Java 提交中击败了26.28%的用户
内存消耗 :42.5 MB, 在所有 Java 提交中击败了5.04%的用户
*/
}

Reference
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/submissions

Recover Binary Search Tree

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Example 1:

Input: [1,3,null,null,2]

1
/
3

2

Output: [3,1,null,null,2]

3
/
1

2
Example 2:

Input: [3,1,4,null,null,2]

3
/
1 4
/
2

Output: [2,1,4,null,null,3]

2
/
1 4
/
3
Follow up:

A solution using O(n) space is pretty straight forward.
Could you devise a constant space solution?

Unsolved

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public void inorder(TreeNode root, List<Integer> nums) {
if (root == null) return;
inorder(root.left, nums);
nums.add(root.val);
inorder(root.right, nums);
}

public int[] findTwoSwapped(List<Integer> nums) {
int n = nums.size();
int x = -1, y = -1;
for(int i = 0; i < n - 1; ++i) {
if (nums.get(i + 1) < nums.get(i)) {
y = nums.get(i + 1);
// first swap occurence
if (x == -1) x = nums.get(i);
// second swap occurence
else break;
}
}
return new int[]{x, y};
}

public void recover(TreeNode r, int count, int x, int y) {
if (r != null) {
if (r.val == x || r.val == y) {
r.val = r.val == x ? y : x;
if (--count == 0) return;
}
recover(r.left, count, x, y);
recover(r.right, count, x, y);
}
}

public void recoverTree(TreeNode root) {
List<Integer> nums = new ArrayList();
inorder(root, nums);
int[] swapped = findTwoSwapped(nums);
recover(root, 2, swapped[0], swapped[1]);
}
}

Reference
https://leetcode-cn.com/problems/recover-binary-search-tree

不同的二叉搜索树 II

给定一个整数 n,生成所有由 1 … n 为节点所组成的二叉搜索树。

示例:

输入: 3
输出:
[
[1,null,3,2],
[3,2,null,1],
[3,1,null,null,2],
[2,1,3],
[1,null,2,null,3]
]
解释:
以上的输出对应以下 5 种不同结构的二叉搜索树:

1 3 3 2 1
\ / / / \
3 2 1 1 3 2
/ / \
2 1 2 3

Unsolved

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public List<TreeNode> generateTrees(int n) {

if (n == 0) return new ArrayList<>();
return helper(1, n);

}

private List<TreeNode> helper(int start, int end) {
List<TreeNode> res = new ArrayList<>();
if (start > end) {
res.add(null);
return res;
}
for (int val = start; val <= end; val++) {
List<TreeNode> left = helper(start, val - 1);
List<TreeNode> right = helper(val + 1, end);
for (TreeNode l : left) {
for (TreeNode r : right) {
TreeNode root = new TreeNode(val);
root.left = l;
root.right = r;
res.add(root);
}
}
}
return res;
}
}

Reference
https://leetcode-cn.com/problems/unique-binary-search-trees-ii

Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes’ values.

Example:

Input: [1,null,2,3]
1
\
2
/
3

Output: [1,3,2]
Follow up: Recursive solution is trivial, could you do it iteratively?

Old

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
vector<int> inorderTraversal(TreeNode* root) {
stack<TreeNode*> stack;
vector<int> vector;

while (root != nullptr || !stack.empty()) {
while (root != nullptr) {
stack.push(root);
root = root->left;
}
if (!stack.empty()) {
root = stack.top();
stack.pop();
vector.push_back(root->val);
root = root->right;
}
}

return vector;
}
}

Reference
https://leetcode-cn.com/problems/binary-tree-inorder-traversal

二叉树的最大深度

给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例:
给定二叉树 [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public int maxDepth(TreeNode root) {
Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
if (root != null) {
stack.add(new Pair(root, 1));
}

int depth = 0;
while (!stack.isEmpty()) {
Pair<TreeNode, Integer> current = stack.poll();
root = current.getKey();
int current_depth = current.getValue();
if (root != null) {
depth = Math.max(depth, current_depth);
stack.add(new Pair(root.left, current_depth + 1));
stack.add(new Pair(root.right, current_depth + 1));
}
}
return depth;
}
}

/*
by LeetCode
*/

Reference
https://leetcode-cn.com/problems/maximum-depth-of-binary-tree

Symmetric Tree

Given a binary tree, check whether it is a mirror of itself (ie, symmetric around its center).

For example, this binary tree [1,2,2,3,4,4,3] is symmetric:

1
/ \
2 2
/ \ / \
3 4 4 3

But the following [1,2,2,null,3,null,3] is not:

1
/ \
2 2
\ \
3 3

Note:
Bonus points if you could solve it both recursively and iteratively.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class Symmetric {
public static void main(String[] args) {

}

public boolean isSymmetric(TreeNode root) {

if (root == null) return true;

return checker(root.left, root.right);
}

public boolean checker(TreeNode left, TreeNode right) {
if (left == null && right != null || left != null && right == null) return false;
if (left == null && right == null) return true;

if (left.val != right.val) return false;

return checker(left.left, right.right) && checker(left.right, right.left);
}
}

/*
执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :37.4 MB, 在所有 Java 提交中击败了41.58%的用户
*/

The base case is that if (root == null).
First divide the problem into smallest piece that we judge the node’s value equals or not.
Then we conquer the problem that the node left.left equals right.right and left.right equals right.left.

Reference
https://leetcode-cn.com/problems/symmetric-tree/submissions

Same Tree

Given two binary trees, write a function to check if they are the same or not.

Two binary trees are considered the same if they are structurally identical and the nodes have the same value.

Example 1:

Input: 1 1
/ \ /
2 3 2 3

[1,2,3],   [1,2,3]

Output: true

Example 2:

Input: 1 1
/
2 2

[1,2],     [1,null,2]

Output: false

Example 3:

Input: 1 1
/ \ /
2 1 1 2

[1,2,1],   [1,1,2]

Output: false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) {
return true;
}

if (p == null || q == null) {
return false;
}

if (p.val != q.val) { // !!!
return false;
}

return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}

Reference
https://leetcode-cn.com/problems/same-tree

Regular Expression Matching

Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’.

‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or .
*
Example 1:**

Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.

Example 2:

Input:
s = “aa”
p = “a*”
Output: true
Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

Example 3:

Input:
s = “ab”
p = “.*”
Output: true
Explanation: “.*” means “zero or more (*) of any character (.)”.

Example 4:

Input:
s = “aab”
p = “cab”
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches “aab”.

Example 5:

Input:
s = “mississippi”
p = “misis*p.”
Output: false

Unsolved

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public boolean isMatch(String text, String pattern) {
if (pattern.isEmpty()) return text.isEmpty();
boolean first_match = (!text.isEmpty() &&
(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));

if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
return (isMatch(text, pattern.substring(2)) ||
(first_match && isMatch(text.substring(1), pattern)));
} else {
return first_match && isMatch(text.substring(1), pattern.substring(1));
}
}
}

/*
https://leetcode-cn.com/problems/regular-expression-matching/solution/zheng-ze-biao-da-shi-pi-pei-by-leetcode/
*/

Reference
https://leetcode-cn.com/problems/regular-expression-matching

[Linux]创建用户

linux下创建用户(一)

Linux 系统是一个多用户多任务的分时操作系统,任何一个要使用系统资源的用户,都必须首先向系统管理员申请一个账号,然后以这个账号的身份进入系统。用户的账号一方面可以帮助系统管理员对使用系统的用户进行跟踪,并控制他们对系统资源的访问;另一方面也可以帮助用户组织文件,并为用户提供安全性保护。每个用户账号都拥有一个惟一的用户名和各自的口令。用户在登录时键入正确的用户名和口令后,就能够进入系统和自己的主目录。

实现用户账号的管理,要完成的工作主要有如下几个方面:
· 用户账号的添加、删除与修改。
· 用户口令的管理。
· 用户组的管理。

一、Linux系统用户账号的管理

用户账号的管理工作主要涉及到用户账号的添加、修改和删除。
添加用户账号就是在系统中创建一个新账号,然后为新账号分配用户号、用户组、主目录和登录Shell等资源。
刚添加的账号是被锁定的,无法使用。

1、添加新的用户账号使用useradd命令,其语法如下:

代码:
useradd 选项 用户名
其中各选项含义如下:

代码:
-c comment 指定一段注释性描述。
-d 目录 指定用户主目录,如果此目录不存在,则同时使用-m选项,可以创建主目录。
-g 用户组 指定用户所属的用户组。
-G 用户组,用户组 指定用户所属的附加组。
-s Shell文件 指定用户的登录Shell。
-u 用户号 指定用户的用户号,如果同时有-o选项,则可以重复使用其他用户的标识号。

用户名 指定新账号的登录名。

例1:
代码:
# useradd –d /usr/sam -m sam
此命令创建了一个用户sam,
其中-d和-m选项用来为登录名sam产生一个主目录/usr/sam(/usr为默认的用户主目录所在的父目录)。

例2:
代码:
# useradd -s /bin/sh -g group –G adm,root gem
此命令新建了一个用户gem,该用户的登录Shell是/bin/sh,它属于group用户组,同时又属于adm和root用户组,其中group用户组是其主组。

这里可能新建组:#groupadd group及groupadd adm 
增加用户账号就是在/etc/passwd文件中为新用户增加一条记录,同时更新其他系统文件如/etc/shadow, /etc/group等。
Linux提供了集成的系统管理工具userconf,它可以用来对用户账号进行统一管理。

2、删除帐号

如果一个用户的账号不再使用,可以从系统中删除。删除用户账号就是要将/etc/passwd等系统文件中的该用户记录删除,必要时还删除用户的主目录。删除一个已有的用户账号使用userdel命令,其格式如下:

代码:
userdel 选项 用户名

常用的选项是-r,它的作用是把用户的主目录一起删除。
例如:

代码:
# userdel sam

此命令删除用户sam在系统文件中(主要是/etc/passwd, /etc/shadow, /etc/group等)的记录,同时删除用户的主目录。

3、修改帐号

修改用户账号就是根据实际情况更改用户的有关属性,如用户号、主目录、用户组、登录Shell等。
修改已有用户的信息使用usermod命令,其格式如下:

代码:
usermod 选项 用户名

常用的选项包括-c, -d, -m, -g, -G, -s, -u以及-o等,这些选项的意义与useradd命令中的选项一样,可以为用户指定新的资源值。另外,有些系统可以使用如下选项:

代码:
-l 新用户名

这个选项指定一个新的账号,即将原来的用户名改为新的用户名。
例如:
代码:
# usermod -s /bin/ksh -d /home/z –g developer sam
此命令将用户sam的登录Shell修改为ksh,主目录改为/home/z,用户组改为developer。

4、用户口令的管理

用户管理的一项重要内容是用户口令的管理。用户账号刚创建时没有口令,但是被系统锁定,无法使用,必须为其指定口令后才可以使用,即使是指定空口令。
指定和修改用户口令的Shell命令是passwd。超级用户可以为自己和其他用户指定口令,普通用户只能用它修改自己的口令。命令的格式为:
代码:

passwd 选项 用户名
可使用的选项:

代码:
-l 锁定口令,即禁用账号。
-u 口令解锁。
-d 使账号无口令。
-f 强迫用户下次登录时修改口令。
如果默认用户名,则修改当前用户的口令。

例如,假设当前用户是sam,则下面的命令修改该用户自己的口令:

代码:
$ passwd
Old password:**
New password:***
Re-enter new password:***

如果是超级用户,可以用下列形式指定任何用户的口令:

代码:
# passwd sam
New password:***
Re-enter new password:***

普通用户修改自己的口令时,passwd命令会先询问原口令,验证后再要求用户输入两遍新口令,如果两次输入的口令一致,则将这个口令指定给用户;而超级用户为用户指定口令时,就不需要知道原口令。

为了系统安全起见,用户应该选择比较复杂的口令,例如最好使用8位长的口令,口令中包含有大写、小写字母和数字,并且应该与姓名、生日等不相同。

为用户指定空口令时,执行下列形式的命令:

代码:
# passwd -d sam

此命令将用户sam的口令删除,这样用户sam下一次登录时,系统就不再询问口令。

passwd命令还可以用-l(lock)选项锁定某一用户,使其不能登录,例如:

代码:
# passwd -l sam

linux下创建用户(二)

二、Linux系统用户组的管理

每个用户都有一个用户组,系统可以对一个用户组中的所有用户进行集中管理。不同Linux 系统对用户组的规定有所不同,如Linux下的用户属于与它同名的用户组,这个用户组在创建用户时同时创建。
用户组的管理涉及用户组的添加、删除和修改。组的增加、删除和修改实际上就是对/etc/group文件的更新。

1、增加一个新的用户组使用groupadd命令。其格式如下:

代码:
groupadd 选项 用户组

可以使用的选项有:
代码:
-g GID 指定新用户组的组标识号(GID)。
-o 一般与-g选项同时使用,表示新用户组的GID可以与系统已有用户组的GID相同。

例1:

代码:
# groupadd group1

此命令向系统中增加了一个新组group1,新组的组标识号是在当前已有的最大组标识号的基础上加1。

例2:

代码:
# groupadd -g 101 group2

此命令向系统中增加了一个新组group2,同时指定新组的组标识号是101。

2、如果要删除一个已有的用户组,使用groupdel命令,其格式如下:

代码:
groupdel 用户组

例如:

代码:
# groupdel group1

此命令从系统中删除组group1。

3、修改用户组的属性使用groupmod命令。其语法如下:

代码:
groupmod 选项 用户组

常用的选项有:
代码:
-g GID 为用户组指定新的组标识号。
-o 与-g选项同时使用,用户组的新GID可以与系统已有用户组的GID相同。
-n新用户组 将用户组的名字改为新名字

例1:

代码:
# groupmod -g 102 group2

此命令将组group2的组标识号修改为102。

例2:

代码:
# groupmod –g 10000 -n group3 group2

此命令将组group2的标识号改为10000,组名修改为group3。

4、如果一个用户同时属于多个用户组,那么用户可以在用户组之间切换,以便具有其他用户组的权限。用户可以在登录后,使用命令newgrp切换到其他用户组,这个命令的参数就是目的用户组。例如:

代码:
$ newgrp root

这条命令将当前用户切换到root用户组,前提条件是root用户组确实是该用户的主组或附加组。类似于用户账号的管理,用户组的管理也可以通过集成的系统管理工具来完成。

让Linux系统中的普通用户也有超级用户的权限

Reference
https://www.cnblogs.com/ylan2009/articles/2321177.h

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.

Example 2:

Input: “cbbd”
Output: “bb”

img

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Solution {

public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}

boolean[][] dp = new boolean[len][len];

// 初始化
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}

int maxLen = 1;
int start = 0;

for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {

if (s.charAt(i) == s.charAt(j)) {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
} else {
dp[i][j] = false;
}

// 只要 dp[i][j] == true 成立,就表示子串 s[i, j] 是回文,此时记录回文长度和起始位置
if (dp[i][j]) {
int curLen = j - i + 1;
if (curLen > maxLen) {
maxLen = curLen;
start = i;
}
}
}
}
return s.substring(start, start + maxLen);
}
}

Reference
https://leetcode-cn.com/problems/longest-palindromic-substring

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: “abcabcbb”
Output: 3
Explanation: The answer is “abc”, with the length of 3.

Example 2:

Input: “bbbbb”
Output: 1
Explanation: The answer is “b”, with the length of 1.

Example 3:

Input: “pwwkew”
Output: 3
Explanation: The answer is “wke”, with the length of 3.
Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
private static int lengthOfLongestSubstring(String s) {
Set<Character> substring = new HashSet<>();
int res = 0;

if (s == null) {
return res;
}

for (int i = 0; i < s.length(); i++) {
int temp = 0;
int j = i;
while (j < s.length()) {
if (!substring.contains(s.charAt(j))) {
substring.add(s.charAt(j++));
temp++;
} else {
substring.clear();
break;
}
}
res = Math.max(temp, res);
}

return res;

/**
执行用时 :127 ms, 在所有 Java 提交中击败了10.50%的用户
内存消耗 :42.3 MB, 在所有 Java 提交中击败了5.02%的用户
*/
}

Using too much time, so I read the leetcode document.
Here is a SlideWindow method.

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
private static int plus(String s) {
int res = 0;
Set<Character> set = new HashSet<>();
int i = 0, j = i;

while (j < s.length()) {
if (!set.contains(s.charAt(j))) {
set.add(s.charAt(j++));
res = Math.max(res, set.size());
} else {
set.remove(s.charAt(i++));
}
}

return res;

/**
执行用时 :10 ms, 在所有 Java 提交中击败了64.95%的用户
内存消耗 :41.6 MB, 在所有 Java 提交中击败了5.02%的用户
*/

We can adjust the SlideWindow by increase i - head pointer and j - rear pointer.
This can sharply optimize the complexity of time.

Reference
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

Valid Parentheses

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Note that an empty string is also considered valid.

Example 1:

Input: “()”
Output: true

Example 2:

Input: “()[]{}”
Output: true

Example 3:

Input: “(]”
Output: false

Example 4:

Input: “([)]”
Output: false

Example 5:

Input: “{[]}”
Output: true

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
public boolean isValid(String s) {
char[] charArray = s.toCharArray();
Stack<Integer> stack = new Stack<>();
if (s == null || s.length() == 0) {
return true;
}

for (int i = 0; i < charArray.length; i++) {
if (trans(charArray[i]) > 0) {
stack.push(trans(charArray[i]));
} else if (trans(charArray[i]) < 0 ) {
if (!stack.isEmpty() && stack.pop() + trans(charArray[i]) == 0) {
continue;
} else {
return false;
}
} else {
return false;
}
}

if (stack.size() == 0) {
return true;
} else {
return false;
}
}

private int trans(char c) {
switch (c) {
case '(': return 1;
case ')': return -1;
case '[': return 2;
case ']': return -2;
case '{': return 3;
case '}': return -3;
default: return 0;
}
}

/**
执行用时 :2 ms, 在所有 Java 提交中击败了91.77%的用户
内存消耗 :37.2 MB, 在所有 Java 提交中击败了5.05%的用户
*/
}

Source code is easy to see.

Reference
https://leetcode-cn.com/problems/valid-parentheses

Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

Example 1:

Input: [“flower”,”flow”,”flight”]
Output: “fl”

Example 2:

Input: [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Unsolved

1
2
3
4
5
6
Input:
["aa","a"]
Output:
"aa"
Answer:
"a"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public static String longestCommonPrefix(String[] strs) {
if (strs == null)
return "";

String res = strs[0];
char[] resChar = res.toCharArray();

for (int i = 0; i < strs.length; i++) {
char[] tempChar = strs[i].toCharArray();
for (int j = 0; j < tempChar.length & j < resChar.length; j++) {
if (resChar[j] != tempChar[j]) {
res = strs[i].substring(0, j);
resChar = res.toCharArray();
break;
}
}
}

return res;
}
}

LeetCode Solution

1
2
3
4
5
6
7
8
9
10
public String longestCommonPrefix(String[] strs) {
if (strs.length == 0) return "";
String prefix = strs[0];
for (int i = 1; i < strs.length; i++)
while (strs[i].indexOf(prefix) != 0) {
prefix = prefix.substring(0, prefix.length() - 1);
if (prefix.isEmpty()) return "";
}
return prefix;
}

Nice idea to use substring to find out what index is it. If strs doesn’t have a substring the index can not be 0. All we need to do is cut the prefix‘s length.

Reference
https://leetcode-cn.com/problems/longest-common-prefix

Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol Value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

I can be placed before V (5) and X (10) to make 4 and 9.
X can be placed before L (50) and C (100) to make 40 and 90.
C can be placed before D (500) and M (1000) to make 400 and 900.
Given a roman numeral, convert it to an integer. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: “III”
Output: 3

Example 2:

Input: “IV”
Output: 4

Example 3:

Input: “IX”
Output: 9

Example 4:

Input: “LVIII”
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: “MCMXCIV”
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
public int romanToInt(String s) {
char[] array = s.toCharArray();
int sum = 0;

for (int i = 0; i < array.length - 1; i++) {
if (trans(array[i]) >= trans(array[i + 1])) {
sum += trans(array[i]);
} else {
sum -= trans(array[i]);
}
}

if (array.length - 1 >= 0) {
sum += trans(array[array.length - 1]);
}

return sum;
}

public int trans(char c) {

switch (c) {
case 'I':
return 1;

case 'V':
return 5;

case 'X':
return 10;

case 'L':
return 50;

case 'C':
return 100;

case 'D':
return 500;

case 'M':
return 1000;

default:
return 0;
}
}
}

We just need to get right number what each character meaning for. And judge the next character implies whether larger than the current character, then we can get it.

Reference
https://leetcode-cn.com/problems/roman-to-integer

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Example:

Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
List<Integer> nodes = new ArrayList<>();

for (int i = 0; i < lists.length; i++) {
while (lists[i] != null) {
nodes.add(lists[i].val);
lists[i] = lists[i].next;
}
}

if (nodes.size() == 0)
return null;

nodes.sort(Comparator.naturalOrder());
ListNode res = new ListNode(nodes.remove(0));
ListNode p = res;

for (int i = 0; i < nodes.size(); i++) {
p.next = new ListNode(nodes.get(i));
p = p.next;
}

return res;
}
}

Reference
https://leetcode-cn.com/problems/merge-k-sorted-lists

Static 理解

一. Static关键字的用途

在《Java编程思想》P86页有这样一段话:

  “static方法就是没有this的方法。在static方法内部不能调用非静态方法,反过来是可以的。而且可以在没有创建任何对象的前提下,仅仅通过类本身来调用static方法。这实际上正是static方法的主要用途。”

这段话虽然只是说明了static方法的特殊之处,但是可以看出static关键字的基本作用,简而言之,一句话来描述就是:

方便在没有创建对象的情况下来进行调用(方法/变量)。

很显然,被static关键字修饰的方法或者变量不需要依赖于对象来进行访问,只要类被加载了,就可以通过类名去进行访问。

static可以用来修饰类的成员方法、类的成员变量,另外可以编写static代码块来优化程序性能。

1. static方法

static方法一般称作静态方法,由于静态方法不依赖于任何对象就可以进行访问,因此对于静态方法来说,是没有this的,因为它不依附于任何对象,既然都没有对象,就谈不上this了。并且由于这个特性,在静态方法中不能访问类的非静态成员变量和非静态成员方法,因为非静态成员方法/变量都是必须依赖具体的对象才能够被调用。

但是要注意的是,虽然在静态方法中不能访问非静态成员方法和非静态成员变量,但是在非静态成员方法中是可以访问静态成员方法/变量的。举个简单的例子:

在上面的代码中,由于print2方法是独立于对象存在的,可以直接用过类名调用。假如说可以在静态方法中访问非静态方法/变量的话,那么如果在main方法中有下面一条语句:

MyObject.print2();

此时对象都没有,str2根本就不存在,所以就会产生矛盾了。同样对于方法也是一样,由于你无法预知在print1方法中是否访问了非静态成员变量,所以也禁止在静态成员方法中访问非静态成员方法。

而对于非静态成员方法,它访问静态成员方法/变量显然是毫无限制的。

因此,如果说想在不创建对象的情况下调用某个方法,就可以将这个方法设置为static。我们最常见的static方法就是main方法,至于为什么main方法必须是static的,现在就很清楚了。因为程序在执行main方法的时候没有创建任何对象,因此只有通过类名来访问。

另外记住,关于构造器是否是static方法可参考:http://blog.csdn.net/qq_17864929/article/details/48006835

2. static变量

static变量也称作静态变量,静态变量和非静态变量的区别是:静态变量被所有的对象所共享,在内存中只有一个副本,它当且仅当在类初次加载时会被初始化。而非静态变量是对象所拥有的,在创建对象的时候被初始化,存在多个副本,各个对象拥有的副本互不影响。

static成员变量的初始化顺序按照定义的顺序进行初始化。

3. static代码块

static关键字还有一个比较关键的作用就是 用来形成静态代码块以优化程序性能。static块可以置于类中的任何地方,类中可以有多个static块。在类初次被加载的时候,会按照static块的顺序来执行每个static块,并且只会执行一次。

为什么说static块可以用来优化程序性能,是因为它的特性:只会在类加载的时候执行一次。下面看个例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
class Person{
private Date birthDate;

public Person(Date birthDate) {
this.birthDate = birthDate;
}

boolean isBornBoomer() {
Date startDate = Date.valueOf("1946");
Date endDate = Date.valueOf("1964");
return birthDate.compareTo(startDate)>=0 && birthDate.compareTo(endDate) < 0;
}
}

isBornBoomer是用来这个人是否是1946-1964年出生的,而每次isBornBoomer被调用的时候,都会生成startDate和birthDate两个对象,造成了空间浪费,如果改成这样效率会更好:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Person{
private Date birthDate;
private static Date startDate,endDate;
static{
startDate = Date.valueOf("1946");
endDate = Date.valueOf("1964");
}

public Person(Date birthDate) {
this.birthDate = birthDate;
}

boolean isBornBoomer() {
return birthDate.compareTo(startDate)>=0 && birthDate.compareTo(endDate) < 0;
}
}

因此,很多时候会将一些只需要进行一次的初始化操作都放在static代码块中进行。

二. Static关键字的误区

1. static关键字会改变类中成员的访问权限吗?

有些初学的朋友会将java中的static与C/C++中的static关键字的功能混淆了。在这里只需要记住一点:与C/C++中的static不同,Java中的static关键字不会影响到变量或者方法的作用域。在Java中能够影响到访问权限的只有private、public、protected(包括包访问权限)这几个关键字。static关键字并不会改变变量和方法的访问权限。

2. 能通过this访问静态成员变量吗?

虽然对于静态方法来说没有this,那么在非静态方法中能够通过this访问静态成员变量吗?先看下面的一个例子,这段代码输出的结果是什么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Main {  
static int value = 33;

public static void main(String[] args) throws Exception{
new Main().printValue();
}

private void printValue(){
int value = 3;
System.out.println(this.value);
}
}
/**
33
*/

这里面主要考察队this和static的理解。this代表什么?this代表当前对象,那么通过new Main()来调用printValue的话,当前对象就是通过new Main()生成的对象。而static变量是被对象所享有的,因此在printValue中的this.value的值毫无疑问是33。在printValue方法内部的value是局部变量,根本不可能与this关联,所以输出结果是33。在这里永远要记住一点:静态成员变量虽然独立于对象,但是不代表不可以通过对象去访问,所有的静态方法和静态变量都可以通过对象访问(只要访问权限足够)。

3. static能作用于局部变量么?

在C/C++中static是可以作用域局部变量的,但是在Java中切记:static是不允许用来修饰局部变量。不要问为什么,这是Java语法的规定。

具体原因可以参考这篇博文的讨论:http://www.debugease.com/j2se/178932.html

三. 常见笔试面试题

1. 下面这段代码的输出结果是什么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Test extends Base{

static{
System.out.println("test static");
}

public Test(){
System.out.println("test constructor");
}

public static void main(String[] args) {
new Test();
}
}

class Base{

static{
System.out.println("base static");
}

public Base(){
System.out.println("base constructor");
}
}

/**
base static
test static
base constructor
test constructor
*/

至于为什么是这个结果,我们先不讨论,先来想一下这段代码具体的执行过程,在执行开始,先要寻找到main方法,因为main方法是程序的入口,但是在执行main方法之前,必须先加载Test类,而在加载Test类的时候发现Test类继承自Base类,因此会转去先加载Base类,在加载Base类的时候,发现有static块,便执行了static块。在Base类加载完成之后,便继续加载Test类,然后发现Test类中也有static块,便执行static块。在加载完所需的类之后,便开始执行main方法。在main方法中执行new Test()的时候会先调用父类的构造器,然后再调用自身的构造器。因此,便出现了上面的输出结果。

2. 这段代码的输出结果是什么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public class Test {
Person person = new Person("Test");
static{
System.out.println("test static");
}

public Test() {
System.out.println("test constructor");
}

public static void main(String[] args) {
new MyClass();
}
}

class Person{
static{
System.out.println("person static");
}
public Person(String str) {
System.out.println("person "+str);
}
}


class MyClass extends Test {
Person person = new Person("MyClass");
static{
System.out.println("myclass static");
}

public MyClass() {
System.out.println("myclass constructor");
}
}

/**
test static
myclass static
person static
person Test
test constructor
person MyClass
myclass constructor
*/

类似地,我们还是来想一下这段代码的具体执行过程。首先加载Test类,因此会执行Test类中的static块。接着执行new MyClass(),而MyClass类还没有被加载,因此需要加载MyClass类。在加载MyClass类的时候,发现MyClass类继承自Test类,但是由于Test类已经被加载了,所以只需要加载MyClass类,那么就会执行MyClass类的中的static块。在加载完之后,就通过构造器来生成对象。而在生成对象的时候,必须先初始化父类的成员变量,因此会执行Test中的Person person = new Person(),而Person类还没有被加载过,因此会先加载Person类并执行Person类中的static块,接着执行父类的构造器,完成了父类的初始化,然后就来初始化自身了,因此会接着执行MyClass中的Person person = new Person(),最后执行MyClass的构造器。

3. 这段代码的输出结果是什么?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Test {

static{
System.out.println("test static 1");
}
public static void main(String[] args) {

}

static{
System.out.println("test static 2");
}
}

/**
test static 1
test static 2
*/

虽然在main方法中没有任何语句,但是还是会输出,原因上面已经讲述过了。另外,static块可以出现类中的任何地方 只要不是方法内部,记住,任何方法内部都不行 ,并且执行是按照static块的顺序执行的。

java 内部类和静态内部类的区别

下面说一说内部类(Inner Class)和静态内部类(Static Nested Class)的区别:
定义在一个类内部的类叫内部类,包含内部类的类称为外部类。内部类可以声明public、protected、private等访问限制,可以声明 为abstract的供其他内部类或外部类继承与扩展,或者声明为static、final的,也可以实现特定的接口。外部类按常规的类访问方式使用内部 类,唯一的差别是外部类可以访问内部类的所有方法与属性,包括私有方法与属性。

一. 创建实例

OutClass.InnerClass obj = outClassInstance.new InnerClass(); //注意是外部类实例.new,内部类

AAA.StaticInner in = new AAA.StaticInner();//注意是外部类本身,静态内部类

二. 内部类中的this

内 部类中的this与其他类一样是指的本身。创建内部类对象时,它会与创造它的外围对象有了某种联系,于是能访问外围类的所有成员,不需任何特殊条件,可理 解为内部类链接到外部类。 用外部类创建内部类对象时,此内部类对象会秘密的捕获一个指向外部类的引用,于是,可以通过这个引用来访问外围类的成员。

三. 外部类访问内部类

内部类类似外部类的属性,因此访问内部类对象时总是需要一个创建好的外部类对象。内部类对象通过‘外部类名.this.xxx’的形式访问外部类的属性与方法。如:
System.out.println(“Print in inner Outer.index=” + pouter.this.index);
System.out.println(“Print in inner Inner.index=” + this.index);

四. 内部类向上转型

内部类也可以和普通类一样拥有向上转型的特性。将内部类向上转型为基类型,尤其是接口时,内部类就有了用武之地。如果内部类是private的,只可以被它的外部类问,从而完全隐藏实现的细节。

五. 方法内的类

方法内创建的类(注意方法中也能定义类),不能加访问修饰符。另外,方法内部的类也不是在调用方法时才会创建的,它们一样也被事先编译了。

六. 静态内部类

定义静态内部类:在定义内部类的时候,可以在其前面加上一个权限修饰符static。此时这个内部类就变为了静态内部类。

通常称为嵌套类,当内部类是static时,意味着:

[1]要创建嵌套类的对象,并不需要其外围类的对象;

[2]不能从嵌套类的对象中访问非静态的外围类对象(不能够从静态内部类的对象中访问外部类的非静态成员);

嵌 套类与普通的内部类还有一个区别:普通内部类的字段与方法,只能放在类的外部层次上,所以普通的内部类不能有static数据和static字段, 也不能包含嵌套类。但是在嵌套类里可以包含所有这些东西。也就是说,在非静态内部类中不可以声明静态成员,只有将某个内部类修饰为静态类,然后才能够在这 个类中定义静态的成员变量与成员方法。

另外,在创建静态内部类时不需要将静态内部类的实例绑定在外部类的实例上。普通非静态内部类的 对象是依附在外部类对象之中的,要在一个外部类中定义一个静态的内部类,不需要利用关键字new来创建内部类的实例。静态类和方法只属于类本身,并不属于 该类的对象,更不属于其他外部类的对象。

七. 内部类标识符

每个类会产生一个.class文件,文件名即为类名。同样,内部类也会产生这么一个.class文件,但是它的名称却不是内部类的类名,而是有着严格的限制:外围类的名字,加上$,再加上内部类名字。

八. 为何要用内部类?

  1. 内部类一般只为其外部类使用;

  2. 内部类提供了某种进入外部类的窗户;

  3. 也是最吸引人的原因,每个内部类都能独立地继承一个接口,而无论外部类是否已经继承了某个接口。因此,内部类使多重继承的解决方案变得更加完整。

加深印象,参考一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
package com.test.xml;
public class OutClassTest {
static int a;

int b;

public static void test() {
System.out.println("outer class static function");
}

public static void main(String[] args) {
OutClassTest oc = new OutClassTest();
// new一个外部类
OutClassTest oc1 = new OutClassTest();
// 通过外部类的对象new一个非静态的内部类
OutClassTest.InnerClass no_static_inner = oc1.new InnerClass();
// 调用非静态内部类的方法
System.out.println(no_static_inner.getKey());

// 调用静态内部类的静态变量
System.out.println(OutClassTest.InnerStaticClass.static_value);
// 不依赖于外部类实例,直接实例化内部静态类
OutClassTest.InnerStaticClass inner = new OutClassTest.InnerStaticClass();
// 调用静态内部类的非静态方法
System.out.println(inner.getValue());
// 调用内部静态类的静态方法
System.out.println(OutClassTest.InnerStaticClass.getMessage());
}

private class InnerClass {
// 只有在静态内部类中才能够声明或定义静态成员
// private static String tt = "0";
private int flag = 0;

public InnerClass() {
// 三.非静态内部类的非静态成员可以访问外部类的非静态变量和静态变量
System.out.println("InnerClass create a:" + a);
System.out.println("InnerClass create b:" + b);
System.out.println("InnerClass create flag:" + flag);
//
System.out.println("InnerClass call outer static function");
// 调用外部类的静态方法
test();
}

public String getKey() {
return "no-static-inner";
}
}

private static class InnerStaticClass {
// 静态内部类可以有静态成员,而非静态内部类则不能有静态成员。
private static String static_value = "0";

private int flag = 0;

public InnerStaticClass() {
System.out.println("InnerClass create a:" + a);
// 静态内部类不能够访问外部类的非静态成员
// System.out.println("InnerClass create b:" + b);
System.out.println("InnerStaticClass flag is " + flag);
System.out.println("InnerStaticClass tt is " + static_value);
}

public int getValue() {
// 静态内部类访问外部类的静态方法
test();
return 1;
}

public static String getMessage() {
return "static-inner";
}
}

public OutClassTest() {
// new一个非静态的内部类
InnerClass ic = new InnerClass();
System.out.println("OuterClass create");
}

}

总结:

  • 1.静态内部类可以有静态成员(方法,属性),而非静态内部类则不能有静态成员(方法,属性)。
  • 2.静态内部类只能够访问外部类的静态成员,而非静态内部类则可以访问外部类的所有成员(方法,属性)。
  • 3.实例化一个非静态的内部类的方法:
  • a.先生成一个外部类对象实例
  • OutClassTest oc1 = new OutClassTest();
  • b.通过外部类的对象实例生成内部类对象
  • OutClassTest.InnerClass no_static_inner = oc1.new InnerClass();
  • 4.实例化一个静态内部类的方法:
  • a.不依赖于外部类的实例,直接实例化内部类对象
  • OutClassTest.InnerStaticClass inner = new OutClassTest.InnerStaticClass();
  • b.调用内部静态类的方法或静态变量,通过类名直接调用
  • OutClassTest.InnerStaticClass.static_value
  • OutClassTest.InnerStaticClass.getMessage()

references:
http://hi.baidu.com/zhumulangma/item/bcd478c140427b2cef466532
http://duqiangcise.iteye.com/blog/697476

Final 理解

一.Final 修饰成员变量的注意事项

final修饰成员变量,该成员变量必须在创建对象之前进行赋值,否则编译失败
final修饰成员变量,固定的不是成员变量拥有的默认值,如果固定的是默认值,那么将导致被final修饰的成员变量的值永远无法修改,只能是默认值,这也不符合语法规则

成员变量的赋值有三种实现方式:

  • 定义成员变量的时候手动赋值
  • 利用构造器对成员变量进行赋值
  • 利用set函数进行赋值(也即利用一般的方法进行赋值)

注意
被final修饰的成员变量,只能拥有3中所描述的赋值方法的1,2。3为什么不行?

解释:如1所描述,被final修饰的成员变量必须在对象创建之前进行赋值,如果方法3可以,那么我们知道对象创建后,才能调用方法3,也就是说成员变量利用方法3进行赋值,会导致成员变量的赋值发生在对象创建之后

二. 为什么被Final修饰的成员变量必须在对象创建之前进行赋值?

理解:
被final关键字修饰的东西有一个特点,那就是一旦被修饰,那么它的值也就终生不变,可见final关键字起到了固定的作用,既然起到固定那么,你就要提前告诉final固定的是谁,如果允许被final修饰的成员变量赋值发生在对象创建之后,那么对象创建完成后final固定的值还是未可知的

三. final修饰成员变量和final修饰局部变量的区别与联系:

  1. 被final修饰的成员变量与局部变量均具有:一旦赋值,该值就终身不变
  2. 被final修饰的成员变量必须要在创建对象之前进行赋值,否则会编译失败,但是局部变量可以不赋值,但是没有被赋值的局部变量不能够被使用,一旦被使用就会编译失败
  3. 综上:一旦决定使用final关键字来修饰成员变量或者局部变量,一定要做到提前赋值

四.Final修饰成员方法:

  1. final修饰成员方法,该成员方法就不能被子类重写,但是仍然可以被子类继承并可以通过子类对象调用该方法

五.Final修饰类

1.final修饰类,该类便不能被其他类继承,但是该类仍然能够创建对象,并且,可以利用该对象调用该类的成员变量或者成员方法

六.Final使用范围:

Final关键字可以修饰类,类的成员变量,类的成员方法,成员方法的局部变量,等等,

但是final关键字不能用来修饰构造方法?
理解:
final修饰普通方法,将导致子类无法重写该方法,而构造方法本身就不能够被子类重写,故如果用final修饰,如同多此一举

Reference
https://blog.csdn.net/xichengfengyulou/article/details/81155290

Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Solution One

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode p = head;
ListNode temp = head;
int len = 1;

if (p == null)
return null;

while (p.next != null) {
len++;
p = p.next;
}

int loc = len - n;

if (loc == 0) {
return head.next;
}

for (int i = 1; i < loc; i++) {
temp = temp.next;
}

temp.next = temp.next.next;

return head;
}
}

Pass one time and get the length of LinkedList, so just count length - n - 1 times we can find the pre pointer. All we need to do is point pre pointer.next equal the next of which pointer we should delete.

Solution Two

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
List<ListNode> stack = new LinkedList<>();
ListNode temp = head;

while (temp != null) {
stack.add(temp);
temp = temp.next;
}

ListNode[] list = stack.toArray(new ListNode[stack.size()]);

if ((list.length - n - 1) < 0) return head.next;

list[list.length - n - 1].next = list[list.length - n].next;

return head;
}
}

Just let the List structure give a help, we can transfer a LinkedList to an Array. So all we need to do is let list[list.length - n - 1].next equals list[list.length - n].next.

Base case: if delete the head node we just need to return head.next.

Reference
https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list

两数相加

给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。

如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外,这两个数都不会以 0 开头。

示例:

输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

ListNode head = new ListNode(0);
ListNode p = head;
ListNode pre = p;
int temp;


while (l1.next != null && l2.next != null) {
temp = l1.val + l2.val;
if (p.val + temp < 10) {
p.val += temp;
p.next = new ListNode(0);
p = p.next; l1 = l1.next; l2 = l2.next;
} else {
p.val = (p.val + temp) % 10;
p.next = new ListNode(1);
p = p.next; l1 = l1.next; l2 = l2.next;
}
}

temp = l1.val + l2.val;
if (p.val + temp < 10) {
p.val += temp;
p.next = new ListNode(0);
pre = p;
p = p.next;
} else {
p.val = (p.val + temp) % 10;
p.next = new ListNode(1);
p = p.next;
}

while (l1.next != null) {
l1 = l1.next;
if (p.val + l1.val < 10) {
p.val += l1.val;
p.next = new ListNode(0);
pre = p;
p = p.next;
} else {
p.val = (p.val + l1.val) % 10;
p.next = new ListNode(1);
p = p.next;
}
}

while (l2.next != null) {
l2 = l2.next;
if (p.val + l2.val < 10) {
p.val += l2.val;
p.next = new ListNode(0);
pre = p;
p = p.next;
} else {
p.val = (p.val + l2.val) % 10;
p.next = new ListNode(1);
p = p.next;
}
}

if (p.val == 0) {
pre.next = null;
}

return head;
}
}

/**
执行用时 :3 ms, 在所有 Java 提交中击败了39.78%的用户
内存消耗 :41.1 MB, 在所有 Java 提交中击败了92.22%的用户
*/

Reference
https://leetcode-cn.com/problems/add-two-numbers

环形链表

给定一个链表,判断链表中是否有环。

为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。 如果 pos 是 -1,则在该链表中没有环。

示例 1:

输入:head = [3,2,0,-4], pos = 1
输出:true
解释:链表中有一个环,其尾部连接到第二个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> container = new HashSet<>();

while (head != null) {
if (container.contains(head)) {
return true;
}
container.add(head);
head = head.next;
}

return false;
}
}

img
Put each ListNode pointer into the Set container.
Because every pointer is unique, we just to judge if there’s a pointer’s address we scan has already contained in Set.

Reference
https://leetcode-cn.com/problems/linked-list-cycle

Implements & Extends 的不同

在类的声明中,通过关键字extends来创建一个类的子类;一个类通过关键字implements声明自己使用一个或者多个接口。

  • extends 是继承某个类, 继承之后可以使用父类的方法, 也可以重写父类的方法;

  • implements 是实现多个接口, 接口的方法一般为空的, 必须重写才能使用;

  • extends是继承父类,只要那个类不是声明为final或者那个类定义为abstract的就能继承;

  • Java中不支持多重继承,但是可以用接口来实现,这样就要用到implements,继承只能继承一个类,但implements可以实现多个接口,用逗号分开就行了 比如 :class A extends B implements C,D,E

接口实现的注意点:

  • 实现一个接口就是要实现该接口的所有的方法(抽象类除外);

  • 接口中的方法都是抽象的;

  • 多个无关的类可以实现同一个接口,一个类可以实现多个无关的接口。

Implements与Extends的不同

extends, 可以实现父类,也可以调用父类初始化 this.parent()。而且会覆盖父类定义的变量或者函数。这样的好处是:架构师定义好接口,让工程师实现就可以了。整个项目开发效率和开发成本大大降低。

implements,实现父类,子类不可以覆盖父类的方法或者变量。即使子类定义与父类相同的变量或者函数,也会被父类取代掉。

这两种实现的具体使用,是要看项目的实际情况,需要实现,不可以修改implements,只定义接口需要具体实现,或者可以被修改扩展性好,用extends。

Reference
https://blog.csdn.net/tolcf/article/details/46135645

删除排序链表中的重复元素

给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public ListNode deleteDuplicates(ListNode head) {
ListNode temp = head;

if (head == null) {
return null;
}

while (temp.next != null) {
if (temp.val == temp.next.val) {
temp.next = temp.next.next;
continue;
}
temp = temp.next;
}

return head;
}
}

/**
执行用时 :1 ms, 在所有 Java 提交中击败了94.59%的用户
内存消耗 :39.3 MB, 在所有 Java 提交中击败了5.00%的用户
*/

Base Case: head==null
Because this is a sorted linked list, we just need to figure out whether the next node’s values equals current node’s value.

Reference
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list

合并两个有序链表

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null | l2 == null) {
if (l1 == null & l2 == null) {
return null;
}
if (l1 != null) {
return l1;
}
if (l2 != null) {
return l2;
}
}
ListNode res = new ListNode(0);
ListNode temp = res;
while (l1 != null & l2 != null) {
if (l1.val <= l2.val) {
temp.val = l1.val;
temp.next = new ListNode(0);
temp = temp.next;
l1 = l1.next;
} else {
temp.val = l2.val;
temp.next = new ListNode(0);
temp = temp.next;
l2 = l2.next;
}
}

if (l1 != null) {
temp.val = l1.val;
while (l1.next != null) {
temp.next = new ListNode(l1.next.val);
temp = temp.next;
l1 = l1.next;
}
} else {
temp.val = l2.val;
while (l2.next != null) {
temp.next = new ListNode(l2.next.val);
temp = temp.next;
l2 = l2.next;
}
}

return res;

/*
执行用时 :1 ms, 在所有 Java 提交中击败了83.58%的用户
内存消耗 :38.5 MB, 在所有 Java 提交中击败了51.34%的用户
*/
}

The code is too complicated. I’m going on to simplify it.

Here is an updated code after I read the official document.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode res = new ListNode(0);// Head Pointer
ListNode temp = res;
while (l1 != null & l2 != null) {
if (l1.val <= l2.val) {
temp.next = l1;
l1 = l1.next;
} else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
temp.next = (l1 == null) ? l2 : l1;
return res.next;

/* 执行用时 :1 ms, 在所有 Java 提交中击败了83.58%的用户
内存消耗 :38.2 MB, 在所有 Java 提交中击败了55.50%的用户
*/
}

This is a nice solution to have a head pointer, which means we haven’t to modified current temp.val and register a new object on the temp.next. Also we needn’t to care whether l1 or l2 is null

Reference
https://leetcode-cn.com/problems/merge-two-sorted-lists

买卖股票的最佳时机

给定一个数组,它的第 i 个元素是一支给定的股票在第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。

注意: 你不能同时参与多笔交易(你必须在再次购买前出售掉之前的股票)。

示例 1:

输入: [3,3,5,0,0,3,1,4]
输出: 6
解释: 在第 4 天(股票价格 = 0)的时候买入,在第 6 天(股票价格 = 3)的时候卖出,这笔交易所能获得利润 = 3-0 = 3 。
随后,在第 7 天(股票价格 = 1)的时候买入,在第 8 天 (股票价格 = 4)的时候卖出,这笔交易所能获得利润 = 4-1 = 3 。

示例 2:

输入: [1,2,3,4,5]
输出: 4
解释: 在第 1 天(股票价格 = 1)的时候买入,在第 5 天 (股票价格 = 5)的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
注意你不能在第 1 天和第 2 天接连购买股票,之后再将它们卖出。
因为这样属于同时参与了多笔交易,你必须在再次购买前出售掉之前的股票。

示例 3:

输入: [7,6,4,3,1]
输出: 0
解释: 在这个情况下, 没有交易完成, 所以最大利润为 0。

动态规划
涉及到多个状态 首先画出状态图

Image
我们控制其中三个状态

  • 天数
  • 购买次数
  • 当前股票状态(0为未持有;1为持有)

以无限次购买股票为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    int n = prices.length;
int dp_0 = 0;
int dp_1 = Integer.MIN_VALUE;

for (int i = 0; i < n; i++) {
dp_0 = Math.max(dp_0, dp_1 + prices[i]);
dp_1 = Math.max(dp_1, dp_0 - prices[i]);
}

return dp_0;

/**
执行用时 :3 ms, 在所有 Java 提交中击败了10.65%的用户
内存消耗 :42.3 MB, 在所有 Java 提交中击败了5.01%的用户
本题可以不必使用DP以达到更快的速度
*/

该例中由于无限次购买可以省略购买次数
dp_0的含义为:当前未持有股票
其只能由dp_0保持不变或dp_1出售得来选取最大值

其中base case(最简单的情况)的赋值:

  • 一开始未持有的状态为0;
  • 一开始持有的状态不可能存在故赋值最小值

在该题中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    int n = prices.length;
int dp_2_0 = 0;
int dp_2_1 = Integer.MIN_VALUE;
int dp_1_0 = 0;
int dp_1_1 = Integer.MIN_VALUE;

for (int i = 0; i < n; i++) {
dp_1_1 = Math.max(dp_1_1, - prices[i]); // !!! - prices[i]
dp_1_0 = Math.max(dp_1_0, dp_1_1 + prices[i]);
dp_2_1 = Math.max(dp_2_1, dp_1_0 - prices[i]);
dp_2_0 = Math.max(dp_2_0, dp_2_1 + prices[i]);

}

return dp_2_0;

/**
执行用时 :3 ms, 在所有 Java 提交中击败了82.59%的用户
内存消耗 :41.9 MB, 在所有 Java 提交中击败了23.33%的用户
*/
`

由于是第二次售出

注意

  • 第一次直接持有的状态只能是购入股票故其只能从(dp_1_1, - prices[i])中选取最大值
  • 第二次持有因为状态转移只能从第一次未持有转移来故其从(dp_2_1, dp_1_0)中选取最大值

base case(最简单的情况)的赋值:

  • 第一次未持有的状态金额肯定为0;
  • 第一次持有的状态不存在故赋值MIN_VALUE
  • 第二次未持有的状态赋值0;
  • 第二次持有的状态因为不可能直接持有故赋值MIN_VALUE

Reference
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii

最接近的三数之和

给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数,使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

例如

给定数组 nums = [-1,2,1,-4], 和 target = 1.
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public int threeSumClosest(int[] nums, int target) {
int temp = nums[0] + nums[1] + nums[2];
int res = temp;
int min = Math.abs(temp - target);
int tempMin;
Arrays.sort(nums);

for (int i = 0; i < nums.length - 2; i++) {
int left = i + 1, right = nums.length - 1;

while (left < right) {
temp = nums[i] + nums[left] + nums[right];
tempMin = Math.abs(temp - target);

if (tempMin < min) {
min = tempMin;
res = temp;
}

if (temp < target) {
left++;
} else if (temp > target) {
right--;
} else {
return target;
}
}
}

return res;
}
}

/**
执行用时 :5 ms, 在所有 Java 提交中击败了95.39%的用户
*/

数组首先排序,循环n次,左右指针在i ~ nums.length - 1范围内移动,判定left<right.
min用来存储最小差值,当有三数之和与target小于该值便将其赋值给res.

Reference
https://leetcode-cn.com/problems/3sum-closest

三数之和(Unsolved)

给定一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例

给定数组 nums = [-1, 0, 1, 2, -1, -4],

满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length <= 2) {
return Collections.emptyList();
}
List<List<Integer>> result = new LinkedList<>();

Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
// 加速1:c为非负数,就不能满足a+b+c=0了
if (nums[i] > 0) {
return result;
}
// 加速2:跳过计算过的数据,同时防止结果重复
if (i != 0 && nums[i] == nums[i-1]) {
continue;
}
int head = i + 1;
int tail = nums.length - 1;
while (head < tail) {
int sum = -(nums[head] + nums[tail]);
if (sum == nums[i]) {
result.add(Arrays.asList(nums[i], nums[head], nums[tail]));
// 加速3:跳过计算过的数据,同时防止结果重复
while (head < tail && nums[head] == nums[head+1]) {
head++;
}
while (head < tail && nums[tail] == nums[tail-1]) {
tail--;
}
}
if (sum <= nums[i]) {
tail--;
} else {
head++;
}
}
}

return result;
}
}

Reference
https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-javajian-ji-ti-jie-by-wang-zi-hao-z/

面向切面编程

Summary

在软件业,AOP为Aspect Oriented Programming的缩写,意为:面向切面编程,通过预编译方式和运行期间动态代理实现程序功能的统一维护的一种技术。AOP是OOP的延续,是软件开发中的一个热点,也是Spring框架中的一个重要内容,是函数式编程的一种衍生范型。利用AOP可以对业务逻辑的各个部分进行隔离,从而使得业务逻辑各部分之间的耦合度降低,提高程序的可重用性,同时提高了开发的效率。

Description

Aspect Oriented Programming(AOP)是较为热门的一个话题。AOP,国内大致译作“面向切面编程”。

“面向切面编程”,这样的名字并不是非常容易理解,且容易产生一些误导。有些人认为“OOP/OOD11即将落伍,AOP是新一代软件开发方式”。显然,发言者并没有理解AOP的含义。Aspect,的确是“方面”的意思。不过,汉语传统语义中的“方面”,大多数情况下指的是一件事情的不同维度、或者说不同角度上的特性,比如我们常说:“这件事情要从几个方面来看待”,往往意思是:需要从不同的角度来看待同一个事物。这里的“方面”,指的是事物的外在特性在不同观察角度下的体现。而在AOP中,Aspect的含义,可能更多的理解为“切面”比较合适。

可以通过预编译方式和运行期动态代理实现在不修改源代码的情况下给程序动态统一添加功能的一种技术。AOP实际是GoF设计模式的延续,设计模式孜孜不倦追求的是调用者和被调用者之间的解耦,提高代码的灵活性和可扩展性,AOP可以说也是这种目标的一种实现。

在Spring中提供了面向切面编程的丰富支持,允许通过分离应用的业务逻辑与系统级服务(例如审计(auditing)和事务(transaction)管理)进行内聚性的开发。应用对象只实现它们应该做的——完成业务逻辑——仅此而已。它们并不负责(甚至是意识)其它的系统级关注点,例如日志或事务支持。

主要功能

日志记录,性能统计,安全控制,事务处理,异常处理等等。

主要意图

将日志记录,性能统计,安全控制,事务处理,异常处理等代码从业务逻辑代码中划分出来,通过对这些行为的分离,我们希望可以将它们独立到非指导业务逻辑的方法中,进而改变这些行为的时候不影响业务逻辑的代码。

控制反转

Summary

控制反转(Inversion of Control,缩写为IoC),是面向对象编程中的一种设计原则,可以用来减低计算机代码之间的耦合度。其中最常见的方式叫做依赖注入(Dependency Injection,简称DI),还有一种方式叫“依赖查找”(Dependency Lookup)。通过控制反转,对象在被创建的时候,由一个调控系统内所有对象的外界实体将其所依赖的对象的引用传递给它。也可以说,依赖被注入到对象中。

Description

Class A中用到了Class B的对象b,一般情况下,需要在A的代码中显式的new一个B的对象。

采用依赖注入技术之后,A的代码只需要定义一个私有的B对象,不需要直接new来获得这个对象,而是通过相关的容器控制程序来将B对象在外部new出来并注入到A类里的引用中。而具体获取的方法、对象被获取时的状态由配置文件(如XML)来指定。

设计模式

IoC可以认为是一种全新的设计模式,但是理论和时间成熟相对较晚,并没有包含在GoF中。
Interface Driven Design接口驱动,接口驱动有很多好处,可以提供不同灵活的子类实现,增加代码稳定和健壮性等等,但是接口一定是需要实现的,也就是如下语句迟早要执行:AInterface a = new AInterfaceImp(); 这样一来,耦合关系就产生了,如:

1
2
3
4
5
6
7
8
9
10
11
classA
{
AInterface a;

A(){}

AMethod()//一个方法
{
a = new AInterfaceImp();
}
}

Class A与AInterfaceImp就是依赖关系,如果想使用AInterface的另外一个实现就需要更改代码了。当然我们可以建立一个Factory来根据条件生成想要的AInterface的具体实现,即:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
InterfaceImplFactory
{
AInterface create(Object condition)
{
if(condition == condA)
{
return new AInterfaceImpA();
}
else if(condition == condB)
{
return new AInterfaceImpB();
}
else
{
return new AInterfaceImp();
}
}
}

表面上是在一定程度上缓解了以上问题,但实质上这种代码耦合并没有改变。通过IoC模式可以彻底解决这种耦合,它把耦合从代码中移出去,放到统一的XML 文件中,通过一个容器在需要的时候把这个依赖关系形成,即把需要的接口实现注入到需要它的类中,这可能就是“依赖注入”说法的来源了。

IoC模式,系统中通过引入实现了IoC模式的IoC容器,即可由IoC容器来管理对象的生命周期、依赖关系等,从而使得应用程序的配置和依赖性规范与实际的应用程序代码分离。其中一个特点就是通过文本的配置文件进行应用程序组件间相互关系的配置,而不用重新修改并编译具体的代码。

当前比较知名的IoC容器有:Pico Container、Avalon 、Spring、JBoss、HiveMind、EJB等。

在上面的几个IoC容器中,轻量级的有Pico Container、Avalon、Spring、HiveMind等,超重量级的有EJB,而半轻半重的有容器有JBoss,Jdon等。

可以把IoC模式看作工厂模式的升华,把IoC容器看作是一个大工厂,只不过这个大工厂里要生成的对象都是在XML文件中给出定义的。利用Java 的“反射”编程,根据XML中给出的类定义生成相应的对象。从实现来看,以前在工厂模式里写死了的对象,IoC模式改为配置XML文件,这就把工厂和要生成的对象两者隔离,极大提高了灵活性和可维护性。

IoC中最基本的Java技术就是“反射”编程。通俗的说,反射就是根据给出的类名(字符串)来生成对象。这种编程方式可以让应用在运行时才动态决定生成哪一种对象。反射的应用是很广泛的,像Hibernate、Spring中都是用“反射”做为最基本的技术手段。

在过去,反射编程方式相对于正常的对象生成方式要慢10几倍,这也许也是当时为什么反射技术没有普遍应用开来的原因。但经SUN改良优化后,反射方式生成对象和通常对象生成方式,速度已经相差不大了(但依然有一倍以上的差距)。

设计模式

Summary

设计模式是面向对象设计中反复出现的问题的解决方案。这个术语在1990年代由Erich Gamma等人从建筑设计领域引入到计算机科学中来。算法不是设计模式因为算法致力于解决问题而非设计问题。设计模式通常提供一种讨论软件设计的公共语言,使得熟练设计者的设计经验可以被初学者和其他设计者掌握。*设计模式还为软件重构提供了目标。

History

Erich Gamma与Richard Helm, Ralph Johnson ,John Vlissides合作出版了Design Patterns - Elements of Reusable Object-Oriented Software 一书,在此书中共收录了23个设计模式。这四位作者在软件开发领域里也以他们的匿名著称Gang of Four(四人帮,简称GoF),并且是他们在此书中的协作导致了软件设计模式的突破。

Pattern Format

尽管名称和顺序在不同的资料中各有不同,描述模式的格式大致分为以下四个主要部分:
模式名称(Pattern Name):每一个模式都有自己的名字,模式的名字使得我们可以讨论我们的设计。
问题(Problem):在面向对象的系统设计过程中反复出现的特定场合,它导致我们采用某个模式。
解决方案(Solution):上述问题的解决方案,其内容给出了设计的各个组成部分,它们之间的关系、职责划分和协作方式。
效果(Consequence):采用该模式对软件系统其他部分的影响,比如对系统的扩充性、可移植性的影响。影响也包括负面的影响。
别名(Also Known As):一个模式可以有超过一个以上的名称。这些名称应该要在这一节注明。
动机(Motivation):该模式应该利用在哪种情况下是本节提供的方案(包括问题与来龙去脉)的责任。
应用(Applicability)
结构(Structure):这部分常用类图与互动图阐述此模式。
参与者(Participants):这部分提供一份本模式用到的类与物件清单,与它们在设计下扮演的角色。
合作(Collaboration):描述在此模式下,类与物件间的互动。
结果(Consequences):这部分应描述使用本模式後的结果、副作用、与交换(trade-off)
实现(Implementaion):这部分应描述实现该模式、该模式的部分方案、实现该模式的可能技术、或者建议实现模式的方法。
例程(Sample Code):示范程式。
已知应用(Known Uses):业界已知的实做范例。
相关模式(Related Patterns):这部分包括其他相关模式,以及与其他类似模式的不同。

Mode

模式列表

  • 基础模式
  • 委托模式
  • 接口模式
  • 代理模式

创建模式

  • 抽象工厂模式(Abstract Factory) ,提供一个创建一系列相关或相互依赖对象的接口,而无需指定它们具体的类。
  • 生成器模式 (Builder),将一个复杂对象的构建与它的表示分离,使得同样的构建过程可以创建不同的表示。
  • 工厂方法模式(Factory Method) ,定义一个用于创建对象的接口,让子类决定将哪一个类实例化。Factory Method使一个类的实例化延迟到其子类。
  • 原型模式 (Prototype) ,用原型实例指定创建对象的种类,并且通过拷贝这个原型来创建新的对象。
  • 单例模式(Singleton),保证一个类仅有一个实例,并提供一个访问它的全局访问点。

结构模式

  • 适配器模式 (Adapter) ,将一个类的接口转换成客户希望的另外一个接口。Adapter模式使得原本由于接口不兼容而不能一起工作的那些类可以一起工作。
  • 桥接模式(Bridge) ,将抽象部分与它的实现部分分离,使它们都可以独立地变化。
  • 组合模式(Composite) ,将对象组合成树形结构以表示“部分-整体”的层次结构。它使得客户对单个对象和复合对象的使用具有一致性。
  • 容器模式
  • 修饰模式 (Decorator) ,动态地给一个对象添加一些额外的职责。就扩展功能而言, 它比生成子类方式更为灵活。
  • 扩展性模式
  • 外观模式
  • 享元模式
  • 管道与过滤器模式
  • 代理模式(Proxy) ,为其他对象提供一个代理以控制对这个对象的访问。

行为模式

  • 责任链模式 (Chain of Responsibility) ,为解除请求的发送者和接收者之间耦合,而使多个对象都有机会处理这个请求。将这些对象连成一条链,并沿着这条链传递该请求,直到有一个对象处理它。
  • 命令模式 (Command) ,将一个请求封装为一个对象,从而使你可用不同的请求对客户进行参数化;对请求排队或记录请求日志,以及支持可取消的操作。
  • 柯里化模式
  • 事件监听器模式
  • 解释器模式
  • 迭代器模式
  • 中介者模式
  • 备忘录模式 (Memento) ,在不破坏封装性的前提下,捕获一个对象的内部状态,并在该对象之外保存这个状态。这样以后就可将该对象恢复到保存的状态。
  • 观察者模式(Observer) ,定义对象间的一种一对多的依赖关系,以便当一个对象的状态发生改变时,所有依赖于它的对象都得到通知并自动刷新。
  • 状态模式 (State) ,允许一个对象在其内部状态改变时改变它的行为。对象看起来似乎修改了它所属的类。
  • 策略模式 (Strategy) ,定义一系列的算法,把它们一个个封装起来, 并且使它们可相互替换。本模式使得算法的变化可独立于使用它的客户。
    模板方法模式
  • 访问者模式 (Visitor),表示一个作用于某对象结构中的各元素的操作。它使你可以在不改变各元素的类的前提下定义作用于这些元素的新操作。
  • 层次访问者模式

并发模式

  • 模式 Action at a distance
  • 模式 Balking
  • 模式 Guarded suspension
  • 模式 Scheduler
  • 模式 Read write lock
  • 模式 Double checked locking
  • 模式 Disable job requests while running job

实时模式

  • 模式 Scheduled task
  • 模式 User interface
  • 模式 Disable job requests while running job

其他

  • 模型—视图—控制器模式

Day03 - 移除元素

给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1:

给定 nums = [3,2,2,3], val = 3,函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int removeElement(int[] nums, int val) {
int res = 0;

for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[res] = nums[i];
res++;
}
}

return res;
}
}

/**
执行用时 :0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗 :38.1 MB, 在所有 Java 提交中击败了5.05%的用户
*/

res记录新数组长度,遍历一遍数组满足条件则在相应位置赋值。

Reference
https://leetcode-cn.com/problems/remove-element

Day02 - 删除排序数组的重复项

给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。

不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例1

给定数组 nums = [1,1,2],函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。你不需要考虑数组中超出新长度后面的元素。`

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
public int removeDuplicates(int[] nums) {
int length;

if (nums.length == 0) {
return 0;
}

length = 1;

for (int i = 0, j = 1; i < nums.length; i++) {
while (j < nums.length && nums[j] == nums[i]) {
j++;
}

if (j >= nums.length)
break;

if (nums[j] != nums[i]) {
nums[i + 1] = nums[j];
length++;
}
}

return length;
}
}

/**
执行用时 :1 ms, 在所有 Java 提交中击败了99.89%的用户
*/

length 记录新数组长度,只需要在原数组中遍历一次与第 i 项比较若不同则将第 j 项赋给第 i+1 项。

Reference
https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

Day01 - 两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] two = new int[2];
for (int i = 0; i < nums.length; i++) {
for (int j = nums.length - 1; j > i; j--) {
if (nums[i] + nums[j] == target) {
two[0] = i;
two[1] = j;
return two;
}
}
}
return null;
}
}

Reference
https://leetcode-cn.com/problems/two-sum

Welcome to GitHub Pages

You can use the editor on GitHub to maintain and preview the content for your website in Markdown files.

Whenever you commit to this repository, GitHub Pages will run Jekyll to rebuild the pages in your site, from the content in your Markdown files.

Markdown

Markdown is a lightweight and easy-to-use syntax for styling your writing. It includes conventions for

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Syntax highlighted code block

# Header 1
## Header 2
### Header 3

- Bulleted
- List

1. Numbered
2. List

**Bold** and _Italic_ and `Code` text

[Link](url) and ![Image](src)

For more details see GitHub Flavored Markdown.

Jekyll Themes

Your Pages site will use the layout and styles from the Jekyll theme you have selected in your repository settings. The name of this theme is saved in the Jekyll _config.yml configuration file.

Support or Contact

Having trouble with Pages? Check out our documentation or contact support and we’ll help you sort it out.