前言

当面对一个有 SQL 性能问题的数据库时，我们应该从何处入手来进行系统的分析，使得能够尽快定位问题 SQL 并尽快解决问题。

show status

通过 show status 命令了解各种 SQL 的执行频率。

MySQL 客户端连接成功后，通过 show[session|global] status 命令可以提供服务器状态信息，也可以在操作系统上使用 mysqladmin extended-status 命令获得这些消息。show[session|global] status 可以根据需要加上参数“session”或者“global”来显示 session 级（当前连接）的统计结果和 global 级（自数据库上次启动至今）的统计结果。如果不写，默认使用参数是“session”。

下面的命令显示了当前 session 中所有统计参数的值：

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

mysql> show status like 'Com_%';
+------------------------------+---------+
|  Variable_name               |  Value  |
+------------------------------+---------+
|  Com_admin_commands          |  0      |
|  Com_alter_db                |  0      |
|  Com_alter_event             |  0      |
|  Com_alter_table             |  0      |
|  Com_analyze                 |  0      |
|  Com_backup_table            |  0      |
|  Com_begin                   |  0      |
|  Com_change_db               |  1      |
|  Com_change_master           |  0      |
|  Com_check                   |  0      |
|  Com_checksum                |  0      |
|  Com_commit                  |  0      |
......

Com_xxx 表示每个 xxx 语句执行的次数，我们通常比较关心的是以下几个统计参数。

• Com_select：执行 SELECT 操作的次数，一次查询只累加 1。
• Com_insert：执行 INSERT 操作的次数，对于批量插入的 INSERT 操作，只累加一次。
• Com_update：执行 UPDATE 操作的次数。
• Com_delete：执行 DELETE 操作的次数。

上面这些参数对于所有存储引擎的表操作都会进行累计。下面这几个参数只是针对 InnoDB 存储引擎的，累加的算法也略有不同。

• Innodb_rows_read：执行 SELECT 操作查询返回的行数。
• Innodb_rows_inserted：执行 INSERT 操作插入的行数。
• Innodb_rows_updated：执行 UPDATE 操作更新的行数。
• Innodb_rows_deleted：执行 DELETE 操作删除的行数。

通过以上几个参数，可以很容易地了解当前数据库的应用是以插入更新为主还是以查询操作为主，以及各种类型的 SQL 大致的执行比例是多少。对于更新操作的计数，是对执行次数的计数，不论提交还是回滚都会进行累加。

对于事务型的应用，通过 Com_commit 和 Com_rollback 可以了解事务提交和回滚的情况，对于回滚操作非常频繁的数据库，可能意味着应用编写存在问题。

此外，以下几个参数便于用户了解数据库的基本情况。

• Connections：试图连接 MySQL 服务器的次数。
• Uptime：服务器工作时间。
• Slow_queries：慢查询的次数。

定位 SQL 语句

可以通过以下两种方式定位执行效率较低的 SQL 语句。

• 通过慢查询日志定位那些执行效率较低的 SQL 语句，用 --log-slow-queries[=file_name] 选项启动时，mysqld 写一个包含所有执行时间超过 long_query_time 秒的 SQL 语句的日志文件。
• 慢查询日志在查询结束以后才记录，所以在应用反映执行效率出现问题的时候查询慢查询日志并不能定位问题，可以使用 show processlist 命令查看当前 MySQL 在进行的线程，包括线程的状态、是否锁表等，可以实时地查看 SQL 的执行情况，同时对一些锁表操作进行优化。

EXPLAIN

通过 EXPLAIN 分析低效 SQL 的执行计划

通过以上步骤查询到效率低的 SQL 语句后，可以通过 EXPLAIN 或者 DESC 命令获取 MySQL 如何执行 SELECT 语句的信息，包括在 SELECT 语句执行过程中表如何连接和连接的顺序，比如想计算 2006 年所有公司的销售额，需要关联 sales 表和 company 表，并且对 moneys 字段做求和（sum）操作，相应 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

mysql> explain select sum(moneys) from sales a,company b where a.company_id = b.id and a.year = 2006\G;
    **************************** 1. row *************************************
                 id: 1
        select_type: SIMPLE
              table: a
               type: ALL
      possible_keys: NULL
                key: NULL
            key_len: NULL
                ref: NULL
               rows: 1000
              Extra: Using where
    **************************** 2. row *************************************
                 id: 1
        select_type: SIMPLE
              table: b
               type: ref
      possible_keys: ind_company_id
                key: ind_company_id
            key_len: 5
                ref: sakila.a.company_id
               rows: 1
              Extra: Using where; Using index
    2 rows in set (0.00 sec)

每个列的简单解释如下：

• select_type：表示 SELECT 的类型，常见的取值有 SIMPLE（简单表，即不使用表连接或者子查询）、PRIMARY（主查询，即外层的查询）、UNION（UNION 中的第二个或者后面的查询语句）、SUBQUERY（子查询中的第一个 SELECT）等。
• table：输出结果集的表。
• type：表示表的连接类型，性能由好到差的连接类型为 system（表中仅有一行，即常量表）、const（单表中最多有一个匹配行，例如 primary key 或者 unique index）、eq_ref（对于前面的每一行，在此表中只查询一条记录，简单来说，就是多表连接中使用 primary key 或者 unique index）、ref（与 eq_ref 类似，区别在于不是使用 primary key 或者 unique index，而是使用普通的索引）、ref_or_null（与 ref 类似，区别在于条件中包含对 NULL 的查询）、index_merge（索引合并优化）、unique_subquery（in 的后面是一个查询主键字段的子查询）、index_subquery（与 unique_subquery 类似，区别在于 in 的后面是查询非唯一索引字段的子查询）、range（单表中的范围查询）、index（对于前面的每一行，都通过查询索引来得到数据）、all（对于前面的每一行，都通过全表扫描来得到数据）。
• possible_keys：表示查询时，可能使用的索引。
• key：表示实际使用的索引。
• key_len：索引字段的长度。
• rows：扫描行的数量。
• Extra：执行情况的说明和描述。

确定问题并采取相应的优化措施

经过以上步骤，基本就可以确认问题出现的原因。此时可以根据情况采取相应的措施，进行优化提高执行的效率。

在上面的例子中，已经可以确认是对 a 表的全表扫描导致效率的不理想，那么对 a 表的 year 字段创建索引，具体如下：

1
2
3

mysql> create index ind_sales2_year on sales2(year);
Query OK,1000 rows affected(0.03 sec)
Records:1000 Duplicates: 0  Warnings: 0

创建索引后，再看一下这条语句的执行计划，具体如下：

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

mysql> explain select sum(moneys) from sales2 a,company2 b where a.company_id = b.id and a.year = 2006\G;
    **************************** 1. row *************************************
                 id: 1
        select_type: SIMPLE
              table: a
               type: ref
      possible_keys: ind_sales2_year
                key: ind_sales2_year
            key_len: 2
                ref: const
               rows: 1
              Extra: Using where
    **************************** 2. row *************************************
                 id: 1
        select_type: SIMPLE
              table: b
               type: ref
      possible_keys: ind_company_id
                key: ind_company_id
            key_len: 5
                ref: sakila.a.company_id
               rows: 1
              Extra: Using where; Using index
    2 rows in set (0.00 sec)

可以发现建立索引后对 a 表需要扫描的行数明显减少（从 1000 行减少到 1 行），可见索引的使用可以大大提高数据库的访问速度，尤其在表很庞大的时候这种优势更为明显。

本文大多摘自《深入浅出MySQL》。

前言

MySQL 从 5.0.3 开始支持分布式事务，当前分布式事务只支持 InnoDB 存储引擎。一个分布式事务会涉及多个行动，这些行动本身是事务性的。所有行动都必须一起成功完成，或者一起被回滚。

