不过，其实完全可以用自然语言处理分词算法再用字典树的说（因为用 HashSet 算法还是太慢了，即使是常量时间判断 has 也不行）

比如说，这个怎么就这么变态的字典里有一个磁：

duangsuse 于 2019 年悼念1989.6.4天anmen事件中死去被屠杀的学生

🌚 怎么就这么反华呢？

分词：

duangsuse(v) 于(p) 2019年(t) 悼念(v) 1989.6.4(m) 天(q) anmen(nx) 事件(n) 中(f) 死去(v) 被(p) 屠杀(v) 的(u) 学生(n)

如果分词后使用集合查询，复杂度是 O(n) * O(1) where n: 输入磁条数，比较慢
如果分词直接上字典树，虽然时间复杂度差一点，而且还是要对每个词条检查，但是性能可能会强一些（因为 hashCode 的 32 位空间很小的，这样 HashSet 判定复杂度会上升很多）

要是我们不仅仅要有设计图纸了，恐怕还得专门弄一个程序辅助建红石方块... 类似：不是有个 MCHDL 吗？

在我的世界打造一台计算机有多难？复旦大神花了一年

【在《我的世界》里从零打造一台计算机有多难？复旦本科生大神花费了一年心血】一块小小的CPU里有多少个晶体管？几十亿个。单枪匹马造出一个CPU乃至完整的电脑需要多长时间？有位大牛在《我的世界》游戏里用实际行动回答了这个问题：可能要花费一年多。「分享自新浪科技」

其实很多用莫名其妙“优化”的人，如果不是为了语义的原因，强调其『性能』高到哪里去，在现在这个程序变换优化编译的时代里，其实也是一种短视...

硬碰硬的东西，强调不如做到。

甚是，这些成天写利用一些高层抽象和用户直接交流应用程序的『高性能计算』大佬们，真应该问问他们会不会写链表和并行快速排序，知不知道啥叫 Reordering，啥叫 SIMD，啥叫并行算法

某些人连递归和尾递归优化都不知道怎么做，却靠着抄代码和自以为是而没有深究的『高端优化技巧』自以为有多么强大的能力，这是误会了，不应该是这样的。

说起来现在讲一个二进制的事情 #bin

首先说 #Java

Java 8 里有这些类型比较奇特：

byte short int long float double
char boolean

java.lang.Object
java.lang.Throwable
java.lang.Cloneable
java.lang.Compareable
java.lang.Number
java.lang.Enum
java.lang.Annotation

java.lang.CharSequence
java.lang.String
java.lang.Void

java.lang.Deprecated

java.lang.Iterable
java.util.Collection
java.util.RandomAccess
java.util.Iterator
java.util.Map
java.util.List
java.util.Set

别的都不看，我们看 primitive numbers
我们今天不谈 Java 1.5 引入的 Autoboxing, Autounboxing, etc，单单看 C-like 语言里这些数值类型的最大值和最小值

所谓的一个 number 呢，一般都是可以进行各种操作的对象，操作包含：加减乘除取余位运算什么的

不要看 java.lang.Number 的 abstract class 定义，没用（只有 coercion，转型的方法），因为 Java 是使用 primitive 方法实现 +-*/^ 等 operator 的

在 Java 里，这些操作都是使用 <i|l|f|d> <cmp|add|sub|mul|div|rem|neg|shl|shr|ushr|or|and|xor|2Type> 字节码指令实现的，byte 和 short 不直接受到支持

比如，你算 println(ary[row*ary.width+column]) 这里 ary 是 int[]

将生成如下字节码，假设 ary 被放在本地表的第一位... 好吧，我应该标注这个是 static 方法（要不然第一位是隐式参数 this），为了保证准确性这代码的确是 javac 编译出来的，我只是截取并注释

import static java.lang.System.out;

