Cocoa

C++11下计算任意函数的执行时间

之前在写优化后的Sieve of Eratosthenes筛法时,写了一个函数用于计算另一个给定函数的执行时间,但是还不够通用,今天用C++11写了一个通用的版本。

#include <chrono>
#include <functional>
#include <future>
#include <stdio.h>
#include <type_traits>

/**
 *  @brief Give the elapsed time of any function
 *
 *  @param func_name Used in printf
 *  @param func The function that to be measured
 *  @param args Arguments of the given function
 *
 *  @return The return value of the given function
 */
template <class Function, class ... Args>
std::future<typename std::result_of<Function(Args...)>::type> runtime(const char * func_name, Function&& func, Args&&... args) {
    typedef typename std::result_of<Function(Args...)>::type return_type;
    typedef std::packaged_task<return_type()> task;
    auto t = std::make_shared<task>(std::bind(std::forward<Function>(func), std::forward<Args>(args)...));
    auto start = chrono::high_resolution_clock::now();
    auto ret = t->get_future();
    {
        (*t)();
    }
    auto end = chrono::high_resolution_clock::now();
    printf("%s: %lfs\n", func_name, ((chrono::duration<double>)((end - start))).count());
    return ret;
}

Ternary Search Tree的应用

最近在研究Key-Value数据库,思考之后打算尝试着重造轮子。目标是做一个高效Key-Value数据库,要实现一个Key-Value数据库本身并不困难,但是要做到存取、查询效率足够高的话,还是要靠背后的数据结构。在一番搜索之后,暂时决定用Ternary Search Tree来实现试试。
简单说明一下Ternary Search Tree,它的结构十分简单,每个结点储存一个字符,还有三个指针,分别对应下一个字符与当前字符的大小关系——小于、等于、大于。

下面是一个典型的三分搜索树的结点的结构

typedef struct tsnode {
    char c;
    struct tsnode * le, * eq, * gt;
} tsnode, * tstree;

查找/插入的字符小于当前字符就转向左子树,大于则转向右子树。当等于的时候,考虑两种情况,一是查找的字符已经是NULL,即需要搜索/插入的字符串已经走到了结尾。如果是插入的话,此时就可以将要插入的字符串的地址赋给当前结点指向等于关系的指针。如果是搜索的话,则可直接返回当前结点指向等于关系的指针(因为我们在插入时将这一指针赋值为了字符串的地址)。

Continue reading Ternary Search Tree的应用

Xcode文档下载插件

以前研究过如何获取Xcode里文档下载的URL,获取Xcode文档下载地址,然而前些日子有朋友说用这种方法已经获取不到了,而且在cycript中执行choose(NSURLSession)之后再回到Xcode时,程序会崩溃。

那么趁着今天晚上有些空闲时间,就研究了一下。于是就有了这么一个东西吧——XcodeDocsFetcher

XcodeDocsFetcher
XcodeDocsFetcher

 

P.S 其实大多数时候直接用Xcode下载也还是挺快的。下载完了可以参考这篇文章的方法安装文档,欺骗Xcode从本机安装Docset

K-means聚类算法计算给定图像中主要颜色

早在2012的时候,iTunes 11就可以从封面中自动提取出主要的颜色用在歌曲列表里的字体和背景上了。

iTunes
iTunes

然而当时的我万万没有想到的是,如今自己也需要这样的算法了。

简单考虑了一下,打算用OpenCV读图,然后自己实现一下K-means算法来计算出给定图像中主要颜色。

对于聚类算法的综合性介绍可以参见这篇zhihu上的回答,用于数据挖掘的聚类算法有哪些,各有何优势?,及其这篇scikit-learn上的文章,scikit-learn Clustering¶。本文不再对聚类算法展开叙述。

Continue reading K-means聚类算法计算给定图像中主要颜色

优化后的Sieve of Eratosthenes筛法

之前写了Sieve of Eratosthenes筛法,但总觉得算法还不够好,因为我们为每个数都留了一个bit,而显然的,除了2以外的偶数都不可能是质数,那么如果我们只为奇数申请bit位来标记的话,效率应该有进一步的提升。

在原来的算法中,我们初始化时是这样的

初始化
Sieve of Eratosthenes筛法初始化

那么,我们真的需要把偶数放进来吗?

Why on earth we need even numbers while we pick primes
Why on earth do we need even numbers while we pick primes

Continue reading 优化后的Sieve of Eratosthenes筛法

Sieve of Eratosthenes筛法

Sieve of Eratosthenes筛法是一种找质数的算法。我们知道,对于一个合数,那么它必定可以分解为两个质数相乘,比如21=3x7。那么我们也可以理解为,一个合数必定是一个质数的倍数,对于刚才的例子,21就是质数3的7倍(当然也可以说是质数7的3倍)。

