Hexo迁移(win->linux)

发表于 2019-01-10 分类于折腾阅读次数： Disqus：本文字数： 1.2k 阅读时长 ≈ 1 分钟

Hexo + Next6 迁移 win -> linux .
更新
1
19.01.10 初始

Vscode系列—c语言

发表于 2018-03-24 更新于 2018-10-05 分类于工具阅读次数： Disqus：本文字数： 17k 阅读时长 ≈ 15 分钟

vscode c语言在ubuntu windows下代码提示/补全,简单编译.

更新

1 2	18.03.24 ubuntu下代码提示/补全 18.10.05 新增win10下配置,补全简单编译.更新版本

阅读全文 »

算法—KMP

发表于 2018-09-19 分类于计算机基础阅读次数： Disqus：本文字数： 2.9k 阅读时长 ≈ 3 分钟

记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.
初步涉及KMP时,有些蒙蔽,还好遇到了阮一峰的讲解,才啃下来.博文图来自资料链接.

资料来源如下

从头到尾彻底理解KMP（2014年8月22日版）
如何更好的理解和掌握 KMP 算法? - 海纳的回答 - 知乎
字符串匹配的KMP算法阮一峰

KMP

暴力搜索

搜索字符串时最常用的是暴力搜索,
- 一个字符一个字符去比较,第一位相同,比较第二位
- 遇到不同字符,目标字符指针后移一位,重复.
- 直到遇到模式字符终止符.返回目标字符指针位置.

以下是暴力搜素的C语言一个实现版本

int ViolentMatch(char* s, char* p)
{
  int sLen = strlen(s);
  int pLen = strlen(p);

  int i = 0;
  int j = 0;
  while (i < sLen && j < pLen)
  {
      if (s[i] == p[j])
      {
          //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j +
          i++;
          j++;
      }
      else
      {
          //②如果失配（即S[i]! = P[j]），令i = i - (j - 1) j = 0
          i = i - j + 1;
          j = 0;
      }
  }
  //匹配成功，返回模式串p在文本串s中的位置，否则返回-1
  if (j == pLen)
      return i - j;
  else
      return -1;
}

对暴力搜索而言,整个流程上改进空间不大,主要集中在当搜索过程.见示例
可以看到整个搜索过程,最明显的一个缺陷是,搜索到模式字符串的中间很长一段了,遇到一个坏字符,目标字符串指针移位1.模式字符还是要从头开始比较,模式字符在上一轮坏字符之前的比较相当于白做了.

KMP算法

当空格与D不匹配时，前面六个字符是”ABCDAB”已知。KMP算法的想法是，设法利用这个已知信息，不要把”搜索位置” j 移回已经比较过的位置，而是继续把它向后移。
经过KMP处理六个字符已知字符串”ABCDAB”后,可以得到一个表格,对应模式字符串每一位可前移的位数.如图
于是整个过程优化如下.
- 但空格与D失配,其前一位 (B->2),所以 j=2
- 但空格与C依旧失配.其前一位 (B->0),所以 j=0

对应c代码变化如下

最主要的变化是引入next[]数组(方便).
因为c语言数组元素由0开始,上文的表格右移一位.0位填充-1.得到next数组.

int KMP(char * t, char * p)
{
  int sLen = strlen(s);
  int pLen = strlen(p);

  int i = 0;
  int j = 0;
  while (i < sLen && j < pLen)
  {
    //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++
    if (j == -1 || s[i] == p[j])
    {
      i++;
      j++;
    }
    else
    {
      //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]
      //next[j]即为j所对应的next值
      j = next[j];
    }
  }
  //匹配成功，返回模式串p在文本串s中的位置，否则返回-1
  if (j == pLen)
      return i - j;
  else
      return -1;
}

部分匹配表(Partial Match Table),next[]数组

