2018 的目标

这个时间定下这个目标似乎有些晚了,不过也算是对之前的目标的一个总结: 不过这段时间的训练下来,总的来说还算是比较满意的。 Codeforce 因为才打了两场,…, 目前稳定在了蓝名,6000 名,LeetCode 目前是 2500 名,HackerRank 目前是 4000 名。 接下来的目的就是将 CF 达到紫名,然后 LC 刷进 1000,HR 就打进 2000 吧。 过段时间找到合适的网络环境之后,可以尝试下 TC 了。 一直吐槽没有一个量化的评判标准对一个程序员来说,现在,我自己觉得这些还不错,于是就开始玩这个游戏。 从之前的计划来看,应该是现在至少已经达到了 CF 紫名,只是很遗憾。。因为比赛时间的问题,一直没有一个很好的状态。 所以现在只能达到的几个目标是: LeetCode: 787 / 39565 (Global Ranking) HackerRank: 3097 / 158209 (Global Ranking) HackerRank: 2 金, 2 银, 6 铜 以上都是竞技比赛的成绩。不是刷题的。 自我感觉还是达到了预期的。 其实,最喜欢的就是这种竞技编程把对方踩在脚下的快感。 相对于 Codeforces 来说,这两边的比赛强度其实小很多,但是 CF 的时间点太不舒服了。也是不得不服老的一点。之前大学,通宵一天或者 2-3 点睡,第二天继续干活。现在,打一场比赛,到 2 点第二天完全是废人一个。只能说挑着比赛打。很明显的感觉不好刷。 说完之前的目标的完成度。现在说一下今年的几个小目标。 首先还是算法训练的。 LeetCode 进 500 Hackerrank 进 2000 Week of Code 每次都能金牌 HackHour 每次都能保银 其余比赛争取都能保银抢金 Codeforces 每次十点半的场都能参加,争取 Rank 在 300 内. 然后就是个人维护的几个项目: hexo 的几个插件,目前都是在修 bug 阶段。加密插件应该会在后期修改下密码输错之后的 alert,以及交互上的改进 firefox 的 json 插件,应该会添加上多个不同类型数据的判断,进行进一步的解析,将渲染层进一步的解耦 vim 的几个插件,主要还是进行维护,同时对 issue 进行跟进 其余没有人用的,还是保持着造轮子的心态进行学习 至于工作,目前首选和备选还有保底已经有了一个比较明确的规划,这个无须在此太费口舌。 总之,新的一年,应该会更加的好玩。

Gruvbox 显示 Syntastic 语法报错信息

Vim 的 Gruvbox 配色方案现在取代了我使用了两年的 Solarized,因为他的分辨率更胜一筹。所以,我决定了后者开始了退役。但是,遇到一个问题,因为 Syntastic 语法检测的时候,他和我现在使用的代码自动格式化插件有冲突。 在格式化之后,他的错误前标(sign)会出现在错误的位置。所以,为了更方便的查找错误,我一般是开语法错误高亮的。就像如下的效果: 但是在使用了 Gruvbox 之后,会出现这样的情况: 这个就很诡异了。他并没有给出对应的语法错误高亮。然后我又更换了几个其他主题,比如 desert,tomorrow 等,发现这个只是在 Gruvbox 上才会出现,所以我去他的 github 上提了这么个 issue 但是,并么有及时的得到回复。 所以,只好自己动手丰衣足食,在比对了 solarized 和 gruvbox 的代码之后,终于发现了端夷。 原来在语法配色中,有 SyntasticError 和 SyntasticWarning 这两个,而在 gruvbox/color/gruvbox.vim 中,它是如下的描述: ” Syntastic: {{{ call s:HL(‘SyntasticError’, s:none, s:none, s:undercurl, s:red) call s:HL(‘SyntasticWarning’, s:none, s:none, s:undercurl, s:yellow) hi! link SyntasticErrorSign GruvboxRedSign hi! link SyntasticWarningSign GruvboxYellowSign ” }}} 所以,理所当然的,它并不能很好的显示出对应的语法错误。只需要修改成如下就好了: ” Syntastic: {{{ call s:HL(‘SyntasticError’, s:red, s:none, s:underline, s:red) call s:HL(‘SyntasticWarning’, s:red, s:none, s:underline, s:red) hi! link SyntasticErrorSign GruvboxRedSign hi! link SyntasticWarningSign GruvboxYellowSign ” }}} 对应的修改之后的效果如下: 感觉不错。

