Tchaikov’s Journal

今天断断续续在写一个伪造磁敏数据的工具。的确是在“伪造数据”。因为现在磁敏和视频数据尚无同步的样本，只有同过拼凑来临时解决测试的问题。但是两种模式的样本中，车辆的速度不一样。所以，生成的磁敏数据不仅仅需要在时间轴上平移，也需要拉伸或者压缩。
这就引进了新的问题。举例来说，由于磁敏数据的采样频率是恒定的，拉伸后的磁敏数据的采样率会比原来要小。为了让采样率恒定，就需要进行插值计算。相应的，如果原始数据在时间轴上被压缩的话，就需要进行外推的计算。这些都是原来没有想到的。当初只是以为算出一个缩放系数就好，哪知道这么麻烦……
明天再想吧。

好容易等到 Google 来了。几个月来一直在看 AIC，但是临场的时候，脑子里所有的排序算法的复杂度都变成了 O(nlg(n))，全忘了！勉强写完，考得稀里糊涂的。感觉希望不大。
虽然 Google 把保密工作做的很好，要求我们在笔试完后把草稿也上交。但是我忍不住想把今天的题目记下来，记下来！笔试被分为两部分，前一部分为选择题，后一部分为问答题。和预料的一样，大多是数据结构和算法的题目。

1. 堆排序、快速排序、归并排序等几种经典排序算法是否 stable
2. garbage collection 使用从根节点遍历，如果没有引用到，则认为可以清除。下面哪些不属于根节点
• 正在运行的函数的参数
• 寄存器中的值
• 在堆上动态分配的空间
• 全局变量
• 局部变量
3. 最差情况下找出第7大元素，需要的时间复杂度为 O(nln(n)) 的数据结构为
• 双向链表
• 已排序的数组
• 平衡二叉树
4. 两个函数 g(x), f(x) 相互递归调用，问 f(x) 随 x 增长，其计算的时间复杂度为何
5. 编写程序计算两个 N*N 矩阵相乘
6. 不用递归，打印一棵二叉树
7. 设有正实数序列 S，求最大的 C，满足 C = A + B，且 A、B、C 都存在于 S 中，给出算法的时间复杂度、空间复杂度的分析。不用代码实现。

1. 矩阵相乘，学过矩阵论的同学想来都不成问题。这个题目的关键是提高程序的性能。我看过 CS APP，这本书对程序优化有着不错的介绍。当时我能想起来的就是 code motion 和 loop un-folding。前者很方便，把 c[i][j] += a[i][k]*b[k][j] 变成 sum += a[i][k]*b[k][j]，最后再把 sum 赋给 a[i][j] 能减少存储器的引用。而后者则需要判断 N 是否能被并行数（即循环展开的级数）整除，以及处理剩下的 a[i][k] 和 b[k][j] 的问题。当时觉得太麻烦，就没有做了。现在看来也不太麻烦。
2. 打印二叉树。我用的是经典的借助栈的办法。其实这种算法也有可以改进的空间。比如说，每次压栈的内容都会在下一次弹出，这就很没有必要。可以在循环里面直接更新 node 指针。但是当时觉得有些繁琐，而且害怕把算法改错，就没有把改进的算法写完。这些改进的方式在 AIC 里都说得很清楚。是我学艺不精。
3. 这个题目作为压轴，Google 肯定是有充分的考虑的。不过我没有想出比较精妙的算法。只是
　

　
1. 先用 quick sort 将 S 排序
　
2. 再从取数组最后一个元素作为 C 的候选人，在前面 n-1 个元素中找能匹配的A和B。如果找不到，C后向前移动。
　
3. 在前面 n - 1 个元素中找能匹配的 A 和 B 有一个需要注意的就是：从后往前移动 B 顺序找的话，只需要找到 ceil(C/2) 就可以了，因为剩下的候选者的和都是小于 C 的。确定 B = S[b] 之后，找  A 可以在S[0..b-1] 之间使用二叉搜索查找。整个算法的时间复杂度为 O(n^2ln(N))
　
4. 另外，如果 S 很小的话， quick sort 可以换成 selection sort
　
5. 如果 S 元素的取值范围很小，而且均为整数的话，可以使用定长的数组 T[MaxN] 来辅助排序和查找，比如，排序可以这样

    for i in S:      T[i] += 1  搜索则可以  return T[i]  

   可以看出，排序的复杂度降到了为 O(n)，搜索则降到了 O(1)。整个算法的时间复杂度为 O(n^2)