这里大量摘录了如何更好的理解和掌握 KMP 算法? - 海纳的回答 - 知乎的答案.
上文提及的表格即部分匹配表.
字符串的前缀和后缀。
- 前缀: 如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。
- 后缀: 后缀A=SB，其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。
- 要注意的是，字符串本身并不是自己的后缀。
PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度,如图
这里换一组字符串“abababca”说明next数组求法
求next数组的过程完全可以看成字符串匹配的过程，即以模式字符串为主字符串，以模式字符串的前缀为目标字符串，一旦字符串匹配成功，那么当前的next值就是匹配成功的字符串的长度。
具体来说，就是从模式字符串的第一位(注意，不包括第0位)开始对自身进行字符串搜索(KMP)。在任一位置，能匹配的最长长度(j值)就是当前位置的next值。如下图所示。
如图

c语言实现

void GetNext(char* p,int next[])
{
  int pLen = strlen(p);
  next[0] = -1;
  int k = -1;
  int j = 0;
  while (j < pLen - 1)
  {
    //p[k]表示前缀，p[j]表示后缀
    if (k == -1 || p[j] == p[k])
    {
      ++k;
      ++j;
      next[j] = k;
    }
    else
    {
      k = next[k];
    }
  }
}

流程(部分):
- next[6]=4
- p[6] != p[4]; k = next[4] = 2
- p[6] != p[2]; k = next[2] = 0
- p[6] != p[0]; k = next[0] = -1
- k == -1; ++k; ++j; next[7]=k=0;
- ……
回到字符串”ABCDAB”,得到的next数组如下

next[]数组改进

当 j 沿着next[]数组回溯时,可能产生一种情况是:连续几次回溯到的字符相同,即连续几次比较了模式字符串里相同的字符.
如上一节流程部分.
- p[4] p[2] p[0]都为元素a,实际只需要与 p[6] 比较一次即可.
未避免这种情况,可以对next[]数组回溯链上,连续相同的字符合并,直接取前一个字符对应位置next[]数组的值.由此产生的数组叫nextval数组.

c代码实现:

void GetNextval(char* p,int next[])
{
  int pLen = strlen(p);
  next[0] = -1;
  int k = -1;
  int j = 0;
  while (j < pLen - 1)
  {
    //p[k]表示前缀，p[j]表示后缀
    if (k == -1 || p[j] == p[k])
    {
      ++k;
      ++j;
      //
      if(p[k]==p[j])
      {
        next[j] = next[k];
      }
      else
      {
        next[j] = k;
      }
    }
    else
    {
      k = next[k];
    }
  }
}

编译 LineageOS 源码

发表于 2018-08-02 分类于 Android笔记阅读次数： Disqus：本文字数： 2.7k 阅读时长 ≈ 2 分钟

资料来源如下

编程环境

Ubuntu16.04

导语

记录编译LineageOS 15.1的过程,备忘.

阅读全文 »

Android随手记—Attempt to invoke interface method ''on a null object reference

发表于 2018-07-27 分类于 Android笔记阅读次数： Disqus：本文字数： 340 阅读时长 ≈ 1 分钟

编程环境

Android Studio 3.1.2

问题

myprivacy测试中一些应用在进入第二个activity时时常闪退,爆出空对象错误.

1	Attempt to invoke interface method 'boolean android.view.inputmethod.InputConnection.finishComposingText()' on a null object reference

但本身Activity跳转之间并没有输入控件.

过程

Google到了,类似故障.
https://github.com/facebook/react-native/issues/18884

解决

关闭 Android Studio的Advanced Profiling即可,非代码错误

备注

python—分析日志

发表于 2018-06-26 分类于编程语言/python 阅读次数： Disqus：本文字数： 731 阅读时长 ≈ 1 分钟

分析日志

需求

简单分析日志文件中两个时间差.
计算平均值,中位数,方差等.
图形化展示.

分析

用到的功能
- 系统io,只需要按行读入即可,当然需要指定gbk编码
- 科学计算的函数库
- 简单的画图库
python库
- 系统的 io 库即可
- numpy 库,大材小用
- matplotlib.pyplot,大材小用

