最近写了一个Java ByteCode的解析器，其实感觉ByteCode文件的结果非常简单，所以最后都是自动机的形式就可以了。后面我会用Go完成一个JVM。地址在我的go-jvm项目的classfile部分。贴一个ClassFile的结构

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

type ClassFile struct {
	minorVersion	uint16
	majorVersion	uint16
	constantPool	ConstantPool
	accessFlags		uint16
	thisClass		uint16
	superClass		uint16
	interfaces		[]uint16
	fields			[]*MemberInfo
	methods			[]*MemberInfo
	attributes		[]AttributeInfo
}

• 目的
  • 某事件发生的频数过低时使用MLE会导致极差的估计偏差，拉普拉斯平滑和M-估计都是为了解决这一问题。
• 拉普拉斯平滑
  • 相当于假设均匀分布的先验的情况下和后验做blending，实际上并没有如此简单。但是这种解释有诸多不合理，想要了解其中的原理可以看看这篇文章。我花了一个小时才看懂，发现概率论得好好补补了。。。
• M-估计
  • P=(r + Pa * m)/(n + m),其中m为估计的值。
  • 或者P=(n/(n+m)) (r/n) + (m/(n+m)) (Pa)
  • 不难看出其实对MLE和拉普拉斯平滑的一种综合。

• http://web.math.sinica.edu.tw/mathmedia/default.jsp
  • 台湾优秀的数学科普网站
• http://setosa.io/ev/
  • 可视化了解数学概念

• 目的
  • 基于经验，我们需要序列化的数据，通常小数（绝对值）多，大数少，所以出现了ZigZag编码，来减少编码数据的大小。

