做有积累的事情

03
May

vim grep插件

By admin|vim|Be the first to comment!

我们经常要在vim里面grep出东西,然后一个一个打开看,很不方便

写了一个插件

可以再vim里面选中,然后g 即可.
因为用的是vim里面的grep,vim 默认会把结果存再quick fix里面
接下来打开的时候直接在quick fix里面打开,非常方便

nnoremap <leader>g :set operatorfunc=<SID>GrepOperator<cr>g@
vnoremap <leader>g :<C-U>call <SID>GrepOperator(visualmode())<cr>

function! s:GrepOperator(type)
    let saved_unnamed_register = @@

    if a:type ==# 'v'
        normal! `<v`>y
    elseif a:type ==# 'char'
        normal! `[v`]y
    else
        return
    endif
    execute "grep! -Rn " . shellescape(@@) . " ."
    cw
    let @@ = saved_unnamed_register
endfunction

将代码保存再.vim/plugin/grep.vim 即可
你可以.vimrc里面添加map

" add quickfix map
nnoremap <leader>cn :cn<cr>
nnoremap <leader>cp :cp<cr>
nmap <leader>cw :cw 10<cr>
02
May

vim复制插件

By admin|vim|Be the first to comment!

vim复制的时候不发复制到c-v的复制缓冲区,很麻烦,自己动手,丰衣足食

nnoremap <silent>y :set operatorfunc=<SID>Pbcopy<cr>g@
vnoremap <silent>y y:<C-U>call <SID>Pbcopy()<cr>

function! s:Pbcopy()
    execute 'call system("pbcopy", getreg("\""))'
    execute 'call system("xsel --clipboard --input", getreg("\""))'
endfunction

将代码保存再.vim/plugin/copy.vim的文件即可

ubuntu环境下 默认得安装一下xsel这个东西

 

26
Mar

Ternary Search Trees 三分树

By admin|algorithm, c|Be the first to comment!

经常碰到要存一堆的string, 这个时候可以用hash tables, 虽然hash tables 查找很快,但是hash tables不能表现出字符串之间的联系.可以用binary search tree, 但是查询速度不是很理想. 可以用trie, 不过trie会浪费很多空间(当然你也可以用二个数组实现也比较省空间). 所以这里Ternary Search trees 有trie的查询速度快的优点,以及binary search tree省空间的优点.

实现一个12个单词的查找

这个是用二分查找树实现,n是单词个数,len是长度,复杂度是O(logn * n),空间是n*len

这个是用trie实现,复杂度O(n), 空间是 这里是18 * 26(假设只有26个小写字符),随着单词长度的增长等,需要的空间就更多

这个是Ternary search tree, 可以看出空间复杂度和binary search tree 一样, 复杂度近似O(n),常数上会比trie差点.

介绍

Ternary search tree 有binary search tree 省空间和trie 查询快的优点.
Ternary search tree 有三个只节点,在查找的时候,比较当前字符,如果查找的字符比较小,那么就跳到左节点.如果查找的字符比较大,那么就跳转到友节点.如果这个字符正好相等,那么就走向中间节点.这个时候比较下一个字符.
比如上面的例子,要查找”ax”, 先比较”a” 和 “i”, “a” < "i",跳转到"i"的左节点, 比较 "a" < "b", 跳转到"b"的左节点, "a" = "a", 跳转到 "a"的中间节点,并且比较下一个字符"x". "x" > “s” , 跳转到”s” 的右节点, 比较 “x” > “t” 发现”t” 没有右节点了.找出结果,不存在”ax”这个字符

构造方法

这里用c语言来实现
节点定义:

typedef struct tnode *Tptr;
typedef struct tnode {
    char s;
    Tptr lokid, eqkid, hikid;
} Tnode;

先介绍查找的方法:

int search(char *s) // s是想要查找的字符串
{
    Tptr p;
    p = t; //t 是已经构造好的Ternary search tree 的root 节点.
    while (p) {
        if (*s < p->s) { // 如果*s 比 p->s 小, 那么节点跳到p->lokid
            p = p->lokid;
        } else if (*s > p->s) {
            p = p->hikid;
        } else {
            if (*(s) == '\0') { //当*s 是'\0'时候,则查找成功
                return 1;
            } //如果*s == p->s,走向中间节点,并且s++
            s++;
            p = p->eqkid;
        }
    }
    return 0;
}

