TimothyQiu's Blog

keep it simple stupid

常用排序算法

选择排序 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++ 版本:

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 汇编语法的主要区别

作为一个爱折腾的大好青年,补番之余还要补一些 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 汇编语法的主要区别了……吧?

关于 WordPress 的标签

今天心血来潮把原来的标签「C/C++」拆成了「C」和「C++」两个,虽说没有了那个很碍眼的斜杠顿时清爽不少,但出现了一个小问题:这两个标签似乎没法并存。

虽然在标签列表里可以显示为两个标签,添加时也可以分别选择添加,但一旦保存,就会又变成只有「C」标签存在。

一番 Google 后,得知如果 Slug 相同会被判为同一个标签,但我的「C++」标签的 Slug 是「cpp」,应该没有这个问题。绕来绕去,失败了 N 多次后,发现在添加标签的地方输入「cpp」保存后就能正确添加「C++」标签。

也就是说让你输入标签的地方实际上要你输入优先判定的是标签的 Slug 而不是 Name?!这是什么坑爹的设定啊?(好吧~WordPress 里标签的 Name 是可以重复的,Slug 不允许重复……)

MinGW 下编译 freeglut

于是国庆一时兴起决定折腾下 OpenGL 玩玩。

本自然段纯吐槽,欢迎略过:学习 OpenGL 的一大幸事是有诸如 NeHe 这样的大神级教程可以参考,可惜开篇光讲怎么在 Win32 下创建空窗口就讲了洋洋洒洒 14 屏。Win32 API 创建窗口不是问题,问题是一来光空窗口就要这么长的篇幅我实在看不下去,二来他木有讲 Linux 版本的(不过示例代码有 Linux 版本下载)。要说创建窗口什么的简洁和跨平台方便还是 GLUT,而且碰巧 Google 到了 GLUTによる「手抜き」OpenGL入門 这篇,不愧是大学的讲义(?),质量非常不错。GLUT 本身貌似决定停留在这个世纪初了,于是改用 freeglut。Arch 下安装 freeglut 直接 pacman -S freeglut 即可,Windows 下就只得自己下载源码编译了。

README.cygwin_mingw 自带了一段 makefile,不过看起来还是手动 gcc 来得方便。

生成动态链接库

下载最新稳定版本源代码并解压后进入 src 目录,执行:

gcc -O2 -c -DFREEGLUT_EXPORTS *.c -I../include
gcc -shared -o freeglut.dll *.o -Wl,--enable-stdcall-fixup,--out-implib,libfreeglutdll.a -lopengl32 -lglu32 -lgdi32 -lwinmm

生成静态链接库

还是 src 目录,执行:

gcc -O2 -c -DFREEGLUT_STATIC *.c -I../include
ar rcs libfreeglut.a *.o

至此,freeglut 就编译好了。

最后可以把 include/GL 里的头文件扔进 MinGW 的 include/GL 文件夹,libfreeglut.a 和 libfreeglutdll.a 扔进 MinGW 的 lib 文件夹, freeglut.dll 扔进 MinGW 的 bin 文件夹方便使用。

p.s. 最初我是把 libfreeglutdll.a 命名成 libfreeglut.dll.a 的,结果静态链接的时候 -lfreeglut 似乎老是选择 libfreeglut.dll.a 而不是 libfreeglut.a,完全不知道为什么。不过反正 libfreeglutdll.a 也是 freeglut 的 README 里推荐的名字,罢了。

Google Talk Bot in Python

上班或者出门在外的时候有没有想过用家里闲着的电脑干点什么事呢?嘛~一切的可能性都得建立在你能连接得到自己的电脑之上才行。家里的电脑不比服务器,IP 并不固定,怎么办呢?解决方法挺多,比如花生壳,比如用 corn 发定时邮件……

对于我来说,写个会告诉你自己 IP 的 GTalk 机器人,想 SSH 连回家之前问一下是最方便的了。Lua 的 XMPP 库完全不懂怎么用,那么就先学现卖用 Python 写咯~

获取本机的公网 IP

由于使用了路由器,直接 ifconfig 是得不到公网 IP 的。那么可以直接在自己的网站上放一个 PHP 页:

<?php echo $_SERVER['REMOTE_ADDR']; ?>

或者利用现成的服务,比如 WhatIsMyIP.com 的自动化支持页面。有了这样一个可以获得访问者 IP 的页面地址,那么就可以用 Python 的 urllib 模块获得该页面的内容,从而得到自己的 IP 地址:

import urllib
ip = urllib.urlopen('http://www.whatismyip.com/automation/n09230945.asp').read()

简单的 GTalk 机器人

Google Talk 因为使用的是开放的 XMPP 协议,用各种语言实现机器人非常容易。(同样用 XMPP 协议的还有网易泡泡和人人桌面,而且据说微软的 Live Messager 最近也要支持 XMPP 协议了呢……腾讯啊~你不考虑来一发么?)比如接下来用的就是 xmpppy 库。

#! /usr/bin/env python
# vim: set fileencoding=utf-8

import xmpp
import urllib
import sys
from datetime import datetime

# 用来当机器人的用户名和密码
username = 'username@gmail.com'
password = 'password'

# 用来获取 IP 的 URL
ipurl = 'http://automation.whatismyip.com/n09230945.asp'

# 命令对应回复的处理
commands = {
    'ip':   lambda text: urllib.urlopen(ipurl).read(),
    'echo': lambda text: text,
}

def MessageCB(conn, mess):
    text = mess.getBody()
    user = mess.getFrom()

    if text is None: text = ''

    mail = user.getNode() + '@' + user.getDomain()
    print datetime.now().strftime('%H:%M:%S'), mail, text

    if ' ' in text: command, args = text.split(' ', 1)
    else:           command, args = text, ''

    if commands.has_key(command):   reply = commands[command](args)
    else:                           reply = unicode('主人已经被我干掉了', 'utf-8')

    conn.send( xmpp.Message(user, reply) )

def StepOn(conn):
    try:
        result = conn.Process(1)
    except KeyboardInterrupt: return 0
    return 1

def GoOn(conn):
    while StepOn(conn): pass

conn = xmpp.Client('gmail.com', debug=[])

if not conn.connect( server=('talk.google.com', 5223) ):
    print 'Unable to connect to server.'
    sys.exit(1)

if not conn.auth(xmpp.JID(username).getNode(), password, 'python'):
    print 'Unable to authorize.'
    sys.exit(1)

conn.RegisterHandler('message', MessageCB)
conn.sendInitPresence()
print 'Bot started.'
GoOn(conn)

上面的这段主要就是定义了两个命令 ip 和 echo,分别负责回答本机 IP 和学舌,其它情况下机器人都只会回复「主人已经被我干掉了」。

要扩展起来,在 commands 字典里添加条目即可 :)

初次写 Python 代码,不知道是不是写得 Pythonic……

p.s. 最近升级了 php 后网站就非常不稳定,暂时还不知道肿么办貌似是因为我某次把 crond 服务干掉了,于是长期没有 logrotate 的原因 =3=