• 过程

  • 双射

    • 构建一个F(int) -> int，让绝对值小的数尽量小，绝对值大的数尽量大。

    • 1	n = (n << 1) ^ (n >> 31);

    • example

      • 0 -> 0
      • -1 -> 1
      • 1 -> 2
      • -2 -> 3
      • 2 -> 4

  • 变长编码

    • 代码

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

      public static int encodeInt(int n, byte[] buf, int pos) { // move sign to low-order bit, and flip others if negative n = (n << 1) ^ (n >> 31); int start = pos; if ((n & ~0x7F) != 0) { buf[pos++] = (byte)((n | 0x80) & 0xFF); n >>>= 7; if (n > 0x7F) { buf[pos++] = (byte)((n | 0x80) & 0xFF); n >>>= 7; if (n > 0x7F) { buf[pos++] = (byte)((n | 0x80) & 0xFF); n >>>= 7; if (n > 0x7F) { buf[pos++] = (byte)((n | 0x80) & 0xFF); n >>>= 7; } } } } buf[pos++] = (byte) n; return pos - start; }

    • 1 2 3 4 5 6 7 8 9

      等价于： while if 第七位满1或有进位: n |= 0x80; 取低位的8位作为一个byte写入buf; n >>>=7（无符号右移7位，在高位插0）; else: 取低位的8位作为一个byte写入buf end

• 目的

  • 普通MergeSort对于原本有序或者接近有序的数组的表现不好，所以引出了Natural Mergesort。

• 过程

  • 和MergeSort自顶向下的过程不同，Natural Mergesort选择了相反的方向。

• 代码

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

  ForwardIterator SortedRangeEnd(ForwardIterator begin, ForwardIterator end, Comparator comp) { /* Edge case - if the input is empty, we're done. */ if (begin == end) return end; /* Get an iterator that's one step ahead of begin. */ ForwardIterator next = begin; ++next; /* Keep marching these iterators forward until we find a mismatch or * hit the end. A mismatch occurs when the element after the current * is strictly less than the current element. */ for (; next != end && !comp(*next, *begin); ++next, ++begin) ; /* The above loop stops either when next is the end of the sequence or * when next is the crossover point. In either case, return next. */ return next; }

这个函数是来找到已经排好序的范围。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

void Merge(ForwardIterator begin, ForwardIterator mid,
             ForwardIterator end, Comparator comp) {
    /* Determine the type of the element being iterated over. */
    typedef typename std::iterator_traits<ForwardIterator>::value_type T;
    /* Create a vector of Ts that will hold the merged sequence. */
    std::vector<T> merge;
    /* Continuously choose the smaller of the two to go in front until some
     * range is consumed.
     */
    ForwardIterator one = begin, two = mid;
    while (one != mid && two != end) {
      if (comp(*one, *two)) { // First sequence has smaller element
        merge.push_back(*one);
        ++one;
      } else { // Second sequence has smaller element.
        merge.push_back(*two);
        ++two;
      }
    }
    /* Once one of the sequences has been exhausted, one of two cases holds:
     *
     * 1. The first sequence was consumed.  In that case, the rest of the
     *    second sequence is valid and we can just copy the merged sequence
     *    in front of it.
     * 2. The second sequence was consumed.  In that case, we copy the rest
     *    of the first sequence into the merged sequence, then write the
     *    merged sequence back.
     */
    if (two == end)
      merge.insert(merge.end(), one, mid);
    std::copy(merge.begin(), merge.end(), begin);
  }

稀疏平常的merge部分。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

NaturalMergesort(ForwardIterator begin, ForwardIterator end,
                      Comparator comp) {
if (begin == end) return;
  /* Track whether the current iteration of the algorithm has made any
   * changes.  If it didn't, then we can finish early.
   */
  bool haveMerged;
  /* Continuously loop, merging together ranges until the input is fully
   * sorted.
   */
  do {
    /* We have not yet merged anything, so clear this flag. */
    haveMerged = false;
    /* Scan forward in the loop, looking for adjacent pairs of sorted ranges
     * and merging them.  
     */
    for (ForwardIterator itr = begin; itr != end; ) {
      /* See how far this range extends. */
      ForwardIterator rangeEnd = SortedRangeEnd(itr, end, comp);
      /* If we hit the end of the range, we're done with this iteration. */
      if (rangeEnd == end) break;
      /* See where the end of that range is. */
      ForwardIterator nextRangeEnd = SortedRangeEnd(rangeEnd, end, comp);
      /* Merge this range with the range after it. */
      Merge(itr, rangeEnd, nextRangeEnd, comp);
      
      /* Flag that we did at least one merge so we don't stop early. */
      haveMerged = true;
      /* Advance the iterator to the start of the next sequence, which is
       * directly after the end of the second sorted range.
       */
      itr = nextRangeEnd;
    }
  } while (haveMerged);
}

可以看到只是一个很小的更改，就能让我们成功降低mergesort最好时间复杂度，真正让mergesort更加实用了。

今天懒癌烦了，灌篇水文吧。

• 目的

  • 为8bit寄存器设计的哈希函数。

• 效果

  • 非常简单
  • 在资料受限的机器上也能快速执行
  • 想要故意构造哈希冲突不是很容易
  • 两个只有一个字符不一样的字符串不会冲突

• 代码

  1 2 3 4 5 6 7 8 9 10

  from random import shuffle example_table = range(0, 256) shuffle(example_table) def hash8(message, table): hash = len(message) % 255 for i in message: hash = table[(hash+ord(i)) % 255] return hash

  ​

你是否有留意过很多的电子博弈游戏平台玩家创建账号后评分大多数是1500分（我印象中欢乐斗地主就是这样的。）。最近柯杰和AlphaGo的围棋3番战举世瞩目，柯杰作为人类目前围棋界世界第一的棋手，你是否知道他目前2800多的积分是如何得到呢？《社交网络》中男猪脚马克扎克伯格被女友甩了，气愤的他创建了Facemash，让用户选择他们觉得更漂亮的女生，那么如何在诸多选择中构建一个合理的排名呢？本文将介绍Elo Rating System，它是目前世界大量双人博弈运动的评分系统,比如可以看看这个新闻（https://bbs.hupu.com/13830203.html）。让我们开车吧。

• 历史

  • 作者Elo是顶级的世界象棋选手，他是美国国际象棋联邦的活跃成员，可是当时使用的Hackness Rating System有些不好使，所以Elo就自己造轮子造出了Elo Rating System。

• 原理

  • 不同选手的表现可能有高有底，所以Elo就把它想成了一个正态分布模型。（实际上后面经过测试大家发现Logistics函数更加合适，后面的简介将会更加Logistics函数版本来讲解。）
  • Elo假定一个选手的水平均值（或许有超常发挥或者失误的情况，但是均值还是能够刻画他/她的水平的）
  • 通过比赛的结果评价选手的水平表现。（获胜用1代表，打平用.5代表，输用0代表。）

• 过程

  • 假定有一场比赛，选手A有评分Ra， 选手B有评分Rb。我们认为

    • Ea = 1 / (1 + 10^(Rb - Ra) / MAX_SCORE_TO_TRANSFER)，Eb可由对称性和Ea + Eb == 1获得。
    • 其中Ea是A获胜的期望。
    • 在比赛结果出来后，可能会根据赛果做两人的分数移交，MAX_SCORE_TO_TRANSFER表明了一次比赛最多能移交的分数。
  • 可以在一场比赛或者多场比赛之后，根据选手的表现调整他/她对应的Ex。
    • R’a = Ra + K(Sa - Ea) # K可以表示为波动系数。
    • 其中Ra是原评分，R’a是新评分，Ea是原来对这场比赛获胜的预期，Sa是他/她比赛的结果，赢了是1，输了是0，平了是0.5。
• 细节考虑
  • 分布模型
    • 目前普遍认为Logistics函数比较适合描述所有选手的能力分布，但是也有系统使用正态分布。
  • 变量K的选择
    • 对于调整过程，K的选择是一个很tricky的过程，太大了可能选手分数波动太大，太小了可能反馈不足。目前很多系统使用对不同的水平层级的选手选择不同的K值，高手的K值比较小，新手或者蒟蒻的K值比较高。
  • 是否零和游戏
    • 如果按照初始的Elo Rating System，那么整个游戏就是个零和游戏，但是因为一个人总是开始的时候分数低，离场时水平提高，分数也高了。所以剩下的人平均分就会往下减。
• 批评
  • 只能赛果中了解信息
    • 如果A和B一直打比赛经常打平，那么很可能他们相当，但是可能在这个过程中他们水平有了上升。后面A和某高手PK赢了，如果是使用Elo Rating System，如果B没有和高手比赛，B的评分就不会提升，这样是很不合理的。所以现代系统通常会希望识别到全局的信息，似乎更合理的做法是使用一个增量评分系统。让系统增加一个根据时间衰减的特性，但这样近期的比赛可能会让elo的估计偏差变大。长期不比赛复出的选手的评分可能会有很大的跳跃，不过总的来说也比纯elo更好。
  • 其设计是为2人博弈设计，多人游戏使用它不太适合。

• F Score
  • 带权的召回率和准确率的调和平均数
  • 当alpha为1的时候，为常见的F1 Score。
• E Score
  • ，所以F = 1 - E。
• G-measure
  • 精度和召回率的几何平均值
  • 也被称作Fowlkes-Mallows index

• mAP(mean Average Precision)

  • mAP是为解决P，R，F-measure的单点值局限性的。为了得到 一个能够反映全局性能的指标，可以看考察下图，其中两条曲线(方块点与圆点)分布对应了两个检索系统的准确率-召回率曲线。
  • 
  • ​
  • 

• ROC曲线

  • 横轴是假阳率/特异度（真阴/ 所有阴），纵轴是真阳率或者敏感度
  • AOC值是ROC曲线覆盖的面积。越大分类效果越好。

• kappa statistic — 衡量不同人相关性判断的一致性

  • K(A) = P(A) - P(E) / 1 - P(E)
  • P(A)是一致性判断指标，P（E）是随机情况下一致性判断比例。

• DGC

​
​
​

最小完美哈希

• 目的

  • 为了快速的定位倒排索引中Term的位置，需要使用哈希表。但是哈希冲突是很伤的事情，所以如果能够有一个哈希函数使得每个Term都落入不同的桶就好了。最小完美哈希闪亮登场了。

• 局限

  • 所有的key都必须都知道。
  • 要有不小于|key|的桶数。

• CHM算法

  • 目的：

  • 实现：

  • 

  • 注意通常ix的空间为key的空间的两倍以上。

  • 设计G：

    • 等价于无环图的遍历

    • 

    • 

    • 

    • 所以如果g(i1) = 0, g(i2) 一定等于0，g(i3)一定等于1…

    • 如果上述的dependency在特定ix中会存在环，最后相当于矩阵不可逆，也就无法求出解了。

    • 如何构造出无环的ix呢？

    • 答案就是：F1(str) == sum str[i] + RndTable1[i] mod n。n就是上面中讲到的ix的space。RndTable1是用随机数打的表。F2的结构也类似，只不过是生成的表不同。

    • 居然用随机的话，很明显了，就是RP好无环就手工，有环就再返工重新生成RndTable，

    • 现在需要的就是分析这个凑的过程的运行效率问题。这个就要涉及到f1,f2这两个函数的值域大小，如果越大，越容易凑出一个g函数，但是g函数的参数域就会比较大，存储这个f函数的数据就需要占用更多的空间。相反如果值域越小，在凑的时候就非常容易出现环，需要更长的时间才能凑出这个g函数。

    • 怎么办呢？

      我们可以使用3个的h函数来降低形成环的可能，就是这样h(x)=g(h1(x))+g(h2(x))+g(h3(x))modn ，这样虽然推理g函数的过程会复杂一些，但是很有效，有实验分析表明，当h函数的值域大约参数域的1.23倍的时候，这个g函数的创建尝试次数是常数。