Hibernate SQLQuery缓存问题分析


前情提要

系统的ORM框架是Hibernate4.1.9, Cache Provider是Ehcache, 设置CacheRegion后遭遇到缓存不失效问题.
比如说: 使用SQL语句查询一个表的数目是10000, 这时候删除掉了该表的一条记录, 那么再次使用同一条语句查询数目时应该重新去数据库查询得到结果为9999, 但是因为缓存没有失效, 所以查出来的还是10000.
但是, Hibernate从古老的3.1版本直到最新的5.3.9都有这个问题, 就很emmmm

原因分析

这个主要的原因是Hibernate在处理SQLQuery时, 没有正确设置querySpaces, 也就是本次查询关联的表名.
如果检测到查询的关联表已经被修改, 那么这个缓存应该立即失效, 由于没有设置querySpaces导致任意SQLQuery都不会被这个机制所影响.

通过Hibernate的查询最后会到org.hibernate.loader.Loader类下的listUsingQueryCache中, 这里会尝试中从Cache中获取数据, 如果Cache中存在数据就返回Cache中的数据:

private List listUsingQueryCache(
        final SessionImplementor session,
        final QueryParameters queryParameters,
        final Set querySpaces,
        final Type[] resultTypes) {

    QueryCache queryCache = factory.getQueryCache( queryParameters.getCacheRegion() );

    QueryKey key = generateQueryKey( session, queryParameters );

    if ( querySpaces == null || querySpaces.size() == 0 )
        LOG.tracev( "Unexpected querySpaces is {0}", ( querySpaces == null ? querySpaces : "empty" ) );
    else {
        LOG.tracev( "querySpaces is {0}", querySpaces );
    }

    List result = getResultFromQueryCache(
            session,
            queryParameters,
            querySpaces,
            resultTypes,
            queryCache,
            key
        );

    if ( result == null ) {
        result = doList( session, queryParameters, key.getResultTransformer() );

        putResultInQueryCache(
                session,
                queryParameters,
                resultTypes,
                queryCache,
                key,
                result
        );
    }
    // ...
}

跟踪getResultFromQueryCache方法, 会发现他最终是从org.hibernate.cache.internal.StandardQueryCacheget方法里获取的数据:

