算法和数据结构总结大纲


时间复杂度

基本原则

一些容易混淆的时间复杂度分析

常数优化

  1. IO优化(快速读写)
  2. 避免浮点数, 尽量只处理整数
  3. 快速乘法, 通过对乘数拆解做移位
  4. 避免除法, 2的整数次幂除法可以用移位代替
  5. 避免取模, 快速取模方法

基本思想

递归

主要可以分为如下三种:

  • 尾部递归, 就是循环, 不支持循环的语言会有尾递归优化
  • 中间递归, 可以用一个栈模拟栈帧来将其转为循环, 比如阶乘的递归实现
  • 树状递归, 这个就比较复杂了, 最好是从需求上将其转为循环, 比如斐波拉契数列的递归实现

分治

前提: 如果原问题可分割成k个子问题,1<k≤n,且这些子问题都可解, 并可利用这些子问题的解求出原问题的解

流程:

  • 分解: 将一个问题分成多个类似的子问题(中间递归或者树状递归都可以)
  • 解决: 简单子问题可以直接求解
  • 合并: 将子问题的解合并成原问题的解

状态和状态转移方程:

  • 状态: 你要求解的子问题
  • 状态转移方程: 如何将子问题合并

例子:

  • 二分查找
  • 快速排序
  • 归并排序
  • MapReduce

贪心

前提:

  • 局部最优解可以合成为全局最优解
  • 某个状态以前的过程不会影响以后的状态, 只与当前状态有关(无后效性)

流程:

  • 分解: 将一个问题分解成线性的多个子问题(中间递归)
  • 解决: 对每一个线性子问题求局部最优解
  • 合并: 将子问题的局部最优解合并成全局最优解
可以视作为分治的一种特殊情况, 问题可以被分解链式的单个问题, 最后合并的时候是线性合并

动态规划

前提: 将原问题分解成为子问题后, 存在重叠子问题

可以视作为分治的一种特殊情况, 同样要求问题可以被分解为链式的单个问题, 只不过由于分解之后的子问题可能重复, 所以保存每一个子问题的最优解, 这个最优解可能在不同的状态下会被更新.
通常容易用递推实现

离散化

只考虑需要的值, 而不用考虑整个值域

基本数据结构

  • 逻辑结构: 集合/线性结构/树形结构/图形结构
  • 存储结构: 顺序存储/链式存储/索引存储/Hash存储

线性表

  • 数组/链表
  • 队列/栈

图论

存储方式

  • 邻接表
  • 邻接矩阵

基础算法

搜索和遍历
  • BFS
  • DFS
最短路算法

松弛操作: 更新两点距离

Dijkstra
  • 单源最短路
  • 要求: 非负权边
  • 适合稠密图, 邻接表
  • 思路: 贪心 O(N^2)

    • 分为已处理集合P和未处理集合Q
    • 每一步从Q中选择距离源点s最近的点u, 更新源点s到点u所有近邻的距离
SPFA(Bellman-Ford)
  • 稀疏图/负权边
  • 思路: 基于BFS O(kN)

    • 源点s入队列
    • 出队列节点u, 如果可以松弛, 节点u的所有近邻入队列
Floyd
  • 多源最短路
  • 思路: 动态规划

    • 假设>$D_k(i, j)$<表示从i到j的最短路径, 且只经过>$[1, k]$<的节点

      • 若经过k点, 那么>$D_k(i, j) = D_{k-1}(i, k) + D_{k-1}(k, j)$<
      • 若不经过k点, 那么>$D_k(i, j) = D_{k-1}(i, j)$<
      • 因此: >$D_k(i, j) = \min{D_{k-1}(i, j), D_{k-1}(i, k) + D_{k-1}(k, j)}$<
