Jason Lee Essay

Only dead fish go with the flow!

Jason Lee Essay

最近貌似docker的镜像又被墙了,官方镜像本来就慢的要杀人,第三方的elk镜像不知道怎么也挂了,pull的时候一直报超时?

docker还有一个叫做http_proxy的东西,可通过代理获取镜像?
但是,有多台机器都要用到镜像?都陪代理吗?不行,心疼代理钱。那只能再搞一个私有的docker registry。

看看,我原本只是要一个镜像,结果平白添加了两件事?

还原问题

1
2
$ docker pull docker.elastic.co/elasticsearch/elasticsearch:6.2.4

添加代理

1
2
$ export ALL_PROXY=socks5://localhost:port 
$ docker pull image

添加registry

registry有很多种,内网版本,阿里云、DaoCloud等任意一家云厂商的registry。

如果公司的局域网,一定要搭建一个私服registry,速度提升的速度不要太明显了。推荐一下Nexus3,可以作为Maven、npm和docker三方私服。

如果在家办公,就一个电脑需要pull,那直接用云厂商的服务更好。

以阿里云为例:
在阿里云的产品目录中找到“容器镜像服务-镜像中心-镜像加速器”这个功能,如果第一次打开可能会提示开通。
里面有具体的安装方式。

1
2
3
4
5
6
7
sudo tee /etc/docker/daemon.json <<-'EOF'
{
"registry-mirrors": ["https://id.mirror.aliyuncs.com"]
}
EOF
sudo systemctl daemon-reload
sudo systemctl restart docker

使用spring-boot项目中添加日志输出,java的日志输出一共有两个大的方案log4j/log4j2 ,logback。log4j2算是对log4j的一个升级版本。
常规做法是引入slf4j作为日志入口,log4j或者logback选择一个做实现。spring的项目里面,只有spring-boot-starter-web用的是log4j,其他的用过的starter全部都是logback。

依赖 dependency-spring-boot-starter-logging

spring-boot-starter-logging还有两个很容易混淆的变种的starter
spring-boot-starter-log4jspring-boot-starter-log4j2

前者在版本更新到了1.3之后就停止了,后者持续更新,需要注意下。

dependencies

spring-boot-starter-logging 依赖有

groupId artifactId version
ch.qos.logback logback-classic 1.2.3
org.apache.logging.log4j log4j-to-slf4j 2.10.0
org.slf4j jul-to-slf4j 1.7.25

上面的列表中可知log的最終打印是使用logback實現的。项目中优先选用 spring-boot-starter-logging

logback配置

先看一个典型的配置文件

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
<?xml version="1.0" encoding="UTF-8"?>
<configuration debug="true">
<property name="name" value="spring-boot-logging"/>
<contextName>${name}</contextName>
<appender name="console" class="ch.qos.logback.core.ConsoleAppender">
<encoder>
<pattern>%d{HH:mm:ss.SSS} [%thread] %-5level %logger{36} - %msg%n</pattern>
</encoder>
</appender>

<appender name="rollingFile" class="ch.qos.logback.core.rolling.RollingFileAppender">
<file>logs/infisa.${name}.log</file>
<rollingPolicy class="ch.qos.logback.core.rolling.TimeBasedRollingPolicy">
<fileNamePattern>logs/${name}.%d{yyyy-MM-dd}.log</fileNamePattern>
</rollingPolicy>
<encoder>
<pattern>%d{HH:mm:ss.SSS} [%thread] %-5level %logger{36} - %msg%n</pattern>
</encoder>
</appender>

<!-- project default level -->
<logger name="cn.lee.jason" level="info"/>

<!-- 定义根日志级别 -->
<root level="info">
<appender-ref ref="rollingFile"/>
<appender-ref ref="console"/>
</root>

</configuration>

configuration

configuration是logback.xml的根节点,所有的配置项目都要位于configuration元素下面,可配置的属性有:

属性名称 默认值 说明
scan true 当此属性设置为true时,配置文件如果发生改变,将会被重新加载
scanPeriod 1min 设置监测配置文件是否有修改的时间间隔,如果没有给出时间单位,默认单位是毫秒。当scan为true时,此属性生效。
debug true 当此属性设置为true时,将打印出logback内部日志信息,实时查看logback运行状态。