示例

按行读入

with open(path,encoding='gbk') as f:
  for number, line in enumerate(f):
      #去空格
      line = line.strip().replace(' ','')
      #匹配字符串
      try:
          ln1 = line.index(str1)
      except ValueError as e:
          ln1 = 1

得到一个list 统计

print("数量",len(time))
print("平均值",np.mean(time))
print("最大值",np.max(time))
print("最小值",np.min(time))
print("方差",np.var(time))

画图

#格式化转化为时间
for ts in x :
  tx.append(datetime.datetime.fromtimestamp(ts/1000))

plt.plot(tx,time)
plt.title('len%d, mean%d, max%d, min%d' % (len(time),np.mean(time),np.max(time),np.min(time))) # 添加图形标题
plt.show()

算法—排序

发表于 2018-06-02 更新于 2018-06-12 分类于数据结构阅读次数： Disqus：本文字数： 1.8k 阅读时长 ≈ 2 分钟

记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

算法第四版

选择排序

步骤
- 寻找数组内最小的元素
- 与未排列的第一个元素交换位置.
- 重复1 2 知道数组排列完成.
代码
- 内循环比较当前元素与已知最小元素
- 外循环交换元素位置
性质
- 运行时间与输入无关..数组有序无序不影响时间.
- 数据移动最少.交换次数与数组长度为线性关系.
- 长度为N的数组 , 选择排序 N2/2 次比较,及N次交换.
分析
- 最直观的排序算法.
- 无法利用数组的初始状态进行优化.(后续重点)

冒泡排序

步骤
- 遍历未排列数组,比较两个相邻元素,依照规则交换/不交换位置.
- 重复1,直到完成数组排序.
代码
- 内循环冒泡整个未排序数组
- 外循环控制内循环冒泡范围
分析
- 可能是效率最差的
- 实际效率与选择排序差不多.

插入排序

步骤
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素,比较已排序序列,找到新元素位置
- 将新元素插入到该位置后
- 重复步骤直到排序完成.
代码
- 取出新元素
- 内循环查找新元素位置
- 插入新元素
- 外循环控制
性质
- 随机数组N, 平均需要 ~ N2/4 次比较及 ~N2/4 次交换.
- 最坏 N2/2 次比较 N2/2 次交换
- 最好 N-1 次比较 0 次交换(已经排序好的….😂)
分析
- 考虑了数组的初始状态,对于大多数元素有序的数组,插入排序可能是最快的.
- 但对于随机数组还不够.
优化
- 查找新元素位置: 二分法查找.而不是遍历.
- 插入新元素时,算法第四版建议,内循环改为类似冒泡方式,将大元素右移

希尔排序

对插入排序分析时,有这样的结论: 对于大多数元素有序的数组,插入排序时间最快,时间为线性级别.
将任意输入的数组大多数元素有序,然后最后使用插入排序.
插入排序对于随机数组的瓶颈在于,一个元素到达正确位置,一次只能移动一位.那么一次可以移动多位,交换至很远位置,可以改善插入排序的性能.
思路: 将数组等间隔 h 分裂,进行插入排序.拆分后的子数组,插入排序成本较低,进行插入排序.
完成后,原数组的有序性增加插入排序成本降低,之后再进行颗粒度更细的拆分-排序.一级一级的降低插入排序成本.直到最后进行 h=1的插入排序.
步骤
- 对数组进行间隔 h 的插入排序.
- 依照递增序列,取 h 值,直到 h = 1,为止,排序完成.
代码
- 内循环为间隔 h 的插入排序
- 外循环为计算 h 值的递增序列.
性质
- 希尔排序的性质并不容易概括,实际上没有完整概括.
- 目前可以证明的:希尔排序的运行时间达不到 N2 级别.
分析
- 考虑了数组初始状态.是如今提到的排序算法中,第一个可以适用与大容量数组排序的.
- h 递增序列的选择,会很大程度上影响希尔排序效果.实际工程中适用那种,需要自行选择.
- 嵌入式系统中没有快排等库函数可选时,首选希尔排序.之后再考虑其他排序算法.