for(int k = 1; k <= n; k++)
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            d[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
最小生成树
Prim
  • 思路: 贪心 O(N^2)

    • 往集合V加入起始点s
    • 找到一端在V中另一端不在V中且权值最小的边
    • 记录这条边, 并把节点添加到V中
    • 直到所有节点都加入V
Kruskal
  • 思路: 并查集 O(NlogN)

    • 对所有边排序
    • 考虑每一条边的两个端点是否在同一并查集中
    • 如果不联通则合并两个并查集
    • 直到所有边都被检查, 或者所有节点都在同一个集合中(记录所有节点数做一次合并就减去一)
拓扑排序

并查集

  • 集合存在代表元素, 但不关心具体是哪一个元素
  • 常用操作

    • 快速找到代表元素/合并两个集合
  • 实现

    • 树和路径压缩

前缀和

  • 定义: 数组前N项的和: >$S[N]=a[1]+a[2]+\cdots+a[N]$<
  • 用途:

    • 快速得到区间和: >$S[M, N] = S[N] - S[M-1]$<
    • 区间快速运算: 对>$[M, N]$<加上k

      • 构造辅助数组aux[i], 表示>$[i, len(a)]$<区别的变化值

        • 拆分成: >$[M, len(a)]$<加上k, >$[N+1, len(a)]$<减去k
        • aux[M] = k, aux[N+1] = -k
        • 求aux的前缀和即可知道每个位置的变化量

论文图表自动编译


前情提要

老板特别喜欢在论文里面加图加表...加到最后整个论文堆了二三十张图, 一张一张手动处理我显然不太能受得了, 所以就写了个脚本来批量生成图表.

我的图表主要分为两类, 一类是柱状图, 这个主要是利用>$LaTeX$<的pgfplot包来画的, 为了批量修改图标样式, 所以利用\input给每张图配置了统一的模板; 另一类就是Visio了, 很多复杂的样式单纯使用>$LaTeX$<根本画不出来, 或者画起来很麻烦. 不过说起来, 使用>$LaTeX$<画的柱状图比起Excel生成的不知道好看到哪里去了(x

正片开始

我要实现的主要目标是, 能够自动识别我的源文件, 然后只要简单的一个make就能编译出我想要的图表.

对于>$LaTeX$<问题不大, 因为texlive本来就是命令行工具, 但是对于Visio来说就很麻烦了, 不过在万能的github上搜了搜发现了这个, 用了用发现这个本质上还是调起Visio然后自动另存为PDF= =它并不能脱离Visio单独使用
不过好在我的环境是Windows Linux Subsystem, 所以调起win32原生应用并不是一个太大的问题.

Makefile模板

# Common Command Alias
ECHO := @echo -e
MKDIR := mkdir -p
CP := cp
RMF := rm -f
RMD := rm -rf

# Function Command Alias
LATEXMK := latexmk -interaction=nonstopmode -file-line-error --outdir=output
VSDX2PDF := ../utils/OfficeToPDF.exe
PDFCROP := pdfcrop
PDF2EPS := pdftops -eps
LATEXINDENT := latexindent

主要是定义了一些常用的变量, 方便调用和修改.

  • LATEXMK是LateX的编译控制器, 会默认调用pdflatex去编译, 当然你可以通过参数选择你实际需要的编译器;
  • VSDX2PDF是之前介绍的, 可以将Visio自动转成PDF的工具;
  • PDFCROP用于自动裁剪白边, 无论是直接编译出的PDF还是VISIO转成的PDF都有白边, 手动去白边很累的;
  • PDF2EPS用于将PDF的图片转成EPS;
  • LATEXINDENT用于格式化tex文件(可能是我的强迫症

编译LATEX图表

include ../../mk/template.mk

OUTPUTDIR := output

SOURCES := .
TEXFILES := $(foreach dir,$(SOURCES),$(notdir $(wildcard $(dir)/*.tex)))
TARGETS := $(TEXFILES:.tex=)

TEMPLATES := template
TEMPLATEFILES := $(foreach dir,$(SOURCES),$(wildcard $(dir)/$(TEMPLATES)/*.tex))

.PHONY: all install clean clean_aux $(TARGETS)
.PRECIOUS: $(OUTPUTDIR)/%.pdf $(OUTPUTDIR)/%.dvi $(OUTPUTDIR)/%.eps

all: $(TARGETS)
    $(ECHO) "\033[36mBuilding $@...\033[0m"

$(OUTPUTDIR):
    $(MKDIR) $(OUTPUTDIR)

$(TARGETS): %: $(OUTPUTDIR)/%.pdf $(OUTPUTDIR)/%.dvi $(OUTPUTDIR)/%.eps | $(OUTPUTDIR)
    $(ECHO) "\033[36mBuilding $@...\033[0m"
    @$(LATEXMK) -c $@.tex >> /dev/null 2>&1

$(OUTPUTDIR)/%.pdf: %.tex $(TEMPLATEFILES) | $(OUTPUTDIR)
    $(ECHO) "\033[36mBuilding $@...\033[0m"
    $(LATEXMK) -pdf $<

$(OUTPUTDIR)/%.dvi: %.tex $(TEMPLATEFILES) | $(OUTPUTDIR)
    $(ECHO) "\033[36mBuilding $@...\033[0m"
    $(LATEXMK) -dvi $<

$(OUTPUTDIR)/%.eps: $(OUTPUTDIR)/%.pdf | $(OUTPUTDIR)
    $(ECHO) "\033[36mBuilding $@...\033[0m"
    $(PDFCROP) $(OUTPUTDIR)/$(*F).pdf $(OUTPUTDIR)/$(*F).pdf
    $(PDF2EPS) $(OUTPUTDIR)/$(*F).pdf

install: $(TARGETS:%=../pdf/%.pdf) $(TARGETS:%=../dvi/%.dvi) $(TARGETS:%=../eps/%.eps)
    $(ECHO) "\033[36mInstalling Files...\033[0m"

$(TARGETS:%=../pdf/%.pdf): ../pdf/%.pdf: $(OUTPUTDIR)/%.pdf
    $(CP) $< $@

$(TARGETS:%=../dvi/%.dvi): ../dvi/%.dvi: $(OUTPUTDIR)/%.dvi
    $(CP) $< $@

$(TARGETS:%=../eps/%.eps): ../eps/%.eps: $(OUTPUTDIR)/%.eps
    $(CP) $< $@

clean_aux:
    $(ECHO) "\033[36mCleaning aux files...\033[0m"
    $(RMF) \
        $(OUTPUTDIR)/*.fdb_latexmk \
        $(OUTPUTDIR)/*.aux \
        $(OUTPUTDIR)/*.fls \
        $(OUTPUTDIR)/*.log \
        $(OUTPUTDIR)/*.synctex.gz

clean:
    $(ECHO) "\033[36mCleaning all files...\033[0m"
    $(RMD) $(OUTPUTDIR)

流程主要是这样子的:

  1. 扫描SOURCES目录下的.tex文件获得已有的TARGETS
  2. 扫描TEMPLATES目录下.tex文件获得已有的TEMPLATEFILES
  3. TARGETS目标转换为OUTPUTDIR/TARGET.pdf触发实际编译
  4. $(OUTPUTDIR)/%.pdf同时依赖源文件和TEMPLATEFILES, 实现源文件/模板修改后触发所有图表自动更新
  5. $(TARGETS:%=../pdf/%.pdf)的目标是为了将OUTPUTDIR下的输出文件安装到父目录的对应文件夹下

这样就可以实现自动识别目录下的源文件并自动编译了, 同时修改文件可以及时且不遗漏的触发增量编译.

编译VISIO图表

include ../../mk/template.mk

OUTPUTDIR := output

SOURCES := .
VSDXFILES := $(foreach dir,$(SOURCES),$(notdir $(wildcard $(dir)/*.vsdx)))
TARGETS := $(VSDXFILES:.vsdx=)

.PHONY: all install clean $(TARGETS)
.PRECIOUS: $(OUTPUTDIR)/%.pdf $(OUTPUTDIR)/%.eps

all: $(TARGETS)
    $(ECHO) "\033[36mBuilding $@...\033[0m"

$(OUTPUTDIR):
    $(MKDIR) $(OUTPUTDIR)

$(TARGETS): %: $(OUTPUTDIR)/%.pdf $(OUTPUTDIR)/%.eps | $(OUTPUTDIR)
    $(ECHO) "\033[36mBuilding $@...\033[0m"

$(OUTPUTDIR)/%.pdf: %.vsdx | $(OUTPUTDIR)
    $(VSDX2PDF) $< $@

$(OUTPUTDIR)/%.eps: $(OUTPUTDIR)/%.pdf | $(OUTPUTDIR)
    $(PDFCROP) $< $<
    $(PDF2EPS) $<

install: $(TARGETS:%=../pdf/%.pdf) $(TARGETS:%=../eps/%.eps)
    $(ECHO) "\033[36mInstalling Files...\033[0m"

$(TARGETS:%=../pdf/%.pdf): ../pdf/%.pdf: $(OUTPUTDIR)/%.pdf
    $(CP) $< $@

$(TARGETS:%=../eps/%.eps): ../eps/%.eps: $(OUTPUTDIR)/%.eps
    $(CP) $< $@

clean:
    $(ECHO) "\033[36mCleaning all files...\033[0m"
    $(RMD) $(OUTPUTDIR)

VISIO的编译流程与LATEX的类似, 只不过没有模板和DVI文件.

图表根目录

include ../mk/template.mk

SOURCES := BarChart DiscTree Visio 
OUTPUTS := pdf dvi eps

.PHONY: all clean $(SOURCES) $(SOURCES:%=clean_%)

all: $(SOURCES)
    $(ECHO) "\033[36mBuilding $@...\033[0m"

$(SOURCES): | $(OUTPUTS)
    $(ECHO) "\033[36mBuilding $@...\033[0m"
    make -C $@ all 
    make -C $@ install

$(OUTPUTS):
    $(MKDIR) $@

clean: $(SOURCES:%=clean_%)
    $(ECHO) "\033[36mCleaning all files...\033[0m"
    $(RMD) pdf dvi eps

$(SOURCES:%=clean_%):
    make -C $(@:clean_%=%) clean

这里的$(SOURCES:%=clean_%)是为了能使用类似于make clean_BarChart来单独清理BarChart子目录.

将各个子目录编译出的文件合并到根目录上并没有在根目录上来控制而是在各个子目录里install到根目录上来. 因为在根目录上很难做到这一点, 因为在编译开始前我对每个子目录到底有哪些目标文件是未知的, 只有在实际的编译流程开始以后才能知道, make(gnu)提供的控制指令有着很大的局限性, 如果用python编写类似的脚本是可以做到类似的需求的.

总结与思考

虽然说调试整个一套编译脚本花费了一定的时间(还包括论文的自动编译以及其他的一些, 不过都很类似), 但是对于整体效率的提升是非常巨大的.

在这之前, 对于LaTeX图表我需要单独每个编译出PDF, 对于Visio我需要每一个文件都点开然后另存为PDF. 同时, 对于裁白边, 都是通过Adobe Illustrator CC打开PDF, 然后全选内容导出资源为PDF, 非常累, 还可能碰到字体的问题. 此外, 还要再用Adobe Acrobat DC打开裁掉白边的PDF将其另存为eps.

图表比较少, 修改不大的时候, 这一套流程下来还可以接受, 但是图表一多, 简直要疯. 然后, 现在只要打开WSL然后make, 只要花上个厕所的时间, 就可以一键自动编译图表及论文了w

思考

  • WSL能够在运行Linux程序的前提下运行win32原生程序是一大优势
  • 以前编译OpenCV以及ROS的时候不知道为什么还要用cmakepython来控制编译, 现在深入用过一遍make以后觉得主要还是make存在着比较大的局限性

最后:

CLI大法好!

一些容易混淆的时间复杂度分析


前言

时间复杂度分析简单来说大概分为这么几种情况:

  • 一层循环就是一层O(N), 循环套循环需要相乘
  • 如果是树状结构, 比如说有分治(二叉搜索, 快排)的时候, 那么就是O(logN)
  • 如果有递归:

    • 如果是尾递归, 那么其实是和循环等价的
    • 如果是树状递归, 比如说斐波拉契数列, 那么就是O(2^N), 确切的说是O(branches^depth)

Example1

Suppose we had an algorithm that took in an array of strings, sorted each string, and then sorted the full array. What would the runtime be?

Let's define new terms-and use names that are logical.

  • Let s be the length of the longest string.
  • Let a be the length of the array.

Now we can work through this in parts:

  • Sorting each string is O(s log s).
  • We have to do this for every string (and there are a strings), so that's O(a*s log s).
  • Now we have to sort all the strings. There are a strings, so you'll may be inclined to say that this takes O(a log a) time. This is what most candidates would say. You should also take into account that you need to compare the strings. Each string comparison takes O(s) time. There are O(a log a) comparisons, therefore this will take O(a*s log a) time.

If you add up these two parts, you get 0(a*s (log a + log s)).

这个很容易误认为是O(N^2 logN), 一方面是string的长度和array的长度并不一样, 另外一方面是在array排序的时候很容易忽略字符串比较还需要花费时间.

Example2

The following code prints all Fibonacci numbers from 0 to n. What is its time complexity?
void allFib(int n) {
    for (int i= 0; i < n; i++) {
        System.out.println(i + ": "+ fib(i));
    }
}

int fib(int n) {
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    return fib(n - 1) + fib(n - 2);
} 

Instead, let's walk through each call.

  • fib(!) -> 2^1 steps
  • fib(2) -> 2^2 steps
  • fib(3) -> 2^3 steps
  • fib(4) -> 2^4 steps
  • fib(n) -> 2^n steps

Therefore, the total amount of work is: 2^1 + 2^2 + 2^3 + 2^4 + ... + 2^N = 2^(N+1)

这个很容易误认为是O(N*2^N), 主要是fib(n)这里的n每次循环都是变化的...很容易被误导

总结

时间复杂度的求法并不是很难, 基本就那么几种情况, 需要注意的是处理字符串时不能忽略掉字符串的长度.

Reference

Cracking the Coding Interview 6th Edition


基于注解的简单权限控制实现


前情提要

这个其实是很早的时候在做本科毕设的时候实现的, 当时因为权限结构简单, 懒得上一个类似于Spring Security这么重的框架, 以及主要是想尝试一下自己实现注解就简单做了一下基于方法注解的权限控制.

设计思路

因为整个系统只有管理员/登录用户/未登录用户三种不同的角色, 并同时考虑到有些接口(比如修改/删除数据)只有作者才能访问, 所以一共设计了@AdminOnly, @CreatorOnly@LoginOnly三种不同的注解.

注解部分实现

注解的实现代码很简单, 主要是注意需要标记@Retention(RetentionPolicy.RUNTIME)才能在运行时通过反射访问到这个注解:

package weplay.annotation;

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

/**
 * Created by sl on 17/4/18.
 * check the accessor is admin
 */
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.METHOD, ElementType.TYPE})
public @interface AdminOnly {
    /**
     * exclude method's name when mark class
     */
    String[] exclude() default {};
    /**
     * indicate the check is valid
     */
    boolean isValid() default true;
}

因为需要@AdminOnly的方法很多, 为了简单所以除了方法注解以外也设置了类注解, 添加exclude属性以排除某一个类中不需要使用该注解过滤的方法, isValid是为了临时禁用该注解, 方便调试.

package weplay.annotation;

import weplay.enums.EntityType;

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

/**
 * Created by sl on 17/4/18.
 * check the accessor is creator
 */
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.METHOD})
public @interface CreatorOnly {
    /**
     * indicate EntityType of Entity
     */
    EntityType type();

    /**
     * indicate the position of EntityId in URI
     */
    int position();

    /**
     * indicate the check is valid
     */
    boolean isValid() default true;

    /**
     * indicate admin can access this handler
     */
    boolean allowAdmin() default true;
}

这里的设计比较纠结, 因为我需要验证当前用户对当前访问的数据条目有没有权限, 所以需要使用type来获得访问数据条目的业务类型, 以及需要通过position来知道具体的数据条目的id, 这样我才能查询到当前访问的数据条目的创建者, 从而判断是否允许访问, allowAdmin表示除了创建者管理员是否也能访问该接口.

package weplay.annotation;

import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;

/**
 * Created by sl on 17/4/22.
 */
@Retention(RetentionPolicy.RUNTIME)
@Target({ElementType.METHOD})
public @interface LoginOnly {
    /**
     * indicate the check is valid
     */
    boolean isValid() default true;
}

这个表示是否只有登录用户才能访问该接口.

注解解析实现

注解的解析放在SpringMVC的Interceptor中, 因为HandlerInterceptor是单例需要可重入, 所以使用了HandlerInterceptor封装RequestContextHolder.currentRequestAttributes()在当前请求的上下文中临时保存值.
fetchInfo()用于从请求中读取后续解析需要的数据, processAdminOnly(), processCreateOnly()processLoginOnly()分别解析三个不同的注解, 这里可以考虑做一个公共接口, 然后不同的注解做不同的实现.
preHandle()中, 通过handlerMethod.getBeanType().getAnnotations()handlerMethod.getMethod().getAnnotations()分别获取类注解和方法注解, 这里使用了Spring提供的HandlerMethod类, 如果直接使用反射的话, 可以通过class.getAnnotations()class.getMethod(name, parameterTypes).getAnnotations()分别获取到类注解和方法注解.
获取到注解对象以后, 可以通过直接之前定义的方法来获取到注解配置时设置的值, 比如adminOnly.exclude(), 然后根据业务需要判断是否放行还是抛出异常中止请求响应.

package weplay.aop;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.web.method.HandlerMethod;
import org.springframework.web.servlet.HandlerInterceptor;
import org.springframework.web.servlet.ModelAndView;
import weplay.annotation.AdminOnly;
import weplay.annotation.CreatorOnly;
import weplay.annotation.LoginOnly;
import weplay.enums.AccountState;
import weplay.enums.AccountType;
import weplay.enums.EntityType;
import weplay.enums.ErrorCode;
import weplay.exception.CustomException;
import weplay.helperBean.viewBean.UserInfo;
import weplay.resource.Settings;
import weplay.service.IActivityService;
import weplay.service.IAuthService;
import weplay.service.IEntityService;
import weplay.service.IUserService;
import weplay.utils.RequestContextUtil;

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;
import java.lang.annotation.Annotation;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by sl on 17/4/18.
 */
public class AuthorityInterceptor implements HandlerInterceptor {
    private IAuthService authService;
    private IUserService userService;
    private IActivityService activityService;
    private IEntityService entityService;

    /**
     * fetch basic info from request
     */
    private void fetchInfo(HttpServletRequest req) throws CustomException {
        String uri = req.getRequestURI();
        String token = req.getHeader("token");
        Integer currentUid;
        AccountType accountType;
        UserInfo userInfo;
        if (token != null) {
            currentUid = authService.readUidByToken(token);
            if (currentUid == Settings.ROOT_ADMIN_ID) {
                accountType = AccountType.ADMIN;
            } else {
                accountType = AccountType.NORMAL;
            }
            userInfo = userService.readUserInfoByUid(currentUid);
        } else {
            token = "";
            currentUid = -1;
            accountType = AccountType.TOURISM;
            userInfo = new UserInfo();
        }
        // save to RequestContextUtil
        RequestContextUtil.setAttribute("uri", uri);
        RequestContextUtil.setAttribute("token", token);
        RequestContextUtil.setAttribute("uid", currentUid);
        RequestContextUtil.setAttribute("accountType", accountType);
        RequestContextUtil.setAttribute("userInfo", userInfo);
    }

    /**
     * process @AdminOnly
     */
    private void processAdminOnly(Annotation annotation, HandlerMethod handlerMethod) throws CustomException {
        AccountType accountType = (AccountType) RequestContextUtil.getAttribute("accountType");

        if (annotation instanceof weplay.annotation.AdminOnly) {
            AdminOnly adminOnly = (AdminOnly) annotation;
            // check isValid
            if (!adminOnly.isValid()) {
                return;
            }
            // check exclude method
            for (String s : adminOnly.exclude()) {
                if (s.equals(handlerMethod.getMethod().getName())) {
                    return;
                }
            }
            // check current user is admin
            if (accountType != AccountType.ADMIN) {
                throw new CustomException(ErrorCode.NO_PERMISSION, "ADMIN ONLY");
            }
        }
    }

    /**
     * process @CreateOnly
     */
    private void processCreateOnly(Annotation annotation) throws CustomException {
        String uri = (String) RequestContextUtil.getAttribute("uri");
        Integer currentUid = (Integer) RequestContextUtil.getAttribute("uid");
        AccountType accountType = (AccountType) RequestContextUtil.getAttribute("accountType");

        if (annotation instanceof CreatorOnly) {
            CreatorOnly creatorOnly = (CreatorOnly) annotation;

            // read EntityType and EntityId
            String[] uriPartition = uri.split("/");
            String entityIdStr = uriPartition[creatorOnly.position()];
            Integer entityId;
            if (entityIdStr.contains(".")) {
                entityId = Integer.valueOf(entityIdStr.split("\\.")[0]);
            } else {
                entityId = Integer.valueOf(entityIdStr);
            }
            EntityType entityType = creatorOnly.type();

            // read CreatorId
            Integer creatorId = -1;
            switch (entityType) {
                case ACTIVITY:
                    creatorId = activityService.readActivityById(entityId).getCreator();
                    break;
                case NOTIFICATION:
                    creatorId = entityService.readNotificationById(entityId).getCreator();
                    break;
                case PHOTO:
                    creatorId = entityService.readPhotoById(entityId).getCreator();
                    break;
            }

            // update accountType
            if (currentUid.equals(creatorId)) {
                accountType = AccountType.CREATOR;
                RequestContextUtil.setAttribute("accountType", accountType);
            }

            // check current User is creator or admin if admin allow access
            if (creatorOnly.isValid() && accountType != AccountType.CREATOR &&
                    !(creatorOnly.allowAdmin() && accountType == AccountType.ADMIN)) {
                throw new CustomException(ErrorCode.NO_PERMISSION, "CREATOR ONLY");
            }
        }
    }

    /**
     * process @CreateOnly
     */
    private void processLoginOnly(Annotation annotation) throws CustomException {
        AccountType accountType = (AccountType) RequestContextUtil.getAttribute("accountType");
        UserInfo userInfo = (UserInfo) RequestContextUtil.getAttribute("userInfo");

        if (annotation instanceof LoginOnly) {
            LoginOnly loginOnly = (LoginOnly) annotation;
            
            // check isValid
            if (!loginOnly.isValid()) {
                return;
            }
            if (accountType == AccountType.TOURISM) {
                throw new CustomException(ErrorCode.NO_PERMISSION, "LOGIN USER ONLY");
            }
        }
    }

    public boolean preHandle(HttpServletRequest req, HttpServletResponse res, Object o) throws Exception {
        // static resource handler
        if (!(o instanceof HandlerMethod)) {
            return true;
        }
        // convert handler into current Type
        HandlerMethod handlerMethod = (HandlerMethod) o;
        // fetch basic info
        this.fetchInfo(req);
        // process Annotations
        List<Annotation> annotations = new ArrayList<Annotation>();
        annotations.addAll(Arrays.asList(handlerMethod.getBeanType().getAnnotations()));
        annotations.addAll(Arrays.asList(handlerMethod.getMethod().getAnnotations()));
        for (Annotation a : annotations) {
            this.processAdminOnly(a, handlerMethod);
            this.processCreateOnly(a);
            this.processLoginOnly(a);
        }
        return true;
    }
}
package weplay.utils;

import org.springframework.web.context.request.RequestAttributes;
import org.springframework.web.context.request.RequestContextHolder;
import org.springframework.web.context.request.ServletRequestAttributes;

import javax.servlet.http.HttpServletRequest;
import javax.servlet.http.HttpServletResponse;

/**
 * Created by sl on 17/4/22.
 * Utils for wrapping RequestContextHolder
 */
public class RequestContextUtil {
    /**
     * prefix for user custom Attribute
     */
    private static String prefix = "u_";

    /**
     * set Attribute to Context
     */
    public static void setAttribute(String key, Object obj) {
        RequestContextHolder.currentRequestAttributes().setAttribute(prefix + key, obj, RequestAttributes.SCOPE_REQUEST);
    }

    /**
     * get Attribute from Context
     */
    public static Object getAttribute(String key) {
        return RequestContextHolder.currentRequestAttributes().getAttribute(prefix + key, RequestAttributes.SCOPE_REQUEST);
    }

    /**
     * remove Attribute at Context
     */
    public static void removeAttribute(String key) {
        RequestContextHolder.currentRequestAttributes().removeAttribute(prefix + key, RequestAttributes.SCOPE_REQUEST);
    }

    /**
     * get Current Request
     */
    public HttpServletRequest currentRequest() {
        return ((ServletRequestAttributes) RequestContextHolder.currentRequestAttributes()).getRequest();
    }

    /**
     * get Current Response
     */
    public HttpServletResponse currentResponse() {
        return ((ServletRequestAttributes) RequestContextHolder.currentRequestAttributes()).getResponse();
    }
}

注解的使用

配置好注解类并在拦截器中处理注解以后, 那么只需要在相应的地方进行注解标注就可以了, 如同使用Java自带或Spring提供的注解一样. 例如:

@RestController
@AdminOnly(exclude = {"createReport"})
public class AdminController {
    \\...
}
@CreatorOnly(type = EntityType.NOTIFICATION, position = 2)
@RequestMapping(path = "/notification/{id:[0-9]+}", method = RequestMethod.DELETE)
public ResponseEntity<String> deleteNotification(@PathVariable("id") Integer id) throws CustomException {
    \\...
}

总结与回顾

总的来说, 注解本质上相当于只是给类或者方法打了一个标记, 具体想要知道一个类或者一个方法是否有这个标记需要通过反射来获得, 并进行对应的处理.
通过反射对于类进行操作, 总体来说是比较慢的, 目前各大框架的配置逐渐从XML形式转变为注解形式, 这一过程是否会造成比较大的性能损失是一个需要思考的问题.
在这一次的例子中, 每一次请求都对其所有的注解进行遍历是比较慢而且进行了很多操作, 可以考虑增加一个HashMap用于记录一个类/方法对应了哪几个注解, 这样下次访问同一个类/方法时直接查表就可以而不用再通过反射来获取. 或者考虑倒排索引的形式, 记录每一个注解都对应哪些方法, 从而避免重复的查询和处理.


简明ArchLinux安装教程


概述

自用的简明ArchLinux安装教程, 主要参考官方Guide, 部分组件按照自己的喜好来

  • 引导管理采用grub2
  • 网络管理采用systemd-networkd
  • 文件系统用的btrfs

启动ArchISO

略 (这都不会还是立刻右上角吧

网络配置

ArchLinux的安装需要网络, 如果是DHCP的动态网络应该默认就配置好了.

如果是静态配置, 那么将需要手动进行配置, 下面将使用systemd-networkd作为网络管理器, 网络配置采用Arch官方推荐的iproute2而不是经典的net-tools.

检测网络是否联通

ping ip.cn

静态网络配置

确认网卡名称并启动网卡(如果没有启动的话)

ip addr show
ip route show
ip link set $interface up

配置systemd-networkd

'/etc/systemd/network/$interface.network'

[Match]
Name=$interface

[Network]
Address=$address/$prefix
Gateway=$gateway
DNS=$dns_server
systemctl start systemd-networkd.service
systemctl start systemd-resolved.service

临时配置静态IP, 路由和DNS(如果不想用systemd-networkd的话)

ip address add $address/$prefix broadcast + dev $interface
ip route add default via $gateway dev $interface
echo 'nameserver $dns_server' >> /etc/resolv.conf

启用NTP服务(TLS连接需要正确的时间)

timedatectl set-ntp true
timedatectl status

磁盘分区

  • 确定DiskName
fdisk -l
  • 磁盘分区

我一般习惯会分一个swap, 因为使用btrfs所以还要再分一个根卷/, 如果使用EFI则需要再分一个 /efi.

fdisk $disk
g: create GPT partition table
n: add a new partition
d: delete a partition
t: change a partition type
p: print the partition table
w: write table to disk and exit
如果使用的是传统BIOS的话, 需要使用t命令将启动分区的类型设置为BIOS boot(4).
  • 格式化分区
mkfs.ext4 $partition # /
mkswap $partition && swapon $partition # swap
mkfs.btrfs -L $label $partition # / (btrfs)
mkfs.vfat $partition # /efi
  • 挂载分区
mount $partition /mnt
mkdir /mnt/efi && mount $partition /mnt/efi # EFI分区

解压基本系统

  • 修改软件源

/etc/pacman.d/mirrorlist

  • 解压基本系统和安装基本包
pacstrap /mnt base grub openssh sudo # 安装sudo和ssh
pacstrap /mnt vim wget zsh git btrfs-progs  # 其他的一些基本包
  • 生成fstab
genfstab -U /mnt >> /mnt/etc/fstab
  • 复制网络配置(如果之间配置了systemd-networkd的话)
cp /etc/systemd/network/$interface.network /mnt/etc/systemd/network/$interface.network
  • Chroot
arch-chroot /mnt

配置基本系统

  • 配置网络并默认启动SSH(如果之间配置了systemd-networkd的话)
systemctl enable systemd-networkd.service
systemctl enable systemd-resolved.service
systemctl enable sshd.service
  • 配置Root密码
passwd
  • 添加新用户并配置Sudo
groupadd sudoers
useradd -m -G sudoers $user
passwd $user
cat '%sudoers ALL=(ALL) ALL' >> /etc/sudoers
  • 生成Initramfs
mkinitcpio -p linux
  • 配置grub
grub-install --target=i386-pc /dev/sdX
grub-mkconfig -o /boot/grub/grub.cfg
至此, 重启就可以进入到Arch的系统里了

额外的系统配置

  • 设置时区和硬件时钟
ln -sf /usr/share/zoneinfo/$Region/$City /etc/localtime
hwclock --systohc
  • 配置Locale

/etc/locale.gen

locale-gen
echo 'LANG=en_US.UTF-8' > /etc/locale.conf
  • 配置主机名和Hosts
echo $hostname > /etc/hostname

/etc/hosts

127.0.0.1   localhost
::1     localhost

尾声

这样就配置好了ArchLinux的基本系统, 其他的图形配置可以重启以后在SSH里慢慢配置.