Economics

通货膨胀

一般定义为:在信用货币制度下,流通中的货币数量超过经济实际需要而引起的货币贬值和物价水平全面而持续的上涨–用更通俗的语言来说就是:在一段给定的时间内,给定经济体中的物价水平普遍持续增长,从而造成货币购买力的持续下降。


通货紧缩

当市场上流通货币减少,人民的货币所得减少,购买力下降,影响物价至下跌,造成通货紧缩。长期的货币紧缩会抑制投资与生产,导致失业率升高及经济衰退。


Discrete Mathematics

七桥问题


欧拉图

通过图(无向图或有向图)中所有边且每边仅通过一次通路称为欧拉通路,相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图(Euler Graph),具有欧拉通路而无欧拉回路的图称为半欧拉图。

  1. 无向连通图G是欧拉图,当且仅当G不含奇数度结点(G的所有结点度数为偶数);
  2. 无向连通图G含有欧拉通路,当且仅当G有零个或两个奇数度的结点;
  3. 有向连通图D是欧拉图,当且仅当该图为连通图且D中每个结点的入度=出度
  4. 有向连通图D含有欧拉通路,当且仅当该图为连通图且D中除两个结点外,其余每个结点的入度=出度,且此两点满足deg-(u)-deg+(v)=±1。(起始点s的入度=出度-1,结束点t的出度=入度-1 或两个点的入度=出度)
  5. 一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环。
  6. 如果图G是欧拉图且 H = G - uv,则H有奇数个u,v-迹仅在最后访问v;同时,在这一序列的u,v-迹中,不是路径的迹的条数是偶数。

哈密顿图

通过图G的每个结点一次,且仅一次的通路(回路),就是哈密顿通路(回路). 存在哈密顿回路的图就是哈密顿图·

哈密顿图的充分条件和必要条件

  1. 在无向简单图G=中½V½³3,任意不同结点,则G是哈密顿图.(充分条件,定理4)
  2. 有向完全图D=;,若 ,则图D是哈密顿图. (充分条件,定理5推论)
  3. 设无向图G=,”V1ÌV,则P(G-V1)£½V1½(必要条件,定理3)

握手定理

设G=为任意无向图,V={v1,v2,…,vn},|E|=m,则所有顶点的度数和为2m


康托定理

  1. 闭区间上的连续实函数是一致连续的。
  2. 一个集合本身的势严格小于其幂集的势。
  3. 如果一个全序集是可列集,且是稠密的,无最大和最小值的,则它一定和有理数集序同构。

Reference :

  1. 欧拉图
  2. 哈密顿图
  3. 七桥问题
  4. 握手定理
  5. 康托定理

Chess

Chess

入门&常识

国际象棋有8*8共64个棋格,相邻的两个棋格总是黑白相间。为了方便,我们可以用A——H,和1——8这些字母和数字来标志每个格子。如下图。对局双方分为黑、白两方,各执16个棋子。这16个棋子分别是8个兵,2个车,2个马,2个象,1个王后,1个国王。只要将对方的国王吃掉就算胜利。

  1. 国王。国王可以直行、横行、斜行,但是每次只能动一个格。国王死掉,棋局结束。
  2. 王后。王后是国际象棋中最为厉害的棋子,她可以直行、横行、斜行,且行走的格数不受限制,只要前方没有其它棋子。
  3. 象。只能斜行。国际象棋中有两个象,一个位于黑格,一个位于白格,着也意味着,黑格中的象永远不会出现在白格的位置。
  4. 马。国际象棋中的马和中国象棋中的马的行走方法是一样的,都是走“日”字。但是国际象棋中的马没有“拌腿”一说。
  5. 车。国际象棋中的车与中国象棋中的车一样,都是可以直走、横走,且走的格数不受限制。另外,车还有一种特殊的走法,叫做“王车易位”。每局中,对局双方都有一次同时移动国王和车的机会。但是王车易位有诸多限制。
  6. 兵。如果兵是第一次行走,可以走一格或者两格,如果不是第一次行走,只能走一格,且只能直行,不能横行和斜行。另外,兵吃子儿的方法比较特殊,一般,兵只能吃斜前方的子儿,吃完后占据斜前方的位置,还有一种特殊的吃法,兵一次走两格,走完后在同一横线上有对方的兵时,可以将其吃掉,然后占据斜前方的位置。这叫做“吃过路兵”。如果己方的兵走到对方的底线时,这时候兵就可以升为除国王和兵以外的其它棋子,由于王后的威力最大,所以,兵经常升为王后。

Mathematics

