TimothyQiu's Blog

keep it simple stupid

Vim 中删除符合条件的行

No Comments

一说筛选数据首先映入脑海的是 grep,但 Windows 下就悲了个具了,从别程序复制(这时候觉得 GUI 不能管道真是太糟糕了)了一坨纯文本数据要筛选,为了这个还要临时保存个文件然后再开个 Cygwin 啊~MSYS 啊什么的真是太不适合我这种懒人了。于是还是要拜托好用的 Vim 来处理。

假设要在某坨数据中删除含有「kernel32」的行,可以执行:

:g/kernel32/d

其中中间的条件部分 kernel32 和一般的查找条件格式相同,最后部分的 d 则和一般的命令按键相同。如果要保留匹配的行则可以把开头的 g 替换为 g!

这样的写法实际是使用了 VIM 的「Multiple Repeats」功能,完整格式是这样的:

:[range]g[lobal]/{pattern}/[cmd]

详情请参考 :help :g :)

Lua 学习笔记:贰

No Comments

最近不是特别忙,于是就抽空开始继续看 PIL 了。

变量声明与 C 语言的不同

Lua 中有一个常见的用法,不论变量、函数都可以用下面这种方法保存到局部变量中(同时加快访问速度):

local foo = foo

书里加了个括号来解释这种写法:

The local foo becomes visible only after its declaration.

这一点需要瞎扯的是 C 语言里相应的东西。

int foo = 12;
int bar = 6;

void foobar(void)
{
    int foo = foo;
    int bar[bar];
}

与 Lua 不同,在 C 语言中初始赋值是声明之后的事情。所以这里函数 foobar 中的 foo 会被初始化为自己(而不是全局的 foo,所以值不确定),bar 却被合法地定义为一个含有 6 个元素的数组。

看似多余的限制

另一个有趣的现象是在 4.4 节中说到:

For syntactic reasons, a break or return can appear only as the last statement of a block; in other words, as the last statement in your chunk or just before an end, an else, or an until.

乍一看觉得加上这个限制真是麻烦,但想想这不正是 break/return 的正确用法么?因为其后的语句都永远不会被执行到,所以如果不是在块的最后写 break/return 是毫无意义的(调试除外)。虽然看上去是挺多余的一段话,但也算是说出了事物的本源。

函数的本质

第六章 More About Functions 中说到我们平时在 Lua 中写的函数声明

function foo (x) return 2*x end

其实是一种语法糖,本质上我们可以把它写成如下代码:

foo = function (x) return 2*x end

于是也就可以说

终于有用的知识

在第 47 页看到了一段令人泪流满面的代码和运行结果:

function derivative (f, delta)
  delta = delta or 1e-4
  return function (x)
           return (f(x + delta) - f(x))/delta
         end
  end

c = derivative(math.sin)
print(math.cos(10), c(10))
  --> -0.83907152907645 -0.83904432662041

最初我并不知道 derivative 是什么意思,但看了示例代码和运行结果,顿时恍然大悟:这货不就是导数吗?

高数里的东西竟然真的在现实生活中出现了!顿时觉得世界真美好 =ω=

看完了《C专家编程》

No Comments

最近终于把闲置良久的《C 专家编程》(Expert C Programming)看完了!光看书名挺可怕的,但它确实是一本读起来很轻松的技术书,我最初就是冲着穿插在正文和每章结尾的八卦去的。最喜欢第六章(运动的诗章:运行时数据结构)和第七章(对内存的思考),因为真的让人有茅塞顿开的感觉。

static 关键字的解释

C 语言的 static 关键字,其作用有二:修饰静态变量;将变量或者函数的作用域限制在文件范围。这两个技能怎么看都没有什么直接联系,以至于连作者都脚注「你可能会奇怪 static 的意义会相差如此之大」。于是我之前一直用「它就是这么定义的,你能怎么着?」来说服自己。