使用非均匀量化处理图像数据

这篇文章其实也算是 “信息编码论” 的一个课程作业的总结吧. 因为之前对图像的处理, 基本都是作为一个 lib-caller , 对其中的原理部分一知半解. 正好研究生有这么个选修课程, 于是就硬着头皮选修了. 然后其中的一个实验就是要求实现一个 jpeg 压缩算法. 然后比较每个人的压缩效率, 同时还要比较信噪比. 所以正好有这个机会可以来尝试下好玩的部分. 我们首先拿到的数据是是 raw 文件. 一个 262144(512×512) bytes 的 raw 文件. 通过样例代码跑出来. 是著名的 Lena 图: 说道 raw 文件, 其实也很好理解, 这是最原始的图像数据, 其实就是一个 512×512 的二维数组, 每个点的数据为 0~255 的灰度值(现在只是黑白图片). 然后我们的任务就是使用各种可能的量化手段来进行图像的压缩. 为什么需要量化, 因为相比较于后期的压缩算法而言(在此也就是 jpeg 算法, 后面有机会再写), 分布越少, 后期的压缩效率更高. 所以, 这边开始最前期处理. 首先就是比较 low 的均匀量化. 将 0-255 均匀地分成四个部分 (0-64, 64-128, 128-192, 192-255). 然后将对应的中点值分别写入到对应的位置. 然后再跑一遍 jpeg 压缩算法. 可以得到均匀量化的图像: 当然, 结果也非常好, 信噪比也有: 22.88 , 在没有使用量化手段的情况下, jpeg 压缩为 262kb -> 66kb, 使用均匀量化之后, 最后的结果是 33kb. 节省了 50% 的空间. 然后就是重头戏了. 那就是非均匀量化. 以上, 我们都只是采用了人为设定的中心点, 进行强行的划分. 所以必然的一个结果就是, 并不能很好地表现出点的分布特性. 而最好的表现点的分布特性的算法莫过于聚类. 然后聚类中, 最常用的便是 k-means 算法. 但是, 在信息论领域, 有一个类似的但是名字不同的算法, 那就是 Lloyd 算法. 对应的数学表达是; 其实就是 k-means … 所以这边使用了这个算法进行设计. 也是从四个开始. 设定初始的四个中心之后, 跑一遍代码, 最后得到这样的一个结果: 可以看到已经好了很多, 对应的信噪比是: 25.98 了. 之后,为了更好地提高信噪比, 就人为地多设定几个初始点. 当达到 8 个的时候: 此时的结果已经很棒了. 信噪比达到了 31.68. 但是, 对应的理论结果就是图像结果变大, 但是实际上, 它是最小的一个. 具体的原因, 之后会写一篇关于 jpeg 算法的文章分析. 此时, 基本就明白了自己的大概思路, 为了写这个课程作业. 只需要不断地改变 kmeans 的初始点位, 找到最优解即可. 但是人工写太过麻烦. 所以我们有了 Kmeans++ 算法. 用它可以确定最优的 k 值. 基本这样, 课程的作业也能完成了. 但是, 为了追求优秀, 就要从一维的结果推广到 N 维. 也就是在多维空间的聚类算法. 其中, 最常用的就是最近邻算法(NN). 通常情况, 我们有三种进行距离判断的函数: Minkowski Distance Euclidean Distance CityBlock Distance 这三种近邻算法分别可以拿到如下的几个中心: 当数据到了多维之后, 就到了乘积量化. 乘积量化正好是我课程论文最后的主要内容. 其实也是一个简单地算法. 主要的原理就是分治. 将多维空间拆成多个低维空间, 然后分别求出不同低维空间的中心点. 然后通过笛卡尔积的方式, 求出多维空间的中心点阵. 最后通过排除法选出最优解. 这个的话, 之后可能有机会会再写个文章纪念下. 最后附一个测试代码: /****************************************************************************** Copyright © 2017 TangDongxin Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files…

MJsonViewer v2.0 插件发布

可能是第一个支持嵌套 json 解析的火狐 json 插件。正如,之前写的那样,因为持续开发,主要是因为喜欢火狐,而且确实有新的需求进来了。 距离上一次的插件发布已经过去了两个多月了,其实总的使用下来还是比较舒服的。不过,有几个小的缺点也还是要说一下。如果一个 json 中的 k-v 的 v 包含了一个嵌套的 json,一般的 json 解释器都是将其作为 string 来解析。 这就带来了一个问题。在软件开发中,我们经常会在 json 中嵌套 json,从而导致在浏览器中的浏览体验极差。加上最近的四个需求: MikeCoder/MJsonViewer [Feature request] Detect if a string value contains JSON and provide an option to format it enhancement MikeCoder/MJsonViewer [Feature request] Option to hide items and bytes counters enhancement MikeCoder/MJsonViewer [Feature request] Alternative Content-Types are not supported (e.g. application/hal+json) enhancement MikeCoder/MJsonViewer [Feature request] Folding for very long strings 我就决定先写一个验证测试版本出来,不过之后的主要任务就是在不破坏原有 json 结构的情况下更好的实现内部 json 的解析。 这个也算是,在总用户到达 2.5k 之后,的一个小的升级吧。 下载地址:https://addons.mozilla.org/en-US/firefox/addon/mjsonviewer/ 代码地址:https://github.com/MikeCoder/MJsonViewer Done.

使用 C 尝试内存管理

在之前苦读『垃圾回收的算法与实现』,也想着什么时候能够自己手动实现一把。加上自己对 redis 也还是算熟悉,也是知道他的内存碎片问题的严重性。所以,就想着这两者结合看看能有什么好玩的地方。 首先就是,如何进行内存的管理。众所周知,C 的内存管理通常使用 malloc 和 free 两个操作进行,于是乎,如果我们需要进行申请堆区的内存空间,(以下的讨论通通以堆区申请内存空间为主,栈区分配的内存通通不考虑),往往就会直接的 malloc(sizeof(xx)),然后再在不需要的时候直接调用 free 进行。但是,操作系统在进行内存分配的时候,并不能保证多次 malloc 的物理空间地址连续,加上内存的换页,就会导致性能的低下,操作系统需要不停的进行换页操作。 而且,在 MacOS(10.13.1) 上,malloc 的策略是,如果有可用的连续空间,直接分配,如果没有逻辑连续的可用空间,则会不停的继续申请。如果超过了系统限制,即使空白部分的总和大于你需要的大小,但是依旧会分配失败。其他的内存分配函数还有 realloc 和 calloc,不过也都是换汤不换药。总的还是选用第一个可用的地址。 接下来就是看,多次的内存申请和使用伪内存管理之后的效率差距: #include <ctype.h> #include <errno.h> #include <float.h> #include <iso646.h> #include <limits.h> #include <locale.h> #include <math.h> #include <setjmp.h> #include <signal.h> #include <stdarg.h> #include <stddef.h> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #include <wchar.h> #include <wctype.h> #define TIMES 100 #define SIZE 10 void print(void *mem, int size) { int i; unsigned char *p = mem; for (i = 0; i < size; i++) { printf(“%d “, *(p + i)); } printf(“”); } void *m_brw(void *mem, unsigned long long len) { return mem + len; } void m_rtn(void *ptr, unsigned long long len) { memset(ptr, 0, len); } int main() { clock_t start,finish; double totaltime; start=clock(); int i; for (i = 0; i < TIMES; i++) { int *a = (int *)malloc(sizeof(int)); printf(“%x”, a); *a = i; free(a); } finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; printf(“%lf”, totaltime); void *block = malloc(SIZE); memset(block, 0, SIZE); start=clock(); for (int i = 0; i < TIMES; i++) { int *a = (int *)m_brw(block, sizeof(int)); *a = i; /* print(block, SIZE); */ m_rtn(a, sizeof(int)); /* print(block, SIZE); */ } finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC; printf(“%lf”, totaltime); return 0; } 以上便是测试代码,使用 m_brw 和…