contextName

每个logger都关联到logger上下文,默认上下文名称为“default”。但可以使用设置成其他名字,用于区分不同应用程序的记录。一旦设置,不能修改。

property

用来定义变量值的标签, 有两个属性,name和value;其中name的值是变量的名称,value的值时变量定义的值。通过定义的值会被插入到logger上下文中。定义变量后,可以使“${}”来使用变量。
例如使用定义上下文名称,然后在设置logger上下文时使用。

appender

负责写日志的组件,它有两个必要属性name和class。name指定appender名称,class指定appender的全限定名.

ConsoleAppender

日志输出到控制台,有以下子节点:
:对日志进行格式化。
:字符串System.out(默认)或者System.err(区别不多说了)

FileAppender

把日志添加到文件,有以下子节点:
      :被写入的文件名,可以是相对目录,也可以是绝对目录,如果上级目录不存在会自动创建,没有默认值。
      :如果是 true,日志被追加到文件结尾,如果是 false,清空现存文件,默认是true。
      :对记录事件进行格式化。(具体参数稍后讲解 )
      :如果是 true,日志会被安全的写入文件,即使其他的FileAppender也在向此文件做写入操作,效率低,默认是 false。

RollingFileAppender

滚动记录文件,先将日志记录到指定文件,当符合某个条件时,将日志记录到其他文件。有以下子节点:
      :被写入的文件名,可以是相对目录,也可以是绝对目录,如果上级目录不存在会自动创建,没有默认值。
      :如果是 true,日志被追加到文件结尾,如果是 false,清空现存文件,默认是true。
      :当发生滚动时,决定RollingFileAppender的行为,涉及文件移动和重命名。属性class定义具体的滚动策略类
      class=”ch.qos.logback.core.rolling.TimeBasedRollingPolicy”: 最常用的滚动策略,它根据时间来制定滚动策略,既负责滚动也负责出发滚动。有以下子节点:
        :必要节点,包含文件名及“%d”转换符,“%d”可以包含一个java.text.SimpleDateFormat指定的时间格式,如:%d{yyyy-MM}。
如果直接使用 %d,默认格式是 yyyy-MM-dd。RollingFileAppender的file字节点可有可无,通过设置file,可以为活动文件和归档文件指定不同位置,当前日志总是记录到file指定的文件(活动文件),活动文件的名字不会改变;
如果没设置file,活动文件的名字会根据fileNamePattern 的值,每隔一段时间改变一次。“/”或者“\”会被当做目录分隔符。
        :
可选节点,控制保留的归档文件的最大数量,超出数量就删除旧文件。假设设置每个月滚动,且是6,则只保存最近6个月的文件,删除之前的旧文件。注意,删除旧文件是,那些为了归档而创建的目录也会被删除。

      class=”ch.qos.logback.core.rolling.SizeBasedTriggeringPolicy”: 查看当前活动文件的大小,如果超过指定大小会告知RollingFileAppender 触发当前活动文件滚动。只有一个节点:
        :这是活动文件的大小,默认值是10MB。
        :当为true时,不支持FixedWindowRollingPolicy。支持TimeBasedRollingPolicy,但是有两个限制,1不支持也不允许文件压缩,2不能设置file属性,必须留空。

      : 告知 RollingFileAppender 合适激活滚动。
      class=”ch.qos.logback.core.rolling.FixedWindowRollingPolicy” 根据固定窗口算法重命名文件的滚动策略。有以下子节点:
        :窗口索引最小值
        :窗口索引最大值,当用户指定的窗口过大时,会自动将窗口设置为12。
        :必须包含“%i”例如,假设最小值和最大值分别为1和2,命名模式为 mylog%i.log,会产生归档文件mylog1.log和mylog2.log。还可以指定文件压缩选项,例如,mylog%i.log.gz 或者 没有log%i.log.zip

logger

