步骤1、在对Stack进行分析前，先看看它是怎么使用的。



步骤2、通过提取源码Stack里面的代码来实现自定义的栈MyStack。

import java.util.EmptyStackException;
import java.util.Vector;

/**
 * MyStack是一个后进先出（LIFO）栈，继承于Vector类；MyStack也是从
 * 源码Stack.java中提取代码生成
 * @param <E> 泛型
 */
public class MyStack<E> extends Vector<E>{
	private static final long serialVersionUID = 1L;
	 /**
     * 创建空栈
     */
    public MyStack() {
    }
    
    /**
     * 把item压入栈顶部。
     * @param   item 压入栈顶的元素.
     * @return  返回item.
     * @see     java.util.Vector#addElement
     */
    public E push(E item) {
        addElement(item);//Vector里面的方法，会将压入栈的元素item存放在数组末尾
        return item;
    }

    /**
     * 查看栈顶的数据，返回值为栈顶元素，Vector数组中最后一个元素，同时把栈中的该元素删除
     *
     * @return  返回值为栈顶元素，Vector数组中最后一个元素
     * @throws  EmptyStackException  当MyStack为空时抛出异常.
     */
    public synchronized E pop() {
        E       obj;
        int     len = size();
        obj = peek();//获取栈顶元素
        removeElementAt(len - 1);//Vector中的方法，根据给的下标删除元素
        return obj;
    }

    /**
     * 查看栈顶的数据，返回值为栈顶元素，Vector数组中最后一个元素，但是不会删除该元素
     * @return  返回值为栈顶元素，Vector数组中最后一个元素
     * @throws  EmptyStackException  当MyStack为空时抛出异常.
     */
    public synchronized E peek() {
        int     len = size();
        if (len == 0)
            throw new EmptyStackException();
        return elementAt(len - 1);//Vector中的方法，在Vector数组末尾添加一个元素
    }

    /**
     * 判断是否为空栈
     * @return  true 栈中没有元素时返回，false 栈中有元素
     */
    public boolean empty() {
        return size() == 0;
    }