归并排序

归并排序的实现与插入/希尔/选择排序不同.
归并排序依赖于归并操作.
- 归并 : 将两个有序数组合并为1个有序数组.
自顶向下递归
- 实际上是一个 sort 的递归调用.
- 将数组分为两个子数组
- 对子数组调用调用sort
- 再对第二层子数组调用 sort
- 直到最终子数组元素个数为1.递归返回开始执行 merge()操作.
自底而上迭代
- 直接归并子元素为1 的各个数组到子元素为2的数组.
- 再归并子元素为2 的各个数组到子元素为4的数组.
- 最后可能存在数组元素不相等,但是不影响归并.
- 直到归并的数组元素为 N.
实际上两者执行的过程是一样的,只是调用的角度不同.
性质
- 空间复杂度不是最优.
- 时间复杂度 NlogN
- 空间复杂度 N
优化
- 原理相同,对小的子数组使用其他高效排序,再归并.

快速排序

应用最为广泛. 原地排序时间成本 NlogN
但是! 坑不少…
原理
- 对于数组中某个元素都进行切分操作,大于/小于该元素的所有元素都在一边. 将数组切分为2个子数组. 递归,直到切分子数组元素个数为1,完成排序.
- 与归并排序在数组分解上一致.
步骤
- 取出数组中某个元素作为切分元素.
- 对数组执行切分.
- 对子数组执行 1 2 直到子数组元素个数为1.递归.
坑
- 原地切分,创建大量新对象性能上不可接受
- 保证访问不越界.
- 慎重处理最大最小元素.
- 相同元素谨慎处理.
性能改进
- 切分元素对性能影响及其重要.
  - 最糟糕情况: 大部分元素有序,使用极值去切分.
  - 为避免这种情况,快排之前,将输入数组乱序处理.
  - 对于大型数组取切分元素时考虑去3 选 1.
- 小数组
  - 使用切换到插入排序.
- 重复元素
  - 一分为二,对于存在大量重复元素的数组,无效的比较次数较多.
  - 改为三取样切分

三切分取样

切分时,不再一分为二,改为 < = >.三部分
三项切分的信息量最优.
对于存在大量重复元素的数组,三切分取样,直接将时间由 NlogN 降低到了 N .

算法—查找

发表于 2018-06-03 分类于数据结构阅读次数： Disqus：本文字数： 2.3k 阅读时长 ≈ 2 分钟

记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

算法第四版

查找

基于符号表的抽象来组织查找有关内容.分为 key-value ,有时又称字典.
分别介绍二叉查找树红黑树及散列表 3种经典的实现.

符号表

定义: 存储键值对的数据结构,支持put插入及 get查找操作.

API:

void put(Key key,Value val)
Value get(Key key)
void delete(Key key)
boolean contains(Key key)
boolean isEmpty()
int size()
Iterable<Key> keys()

规则
- 没有重复key
- key不能为空
- value不能为空
- 删除操作即使实现.
- key为不可变类型数据.
成本
- 使用比较次数来统计成本.
- 内循环不进行比较时,统计数组访问次数.

其他

有序符号表

额外API

main()
max()
floor(Key key)
select(int k)

无序符号表
- 经典的基于链表实现.

二叉查找树BST

数据结构:结点
- 一个唯一key
- 对应value
- 一条左链接
- 一条右链接
- 一个节点计数器(该节点的子节点总数)
get方法
表中存在对应方法即返回对应值,否则返回空.
代码:递归实现
- 实现get(Node x,Key key)
  - 查找Key 对应值,没有返回null
  - 对比 x 与 key 值.
  - 根据结果返回 get(x.right,key) or get(x.left,key)