插入某一个字符串:

Tptr insert(Tptr p, char *s)
{
    if (p == NULL) {
        p = (Tptr)malloc(sizeof(Tnode));
        p->s = *s;
        p->lokid = p->eqkid = p->hikid = NULL;
    }
    if (*s < p->s) {
        p->lokid = insert(p->lokid, s);
    } else if (*s > p->s) {
        p->hikid = insert(p->hikid, s);
    } else {
        if (*s != '\0') {
            p->eqkid = insert(p->eqkid, ++s);
        } else {
            p->eqkid = (Tptr) insertstr; //insertstr 是要插入的字符串,方便遍历所有字符串等操作
        }
    }
    return p;
}

同binary search tree 一样,插入的顺序也是讲究的,binary search tree 在最坏情况下顺序插入字符串会退化成一个链表.不过Ternary search Tree 最坏情况会比 binary search tree 好很多.

肯定得有一个遍历某一个树的操作

//这里以字典序输出所有的字符串
void traverse(Tptr p) //这里遍历某一个节点以下的所有节点,如果是非根节点,则是有同一个前缀的字符串
{
    if (!p) return;
    traverse(p->lokid);
    if (p->s != '\0') {
        traverse(p->eqkid);
    } else {
        printf("%s\n", (char *)p->eqkid);
    }
    traverse(p->hikid);
}

应用

这里先介绍两个应用,一个是模糊查询,一个是找出包含公共前缀的字符串, 一个是相邻查询(哈密顿距离小于某个范围)
模糊查询
psearch(“root”, “.a.a.a”) 应该能匹配出baxaca, cadakd 等字符串

void psearch1(Tptr p, char *s)
{
    if (p == NULL) {
        return ;
    }
    if (*s == '.' || *s < p->s) { //如果*s 是'.' 或者 *s < p->s 就查找左子树
        psearch1(p->lokid, s);
    }
    if (*s == '.' || *s > p->s) { //同上
        psearch1(p->hikid, s);
    }
    if (*s == '.' || *s == p->s) { // *s = '.' 或者 *s == p->s 则去查找下一个字符
        if (*s && p->s && p->eqkid != NULL) {
            psearch1(p->eqkid, s + 1);
        }
    }
    if (*s == '\0' && p->s == '\0') {
        printf("%s\n", (char *) p->eqkid);
    }
}

解决在哈密顿距离内的匹配问题,比如hobby和dobbd,hocbe的哈密顿距离都是2

void nearsearch(Tptr p, char *s, int d) //s 是要查找的字符串, d是哈密顿距离
{
    if (p == NULL || d < 0)
        return ;
    if (d > 0 || *s < p->s) {
            nearsearch(p->lokid, s, d);
    }
    if (d > 0 || *s > p->s) {
            nearsearch(p->hikid, s, d);
    }
    if (p->s == '\0') {
        if ((int)strlen(s) <= d) {
            printf("%s\n", (char *) p->eqkid);
        }
    } else {
        nearsearch(p->eqkid, *s ? s + 1 : s, (*s == p->s) ? d : d - 1);
    }  
}

搜索引擎输入bin, 然后相应的找出所有以bin开头的前缀匹配这样类似的结果.比如bing,binha,binb 就是找出所有前缀匹配的结果.

void presearch(Tptr p, char *s) //s 是想要找的前缀
{
    if (p == NULL)
        return;
    if (*s < p->s) {
        presearch(p->lokid, s);
    } else if (*s > p->s) {
        presearch(p->hikid, s);
    } else {
        if (*(s + 1) == '\0') {
            traverse(p->eqkid); // 遍历这个节点,也就是找出包含这个节点的所有字符
            return ;
        } else {
            presearch(p->eqkid, s + 1);
        }
    }
}

总结

1.Ternary search tree 效率高而且容易实现
2.Ternary search tree 大体上效率比hash来的快,因为当数据量大的时候hash出现碰撞的几率也会大,而Ternary search tree 是指数增长
3.Ternary search tree 增长和收缩很方便,而 hash改变大小的话则需要拷贝内存重新hash等操作
4.Ternary search tree 支持模糊匹配,哈密顿距离查找,前缀查找等操作
5.Ternary search tree 支持许多其他操作,比如字典序输出所有字符串等,trie也能做,不过很费时.

参考:http://drdobbs.com/database/184410528?pgno=1

1 2 3 … 10