TimothyQiu's Blog

keep it simple stupid

C++11 Variadic Template

分类:技术

听说这个特性是很久以前了,总是读作「维拉迪克·坦普雷特」,一直没反应过来中文到底该叫什么,因为 C 时代的 Variadic Macro 我一直是很象形地读作「点点点」的 = =||

OK,扯远了。Variadic Template 对应中文应该是「可变参数模板」。

阅读剩余部分...

字符动画的制作方法

分类:技术

字符画版本的 Bad Apple 的流行应该是好多年以前的事情了吧……虽然当时也想过自己做一个,但一直觉得图片转字符画是一个很神秘的过程(据说 mplayer 可以直接把视频按字符画输出)。前两天做完 ssoaag 发现,貌似可以用这个东西的原理输出字符动画,于是就有了下面这个视频 = =

【似乎是教程】如何制作字符动画

看到最后的效果你会发现最终产出的字符动画最右一列字符是略有问题的,在视频里也注明了,是那个 GetColor 函数里有个失误 = = 会导致某些情况下取到下一行的颜色,需要 continue 掉,并且把最后除以的 w * h 变成真正有效的像素数。

SSOAAG

分类:技术

好吧,标题的意思其实是 Some Sort Of Ascii Art Generator……

把这两天的无聊成果放 GitHub 上了,按标题的意思可以理解为某种字符画生成器。

一句话解释原理

在一个 HTML 文档里,把一系列「■」字符作为像素点,并用 <span> 元素为每一个字符指定颜色。再把行距、字间距变小,就形成了一个画布。把图片中每一个像素的颜色赋值给对应的「■」字符就可以产出该图片的马赛克版本(类似于放大 N 倍后的效果)。而根据这个像素点的颜色值可以计算出灰度,再根据灰度的深浅选择相应的字符代替「■」字符(比如灰度小于 64 选 @、小于 128 选 :、其余选 .),就可以产出该图片的字符画版本了。

好吧,这不是一句话,这是一段话 Orz...

Bitmap

嗯,挑了个很矬的名字命名这个类。Bitmap 类主要是为了读取位图文件中的颜色数据而生的。在 Load 时解析位图文件内容,无论原来是什么格式,内部都用 0xAARRGGBB 的形式保存……………………(这是设想)

现实:色深和压缩方式好多……于是目前只把最简单的未压缩版本的 1位色(黑白)/ 4位色 / 8位色 / 16位色 / 24 位色 / 32 位色位图读取实现了。

于是 DIB Header 是 BITMAPINFOHEADER 版本及以后的未压缩位图应该都可以读取了,理论上 4 色位图也支持读取,但我真心没有找到可以产出一个 4 色位图的办法,汗~

程序崩溃的善后工作

分类:技术

说来,写 C/C++ 的程序,由于指针的存在,程序崩溃什么的也就没什么大惊小怪的了。人非圣贤,孰能无过嘛,而且个人觉得程序崩溃比出现错误的结果好调试多了:在 Visual Studio 里 Debug 版本 F5 调试运行直接可以断在崩溃的地方,方便调试。但 Release 版本就没这么幸运了 :(

如果说单纯是是调试 Release 版本,我只用过《游戏之旅》中介绍的勾选 Linker 选项中的 Generate Map File,然后通过崩溃提示信息中提供的 EIP 查这个 Map File 找到崩在哪个函数里,兴致高一点的根据反汇编一步步走下去兴许还能知道是崩在哪句上 :)

不过说到最终交付出去的程序,面对可能存在的各种未知问题,还是生成 Dump 文件,把崩溃那一刻的信息写进文件以供日后分析比较靠谱。

阅读剩余部分...

常用排序算法

分类:技术

选择排序 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 啦,具体实现随便挑 :)