简单搜到看到的版本。。。

版本1：事务执行前后数据库的状态保存一致。（某公众号复习资料）

感想： ？？？

版本2：几个并行执行的事务，其执行结果必须与按某一顺序串行执行的结果相一致。（百度百科）

感想：感觉这个解释更偏向隔离性？

版本3：一致性是指事务必须使数据库从一个一致性状态变换到另一个一致性状态。

感想：听君一席话，如听一席话

版本4：数据库处理前后结果应与其所抽象的客观世界中真实状况保持一致。

感想：好像有点明白，有几个版本是从这个角度说的（很多都是银行账户存取款的例子，转账前后钱应该守恒，且不能转超出余额的钱让余额变成负数等等）。一致性有时也被称为正确性 (Correctness)，即操作前后，数据库记录的数据是正确、符合期望的。

索性连英文的版本也一起查了：

Consistency ensures that a transaction can only bring the database from one valid state to another, maintaining database invariants: any data written to the database must be valid according to all defined rules, including constraints, cascades, triggers, and any combination thereof. This prevents database corruption by an illegal transaction, but does not guarantee that a transaction is correct. Referential integrity guarantees the primary key – foreign key relationship. （Wikipedia）

保障只会从一个有效/正确的状态，转变成另一个有效/正确的状态。

那么什么是不正确/无效呢？就是违反了任何已定义的规则的情况，包括违反约束条件、级联、触发器等不合法操作。如试图插入重复的主键（数据库不会让你这么做的），违反外键约束，违反unique等等。在干了这种事之后会发生什么呢？Commit是不会commit了，基本都是被catch、报错、rollback了。而既然非法操作被回滚，也就不会走向一个不正确/无效的状态，而是回到原先的有效状态。

另一个角度来说，只有操作全都合法，符合约束，才可能被提交，而在此情况下，新的状态也是符合约束、有效的。

而各种约束、级联、触发器、自定义的各种检查（if之类的，不通过就rollback之类的），也都是为了让数据更加“正确”，与数据要反映的事实相符合、一致。大概也就是这样了吧。

继续的复习……

事务 Transaction

经常以下面这种形式存在的，满足ACID的数据库操作（一系列操作）。

BEGIN TRY 
	BEGIN TRANSACTION 
		-- 事务的操作写这里 -- 
	COMMIT TRANSACTION 
END TRY 
BEGIN CATCH 
	IF (@@TRANCOUNT > 0) 
    	-- 处理错误、写错误日志等操作 -- 
 		ROLLBACK TRANSACTION 
    END IF 
END CATCH

只有顺利运行过commit才真正改动了数据库信息，rollback的话一切还原。

ACID

其中AID没什么争议，尤其是A和D。C上面解释了。

• 原子性 (Atomicity)：同一个事务里的操作不可分割，要么全部执行 (commit掉)，要么全部不执行 (rollback掉)。不会出现一半执行了，一半没执行的情况，即便执行到半截断电了也不会。
• 隔离性 (Isolation)：每个事务独立执行，多个并发事务互不干扰。
• 持久性 (Durability) : 事务提交后，对系统的影响是持久的。已经改动的数据不会丢失，即便数据库出现故障。

隔离性的话，还存在隔离等级：