用来设置某一个包或具体的某一个类的日志打印级别、以及指定仅有一个name属性,一个可选的level和一个可选的addtivity属性。
可以包含零个或多个元素,标识这个appender将会添加到这个loger
    name: 用来指定受此loger约束的某一个包或者具体的某一个类。
    level: 用来设置打印级别,大小写无关:TRACE, DEBUG, INFO, WARN, ERROR, ALL和OFF,还有一个特俗值INHERITED或者同义词NULL,代表强制执行上级的级别。 如果未设置此属性,那么当前loger将会继承上级的级别。
addtivity: 是否向上级loger传递打印信息。默认是true。同一样,可以包含零个或多个元素,标识这个appender将会添加到这个loger。

root

它也是元素,但是它是根loger,是所有的上级。只有一个level属性,因为name已经被命名为”root”,且已经是最上级了。
    level: 用来设置打印级别,大小写无关:TRACE, DEBUG, INFO, WARN, ERROR, ALL和OFF,不能设置为INHERITED或者同义词NULL。 默认是DEBUG。

作为一个Java攻城狮,随着项目的数目和oracle的努力工作,很容易遇到安装多版本的jdk的问题。

为什么需要多个JDK?

JDK全称是Java SE Development Kit .Java历经了二十几年的发展,到现在已经发布到了JDK10的版本。随着版本的改进,新的特性越来越多的加入,类似5.0引入的泛型,8.0引入的lambda和stream API都对开发有极大的效率提升,不可避免的需要对技术进行升级。同时,主流的开发框架工具spring,mybatis,maven等都会跟随jdk版本进行升级,所以需要一个开发者同时具备多个开发环境。

除了jdk,java的开发环境中,还有maven/gradle,idea/myeclipse等工具需要随着jdk版本进行升级。

经典的配合方案

  1. oracle官网下载jdk,下载对应自己系统版本的jdk安装包/压缩包。
  2. 配置环境变量,JAVA_HOME,CLASSPATH,并将__JAVA_HOME\bin__目录加入__PATH__.
  3. maven官网下载maven的安装文件。
  4. 配置环境变量__M2_HOME__。

如果是gradle用户,请替换3-4步骤。

如何拥有多个JDK?

软链接方案

软链接的做法很简单,比如:

1
2
3
4
5
6
$: ll
drwxr-xr-x 8 jason jason 4096 12月 20 08:24 jdk1.8.0_161
$: ls -n jdk1.8.0_161 jdk
$: ll
lrwxrwxrwx 1 jason jason 12 3月 21 09:33 jdk -> jdk1.8.0_161/
drwxr-xr-x 8 jason jason 4096 12月 20 08:24 jdk1.8.0_161/

然后将软链接__jdk__配置为__JAVA_HOME__。当增加jdk版本时,需要这么做,

1
2
3
4
5
6
7
8
9
10
$: ll
lrwxrwxrwx 1 jason jason 12 3月 21 09:33 jdk -> jdk1.8.0_161/
drwxr-xr-x 8 jason jason 4096 12月 20 08:24 jdk1.8.0_161
drwxr-xr-x 8 jason jason 4096 12月 20 08:24 jdk1.7.0_81
$: rm -rf jdk
$: ls -n jdk1.7.0_81 jdk
$: ll
lrwxrwxrwx 1 jason jason 12 3月 21 09:33 jdk -> jdk1.7.0_81/
drwxr-xr-x 8 jason jason 4096 12月 20 08:24 jdk1.8.0_161
drwxr-xr-x 8 jason jason 4096 12月 20 08:24 jdk1.7.0_81

类似的maven也可以用同样的方式实现,但是这个办法问题在于,每个版本的jdk或者maven需要手工去下载,然后手工去更改软链接。比较费时,这时候,作为能机器做的绝不手工的程序员能想到了,可以写一个shell脚本,切换版本啊,幸运的是已经有人提供了这个服务,请出主角SDKMAN.

SDKMAN ! The Software Development Kit Manager

顾名思义,软件开发工具吧的管理工具。那么sdkman可以管理哪些kit呢?ant,java,gradle,maven,springboot-cli,groovy,kotlin,scala这些基于jvm的开发语言都包括进来。