分布式事务的原理

在 MySQL 中，使用分布式事务的应用程序涉及一个或多个资源管理器和一个事务管理器。

• 资源管理器（RM）用于提供通向事务资源的途经。数据库服务器是一种资源管理器。该管理器必须可以提交或回滚由 RM 管理的事务。例如，多台 MySQL 数据库作为多台资源管理器或者几台 MySQL 服务器和几台 Oracle 服务器作为资源管理器。
• 事务管理器（TM）用于协调作为一个分布式事务一部分的事务。TM 与管理每个事务的 RMs 进行通讯。一个分布式事务中各个单个事务均是分布式事务的“分支事务”。分布式事务和各分支通过一种命名方法进行标识。

MySQL 执行 XA MySQL 时，MySQL 服务器相当于一个用于管理分布式事务中的 XA 事务的资源管理器。与 MySQL 服务器连接的客户端相当于事务管理器。

要执行一个分布式事务，必须知道这个分布式事务涉及到了哪些资源管理器，并且把每个资源管理器的事务执行到事务可以被提交或回滚时。根据每个资源管理器报告的有关执行情况的内容，这些分支事务必须作为一个原子性操作全部提交或回滚。要管理一个分布式事务，必须要考虑任何组件或连接网络可能会故障。

用于执行分布式事务的过程使用两阶段提交，发生时间在由分布式事务的各个分支需要进行的行动已经被执行之后。

• 在第一阶段，所有的分支被预备好。即它们被 TM 告知要准备提交。通常，这意味着用于管理分支的每个 RM 会记录对于被稳定保存的分支的行动。分支指示是否它们可以这么做。这些结果被用于第二阶段。
• 在第二阶段，TM 告知 RMs 是否要提交或回滚。如果在预备分支时，所有的分支指示它们将能够提交，则所有的分支被告知要提交。如果在预备时，有任何分支指示它将不能提交，则所有分支被告知回滚。

在有些情况下，一个分布式事务可能会使用一阶段提交。例如，当一个事务管理器发现，一个分布式事务只由一个事务资源组成（即单一分支），则该资源可以被告知同时进行预备和提交。

分布式事务的语法

分布式事务（XA 事务）的 SQL 语法主要包括：

XA {START|BEGIN} xid [JOIN|RESUME]

XA START xid 用于启动一个带给定 xid 值的 XA 事务。每个 XA 事务必须有一个唯一的 xid 值，因此该值当前不能被其他的 XA 事务使用。

xid 是一个 XA 事务标识符，用来唯一标识一个分布式事务。xid 值由客户端提供，或由 MySQL 服务器生成。xid 值包含 1~3 个部分：

xid: gtrid [, bqual [, formatID ]]

• gtrid 是一个分布式事务标识符，相同的分布式事务应该使用相同的 gtrid，这样可以明确知道 xa 事务属于哪个分布式事务。
• bqual 是一个分支限定符，默认值是空串。对于一个分布式事务中的每个分支事务，bqual 值必须是唯一的。
• formatID 是一个数字，用于标识由 gtrid 和 bqual 值使用的格式，默认值是 1。

下面其他 XA 语法中用到的 xid 值，都必须和 START 操作使用的 xid 值相同，也就是表示对这个启动的 XA 事务进行操作。

1
2

XA END xid [SUSPEND [FOR MIGRATE]]
XA PREPARE xid

使事务进入 PREPARE 状态，也就是两阶段提交的第一个提交阶段。

1
2

XA COMMIT xid [ONE PHASE]
XA ROLLBACK xid

这两个命令用来提交或者回滚具体的分支事务。也就是两阶段提交的第二个提交阶段，分支事务被实际的提交或者回滚。

1

XA RECOVER  返回当前数据库中处于 PREPARE 状态的分支事务的详细信息。

分布式的关键在于如何确保分布式事务的完整性，以及在某个分支出现问题时的故障解决。XA 的相关命令就是提供给应用如何在多个独立的数据库之间进行分布式事务的管理，包括启动一个分支事务、使事务进入准备阶段以及事务的实际提交回滚操作等，如下所示的例子演示了一个简单的分布式事务的执行，事务的内容是在 DB1 中插入一条记录，同时在 DB2 中更新一条记录，两个操作作为同一事务提交或者回滚。

↓↓分布式事务例子↓↓

存在的问题

虽然 MySQL 支持分布式事务，但是在测试过程中，还是发现存在一些问题。

如果分支事务在达到 prepare 状态时，数据库异常重新启动，服务器重新启动以后，可以继续对分支事务进行提交或者回滚的操作，但是提交的事务没有写 binlog，存在一定的隐患，可能导致使用 binlog 恢复丢失部分数据。如果存在复制的数据库，则有可能导致主从数据库的数据不一致。

如果分支事务的客户端连接异常中止，那么数据库会自动回滚未完成的分支事务，如果此时分支事务已经执行到 prepare 状态，那么这个分布式事务的其他分支可能已经成功提交，如果这个分支回滚，可能导致分布式事务的不完整，丢失部分分支事务的内容。

如果分支事务在执行到 prepare 状态时，数据库异常，且不能再正常启动，需要使用备份和 binlog 来恢复数据，那么那些在 prepare 状态的分支事务因为并没有记录到 binlog，所以不能通过 binlog 进行恢复，在数据库恢复后，将丢失这部分的数据。

总结

MySQL 的分布式事务还存在比较严重的缺陷，在数据库或者应用异常的情况下，可能会导致分布式事务的不完整。如果应用对于数据的完整性要求不是很高，则可以考虑使用。如果应用对事务的完整性有比较高的要求，则不太推荐使用分布式事务。

以上大多摘自《深入浅出MySQL》

前言

和大多数数据库不同，MySQL 中有一个存储引擎的概念，针对不同的存储需求可以选择最优的存储引擎。

概述

插件式存储引擎是 MySQL 数据库最重要的特性之一，用户可以根据应用的需要选择如何存储和索引数据、是否使用事务等。MySQL 默认支持多种存储引擎，以适用于不同领域的数据库应用需要，用户可以通过选择使用不同的存储引擎提高应用的效率，提供灵活的存储，用户甚至可以按照自己的需要定制和使用自己的存储引擎，以实现最大程度的可定制性。

MySQL 5.0 支持的存储引擎包括 MyISAM、InnoDB、BDB、MEMORY、MERGE、EXAMPLE、NDB Cluster、ARCHIVE、CSV、BLACKHOLE、FEDERATED 等，其中 InnoDB 和 BDB 提供事务安全表，其它存储引擎都是非事务安全表。

特性

下面列出几种常见的存储引擎，并对比之间的区别。

本文重点介绍最常遇到的两种存储引擎：MyISAM 和 InnoDB。

MyISAM

MyISAM 是 MySQL 的默认存储引擎。MyISAM 不支持事务、也不支持外键，其优势是访问的速度快，对事务完整性没有要求或者以 SELECT、INSERT 为主的应用基本上都可以使用这个引擎来创建表。

每个 MyISAM 在磁盘上存储成 3 个文件，其文件名都和表名相同，但扩展名分别是：

• .frm（存储表定义）
• .MYD（MYData，存储数据）
• .MYI（MYIndex，存储索引）

数据文件和索引文件可以放置在不同的目录，平均分布 IO，获得更快的速度。

MyISAM 类型的表可能会损坏，原因可能是多种多样的，损坏后的表可能不能访问，会提示需要修复或者访问后返回错误的结果。MyISAM 类型的表提供修复的工具，可以用 CHECK TABLE 语句来检查 MyISAM 表的健康，并用 REPAIR TABLE 语句修复一个损坏的 MyISAM 表。表损坏可能导致数据库异常重新启动，需要尽快修复并尽可能地确认损坏的原因。