那么我们求给定范围内的质数就可以利用这一点——先把所有的数列出来,然后从2开始,把所有数的倍数都去掉,这样我们就能留下给定范围内的质数了。举个例子,求42以内的所有质数,那么我们的算法大致上是这样操作的:

Continue reading Sieve of Eratosthenes筛法

Using generating functions to solve recurrence relations

前几天在《Discrete Mathematics and its Applications》上看到了这三道题,均要求使用生成函数求解,题目如下:

  1. ak = ak-1 + 2ak-2 + 2k, a0 = 4, a1 = 12
  2. ak = 4ak-1 - 4ak-2 + k2, a0 = 2, a1 = 5
  3. ak = 2ak-1 - 3ak-2 + 4k + 6, a0 = 20, a1 = 60

昨天在StackExchange[1]上询问之后,今天花了一早上的时间做了一遍,下面就是完整的步骤和总结。

  • Problem 1

 ak=ak-1+2ak-2+2k a0=4 a1=12

我们首先令f(x)为序列{ak}的生成函数,即

fx=k0akxk

然后我们对递推关系式(也就是上面大括号中的第一个式子)中的每一项都乘以xk,得

akxk=ak-1xk+2ak-2xk+2kxk

接着对每一项都取k从2开始的和

k2akxk=k2ak-1xk+k22ak-2xk+k22kxk

= k2ak-1xk+2k2ak-2xk+k22kxk

在这之后我们将对每一项都进行变形,变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。

k2akxk=k2akxk+a1x+a0-a1x-a0

=k0akxk-a1x-a0

= fx-4x-12


k2ak-1xk=xk2ak-1xk-1

= xk1akxk

= xk0akxk-a0

= xfx-4


k2ak-2xk=x2k2ak-2xk-2

= x2k0akxk

= x2fx


k22kxk=k02kxk-2x

=11-2x-1-2x-1

现在我们将变形后的式子替换回去

fx-4x-12=xfx-4+2x2fx+11-2x-2x-1
合并同类项,然后分解分式多项式得

fx=23·11-2x2+389·11-2x-89·11+x

根据生成函数与序列{ak}的关系,可得

ak=23C2+k-12-12k+389·2k-89·-1k

=231+k2k+389·2k-89·-1k

=449·2k+23k·k3-89·-1k
至此,我们解出了满足递推关系和初始条件的解
  • Problem 2

 ak=4ak-1-4ak-2+k2 a0=2 a1=5

我们首先令f(x)为序列{ak}的生成函数,即

fx=k0akxk

然后我们对递推关系式(也就是上面大括号中的第一个式子)中的每一项都乘以xk,得

akxk=4ak-1xk-4ak-2xk+k2xk

接着对每一项都取k从2开始的和

k2akxk=k24ak-1xk-k24ak-2xk+k2k2xk

= 4k2ak-1xk-4k2ak-2xk+k2k2xk

在这之后我们将对每一项都进行变形,变形之后将会消去求和符号。变形的目标是将和式写为f(x)和已知的项的和。

k2akxk=k2akxk+a1x+a0-a1x-a0

=k0akxk-a1x-a0

= fx-5x-2


k2ak-1xk=xk2ak-1xk-1

= xk1akxk

= xk0akxk-a0

= xfx-2


k2ak-2xk=x2k2ak-2xk-2

= x2k0akxk

= x2fx

最后的这个k2的和式处理稍微复杂一些

k2k2xk=k0k2xk-x

=xk0k2xk-1-x

=xk0kkxk-1-x

化简到这一步之后,下面我们对和式积分,然后再求导

=xk0kxk'-x

=xxk0kxk-1'-x

再来一次

=xxk0xk''-x

到了这一步之后就简单了

=xx11-x''-x

=xx1-x2'-x

=x1+x1-x3-x

现在我们将变形后的式子替换回去

fx-5x-2=4xfx-2-4x2fx+x1+x1-x3-x

合并同类项,然后分解分式多项式得

fx=21-x3+51-x2+131-x+61-2x2-241-2x

根据生成函数与序列{ak}的关系,可得

ak=2C3+k-13-1+5C2+k-12-1+13+6C2+k-12-12k-24·2k

=22+k1+k2+51+k+13+61+k2k-24·2k

展开、合并同类项

=2+13+5+6·2k-24·2k+3k+5k+6k·2k+k2

=20-18·2k+8k+6k·2k+k2

至此,我们解出了满足递推关系和初始条件的解
  • Problem 3

Problem 3的和处理方式前面的Problem 1十分相似,这里不再给出解答。
  • 总结

一般来讲,使用生成函数求解递推关系第一步是在递推关系式的各项上乘以xk,然后取k>=m(m为递推关系式的阶数,即如果是二阶递推关系式m就取2)时的和式并分别变形,最后通过生成函数f(x)与序列ak的关系解出。

  • References

[1]: How to solve these recurrence relations bu using generating function

いまが最高!