如何安装?

安装很简单,下载一个shell脚本,执行后就可以了。

1
2
3
4
$ curl -s "https://get.sdkman.io" | bash
$ source "$HOME/.sdkman/bin/sdkman-init.sh"
$ sdk version
sdkman 5.0.0+51
日常使用

以安装java为例

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
$ sdk list java

================================================================================
Available Java Versions
================================================================================
9.0.4-zulu
9.0.4-oracle
9.0.4-openjdk
8.0.163-zulu
8.0.161-oracle
7.0.141-zulu
6.0.93-zulu
10.0.0-zulu
10.0.0-oracle
10.0.0-openjdk
$ sdk install java 8.0.161-oracle

Oracle requires that you agree with the Oracle Binary Code License Agreement
prior to installation. The license agreement can be found at:

http://www.oracle.com/technetwork/java/javase/terms/license/index.html

Do you agree to the terms of this agreement? (Y/n): y


Downloading: java 8.0.161-oracle
In progress...

######################################################################## 100.0%

Repackaging Java 8.0.161-oracle...

Done repackaging...

Installing: java 8.0.161-oracle
Done installing!


Setting java 8.0.161-oracle as default.
$ java -version
java version "1.8.0_161"
Java(TM) SE Runtime Environment (build 1.8.0_161-b12)
Java HotSpot(TM) 64-Bit Server VM (build 25.161-b12, mixed mode)
$ sdk list java

================================================================================
Available Java Versions
================================================================================
9.0.4-zulu
9.0.4-oracle
9.0.4-openjdk
8.0.163-zulu
> * 8.0.161-oracle
7.0.141-zulu
6.0.93-zulu
10.0.0-zulu
10.0.0-oracle
10.0.0-openjdk

以上有一点需要主要,下载jdk的时候需要同意oracle的协议,这个在oracle官网下载的时候也需要确认。
一个jdk就配置好了。
如果需要切换一个jdk版本呢?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
$ sdk install java 7.0.141-zulu  

Downloading: java 7.0.141-zulu

In progress...

######################################################################## 100.0%

Repackaging Java 7.0.141-zulu...

Done repackaging...

Installing: java 7.0.141-zulu
Done installing!

Do you want java 7.0.141-zulu to be set as default? (Y/n): n
$ sdk default java 7.0.141-zulu

Default java version set to 7.0.141-zulu
$ java -version
openjdk version "1.7.0_141"
OpenJDK Runtime Environment (Zulu 7.18.0.3-linux64) (build 1.7.0_141-b11)
OpenJDK 64-Bit Server VM (Zulu 7.18.0.3-linux64) (build 24.141-b11, mixed mode)

版本顺利改变。

TIPS zulu的jdk是基于openjdk的一个改进版本,是另一个jvm的实现。

这样SDKMAN就完成了jdk的切换,类似的道理maven,groovy等都可以这样实现。

总结下吧

SDKMAN安装简单,方便切换多个版本,主要的是省去了去各个网站的单独下载。还是挺方便的。

工具使用svn2git ,gitlab官方推荐的工具,安装方法详细见官网

迁移步骤分为4步:

  1. 确定svn路径及目录分布(branch,tags,trunk)目录。
  2. 执行迁出代码和转换为git工程(svn2git)
  3. 创建gitlab工程。
  4. 提交到git。

详细步骤

确定svn路径及目录分布

首先要确认待转换的SVN目录,比如svn://svn.com/web/product/sample

这个目录下面有branch,tags和trunk目录。

svn的标准目录是branches,tags,trunk三个目录,分别存放分支,版本和主干代码。

执行迁出代码和转换为git工程

svn2git主要api解释

1
2
3
4
5
6
7
8
9
10
Usage: svn2git SVN_URL [options]
Specific options:
--trunk TRUNK_PATH 重新指定trunk目录路径 (default: trunk)
--branches BRANCHES_PATH 重新指定braches目录,在本文中需指向branch目录
--tags TAGS_PATH 重新指定tags目录,在本文中需指向tags目录