MyISAM 的表又支持 3 种不同的存储格式，分别是：

• 静态（固定长度）表
• 动态表
• 压缩表

其中，静态表是默认的存储格式。静态表中的字段都是非变长字段，这样每个记录都是固定长度的，这种存储方式的优点是存储非常迅速，容易缓存，出现故障容易恢复；缺点是占用的空间通常比动态表多。静态表的数据在存储的时候会按照列的宽度定义补足空格，但是在应用访问的时候并不会得到这些空格，这些空格在返回给应用之前已经去掉。

InnoDB

InnoDB 存储引擎提供了具有提交、回滚和崩溃恢复能力的事务安全。但是对比 MyISAM 的存储引擎，InnoDB 写的处理效率差一些并且会占用更多的磁盘空间以保留数据和索引。

自动增长列

InnoDB 表的自动增长列可以手工插入，但是插入的值如果是空或者 0，则实际插入的将是自动增长后的值。

可以通过 ALTER TABLE *** AUTO_INCREMENT = n 语句强制设置自动增长列的初始值，默认从 1 开始，但是该强制的默认值是保留在内存中的，如果该值在使用之前数据库重新启动，那么这个强制的默认值就会丢失，就需要在数据库启动以后重新设置。

可以使用 LAST_INSERT_ID() 查询当前线程最后插入记录使用的值。如果一次插入了多条记录，那么返回的是第一条记录使用的自动增长值。

对于 InnoDB 表，自动增长列必须是索引。如果是组合索引，也必须是组合索引的第一列，但是对于 MyISAM 表，自动增长列可以是组合索引的其它列，这样插入记录后，自动增长列是按照组合索引的前面几列进行排序后递增的。

外键约束

MySQL 支持外键的存储引擎只有 InnoDB，在创建外键的时候，要求父表必须有对应的索引，子表在创建外键的时候也会自动创建对应的索引。

在创建索引的时候，可以指定在删除、更新父表时，对子表进行的相应操作，包括 RESTRICT、CASCADE、SET NULL 和 NO ACTION。其中 RESTRICT 和 NO ACTION 相同，是指限制在子表有关联记录的情况下父表不能更新；CASCADE 表示父表在更新或者删除时，更新或者删除子表对应记录；SET NULL 则表示父表在更新或者删除的时候，子表的对应字段被 SET NULL。选择后两种方式的时候要谨慎，可能会因为错误的操作导致数据的丢失。

当某个表被其他表创建了外键参照，那么该表的对应索引或者主键禁止被删除。

存储方式

InnoDB 存储表和索引有以下两种方式。

• 使用共享表空间存储，这种方式创建的表的表结构保存在 .frm 文件中，数据和索引保存在 innodb_data_home_dir 和 innodb_data_file_path 定义的表空间中，可以是多个文件。
• 使用多表空间存储，这种方式创建的表的表结构仍然保存在 .frm 文件中，但是每个表的数据和索引单独保存在 .ibd 中。如果是个分区表，则每个分区对应单独的 .ibd 文件，文件名是“表名+分区名”，可以在创建分区的时候指定每个分区的数据文件的位置，以此来将表的 IO 均匀分布在多个磁盘上。

要使用多表空间的存储方式，需要设置参数 innodb_file_per_table，并重新启动服务后才可以生效，对于新建的表按照多表空间的方式创建，已有的表仍然使用共享表空间存储。如果将已有的多表空间方式修改回共享表空间的方式，则新建表会在共享表空间中创建，但已有的多表空间的表仍然保存原来的访问方式。所以多表空间的参数生效后，只对新建的表生效。

多表空间的数据文件没有大小限制，不需要设置初始大小，也不需要设置文件的最大限制、扩展大小等参数。

对于使用多表空间特性的表，可以比较方便地进行单表备份和恢复操作，但是直接复制 .ibd 文件是不行的，因为没有共享表空间的数据字典信息，直接复制的 .ibd 文件和 .frm 文件恢复时是不能被正确识别的，但可以通过以下命令：

1
2

ALTER TABLE tbl_name DISCARD TABLESPACE;
ALTER TABLE tbl_name IMPORT TABLESPACE;

将备份恢复到数据库中，但是这样的单表备份，只能恢复到表原来在的数据库中，而不能恢复到其他的数据库中。如果要将单表恢复到目标数据库，则需要通过 mysqldump 和 mysqlimport 来实现。

注意：即便在多表空间的存储方式下，共享表空间仍然是必须的，InnoDB 把内部数据词典和工作日志放在这个文件中。

适用环境

在选择存储引擎时，应根据应用特点选择合适的存储引擎，对于复杂的应用系统可以根据实际情况选择多种存储引擎进行组合。

• MyISAM：默认的 MySQL 插件式存储引擎。如果应用是以读操作和插入操作为主，只有很少的更新和删除操作，并且对事务的完整性、并发性要求不是很高，那么选择这个存储引擎是非常适合的。MyISAM 是在 Web、数据仓储和其他应用环境下最常使用的存储引擎之一。
• InnoDB：用于事务处理应用程序，支持外键。如果应用对事务的完整性有比较高的要求，在并发条件下要求数据的一致性，数据操作除了插入和查询以外，还包括很多的更新、删除操作，那么 InnoDB 存储引擎应该是比较合适的选择。InnoDB 存储引擎除了有效地降低由于删除和更新导致的锁定，还可以确保事务的完整提交（Commit）和回滚（Rollback），对于类似计费系统或者财务系统等对数据准确性要求比较高的系统，InnoDB 都是合适的选择。

本文大多摘自《深入浅出MySQL》。

年前一个月，怎么能不跳动？

各大厂爆料不断，裁员信号到处闪烁，人心惶惶。

看到最多的一句话是：2019，保住饭碗！

裁团风波此起彼伏，有赞年会公然宣布 996，便利蜂裁员新招层出不穷，新东方的释放自我，微信、陌陌的令人羡慕……

据说 2018 是未来五年经济最好的一年，呜呼哀哉！

这是一个危机四伏的时代，同样也是一个充满机遇的时代，市场的一番大清洗将会把未来带向何处呢？

还是要保持自身的竞争力，技多不压身，仗技走天涯，学习思考不能断！

另外，保持健康最重要！2019 还是要坚持锻炼，自律。

我是 2018 年 3 月底来到现在这家公司的，也快满一年了。

很荣幸，被评为了 2018 年度最佳新人奖，也作为其中之一主持人主持了 2018 年的公司年会。

想想距离之前在大学做主持，已经过去了 5 年了，真是好快啊！

意料之中，抽奖无缘。一张来伊份购物卡，阳光普照。

年会结束跟同事又聚了下，说了不少东西。赚钱真不容易啊！

2019 年，毕业就快 2 年了，现在还是没有攒什么钱，对比别人真的感觉好失败。

打工没什么激情，创业没那个勇气，好难啊。

前段时间去看了场直火帮的现场，都市的夜晚是年轻人的狂欢。

白日里压抑的所有情绪都在夜晚爆发，肆意尖叫。

现场还是很不一样的，音乐鼓点直击心脏，就像是个泵在血海中抽放。

适当调节生活也是相当不错的。

在这里我要说说《大江大河》这部电视剧，真的很不错！

那几天一有空就看，晚上下班早早地就洗漱好躲被窝里看，本来被子就薄，还漏一个大口子，甚是好看甚是好看。

短短的电视剧中反映了很多东西，我真的是喜欢这类的作品。

例如：路遥《平凡的世界》，陈忠实《白鹿原》，余华《活着》、《兄弟》等作品。

现在怕是出不了这类大作了，时代不同了。