数学三大危机:

  1. 希帕索斯(Hippasu,米太旁登地方人,公元前5世纪)发现了一个腰为1的等腰直角三角形的斜边(即根号2)永远无法用最简整数比(不可公度比)来表示,从而发现了第一个无理数,推翻了毕达哥拉斯的著名理论。相传当时毕达哥拉斯派的人正在海上,但就因为这一发现而把希帕索斯抛入大海;
  2. 微积分的合理性遭到严重质疑,险些要把整个微积分理论推翻;
  3. 罗素悖论:S由一切不是自身元素的集合所组成,那S包含S吗?用通俗一点的话来说,小明有一天说:“我正在撒谎!”问小明到底撒谎还是说实话。罗素悖论的可怕在于,它不像最大序数悖论或最大基数悖论那样涉及集合高深知识,它很简单,却可以轻松摧毁集合理论!

RedBlackTree

Red Black Tree

Red Black Tree由Rudolf Bayer发明的,当时被称为平衡二叉B树。后来,在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。

红黑树每个节点都带有颜色属性的二叉查找树,颜色为红色或黑色。二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了额外要求:

  1. 节点是红色或黑色
  2. 根节点是黑色
  3. 每个叶节点是黑色的
  4. 每个红色节点的两个子节点都是黑色
  5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点