Makefile 的多目录结构写法

因为最近迷上了 C 语言。所以开始进行的一些项目的编写都是采用的 C 语言。这么就会带来一个小的问题,就是 makefile 的写法问题。 比如一个目录结构是这样的: . ├── LICENSE ├── ReadMe.md ├── TODO.md ├── makefile ├── src │   ├── makefile │   └── … └── test ├── makefile └── … 如何协调好三个 makefile 的作用。这边我自作主张的给自己的 makefile 链做了一个如下的约定: 每一个单独的 makefile 可自己执行 makefile 中的变量以上级传递的变量为准 如果出现冲突,以上级为准 最后的安装和集成工作由上级进行,比如 src 中的 makefile 只进行编译成 .o 的操作,但是最后编译成 so 或者静态连接文件则由根目录的 makefile 决定。 以此为基础,所以便有了如下的 makefile 写法。 项目更目录的 makefile # /makefile ifndef CC CC = gcc export CC endif ifndef CFLAGS CFLAGS = -g -Wall -std=c89 export CFLAGS endif build: cd src && make .PHONY: test test: cd test && make test .PHONY: clean clean: cd src && make clean cd test && make clean src 目录下的 makefile # /src/makefile ifndef CC CC = gcc endif ifndef CFLAGS CFLAGS = -g -Wall -std=c89 endif main: main.c $(CC) $(CFLAGS) -o main main.c .PHONY: clean clean: rm main test 目录下的 makefile # /test/makefile ifndef CC CC = gcc endif ifndef CFLAGS CFLAGS = -g -Wall -std=c89 endif test: test_main ./test_main test_main: test_main.c $(CC) $(CFLAGS) -o $@ test_main.c .PHONY: clean clean: rm test_main 不过也有比较麻烦的地方,就是如果有多个 lib 路径,比如说 lib 文件夹,里面有 src 需要的类库。需要链接。 那就可以通过 VPATH 方式进行实现。 . ├── lib │   ├── lib.c │   ├── lib.h │   └── makefile ├── makefile ├── src │   ├── main.c │   └──…