再过几天就回家过春节了，说到过年也是不怎么提得起兴致啊。

跟个国庆一样，回家呆一周就又得回来过上班日子了。

“回家就跟回娘家一样”难怪我爸如是说道……

谁想呢，我也不想啊，好难啊。

长大了，好多事情就自然而然变了。

小时候的过年总是伴着地上厚厚的积雪，一捆烟花棒，一盒火柴或是口袋里塞着个黑口打火机。

不一样咯。

最后，一段《站在悬崖边的我》

我站在悬崖边，视线慢慢下移
只看见一片山，飘着那一层云
都说居高思危，我却有点神往

那是一张床垫，还是一张薄纸
那下面是什么，是那汪洋大海
还是坚硬的沙石，血肉模糊

天色越来越暗，回去的路越来越糊
我站在悬崖边，开始犹豫

前方需要勇气，可能粉身碎骨
后方道路平坦，也许一世平庸

左右思索着，天却已经全黑了
我伸手，看不清楚自己的手指
一阵眩晕，脚下一滑，身体前倾

我还没来得及惊呼
眼睛就睁开了

站在悬崖边的我

全排列问题在这里有两个版本，其中略有差异。看完就会感觉似曾相识，一种莫名的熟悉感从心底喷涌上来。

第一个版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
  [1,2,3],
  [1,3,2],
  [2,1,3],
  [2,3,1],
  [3,1,2],
  [3,2,1]
]

有什么感觉？

这不就是暗箱摸球，箱子里有不同颜色的球 n 个，列出你可能会摸出球的所有顺序，不放回。

先贴上大神的详细解析：链接

利用 List.add(int index, E element) 方法可以将元素插入指定的位置，可以满足题意。

整体分析：根据可插入的地方不同从而展开不同的分支，典型的树形结构。

代码如下：

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

public List<List<Integer>> permute(int[] nums) {

    List<List<Integer>> permutations = new ArrayList<>();
    if (nums.length == 0)
        return permutations;
    helper(nums, 0, new ArrayList<>(), permutations);
    return permutations;

}

/**
 * 
 * @param nums
 *            原数组
 * @param start
 *            选择填充数字下标
 * @param permutation
 *            单个集合
 * @param permutations
 *            目标返回集合
 */
private void helper(int[] nums, int start, List<Integer> permutation, List<List<Integer>> permutations) {

    // 满足条件添加 返回
    if (permutation.size() == nums.length) {
        permutations.add(permutation);
        return;
    }
    // 分别插入不同的位置
    for (int i = 0; i <= permutation.size(); i++) {
        // 避免在原集合上操作 需新集合
        List<Integer> newPermutation = new ArrayList<>(permutation);
        newPermutation.add(i, nums[start]);
        helper(nums, start + 1, newPermutation, permutations);
    }
}

注意每次插入前要 new 一个新集合对象，不能在原集合对象上操作。

第二个版本：

1
2
3
4
5
6
7
8
9
10
11

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

与第一个版本区别是：该版本数组中可以有重复元素，且返回的集合中不能有重复的元素（即重复的集合排列顺序）。

去重，我首先想到的是这样：不管你序列中有没有重复的数字，我就当满足条件的时候判断下是否已经存过了该排列顺序不就行了。

然后我就将使用过的数字全都按顺序拼接成字符串，too young …

指定位置插入元素，List 很好实现，可是 String 怎么办。方法肯定有啊，比如每个元素之间用自定义分隔符拼接，再转成数组找到指定的位置插入，再转。只要功夫深，铁杵磨成针。可是麻烦啊，算暴力解法，遂弃之。

解题代码如下：

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

public List<List<Integer>> permuteUnique(int[] nums) {
    List<List<Integer>> permuteUniques = new ArrayList<>();
    if (nums == null || nums.length == 0)
        return permuteUniques;
    // 要去重 先排序
    Arrays.sort(nums);
    boolean[] used = new boolean[nums.length];
    dfs(nums, used, permuteUniques, new ArrayList<>());
    return permuteUniques;
}

/**
 * 
 * @param nums
 *            原数组
 * @param used
 *            标记数字使用状态
 * @param permuteUniques
 *            目标集合
 * @param permuteUnique
 *            单个集合
 */
private void dfs(int[] nums, boolean[] used, List<List<Integer>> permuteUniques, List<Integer> permuteUnique) {
    if (permuteUnique.size() == nums.length) {
        permuteUniques.add(new ArrayList<>(permuteUnique));
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) // 已经标记过的略过
            continue;
        // 数字有重复的 说明刚释放的值与该值一样 略过
        if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1])
            continue;
        used[i] = true; // 标记使用
        permuteUnique.add(nums[i]); // 该数字加入集合
        // 重复操作 选择剩余数字
        dfs(nums, used, permuteUniques, permuteUnique);
        // 当出栈时将最后一个数从集合中删除 同时该数恢复未使用状态 继续操作
        used[i] = false;
        permuteUnique.remove(permuteUnique.size() - 1);
    }

}

由于要去重，所以先将数组排序。与第一版本的大致思路一样，遍历数组将未标记的值插入。

1
2

if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) // 数字有重复的 说明刚释放的值与该值一样 略过
    continue;

这行代码至关重要，与出栈时候的 used[i] = false; 相对应，实现了重复操作不执行的功能。

同样，permuteUniques.add(new ArrayList<>(permuteUnique)); 也是需要 new 一个新对象塞入。

想直接要源码的，点这里。

简介

Sharding-JDBC 定位为轻量级 Java 框架，在 Java 的 JDBC 层提供的额外服务。 它使用客户端直连数据库，以 jar 包形式提供服务，无需额外部署和依赖，可理解为增强版的 JDBC 驱动，完全兼容 JDBC 和各种 ORM 框架。

• 适用于任何基于 Java 的 ORM 框架，如：JPA, Hibernate, Mybatis, Spring JDBC Template 或直接使用 JDBC
• 基于任何第三方的数据库连接池，如：DBCP, C3P0, BoneCP, Druid, HikariCP 等
• 支持任意实现JDBC规范的数据库。目前支持 MySQL，Oracle，SQLServer 和 PostgreSQL

前言

本例只是简单实现了 Sharding-JDBC 中的读写分离功能，请注意。

所用到的技术栈及版本：

• SpringBoot 2.0.4
  • Spring Data JPA
  • HikariDataSource
  • Gson 2.8.5
  • lombok 1.16.22
  • mysql-connector-java 5.1.46
• sharding-jdbc-core 2.0.3

主要部分

配置文件：application.yml

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

# JPA
spring:
  jpa:
    show-sql: true
    database-platform: org.hibernate.dialect.MySQL5InnoDBDialect
    hibernate:
      ddl-auto: create

# Server
server:
  port: 8888

# Sharding JDBC
sharding:
  jdbc:
    data-sources:
      ds_master:
        type: com.zaxxer.hikari.HikariDataSource
        driver-class-name: com.mysql.jdbc.Driver
        jdbc-url: jdbc:mysql://localhost:3306/master?characterEncoding=utf8&useSSL=false
        username: root
        password: root
      ds_slave:
        type: com.zaxxer.hikari.HikariDataSource
        driver-class-name: com.mysql.jdbc.Driver
        jdbc-url: jdbc:mysql://localhost:3306/slave?characterEncoding=utf8&useSSL=false
        username: root
        password: root
    master-slave-rule:
      name: ds_ms
      master-data-source-name: ds_master
      slave-data-source-names: ds_slave
      load-balance-algorithm-type: round-robin

这里用的是 springboot2.0 默认的数据库连接池 HikariDataSource

• load-balance-algorithm-type：
  查询时的负载均衡算法，目前有2种算法，round_robin（轮询）和random（随机）