    /**
     * 搜索o在栈中距离栈顶最近的相同元素的距离
     * @param   o   要搜索的元素.
     * @return  返回距离栈顶最近的相同元素的距离，以1为基准。如果栈中不存在这个元素，返回-1
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }
}


步骤 3、代码测试及运行结果：



从测试代码跟测试结果看，步骤3跟步骤1的不同之处就是在测试代码中创建栈的对象的类不一样，一个是Stack，一个是MyStack，其他完成相同。

在上一篇文章中，我们简介了怎么使用源码对TensorBoard进行编译教程，没有定制需求的可以直接使用pip进行安装。
TensorBoard中的graph是一种计算图，里面的点用于表示Tensor本身或者运算符，图中的边则代表Tensor的流动或者控制关系。
本文主要从代码的层面，分析graph的数据来源与结构。
一般来说，我们在启动TensorBoard的时候会使用--logdir参数配置文件路径(或者设置数据库位置)，这些日志文件为TensorBoard提供了数据。于是我们打开一个日志文件，查看里面的内容
我们看到，文件是通过二进制展示的，因此无法直接读取文件的内容。
回到浏览器中，进入graph网页，通过开发者工具发现，构造图的时候调用了一个接口
http://localhost:6006/data/plugin/graphs/graph?large_attrs_key=_too_large_attrs&limit_attr_size=1024&run=task1
用浏览器打开这个地址，看到以下内容
node {
name: "Input/X"
op: "Placeholder"
attr {
key: "_output_shapes"
value {
list {
shape {
unknown_rank: true
}
}
}
}
attr {
key: "dtype"
value {
type: DT_FLOAT
}
}
attr {
key: "shape"
value {
shape {
unknown_rank: true
}
}
}
}
...
每个node都能够与图中的一个节点相对应，因此我们可以确定，这个接口里返回的node，就是构成图所需要的数据结构。
那么，TensorBoard是怎么将日志文件转化为图的呢？
TesnorBoard中的每个模块都是以plugin存在的，我们进入tensorboard/plugin/graph/graphs_plungin.py，在这个文件中定义了graph相关的接口
def get_plugin_apps(self):
return {
'/graph': self.graph_route,
'/runs': self.runs_route,
'/run_metadata': self.run_metadata_route,
'/run_metadata_tags': self.run_metadata_tags_route,
}
我们可以看到，‘/graph'这个接口返回值为self.graph_route，在这个文件中搜索graph_route方法
@wrappers.Request.application
def graph_route(self, request):
"""Given a single run, return the graph definition in protobuf format."""
run = request.args.get('run')
if run is None:
return http_util.Respond(
request, 'query parameter "run" is required', 'text/plain', 400)
limit_attr_size = request.args.get('limit_attr_size', None)
if limit_attr_size is not None:
try:
limit_attr_size = int(limit_attr_size)
except ValueError:
return http_util.Respond(
request, 'query parameter `limit_attr_size` must be an integer',
'text/plain', 400)
large_attrs_key = request.args.get('large_attrs_key', None)
try:
result = self.graph_impl(run, limit_attr_size, large_attrs_key)
except ValueError as e:
return http_util.Respond(request, e.message, 'text/plain', code=400)
else:
if result is not None:
(body, mime_type) = result # pylint: disable=unpacking-non-sequence
return http_util.Respond(request, body, mime_type)
else:
return http_util.Respond(request, '404 Not Found', 'text/plain',
code=404)
在这个方法中，分别取了“run”,”limit_attr_size“和“large_attrs_key”三个参数，和前面url所调用的参数一致，介绍这个是我们要找的方法。在方法的最后，调用了self.graph_impl生成了图，我们继续查看这个方法
def graph_impl(self, run, limit_attr_size=None, large_attrs_key=None):
"""Result of the form `(body, mime_type)`, or `None` if no graph exists."""
try:
graph = self._multiplexer.Graph(run)
except ValueError:
return None
# This next line might raise a ValueError if the limit parameters
# are invalid (size is negative, size present but key absent, etc.).
process_graph.prepare_graph_for_ui(graph, limit_attr_size, large_attrs_key)
return (str(graph), 'text/x-protobuf') # pbtxt
这个方法调用了self._multiplexer.Graph(run)生成图。_multiplexer是一个event_multiplexer实例，在graph_plugln初始化时通过base_plaugin.TBContext获得。
def __init__(self, context):
"""Instantiates GraphsPlugin via TensorBoard core.
Args:
context: A base_plugin.TBContext instance.
"""
self._multiplexer = context.multiplexer
进入tensorboard/backend/event_processing/event_multiplexer，找到Graph方法
def Graph(self, run):
"""Retrieve the graph associated with the provided run.
Args:
run: A string name of a run to load the graph for.
Raises:
KeyError: If the run is not found.
ValueError: If the run does not have an associated graph.
Returns:
The `GraphDef` protobuf data structure.
"""
accumulator = self.GetAccumulator(run)
return accumulator.Graph()
def GetAccumulator(self, run):
"""Returns EventAccumulator for a given run.
Args:
run: String name of run.
Returns:
An EventAccumulator object.
Raises:
KeyError: If run does not exist.
"""
with self._accumulators_mutex:
return self._accumulators[run]
Graph方法获取了run对应的accumulator实例，并返回了这个实例的Graph方法的返回值。我们进入tensorboard/backend/event_processing/event_accumulator，找到Graph()方法
def Graph(self):
"""Return the graph definition, if there is one.
If the graph is stored directly, return that. If no graph is stored
directly but a metagraph is stored containing a graph, return that.
Raises:
ValueError: If there is no graph for this run.
Returns:
The `graph_def` proto.
"""
graph = tf.GraphDef()
if self._graph is not None:
graph.ParseFromString(self._graph)
return graph
raise ValueError('There is no graph in this EventAccumulator')
事实上，它返回了一个GraphDef图，因此我们也可以通过将日志转换为GraphDef的方式读取日志。
# 导入要用到的基本模块。为了在python2、python3 中可以使用E侣兼容的 print 函数
from __future__ import print_function
import numpy as np
import tensorflow as tf
# 创建图和Session
graph = tf.Graph()
sess = tf.InteractiveSession(graph=graph)
#日志路径
model_fn = '/log/events.out.tfevents.1535957014.ubuntu'
for e in tf.train.summary_iterator(model_fn):
if e.HasField('graph_def'):
graph = e.graph_def;
graph_def = tf.GraphDef()
graph_def.ParseFromString(graph)
print(graph_def)
我们新版建一个python文件，改日志路径为自己的日志位置，便可以得到与TensorBoard相同的内容。
以上这篇使用TensorBoard中graph模块图结构分析就是小编共享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持乐购源码。

在词法分析器中使用怎么样的算法和数据结构是我们的主要研究内容。
词法分析器的实现方法
手工编码实现法
相对复杂，且容易出错
当能够对各个部分进行相当好的控制，效率高
是目前非常流行的实现方法
GCC， LLVM，...
词法分析器的生成器
可快速原型、代码量少
但较难控制细节
如下是手工编码分析常用的转移图：
其中双圆圈表示接收/识别状态，一个单词的识别已经结束。
下面给出一个转移图算法的例子：
token nextToken(){
    c = getChar();
    switch(c){
        case '<': c = getChar();
                  switch(c) {
                      case '=': return LE;
                      case '>': return NE;
                      default: rollback(); return;
                  }
        case '=': return EQ;
        case '>': c = nextChar();
                  switch(c): //similar
    }
}
token nextToken(){
    c = getChar();
    switch(c){
        // continued from abobe cases...
        case 'a', ..., 'z', 'A', ..., 'Z', '_':
            c = getChar();
            while(c == 'a' ||  c == 'b' || ... || c == '_')
                c = getChar(); 
    }
}
识别关键字
（以 if 为例），有如下两种方法：
对于 标识符 和 关键字 其实是有很大的交集的：
从语法分析的角度看，关键字是标识符的一部分
以C语言为例：
标识符：以字母或下划线开头，后面跟零个或者多个字母、下划线、或数字。
关键字：if, while, else, ....
关键字表算法
对给定语言中所有的关键字，构架关键字构成的哈希表H
对所有的标识符和关键字，先统一按标识符的转移图进行识别
识别完成后，进一步查表H看是否是关键字
通过合理的构造哈希表H（完美哈希），可以O(1)时间完成
原文链接：
编译原理 - 网易云课堂

算法复杂度分析
一、什么是复杂度分析？

对算法运行所需要时间的分析叫时间复杂度分析
对算法运行时所占用的空间的分析叫空间复杂度分析

二、 为什么需要复杂度分析？

1.测试结果非常依赖测试环境
2.测试结果受数据规模的影响很大


三、怎么对复杂度进行分析？


1. 只关注循环次数最多的一段代码
大O这种复杂度表示方法只是一种变化趋势。我们通常会忽略掉公式中的常量、低阶、系数，只需要记录一个最大阶的量级就可以了。所以，我们在分析一个算法、一段代码的时间复杂度的时候，只关注循环执行次数最多的那一段代码就可以了。


2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n)))=O(max(f(n), g(n))).


3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n)).也就是说，假设 T1(n) = O(n)，T2(n) = O(n )，则 T1(n) * T2(n) = O(n )。落实到具体的代码上，我们可以把乘法法则看成是嵌套循环


复杂度量级


常量级别	O(1)


对数阶级 O(logn)


线性阶 O(n)


线性对数阶 O(nlogn)


平方阶 O(n2)、立方阶O(n3)…k次方阶 O(n^k)


指数阶O(2^n)


阶乘阶O(n!)
对于刚罗列的复杂度量级，我们可以粗略地分为两类，多项式量级和非多项式量级。其中，非多项式量级只有两个：O(2 ) 和 O(n!)。

我们把时间复杂度为非多项式量级的算法问题叫作NP（Non-DeterministicPolynomial，非确定多项式）问题。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。


空间复杂度
我们常见的空间复杂度就是 O(1)、O(n)、O(n )，像 O(logn)、O(nlogn) 这样的对数阶复杂度平时都用不到。而且，空间复杂度分析比时间复杂度分析要简单很多。

最好、最坏、平均、均摊时间复制度


最好时间复杂度
最好情况时间复杂度就是，在最理想的情况下，执行这段代码的时间复杂


最坏时间复杂度
最坏情况时间复杂度就是，在最糟糕的情况下，执行这段代码的时间复杂度


平均情况时间复杂度
用代码在所有情况下执行的次数的加权平均值表示


均摊时间复杂度
在代码执行的所有复杂度情况中绝大部分是低级别的复杂度，个别情况是高级别复杂度且发生具有时序关系时，可以将个别高级别复杂度均摊到低级别复杂度上。基本上均摊结果就等于低级别复杂度。