如何阅读 C 语言的声明

众所周知,C 语言的一大难点就在于变量声明。 比如说如下的几个例子: char* const *(*next)(); char *(*c[10])(int **p); void (*signal(int, void(*)(int)))(int); 基本上每一个都是晦涩难懂,看了简直像杀人。但其实也是相对来会所比较简单的一个。如果熟悉编译原理,其实可以通过人脑编译器的手段来解决难懂问题。毕竟,代码也需要编译器进行翻译。 首先我们得知道运算符号的优先级顺序。这里只说在声明期间会出现的符号。主要分为变量名,括号内内容,后缀操作符如:[], (),前缀操作符如: *,类型描述符如:const, volatile, 其中, 如果 const 或 volatile 后面跟着类型如 int, long 等,那么它作用于类型。其他情况下,const 和 volatile 作用于左边的指针。 理解了这个顺序,就可以来看看如何解读第一个声明了。 首先,next 先拿出来,说明,next 是一个 … 变量。声明变成了 char* const *(*)(); 然后看到 *,说明 next 是一个指向 … 的指针。声明变成了 char* const *(); 然后就是 ()符号,说明 next 是一个指向函数的指针。然后再是一个 * 表明读取指针的内容即该函数地址。所以声明等价于 char* const func(); 那么接着看,char* const 就表示返回值是一个 const 字符指针。 所以该声明就能读出来了。即 next 是一个函数指针,该函数返回值是一个 const 字符指针。 再来看看第二个声明: 首先 c 先拿出来,一看有后缀操作符,那就直接拿出来 c[10],说明 c 是一个大小为 10 的数组。声明变成了 char *(*)(int**p); 然后可以看到有一个指针操作符,那就可以看成,c 是一个大小为 10 的数组,内容是指针。声明变成了 char *()(int **p); 因为可以看到紧跟的是一个后缀操作符,可以知道,这是一个函数,它接受的参数是一个指向 int 的指针的指针(可以理解为二维数组)。 往前就是一个 * 号,表示读取该指针的内容,最前面的 char 表示该函数的返回值是字符。 所以,最后这个声明也能看出来了:c 是一个大小为 10 的数组,数组的类型是一个指向函数的指针,该函数接受一个指向 int 的指针的指针,返回值是 char。 最后就可以看最后的一个声明了。 首先拿出来 signal ,紧跟着是一个后缀操作符,所以可以读作 signal 是一个函数,他接受的参数是一个 int 和一个返回值为 void 接受参数为 int 的函数指针。 声明变成了 void (*)(int);,是不是突然就简单了。这个就可以读作一个指向函数的指针,该函数返回值为 void 参数为 int。 所以最后的声明也就出来了。signal 是一个函数指针,它指向的函数读入的参数为 int 和一个返回值为 void 接受参数为 int 的函数指针,指向的函数的返回值也是一个返回值为 void 参数为 int 的函数指针。 虽然有点拗口,但是实际使用的时候,其实也很简单。 #include “signal.h” #include “stdio.h” #include “sys/signal.h” void f(int a) { printf(“%d”, a); } int main(int argc, char *argv[]) { void (*sfp)(int); sfp = f; signal(SIGINT, sfp); int a; scanf(“%d”, &a); return 0; } 这样的话其实就完成了一个绑定。在这个例子里,你可以通过 ctrl + c 来触发一个 SIGINT 信号。然后系统会自动的执行那个回调函数。当然你也可以手动触发这个函数:(*signal(SIGINT, sfp))(2);, 当然,通常情况是,异常退出。 以上就是刚看完的一个理解声明的方法以及几个简单的实例。不得不说,和其他严格限制程序员想象力的高级语言不同。C 只定义了简单的规则,然后留有大片的空间可供发挥。非常喜欢这个。