• master-data-source-name： 主数据源名称
• slave-data-source-names： 从数据源名称 多个用逗号隔开

存放数据源数据：ShardingMasterSlaveConfig.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

package com.example.shardingjdbc.config;

import java.util.HashMap;
import java.util.Map;

import org.springframework.boot.context.properties.ConfigurationProperties;

import com.zaxxer.hikari.HikariDataSource;

import io.shardingjdbc.core.api.config.MasterSlaveRuleConfiguration;
import lombok.Data;

/**
 * 存放数据源
 * 
 * @author ffj
 *
 */
@Data
@ConfigurationProperties(prefix = "sharding.jdbc")
public class ShardingMasterSlaveConfig {

    private Map<String, HikariDataSource> dataSources = new HashMap<>();

    private MasterSlaveRuleConfiguration masterSlaveRule;
}

用了 Lombok 显得简便了些

配置数据源：ShardingDataSourceConfig.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
59
60
61
62
63
64
65

package com.example.shardingjdbc.config;

import java.sql.SQLException;
import java.util.HashMap;
import java.util.Map;

import javax.sql.DataSource;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.boot.autoconfigure.condition.ConditionalOnProperty;
import org.springframework.boot.context.properties.EnableConfigurationProperties;
import org.springframework.context.annotation.Bean;
import org.springframework.context.annotation.Configuration;

import com.zaxxer.hikari.HikariDataSource;

import io.shardingjdbc.core.api.MasterSlaveDataSourceFactory;

/**
 * 配置数据源详细信息
 * 
 * @author ffj
 *
 */
@Configuration
@EnableConfigurationProperties(ShardingMasterSlaveConfig.class)
@ConditionalOnProperty({ "sharding.jdbc.data-sources.ds_master.jdbc-url",
        "sharding.jdbc.master-slave-rule.master-data-source-name" })
public class ShardingDataSourceConfig {

    private static final Logger log = LoggerFactory.getLogger(ShardingDataSourceConfig.class);

    @Autowired(required = false)
    private ShardingMasterSlaveConfig shardingMasterSlaveConfig;

    /**
     * 配置数据源
     * 
     * @return
     * @throws SQLException
     */
    @Bean("dataSource")
    public DataSource masterSlaveDataSource() throws SQLException {
        shardingMasterSlaveConfig.getDataSources().forEach((k, v) -> configDataSource(v));
        Map<String, DataSource> dataSourceMap = new HashMap<>();
        dataSourceMap.putAll(shardingMasterSlaveConfig.getDataSources());
        DataSource dataSource = MasterSlaveDataSourceFactory.createDataSource(dataSourceMap,
                shardingMasterSlaveConfig.getMasterSlaveRule(), new HashMap<>());
        log.info("masterSlaveDataSource config complete！！");
        return dataSource;
    }

    /**
     * 可添加数据源一些配置信息
     * 
     * @param dataSource
     */
    private void configDataSource(HikariDataSource dataSource) {
        dataSource.setMaximumPoolSize(20);
        dataSource.setMinimumIdle(5);
    }
}

主要的配置内容就是这些了，接下来我们编写几个方法来测试。

测试

• 先创建一个实体类

大众测试实体类，我选 UserEntity:

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

package com.example.shardingjdbc.entity;

import java.io.Serializable;

import javax.persistence.Column;
import javax.persistence.Entity;
import javax.persistence.Id;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * 测试用户类
 * 
 * @author ffj
 *
 */
@AllArgsConstructor
@NoArgsConstructor
@Data
@Entity(name = "user")
public class UserEntity implements Serializable {

    /**
     * 
     */
    private static final long serialVersionUID = -6171110531081112401L;
    @Id
    private int id;
    @Column(length = 32)
    private String name;
    @Column(length = 16)
    private int age;

}

同样，Lombok 不可少。由于之前 application.yml 中 ddl-auto 设置的是 create，所以每次重启程序都会重新生成空表。

• 我选择 JPA 的原因就是它作为简单测试最适合不过了

  1 2 3 4 5 6 7 8 9 10

  package com.example.shardingjdbc.repository; import org.springframework.data.jpa.repository.JpaRepository; import com.example.shardingjdbc.entity.UserEntity; public interface UserRepository extends JpaRepository<UserEntity, Integer> { }

  只要继承 JpaRepository 就可以了，我们只需要使用它的基本方法即可。

• 写个 Controller 类

  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

  package com.example.shardingjdbc.controller; import java.util.List; import javax.annotation.Resource; import org.springframework.web.bind.annotation.PostMapping; import org.springframework.web.bind.annotation.RestController; import com.example.shardingjdbc.entity.UserEntity; import com.example.shardingjdbc.service.UserService; import com.google.gson.Gson; /** * 用户测试类 * * @author ffj * */ @RestController public class UserController { @Resource private UserService userService; @PostMapping("/save") public String saveUser() { UserEntity user = new UserEntity(1, "张三", 22); userService.saveUser(user); return "success"; } @PostMapping("/getUser") public String getUsers() { List<UserEntity> users = userService.getUsers(); return new Gson().toJson(users); } }

  Service 就不贴了，就是简单调用。

方便查看测试结果，这里用 Gson 来转化为 Json 输出。

• 启动程序

从上到下看启动日志：

1
2
3
4
5

2018-12-27 15:16:12.907  INFO 2940 --- [           main] com.zaxxer.hikari.HikariDataSource       : HikariPool-1 - Starting...
2018-12-27 15:16:13.132  INFO 2940 --- [           main] com.zaxxer.hikari.HikariDataSource       : HikariPool-1 - Start completed.
2018-12-27 15:16:13.141  INFO 2940 --- [           main] com.zaxxer.hikari.HikariDataSource       : HikariPool-2 - Starting...
2018-12-27 15:16:13.147  INFO 2940 --- [           main] com.zaxxer.hikari.HikariDataSource       : HikariPool-2 - Start completed.
2018-12-27 15:16:13.148  INFO 2940 --- [           main] c.e.s.config.ShardingDataSourceConfig    : masterSlaveDataSource config complete

可以看出有两个数据源，没毛病。

1
2

Hibernate: drop table if exists user
Hibernate: create table user (id integer not null, age integer, name varchar(32), primary key (id)) engine=InnoDB

程序启动 user 表重建，没毛病。

1
2
3
4
5