1. 经典算法的特性没有掌握，比如几个排序的时间复杂度和 stable 与否。(AIC)
2. 算法的改进方法，改进思想还是囫囵吞枣了，没有学到。(AIC)
3. 性能优化的道理知道了一些，不过碰到具体问题还是手软了。学得不扎实。(CS APP)

IPython 真个是好东西，方便的“帮助模式”，以及 tab 补全。让我这种只会在 terminal 里输入 python 然后开打的人打开眼界！不过 IPython 虽好，用 Emacs 的人总喜欢尽可能地把所有的事情移到 Emacs 下去做。想想看，也是啊，Emacs 里的括弧对齐，方便的输入方式，在 ipython 里打了一会儿，就怀念起来了。你猜对了，接下来说的肯定是 IPython 提供的 py-shell。
py-shell 是在 ipython.el 里提供的一个命令，让我们能使用在 Emacs 底下用上 ipython。先介绍一下 py-shell：
py-shell 的 major-mode 是 Comint 模式（即 command interpreter 模式），在这个模式下用户的输入被 Emacs 收下，喂给指定的 command interpreter（本例中就是 ipython 了），而 interpreter 的输出则被打印到当前的 buffer 中。当然，实际的 Comint 比这个复杂得多，Comint 会过滤输入输出，加入自己的操作比如定义一些 key-map，让自动补全更 Emacs 化。把自动补全显示到专门的 *IPython Completions* buffer 中。
我们都知道 Python 用缩进来控制程序的结构，如果缩进有问题的话，就无法写很多 Python 程序了。而 py-shell 的缩进却是有问题的。

In [11]: def wc(file):
  ....: count = 0
  ....: for line in file:
  ....: count += 1
  ....: return count

本来应该这样的：

In [11]: def wc(file):
   ....:     count = 0
   ....:     for line in file:
   ....:         count += 1
   ....:     return count
   ....:

为了解决缩进的问题，我和 ipython.el 斗争了一个晚上。首先求助于 google 大神，没找到有意义资料。接着在水木上发帖求助，好在有朋友也遇到了这个问题。而且有了补救的方法。他的办法就是在开启另外一个辅助的 python-mode buffer *IPython Indentation Calculation*，在那里面插入和 *Python* buffer 里相同的输入语句，让 python-mode 帮助我们计算缩进的字符串，然后再把这个字符串记下，待 comint 要输出的时候，再把缩进字符串加到输出的提示符后面。这个方法虽然有些绕弯，但是一下子也找不出什么更好的替代方案了。但是补救方法只是在 Windows 的 NTEmacs 上可行，在 Debian 的 Emacs 下却会不正常（第二版的设置根本就无效）。具体的修改：

• 只是加入了一个 “RET” 的 key map—— ipython-newline-and-indent()

• 负责更新 *IPython Indentation Calculation*
• 以及抓取缩进字符串

• 负责检查 ipython 的提示符
• 并插入正确的缩进字符串
• 清空缩进字符串

Liu Jin 的办法是在 ipython-newline-and-indent() 抓取缩进字符串，这个办法可能会有 race condition 的问题。不知道是 ipython-newline-and-indent 先执行完毕，还是 ipython-indentation-hook 先执行。测试下来，ipython-indentation-hook 从没有等到过抓好的字符串。因此，我把抓取字符串的工作从 ipython-newline-and-indent() 移动到了 ipython-indentation-hook()，并作了一些小改动。看起来没问题了，但是用了一阵子，碰到了新的问题。照 Liu Jin 的提示，我在 py-python-command-args 中又加了 -noautoindent。现在看上去没问题了。先将就着使吧。