看完第六章和第七章,我终于可以用一个像样的理由来解释 static 这个奇怪的家伙了:它的主要作用是把被修饰的变量放到数据段(这样相对于不断在栈上生生死死的自动变量就「静态」得名至实归了),捎带着还会把被修饰的变量/函数的作用域限制得尽可能小。

由于所在的位置是数据段,这也解释了为什么静态变量和全局变量默认会被初始化为零(物理零)的问题 :)

对内存泄漏的看法

早在学习 C 之前就一直听大家把「内存泄漏」描述得跟巫师们描述伏地魔似的,所以后来虽然觉得指针什么的并不是什么很特别的东西,但对内存分配和回收什么的总是特别小心。以至于后来学了 C++ 之后觉得 RAII 什么的真是神器啊~恨不得以后再也不用裸指针了……

没错,这是好事。但内存泄漏也并不是不能放进一丝一缕:因为程序退出时操作系统会把分配给程序的内存块(重点在于这里也包括「堆」)一并回收,那么在程序即将退出时去释放那些在整个程序的生命周期内只会申请一次的内存是不是重复劳动,反而加重了系统的负担呢?

嗯~以上就是看完书最大的两点收获。另外第一次看第三章末尾八卦部分「一时间,可乐机似乎很快将成为 Internet 上最常见的硬件系统」的时候笑抽了 ^q^

常用排序算法

2 Comments

选择排序 Selection sort

每次从尚未排好的数组范围里选出一个最小的放到正确的位置。

C 语言版本:

void selection_sort(int array[], int size)
{
    int lhs, rhs;
    int min;

    for (lhs = 0; lhs < size - 1; lhs++) {
        min = lhs;
        for (rhs = lhs + 1; rhs < size; rhs++) {
            if (array[rhs] < array[min])
                min = rhs;
        }
        swap(array, lhs, min);
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void selectionSort(Iter begin, Iter end, Compare compare)
{
    for (auto iter = begin; iter != end; ++iter) {
        std::iter_swap(iter, std::min_element(iter, end, compare));
    }
}

快速排序 Quicksort

从数组里选出一个基准元素,通过交换位置让它前面的元素都比它小、后面的元素都比它大,最后分而治之。

C 语言版本:

void quicksort(int array[], int left, int right)
{
    if (left < right) {
        int pivit = right; // lazy :(
        int store = left;
        int i;

        for (i = left; i < right; i++) {
            if (array[i] < array[pivit]) {
                swap(array, i, store);
                store++;
            }
        }
        swap(array, store, pivit);

        quicksort(array, left, store - 1);
        quicksort(array, store + 1, right);
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void quickSort(Iter begin, Iter end, Compare compare)
{
    auto distance = std::distance(begin, end);
    if (distance > 1) {
        auto const pivot = std::next(begin, distance / 2);
        std::nth_element(begin, pivot, end, compare);
        quickSort(begin, pivot, compare);
        quickSort(pivot, end, compare);
    }
}

插入排序 Insertion sort

每次从尚未排好的数组范围取出一个元素,放到已排好的数组范围中的正确位置。(现实生活中排序时一般用的就是类似这种算法)

C 语言版本:

void insertion_sort(int array[], int size)
{
    int lhs, rhs;
    int cur;

    for (rhs = 1; rhs < size; rhs++) {
        cur = array[rhs];
        for (lhs = rhs - 1; (lhs > 0) && (array[lhs] > cur); lhs--)
            array[lhs + 1] = array[lhs];
        array[lhs] = cur;
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void insertionSort(Iter begin, Iter end, Compare compare)
{
    for (auto iter = begin; iter != end; ++iter) {
        std::rotate(std::upper_bound(begin, iter, *iter, compare),
                    iter,
                    std::next(iter));
    }
}

堆排序 Heapsort

保持未排数组为堆积树,每次摘取根结点,即可取出当前未排范围中的最大/最小值放入正确位置。

C 语言版本:

void sift_down(int heap[], int root, int end)
{
    int l_child = root * 2 + 1;
    int r_child = root * 2 + 2;
    int max = root; // max heap

    if (l_child <= end && heap[l_child] > heap[max])
        max = l_child;

    if (r_child <= end && heap[r_child] > heap[max])
        max = r_child;

    if (max != root) {
        swap(heap, max, root);
        sift_down(heap, max, end);
    }
}

void heapsort(int array[], int size)
{
    int i;

    // from last parent node
    for (i = (size - 2) / 2; i >= 0; i--)
        sift_down(array, i, size - 1);

    for (i = size - 1; i > 0; i--) {
        swap(array, 0, i);
        sift_down(array, 0, i - 1);
    }
}

C++ 版本:

template <typename Iter, typename Compare>
void heapSort(Iter begin, Iter end, Compare compare)
{
    std::make_heap(begin, end, compare);
    std::sort_heap(begin, end, compare);
}

嗯,基本上常用的就是这些啦~

什么,没有冒泡排序?好吧,我至今都想不明白像冒泡排序这样写起来没有选择排序方便、想起来没有插入排序方便的排序算法是怎么成为教科书中的天字第一号排序算法的。嗯……连奥巴马都知道不能用冒泡排东西。

最后,别忘了还有睡眠排序这样神奇的存在 :)

p.s. 代码里的交换两个元素的值,美观起见就直接写 swap 啦,具体实现随便挑 :)

AT&T 和 Intel 汇编语法的主要区别

No Comments

作为一个爱折腾的大好青年,补番之余还要补一些 Linux 下的基础,比如 GDB 的正确使用方法。但无论是看 gdb 还是 gcc -S 里的汇编,感觉都不能一下子接受这种设定。

后来发现,虽然同为 x86 汇编,但语法也分两大流派:之前上学时学的 Intel 语法,以及流行于 Unix/Linux 平台上的 AT&T 语法。

首先,两者最让人纠结的区别就是源操作数、目标操作数的顺序。AT&T 语法先写源操作数,再写目标操作数;Intel 语法先写目标操作数,再写源操作数:

AT&T
movl %esp, %ebp
Intel
MOV EBP, ESP
然后,另一个明显的区别就是指令的命名(或者说,操作数大小的指定方式)。AT&T 语法将操作数的大小表示在指令的后缀中(b、w、l);Intel 语法将操作数的大小表示在操作数的前缀中(BYTE PTR、WORD PTR、DWORD PTR):

AT&T
decw (%eax)
Intel
DEC WORD PTR [EBX]
再者,各种取址方式的表示。AT&T 语法总体上是offset(base, index, width)的格式;Intel 语法总体上是[INDEX * WIDTH + BASE + OFFSET]的格式:

AT&T
movl           0x0100, %eax
movl           (%esi), %eax
movl         -8(%ebp), %eax
movl  0x0100(,%ebx,4), %eax
movl 0x8(%edx,%ebx,4), %eax
Intel
MOV EAX, [0100]
MOV EAX, [ESI]
MOV EAX, [EBP-8]
MOV EAX, [EBX*4+0100]
MOV EAX, [EDX+EBX*4+8]

另外,各种非十进制数制下数字的表示方法。AT&T 语法用前缀表示数制(0x、0、0b);Intel 语法用后缀表示数制(h、o、b):

AT&T
movl 0x8   , %eax
movl 010   , %eax
movl 0b1000, %eax
Intel
MOV EAX,    8h
MOV EAX,   10o
MOV EAX, 1000b
最后就是零碎的东西的表示方法了。AT&T 语法要在常数前加 $、在寄存器名前加 % 符号;Intel 语法没有相应的东西要加:

AT&T
subl $0x30, %eax
Intel
SUB EAX, 30
于是,以上就是 AT&T 和 Intel 汇编语法的主要区别了……吧?