public List get(
        QueryKey key,
        Type[] returnTypes,
        boolean isNaturalKeyLookup,
        Set spaces,
        SessionImplementor session) throws HibernateException {
    LOG.debugf( "Checking cached query results in region: %s", cacheRegion.getName() );

    List cacheable = (List) cacheRegion.get( key );
    logCachedResultDetails( key, spaces, returnTypes, cacheable );

    if ( cacheable == null ) {
        LOG.debug( "Query results were not found in cache" );
        return null;
    }

    Long timestamp = (Long) cacheable.get( 0 );
    if ( !isNaturalKeyLookup && !isUpToDate( spaces, timestamp ) ) {
        LOG.debug( "Cached query results were not up-to-date" );
        return null;
    }
    // ...

这里会在isUpToDate方法里检测数据是否已经失效, 该方法的实现在org.hibernate.cache.spi.UpdateTimestampsCache:

public boolean isUpToDate(Set spaces, Long timestamp) throws HibernateException {
    final boolean debug = LOG.isDebugEnabled();
    final boolean stats = factory != null && factory.getStatistics().isStatisticsEnabled();

    for ( Serializable space : (Set<Serializable>) spaces ) {
        Long lastUpdate = (Long) region.get( space );
        if ( lastUpdate == null ) {
            if ( stats ) {
                factory.getStatisticsImplementor().updateTimestampsCacheMiss();
            }
            //the last update timestamp was lost from the cache
            //(or there were no updates since startup!)
            //updateTimestamps.put( space, new Long( updateTimestamps.nextTimestamp() ) );
            //result = false; // safer
        }
        else {
            if ( debug ) {
                LOG.debugf(
                        "[%s] last update timestamp: %s",
                        space,
                        lastUpdate + ", result set timestamp: " + timestamp
                );
            }
            if ( stats ) {
                factory.getStatisticsImplementor().updateTimestampsCacheHit();
            }
            if ( lastUpdate >= timestamp ) {
                return false;
            }
        }
    }
    return true;
}

如果发现上次的更新时间lastUpdate比缓存的时间timestamp更新则会更新缓存, 但是因为SQLQuery不会设置querySpaces, 所以根本连这个循环都进不去= =

关于querySpaces的值的设置, 根据跟踪主要是在org.hibernate.loader.custom.sql.SQLCustomQuery中设置的:

    public SQLCustomQuery(
            final String sqlQuery,
            final NativeSQLQueryReturn[] queryReturns,
            final Collection additionalQuerySpaces,
            final SessionFactoryImplementor factory) throws HibernateException {

        LOG.tracev( "Starting processing of sql query [{0}]", sqlQuery );
        SQLQueryReturnProcessor processor = new SQLQueryReturnProcessor(queryReturns, factory);
        SQLQueryReturnProcessor.ResultAliasContext aliasContext = processor.process();


//        Map[] propertyResultMaps =  (Map[]) processor.getPropertyResults().toArray( new Map[0] );
//        Map[] collectionResultMaps =  (Map[]) processor.getCollectionPropertyResults().toArray( new Map[0] );
//
//        List collectionSuffixes = new ArrayList();
//        List collectionOwnerAliases = processor.getCollectionOwnerAliases();
//        List collectionPersisters = processor.getCollectionPersisters();
//        int size = collectionPersisters.size();
//        if (size!=0) {
//            collectionOwners = new int[size];
//            collectionRoles = new String[size];
//            //collectionDescriptors = new CollectionAliases[size];
//            for ( int i=0; i<size; i++ ) {
//                CollectionPersister collectionPersister = (CollectionPersister) collectionPersisters.get(i);
//                collectionRoles[i] = ( collectionPersister ).getRole();
//                collectionOwners[i] = processor.getAliases().indexOf( collectionOwnerAliases.get(i) );
//                String suffix = i + "__";
//                collectionSuffixes.add(suffix);
//                //collectionDescriptors[i] = new GeneratedCollectionAliases( collectionResultMaps[i], collectionPersister, suffix );
//            }
//        }
//        else {
//            collectionRoles = null;
//            //collectionDescriptors = null;
//            collectionOwners = null;
//        }
//
//        String[] aliases = ArrayHelper.toStringArray( processor.getAliases() );
//        String[] collAliases = ArrayHelper.toStringArray( processor.getCollectionAliases() );
//        String[] collSuffixes = ArrayHelper.toStringArray(collectionSuffixes);
//
//        SQLLoadable[] entityPersisters = (SQLLoadable[]) processor.getPersisters().toArray( new SQLLoadable[0] );
//        SQLLoadableCollection[] collPersisters = (SQLLoadableCollection[]) collectionPersisters.toArray( new SQLLoadableCollection[0] );
//        lockModes = (LockMode[]) processor.getLockModes().toArray( new LockMode[0] );
//
//        scalarColumnAliases = ArrayHelper.toStringArray( processor.getScalarColumnAliases() );
//        scalarTypes = ArrayHelper.toTypeArray( processor.getScalarTypes() );
//
//        // need to match the "sequence" of what we return. scalar first, entity last.
//        returnAliases = ArrayHelper.join(scalarColumnAliases, aliases);
//
//        String[] suffixes = BasicLoader.generateSuffixes(entityPersisters.length);

        SQLQueryParser parser = new SQLQueryParser( sqlQuery, new ParserContext( aliasContext ), factory );
        this.sql = parser.process();
        this.namedParameterBindPoints.putAll( parser.getNamedParameters() );

//        SQLQueryParser parser = new SQLQueryParser(
//                sqlQuery,
//                processor.getAlias2Persister(),
//                processor.getAlias2Return(),
//                aliases,
//                collAliases,
//                collPersisters,
//                suffixes,
//                collSuffixes
//        );
//
//        sql = parser.process();
//
//        namedParameterBindPoints = parser.getNamedParameters();


        customQueryReturns.addAll( processor.generateCustomReturns( parser.queryHasAliases() ) );

//        // Populate entityNames, entityDescrptors and querySpaces
//        entityNames = new String[entityPersisters.length];
//        entityDescriptors = new EntityAliases[entityPersisters.length];
//        for (int i = 0; i < entityPersisters.length; i++) {
//            SQLLoadable persister = entityPersisters[i];
//            //alias2Persister.put( aliases[i], persister );
//            //TODO: Does not consider any other tables referenced in the query
//            ArrayHelper.addAll( querySpaces, persister.getQuerySpaces() );
//            entityNames[i] = persister.getEntityName();
//            if ( parser.queryHasAliases() ) {
//                entityDescriptors[i] = new DefaultEntityAliases(
//                        propertyResultMaps[i],
//                        entityPersisters[i],
//                        suffixes[i]
//                    );
//            }
//            else {
//                entityDescriptors[i] = new ColumnEntityAliases(
//                        propertyResultMaps[i],
//                        entityPersisters[i],
//                        suffixes[i]
//                    );
//            }
//        }
        if ( additionalQuerySpaces != null ) {
            querySpaces.addAll( additionalQuerySpaces );
        }

//        if (size!=0) {
//            collectionDescriptors = new CollectionAliases[size];
//            for ( int i=0; i<size; i++ ) {
//                CollectionPersister collectionPersister = (CollectionPersister) collectionPersisters.get(i);
//                String suffix = i + "__";
//                if( parser.queryHasAliases() ) {
//                    collectionDescriptors[i] = new GeneratedCollectionAliases( collectionResultMaps[i], collectionPersister, suffix );
//                } else {
//                    collectionDescriptors[i] = new ColumnCollectionAliases( collectionResultMaps[i], (SQLLoadableCollection) collectionPersister );
//                }
//            }
//        }
//        else {
//            collectionDescriptors = null;
//        }
//
//
//        // Resolve owners
//        Map alias2OwnerAlias = processor.getAlias2OwnerAlias();
//        int[] ownersArray = new int[entityPersisters.length];
//        for ( int j=0; j < aliases.length; j++ ) {
//            String ownerAlias = (String) alias2OwnerAlias.get( aliases[j] );
//            if ( StringHelper.isNotEmpty(ownerAlias) ) {
//                ownersArray[j] =  processor.getAliases().indexOf( ownerAlias );
//            }
//            else {
//                ownersArray[j] = -1;
//            }
//        }
//        if ( ArrayHelper.isAllNegative(ownersArray) ) {
//            ownersArray = null;
//        }
//        this.entityOwners = ownersArray;

    }

可以看到这个构造函数的代码很长, 但大部分都被注释掉了, 和querySpaces有关的只有这一句querySpaces.addAll( additionalQuerySpaces );.
这里的additionalQuerySpaces是在建立查询时放入的一个参数, 可以手动指定querySpaces, 如果没有手动指定, 那么这里也是空的, 因此查询进行到Loader层的时候也会是空的.
可以看到这个方法中注释掉了大量代码, 其中也包括处理querySpaces的部分, 可能是原来写的有问题, 所以作者干脆注释掉算了= =
然后...直到最新版本, 也再也没有人动过这里的代码= =
所以说, 开源有好的地方, 但是也是有不好的地方的_(:3」∠)_

既然已经知道了问题, 那么有两种解决问题的思路:

  1. 重写SQLCustomQuery类, 将这里对querySpaces手动实现上去, 未来也许还可以提交一个PR

    • 这种方式的问题是, 单独对框架进行修改不利于日后的升级, 未来接手维护的人可能不太清楚你都改了那些内容, 会不会对业务有影响, 因此不敢轻易升级
  2. 不用Hibernate提供的缓存, 而是根据业务需要在Hibernate外手动建立一个针对业务的查询缓存

    • 这种方式感觉就是很不优雅= =

解决方法

业务层缓存

基本思路是实现一个单例, 然后使用ReadWriteLock对读写进行加锁以保证线程安全, 单例采用DCL实现:

public class CountCache{
    private volatile static CountCache instance;
    private Map<String, Long> cache = new HashMap<>();
    private Map<String, Long> cacheTime = new HashMap<>();

    // 加读写锁保证线程安全
    private ReadWriteLock rwLock = new ReentrantReadWriteLock();

    // 超时时间设置, 单位为秒
    private final static int timeout = 1800;

    // 防止直接创建实例
    private CountCache(){}

    /**
     * DCL形式的单例
     */
    public static CountCache getInstance(){
        if(instance == null){
            synchronized(CountCache.class){
                if(instance == null){
                    instance = new CountCache();
                }
            }
        }
        return instance;
    }

    /**
     * 读缓存内容, 如果写入时间超时, 则缓存无效
     */
    public long readCache(String key){
        try{
            if(rwLock.readLock().tryLock() || rwLock.readLock().tryLock(1, TimeUnit.SECONDS)){
                try{
                    if(cacheTime.containsKey(key)){
                        long interval = System.currentTimeMillis() - cacheTime.get(key);
                        // if timeout
                        if(interval / 1000 > timeout){
                            invalidateCache(key);
                            return -1;
                        }
                        // read cache
                        return cache.get(key);
                    }
                }finally{
                    rwLock.readLock().unlock();
                }
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
        return -1;
    }

    /**
     * 写缓存内容, 记录写入时间
     */
    public void writeCache(String key, long value){
        try{
            if(rwLock.writeLock().tryLock() || rwLock.writeLock().tryLock(1, TimeUnit.SECONDS)){
                try{
                    cache.put(key, value);
                    cacheTime.put(key, System.currentTimeMillis());
                }finally{
                    rwLock.writeLock().unlock();
                }
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
    }

    /**
     * 将缓存失效
     */
    public void invalidateCache(String key){
        try{
            if(rwLock.writeLock().tryLock() || rwLock.writeLock().tryLock(1, TimeUnit.SECONDS)){
                try{
                    cache.remove(key);
                    cacheTime.remove(key);
                }finally{
                    rwLock.writeLock().unlock();
                }
            }
        }catch(InterruptedException e){
            e.printStackTrace();
        }
    }
}

魔改SQLCustomQuery

有没有什么办法在不修改Hibernate的Jar包的前提下实现对SQLCustomQuery类的替换呢?
能不能在运行时, 卸载掉原来的SQLCustomQuery类然后加载我们自定义的SQLCustomQuery类, 让我们自定义的类替换掉原有的实现?

替换原有类

经过调研, 替换原有类主要有两种思路:

  1. 自定义一个自己的类加载器, 然后越早越好, 使用这个自定义的类加载器来加载所有的类, 而不是Tomcat自带的WebappClassLoader, 这样整个WEB应用都会使用我们自定义的类加载器了, 这样在我们的类加载器对单独几个特殊的类来做特殊的加载就很容易

    • 理论基础是: 一个类会用它自己的类加载器来加载它所new的对象, 所以只要在很早的时候加载一个启动类, 那么由这个类派生出来的所有类都会使用我们的类加载器了
    • 实现上的话, 我们可以定一个黑名单, 在黑名单里的类不委托WebappClassLoader加载, 而是我们自己加载, 而正常的类都交给WebappClassLoader来加载, 使用正常的双亲委托机制
    • 但是, 很难找到一个那么早的时机来使用自己的类加载器, 要是需要修改Tomcat源码的话...还不如直接修改Hibernate源码了
  2. 使用Instrument机制, 这样需要在Java虚拟机启动的时候带一个Agent, 在Agent里面我们要对JVM虚拟机做一些操作就很容易, 替换一个类更是可行的

    • 比如说, IDEA就会在启动程序的时候带上-javaagent:C:\App\JetBrains\apps\IDEA-U\ch-0\183.5912.21\lib\idea_rt.jar=5451:C:\App\JetBrains\apps\IDEA-U\ch-0\183.5912.21\bin参数
    • 但是, 这样操作的话需要修改Tomcat的Boostrap脚本, 协调起来比较麻烦...还不如直接修改Hibernate源码了

更加简单的方法

经过测试, 其实根本没必要进行上述那么复杂的操作, Tomcat会优先加载WEB-INF/classes中的类然后才去加载WEB-INF/libs下的类, 因此我们只要在自己的应用里实现一个同名的类就可以了.
这样, Tomcat会优先加载我们应用中的类, 而忽略掉Jar包中的类的加载.

修改后的SQLCustomQuery如下:

public class SQLCustomQuery implements CustomQuery{
    // 缓存数据库中的所有表名
    private static Set<String> allUserTables;

    public SQLCustomQuery(
            final String sqlQuery,
            final NativeSQLQueryReturn[] queryReturns,
            final Collection additionalQuerySpaces,
            final SessionFactoryImplementor factory) throws HibernateException{

        // 省略SQLCustomQuery原有代码

        // 一个简单的提取SQL所查询的表的思路是, 因为我们的业务表拥有固定的前缀
        // 那么只需要按空格分开所有Token, 然后只保留固定前缀开头的单词最后去重即可, 但是有极低的可能性误判
        // 更加靠谱的思路的是, 我们去获取我们所有表的列表, 所以只取已知表的单词就是所查询的表
        // 考虑到第一种和第二种方法实现起来难度差不多, 所以干脆实现第二种了
        LOG.infov("Loaded Custom SQLCustomQuery of SQL Query [{0}]", sql);

        // 初始化或更新所有表的列表
        try{
            // 初次使用需要初始化
            if(allUserTables == null){
                allUserTables = queryUserTables();
            }
            // 如果谁想不开在代码修改表结构的话, 更新缓存的表名
            String lowerSQL = sql.toLowerCase();
            if(lowerSQL.contains("table") && (lowerSQL.contains("create") || lowerSQL.contains("drop"))){
                allUserTables = queryUserTables();
                LOG.warnv("Create/Drop Table! Query: [{0}]", sql);
            }
        }catch(NamingException | SQLException e){
            e.printStackTrace();
        }

        // 提取SQL查询中的所有Token, 并记录包含表名的Token
        String[] sqlTokens = sql.split("  *");
        for(String token : sqlTokens){
            if(allUserTables.contains(token)){
                querySpaces.add(token);
            }
        }
    }

    /**
     * 这里采用JDBC直接查询数据库所有表名
     */
    private Set<String> queryUserTables() throws NamingException, SQLException{
        Context ctx = new InitialContext();
        String dbName = ApplicationContainer.sc.getAttribute("dataSource").toString().toLowerCase();
        DataSource ds = (DataSource)ctx.lookup("java:comp/env/" + dbName);

        Connection conn = null;
        Set<String> result = new HashSet<>();
        try{
            conn = ds.getConnection();
            Statement st = conn.createStatement();
            ResultSet rs = st.executeQuery("select table_name from user_tables"); // Oracle 数据库
            while(rs.next()){
                result.add(rs.getString(1));
            }
        }finally{
            if(conn != null && !conn.isClosed()){
                conn.close();
            }
        }

        return result;
    }

一个简单获取所关联的表名思路就是先获取所有的表名, 然后看每一个SQL中的Token是否是表名, 如果是则添加到querySpaces中.
如果真的要去解析SQL, 建立AST语法树的话, 那就太麻烦了_(:3」∠)_
直接正则表达式的话, 因为很难预料业务代码会写出什么样的SQL, 所以并不是特别靠谱.

直接采用JDBC查询的原因是, 这样的操作比较快, 而且只查询一次, 且在框架内部操作并不适合再通过Hibernate去查询.

由于allUserTables被重复设置也没什么问题, 所以不太需要考虑线程安全问题.

当然, 根据我们的实际业务需要, 这样来处理querySpaces没有太大问题, 但是如果作为框架内部代码显然不能这么实现, 到时候还是需要解析SQL, 处理AST然后获得相关联的表. 等我什么时候学了编译原理, 这里还没有人改我就写一个然后提个PR吧233

简单总结

没什么想说的_(:3」∠)_ 辣鸡Hibernate(x

数据库范式简明解释


总的来说, 数据库范式就是逐渐消除数据冗余的过程.

1NF: 字段不可分

  • 属性的原子性约束
  • 一个数据库中字段不能包含多个可分的字段

    • 比如说不能把手机和邮箱记录在同一个字段中
    • 同理, 把多个手机记录在同一个字段中也是不合适的

2NF: 非主键字段完全依赖于主键 (消除部分子函数依赖)

  • 记录的惟一性约束
  • 消除了主键组合字段之间的依赖
  • 反例: 两个独立的组合主键 (K1, K2) -> (V1, V2) | (K1) -> (V1), (K2) -> (V2), (K1) -> (K2)

    • 修改为: (K1) -> (V1), (K2) -> (V2), (K1) -> (K2)

3NF: 非主键字段不依赖于其它非主键字段 (消除传递依赖)

  • 字段冗余性的约束
  • 消除了非主键字段之间的依赖
  • 不存在非主键字段对任一候选主键的传递函数依赖
  • 数据冗余: V1依赖于V2, 导致多个重复V1时, V2也发生重复 (K1) -> (V1, V2) | (V1) -> (V2)

    • 修改为: (K1) -> (V1), (V1) -> (V2)

BCNF: 任何字段不依赖于其他字段 (消除传递依赖)

  • 字段冗余性的约束
  • 消除了所有字段之间的依赖(
  • 不存在任何字段对任一候选主键的传递函数依赖
  • 主键依赖主键: (K1, K2) -> (V1) | (K1) -> (K2)

    • 修改为: (K1) -> (V1), (K1) -> (K2)
  • 与3NF的主要区别是: 3NF只考虑了非主键字段之间的依赖, 而没有考虑主键组合字段之间的依赖, BCNF是一种更严格的3NF

算法和数据结构总结大纲


时间复杂度

基本原则

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

常数优化

  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