2018-12-27 15:16:15.198  INFO 2940 --- [           main] o.s.w.s.handler.SimpleUrlHandlerMapping  : Mapped URL path [/**] onto handler of type [class org.springframework.web.servlet.resource.ResourceHttpRequestHandler]
2018-12-27 15:16:15.550  INFO 2940 --- [           main] o.s.j.e.a.AnnotationMBeanExporter        : Registering beans for JMX exposure on startup
2018-12-27 15:16:15.587  INFO 2940 --- [           main] o.s.b.w.embedded.tomcat.TomcatWebServer  : Tomcat started on port(s): 8888 (http) with context path ''
2018-12-27 15:16:15.591  INFO 2940 --- [           main] c.e.s.ShardingJdbcApplication            : Started ShardingJdbcApplication in 5.36 seconds (JVM running for 5.725)
2018-12-27 15:16:15.592  INFO 2940 --- [           main] c.e.s.ShardingJdbcApplication            : ----------启动成功----------

端口为配置文件中指定的 8888，启动成功日志打印，也没毛病，成功。

注意：启动程序前别忘了先自行创建数据库！

现在我们在 slave 库中执行以下提供的 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
32

/*
Navicat MySQL Data Transfer

Source Server         : localhost
Source Server Version : 50720
Source Host           : localhost:3306
Source Database       : slave

Target Server Type    : MYSQL
Target Server Version : 50720
File Encoding         : 65001

Date: 2018-12-27 16:23:00
*/

SET FOREIGN_KEY_CHECKS=0;

-- ----------------------------
-- Table structure for user
-- ----------------------------
DROP TABLE IF EXISTS `user`;
CREATE TABLE `user` (
  `id` int(11) NOT NULL,
  `age` int(11) DEFAULT NULL,
  `name` varchar(32) DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

-- ----------------------------
-- Records of user
-- ----------------------------
INSERT INTO `user` VALUES ('2', '23', '李四');

好了，从库中表和数据都有了，进入正题。

• 测试主库插入数据
  我用的是 Postman ：选择 POST 方式，url：localhost:8888/save，点击 Send。

  1	Hibernate: insert into user (age, name, id) values (?, ?, ?) // 打印出这条日志

  返回 success，成功执行。查看主数据库中 user 表数据，确实插入，成功！

• 测试从库查询数据
  还是 Postman ：选择 POST 方式，url：localhost:8888/getUser，点击 Send。

  1	Hibernate: select userentity0_.id as id1_0_, userentity0_.age as age2_0_, userentity0_.name as name3_0_ from user userentity0_ // 打印出这条日志

  返回： [{"id":2,"name":"李四","age":23}]，数据正确，成功！

以上就是 SpringBoot2.0 + ShardingJDBC 实现数据库读写分离的全部内容了。

参考博文

• springboot2.0中用sharding-jdbc实现读写分离，集成Druid
• Spring Boot中整合Sharding-JDBC读写分离示例

你好，依旧 此篇作为对 2018 的整年回顾

尾巴，走了；你好，依旧。

2018 的尾巴已经来到，也是到了时候该让她的尾巴跟头部围成一个圈圈了。

2018，看过几场电影，吃过几场温馨的饭，睡过几场懒觉，看过几次凌晨的星空。

2018，分过一次手，游过几次怪味的泳，红过几次眼，回过不超五次的家。

2018，我重新拾起了运动，不为别的，只为自己能够多活两年。

2018，我重新调整了饮食，却始终调不过来作息。

2018，我看了好多书，有科幻代表《三体》，有经典散文集《自在独行》，有轻描淡写一生历程的《浮生六记》，也有极具讽刺的《兄弟》等等。当然，专业书籍也不能拉下。我自知是个爱书之人，我爱看书与爱看电影是一回事，都是喜欢故事，喜欢在这些源于生活中而来的作品之间，有所感悟，体会情愫。我想，这与我善于思考，善于总结，有些许相关吧。最近在看《城南旧事》。

今年 3 月，我换了份工作，因此也搬了个新的住处。很幸运，两位室友人很不错，还都是个硕士生，与优秀的人一同来往，谁人不喜欢呢？期间我还买了个方形玻璃缸，作为我那鳄龟的新住处（去年 8 月份买的两只苗子，现在只剩一只，长得倍儿快！有时间我可再另开一篇来专门絮叨絮叨）。后觉着这么个大缸就供着个龟大爷，浪费至极。于是我之后又陆陆续续往里丢过虾（包含着龙虾）、泥鳅，可几日后往往就不见其踪影，只有可怜的残骸在水中无目的晃荡。我不甘心，10 月份左右又进购了一批草金苗，大约五六十只。直到今日，12 月中旬，还剩下 7 只幸运儿，不知是否因为这气温影响了龟爷，还是幸运儿的过人闪躲之处，或是他们惺惺相惜，已成为了朋友？我不得知，我只知三天两头给它喂食鸡肉，应该是饿不着它的吧。话说幸运儿草金们，其中有两三条我甚是得意，身上条纹十分漂亮，尾巴又大又长，要是最终也遭遇不幸，我怕是会难过会后悔吧。可是，住所实在是小，我还能做些什么呢？我喜欢各种宠物，本想养猫养狗，一想处境，我便立刻就会打消这种不实际的念头，这也是我选择养龟的原因吧。

由于换了份工作，该司并非互联网公司，工作强度自然也没有那么大。也正是因为如此，我有了更多的时间能做我自己喜欢做的事情，就比如看书，跑步。独处的日子，看书是最好的项目了。晚上我也有了时间自己随意煮煮蔬菜，煮煮鸡胸，煮煮面条，健康又便宜，因此还与菜场的大爷变得熟知。虽然这种生活长期也不错，但是我是知道的，我是不愿意的。在这段时间里，我有了时间可以巩固基础，有了时间可以学习其他的东西，有了时间可以将之前未完全消化的东西一一吸干。我并没忘给自己充电，虽然也看了不少非专业书籍，但是那也是必要的，那些充实了我的灵魂，渐渐造就了我的气质，每每读完一本书我都有所收获。厚积而薄发，我一直在等待它的到来！

我在以前的随记中写过：时间往往在你回顾的时候，才会觉得过得好快。我也写过：原来我早已习惯了孤独，只是在孤独的岁月之中穿插了一段不那么孤独的时光，使我暂忘孤独。一个人的时候，往往会思考更多。虽说人类是群居动物，但是现在正慢慢走向独居世界，与外界网络相连即可。人们经常会畅想未来，畅想未来会变得多么科幻多么神奇多么智能，无可厚非，因为过去几年我们确实是发展可谓“神速”。但是我在想，过去是因为西方的互联网本就比中国发展要快，所以中国可以借鉴西方来避坑，从而快速发展。而如今，中国互联网已是首屈一指，无从可借鉴，只能我们自己一步一脚印来创新推进。畅想固然是好，人们也都想时代发展越快越好，可是我个人觉得还是不能太过于“妄想”，没必要过于急躁，就怕大家都在畅想美好未来的时候，天突然就塌了。当然，这也是我个人想法，磨刀不误砍柴工，美好生活人人都想，前提还是应脚踏实地。

也是在今年，租了服务器，重新注册了域名，搭建了自己的个人博客，开始了持续的记录总结。简书却是我最近才注册的，不为别的，我只想把一些生活感悟、牢骚，在这记录，也只会记录这些。从今年开始，每月我在自己博客都会写上一篇月结记录，初衷是为了让自己觉得过得不会那么虚空，同样更重要的是为了记录我的岁月。为了这些宝贵资料不丢失，我也做了备份。曾经，年少气盛的我丢失过许多美好记忆的书信，使得现在我都后悔不已，这些都是属于我们独一无二的财富。生活无远虑，只有近忧。不管如何，我们都要学会记录生活，也许也许，终有一日我也会有个幸福的家庭，子孙后辈也会静静坐在身边听一个糟老头子讲述他的过往。

犹记得去年 12 月底与朋友们欢聚苏州，共游园林。今年怕是没有机会了，前几日刚好去杭州出差，两位好友在杭州做事，便约出来一同吃了顿饭。这顿饭，我们吃了半小时，等了却将近两小时。那几日刚好是今年雪下得最大的日子，又正值周末，饭点，想想也难免。吃完后各自回府，下了地铁我本想打车，无奈道路积雪严重，天气恶劣。于是在等了十几分钟出租车后，我撑着小黑伞，踩着雪地，走了两三公里回到了宾馆，小黑伞已早成了小白伞了。距离毕业已过去了一年有余，大家身上也都多了一丝成熟稳重，几日前我还翻了下毕业相册，嗯，变化大倒是不大，就是头发好像都少了一些！

2018，我放慢了工作节奏，给了自己更多的时间去回顾，去务实基础，博观约取，厚积薄发！

2018，我同时也加强了锻炼，没有一个好身体将来又怎么能够撑得起一番事业！

2018，是积累的一年，寒冬虽冷，却总有见到明媚一天的啊！

你好，19！

住在对面的居民，我想与我这边环境也相似，只是人口数量略有差异。

有段时间，每晚下班我进房间打开房灯，第一件事就是站在窗外静静的看着对面的居民们。因为是老式小区，楼层不高，每栋之间的间隔也不大，看不清对面的模样但至少看得清对面的举动。

住在对面的居民，每户人家做的事皆不相同，作息时间皆不相同，窗外布置也是皆不相同。有时我就呆呆的站在那看，不知为什么，我就是能呆呆的站在那看。

住在对面的居民，能看见内部情况的户数不多，却给我有种人生百态的感觉。我想这也是吸引我的原因，是我在此执笔想要记录的原因吧。

住在对面楼斜上角的住户，是一家三口。看不清他们具体模样，只是知道小孩还小，还不会走路。往往见到他们都是在轮流抱着孩子，哄着睡觉，经常就是一哄一两个小时。当小孩入睡后，夫妻俩才开始走到厨房，不知是洗吃完饭后的碗筷还是才开始动手做饭。

住在夫妻俩下两层的是一位好学之人，对其的了解甚少，因为当我驻窗前“偷窥”时，他八成是坐在桌前，也只有桌前那扇窗没拉窗帘。由于晚上视线昏暗加之一定的观察距离，我只知他是位男性，大多独自一人坐在桌前，看书或是写字，我便看不大清了。纵上观之，好学之人，那是定错不了的了。

住在正对面楼偏上一点的是一个大家庭，观察至今我看到出现过一个老头、一个老太、还有较之年轻的一男一女。因为楼层的原因，我只能看到其窗外晾晒的衣物，无法窥视到内部的情形。只是有时能看到一男的或是女的走过来拉上窗户，拉上窗帘，像似要与外界隔绝，美美地做个美美的梦。有个周末，我坐在床上看着投影中的电影，眼睛往窗外一瞥，霎时汗毛直立。待我定睛瞧时，原来是这户窗外挂了个人形玩偶在那晾晒，好不瘆人。

住在对面稍偏右下的一个小房间里住着一个人，应该是男性。经常看他坐在电脑桌前，毛玻璃的蒙眬使我看不清他在键盘上的手速，但我想，那定是青轴。偶尔起身，那便应该是尿意来袭或是口干舌燥了吧。

再往右数米处有间房间最近一直在粉刷装修，往往十一二点还能见到粉刷匠在吊灯下的身影。背后有个美满的家庭，再多的重担肩上扛着，脸上还是挂着幸福的笑容。

再往上一点有个房间好像是个女性独处，有次晚上偶尔看到其窗帘未拉上，她正趴在床上玩手机，还是毛玻璃蒙眬，也许是男性也说不准。后来我每每往那边瞧时，皆是漆黑一片。恐是精神作祟？好不瘆人。

前些日子降了几场大雪，我去杭州出差那几日正是雪下得最大的时候。出门时撑的是黑伞，没过几分钟便已是白伞了。一夜过后，清晨出门，看着路边单车坐垫上足足有五六公分积雪，已是多少年没下过如此大雪了。犹记得儿时，记忆中的过年都是在厚厚的白雪上渡过。那时我们喜欢玩鞭炮，点火花棒在空中使劲了甩，不像如今，我们老家已经禁炮许多年了。都说现在过年越来越没有年味儿了，不是年味儿它消失了，是我们不知觉中已然长大。

忙碌，如今整日忙碌，却有时又不知到底在忙碌些什么。我们不妨自己找个时间，静静呆会，可以看看月亮看看星星，看看过往的路人，也可以跟我一样看看住在对面的居民。

Life is like a box of chocolate,you never know what you are going to get.

共勉。

看标题不知是否让您想起了有向图中的最短路径，是有些许类似，不过该题比其更简单更加清晰、直观、好理解。相信您看完这个之后，脑回路肯定更加的明亮！

题目描述如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]
自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

初看题目，上下有关联，有结束点，是个适合用递归的题目。以三角形的“行数”作为递归的结束判断，行数加上下标作为参数来回穿插。可行，可行！

于是大笔一挥：

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

int size = 0;
TreeSet<Integer> ts = new TreeSet<>();
List<List<Integer>> list;

/**
 * 超时
 * 
 * @param triangle
 * @return
 */
public int minimumTotal(List<List<Integer>> triangle) {
    list = triangle;
    size = triangle.size();
    if (size == 0)
        return 0;

    helper(0, 0, 0);
    return ts.first();
}

/**
 * 
 * @param row
 *            行数
 * @param index
 *            在该行中下标
 * @param sum_length
 *            路径之和
 */
private void helper(int row, int index, int sum_length) {
    if (row >= size) {
        ts.add(sum_length);
        return;
    }
    sum_length += list.get(row).get(index);
    helper(row + 1, index, sum_length);
    helper(row + 1, index + 1, sum_length);
}

是的，代码没有问题，可是拿去跑的时候，数据较大的测试用例却给了一个大红色的 超出时间限制。这里将 TreeSet 换成一个 MIN_LENGTH 整型变量每次进行比较取较小值，结果一样，都是超时。

本来是满怀欣喜，豪气撸码，结果给撞了个豆腐墙。

墙不硬，问题不大。我们换个思路，再摸摸青青草地。

以往出现这种求最小值、最大值啊，需要数据之间相关联相加减乘除的啊，用的都是 DP 居多啊！

脑浆乍现，回路高速擦亮，越擦越亮，越擦越闪，终于“吡”得一身，为数不多的小草又飘下几根，成了！

我也不用额外的空间了，就在你身上肆虐！

再回头看下那个“三角形”：

1
2
3
4
5
6

[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

既然是要一个最小值，那我就逐步缩减法，自下而上攻之。

根据题目要求我们知道如果上一行的元素下标为 i，那它只能跟它下一行的下标为 i 和 i+1 两元素相加。当然，我们只需要这两者的较小值。

即：

1
2
3
4
5
6
7
8
9
10
11
12
13

 [6,5,7]   // i 行
[4,1,8,3]  // j 行

以这两行为例 （条件：j = i + 1）

i 行中的 6 可以跟 j 行中的 4 或者 1 相加，由于我们结果取的是最小值，所以我们只留较小值
6 + 4 = 10, 6 + 1 = 7
因为 10 > 7，所以 i 行中的 6 我们就随之替换为 7

剩余元素同理，i 行最终便成了：
[7,6,10]

再由此，层层攻上。随着数量越来越少，最终顶上的那位佼佼者便是我们要取的首级！

武器献之：

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

/**
 * DP
 * 
 * @param triangle
 * @return
 */
public int minimumTotal(List<List<Integer>> triangle) {

    // 从倒数第二行开始往上走
    for (int i = triangle.size() - 2; i >= 0; i--) {
        // 从每行的起始下标开始直到 i
        for (int j = 0; j <= i; j++) {
            // i 行 j 下标的值
            int self = triangle.get(i).get(j);
            // 将 i 行 j 下标的值赋为 ： i 行 j 下标的值 与 i+1 行 j 下标和 j+1 下标值之和的较小值
            triangle.get(i).set(j,
                    Math.min(triangle.get(i + 1).get(j) + self, triangle.get(i + 1).get(j + 1) + self));
        }
    }
    // 层层往上 顶层值便是路径最小值
    return triangle.get(0).get(0);
}

这道题容易理解，对 DP（动态规划） 会有一个较为清晰的认知，我认为还是很不错的，故特意整理之。

文笔不好，望见谅！ End.

代码编译的结果从本地机器码转变为字节码，是存储格式发展的一小步，却是编程语言发展的一大步。

概述

执行引擎是 Java 虚拟机最核心的组成部分之一。在不同的虚拟机实现里面，执行引擎在执行 Java 代码的时候可能会有解释执行（通过解释器执行）和编译执行（通过即时编译器产生本地代码执行）两种选择，也可能两者兼备，甚至还可能会包含几个不同级别的编译器执行引擎。

但从外观上看起来，所有的 Java 虚拟机的执行引擎都是一致的：输入的是字节码文件，处理过程是字节码解析的等效过程，输出的是执行结果。接下来将主要从 概念模型的角度来总结下虚拟机的 方法调用和 字节码执行。

运行时栈帧结构

栈帧是用于支持虚拟机进行方法调用和方法执行的数据结构，它是虚拟机运行时数据区中的虚拟机栈的栈元素。每一个方法从调用开始至执行完成的过程，都对应着一个栈帧在虚拟机栈里面从入栈到出栈的过程。

每一个栈帧都包括了局部变量表、操作数栈、动态连接、方法返回地址和一些额外的附加信息。在编译程序代码的时候，栈帧中需要多大的局部变量表，多深的操作数栈都已经完全确定了，并且写入到方法表的 Code 属性之中，因此，一个栈帧需要分配多少内存，不会受到程序运行期变量数据的影响，而仅仅取决于具体的虚拟机实现。

局部变量表

局部变量表是一组变量值存储空间，用于存放方法参数和方法内部定义的局部变量。它的容量以变量槽（Variable Slot，下称 Slot）为最小单位。

在方法执行时，虚拟机是使用局部变量表来完成参数值到参数变量列表的传递过程的，如果执行的是实例方法（非 static 的方法），那局部变量表中第 0 位索引的 Slot 默认是用于传递方法所属对象实例的引用，在方法中可以通过关键字 this 来访问到这个隐含的参数。其余参数则按照参数表顺序排列，占用从 1 开始的局部变量 Slot，参数表分配完毕后，再根据方法体内部定义的变量顺序和作用域分配其余的 Slot。

局部变量定义了但没有赋初始值，是不能使用的，切记！

操作数栈

操作数栈也常称为操作栈，它是一个后入先出栈。同局部变量表一样，它的最大深度也是在编译时就写入到 Code 属性的 max_stacks 数据项中。

当一个方法刚刚开始执行时，这个方法的操作数栈是空的，在方法的执行过程中，会有各种字节码指令往操作数栈中写入和提取内容，也就是出栈 / 入栈操作。如：在做算术运算的时候是通过操作数栈来进行的，又或者在调用其他方法的时候是通过操作数栈来进行参数传递的。

动态连接

每个栈帧都包含一个指向运行时常量池中该栈帧所属方法的引用，持有这个引用是为了支持方法调用过程中的动态连接。

字节码中的方法调用指令就以常量池中指向方法的符号引用作为参数。这些符号引用一部分会在类加载阶段或者第一次使用的时候就转化为直接引用，这种转化称为 静态解析。另外一部分将在每一次运行期间转化为直接引用，这部分称为 动态连接。

方法返回地址

当一个方法开始执行后，只有两种方式可以退出这个方法：

• 执行引擎遇到任意一个方法返回的字节码指令，这时候可能会有返回值传递给上层的方法调用者，是否有返回值和返回值的类型将根据遇到何种方法返回指令来决定，这种退出方法的方式称为正常完成出口。
• 在方法执行过程中遇到了异常，并且这个异常没有在方法体内得到处理，无论是 Java 虚拟机内部产生的异常还是代码中使用 athrow 字节码指令产生的异常，只要在本方法的异常表中没有搜索到匹配的异常处理器，就会导致方法退出，这种退出方法的方式称为异常完成出口。

一个方法使用异常完成出口的方式退出，是不会给它的上层调用者产生任何返回值的。

方法退出的过程实际上就等同于把当前栈帧出栈，因此退出时可能执行的操作有：恢复上层方法的局部变量表和操作数栈，把返回值（如果有的话）压入调用者栈帧的操作数栈中，调整 PC 计数器的值以指向方法调用指令后面的一条指令等。

附加信息

虚拟机规范允许具体的虚拟机实现增加一些规范中没有描述的信息到栈帧之中，例如与调试相关的信息，这部分信息完全取决于具体的虚拟机实现。

在实际开发中，一般会把动态连接、方法返回地址与其他附加信息全部归为一类，称为栈帧信息。

方法调用

方法调用并不等同于方法执行，方法调用阶段唯一的任务就是确定被调用方法的版本（即调用哪一个方法），暂时还不涉及方法内部的具体运行过程。

一切方法调用在 Class 文件里面存储的都只是符号引用，而不是方法在实际运行时内存布局中的入口地址（相当于之前说的直接引用）。

解析

调用目标在程序代码写好、编译器进行编译时就必须确定下来。这类方法的调用称为解析。

在 Java 虚拟机里面提供了 5 条方法调用字节码指令：

• invokestatic：调用静态方法
• invokespecial：调用实例构造器 <init> 方法、私有方法和父类方法
• invokevirtual：调用所有的虚方法
• invokeinterface：调用接口方法，会在运行时再确定一个实现此接口的对象
• invokedynamic：先在运行时动态解析出调用点限定符所引用的方法，然后再执行该方法，在此之前的 4 条调用指令，分派逻辑是固化在 Java 虚拟机内部的，而 invokedynamic 指令的分派逻辑是由用户所设定的引导方法决定的

只要能被 invokestatic 和 invokespecial 指令调用的方法，都可以在解析阶段中确定唯一的调用版本，符合这个条件的有静态方法、私有方法、实例构造器和父类方法 4 类。它们在类加载的时候就会把符号引用解析为该方法的直接引用，称为 非虚方法。其余的称为 虚方法。

final 方法是一种非虚方法。

分派

静态分派

Human man = new Man()

上面代码中的 Human 称为变量的静态类型，或是外观类型，Man 称为变量的实际类型。静态类型和实际类型在程序中都可以发生一些变化，但是静态类型的变化仅仅在使用时发生，变量本身的静态类型不会被改变，并且最终的静态类型是在编译期可知的；而实际类型变化的结果在运行期才可确定，编译器在编译程序时并不知道一个对象的实际类型是什么。

编译器在重载时是通过参数的静态类型而不是实际类型作为判断依据的，所以，两个静态类型相同但实际类型不同的变量，在编译阶段，Javac 编译器会根据参数的静态类型决定使用哪一个重载版本。

动态分派

我们先说说重写，重写与动态分派关系密切。invokevirtual 指令执行是在 运行期确定接收者的实际类型，所以调用中的 invokevirtual 指令把常量池中的类方法符号引用解析到了不同的直接引用上，这个过程就是 Java 语言中方法重写的本质。

我们把这种在运行期根据实际类型确定方法执行版本的分派过程称为动态分派。

单分派与多分派

方法的接收者与方法的参数统称为方法的宗量，根据分派基于多少种宗量，可以将分派划分为单分派和多分派两种。

单分派是根据一个宗量对目标方法进行选择，多分派是根据多于一个宗量对目标方法进行选择。

基于栈的字节码解释执行引擎

探讨虚拟机是如何执行方法中的字节码指令的。

解释执行

Java 语言中，Javac 编译器完成了程序代码经过词法分析、语法分析到抽象语法树，再遍历语法树生成线性的字节码指令流的过程。因为这一部分动作是在 Java 虚拟机之外进行的，而解释器在虚拟机的内部，所以 Java 程序的编译就是半独立的实现。

基于栈的指令集与基于寄存器的指令集

基于栈的指令集主要优点就是可移植，还可把一些访问频繁的数据放到寄存器中获取尽量好的性能，代码会相对更加紧凑，编译器实现更加简单等。

栈架构指令集的主要缺点是执行速度相对来说会稍慢一些，完成相同功能所需的指令数量较寄存器架构多，频繁的栈访问导致频繁的内存访问。

End.