- get由传入根节点调用 get(Node x,Key key)
put方法
存在则更新值,不存在则插入新值.
代码:递归实现
- 实现Node put(Node x,Key key,Value val)
  - x为空,则创建新节点并插入key val
  - 对比x key 值
  - x = key,则更新值.
  - 根据结果返回 put(x.right,key,val) or put(x.left,key,val)
  - 更新节点计数器
- put传入根节点调用Node put(Node x,Key key,Value val)
分析
- 如同union-find问题,二叉树生长的方式及平均深度对查找及插入的影响很大.二叉查找树性能非常依赖于 key分布足够随机.

有序符号表

最大最小
- 传入节点左链接是否为空? 返回传入节点 : 递归调用min(x.left)
- 传入节点左链接是否为空? 返回传入节点 : 递归调用mam(x.right)
向上/下取整
- 递归
  - 传入节点左链接为空.返回 null
  - 传入节点左链接 = key-value 返回传入节点
  - 传入节点左链接 < key-value 返回递归传入左链接
  - 传入节点左链接 > key-value 递归传入右链接
    - 判断返回值t 为空?
      - 不为空返回 t
      - 为空返回传入节点.
- 递归调用.
排名
- 与节点计数器有关.
- key = 传入节点,返回左子树节点总数.
- key < 传入节点,返回递归左子树.
- key > 传入节点,返回递归右子树.
删除最大/最小键
- 删除最大/最小值,因其子链接均为空,无妨.
删除 -二叉树中间呢?
- 查找到要删除的节点
- 保存父链接左右子链接.
- 选择右子树,查找最小节点.(不断选择左子树,直到遇到左子链接为空元素)
- 将右子树最小元素移植到已删除元素位置.
- 处理右子树最小元素右子链接(直接链接到父节点)
- 可能存在性能问题.
范围查找
- 首先遍历操作
  - 递归要不要简单
  - x为空? 返回
  - 过程处理.
  - 不为空, 递归左节点递归右节点.
- 在过程处理中进行过滤操作.
- 因二叉树数值相对有序,舍弃掉不存在想要值的子树.

平衡查找树

只使用二叉树而保持树生长的平衡,代价很高.
so,对节点的基础数据结构动一些手脚,引入 2-3 树.
最大的变化在于插入新元素.但随之带来的完美平衡的 2-3 树,让数据结构复杂度很值.

节点可以保存2个key,3个子链接.代表 <a ,a< <b ,>b 3种.
随之带来的好处,树可以一直保持为完美平衡.所有空链接,到根节点的距离相同.
查找
- 相对二叉树变动不大.依旧是递归实现.
- 在判断时加入了2 3节点的指向判断,难度不大,直到遇到空链接为止.
插入
- 我们所设想的依旧是通过递归的方式实现.尽量统一实现方式.
- 过程类似,查找插入位置->插入数据->恢复
  - 空节点
    - 直接插入数据即可
  - 2节点
    - 将2节点,变更为3节点.
  - 3节点(比较麻烦)
    - 父节点为空: 直接存入数据->节点变为4节点->4节点分解为3个 2节点,深度+1.
    - 父节点为2节点: 直接存入数据->节点变为4节点->将父节点变为3节点->4节点分解为两个 2节点.
    - 父节点为3节点: 直接存入数据->节点变为4节点->将父节点变为4节点->父节点向上反推过程,直到遇到2节点为止->4节点分解为两个2节点.
    - 整个过程: 存入变4节点,向上反推直到遇到空节点/2节点为止.分解恢复2-3树.
  - 性能
    - 即使最坏情况下,大小为N的 2-3 树,插入及查找操作访问节点必然不超过 lgN ,因为2-3树保持了完美的平衡.
    - 但额外的维护代码冗余,由此引出红黑树.

红黑树