这些约束确保了红黑树的关键特性:从根到叶子的最长的可能路径不多于最短的可能路径的两倍长`。

RedBlackTree

Reference :

  1. Wiki 红黑树
  2. Wiki 平衡树

Beam

Apache Beam的主要目标是统一批处理和流处理的编程范式,为无限,乱序,web-scale的数据集处理提供简单灵活,功能丰富以及表达能力十分强大的SDK。

Apache Beam项目重点在于数据处理的编程范式和接口定义,并不涉及具体执行引擎的实现,Apache Beam希望基于Beam开发的数据处理程序可以执行在任意的分布式计算引擎上。

Apache Beam基本架构

  1. 统一批处理和流处理的需求。
  2. 生成的分布式数据处理任务应该能够在各个分布式执行引擎上执行,用户可以自由切换分布式数据处理任务的执行引擎与执行环境。

Apache Beam主要由Beam SDKBeam Runner组成,Beam SDK定义了开发分布式数据处理任务业务逻辑的API接口,生成的的分布式数据处理任务Pipeline交给具体的Beam Runner执行引擎。

Beam Model

  1. 数据。分布式数据处理要处理的数据类型一般可以分为两类,有限的数据集和无限的数据流。
  2. 时间。Process Time是指数据进入分布式处理框架的时间,而Event-Time则是指数据产生的时间。
  3. 乱序。对于流处理框架处理的数据流来说,其数据的到达顺序可能并不严格按照Event-Time的时间顺序。对于基于Event Time定义的时间窗口来说,可能存在时间靠前的消息在时间靠后的消息后到达的情况。

Beam Model处理的目标数据是无限的时间乱序数据流,不考虑时间顺序或是有限的数据集可看做是无限乱序数据流的一个特例。

Beam Model从下面四个维度归纳了用户在进行数据处理的时候需要考虑的问题:

  1. What。如何对数据进行计算?
  2. Where。数据在什么范围中计算?
  3. When。何时将计算结果输出?
  4. How。迟到数据如何处理?

Beam SDK

Pipeline :

PCollection :

Transform :

Source and Sink :

A typical Beam driver program works as follows:

  1. Create a Pipeline object and set the pipeline execution options, including the Pipeline Runner.
  2. Create an initial PCollection for pipeline data, either using the Source API to read data from an external source, or using a Create transform to build a PCollection from in-memory data.
  3. Apply Transforms to each PCollection. Transforms can change, filter, group, analyze, or otherwise process the elements in a PCollection. A transform creates a new output PCollection without consuming the input collection. A typical pipeline applies subsequent transforms to the each new output PCollection in turn until processing is complete.
  4. Output the final, transformed PCollection(s), typically using the Sink API to write data to an external source.
  5. Run the pipeline using the designated Pipeline Runner.

Creating the Pipeline

Working with PCollections

Reference :

  1. Apache Beam: 下一代的大数据处理标准

###Jetty

Configure

Configuring the Server

Desc Value
ThreadPool
Handlers
Server Attributes
Server fields
Connectors
Services

##Netty

Netty

###架构总览
archietecture

Netty is a NIO client server framework which enables quick and easy development of network applications such as protocol servers and clients. It greatly simplifies and streamlines network programming such as TCP and UDP socket server. – Netty 官网

总体来说 Netty算是一个异步-事件驱动网络框架,具有很高的性能与扩展能力。

###重要组件介绍

  1. ServerBootstrap instance is then configured, as shown in the following listing, to set options, such as the port, the threading model/event loop, and the server handler to handle the business logic

  2. EventExecutor : a special EventExecutorGroup which comes with some handy methods to see if a Thread is executed in a event loop.

  3. EventExecutorGroup : responsible for providing the EventExecutor’s to use via its next() method.

2.Bootstrap

3.Channel

4.ChannelPipeline

可以理解为ChannelHandler的有序容器

5.ChannelBuffer

6.ChannelHandler

ChannelHandler分为ChannelInboundHandler与ChannelOutboundHandler两类

ChannelInboundHandler对从Client –> Server的消息进行处理

ChannelOutboundHandler对从Server –> CLient的消息进行处理

7.ChannelHandlerContext

###示例程序
以著名的Discard程序为例 说明Netty程序基本结构

首先是Server端结构

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
EventLoopGroup bossGroup = new NioEventLoopGroup(1);
EventLoopGroup workerGroup = new NioEventLoopGroup();

ServerBootstrap b = new ServerBootstrap();
b.group(bossGroup, workerGroup)
.channel(NioServerSocketChannel.class)
.handler(new LoggingHandler(LogLevel.INFO))
.childHandler(new ChannelInitializer<SocketChannel>() {
@Override
public void initChannel(SocketChannel ch) {
ChannelPipeline p = ch.pipeline();
if (sslCtx != null) {
p.addLast(sslCtx.newHandler(ch.alloc()));
}
p.addLast(new DiscardServerHandler());
}
});

// Bind and start to accept incoming connections.
ChannelFuture f = b.bind(PORT).sync();

// Wait until the server socket is closed.
// In this example, this does not happen, but you can do that to gracefully
// shut down your server.
f.channel().closeFuture().sync();

之后是Client端结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
EventLoopGroup group = new NioEventLoopGroup();
Bootstrap b = new Bootstrap();
b.group(group)
.channel(NioSocketChannel.class)
.handler(new ChannelInitializer<SocketChannel>() {
@Override
protected void initChannel(SocketChannel ch) throws Exception {
ChannelPipeline p = ch.pipeline();
if (sslCtx != null) {
p.addLast(sslCtx.newHandler(ch.alloc(), HOST, PORT));
}
p.addLast(new DiscardClientHandler());
}
});

AbstractBootstrap中
doBind(final SocketAddress localAddress)

init(Channel channel)

A Future is an abstraction, which represents a value that may become available at some point.

A Future object either holds the result of a computation or, in the case of a failed computation, an exception.

##Your first Netty application

A Netty application begins with one of the Bootstrap classes, a Bootstrap is a construct Netty provides that makes it easy for you to configure how Netty should setup or bootstrap the application.

In order to allow multiple protocols and various ways of processing data, Netty has what are called handlers.

The ChannelInboundHandler receives messages which you can process and decide what to do with it.

When a channel is registered, Netty binds that channel to a single EventLoop for the lifetime of that Channel. EventLoop is always bound to a single Thread that never changed during its life time.

EventLoopGroup contains one or more EventLoop

Netty allows the same EventLoopGroup to be used for processing IO and accepting
connections.

To understand what happens to data when it is written or read, it is first essential to have some understanding of what handlers are.

Handlers themselves depend upon the aforementioned ChannelPipeline to prescribe their order of execution.

A ChannelHandler may do some action on the data and then may pass it to the next
ChannelHandler in the ChannelPipeline. Another often action is do not do any action at all and just pass the specific event to the next ChannelHandler in the ChannelPipeline. This next ChannelHandler may handle it then or just forward it to the next ChannelHandler again.

Both ChannelInboundHandler and ChannelOutboundHandler can be mixed into the same ChannelPipeline.

###Encoding

When you send or receive a message with Netty it must be converted from one form to another.

If the message is being received it must be converted from bytes to a Java object (decoded by some kind of decoder).

If the message is being sent it must be converted from a
Java object to bytes (encoded by some type of encoder).

##Transports

Channel interface, which is used for all of the outbound operations. All I/O operations in Netty are asynchronous.

A channel provides a user:
Current state of the channel 
ChannelConfig configuration parameters of the channel
I/O operations that the channel supports
ChannelPipeline which handles all I/O events and requests

The ChannelPipeline holds all of the ChannelHandler instances that should be used for the inbound and outbound data that is passed through the channel.

ChannelHandler use for :

  1. Transforming data from one format to another.
  2. Notifying you of exceptions.
  3. Notifying you when a Channel becomes active or inactive.
  4. Notifying you once a channel is registered/deregistered from an EventLoop.
  5. Notifying you about user-specific events.

###IOI(Old blocking I/O )

The OIO transport is a compromise in Netty.

##Buffers

Different types of ByteBuf

  1. HEAP BUFFERS
  2. DIRECT BUFFERS
  3. COMPOSITE BUFFERS

##Transports
The heart of the transport API is the Channel interface, which is used for all of the outbound operations. A channel has a ChannelPipeline and a ChannelConfig
assigned to it.

The ChannelPipeline holds all of the ChannelHandler instances that should be used for the inbound and outbound data that is passed through the channel.

##ChannelHandler

your channel handler must extend the ChannelInboundHandlerAdapter class and override the messageReceived method. This method is called every time messages are received, which in this case are bytes.

channelActive Called after the connection to the server is established

channelRead0 Called after you receive data from the server

exceptionCaught Called if any exception was raised during processing

ChannelInboundHandler and ChannelOutboundHandler extends ChannelHandler

##ChannelPipeline

The ChannelPipeline holds all of the ChannelHandler instances that should be used for the inbound and outbound data that is passed through the channel.

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
                                              I/O Request
via {@link Channel} or
{@link ChannelHandlerContext}
|
+---------------------------------------------------+---------------+
| ChannelPipeline | |
| \|/ |
| +---------------------+ +-----------+----------+ |
| | Inbound Handler N | | Outbound Handler 1 | |
| +----------+----------+ +-----------+----------+ |
| /|\ | |
| | \|/ |
| +----------+----------+ +-----------+----------+ |
| | Inbound Handler N-1 | | Outbound Handler 2 | |
| +----------+----------+ +-----------+----------+ |
| /|\ . |
| . . |
| ChannelHandlerContext.fireIN_EVT() ChannelHandlerContext.OUT_EVT()|
| [ method call] [method call] |
| . . |
| . \|/ |
| +----------+----------+ +-----------+----------+ |
| | Inbound Handler 2 | | Outbound Handler M-1 | |
| +----------+----------+ +-----------+----------+ |
| /|\ | |
| | \|/ |
| +----------+----------+ +-----------+----------+ |
| | Inbound Handler 1 | | Outbound Handler M | |
| +----------+----------+ +-----------+----------+ |
| /|\ | |
+---------------+-----------------------------------+---------------+
| \|/
+---------------+-----------------------------------+---------------+
| | | |
| [ Socket.read() ] [ Socket.write() ] |
| |
| Netty Internal I/O Threads (Transport Implementation) |
+-------------------------------------------------------------------+

Included transports

NIO  Nonblocking I/O

OIO  Old blocking I/O

Local  In VM transport

Embedded transport

##Codec

##Bootstrap

A Netty application begins with one of the Bootstrap classes, is a construct Netty provides that makes it easy for you to configure how Netty should setup or bootstrap the application.

The ChannelInboundHandler receives messages which you can process and decide what to do with it. You may also write/flush data out from inside an ChannelInboundHandler when your application needs to provide a response.

ChannelInitializer is to add ChannelHandler implementations to whats called the ChannelPipeline.

All Netty applications are based on what is called a ChannelPipeline.

All IO operations in Netty are performed asynchronously.

ChannelFuture is a special java.util.concurrent.Future, which allos you to register ChannnelFutureListeners tot he ChannelFuture.

##Thread Model

ChannelHandlers contain your business logic, are guaranteed to be executed by a single thread at the same time for a specific Channel. This doesnt mean Netty fails to use multithreading, but it does limit each connection
to one thread as this design works well for nonblocking execution.

Theres no need for you to think about any of the issues you often have when working with multithreaded applications.


General API for compression codecs

Each compression codec is presented as its own class. It’s difficult to switch one compression codec to another without significant code modifications.

Modifications:
Added classes:

  • CompressionCodecFactory - factory for all compression codecs
  • CompressionDecoder - abstract class, parent for all compression decoders
  • CompressionEncoder - abstract class, parent for all compression encoders
  • CompressionFormat - enum with all available compression formats

Extend all compression encoders and decoders to use new abstract classes.

Result:General API for every compression codecs.


Reference :

  1. New and noteworthy in 4.0
  2. Netty4学习笔记

###Finagle

http://monkey.org/~marius/funsrv.pdf

  1. Futures The results of asynchronous operations are represented by futures which compose to express dependencies between operations.

  2. Services Systems boundaries are represented by asynchronous functions called services. They provide a symmetric and uniform API: the same abstraction represents both clients and servers.

  3. Filters Application-agnostic concerns are encapsulated by filters which compose to build services from multiple independent modules.