JSON 解析器

这篇博客主要是最近开始玩 C,所以准备找个东西练手,突然发现,顺手写个 JSON 解析器吧。于是就开始了。 相对于其他比较成熟的上层语言。C 主要的问题就是没有基础的数据结构,而且相对于弱类型语言而言,C 的类型在解析的时候有个类型转换的坑。但是相对于其他的强类型语言而言,C 又有一个好处,那就是没有一个 void* 解决不了的问题,如果有,那就用两个。 不过相对于工作时的清闲,现在上课的时候确实没有什么时间进行额外的代码编写。所以断断续续写了一周多。 主要的使用方法就是: struct value *val = parse_new(); char *json1 = “{\”fff\”:[2,4,5,6]}”; parse(val, json1); map_display(*(struct map*)val->value); struct value key; key.type = STRING; key.value = (void*)”fff”; list_display(*(struct list*)(map_find(*(struct map*)val->value, key)->value)); 首先初始化一个 val 对象作为头,然后直接调用 parse 函数。这样就可以把数据解析完成了。 其实还是挺简单的。主要的目的也只是检查自己对 C 语言的熟悉程度。目前也只是个简单的版本。之后会慢慢的进行优化。比如目前就不支持 null, 非十进制数字解析等等。 说道 JSON 的解析,其实 JSON 本身的格式非常的简单。按照 官网的说法,状态转换也无外乎以下几种: 相对于细节上,整体看下来的话其实更简单:{ “key”: value } 和 [ value ],而 value 有可能是 list,和 map 两种数据结构。 而判断就是第一个字符是否是 ‘[‘ 或者 ‘{‘。然后就是一个递归向下的解析。 所以总体而言还是简单的。不过写下来的第一个感觉还是觉得 makefile 很棒,通过不同的规则,可以实现粒度为文件的编译控制。不过因为失误(Java 的 import 习惯),导致了一个环形依赖的错误。 不足: 比如,在 list.c 和 map.c 中有 list_display 和 map_display 两个函数,但是,我会在 value.c 中的 value_display 中进行调用。因为需要根据 value->type 的不同,使用不同的 display 方式,所以需要在 value.h 中 include “list.h” 和 “map.h”,但是在这两个文件中,我也需要 include “value.h” 这就带来了环形依赖。解决的办法就是额外增加一个 utils.h 的模块,主要作用就是根据 value->type 的不同来采取不同的展示方法。 同时,前一篇的 C OOP 编程也提到了另一个解决方案,就是通过函数指针来做。这个会在之后完成。 TODO:(闲的时候再做) 支持 JSON 所有的特性,比如各种数字 尽量使用流的方式进行读取,而非现在的先读入再解析 优化基础数据结构,同时优化解析后的读取方式 JSON 吐槽的地方 因为历史原因,JSON 是基于 JavaScript 发展起来的,所以也带上了明显的 JavaScript 标签。有一个非常严重的错误就是,在 json 中,并没有对 number 这个作出明确定义。比如,在 C 中,int 对应的 32 位整形变量。但是 JSON 不管啊,不管多长多大的数字,通通都是 int,甚至远远超出 long long 的范围都不管。 所以,会有这么个现象,在联通 APP 上充值写上 9*10^100 时,使用微信付款,最后微信只需要付款 INT_MAX 即宣告交易成功。(支付宝就么有这个 bug)。如果使用 XML 就有机会减少此类事情的发生。而且在网络上传输的数据,我还是觉得 String 比 number 类型好。 如果说要我选一个通用性更高的协议或者说更完备的序列化手段,messagepack 明显更好。

C 的假装 OOP 写法

之前微博上说 C 的一个好处就是没有什么是一个 void* 解决不了的,然后因为自己用 C 写一个小程序,遇到了一个问题,就是因为 C 是强类型,但是如果需要写一个相对通用的数据结构。这个稍微有点麻烦。 比如说,hashmap,我们常用的都是 <string, string> 的一个 map,于是,相对来说的话,hash 函数比较容易。但是,如果是需要实现 Java 那样的通用数据结构呢,是不是需要对每个特定的数据对象写一个? 所以这边就扯到了这么个比较好玩的技巧。 先看下效果: main.c #include “value.h” #include “value_a.h” #include “value_b.h” int main(void) { struct value v1; value_a_instance(&v1); v1.set(&v1, (void*)”hello”); v1.display(&v1); printf(“%lld”, v1.hash(&v1)); struct value v2; value_b_instance(&v2); double a = 2.0f; v2.set(&v2, (void*)&a); v2.display(&v2); printf(“%lld”, v2.hash(&v2)); printf(“%lf”, *(double*)v2.data); return 0; } value.h #ifndef VALUE_H #define VALUE_H 1 #include <stdio.h> #include <stdlib.h> #include <assert.h> struct value { void (*display)(struct value*); uint64_t (*hash)(struct value*); void (*set)(struct value*, void*); void (*instance)(struct value*); void *data; }; #endif /* ifndef VALUE_H */ 我们可以看到,通过对 value 调用 value_x_instance 函数可以拿到属于新的类型的对象指针。 这个新的类型主要包含了几个函数指针,主要用途就是通过注入的不同指针,对其进行 value 操作。 value_a.h #ifndef VALUE_A_H #define VALUE_A_H 1 #include “value.h” void value_a_display(struct value*); uint64_t value_a_hash(struct value*); void value_a_set(struct value*, void*); void value_a_instance(struct value*); #endif /* ifndef VALUE_A_H */ value_a.c #include “value_a.h” void value_a_display(struct value* v) { puts((char*)v->data); } uint64_t value_a_hash(struct value* v) { return 2; } void value_a_set(struct value* v, void* data) { assert((char*)data); v->data = data; } void value_a_instance(struct value* v) { v->data = (void*)malloc(sizeof(char)); v->display = value_a_display; v->hash = value_a_hash; v->set = value_a_set; } 这两个文件就是对此函数的诠释,只不过这边比较简单,所以很多的细节都是简化的。 这样一来,如果我们需要进行存储数据结构的编写,就觉得很舒服了。比如 list 的定义就可以如下: struct list { list *pre; list *next; struct value *node; }; 然后通过 insert 的参数,对其 value 进行注入。不过有个不好的地方,这边在调用内部方法的时候,需要指定 self 参数。这个实属无奈之举。本来还想通过栈帧找到父结构体,但这个代码就太依赖于系统,编译器。所以只能这样。 不过,这就刚刚好了。其实还有一种方法,通通 void* 然后再加一个类型模版,不过这就是要理一下 C++…