• 读未提交（Read Uncommitted）: 一个事务读取了另一个事务还未提交的数据，而第二个事务之后可能回滚了并没执行这个更新，也就是脏读。
• 读已提交（Read Committed）: 只会读取其他事务已经提交的数据。但是依然可能发生“不可重复读”。一个事务读取某数据后，另一个事务修改了该数据。那么第一个事务里，再次尝试读这个数据时就读不到原来的值了。
• 可重复读 （Repeatable Read）: 在一个事务中，无论读同一个数据几次 (且无论中途其他事务是否修改了它），读取到的值都一样。但是可能出现幻读，如A事务查询id=123，返回0行，B事务插入id=123，A查询id=123，依然没有结果，A插入id=123失败（A认为id=123不存在，但却无法插入）。
• 可串行化（Serializable）：把多个并发事务一个一个串行执行，不会有任何上述问题，但速度很慢……

Ref：

• https://www.cnblogs.com/huanghai223/archive/2011/12/12/2284436.html
• https://en.wikipedia.org/wiki/ACID
• https://baike.baidu.com/item/数据库事务/9744607
• https://zhuanlan.zhihu.com/p/174554969
• https://www.zhihu.com/question/31346392
• https://blog.csdn.net/c0d5r/article/details/110680789
• https://cloud.tencent.com/developer/article/1593481

创建型模式 Creational Pattern

如何创建对象。如隐藏一些具体的创建逻辑，从而提高代码的灵活性与可重用性。

工厂 Factory

• 不直接靠new来创建实例，而是建造一个工厂类，再通过工厂的方法创建“产品”类。
• 使用者使用产品，不需要知道工厂具体怎样生产、产品的具体细节，只需要知道工厂可以生产产品，且生产出来的产品都具有自己想要的某种用途（产品们需要有统一接口）就可以了。

public interface Product {
    void doSomething();
    void showName();
}

/*------Product A -----*/
public class ProductA implements Product {
    public String name = "Product A";
    void doSomething() {
    	System.out.println("A: do something");
    }
    
    void showName() {
    	System.out.println(name);
    }
}

/*------Product B -----*/
public class ProductB implements Product {
    public String name = "Product B";
    void doSomething() {
    	System.out.println("B: do something");
    }
    
    void showName() {
    	System.out.println(name);
    }
}


/*-----------Factory------------*/
public class MyFactory {
    public Product getProduct(String productType) {
    	if(productType.equals("A") return new ProductA();
        else if(productType.equals("B")) return new ProductB();
        else return null;
    }
}

/* ================== OR ================== */

public abstract class MyFactory {
    public void makeUseOfProduct() {
    	Product p = getProduct();
        p.showName();
        p.doSomething();
    }
    
    public abstract Product getProduct();
}

public class FactoryA extends MyFactory {
    @Override
    public Product getProduct() {
    	return new ProductA();
    }
}

public class FactoryB extends MyFactory {
    @Override
    public Product getProduct() {
    	return new ProductB();
    }
}

// and use the subclasses to generate and make use of products

抽象工厂 Abstract Factory

• 让工厂不只能生产一个，而是能生产一套产品。
• 可以保证一个工厂里生产出来的产品都是配套的（比如都是服装工厂，但一个男装，一个女装）
• 使用者不用知道工厂具体怎么生产，但可以知道从同一个工厂拿出的产品是配套的（只使用从男装工厂生产的产品，就不会出现女装大佬）

public interface Upper {
    void printName();
    void dress();
}

public interface Lower {
    void printName();
    void dress();
}

public abstract class ClothingFactory {
    public abstract Upper produceUpper();
    public abstract Lower produceLower();
    
    public void dressUp() {
        Upper upper = produceUpper();
        Lower lower = produceLower();
        
        upper.dress();
        lower.dress();
    }
}

public class WomensClothingFactory {
    @Override
    public Upper produceUpper() {
        // produce women's upper garment
    }
    
    @Override
    public Lower produceLower() {
        // produce women's lower garment
    }
}

public class MenssClothingFactory {
    @Override
    public Upper produceUpper() {
        // produce men's upper garment
    }
    
    @Override
    public Lower produceLower() {
        // produce men's lower garment
    }
}

建造者 Builder

• 一步一步构造对象
• 适用于，有很多步骤有通用性，但具体步骤容易有改变，或者构造对象时并非每个步骤都执行的时候
• 例：StringBuilder，每个步骤增加或去除字符，最后生产一个字符串
• 例：构建一个套餐，一道一道点菜，最后结账
• 例：装修房屋，埋线、刷墙、铺地板、安装厨房、安装卫生间、摆放家具等等
• 有时也可以安排一个Director负责指挥一个或多个Builder按一定程序执行建造步骤

public interface Builder {
    PartA buildStepA();
    PartB buildStepB();
    void buildStepC();
    
    void reset();
    Product getResult();
}

public class Director {
    private Builder builder;
    
    public Director(builder) {
        this.builder = builder;
    }
    
    public void changeBuilder(builder) {
        this.builder = builder;
    }
    
    public Product build(String type) {
    	if(type.equals("A")) {
            builder.buildStepA();
            builder.buildStepC();
            return builder.getResult();
        } else {
            builder.buildStepB();
            builder.buildStepC();
            return builder.getResult();
        }
    }
}

单例 Singleton

• 每个单例类只有一个实例
• 全局要用这个类时，访问的都是同一个实例
• 用来减少一个被全局共用的类的频繁创建和销毁
• 例：对某个数据库的访问
• 例：一份全局通用的配置文件
• 例：一个可以重用的pipeline
• 注意：多线程时还需要注意同步问题，避免多个线程产生多个实例
• 注意：很多测试框架不支持对Singleton的单元测试（因为private constructor还有static的getInstance）

public class MySingleton {
    private MySingleton instance;
    
    // 防止它被从外部创建
    private MySingleton() {}
    
    public static MySingleton getInstance() {
        if(instance==null) {
        	synchronized (MySingleton.class) {
                if(instance==null) {
                    instance = new MySingleton();
                }
            }
        }
        
        return instance;
    }
    
    public void doSomething() {
        // do something
    }
}

原型 Prototype

• 说白了就是允许Clone的类 （Java里实现Cloneable接口，override clone方法）
• 允许使用者在不了解类的全貌（没有class文件），只有对象的情况下，也能复制对象

结构型模式 Structural Pattern

如何把对象们组合到一起，让它们在一个系统里可以互相配合的工作。

适配器 Adapter

• 如果两个类无法配合，比如输入输出不匹配，那就在中间插一个适配器
• 例：电源是240V电压，手机充电需要12V，插一个从240V转到12V的适配器
• 例：笔记本没有SD卡插口，往USB口插一个读卡器，再往读卡器里插SD卡
• 例：A程序输入XML，B程序读JSON，中间插一个XML转JSON的适配器

桥接 Bridge

• 如果一个类有多个独立维度的变化，则可以把每个维度都拆成一个新的类或接口
• 例：图形包含（红的圆，白的圆，蓝的圆，红的正方形，蓝的正方形，红的三角，白的三角……），可以解耦成：图形 {形状，颜色}

组合 Composite

• 树形结构模式
• 希望用户能够忽略组合对象和单个对象的不同（组合对象和单个对象都实现同一个接口，组合对象的接口对组合中每个单独对象调用该接口）
• 例：单个图形可以被绘制，组合图形的绘制则是把组合中每个图形都绘制出来

过滤器/标准 Filter/Criteria

• 允许用户以不同标准过滤一组对象

public interface Criteria {
    public List<T> meet(List<T> toFilter);
}

public class Criteria1 implements Criteria {
    @Override
    public List<T> meet(List<T> toFilter) {
    	List<T> list = new ArrayList<T>();
        for(T item: toFilter){
            if(item.getAttr1().equals("value 1")) {
                list.add(item);
            }
        }
        return list;
    }
}

public class Criteria2 implements Criteria {
    @Override
    public List<T> meet(List<T> toFilter) {
    	List<T> list = new ArrayList<T>();
        for(T item: toFilter){
            if(item.getAttr2().equals("value 2")) {
                list.add(item);
            }
        }
        return list;
    }
}


public class AndCriteria implements Criteria {
 
   private Criteria c1;
   private Criteria c2;
 
   public AndCriteria(Criteria c1, Criteria c2) {
      this.c1 = c1;
      this.c2 = c2; 
   }
 
   @Override
   public List<T> meet(List<T> toFilter) {
      List<T> firstCriteriaList = c1.meet(toFilter);     
      return c2.meet(firstCriteriaList);
   }
}


// or 就求并集

装饰器 Decorator

• 即在某个类外面多包一层，这一层具有自己的某些作用，且允许透过这一层使用里面包的东西原本有的
• 使用继承很别扭、不容易的时候，可以使用装饰器
• 装饰类和被装饰类可以独立发展
• 可能需要在被装饰的类外面多包一层Wrapper类
• 一些语言和框架可以在类和方法上直接@注释来进行装饰
• (也可以理解为往类里注入属性和方法)

外观 Facade

• 隐藏复杂系统内部的逻辑，提供一个简单的对外接口供客户端使用
• 客户端不与系统耦合，外观类与系统耦合
• 外观类可能提供的功能比系统所能提供的全部要少很多，但只要提供可续断所需就可以了
• 例：觉得办理某些手续的流程复杂难懂，找中介（外观类）来处理
• 例：公司的接待人员

享元 Flyweight

• 也被称作缓存 Cache
• 当有大量对象有相同的部分，且这些部分基本不变时，可以通过把共享的部分抽取出来单独存一份来节省内存
• 如果有相同的业务请求，直接返回内存中已有的，避免重新创建
• 相同的部分只存一份，不同的部分各存各的
• 例：游戏中一群鸟共享一份绘图资源，各存各的位置和飞行速度
• 例：Java中的String，数据库的数据池
• 例：在HashMap或字典类等里对共享资源进行缓存，如果命中，直接返回
• 例：键值对、查询结果等缓存进NoSQL数据库

代理 Proxy

• 为了增加对访问的控制、方便管理访问、或者方便访问，在访问者和被访问的类之间增加一层代理
• 与适配器之间的差别：代理不改变被代理的接口
• 与装饰器之间的差别：代理不增加功能，而是增加控制
• 例：车票的代售点
• 例：以银行卡代理银行账户，进行收付款

行为模式 Behavioral Pattern

关乎对象之间的职责划分与通讯、如何设计以完成算法。

责任链 Chain of Responsibility

• 又称CoR或Chain of Command
• 在一串不同的Handlers传递Request，每个Handler决定是否处理这个请求、以及是否继续把它传给下一个Handler

可能以两种常见形式存在：

• 一连串的Handler是一连串的检测或处理，每个Handler是一个步骤。如果通过检测或处理成功，则传给下一个Handler，否则直接返回失败。（e.g. 用户认证：检测ID与口令是否匹配，是否命中缓存，IP是否短时间多次试图认证等一连串处理）（e.g. 拨打客服热线->提示按键咨询详情->自动回复答案, 询问是否转人工->人工客服 ->客服转其他专业部门……）
• 一连串的Handler中，请求会被第一个能处理它的Handler处理，并返回。如果一个Handler决定自己不能处理，则传给下一个，直到没有更多Handler，返回失败。（e.g. 一个GUI上的点击事件被哪层Handler捕获、处理）

命令 Command

• 又称Action或Transaction
• 把请求封装成一个包含所有完成请求所需外部信息的类，以便把请求当参数传入方法、建立请求队列、延迟执行、处理异常（无法执行的操作）等等
• 便于对行为进行记录、执行、撤销、事务等处理

解释器 Interpreter

• 给定一种语言和它的语法，定义一个解释器解释语句。
• 例： SQL解析、符号处理引擎
• 实现：构建语法树，并定义终结符与非终结符

迭代器 Iterator

• 提供一种遍历集合的方法，且无序知道该集合的底层表示（不需要知道它是数组、列表、数还是什么别的形式）
• Iterator接口，需要实现next和hasNext方法

中介者 Mediator

• 又称 Intermediary 或 Controller
• 当对象与对象之间存在大量关联时（网状结构），把它们的关联转入一个中介里，解耦成一个星状结构
• 缺点是中介者可能变得很复杂

备忘录 Memento

• 又称 Snapshot
• 存储、恢复对象的某个状态，且无需知道该对象的具体实现
• 备忘录模式使用三个类 Memento、Originator 和 CareTaker
• Memento包含对象的状态/快照，比如某实例序列化后的字符串。这个状态、快照，不可被其他类直接访问。其他类可访问Memento的元信息，如时间戳
• Originator负责创建Memento里存放的快照，需要有对要存档对象的访问权。只有Originator有对Memento的读写权限，可以修改、恢复Memento里存储的状态
• 存放Memento的类叫Caretaker，只负责存放、调取Memento，无权查看里面内容
• 例：编辑器的历史记录，每个操作都是一个Memento，编辑器本身是Originator，历史记录是CareTaker。每次撤销是CareTaker拿出栈顶操作，然后编辑器再（Originator）恢复里面存放的状态

观察者 Observer

• 又称 Event-Subscriber，或 Listener
• 当一个对象被修改时，通知所有依赖它的对象 （即多个对象观察着一个对象的变化）
• 也可以认为是Publisher-Subscriber模式的一种。每次对象更新都向所有订阅者/观察者推送更新消息

状态 State

• 此模式中，类的行为是基于它的状态改变的
• 同一个类状态不同时，仿佛它变成了另一个类
• 状态需要是有穷的，且存在状态间的转化关系
• 例：文档 {草稿，审阅，修订，已发布}
• 例：人 {状态好，状态一般，状态差}

策略 Strategy

• 一个类的行为或其算法可以在运行时更改
• 一个类可以通过很多种不同方式去做某件事。为每个方式分别创建为一个类或函数，并称它们为策略。这个类随着策略的改变而改变做这件事的行为
• 主要用于解决if...else太多的问题
• 例：lambda函数作为策略参数传入方法
• 例：给每个策略一个相同的接口，让原来的类(Context) 存一个策略的引用，并调用策略的那个接口
• 例：路线规划 {公交，驾车，步行，骑行}

模板 Template

• 在一个类里定义某种算法的骨架，然后在子类里实现骨架的具体步骤
• 把算法分割成若干步骤，每个步骤一个方法，然后在一个方法里执行所有的步骤
• 封装不变部分，扩展可变部分
• 父类控制行为，子类控制具体实现

访问者 Visitor

• 将对象与对象上的操作分离
• 如果需要作用在类上的方法与类不怎么相关，为了防止大量这样不相关的方法污染这个类，创建一个访问者类并将方法写入访问者，把原来那个类当参数传入。

public class DataNode1 implements DataNode {
    public string data;
    public SpecialObject1 specialObject1;
    public void processData(){
        // ...
        // 与这个类很相关的方法，所以保留了
    }
    
    /* double delegation
       让类自己来选择当有Visitor来时，执行Visitor里哪个方法来处理自己
       因为Visitor里可能有多个处理不同类的方法，而用户也可能不知道选哪个好 */ 
    public void accept(Visitor v) {
    	v.manageDataNode1(this);
    }
}

public class DataNode2 implements DataNode {
    // 总之就是另一个类
    public string data;
    public SpecialObject2 specialObject2;
    public void processData(){
        // ...
    }
    
    // double delegation
    public void accept(Visitor v) {
    	v.manageDataNode2(this);
    }
}

public class Visitor {
    public static String exportDataAsJSON(DataNode d) {
        // 比如这是一个与DataNode很不相关的方法
        // 用得不多，但偶尔需要
        // 不想让它污染DataNode
    }
    
    public static void manageDataNode1(DataNode1 d) {
        // 专门处理DataNode1类的方法
        d.specialObject1.doSomething();
    }
    
    public static void manageDataNode2(DataNode2 d) {
        // 专门处理DataNode2类的方法
        d.specialObject2.doSomething();
    }
    
    public static void manageDataNode(DataNode d) {
    	d.accept(this); // double delegation
        // 用户也不知道应该用哪个方法的时候
        // 让DataNode自己决定用Visitor的哪个方法吧
    }
}

Ref:

• https://www.runoob.com/design-pattern/design-pattern-intro.html
• https://refactoring.guru/design-patterns

什么是WSL

WSL是Windows Subsystem for Linux的缩写。简单来说，它可以直接在Windows上跑一个Linux（可以自己挑发行版），这样就可以方便的在Windows机子上用Linux系统的软件与工具了。比如在Windows上，安装Docker要求WSL2或者Hyper-V。家庭版的Windows就没得选啦，只能WSL2……

其他选择与比较

在装了Windows的机子上使用Linux的其他选择主要有

• VM（虚拟机）
• 双/多系统

其中VM主流上是使用VMWare（付费）、VirtualBox（免费）、Hyper-V（Windows比较贵的版本限定…）和系统镜像在Windows里配置、启动虚拟系统。硬件足够好的时候可以同时启动多个。

多系统就是直接在硬盘上再多安装一个或多个系统，然后在启动时选择要启动哪个。可以最高效的让系统使用硬件资源，但一次只能开一个系统。安装前需要根据要安装的系统对部分硬盘进行格式化，而安装后也可能因为文件系统的不兼容，切换系统后存在一定的文件读写上的困难（如Windows无法直接读取Linux的各种ext格式，跨系统访问文件后也可能产生一些奇奇怪怪的文件占用和锁）。

WSL与VM

• WSL可以启动得比VM更快，占用资源也比VM更少（WSL2其实是使用VM的，但有针对性优化）
• WSL与Windows的连通性更好，文件系统可以说是的联通的。而VM和Windows是分隔开的，作为沙盒，有更好的安全性，更适合做各种作死的实验……
• VM里可以提供更完整全面的Linux功能，比如图形、音频、硬件支持
• VM里可以跑的不只是Linux，泛用性更好一些

WSL和WSL2的差异

Ref: https://docs.microsoft.com/zh-cn/windows/wsl/compare-versions

• WSL1直接在Windows运行，WSL2是使用VM的。
• WSL2相比WSL1，优化了文件系统性能，也提高了系统调用兼容性（即更高的硬件使用效率）。
• 跨Windows和Linux系统的文件访问上，WSL1更快
• WSL2不支持串行接口，所以要用到外接设备的话，只能WSL1、VM或多系统
• WSL2的内存是随使用状况动态增减的，且目前版本暂不支持在使用中把用于缓存的内存释放回Windows

WSL2安装、启用

前提

Windows 10 的 Build 19041 以上，或Windows 11。

安装

wsl --install

很简单，直接在PowerShell里运行上述，会启用一个默认Ubuntu发行版的WSL2。

需要使用其他发行版的话：

wsl --list --online

可以查看可用的发行版，目前来说有Ubuntu(多个版本), Debian, Kali(专注于搞渗透测试用的那个), openSUSE, SLES。

配置

上一步安装完后，需要重新启动，才可以在开始菜单找到安装好的对应Linux发行版。第一次启用会要求创建一个管理员用户，要记好用户名和密码。

如果安装之前就安装过Windows Terminal，那从开始菜单启动、设置好密码后，从Windows Terminal就也可以找到这个选项了。

Graph

G = (V, E), where V is a set of vertices, and E is a set of edges.

For some reason unknown, people usually use n for the number of vertices, and m for the number of edges. |V|=n, |E|=m

An edge can not point to nowhere. It's always with 2 vertices.

• Complete Graph: A graph where all vertices are connected to each other.
• Connected Graph: A graph where all vertices are connected, not necessarily to each other.
• Acyclic Graph: A graph that has no cycles.

Incident Edges

I(v) = { {x,v} in E}

It's all the edges connected to the particular vertex.

Degree

D(v) = |I(v)|

The number of edges one vertex has.

Adjacent Vertices

A(v) = {x: {x, v} in E}

Path

Path(G₁) = Sequence of vertices connected by edges.

Cycle

Cycle(G₂) = Path with that goes in circle (with common begin and end vertex).

Simple Graph

A graph that has no self-loop or multi-edges.

Subgraph

G' = {V', E'} where V' belongs to V, and E' belongs to E and

if edge (u,v) belongs to E', then both u and v belongs to V'.

• Complete subgraph: A subgraph that is a complete graph
• Connected subgraph: All vertices in the subgraph are connected.
• Acyclic subgraph: A subgraph that has no cycle.
• Spanning Tree: A subgraph of graph G that contains all vertices of G with no cycle.

Observations / Calculations

In a graph with n vertices and m edges:

Minimum Edges:

• In a not-connected graph — 0
• In a connected graph — n-1

Maximum Edges:

• In a simple graph — n* (n-1) / 2
• In a not-simple graph — Infinity

Sum of degree(v) for all v in V = 2*m — or 2*|E|

Acyclic graph with n vertices has (n-1) edges.

Complete graph with n vertices has n* (n-1) / 2 edges.

Graph ADT

Data

• Vertices
• Edges
• Some data structure maintaining structure between vertices and edges

Functions

• insertVertex(K key) — key as label of vertex
• insertEdge(Vertex v1, Vertex v2, K key) — key as label of edge
• removeVertex(K key) or removeVertex(Vertex v)
• removeEdge(K key) or removeEdge(Vertex v1, Vertex v2)
• incidentEdges(Vertex v)
• areAdjacent(Vertex v1, Vertex v2)

-- to be continued

Ref:

• https://www.bilibili.com/video/BV1454y127Lk?p=30

整数

Integer / int

• 32位有符号整数，具体范围是：-2³¹ (-2147483648) ~ 2³¹ -1 (2147483647)
• 大致范围：正负2*10⁹ 不用管溢出，10¹⁰ 不行
• Integer接受null, int不接受
• Integer需要是用equals判断相等（直接用==会判断是否是同一个对象，而非是否数值相等），但>=与<=可以可以正常使用
• Integer.parseInt返回int，Integer.valueOf返回Integer

Long / long

• 64位有符号整数，具体范围是 -2⁶³ (-9223372036854775808) ~ 2⁶³ -1 (9223372036854775807)
• 大致范围：-9*10¹⁸ ~ 9*10¹⁸
• 默认值是0L

Byte / byte

• 8位有符号整数，具体范围是 -128 ~ 127

Short / short

• 16位有符号整数，具体范围是-32768 ~ 32767

小数

Float / float

• 有符号32位IEEE754标准的浮点数
• 符号位(s)：1，指数位(E)：8，尾数位(M)：23
• 值为 (-1)^S * 2^E-127 * (1.M)
• 取值范围：负无穷， -2¹²⁸ ~ -2^-149 ，0，2^-149 ~ 2¹²⁸ ，正无穷
• 范围不连序，无法表示非常接近0的数
• 精度有限，7~8位有效位（7准确，8大部分准确）

Double / double

• 有符号64位IEEE754标准的浮点数
• 符号位(s)：1，指数位(E)：11，尾数位(M)：52
• 值为 (-1)^S * 2^E-1023 * (1.M)
• 区直单位：负无穷， -2¹⁰²⁴ ~ -2^-1074 ，0，2^-1074~ 2¹⁰²⁴ ，正无穷
• 精度有限，能保证15~16有效位

其它

Character / char

• 16位Unicode，范围是0~65535
• 最小 \u0000
• 最大 \uffff

Boolean / boolean

• true / false
• 使用Boolean（带null）的情况，需要在List, Set, Map等中使用时；或以null表示此值是未知的（如，未填写、还没有进行过判断）

Ref:

• https://blog.csdn.net/a327369238/article/details/52354811
• https://www.runoob.com/java/java-basic-datatypes.html
• https://segmentfault.com/a/1190000005015151

Disjoint Sets is the data structure that supports the operation of adding one element (as their own set), [finding the label/canonical_name of one element in a set], and union 2 sets.

It can represents data like:

• Set1 (people whose favorite color's green)
• Set2 (people whose favorite color's blue)
• Set3 (people whose favorite color's red)
• ...

For set S = {S₁, S₂, S₃, ... , S_k}:

• find(S_i) where 1<=i<=k, gives representative integer of the set.

e.g. find(S_i) = min(S)

• join(Set1, Set2): join 2 sets into one. After this operation, find(S_i) where S_i was in Set1, will equal to find(S_j) where S_j was in Set2.

Key Ideas

• Each element exists in exactly one set.
• (Elements in sets are not ordered.)
• (If the element is not integer, hash it to integer first.)
• Every set is an equitant representation: 4 belongs to [0]_R, 8 belongs to [0]_R, then find(4)==find(8) is true (find(4) is 0, and find(8) is 0).

Build

When building disjoint sets:

• Start with everything separated
• Build sets by union the elements

Implementations

Array

Store label of item at array[hash(item)]

• find: O(1)
• union: O(n) – need to go through the array to update labels of one set

Up-Tree

Continue using an array where index is the key. Start all content in array as -1.

The value of array is:

• -1 if we've found the representative element
• The index of parent, if we haven't found the rep.

• find: O(h) where h is the height of the up-tree, and h is only bounded by n (size of the array). So we would like to keep the trees short.
• union: O(1)

Make up-trees faster: instead of storing -1 at roots, store -[number of nodes in tree] and use smart union:

int DisjointSets::find(int i) {
    if(arr_[i]<0) return i; // this is the root
    else return find(arr_[i]);
}

void DisjointSets::union(int r1, int r2) {
    arr_[r1] = r2; // points r1 to r2
}

void DisjointSets::unionBySize(int r1, int r2) {
    // union by size: keeps the number of nodes in a tree smaller
    
    int newSize = arr_[r1] + arr_[r2];
    
    if(arr_[r1]<arr_[r2]) { // r1 has more nodes
        arr_[r2] = r1; // so only -arr_[r2] nodes gets 1 layer higher
        arr_[r1] = newSize;
    } else {
        arr_[r1] = r2;
        arr_[r2] = newSize;
    }
}

void DisjointSets::unionByHeight(int r1, int r2) {
    // union by height: keeps the height of all trees smaller
    
    if(arr_[r1]< arr_[r2]) { // r1 is heigher
        arr_[r2] = r1; // so r1 doesn't get heigher
    } else if (arr_[r1]>arr_[r2]) {
        arr_[r1] = r2;
    } else { // tree gets higher no matter what
        arr_[r1] = r2;
        arr_[r2] -= 1;
    }
}

which makes the height of the trees: O(log(n))

Path Compression

int DisjointSets::find(int i) {
    if(arr_[i]<0) return i; // this is the root
    else {
        int root = find(arr_[i]);
        arr_[i] = root;
        return root;
    }
}

which makes find O(log(n)) amortized.

If we use both smart union and path compression?

The iterated log function:

log*(n) = {

0 , n<=1

1+log*(log(n)) , n>1

}

e.g. What's lg*(2⁶⁵⁵³⁵)?

1: lg(2⁶⁵⁵³⁵) = 65535,

2: lg(65535) = 16,

3: lg(16) = 4,

4: lg(4) = 2,

5: lg(2) = 1

so lg*(2⁶⁵⁵³⁵) = 5

union_find: O(m*α(n)) or O(α(n)) amortized, where n is number of items in Disjoint Sets. For all practice inputs, it's roughly O(1)

Ref:

• https://courses.engr.illinois.edu/cs225/fa2020/
• https://www.bilibili.com/video/BV1454y127Lk?p=29

• insert(value)
• remove()
• isEmpty()

Where value is among int, string, double, char... or objects that supports < operator.

Heap

Unsorted Array: O(1)* insert, O(n) removeMin (need to find min first)

Unsorted Linked List: O(1) insert, O(n) removeMin

Sorted Array: O(n)* insert, O(1) removeMin

Sorted Linked List: O(n) insert, O(1) removeMin

It's easier to removeMin on sorted structures and insert on unsorted structures.

To balance the worst case time to O(lg(n)) insert and O(lg(n)) removeMin, we could use a binary tree.

Definition

(min-)Heap

A complete binary tree t is a min-heap if:

• T = {} or
• T = {r, T_L, T_R} where r is less than roots of {T_L , T_R} and {T_L , T_R} are min-heaps.

Logically it's a tree, and implementation-wise, it's an array.

The heap above in array would be: [1, 4, 5, 12, 7, 6, 8, 13, 14, null, null, 11, null, null, null]

We could define left must be larger or smaller than right, but as long as all roots are smaller than their children, it's a min-heap.

Priority queues are based on heaps.

Operations

• Left child of node[i]: node[2*i]
• Right child of node[i]: node[2*i + 1]
• Parent of node[i]: floor(i/2)

We could also store the number of nodes, n, in node[0], and the above remains the same. Knowing the number of nodes can help you know where in the array is outside of the heap.

How to Insert

template <class T>
void Heap<T>::_insert(const T & key) {
    // check if there's enough space
    if (size_ == capacity) {
        _growArray();
    }
    
    // insert element at the end of array
    item_[++size] = key;
    
    // restore heap property
    _heapifyUp();
}

template <class T>
void Heap<T>::_heapifyUp(size_t index) {
    if(index>1) { // 1 is the root here, as we stored size in 0
        if(item_[index] < item_[parent(index)]) {
            std::swap(item_[index], item_[parent(index));
            _heapifyUp(parent(index));
        }
    }
}

How to Remove

removeMin() is removing root of a min-heap, and removeMax() is removing root of a max-heap.

When removing root:

1. Swap root with the last node.
2. Remove the last node (root).
3. Heapify to restore heap property

template <class T>
T Heap<T>::_remove() {
    T min_value = item_[1];
    item_[1] = item_[size--]; // swap with last and delete
    
    _heapifyDown();
    return min_value; // return original root value
}

template <class T>
void Heap<T>::_heapifyDown(size_t index=1) {
    if(!_isLeaf(index)) {
        size_t minChildIndex = _minChild(index);
        if(item_[index] > item_[minChildIndex]) {
            std::swap(item_[index], item_[minChildIndex]);
            _heapifyDown(minChildIndex);
        }
    }
}

How to Build a Heap

buildHeap - heapifyUp: O(n*log(n))  – each insert is O(log(n))

void Heap<T>::buildHeap() {
    for(unsigned i=2; i<= size_; i++) {
        heapifyUp(i);
        // takes O(n logn)
    }
}

buildHeap - heapifyDown: O(n)  – takes time of O(sum of the height of all sub trees)

void Heap<T>::buildHeap() {
    for(unsigned i=parent(size_); i>0; i--) {
        heapifyDown(i);
        // takes O(n)
    }
}

Prove heap building running time:

• S(h): Sum of heights of all nodes in a complete tree of h
• S(0) = 0
• S(1) = 1 + 0 + 0 = 1
• S(2) = 2 + 1 + 1 = 4
• ....
• S(h) = h + 2 * S(h-1) = 2^(h+1) -h - 2
• Since h<=lg(n),
• O(2^(lg(n)+1) - lg(n) -2) = O(n-2-lg(n)) = O(n)

Ref:

• https://regexcheatsheet.com/
• https://www3.ntu.edu.sg/home/ehchua/programming/howto/Regexe.html

ref: Common Fonts for Windows & MAC

‌‌

Serif

Serif 来自古荷兰语的“短线”、“线”。Serif 指衬线字体，即在字母的开始、结束的地方有额外装饰的字体。

衬线字体的由来：据说是来自对笔刷、雕刻字体的模仿。衬线即用刷子刷字时，为了让字母的开始、结尾整齐无毛刺，而垂直书写方向进行划线、停顿等而留下的痕迹。以及雕刻时下刀、收刀、或为了遮盖结尾不整齐而留下的痕迹。

下图中箭头指的就是衬线。

较常见的 serif 字体有 Times (即Time Roman), Times New Roman, Georgia, Palatino, Bookman等。

Sans Serif

Sans 是法语的“没有”。Sans-Serif 指无衬线字体，如上图所示。

较常见的 sans-serif 字体有 Helvetica, Arial, Verdana, Tahoma, Segoe UI等。此外，安卓上还常见Roboto和Droid Sans。

Monospace

每个字符占得空间都一样大，无论内容是什么，上下两行的字母间都能两两对齐。经常用于显示程序，字符画等。

较常见的 monospace 字体有 Courier, Courier New, Andale Mono等。

哪里都能放心使用的英文字体

ref: https://web.mit.edu/jmorzins/www/fonts.html

The fonts that are most safe to use are（基本哪里都能用的系统自带）:

• Arial / Helvetica
• Times New Roman / Times
• Courier New / Courier

Other options that usually work cross-platform are（其他跨平台选择）:

• Palatino
• Garamond
• Bookman
• Avant Garde

Fonts that work on Windows and MacOS but not Unix+X are（Window/MacOS自带，Unix+X没有）:

• Verdana
• Georgia
• Comic Sans MS
• Trebuchet MS
• Arial Black
• Impact

中文字体

兼容问题

很可惜，各种操作系统中并没有一个能通用的中文字体。

对 Windows:

• Vista之后：Microsoft Yahei，微软雅黑
• Vista之前：SimSun (中易宋体)

对 Mac OS 和 iOS

• ‌Hiragino Sans GB （冬青黑体/苹果丽黑）
• 华文黑体

对Android:

• Droid Sans Fallback

对Linux各发行版……没辙了，只能试试看对方有没有安装开源中文字体

• WenQuanYi Micro Hei （文泉驿微米黑）（这个最常见了）
• Source Han Sans （思源黑体）

且 &  Bitwise AND

按位且。向右对其，对其后两位都在且两位都为1的时候才为1。

例：1110 & 0001 = 0000，1111 & 1101 = 1101， 1010 & 1001 = 1000

常见用途：掩码，取某个数第n位（& 除了第n位是1，其他都是0的数，然后除以n个2）, 判断一个数的奇偶（&1==1是奇数）

或 |  Bitwise OR

按位或。向右对其，对其后有一位为1就为1

例：0000|1111 = 1111， 0101 & 1010 = 1111，0010 & 1010 = 1010

非 ~  Bitwise Complement/NOT

按位取反

例： ~0000 = 1111，  ~1010 = 0101， ~1110 = 0001

注意：在大多语言的大多数据类型里，数都不只4位，高位的0取非后都会变成1

如，java中：

1: 00000000000000000000000000000001

~1(-2): 11111111111111111111111111111110

1000: 00000000000000000000001111101000

~1000(-1001): 11111111111111111111110000010111

public static void printAllBits(int t){
	System.out.println(t);
	int[] res = new int[32];
	for(int i = 0; i<32; i++){
		res[i] = t&1; // 取末位
		t>>=1; // 右移
	}
	for(int i=31; i>=0; i--){ //从高位开始打印
		System.out.print(res[i]);
	}
	System.out.println();
}

异或 ^ Bitwise XOR

按位异或。向右对其，对其的两位不同时取1，相同时取0

例：1111^0000 = 1111,  1010^0001 = 1011,  0001^0101 = 0100

常见用途：抵消相同的数，判断两数符号是否相同（异或后看符号位）

乘除和位移

十进制和二进制

二进制：11101 即 1*2⁴ + 1*2³ + 1*2² + 0*2¹ + 1*2⁰

十进制： 2⁴ + 2³ + 2² + 0 + 2⁰ = 16+8+4+0+1 = 29

乘法和左移

例：29 (11101) * 4 (10)

= (1*2⁴ + 1*2³ + 1*2² + 0*2¹ + 1*2⁰)* 2²

= (1*2⁶ + 1*2⁵ + 1*2⁴ + 0*2³ + 1*2²) + (0*2¹ + 0*2⁰)  

（即二进制 1110100，11101左移两位）

所以，a * 2ⁱ == a<<i

例： 29 (11101) * 7(111)

= (1*2⁴ + 1*2³ + 1*2² + 0*2¹ + 1*2⁰) * (1* 2² + 1* 2¹ + 1* 2⁰)

= (29<<2) + (29<<1) + 29

public Class MultiplyByShift {
    public static int multiply(int a, int b){
    	// 假设没有溢出
        
        int res = 0;
        boolean negative = (a^b)<0; // 异或后只看最高位（符号位）
        // 若a,b中只有一个负数，则最高位0^1 = 1，结果为负
        
        int m = a<0? -a: a;
        int n = b<0? -b: b;
        
        int i = 0;
        
        while(n>0){
            int t = n & 1; // n的最后一位
            n >>= 1;
            if(t==1) res += (m<<i);
            i++;
        }
        
        return negative? -res: res;
    }
}

除法和右移

例：101(1100101)/4(10)

= (1*2⁶ + 1*2⁵ + 0*2⁴ + 0*2³ + 1*2² + 0*2¹ + 1*2⁰) / 2²

= 1* 2⁴ + 1*2³ + 0*2² + 0*2¹ + 1*2⁰ + 0*2^-1 + 0*2^-2

在整数范围为 1* 2⁴ + 1*2³ + 0*2² + 0*2¹ + 1*2⁰ 即11001

所以a/2^b = a>>b

通过位移来做除法时，如果除数不是2的幂，我们可以依次试探每一位

例：101(1100101)/13(1101)

13(1101)右移1位，26(11010)<=101;

右移2位, 52(110100)<=101;

右移3位，104>101;

所以结果第3位是0，第2位是1

把101拆成 (1*13*2²) + 49，继续试探49

49 = (1*13*2¹)+ 23,  23 = (1*13*2⁰ +22)

所以101/13 = 二进制的111，即7

public class DivideByShift {
    public static void main(String[] args) {
        System.out.println(divide(1234567,123)+","+1234567/123);
    }
    
    public static int divide(int a, int b){
    	// 假设没有溢出
        boolean negative = (a^b)<0;
        int m = a<0? -a:a;
        int n = b<0? -b:b;
        
        int res = 0;
        
        while(m>=n){
            int i=0;
            while((n<<i) <=m) i++;
            i--;
            res += (1<<i);
            m -= (n <<i);
        }
        
        return negative? -res: res;
    }
}

谈谈溢出（Java的情况）

Java的Integer的取值范围是-2147483648到2147483647。

向下溢出

Integer.MIN_VALUE，即-2147483638，是个比较烦的数，因为取负它会溢出。Integer.MIN_VALUE = -Integer.MIN_VALUE = -2147483638.... 所以想要存它的绝对值，就只好用Long了。

正确的得到Integer.MIN_VALUE的办法：

Long abs = -(Long)Integer.MIN_VALUE; // 一定要先转换成Long再取负

Java里，负数移位不会变成正数，但是可能变成0

向上溢出

使用*做乘法时，先乘再判断是否符号变化是不靠谱的，因为乘一次可能产生2次溢出抵消符号变化。

使用左移和+做乘法时，每次相加后检查符号位改变是可以的。

A hash table has:

• A hash function h(k)
• An array
• Something that handles collisions and else

Dictionary in Python is a hash table.

Hash Function

A function that maps keys from key-space to an integer bounded by array size.

A hash function consists of 2 parts:

1. Takes key and produce some integer
2. A compression: shrinks large integer into range of array  (almost always mod N)

Characteristics of a good hash function:

• O(1) computation time
• Deterministic (it is not random): for k₁ = k₂ , h(k₁) = h(k₂)
• Satisfy SUHA (Simple Uniform Hashing Assumption)

SUHA:

• Keys are distributed uniformly in array.
• For i ≠ j, P(h(i)=h(j)) = 1/N, where N is the size of array (choosing index for i like randomly choosing an index of the array).
• (Hash by mod is not SUHA)

Collision Handling

Separate Chaining (open hashing)

Store linked lists (a pointer) in array.

For example: |S|=n, |Array| = N

When collide, create a new node in the list in array[h(key)].

When hashing by mod:

• Insert: O(1)
• Find/Remove: O(n)  (Find/Remove: worst case collision)

When hashing satisfy SUHA:

• insert(O1)
• Find/Remove: O(n/N).

n/N is called load factor, it describes how efficiently the array is used.

Probe-based Hashing (closed hashing)

Use linear probing: when collide, just put into the next available space.

To make every key into array, size of array size should be no smaller than size of key space.

When find, calculate h(key) and try the value at that index. If it is not equal to key, find next, loop until finding the key in the array.

When hashing by mode:

• Insert: O(n)
• Find/Remove: O(n)

When SUHA:

• Insert: O(n/N)
• Find/Remove: O(n/N)

(Basically, no one uses this...)

Double Hashing (closed hashing)

If hashing once, collide, hash again, until finding available space.

• S = {k₁, k₂, ... , k_n},  |S| = n
• |Array| = N
• h₁(k) = k % N
• h₂ = 5 - (k%5)
• h(k,i) = (h₁(k) + i*h₂(k))%N, where i is the number of tries before finding available space
• N and all h₂ values should share no factors. Thus, we'd like N to be a prime

Comparisons

The expected number of probes for find(key) under SUHA,

where |Key Space| = n, |Array| = N,  

and a is load factor: (n/N)

Linear Probing:

• Successful: (1+1/(1-a))/2
• Unsuccessful: (1+1/(1-a))²/2

Double Hashing:

• Successful: 1/a * ln(1/(1-a))
• Unsuccessful: 1/(1-a)

Separate Chaining:

• Successful: 1+a/2
• Unsuccessful: 1+a

When heavily loaded, avoid linear probing and double hashing. When hash is SUHA and load factor is less than 0.75 (75% of the array space used), then linear probing and double hashing are pretty fast (double hashing is still generally faster than linear probing when a is under 0.75). When light loaded, these 2 can be faster than separate chaining.

When hash function is bad (not SUHA), usually separate chaining is better.

ReHashing

When having too many keys, and the array is filled (n/N>some constant value), we could expand array length to 2*N or next prime.

When changing N, as hash function is updated, we need to calculate new indexes for old keys in the new (expanded) array. This is called rehashing.

Rehashing takes O(n), but the chances we need to rehash is O(1) amortized, expected, given SUHA hashing.

Summary

Better Collision Strategy

Big records: separate chaining

Structure speed: double hashing

Constraints exist on hashing but not BSTs

• Amortized
• Probalistic runtime
• SUHA

Hash table only support exact matches, while BST supports range find.

In C++, map is implemented with red-black tree (it supports range find), and unordered_map is implemented with hashing.

Ref:

• https://courses.engr.illinois.edu/cs225/fa2020/
• https://www.bilibili.com/video/BV1454y127Lk?p=26

Short for k-dimension-tree. When search is not enough in one dimension, Kd-Trees may be used.

e.g. Search in 2D. Given x₁, x₂, y₁, y₂, find all points within the range.

If we don't want to go through all of the points – O(n) time

then, we could have a tree, where each root for sub-tree splits points in one axis.

For the same sets of points, there are multiple ways to build a Kd-Tree.

For the example above, P₁ splits y-axis. All nodes in sub-tree on left are with Y less than Y_P1 , and all nodes in sub-tree on right are with Y larger than Y_P1 .

B-Tree

Motivation

When data set is huge, we can't always expect that we could fill all of them in main memory. They could be stored in disks, cloud, pingfs, etc.

If we have large seek time for data (e.g. all nodes are on different servers so the time going from one node to another is significant), then we would want to minimize the number of reads. In order to do that:

• Tree must be short
• Find relevant data
• Work local to a node is fast –> Do more things in a single node and decide where to go next. Have more children and larger nodes.

Definition

A B-Tree of order m:

• Is an m-way tree
• Will have (m-1) or less keys and 0~m children per node
• All keys within a node are ordered (sorted array)
• All leaves hold no more than (m-1) keys
• All internal nodes have exactly one more child than keys
• Root node can be a leaf or have [2,m] children
• All non-root, internal nodes have [ceil(m/2),m] children
• All leaves are on the same level
• Height is O(log_m(n)) – meaning the number of seeks will be O(log_m(n))

Build a tree that uses [1 network packet (TCP 1500 bytes)] / [1 disk block (512/8192 bytes)] per node.

Example of B-Tree operations: https://www.cs.usfca.edu/~galles/visualization/BTree.html

B-Tree Insertion

When a B-Tree node reaches m keys:

Take the key in middle, push it up. Create 2 new nodes from the rest of this node and link to the one we just pushed up. Then insert.

B-Trees are built bottom up. When reaching m keys, they push nodes up.

Leaves of B-Tree are all at the same level.

B-Trees are perfect trees (perfect tree: all leaves have the same distance to root).

Leaves in B-Tree has at least ceil(m/2)-1 keys.

B-Tree Search

bool BTree::_exists(BTree &node, const K &key) {
    unsigned i;
    for( i=0; i<node.keys_ct_ && key<node.keys_[i]; i++) {
        // i < number of keys in node
        // find the first i, where key >= node.keys[i]
    }
    
    if(i<node.keys_ct && key == node.keys_[i]) {
        // if i is not out of the array, check if we've found the key
    	return true;
    }
    
    if(node.isLeaf()) { // base of recursion
        // if this is a leaf, and key is not here
        return false;
    } else {
        BTreeNode nextChild = node._fetchChild(i);
        // child could be in cloud -- anyway, handle it with the func
        return _exists(nextChild, key);
    }
    
}

ref: https://courses.engr.illinois.edu/cs225/fa2020/

ref: https://www.bilibili.com/video/BV1454y127Lk

搞一只看版猫到博客居然比搞一只看板娘还要麻烦……囧

虽说最后猫是放出来了，但八成还是哪里没用对吧，编译出来动辄四五百kb的js文件（虽然确实是没有特别狠的压缩，uglify全开之后运行会出错……），还有官方原版Demo直接编译出的1.6MB js+sourcemap（不含模型与图片），怎么看怎么别扭（捂脸）…… 这个只有短短5页的官方文档也是没说多少东西，也可能是因为大部分用户都是开发手机原生应用，而不是网页的吧。

要找教程的话，往这边走吧~

其他人努力研究的v4 SDK教程：

• https://blog.csdn.net/qq_37735413/article/details/119413744 (让我意识到了模型使用非标准参数名的问题)

还不清楚是哪个版本，但是文档链接很多：

• https://github.com/stevenjoezhang/live2d-widget

应该是旧版本SDK的应用：

• https://blog.csdn.net/qq_37735413/article/details/104769280
• https://github.com/EYHN/hexo-helper-live2d

Live2D

就是目前的很多手机游戏里2D 动态立绘背后的那个技术，或者说，一套专门应对活动幅度较小的类生物的2D 动画生成技术。我的直观印象是一套可以灵活控制的形变系统 + 物理 + 模型和动作管理。

Live2D Editor & Sample Data (hijiki)

Live2D 官网大多的模型样例（除了有三方版权的）大多是对一般使用者和小型公司免费的。这只猫就是tororo&hijiki包里的其中一只。

使用

使用Live2D需要有：

1. 模型： 包括texture、部件、参数（上面绑有不同部件的关键帧）、动作（部件、组件参数变化）
2. SDK

模型

Runtime里的model3.json长这个样子：

其中.2048文件夹里是材质png图片，

motion文件夹是每个动作的json（每个动作，各部件网格顶点位置变化等），

cdi3是参数的描述的样子（但也并不是到default parameter的mapper...），

moc3是模型文件，里面包含部件和参数的设定，

model3是对模型的描述和配置，

physics3是一些物理（如头发摆动？）和动画的参数，

pose3似乎是同一部位的多个图片（如无法靠单一图片形变做到的，同一部件的不同状态）

杂谈

说到动画，就想跟死掉的Flash比较一下。小学的时候，Flash在我心目中的一大黑科技就是补间动画。给出形状A和形状B，计算从A变成B之间的过程并自动填补关键帧。但除非图形规则，这个生成的补间对用户来说基本是不可控的。中间过程可能生成得很自然，也可能先从A扭曲成奇怪的图案，再变成正常的B。当然，这种情况，大家一般会删了补间，在中间加几个缓冲的关键帧（我们预期的中间状态），让帧与帧之间的差异更小，变化更规则，再创建补间。Live2D 这边，通过在图形上创建由多个三角形组成的多边形网格（一堆三角形可以组合出各种多边形），拖拽网格上节点造成形变生成关键帧。然后因为这些形变都被这些节点的移动描述了，补间的生成就会很规则。

印象中与Flash几乎同期的，还有一个基于骨骼生成补间的Moho。查了下它还好好活着……是在图片上创建并绑定骨架，通过拖拽骨架顶点对图片进行形变来创建关键帧，然后创建补间。感觉很像是Flash和Live2D的中间状态。

Live2D SDK for Web

模型自定义参数名的问题

比较快速但一点也不正规的操作：改Framework/src/cubismdefaultparameterid.ts

附camel case与snake case可以放进浏览器console转换：

/*
目标参数名 json示例 (猫的模型tororo和hijiki使用的参数命名）
{
    "ParamAngleX": "PARAM_ANGLE_X",
    "ParamAngleY": "PARAM_ANGLE_Y",
    "ParamAngleZ": "PARAM_ANGLE_Z",
}


默认参数名json示例
{
    "ParamAngleX": "ParamAngleX",
    "ParamAngleY": "ParamAngleY",
    "ParamAngleZ": "ParamAngleZ",
}
*/

//主要是需要这个，因为默认是camel case，但有些模型是snake case
function camel_to_snake(name) {
  return name.replace(/([A-Z])/g,"_$1").toLowerCase().substring(1);
}

for(k in json){
	json[k] = camel_to_snake(json[k]).toUpperCase();
}


function snake_to_camel(name) {
	return name.split("_")
        .map(x => x.slice(0,1).toUpperCase()+
             x.slice(1).toLowerCase()).join('');
}

当然了，如果压根就不在所谓“标准参数”列表里，那也就没什么简便办法了。

事件监听与动作的问题

总之，在官方Github的例子里，事件监听在lappdelegate.ts，如下部分。自行按需改动，比如把canvas.ontouchmove改成document.ontouchmove之类的。

if (supportTouch) {
      // タッチ関連コールバック関数登録
      canvas.ontouchstart = onTouchBegan;
      canvas.ontouchmove = onTouchMoved;
      canvas.ontouchend = onTouchEnded;
      canvas.ontouchcancel = onTouchCancel;
} else {
	...
}

动作在lapplive2dmanager.ts里（这个onTap这里）：

public onTap(x: number, y: number): void {
    if (LAppDefine.DebugLogEnable) {
      LAppPal.printMessage(
        `[APP]tap point: {x: ${x.toFixed(2)} y: ${y.toFixed(2)}}`
      );
    }

    for (let i = 0; i < this._models.getSize(); i++) {
      if (this._models.at(i).hitTest(LAppDefine.HitAreaNameHead, x, y)) {
        if (LAppDefine.DebugLogEnable) {
          LAppPal.printMessage(
            `[APP]hit area: [${LAppDefine.HitAreaNameHead}]`
          );
        }
        this._models.at(i).setRandomExpression();
      } else if (this._models.at(i).hitTest(LAppDefine.HitAreaNameBody, x, y)) {
        if (LAppDefine.DebugLogEnable) {
          LAppPal.printMessage(
            `[APP]hit area: [${LAppDefine.HitAreaNameBody}]`
          );
        }
        this._models
          .at(i)
          .startRandomMotion(
            LAppDefine.MotionGroupTapBody,
            LAppDefine.PriorityNormal,
            this._finishedMotion
          );
      } else {
        if (LAppDefine.DebugLogEnable) {
          LAppPal.printMessage(
            `[APP]hit area: None`
          );
        }
        this._models
          .at(i)
          .startRandomMotion(
            LAppDefine.MotionGroupTap,
            LAppDefine.PriorityNormal,
            this._finishedMotion
          );
      }
    }
  }

也可以在监听器里直接这样触发动作的更新

let instance = LAppLive2DManager.getInstance();
instance._models.at(0).startRandomMotion(
	LAppDefine.MotionGroupTap, 
    //其实就是model3里的动作, 比如"Tap", "Flick"
	
    LAppDefine.PriorityNormal, 
    //更换动作的优先级
	
    instance._finishedMotion 
    //回调，其实就在console打印了个 Motion Finished
);

应用于Ghost CMS的问题

由于目前Ghost CMS不支持图片、js、css以外的静态资源，模型是不可以直接打包在Theme里的，不然读取json和moc文件会直接301然后404。

解决方案

需求：让脚本能够成功的加载模型（静态资源，.json, .moc, .png等等），最好还不要跨域。

情况：Ghost官方估计不会这么做的，它们都声明过连媒体库都不做。

暴力的办法：反正本来网站也是nginx反代的，在相同域名下直接多配置一个location在根之前进行匹配，用于加载模型。

location /live2d/ {
    root /somepath/somepath;
    autoindex on;
}

如上，把模型放在/somepath/somepath/live2d目录下，然后在themes的js里从/live2d/加载模型就行了。

A BST (binary search tree) is a tree T such:

• T = {} or
• T = {r, T_L, T_R} where all nodes in T_L has keys less than r, all nodes in T_R has keys greater than r, and T_L and T_R are BSTs.

// BST.h
#pragma once

template <typename K, typename V>
class BST {
    public:
        BST();
        void insert(const K & key, const V & value);
        void remove(const K & key);
        K find(const K & key) const;
        
    private:
        struct TreeNode {
            TreeNode *left, * right;
            K key;
            V value;
            TreeNode(const K & k, const V & v): key(k), value(v), left(NULL), right(NULL){}
        }
        
        TreeNode *root_;
    
}


// cpp
template <typename K, typename V>
V BST::find(const K & key) {
    TreeNode * node = _find(root_,key);
    if(node) {
        return node->value;
    } else {
        // deal with null case
        return V();
    }
}


template <typename K, typename V>
TreeNode *& _find(TreeNode *&node, const K & key) {
// returns a pointer reference of a treenode
// so if we want to find then update/insert, we can do it

    if(node == nullptr) { return node;} // can't find the key
    if(node->k==key) { // find exactly the key
        return root;
    } else {
        if(node->k > key) {
            return _find(node->left, key);
        } else {
            return _find(node->right, key);
        }
    }
}


template <typename K, typename V>
void BST::insert(const K & key, const V & value) {
	_insert(root_, key, value);
}

template <typename K, typename V>
_insert(TreeNode *& root, const K & key, const V & value) {
    TreeNode *& loc = _find(root,key);
    if(loc == nullptr) {
        loc = new TreeNode(key, value);
    }
}

BST Remove:

IOP (In-order predecessor): left tree right most child. Largest node that is less than root.

IOS (In-order successor): right tree left most child. Smallest node that is larger than node.

When removing a node in BST:

• find the key
• find IOP or IOS
• swap node with key and IOP/IOS
• delete the node with key (it's 0-child delete now)

BST Worst Cases:

• find: O(h)
• insert: O(h)
• remove: O(h)   —> O(h)+O(h)  (find the node to remove, and find it's IOP/IOS)
• traversal: O(n)

For all BST, Lower bound: O(lg(n)) (when it is balanced), Upper bound: O(n) (when it is like a stick)

For all BST with n nodes (randomly sequenced), the average height of the trees is lg(n)

A balanced BST (O(h) for find, insert, delete, where h=lg(n), and O(n) for traverse) is a better choice for dictionary than sorted array (O(n) for insert, delete, traverse, O(lg(n) for find) and sorted list (O(n) for find, insert, delete, traverse).

Height Balanced Tree

Height Balance: b = height(T_R)-height(T_L)

A tree T is height balanced if :

• T = {}
• T = {r, T_L, T_R}, |b|<=1, and T_L and T_R are balanced trees

A complete tree is always balanced.

BST Rotation

• 4 kinds of rotations (L, R, LR, RL) (LR & RL for elbows)
• All rotations are local (subtrees are not impacted)
• All rotations are constant time: O(1)
• BST property maintained

Goal: produce trees of height h=O(log(n)) using only O(log(n)) time for each operation.

We call these trees AVL (Adelson-Velokii-Landis) trees.

AVL Tree

Three issues for consideration:

• Rotations: to fix imbalance
• Maintaining height: track height of each node
• Detect imbalance: when a node become out of balance

When a new node is inserted, only when the tree becomes taller, it becomes imbalanced.

Insert into an AVL tree:

• Insert at proper place – O(h)
• Check for imbalance – O(1)
• Rotate if necessary – O(1)
• Update height

struct TreeNode {
    T key;
    unsigned height;
    TreeNode *left;
    TreeNode *right;
}


template <class T>
void AVLTree::_insert(const T &x, TreeNode<T> *& t) {
    if(t==NULL) { // base case. insert into empty tree
        t = new TreeNode(x,0,NULL,NULL);
    }
    else if(x < t->key) { // insert into left sub-tree
        _insert(x, t->left);
        int balance = height(t->right) - height(t->left);
        // helper func to handle when t doesn't have a left or right child
        int leftBalance = height(t->left->right) - height(t->left->left);
        
        if(balance == 2) { // out of balance
        	if(leftBalance == -1) { // a stick
            	rotateR(t);
            }
            else { // elbow
            	rotateLR(t);
            }
        }
    }
    else if(x > t->key) { // insert into right sub-tree
        _insert(x, t->right);
        int balance = height(t->right) - height(t->left);
        int rightBalance = height(t->right->right) - height(t->right->left);
        if(balance == 2) { // out of balance
            if(rightBalance == 1) { // a stick
            	rotateL(t);
            } else { // elbow
                rotateRL(t)l
            }
        }
    } 
    
    t->height = 1 + max(height(t->left), height(t->right));
}

Analysis

Find runs at O(h)

Insert runs at O(h) find + O(1) add + O(1) rebalance, total O(h)

Remove runs at O(h) find + O(h) find IOP/IOS + O(1) remove + h*O(1) rebalance, total O(h)

Where h is O(log(n)).

Minimum number of nodes

Let N(h) be smallest number of nodes in an AVL tree of height h:

N(-1) = 0,

N(0) = 1,

N(1) = 2,

...

N(h) = 1 + N(h-1) + N(h-2),

which is, root + a sub tree of (h-1) and a sub tree of (h-2), balance = 1 or -1

So, N(h) > N(h-1) + N(h-2) >= 2*N(h-2) >= 2^h/2  (when h>=1)

An AVL tree of height h has at least 2^h/2 nodes.

Invert it:

n >= N(h) > 2^h/2,

n>= 2^h/2

log(n) >= h/2

h<= 2 log(n) — where log(n) > 0

So for an AVL tree, h=O(log(n))

Summary of Balanced BST Trees

AVL

• Max height: 1.44 * lg(n)
• Rotations:
• find – 0 rotation
• insert – 1 rotation at most (LR, RL count as 1)
• remove – h rotations at most, where h is O(log(n))

Red-Black Tree

• Max height: 2 * lg(n)
• Constant numbers of rotations:
• insert – 2 rotations at most
• remove – 3 rotations at most
• Works better with modern hardware (more caches and predicters)
• (C++'s standard map is Red-Black tree)

// map API
map<string,int> grades;
//....
grades["someone"] = 100;
cout << "Someone's grade is: " << grades["someone"] << endl;
grades.erase("someone");

Pros of Cons of BST

Pros

Running time O(log(n)), improvement over lists and arrays as dictionary.

Good for:

• Approximate find: Each step (the sub-tree) is closer to target
• Range and nearest neighbor find

Cons

• Never O(1)
• In-memory requirement: following pointer is O(1) and fast -> assume everything is in memory (if it points to resources elsewhere, like on another computer or database over Internet, it could be slow)

ref: https://courses.engr.illinois.edu/cs225/fa2020/

性质

稳定性

按比较的标准，两元素相等时，不会改变这两个元素的相对顺序。

意义是，在按某一标准进行排序时，不打乱按其他标准已经排好的顺序。

例：（A, 2), (B, 1), (C, 3), (D, 2) 本身已经按字母排序，若对数字排序，非稳定的排序可能会将D放到A前面，而稳定的排序可以确保A, D间顺序不变。

就地性

是否需要额外的空间存放辅助数组，还是直接在要排序的数组上操作就可以。

另外，无关就地性，如果希望输入的数组不要被改动，可以在排序前先复制数组再操作。

// 例，利用Arrays.copyOf
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

自适应性

时间复杂度受元素分布影响。

能找到的相关资料不多，可能这个说法不太常见，但用处应该是，在已经近似是有序（知道无序元素并不多）的条件下，有自适应性的排序算法拥有更低的时间复杂度。

比较类

基于元素之间的比较（>, <, =）来进行排序。

速度

一般情况下：快速>归并>希尔>堆

数据规模		快速排序		归并排序		希尔排序		堆排序
1000万		0.75		1.22		1.77		3.57
5000万		3.78		6.29		9.48		26.54
1亿		7.65		13.06		18.79		61.31

冒泡排序

{无序，有序}，每次比较无序部分中相邻的两个元素，顺序错误就交换过来。每轮循环可以确保一个最大/最小被找到并放在最边缘（成为整个序列后方有序序列的一部分）。

public static void bubbleSort(int[] arr) {
	for (int i = 0; i < arr.length-1 ; i++) {
		boolean flag = true; // 跳出旗帜
		// 如果一轮内循环中没有进行过交换
		// 说明前方的顺序已经全部是正确的，可以停止继续排序了

		for (int j = 0; j < arr.length - i; j++) {
			// i每加1，后面就多一位已经排好的，不许要进入下轮内循环
			if (arr[j] > arr[j + 1]) {
				int tmp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = tmp;

				flag = false; // 标记有过交换
			}
		}

		if (flag) { // 没有交换，已经排好了
			break;
		}
	}
}

选择排序

每次循环都找到最大/最小元素的位置，然后交换到开头/结尾。

public static void selectionSort(int[] arr) {
	for (int i = 0; i < arr.length - 1; i++) {
		// i 为第(i+1)小元素应该在的位置
		// arr.length - 1 因为后面只剩一个元素的时候就不用交换了。。。
		
		int min = i; // 用于记录最小元素位置，之后交换到位置i

		for (int j = i + 1; j < arr.length; j++) {
			if (arr[j] < arr[min]) {
				min = j;
			}
		}

		if (i != min) {
			int tmp = arr[i];
			arr[i] = arr[min];
			arr[min] = tmp;
		}

	}
}

插入排序

类似整理扑克牌，把整个数组看做 {有序序列，无序序列} （一开始只把第一个元素看做有序，后面全是无序）。从无序序列里拿东西建造前面的有序序列，直到无序序列消耗完。

每次把无序序列中第一个元素插进有序序列它该在的地方（有序序列长度+1，无序序列长度-1）。

public static void insertionSort(int[] arr) {
	for (int i = 1; i < arr.length; i++) {
		// 第0个跳过，直接看做只有1个元素的有序序列
		// 无序从第1个开始
		int tmp = arr[i]; 

		int j = i; 
		while (j > 0 && tmp < arr[j - 1]) {
			// 拿着tmp那个无序，把比它大的有序往右移腾地方
			arr[j] = arr[j - 1]; 
			j--;
		}

		if (j != i) {
			arr[j] = tmp; // 把tmp插过去
		}

	}
}

希尔排序

每次以一定的步长把整个序列划分成若干子序列，分别对这些子序列进行插入排序，并逐渐减小步长，直至最后步长为1。

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

例，步长为5时，子序列分别为：

[3, 1], [5,6], [9,7], [2,8], [4,10]，分别排序后 --> [1,3], [5,6], [7,9], [2,8], [4,10]

此轮排序后--> [1,5,7,2,4,3,6,9,8,10]

（如每次步长缩短至原来的一半后向下取整）缩短步长至2，此时子序列为：

[1,7,4,6,8], [5,2,3,9,10]， 分别排序后 --> [1,4,6,7,8], [2,3,5,9,10]

此轮排序后 --> [1,2,4,3,6,5,7,9,8,10]

最后经一轮步长为1的插入排序

public static void shellSort(int[] arr) {
    int length = arr.length;
    int temp;
    for (int step = length / 2; step >= 1; step /= 2) {
        for (int i = step; i < length; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

• 希尔排序中比较糟糕的情况：临近几轮step互为倍数的情况，会导致上一轮已经排好序的数字们又被归在同一组进行排序，降低效率

快速排序

使用分治法（Divide and conquer）的一种排序，速度通常较快。每次选择一个值为基准（一般直接取序列第一个值），把比它小的全挪动到它左边。然后，以这个值为分界，对它左边、右边的序列分别进行快速排序（递归），直到每个要排序的序列长度都为1，就排好了。

public class QuickSort {
    public static void main(String[] args) {
    	// 实验
        int[] arr = {3,1,8,2,4,5,2,-1,0,9,10,-2,-5,4,6};
        sort(arr);
    }
    
    public static int[] sort(int[]arr){
    	quickSort(arr,0,arr.length-1);
        return arr;
    }
    
    private static void quickSort(int[] arr, int left, int right) {
        if(left<right){// 则包含left,right的序列长度>=2
            int partition_index = partition(arr, left, right);
            quickSort(arr,left, partition_index-1);
            quickSort(arr,partition_index+1, right);
        }// 即，当每个子序列只剩1个元素，结束排序
    }
    
    private static int partition(int[] arr, int left, int right) {
        //int left_ = left, right_ = right; // 只是为了打印，不要在意
        
        int base = arr[left]; // 基准值
        while(left<right){
            while(left<right && arr[right]>=base){
            	// 从右向左找小于base的元素
                // 大于base的不管，直接跳过
                // 如果一路都没有小于base的，内外循环就都结束了。。。
                right--;
            }
            arr[left] = arr[right]; //换到最左边（base的位置）
            while(left<right && arr[left]<=base){
            	// 从左往右找大于base的元素
                left++;
            }
            arr[right] = arr[left]; // 放到刚才刚才那个小于base元素的位置
        }
        arr[left] = base; // 出循环，left,right指向同一个位置
        // 左边没有比base大的,右边没有比base小的
        
        /*
        System.out.println("---partition----base:"+base+"(pos:"+left+")");
        System.out.println("---range: pos"+left_+"(val in outcome:"+arr[left_]+
                           ") ~ pos"+right_+"(val in outcome:"+arr[right_]+")");
        System.out.println("---outcome---"+Arrays.toString(arr));
        System.out.println(); // 打印结果（快速排序的中间过程）
        */
        return left; // 返回base/partition的位置
    }
    
}

• 每次执行QuickSort其实是把基准值放在它正确的位置（左边所有数比它小，右边所有数比它大，那么它一定已经在正确位置上）

归并排序

1. 把整个无序序列里的元素拆成一个一个的
2. 拿两个单个元素组成有序序列
3. 拿两个由两个单个元素组成有序序列组成有序序列
4. 拿两个由两个有序序列组成的有序序列组成有序序列
5. 拿两个由两个由两个有序序列组成的有序序列组成的有序序列组成有序序列
6. ……

你懂的:)

(其实大概拿3、4、5个也无所谓，只是两个写着比较方便……)

public class MergeSort {
    public static void main(String[] args) {
    	// 测试
        int[] arr = {3,1,8,2,4,5,2,-1,0,9,10,-2,-5,4,6,-11,0,0,0,3,4};
        int[] res = sort(arr);
        System.out.println("---final result: "+Arrays.toString(res));
    }
    
    public static int[] sort(int[]arr){
    	int[] res = mergeSort(arr);
        return res;
    }
    
    private static int[] mergeSort(int[] arr) {
        if(arr.length>=2){ //折半
            int mid = arr.length/2; // 拆分拆分，直到每个列表只剩一个元素
            int[] left = mergeSort(Arrays.copyOfRange(arr, 0, mid));
            int[] right = mergeSort(Arrays.copyOfRange(arr, mid, arr.length));
            return merge(left,right); // 然后把两个有序序列重组
        }
        return arr; //会一直递归到每个序列只剩1个元素
    }
    
    private static int[] merge(int[] l1, int[] l2){
    	// l1、l2都是有序序列
        int i=0, j=0,c=0;
        int len1 = l1.length;
        int len2 = l2.length;
        int len3 = len1+len2;
        int[] res = new int[len3];
        while(i<len1 && j<len2){ // 两个序列都还有元素时
        	// 插小的那个元素，然后移动指针到下一位
            // 也有不记录指针位置，看做两个队列，每次poll序列开头的
            if(l1[i]<=l2[j]){
                res[c++] = l1[i++];
            }
            else {
                res[c++] = l2[j++];
            }
        }
        // 有一个序列空了
        // 把另一个序列里剩下的直接全塞进result
        while(i<len1){
            res[c++] = l1[i++];
        }
        while(j<len2){
            res[c++] = l2[j++];
        }
        
        /*
        // 打印本轮合并的结果
        System.out.println("---merge");
        System.out.println("---l1: "+Arrays.toString(l1));
        System.out.println("---l2: "+Arrays.toString(l2));
        System.out.println("---outcome: "+Arrays.toString(res));
        System.out.println();*/
        
        return res; // res依然是个有序序列
    }
    
}

堆排序

一种使用最大/最小堆来记录部分比较的过程，从而加速的选择排序。不使用额外空间的原地排序，但不稳定。也可以用来寻找最大/最小的N个值（top N问题）。

看上去的样子是：

{最大（或最小）堆：记录了部分比较过程的无序序列，有序序列}

堆

拿数组存储的完全二叉树。N_i 的父节点为N_(i-1)/2 ，左子节点为N_2i+1 ，右子节点为N_2i+2 。

最大堆：每个节点大于等于其子节点

最小堆：每个节点小于等于其子节点

步骤

1. 构建一个最大（最小）堆，即寻找无序区中的最大（最小）值
2. 把堆顶（堆里的最大/最小值）与最后一个元素交换。此时，len缩短1，把最后一个元素从堆的范围移除（把最大/最小值划入有序序列部分）。
3. 维护堆/无序区，使它重新成为最大（最小）堆（即从无序区找出最大/最小值。
4. 重复第二、三步，直至所有元素从无序区（堆）划分至有序区。

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {3,1,8,2,4,5,2,-1,0,9,10,-2,-5,4,6,-11,0,0,0,3,4};
        sort(arr);
        System.out.println("---final result: "+Arrays.toString(arr));
    }
    
    public static void sort(int[]arr){
        int len = arr.length;
        
        // 构建最大堆
        // 从倒数第二层（非叶子），依次与子节点比较并把较大的交换上去
        for (int i = (len-2) / 2; i >= 0; i--) {
            heapify(arr, i, len);
        }
        
    	for (int i = len - 1; i > 0; i--) {
            swap(arr, 0, i); // 取堆顶的最大值，与最后的节点交换
            len--; // 把这轮的最大值划分出去
            heapify(arr, 0, len); // 堆的部分重新排序
        }
    }


    private static void heapify(int[] arr, int i, int len) {
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;

        if (left < len && arr[left] > arr[largest]) {
        	// 若左子节点存在，且比父节点大
            largest = left;
        }

        if (right < len && arr[right] > arr[largest]) {
        	// 右子节点存在，且比父节点大
            largest = right;
        }

        if (largest != i) {
            swap(arr, i, largest); // 把较大的节点换上去
            heapify(arr, largest, len); //largest现在是原来的i
            // 看交是否需要把它继续往下置换
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

基数排序

按位排序，用于排序整数或可以用整数表示的数据（如日期、字符）。

例：[12, 25, 11, 15, 46, 42, 23, 35, 40,13]

按个位排序

0: 40----1: 11----2:12, 42----3: 23, 13---- 5: 25, 15, 35-—6:46

[40, 11, 12, 42, 23, 13, 25, 15, 35, 46]

按十位排序

1: 11, 12, 13, 15----2: 23, 25-—3:35-—4:40, 42, 46

[11, 12, 13, 15, 23, 25, 35, 40, 42, 46]

//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
    var mod = 10;
    var dev = 1;
    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
        for(var j = 0; j < arr.length; j++) {
            var bucket = parseInt((arr[j] % mod) / dev);
            if(counter[bucket]==null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        var pos = 0;
        for(var j = 0; j < counter.length; j++) {
            var value = null;
            if(counter[j]!=null) {
                while ((value = counter[j].shift()) != null) {
                      arr[pos++] = value;
                }
          }
        }
    }
    return arr;
}

桶排序

像是搞HashMap一样先搞一堆桶，然后按某种函数映射把元素塞进各个桶（但其实基本就是把整个区间分成n段，然后把属于该段的元素放进该段），每个桶分别排序，最后再把每个桶里排好序的倒出来拼在一起。。。

function bucketSort(arr, bucketSize) {
    if (arr.length === 0) {
      return arr;
    }

    var i;
    var minValue = arr[0];
    var maxValue = arr[0];
    for (i = 1; i < arr.length; i++) {
      if (arr[i] < minValue) {
          minValue = arr[i];
      } else if (arr[i] > maxValue) {
          maxValue = arr[i];
      }
    }

    //桶的初始化
    var DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认容量为5
    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;  
    var buckets = new Array(bucketCount);
    for (i = 0; i < buckets.length; i++) {
        buckets[i] = [];
    }

    //利用映射函数将数据分配到各个桶中
    for (i = 0; i < arr.length; i++) {
        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
    }

    arr.length = 0;
    for (i = 0; i < buckets.length; i++) {
        insertionSort(buckets[i]);   // 对每个桶进行排序，这里使用了插入排序
        for (var j = 0; j < buckets[i].length; j++) {
            arr.push(buckets[i][j]);                      
        }
    }

    return arr;
}