将2-3树中 1个 3节点拆分为 2个2节点,中间使用红色链接.
插入/删除相较于2-3树,复杂.但基础数据结构简单.
牺牲一些平衡性,换来程序设计的便利.
前置要求
- 节点是红色或黑色。
- 根是黑色。
- 所有叶子都是黑色（叶子是NIL节点）。
- 每个红色节点必须有两个黑色的子节点。（从每个叶子到根的所有路径上不能有两个连续的红色节点。）
- 从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点。
数据结构
- 在二叉树基础上增加了节点颜色一项.其他不变.

方法实现

基础操作

右/左旋
颜色变化
查找
- 与二叉树查找相同.
插入
- 类比2-3树,更加复杂,但基本过程一致.
- 查找位置->插入节点->修复红黑树.
- 插入

散列表

算法—优先队列and堆排序and排序应用

发表于 2018-06-02 分类于数据结构阅读次数： Disqus：本文字数： 1.4k 阅读时长 ≈ 1 分钟

记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

算法第四版

阅读全文 »

算法— union-find

发表于 2018-05-31 分类于算法阅读次数： Disqus：本文字数： 1.2k 阅读时长 ≈ 1 分钟

记录学习数据结构的总结,希望可以不拘泥于细节和语言,重视应用与推演.

资料来源如下

算法第四版

问题描述

白话文: 一堆网点,随机相连,设计一个算法快速检查两个点是否联通.
物理对应: 闲的一堆金属触点,随机用导线连接,快速查找两个点电路通不通.

精确描述:

定义如下API:

UF(int N) ;//初始化 N 个点
void union(int p,int q)//连接p q
int find(int p)//N个点的分量标识符
boolean conneted(int p ,int q)//p q联通返回true
int count()//连通分量数量

设计算法的任务分解为
- 定义数据结构高效表示连通.
- 高效实现API方法.

实现算法

叙述原理,不拘泥于代码

quick-find

第一印象,所谓连通两个点,类似物理上的通路,表示两个点的id的值相同即可.
p q 连通,则标识量置为相同值.
分析
- 非常直观
- find conneted 非常快.
- union随着需要连接的节点数量而增大,每次执行 union 都需要遍历整个网格.时间复杂度平方.
- 大型网格union成本不可接收.
改进
- 从标识量入手,降低 union 复杂度,即使意味着 find conneted 等成本上升.
- 平衡各个方法成本.

quick-union

肯定要对标识量下手了,极端一点,将标识量改为类似树木生长的实现,每个连通拥有一个根元素.
conneted 判断两个节点的根元素是否相同.
union 连通即将两个连通的根元素链接.
find 直接返回根节点.
这样 union 的复杂度降低,找到根节点,新建一个链接即可完成.
分析
- 逻辑上也比较好理解,类似连通节点,用绳子串起来了.
- union 的时间复杂度降低到了线性级别.
- 但 find 的成本在最糟糕情况下到了平方级别.
- 最糟糕生长情况,从上到下,一个深度只有一个节点.
改进
- 由导致 find 最糟糕情况入手,避免这种情况.关注点在树生长的过程.

加权quick-union

我们的目标控制树的生长,即控制树生长的深度,尽力减少平均深度.
主要做法: union 时,区分大小树,(节点多的树为大),小树只能链接到大树.代码上要增加一个数组来标识一个连通的节点数.
分析
- 可以很好控制树生长的高度.
- 各个方法的时间复杂度,平衡很好.
- 但是还不是最完美.
改进
- 继续改进 union 时操作,控制树生长的高度.

路径压缩的加权quick-union

对 union 操作似乎无法继续改进.
但是从直觉上考虑,要控制树的深度,最直接的情况就是所有节点直接连接到根节点.
so,在 find 操作中加入这个转换,将所有节点直接连接到根节点.
分析
- 这是我们目前可以找到的最优解.
- 但不是所有操作都可以在场数级别.

总结

完整详细定义问题,找到解决问题所必须的抽象操作并定义 API
对于搜索类操作,改进算法的一个方面是: 增加一个数据点可以访问的维度.不限于周围元素,通过某种对应关系,拓展维度.