--authors AUTHORS_FILE 帐号映射文件
--exclude REGEX 排除目录
-v, --verbose  过程日志限制
-h, --help Show this message

authors.txt是映射svn用户和gitlab目录的情况。比如

1
abc=abc<abc@gitlab.com>

如果现有的目录结构不一致,需要在目录里面填写对应的目录映射。执行以下命令,根据svn工程的大小决定执行时间。

1
svn2git svn://svn.com/web/product/sample --branches branch --tags tags --authors authors.txt -v
可能出现的问题
  1. no associate commit message
    这个是由于branch或者tag的路径映射问题,修改.git/config文件中的branches和tags的映射可解决。
    1
    2
    3
    4
    5
     branches = product/checkup/branch/*:refs/remotes/svn/*
    tags = product/checkup/tags/*:refs/remotes/svn/tags/*
    ==>
    branches = product/checkup/branch/*:refs/remotes/svn/branches/*
    tags = product/checkup/tags/*:refs/remotes/svn/tags/*
创建gitlab工程

在gitlab 中创建对应的工程,获得指定的工程路径,推荐使用ssh通道提交。
使用ssh通道提交,需要提前配置ssh公钥,具体方法参考官方文档

提交到git
1
2
git push --all
git push --tags

然后gitlab页面查看时,能找到数量大于svn中的branch和tags即可。

完整shell流程

1
2
3
4
svn2git svn://svn.com/web/product/sample --branches branch --tags tags --authors authors.txt -v
git remote add origin git@gitlab.com:sample/sample.git
git push --all
git push --tags

工作

产品

桌面和移动端都需要建设,重点在与移动端,构建可以在桌面、微信、app三端的web应用。

溪流健康

健康画像、病历还原、病历上传、异常信息及解读、健康咨询、自测工具、常见药品。

科研产品

自定义CRF,数据权限,检索功能,。

智能推荐

形成一套完整的流程,可配置式的扩充预测疾病模型。

技术

Spring-boot

后台java服务转向微服务方向的spring-boot构建方式,能快速构建、发布、测试、升级服务。

elasticsearch

  • 升级版本号到6系列,升级相应的插件体系
  • 深入luccen部分,优化检索病历功能的评分公式
  • 结合logstash和kinbana构建日志收集分析可视化平台

redis/缓存

引入缓存技术,引入redis缓存热点数据,一些大容量的系统用redis做生产库。

Docker/K8S

将应用转换为服务部署到docker中,对外发布的服务用容器编排方式发布,同时也可以易于在CI/CD流程中进行独立的测试。硬件资源使用k8s管控,所有的服务都工作在docker环境中。

Angular/Ionic

移动端/桌面端的web应用的框架主要依赖angular构建,相应的版本升级到4.0+,移动端主要用ionic进行开发。桌面端UI基于bootstrap构建。

工程

前端工程化

基于gulp的搭建构建、测试、发布流程,完成从开发到单元测试的自动化流程。

自动化工程

代码提交阶段完成静态审查,单元测试的工作,CI/CD流程中完成自动化回归测试的工作,人工测试后进行自动发布工作。

CI流程

持续集成所有的代码构建、测试工作,新做的功能纳入CI体系。

CD流程

公网服务纳入持续发布流程。

团队建设

团队建设方面希望能有一些经费,进行不定期团队建设。

招聘4+人

王鹏由于个人发展原因,离开北京发展,离职1人。

下一年的重点偏向移动端,这部分希望可以扩充人员,扩充一组移动端应用开发的人员,至少包含1个在移动端有过开发经验的技术人员。

Elasticsearch的技术去年一整年主要精力都在完成取数和主动服务器上面,对于这类数据源的技术层面还有一些问题也需要提升和解决,这部分希望能够再加1人,解决两方面的问题:产品化,将取数的功能完整做成易于部署的完整项目;技术升级,将病历检索功能纳入科研产品体系,构建溪流数据的病历检索库。

生活

健康

体重控制到180,6月份达到190。

收入

提升50%,达到35以上。

问题:

给定一个数组,如下所示。目的:按层级输出每个节点的值。
你想输入的替代文字

输出:

4 2 6 1 3 5 7

解决思路:

对于level-order-travels类的问题,简单适用的算法是:breadth-first-search (BFS)。
广度优先算法(Breadth-First-Search),简称BFS,是一种图形搜索演算法。简单的说,BFS是从根节点开始,沿着树的宽度遍历树的节点,如果发现目标,则演算终止。

算法分析:

BFS是一种盲目搜寻法,目的是系统地展开并检查图中的所有节点,以找寻结果。换句话说,它并不考虑结果的可能位置,彻底地搜索整张图,直到找到结果为止。

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
levelOrder(BinaryTree t) {
if(t is not empty) {
// enqueue current root
queue.enqueue(t)

// while there are nodes to process
while( queue is not empty ) {
// dequeue next node
BinaryTree tree = queue.dequeue();

process tree's root;

// enqueue child elements from next level in order
if( tree has non-empty left subtree ) {
queue.enqueue( left subtree of t )
}
if( tree has non-empty right subtree ) {
queue.enqueue( right subtree of t )
}
}
}
}

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void levelOrder(Node root) {
Queue<Node> queue = new LinkedList<Node>();
if (root != null) {
// enqueue current root
queue.offer(root);

// while there are nodes to process
while (queue != null && queue.size() > 0) {
// dequeue next node
Node tree = queue.poll();

System.out.print(tree.data + " ");

// enqueue child elements from next level in order
if (tree.left != null){
queue.offer(tree.left);
}
if (tree.right != null){
queue.offer(tree.right);
}
}
}
}

问题:用sql求出1000以内的质数?输出形式为:

2&3&5&7

求质数算法其实不算难,运用循环的方式对大部分的程序语言来讲都不男写,但sql是个例外。循环对于普通的sql并不好写,除非采用存储过程。

数学定义

数学中的定义是这样的:素数,又称为质数,是指在一个大于1的自然数中,除了1和此整数自身外,无法被其他自然数整除的数。或者说素数是只有1和本身两个因数的数。

一般解法

验证素数的算法可分为两大类,即确定性算法及随机算法。确定性算法中最常用的就是试除法。试除法是根据素数的定义得出的一种方法,用需要验证的数N逐个除以从2开始至N-1中的所有数,若能被某一个数整除,表示有一个因数,说明数N不是素数;若直到N-1都不能被整除,则说明该数是素数。

从上面的思路可以得出的一般算法就是双重迭代的方式。

1
2
3
4
5
6
7
8
9
10
11
boolean isPrime(int n){
if(n<=1){
return false;
}
for(int i=2;i<n;i++){
if(n%i ==0){
return false;
}
}
return true;
}

升级解法

其实,可以对素数的定义进行进一步的分析。要判断数N是否为素数,不需要用N一直除到N-1才能确认,而只需要除到就可以了。
解法就是整数做被除数,所有比他小的数做

1
2
3
4
5
6
7
8
9
10
11
boolean isPrime(int n){
if(n<=1){
return false;
}
for(int i=2;i*i<=n;i++){
if(n%i ==0){
return false;
}
}
return true;
}

sql解法

sql用sql实现上述过程,就比较困难了。需要借助一些特殊的方式。

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
SELECT
GROUP_CONCAT(NUMB SEPARATOR '&')
FROM
(
SELECT
@num :=@num + 1 AS NUMB
FROM
information_schema. TABLES t1,
information_schema. TABLES t2,
(SELECT @num := 1) tmp
) tempNum
WHERE
NUMB <= 1000
AND NOT EXISTS (
SELECT
*
FROM
(
SELECT
@nu :=@nu + 1 AS NUMA
FROM
information_schema. TABLES t1,
information_schema. TABLES t2,
(SELECT @nu := 1) tmp1
LIMIT 1000
) tatata
WHERE
FLOOR(NUMB / NUMA) = (NUMB / NUMA)
AND NUMA *NUMA <= NUMB
AND NUMA > 1
)

主要借助了information_schema. TABLES来构造一个足够大的行数,如果information_schema. TABLES没有足够的行,那求不出正确的解;而information_schema. TABLES行数太多,又会导致代码执行效率底下。

还有更好的解法去发掘。。。

问题:

问题来源:hackerrank-SQL-Projects

问题翻译过来大致是:有一个表__projects__ ,表面有3个字段 task_id , start_date , end_dateend_date__永远比__start_date__大一天。如果__end_date__是连续的,即__end_date == start_date ,那么连续的task是同一个project的任务。求每个project的起始时间是多少?

分析问题:

思路1 : 递归方法

最简单的思路,找到第一个任务的结束时间,根据这个结束时间再去查找下一个开始时间,从而得到下一个的结束时间,重复前面的步骤;如果查找不到开始时间,结束。

但是这里面有一个问题,sql对于递归支持很不友好,写起来很复杂。放弃。

思路2:求所有的开始和结束时间,进行配对。

这个思路是建立在每个task的时间不重合的基础上,幸运的是完全符合本题目的要求。

思路如下:如果一个任务有开始,那么必定有结束;那首尾相接的task,如同链表一样,必定有一个开始和结束。开始时间数和结束时间数相同,且一一匹配。那么求出所有的开始时间和结束时间,按照先后顺序匹配,即得出每个project的时间长度。

解法:

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

SELECT
start_date,
end_date
FROM (
SELECT
@rownum := @rownum + 1 AS rownum,
Start_Date
FROM Projects p
JOIN (SELECT @rownum := 0) b
WHERE Start_Date NOT IN (SELECT End_Date
FROM Projects)) t1
JOIN (
SELECT
@rownum2 := @rownum2 + 1 AS rownum,
End_Date
FROM Projects
JOIN (SELECT @rownum2 := 0) b
WHERE End_Date NOT IN (SELECT Start_Date
FROM Projects)) t2 ON t1.rownum = t2.rownum
ORDER BY DATEDIFF(end_date, start_date), start_date

解释

代码的关键在于,构建了rownum来进行排序,用时间顺序一致的开始和结束时间作为同一对时间来对待。
关键在于求rownum这一部分,其实还应该再加上一个排序,保证时间的先后次序一致。

总结:

这个问题的思考过程中,解决起来的关键点是如何找出数据的规律,代码的复杂度没有想象的那么高,转个弯就好了。

上周五和老婆大人去刷了一波时下大热门影片《寻梦环游记》,看的某人忍不住来废话几句。

有几点值得推荐:

  • 故事非常棒,有亡灵但跟恐怖片完全不搭边;
  • 电影音乐真的好听,几首歌曲都很有水准;
  • 皮克斯真是动画的另一类,动画做到了比真人电影更精致的地步;

主题:

近些年的美国电影都在输出一个叫做Family的概念,速度激情系列、赛车总动员系列、小黄人系列、魔兽等这些电影,有着各种各样的主题,但大部分都是围绕这Family发展的。速度激情系列为了Family可以不顾以前兄弟的生死选择对手做队友,甚至连魔兽这样的电影都要从一个兽人家庭作为一条线,不得不说,这的确是个容易打动人的方式。
Coco给我们描绘了一个这样的世界,人的身体死亡了会变成亡灵;亡灵依靠人的记忆存活,当没有人记起的时候,亡灵也死了。这和我们大部分理解的生死几乎是一致的表达,永远活在我们心中。

人物

整部片子主要有三个人物,米格,德拉库斯,埃克托。
米格,这部电影的线索人物,从人世间到亡灵世界,从coco到埃克托,米格就是一个充满阳光的精灵信使,有梦想,有活力,有是非心,有憎恶心,有恻隐心。
德拉库斯一开始作为正面人物出场,无数光环加身,人们心目中完美的艺术家,米格的偶像。影片中后段人物反转后,以为最后会再反转一次,将德拉库斯转变回来,结果证明想多了。
埃克托,感觉出场那段是个bug,讲道理埃克托作为老祖宗,即便伊梅尔达再强势,也不至于其他几个不认识他的地步吧?而且米格是家族的后人,那埃克托为什么也会认为米格是德拉库斯的后代呢?

翻译来源https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

简介

假设对于一个有限长度的数组序列(0, 3, 3, 5, 8),需要生成对应的所有全排列。有什么好的办法做到?

最原始的方案是使用自顶向下的递归方式。首先选举出第一个位置的元素,然后递归选择第二个元素从剩下的元素中,直到剩余一个元素。但是这种方法很复杂因为它需要递归、堆栈存储和去重。而且,如果坚持操作序列(不使用临时数组),那么这种方法在生成字典序排列的使用会有很大的困难。

最有效生成所有排列的方式是以字典序最小的开始,重复进行计算下一个排列。这个简单而又快速的算法将在本页进行阐述。我们将会使用具体的例子来解释算法的每一个步骤。

算法描述

序列(0, 1, 2, 5, 3, 3, 0)作为测试数据。

本算法的关键步骤是当我们计算生成下一个排列时,必须尽可能小的增加序列值。就像我们数数一样,我们总是尽可能的去修改最右侧(低位)的数据,保持左侧(高位)的数字不动一样。例如:从{0,1}到{0,2},完全不需要将第一个元素从0改到1,改动第二个元素将获得更小的增加。事实上,第二个元素也无需改动,这将是接下来要说明的。

首先,标记出最长的非升序后缀子串(微弱下降)。在例子中这个后缀子串就是(5, 3, 3, 0)。最长非升序后缀已经是后缀串所有排列中的最大排列了,所以不可能计算它的下一个组合,如果要获得下一个组合,就必须和左侧的元素作出交换。(标记最大非升序后缀字串可以在通过从右往左搜索在O(n)时间内完成,还有后缀至少含有一个元素,因为一个元素的子串是非升序的)。

第二步,取出后缀子串左侧紧邻的元素(本例子中是2)称之为pivot。(如果没有这个元素,那就说明整个字串是非升序的,那么这个字符串就是最大的子串了)。pivot 必须小于后缀子串的第一个元素(5),故后缀中存在部分元素大于pivot.当我们把pivot和后缀中的大于pivot的最小元素进行交换后,就得到了最小的目标前缀。(前缀就是序列中去掉后缀的部分)。在这个例子中,最终得到了前缀(0, 1, 3)和更新后的后缀(5, 3, 2, 0)。(如果后缀有多个可选项,那就要选择最右侧的选项,接下来进入下一步。)

最后,对后缀进行非降序排序,因为前一步已经增大了前缀,所有我们希望后缀尽可能的小。事实上,完全可以避免排序而是进行简单的倒置后缀,原因在于替换元素没有改变排序。这样就得到了序列(0, 1, 3, 0, 2, 3, 5)就是我们想要计算出的的下一个排列。

简明的数学描述:

找出最大的索引i 确保有array[i − 1] < array[i](如果不存在i,那说明序列已经是最大排列)

找出最大索引 j 使得 j ≥ i 同时 array[j] > array[i − 1]。

交换array[j] 和 array[i − 1]。

倒置以array[i]开头的后缀子串。

如果你真的读懂了这个算法,这里还有一个拓展练习:设计一个算法计算出前一个最大的字典序排列。

样例代码 (Java)

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
boolean nextPermutation(int[] array) {
// Find longest non-increasing suffix
int i = array.length - 1;
while (i > 0 && array[i - 1] >= array[i])
i--;
// Now i is the head index of the suffix

// Are we at the last permutation already?
if (i <= 0)
return false;

// Let array[i - 1] be the pivot
// Find rightmost element that exceeds the pivot
int j = array.length - 1;
while (array[j] <= array[i - 1])
j--;
// Now the value array[j] will become the new pivot
// Assertion: j >= i

// Swap the pivot with j
int temp = array[i - 1];
array[i - 1] = array[j];
array[j] = temp;

// Reverse the suffix
j = array.length - 1;
while (i < j) {
temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}

// Successfully computed the next permutation
return true;
}

这个代码可以按照你的理解机械翻译为其他的编程语言。(注意:在Java中,数组从0开始)。

再次声明翻译https://www.nayuki.io/page/next-lexicographical-permutation-algorithm

龙城飞将

0%