class Main {
void printIndex(int[] ary, int width, int row, int column) { out.println(ary[row*width+column]$
}

getstatic Ljava/lang/System.out:Ljava/io/PrintStream;
aload_1 ; int[] ary
iload_3 ; row in (*) operation
iload_2 ; width
imul ; row * width
iload 4 ; column
iadd ; (row * width) + column
iaload ; subscript ary with x
invokevirtual Ljava/io/PrintStream.println:(I)V;
return

生成代码？看起来很复杂？其实面向 JVM 的编译器写起来很简单，考虑一下类型的问题和静态本地表长度，最大栈深度，然后后序遍历抽象语法树输出字节码指令流就可以了

那么这次讲什么？只是讲他们的长度。

打开 Hex editor 应该经常能看到一些东西『有符号』『无符号』『整型数』
就是一种整数 {Z} 啦 (signed)
对于 unsigned，就是 {N}

不过计算机不是数学，精度有限制，是靠二进制来存储的，二进制是一种状态序列（组合），每一位都有两种状态：0 或者 1。

0b00 : case 0
0b01 : case 1
0b10 : case 2
0b11 : case 3

二位的二进制可以存储四种状态：这很好，这意味着我们可以有 0-3 之间的整数
至于具体的『整型数据操作实现』比如比较（大、小、同一）、相加相减，都是由机器层面实现的，我们不需要操心。

如果我们要存储符号，可以留一个位的状态来存储『它是不是一个负数』这个状态

0b01: +1
0b11: -1

很多人说不是直接通过一个符号位来的，是通过补码，但其实补码就是符号位... 只不过是加上了按位取反而已, 一种编码细节
有符号数字的操作也可以让机器来实现（不然也没必要使用二进制了）

要取一个数字的 lowbit（没有符号位的部分）可以使用如下位运算（Ruby）：

def lowbit(x); return (-x) & x; end
lowbit(1) == lowbit(-1)

C 里面可以写成宏定义或者 inline procedure, 因为我这里 inline 会出现链接符号找不到的愚蠢问题，所以干脆使用宏定义

#define lowbit(x) ((x) & (-(x)))

当然这和按位取反（inverse by bit）是不一样的

====

十六进制

16 进制是表示二进制的一种简单记法，它一般被用于表示二进制数值。

计算机科学里的数值和数学里的数的区别，主要是计算机科学的『机器数值』是有最大值最小值范围限制的（二进制 n 位，因为现代常用电子计算机基于二进制），而数学只是一种抽象定义，它没有位数的限制

== 对数函数

这里不是数学教程，所以只有使用没有定义。

-- 以 n 为底关于 n 的对数
log(n) x = k
where k: n^k == x

-- n 的 k 次幂
n ^ 0 = 1
n ^ k = n {* n} repeats for k-1 times

使用诸如：

满二叉树（对于非叶子节点，每一层都有两个子节点）第 n 层的节点个数： 2 ^ (n - 1) — 排除第一层根节点不符合二元增长律的
有 n 个节点的满二叉树的层数： log2 (n - 1) +1 — 排除第一个不符合增长率的节点，算出第二层和下面的，再加上第一个节点

== 十六进制和二进制

log2(16) = 4

我们这里算的是『序列』case 数目，不过我们知道，

2^4 = 16，也就是说，一位 2 case，重复 4 次就可以表示一位 16 case 的情况（或者说，4 位二进制有 16 个 case）

log2(10) 不是整数，所以无法直接将 10 进制和二进制对应，不过 log2(8) 也是整数 3，所以 3 位二进制可以对应一位 8 进制

下面 0x 后面跟随十六进制、0b 后面跟随二进制

所谓 16 个 case 是，四位二进制，按照 <> 里的位为 1 的情况，可以这么与 16 进制对应：

0b <+8> <+4> <+2> <+1>

{} 里的东西可以重复无数遍或者不出现，[] 里的东西是一些字符的区间，用于表示 {} 里重复的字符都在此区间里

0x {[0-9A-Z]}

0-9 A-F 一共是 16 个数字，10 通过 A 表示，11 通过 B 表示，...

因为一般都是这么表示的（简单的二进制加减法）

0xFF : 0b1111_1111
0xFE: 0b1111_1110

0xFE 换算为二进制，直接对每一位写对应的二进制

hexDigitToBinary(0xA) = 0b1010 — +8 +2 = 10
hexDigitToBinary(0xD) = 0b1101 — +8 +4 +1 = 13
hexDigitToBinary(0xE) = 0b1110
hexDigitToBinary(0xF) = 0b1111 — 15

换算回来等同（这本身就是一个双向映射关系）。

== 字节序（ByteOrder）

字节序是一个底层硬件实现的细节，一般分为大端字节序和小端字节序，二者可以互相转化，它是一种二进制数值表示的规格
一旦一个数值类型长过一字节（比如 Java int，4 字节）就会出现字节序的问题

enum ByteOrd { LittleEndian = 0xfffe; BigEndian = 0xfeff }

我们所认为的『大位』（比如 13 里的十位）会被小端放在前面的字节里（所以它是从结束的字节起始一个数值），被大端放在后面的字节里

一般 x86 等 CISC 机器都会使用小端字序、ARM 等 RISC 机器会使用大端字序，大端字序也被称为网络序（因为在计算机网络上传递整型一般使用大端），小端也被称为本地序

最后在铺垫了这么多之后我们可以看看 Java 基本型的位长度了：

所谓基本型就是：

byte short
int long float double
char boolean

== Java 可以对这些『基元类型』进行打包（到 Java Heap，堆上，用于 pass-by-reference 等，一般 int 等类型都是按值复制“传递” pass-by-value 的）

=== 传递和堆上存储

private class Product2 {
  String name, int value;
  public Product2(String name, int value) {...}
}
// invariant over T
private class Product2ParamizedType<T> {
  String name, T value;
  public Product2(String name, T value) {...}
}

public void main(String... args) {
int a = 1;
dowith(a);
out.println(a);
Product2 prod = new Product2("int", a);


// 不得不转换为引用型 Object，因为 Java 的泛型支持是（基于泛型擦除的）假泛型，实际上 Java 编译器不需要让 ParamizedType 类变成字节码模板
// 使用了 Java 1.3 开始的自动值类型装箱和泛型检查语法糖
  Product2ParamizedType<Integer> prod_generic = new Product2ParamizedType<>("int", 2);

}

void dowith(int x) { x = 2; out.println(x); }

Java 运行时，在一个小的视角下非常简单：

一个方法本地表，存储 int a; 这种局部变量，一个方法实例（存在调用栈上的方法）的本地表会在方法结束运行后删除
一个求值栈，用来向被组合的操作传递参数（比如调用 dowith(a);）

有时候不同方法的本地表有重叠（比如参数传递时）不过这里不需要考虑，这是由于运行时优化相关的原因

==== Java 的 Lambda 和本地表这些无关，Java 本身“好像”是支持 Lexical Scoping 的（Lexicalscope 和 Lambda calculus 本身有很大的关系）（因为 Java 支持 Higher-Order function？并不）
Java 的 Lambda 只是匿名内部类的语法糖，而 invokedynamic 和 Lambda 本身没有本质性的联系，只不过是 invokedynamic 必须被用来（在内部实现 Lambda 对象生成时）调用 java.lang.invoke.LambdaMetaFactory 实现 Lambda 的 bootstrap 而已，Google 也有 Runtime desugar 实现，invokedynamic 本身能实现的功能 Reflect 同样也可以实现（通过 java.lang.reflect.Method）
Lambda 里的变量都必须是“effective final”的原因，也正是因为 Lambda out.println(x -> x + 1) 只是匿名内部类 new Object() { @Override boolean equals(Object y) { return true; } } 的语法糖而已，被“capture”的本地变量只是会被复制到被动态生成子类的字段里而已，本身不能被 Lambda 对象操作而改变。

import java.util.Arrays;
import java.util.stream.Collectors;

public static void main(String[] args) {out.println(Arrays.asList(new Integer[] {1,2,3}).stream().map(x -> x + 1).collect(Collectors.toList()));}

==== 相关的还有子程序（包括所谓的各种运算符比如 +-*/）参数求值方式：立即求值（call-by-value）、惰性求值（call-by-name）、每次重新求值（call-by-need）

== 打包后的类型

int.class => java.lang.Integer
short long boolean 什么的依此类推

Arrays.asList(char.class.getClass().getMethods()).stream().filter { it.getName().endsWith("Name") }.collect(java.util.stream.Collectors.toList())

char.class 是个例外： => java.lang.Character

== 长度

byte short int long 的字节长度分别是
1 2 4 8
按位算就是 (*8)
8 16 32 64
float double 分别是 32/64 位 IEEE754 浮点

char 是 16 位 UTF-16 字符 code point 值
boolean 理论上是一位，实现时有人作为 int 实现（虽然也可以作为实际的一位实现，不过有个对齐(alignment)的问题，可以使用类似 bitmask/bitshift 的方法解决，只是硬件的原因），不过值只能是 0 或者 1

== 所以，有长度就有最大最小值

Integer.MAX_VALUE == 0x7F_FF_FF_FF
Integer.MIN_VALUE == -0x80_00_00_00

根据上面的十六进制速记法应该知道
MAX 第一个字节是：0b0111_1111
MIN 的则是：0b1000_0000
可以看到第一位是符号位，不过因为 Java 语言的原因，Hex 表示溢出了没有正确设置符号位，所以得手动加上负号

== 余下的表示

assert Byte.MAX_VALUE == (2**7)-1
assert Byte.MIN_VALUE == -(2**(8-1))

然后我们干脆定义个函数帮我们做算了...

void assertSignedMinMax(lenSigned, klass) {
final MIN_VALUE_VAR = "MIN_VALUE"
final MAX_VALUE_VAR = "MAX_VALUE"
validSpace = 2 ** (lenSigned - 1)
max = validSpace - 1
min = -validSpace
final expectMin = klass.getDeclaredField(MIN_VALUE_VAR).get(null), expectMax = klass.getDeclaredField(MAX_VALUE_VAR).get(null)
assert min == expectMin && max == expectMax
}

assertSignedMinMax(16, Short.class)

... 跑路... 又熬夜了

啊嗨！
java.lang.Deprecated 是什么鬼类型…

[DuangSUSE@duangsuse]~% javap java.lang.Deprecated
Compiled from "Deprecated.java"

public interface java.lang.Deprecated extends java.lang.annotation.Annotation {}

它是一个 @interface 啊，用来标记某些东西已经『被废弃了』

[src/share/classes/java/lang/Deprecated.java] [oracle docs]

@Documented
@Retention(RetentionPolicy.RUNTIME)
@Target(value={CONSTRUCTOR, FIELD, LOCAL_VARIABLE, METHOD, PACKAGE, PARAMETER, TYPE})
public @interface Deprecated {}

接上面没有写完的：
最终结果：

assertSignedMinMax(8, Byte.class)

assertSignedMinMax(16, Short.class)


assertSignedMinMax(32, Integer.class)

assertSignedMinMax(64, Long.class)

这是整形

Float.MIN_VALUE //=> 1.4E-45
Float.MAX_VALUE //=> 3.4028235E38

Double.MIN_VALUE //=> 4.9E-324
Double.MAX_VALUE //=> 1.7976931348623157E308

这是实型（准确的说只是有理数不是实数）

https://en.wikipedia.org/wiki/IEEE_754#Basic_and_interchange_formats

Float 有 24 个二进制位的有效数值，Double 则有 53 个
JavaScript 的 Number 默认为 Double，不过 ES6 也加入了 Integer 和 Integer literal 1000n


Character 的最小值为 0，想也知道（往下肯定不是 Unicode 有效的，再说还有下面的 unsigned）

(int) Character.MIN_VALUE //=> 0

(int) Character.MAX_VALUE //=> 65535

最大值是 2 ^ sizeof(unsigned short)

Boolean 是完全可枚举的（理论上或者实践上或者语义上），就不需要认为它是 Number 了

实际上一些语言里 True False 完全可以只是一个类型的数据构造器而已...

比如 Haskell：

data Boolean = True | False deriving (Eq, Show, Read, Enum)

比如 Agda：

data Bool: Type0 where
true false : Bool

https://agda.github.io/agda-stdlib/Agda.Builtin.Bool.html


====

完结撒花！ 🌸

尾记：

上面的东西意义不明确，而且有点冗长
有人可能会说我写东西经常这样（废话一大堆）
其实这正是我的风格，我有这样先写 background 的习惯，
不同于其他很多人（尤其是学院派），我会把一些比较难理解的东西一遍一遍的重复，这是为了能更好的记住他们，顺带多传播点信息
就是这样，喵。

#Math #music

最近知道了两个之前不知道的芝士： 🤔

+ 音高是什么！
+ x 的 （n 的倒数次方）等于开 x 的 n 次方根
where
n 的倒数: 1 / n
x 的 k 次方: x {* x} repeats for (k-1) times
n 的 k 次方根: (x 的 k 次方 = n) => x
+ 数学函数和数学操作符是不一样的

#tech #daily #Java #JavaScript #dev

🐱 duangsuse 的学习日常 ⭐️

+ 程序设计语言::Closure、Pattern Matching、Stream、Generators #pl #cs

+ 程序设计语言类型::这些名词，你知道吗？（涉及 Parameteric Polymorphism 和 Empty Types(aka. Bottom types)、Product types、Subtyping 等内容）

+ 高性能计算::C 语言和高性能计算、x86 汇编和 SIMD（单指令多数据）运算、JNI 外置原生算法

+ 软件架构::FFMpeg av* 库水印程序

+ 数据库::关系代数 #db

+ {Android, 数据结构和算法}::Android 的离散数组 SparseArray 和 ArrayMap #algorithm

+ 数据结构和算法::这些算法和数据结构，忘记了吗？

+ Rust/数据结构和算法::Rust 的 Vector 实现
+ Rust::Hole 类型、snappy 绑定、Tree 类型、LinkedList、Box、Rc、std::thread 等

+ Java 的二进制流读写器 #bin
+ Java 的 Android android.content.SharedPreferences 代理库 Prefer
+ {软件架构, Android}::编写一个 Android 上的 Service！（感谢 @YuutaW 提供学习资源，ShutdownService 默写）
+ 软件项目管理::Gradle 的抽象总结

+ JavaScript ES6: sm.ms.js
+ JavaScript ES6: 基于 CheerIO 和 Requests.js-promise-native 的爬虫，默写（感谢 @ice1000 的原实现，这可能是冰封哥有史以来最奇怪的代码，因为他写了两个完全可以被替换为更有意义结构的没有用的控制结构...）
+ JavaScript ES6: ArrayBuffer, DataView 读 BMP、再看 ASCII 艺术画生成

+ Kotlin::简单的 Realm ORM + RecyclerView Android 应用
+ Kotlin::Shell execute
+ Kotlin::Coroutine
+ Kotlin::Kotlin Native 和 Kotlin JavaScript 与 Gradle/Groovy
+ Kotlin HTML DSL
+ Kotlin 内部代理类 (Delegates)
+ Kotlin OkHttp 同步/异步封装

+ C 程序设计语言::libBMP 和 libWAV
+ C 程序设计语言::OpenGL 体验

+ 无脑模式::线性代数::高斯·约当消元法（Gauss Jordan）解齐次线性方程组（Homogenuous Linear Equation Group）
+ 无脑模式::C++/Qt::拼音分词、英文音标转换和 TTS 合成
+ 无脑模式::Haskell 抄写 Haskell 的 AlgorithmW Hindley-Milner Type system type infer algorithm 实现

+ Javax Servlet 架构体验 🤔

https://raw.githubusercontent.com/yairchu/Algorithm-W-Step-By-Step/master/AlgorithmW.lhs

现在就可以试用 Haskell 编写的 Type inferer，可惜我还要再抄一遍（🙈

AlgorithmW.tex: Algorithm.lhs
lhs2Tex $< > $@

AlgorithmW.pdf: AlgorithmW.tex
latex $<
pdflatex $<

AlgorithmW: Algotithm.lhs
ghc --make $<

https://www.gnu.org/software/make/manual/html_node/Automatic-Variables.html

#Haskell 开心。 ghc -e main AlgorithmW.lhs