Monthly Archives: March 2016

Hack Space

Enhancement of Ternary Search Tree

Leave a comment

As we memtioned in the Application of Ternary Search Tree, a typical node structure of TST is

正如我们在Ternary Search Tree的应用中提到的那样，一个典型的TST结点的结构题如下

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

Its insertion and searching are really fast when the string in given strings set is short (I'm not going to define the exactly length of a string that we could say it's short, but we will see the decrement of running time after we applying the improvement). When the string length increases, the insertion and searching time grow, of course. The question is, we only compare one char at a time.

当给定输入集的字符串都比较短的时候（我并不打算定义低于多少个字节长才叫短，但是在应用了改进之后，我们将会明显看见运行时间的减少）。当字符串长度增加时，理所当然的，插入和搜索的时间也会增加。但问题在于，我们一次只比较了一个字符。

Continue reading Enhancement of Ternary Search Tree →

Mark

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

Leave a comment

之前在写优化后的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;
}
Hack Space

Ternary Search Tree的应用

1 Comment

最近在研究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的应用 →